Why is fmincon ending in points it knows are sub-optimal?

So I'm running fmincon on some complex function.

                                            First-order      Norm of
 Iter F-count            f(x)  Feasibility   optimality         step
    0       6    1.264764e+04    0.000e+00    6.529e+09
    1      13   -3.111363e+04    0.000e+00    1.043e+10    1.485e+01
    2      19   -3.413651e+04    0.000e+00    7.615e+09    8.769e+03
    3      25   -3.861130e+04    0.000e+00    1.613e+09    6.264e+02
    4      34   -3.840241e+04    0.000e+00    1.376e+09    9.530e-03
    5      41   -3.843143e+04    0.000e+00    5.582e+09    9.954e-01

I get this and it ends there at Iteration 5, returning the parameter values of that iteration and calling it an optimum. However, clearly, iteration 3 had found a superior feasable solution.

Any clue as to why this is happening? And how to stop that? The program that ultimately calls on fmincon is a complex code written by someone else, that I don't understand fully. Could he have put some option to stop fmincon from returning the values at iteration 3 instead of the ones at the last iteration?

Answer 1

[Alan Weiss]

It appears that the first-order optimality measure is nowhere near zero, so I am sure that fmincon does not claim that it reached a minimum. It probably stopped because the norm of the step was too small, meaning it could not proceed. For suggestions on what to do in this case, see Local Minimum Possible.

Alan Weiss

MATLAB mathematical toolbox documentation

[Patrick Aoun]

You're absolutely right. I cheated. I only sent a part of the whole log.

Thing is, what I'm describing has happened before. Right now the optimisation is not done, but it very often ends at a point that is inferior to a previous iteration.

The idea is the same though. It starts optimizing, goes through some feasable points that have some relatively low f(x), then it ends on a point for which the f(x) is higher than a previous f(x).

Would that happen if fmincon stops for a reason other than reaching a minimum?

As of right now:

                                            First-order      Norm of
 Iter F-count            f(x)  Feasibility   optimality         step
    0       6    1.264764e+04    0.000e+00    6.529e+09
    1      13   -3.111363e+04    0.000e+00    1.043e+10    1.485e+01
    2      19   -3.413651e+04    0.000e+00    7.615e+09    8.769e+03
    3      25   -3.861130e+04    0.000e+00    1.613e+09    6.264e+02
    4      34   -3.840241e+04    0.000e+00    1.376e+09    9.530e-03
    5      41   -3.843143e+04    0.000e+00    5.582e+09    9.954e-01
    6      47   -3.835305e+04    0.000e+00    3.192e+09    1.510e+00
    7      53   -2.526914e+04    0.000e+00    8.085e+09    3.437e-01
    8      59   -2.493197e+04    0.000e+00    1.416e+10    1.953e+02
    9      65   -3.688002e+04    0.000e+00    9.303e+09    1.534e+02
   10      72   -3.683397e+04    0.000e+00    4.620e+09    1.041e+01
   11      83   -2.981059e+04    0.000e+00    1.402e+09    3.818e-02
   12      95   -2.926089e+04    0.000e+00    2.164e+10    1.468e-02
   13     103   -2.935060e+04    0.000e+00    4.057e+10    8.653e-02

[Alan Weiss]

It seems that your problem has 6 dimensions, and that the estimated derivatives are quite high. Perhaps you could try patternsearch starting from either your original initial point, or from the best point that fmincon encountered. The reason I suggest this is that your problem looks poorly scaled, and instead of going through the pain of scaling it better, why not just throw patternsearch at it? With only 6 dimensions, patternsearch won't be terrible. You might want to start it with a large initial mesh size, because fmincon took some large steps early.

Alan Weiss

MATLAB mathematical toolbox documentation

[Patrick Aoun]

Wow that's uncanny. You're right again. You figured out the scaling problem and the 6 dimensions using the fact that F-count jumps by 6 and Norm of step is kind of all over the place?

Yes indeed, I have 6 dimensions and one of those has a much much larger scale than the others.

I didn't know that was confusing for the solver but it makes sense. I'll look into patternsearch.

Huge thanks

[Matt J]

The idea is the same though. It starts optimizing, goes through some feasable points that have some relatively low f(x), then it ends on a point for which the f(x) is higher than a previous f(x).

As I recall (though Alan may correct me), not all fmincon algorithms are guaranteed monotonic. Furthermore, there are various criteria that fmincon uses to decide to stop, but the whole history of previous x and f(x) visited are not taken into consideration by any of them. Beyond local criteria, like the first order optimality measure, only progress since the most recent iteration is considered.

[Patrick Aoun]

Oh well if that's the case that would definitely answer the original question.

[Alan Weiss]

Matt is quite correct that fmincon does not enforce monotonicity of the objective function during its iterations, and does not use the whole history in deciding when to stop, but uses only the current iteration's data.

And Patrick, I'm tickled that you were impressed by my analysis of your problem when I had no access to any problem details. But I see these types of optimization issues often--after all, it is my job!

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 2

[Matt J]

However, clearly, iteration 3 had found a superior feasable solution.

That is not clear because the "Feasibility" metric is only displayed to a few decimal places. My first thought is to check the feasibility values to higher precision.

There is in any case rather little information here with which to diagnose. We would need to have the exitflag and other output information from fmincon to really make good guesses.

The program that ultimately calls on fmincon is a complex code written by someone else, that I don't understand fully. Could he have put some option to stop fmincon from returning the values at iteration 3 instead of the ones at the last iteration?

The input would definitely also help with diagnosis. You could set a breakpoint at the line of the code where fmincon is called. Then save all of its inputs to the base workspace (e.g., with this ) so that they can be run and studied separately.

[Patrick Aoun]

Thanks for the answer

Wouldn't feasability write something like 1.000e-07 if it was not 0? As for the output options you're right I'll provide them soon.

The breakpoint in front of the fmincon is clever I'm doing this right now thanks.