hairy optimization problem
I have a function f(x,y) which produces N values [v1,v2,v3 .... vN] where some of the values are None (only found after evaluation) each evaluation of "f" is expensive and N is large. I want N x,y pairs which produce the optimal value in each column. A brute force approach would be to generate [v11,v12,v13,v14 ....] [v21,v22,v23 ....... ] etc then locate the maximum of each column. This is far too slow ......Any other ideas?
Hi Mathew, You could use Newton's method to optimize for each vi sequentially. If you have an expression for the jacobian, it's even better. What I'd do is write a class with a method f(self, x, y) that records the result of f(x,y) each time it is called. I would then sample very coarsely the x,y space where I guess my solutions are. You can then select the x,y where v1 is maximum as your initial point for Newton's method and iterate until you converge to the solution for v1. Since during the search for the optimum your class stores the computed points, your initial guess for v2 should be a bit better than it was for v1, which should speed up the convergence to the solution for v2, etc. If you have multiple processors available, you can scatter function evaluation among them using ipython. It's easier than it looks. Hope someone comes up with a nicer solution, David On Wed, May 6, 2009 at 3:16 PM, Mathew Yeates <myeates@jpl.nasa.gov> wrote:
I have a function f(x,y) which produces N values [v1,v2,v3 .... vN] where some of the values are None (only found after evaluation)
each evaluation of "f" is expensive and N is large. I want N x,y pairs which produce the optimal value in each column.
A brute force approach would be to generate [v11,v12,v13,v14 ....] [v21,v22,v23 ....... ] etc
then locate the maximum of each column. This is far too slow ......Any other ideas?
_______________________________________________ Numpydiscussion mailing list Numpydiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
hi mathew, 1) what does it mean if a value is None? I.e., what is larger: None or 3? Then first thing I would do is convert the None to a number. 2) Are your arrays integer arrays or double arrays? It's much easier if they are doubles because then you could use standard methods for NLP problems, as for example Newton's method as suggested above. But of the sound of it you could possibly enumerate over all possible solutions. This may possibly be formulated as a linear mixed integer program. This is also a hard problem, but can be usually solved quite fast nowadays. In the worst case, you might have to use algorithms as genetic algorithms or a stochastic search as e.g. simulated annealing which often do not give good results. 3) It is not clear to me what exactly you are trying to maximize. As far as I understand you actually have N optimization problems. This is very unusual! Typically the problem at hand can be formulated as *one* optimization problem. Could you tell us, what exactly your problem is and why you want to solve it? I am pretty sure that there is a much better approach than solving N optimization problems. It is good practice to first find the category of the optimization problem. There are quite a lot of them: linear programs, nonlinear programs, mixed integer linear programs, .... and they can further be distinguished by the number of constraints, type of constraints, if the objective function is convex, etc... Once you have identified all that for your given problem, you can start looking for a standard solver that can solve your problem. On Thu, May 7, 2009 at 5:59 AM, David Huard <david.huard@gmail.com> wrote:
Hi Mathew,
You could use Newton's method to optimize for each vi sequentially. If you have an expression for the jacobian, it's even better.
What I'd do is write a class with a method f(self, x, y) that records the result of f(x,y) each time it is called. I would then sample very coarsely the x,y space where I guess my solutions are. You can then select the x,y where v1 is maximum as your initial point for Newton's method and iterate until you converge to the solution for v1. Since during the search for the optimum your class stores the computed points, your initial guess for v2 should be a bit better than it was for v1, which should speed up the convergence to the solution for v2, etc.
If you have multiple processors available, you can scatter function evaluation among them using ipython. It's easier than it looks.
Hope someone comes up with a nicer solution,
David
On Wed, May 6, 2009 at 3:16 PM, Mathew Yeates <myeates@jpl.nasa.gov> wrote:
I have a function f(x,y) which produces N values [v1,v2,v3 .... vN] where some of the values are None (only found after evaluation)
each evaluation of "f" is expensive and N is large. I want N x,y pairs which produce the optimal value in each column.
A brute force approach would be to generate [v11,v12,v13,v14 ....] [v21,v22,v23 ....... ] etc
then locate the maximum of each column. This is far too slow ......Any other ideas?
_______________________________________________ Numpydiscussion mailing list Numpydiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
_______________________________________________ Numpydiscussion mailing list Numpydiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
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
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 "rinserepeat" 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 "fixedpoint" 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 _______________________________________________ Numpydiscussion mailing list Numpydiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
 View this message in context: http://www.nabble.com/hairyoptimizationproblemtp23413559p23428578.html Sent from the Numpydiscussion mailing list archive at Nabble.com.
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 "rinserepeat" 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 "fixedpoint" 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 _______________________________________________ Numpydiscussion mailing list Numpydiscussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpydiscussion
David Huard wrote:
Hi Mathew,
You could use Newton's method to optimize for each vi sequentially. If you have an expression for the jacobian, it's even better. Here's the problem. Every time f is evaluated, it returns a set of values. (a row in the matrix) But if we are trying to find the minimum of the first column, we only care about the first value in the set. This is really N optimization. problems I want to perform simultaneously.
Find N (x,y) values where x1,y1 minimizes f in the first column, x2,y2 minimizes f in the second column, etc. And ... doing this a column at a time is too slow (I just did a quick calculation and my brute force method is going to take 30 days!)
What I'd do is write a class with a method f(self, x, y) that records the result of f(x,y) each time it is called. I would then sample very coarsely the x,y space where I guess my solutions are. You can then select the x,y where v1 is maximum as your initial point for Newton's method and iterate until you converge to the solution for v1. Since during the search for the optimum your class stores the computed points, your initial guess for v2 should be a bit better than it was for v1, which should speed up the convergence to the solution for v2, etc.
If you have multiple processors available, you can scatter function evaluation among them using ipython. It's easier than it looks.
Hope someone comes up with a nicer solution,
David
On Wed, May 6, 2009 at 3:16 PM, Mathew Yeates <myeates@jpl.nasa.gov <mailto:myeates@jpl.nasa.gov>> wrote:
I have a function f(x,y) which produces N values [v1,v2,v3 .... vN] where some of the values are None (only found after evaluation)
each evaluation of "f" is expensive and N is large. I want N x,y pairs which produce the optimal value in each column.
A brute force approach would be to generate [v11,v12,v13,v14 ....] [v21,v22,v23 ....... ] etc
then locate the maximum of each column. This is far too slow ......Any other ideas?
_______________________________________________ Numpydiscussion mailing list Numpydiscussion@scipy.org <mailto:Numpydiscussion@scipy.org> http://mail.scipy.org/mailman/listinfo/numpydiscussion
participants (4)

David Huard

Ken Basye

Mathew Yeates

Sebastian Walter