fmincon Current Step Size

I'm pretty much confused with the behavior of fmincon function (interior point algorithm). I want to minimize some custom nonlinear function (.m file), with very simple linear limits - all the variables should be greater than or equal to zero (blo=zeros(...)). The function also provides correct gradients, so the optimization job should be easy.

More details about the system:

• x is vector of about 400 elements, with initial values of magnitude 1e37
• function value after the first iteration is about 150
• partial derivatives returned by the function are pretty small (but correct!). dx(1)=-3e-36, dx(end)=+8e-11, while others are much smaller (negative, in magnitudes 1e-40 to 1e-47).

fmincon does just two iterations (two function executions), and successfully exits with the message:

"fmincon stopped because the size of the current step is less than the default value of the step size tolerance and constraints are satisfied to within the default value of the constraint tolerance."

Obviously the curvature is not steep enough, so fmincon satisfies its criteria in just two iterations. But instead it should use significantly larger "current step size" to do the job appropriately. I've gave my best to find a way to force fmincon to use greater step, to play around with other parameters, to tweak it by multiplying derivatives with 1e50, but with no luck. It always finishes in few iterations with the function value of 150.

Funny thing is that I was able to write few lines iterative program and do the job "manually", and after about 1,000 iterations I've got function value of 0 (plus 1e-12).

How to make fmincon to actually find the minimum (optimum)?

Any help would be appreciated.

Thanks!

Answer 1

[Fat Dragon]

The only solution that worked for me was to provide user-defined Hessian function. Although it took me few weeks to calculate and code second derivatives, since the software will be used many times by many people - it was worthwhile. With correct Hessian function fmincon works like charm.

Btw. I believe that there is a room for improving fmincon algorithm when it comes to "step size". It was obvious in my case when it stalled at certain value. Although with each subsequent iteration the value of the objective function was constantly decreasing (without oscillations), the rate was way too slow. I suggest adding some logic that will increase step size when objective function constantly decreasing without oscillations.

Thanks

Answer 2

[Alan Weiss]

It sounds to me as if the scaling of your problem is an issue, with these huge x values and tiny derivative values. Is it possible to scale your x coordinates by, say, 1e37?

 function [f,gradf] = scaledfn(x)
 f = oldfun(1e37*x); % oldfun is your former objective function
 g = oldgrad(1e37*x)*1e37; % oldgrad is your former gradient
 end

I wonder if patternsearch would work any better. I suggest that you try giving TolFun = 0 in any case, whether you use patternsearch or fmincon, so the solver doesn't stop right away.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Fat Dragon]

First I want to thank you for trying to help, and to apologize for my late answer - I wanted to find the solution before answering.

Regarding your suggestion to try patternsearch function: as far as I know it does not accepts user supplied gradient, and if so it cannot be the most appropriate solution. No gradientless method can be more efficient than one with correct gradients supplied. For this reason I haven't gave it a try.

Regarding suggested scaling: it helped a bit - fmincon did about 20 meaningful iterations and successfully decreased the objective function to 1e33 (in the new version I have amplified the objective). But after that it starts stalling - it continues to run and to decrease the objective but way too slow. After hours of work the objective function was still of 1e33 magnitude. Just for comparison, the script I have developed successfully decreases the objective function to 1e28 very fast. (The reason for me not to use my script is that it can work only with unconstrained problem, while the software I am developing must support nonlinear constraints also.)

Another thing is that although I've set TolFun = 0, it still happens that it finishes too early with "current step smaller than..." message.

I will describe the final solution below.

Thanks!