efficient algorithm to find minimum of multivariable function

Question

I have a multivariable function that I wish to minimize. The function has two input arguments, a vector c and a scalar \theta.

Using fmincon in MATLAB to solve the optimization problem for both c and \theta is complicated because certain values of \theta causes numerical errors. However, fixing theta, c can be easily obtained via fmincon without any errors.

So the plan now is to do a brute force approach, i.e. compute c for each value of \theta in the range 1:100 (although the true constraint for \theta is \theta \ge 0) and choose \theta (and the corresponding c) for which the objective value is minimized simply by plugging the estimated parameters back to the objective function.

Now this doesn't sound very efficient to me and I'm wondering if I can employ a bisection method-esque approach so that I would not have to go over all possible values of \theta in the range specified above.

Thanks a lot!

Answer 1

Bisection search over theta will only work if the objective function is convex (or quasiconvex) in theta. Otherwise, you risk finding a local min instead of a global min.

Doing a nested fmincon, as @chipaudette suggests, should work if you choose a solver capable of solving nonconvex optimization problems. (The MATLAB help on this topic is a little vague, but I think the SQP solver should be OK.) But I suspect it will be more efficient just to enumerate over the relevant range of theta, rather than using fmincon for it.

Answer 2

You should be able to let fmincon do you work for you on both c and theta. If it has problems getting a decent result when theta is included, it is likely because the elements in c and theta are of very different scales. You should scale your equations so that all of the variables end up around a value of 1.0. This greatly improves the performance (ie, speed) and accuracy of nearly any numerical optimization code.

So, if you suspect that the final values of c might end up being [1.0 0.001 10.0] and you suspect that theta might end up as [10.0], you would formulate your problem as

>>>>>>>>>>>>>>>>>>>>> in your main program prior to invoking fmincon
c = [1.0 0.001 10.0]
theta = 10.0
foo_x = [c(:);thetha];
scale_fac = [1.0 1000.0 0.1 0.1];
x = foo_x .* scale_fac;  %scale your seed values to be near 1.0

>>>>>>>>>>>>>> inside your function
function err = myfunction(x,scale_fac)
foo_x = x ./ scale_fac;  %de-scale to get back to correct magnitude
c = foo_x(1:3);
theta = foo_x (4);

...rest of your code