[Numpy-discussion] hairy optimization problem

[Mathew Yeates]

Thanks Ken,
I was actually thinking about using caching while on my way into work. 
Might work. Beats the heck out of using brute force. One other question 
(maybe I should ask in another thread) what is the canonical method for 
dealing with missing values?

Suppose f(x,y) returns None for some (x,y) pairs (unknown until 
evaluation). I don't like the idea of setting the return to some small  
value as this may create local maxima in the solution space.

Mathew

Ken Basye wrote:
> 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 at scipy.org
>> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>>
>>
>>     
>
>