[Numpy-discussion] hairy optimization problem

Ken Basye kbasye1@jhu....
Thu May 7 10:35:48 CDT 2009


Hi Mathew,
   Here are some things to think about:  First, is there a way to decompose
'f' so that it computes only one or a subset of K values, but in 1/N ( K/N)
time?  If so, you can decompose your problem into N single optimizations. 
Presumably not, but I think it's worth asking.  Second, what method would
you use
if you were only trying to solve the problem for one column?  
   I'm thinking about a heuristic solution involving caching, which is close
to what an earlier poster suggested.  The idea is to cache complete (length
N) results for each call you make.  Whenever you need to compute f(x,y),
consult the cache to see if there's a result for any point within D of x,y
(look up "nearest neighbor search").  Here D is a configurable parameter
which will trade off the accuracy of your optimization against time.  If
there is, use the cached value instead of calling f.  Now you just do the
"rinse-repeat" algorithm, but it should get progressively faster (per
column) as you get more and more cache hits.
  Possible augmentations:  1) Within the run for a given column, adjust D
downward as the optimization progresses so you don't reach a "fixed-point"
to early.  Trades time for optimization accuracy.    2) When finished, the
cache should have "good" values for each column which were found on the pass
for that column, but there's no reason not to scan the entire cache one last
time to see if a later pass stumbled on a better value for an earlier
column.  3) Iterate the entire procedure, using each iteration to seed the
starting locations for the next - might be useful if your function has many
local minima in some of the N output dimensions.



Mathew Yeates wrote:
> 
> Sebastian Walter wrote:
>> N optimization problems. This is very unusual! Typically the problem
>> at hand can be formulated as *one* optimization problem.
>>
>>   
> yes, this is really not so much an optimization problem as it is a 
> vectorization problem.
> I am trying to avoid
> 1) Evaluate f over and over and find the maximum in the first column. 
> Store solution 1.
> 2) Evaluate f over and over and find the max in the second column. Store 
> solution 2.
> Rinse, Repeat
> _______________________________________________
> Numpy-discussion mailing list
> Numpy-discussion@scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
> 
> 

-- 
View this message in context: http://www.nabble.com/hairy-optimization-problem-tp23413559p23428578.html
Sent from the Numpy-discussion mailing list archive at Nabble.com.



More information about the Numpy-discussion mailing list