Finding a minimum

[krtxmrtz]

I have a function f:R² -> R². The variables are x,y, the coordinates of a point on a plane, and the function assigns 2 "properties" to each point that can be calculated through more or less complex algorithms so that to each pair (x,y) of coordinates corresponds a unique pair (v,w) where I have called v=f₁ and w = f₂.

I'm trying to find a point (x,y) where the values of both u and v are as low as possibly achievable with the minimization algorithm, probably not absolute minimums. The way I do is I select a large number of randomly selected points and at each one of them test for the v and w values. What I haven't clearly decided is the most convenient approach in order to minimize both values. For only one value, clearly you accept a point if it has v (or w) less than the previous value, otherwise reject the point. For the 2 values, you may find e.g. a point with lower v than the previous point but maybe higher w. Therefore, should I try to minimize something like u*v? Or maybe Sqrt(u² + v²)? Or some other quantity? The range of u is the interval [0,1] but w may take values from 0 to w_max where w_max is also a function of the position (x,y).

[zaza]

Can you use something like the downhill simplex method?

[krtxmrtz]

Can you use something like the downhill simplex method?

I don't know because I never took time to learn it. Maybe it's a good time now, but I need to know if it can be applied to my problem, given that the explicit form of the f is not known. Rather, u and v are calculated for each point on a grid from a set of numeric values (call these "z") contained in a matrix where each column (row) corresponds to a value of x (y).
I mean, you certainly end up with explicit values of v and w at each point, but you can't (at least easily, as v and w are determined through a quite complex algorithm) calculate, say, the derivatives in case these are necessary.

[VBAhack]

A few comments:

1. As to what to minimize, I don't think there is a universal answer. I think it depends on the values that v & w can take. You'll probably need to find a few examples by whatever means and study them to convince yourself which form the residual function should take: v*w or v² + w², etc.

2. Re derivatives, some optimization methods don't need them, but derivatives can be estimated if v=f(x,y) and w=f(x,y) are smooth and continuous by using central or forward differencing.

3. I saw a clever random optimization algorithm that successively zeroed in on the values that produce minimin results. It went something like this. Take x random points within pre-set bounds of the independent variables. Rank the results in order of increasing objective function. Pick the best y cases, determine new bounds on independent variables (hopefully smaller bounds than originally), then repeat until some sort of convergence criteria is met. If you want, I could dig around and find the reference. The thing is a function to minimize is needed, which takes you back to 1.

4. What you really have is simultaneous minimization of two functions, v and w that have the same independent variables.

[krtxmrtz]

A few comments:

1. As to what to minimize, I don't think there is a universal answer. I think it depends on the values that v & w can take. You'll probably need to find a few examples by whatever means and study them to convince yourself which form the residual function should take: v*w or v² + w², etc.

2. Re derivatives, some optimization methods don't need them, but derivatives can be estimated if v=f(x,y) and w=f(x,y) are smooth and continuous by using central or forward differencing.

3. I saw a clever random optimization algorithm that successively zeroed in on the values that produce minimin results. It went something like this. Take x random points within pre-set bounds of the independent variables. Rank the results in order of increasing objective function. Pick the best y cases, determine new bounds on independent variables (hopefully smaller bounds than originally), then repeat until some sort of convergence criteria is met. If you want, I could dig around and find the reference. The thing is a function to minimize is needed, which takes you back to 1.

4. What you really have is simultaneous minimization of two functions, v and w that have the same independent variables.

Since the resulting value of the function is a vector with 2 components, I believe the best policy is try to minimize v² + w², i.e. the square of the modulus. This is actually the question I was pondering when I started this thread.

About the optimization algorithm, my function is so much jagged that you can have loads of local minimums all over the pre-set bounds of (x,y). That's why I also use random points, as you can read in my first post. Even if the number of random points is limited (to avoid large computation times), the result is likely to be a "good" minimum in the sense that new runs of the algorithm would produce only slightly better results if any at all.