Cost functional calculation for global optimization in CUDA -

-

i trying optimize function (say find minimum) n parameters (xn). xi's bound range (for example -200 200) , if parameter leaves range, function goes infinity fast. however, n can large (from 20 60-70) , computing it's value takes long time.

i don't think details about function of big relevance, here some: consists of weighted sum of 20-30 smaller functions (all different), on part consist of sums of dot products under sign of inverse sinusoidal function (arcsin, arccos, arctan, etc). arcsin(x1 . x2) + arcsin(x4 . x7) + ....

the function has many local minima in general, approaches such (naive) conjugated gradients or quasi-newton useless. searching entire domain brute force slow.

my initial idea use sort of massive parallelization in combination genetic algorithm, performs many searches on different spots in domain of function, , @ regular intervals checks whether of searches reached local minima. if yes, compares them , discards results smallest one, , continues search until reasonably small value found.

my 2 questions are:

1) possible implement problem in cuda or similar technology? can cuda compute value of function fast enough?

2) better/faster implement problem on multicore pc (with 12+ cores)?

it possible implement global optimization algorithms on gpus, may have modify algorithms best performance. have implemented half dozen population-based metaheuristics on gpus, , possible excellent speedups relative multi-threaded cpu.

with population-based algorithms iterated on generations, may find population size becomes limiting factor in performance. if objective function not parallelizable, maximum number of parallel threads number of candidate solutions in population. gpus work best with, @ minimum, tens of thousands of simultaneous threads, not practical population-based algorithms due population inertia , other effects.

you can around population limitations extent running multiple instances of optimization in parallel, each starting different random seed. further, can arrange parallel instances communicate on network topology (this island model algorithm), parallel instances can collaboratively evolve solutions complex problems. have implemented in opencl msce thesis.

so overall, here succinct answers questions:

1) yes, can implement in cuda or similar technology. speedup depend on how parallelizable objective function , how many parallel instances want run @ same time. 2) faster implement on cpu, due wider range of existing libraries , fact cpu programming models conceptually simpler gpu models. whether or not "better" depends on value.

this still area of active research, , take longer build working gpu implementation take multicore cpu implementation. if implementation time primary concern, recommend take @ pagmo project (and python bindings pygmo), excellent implementation of island model optimizer wide range of local , global optimization functions included. islands can assigned arbitrary algorithm run independently, , can specify how communicate collaboratively optimize objective function.

http://sourceforge.net/apps/mediawiki/pagmo/index.php?title=main_page

your question within research area, , happy further if need it.


Comments

Post a Comment

Popular posts from this blog

c# - SVN Error : "svnadmin: E205000: Too many arguments" -

-
i trying reposotries using c# code process svncommand = null; var psi = new processstartinfo("svnadmin"); psi.redirectstandardoutput = true; psi.redirectstandarderror = true; psi.useshellexecute = false; psi.arguments= @"dump c:\repositories\myrepo > c:\temp\myrepodumpfile.dump"; using (svncommand = process.start(psi)) { var myoutput = svncommand.standardoutput; var myerror = svncommand.standarderror; debug.write("output :" + environment.newline + environment.newline + myoutput.readtoend() + environment.newline + "error :" + environment.newline + environment.newline + myerror.readtoend()); svncommand.close(); } when use dump command commandline svnadmin dump c:\repositories\myrepo > c:\temp\myrepodumpfile.dump it works fine when try ...
Read more

c# - Copy ObservableCollection to another ObservableCollection -

-
how copy observablecollection item observablecollection without reference of first collection? here observablecollection item value changes affecting both collections. code private observablecollection<ratemodel> _allmetalrate = new observablecollection<ratemodel>(); private observablecollection<ratemodel> _metalrateondate = new observablecollection<ratemodel>(); public observablecollection<ratemodel> allmetalrate { { return this._allmetalrate; } set { this._allmetalrate = value; notifypropertychanged("metalrate"); } } public observablecollection<ratemodel> metalrateondate { { return this._metalrateondate; } set { this._metalrateondate = value; notifypropertychanged("metalrateondate"); } } foreach (var item in metalrateondate) allmetalrate.add(item); what causing , how can solve it? you need clone object referenced item before it's a...
Read more

All overlapping substrings matching a java regex -

-
is there api method returns (possibly overlapping) substrings match regular expression? for example, have text string: string t = 04/31 412-555-1235; , , have pattern: pattern p = new pattern("\\d\\d+"); matches strings of 2 or more characters. the matches are: 04, 31, 412, 555, 1235. how overlapping matches? i want code return: 04, 31, 41, 412, 12, 55, 555, 55, 12, 123, 1235, 23, 235, 35. theoretically should possible -- there obvious o(n^2) algorithm enumerates , checks substrings against pattern. edit rather enumerating substrings, safer use region(int start, int end) method in matcher . checking pattern against separate, extracted substring might change result of match (e.g. if there non-capturing group or word boundary check @ start/end of pattern). edit 2 actually, it's unclear whether region() expect zero-width matches. specification vague, , experiments yield disappointing results. for example: string line = "xx90xx"; strin...
Read more