Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
fmincon: final result is worse than initial guess
1,274 views
Skip to first unread message
Matthias
Sep 23, 2016, 6:01:08 AM9/23/16
to
Hello,
I'm using fmincon with nonlinear constraints and the sqp algorithm (but also tried interior-point).
I always start the optimization with guaranteed feasibility of the initial guess. But in rare cases the optimization moves through an infeasible area and ends up with a feasible solution being worse than the initial guess. What's going wrong here and how can I prevent from this?
Thank you
Matthias
I'm using fmincon with nonlinear constraints and the sqp algorithm (but also tried interior-point).
I always start the optimization with guaranteed feasibility of the initial guess. But in rare cases the optimization moves through an infeasible area and ends up with a feasible solution being worse than the initial guess. What's going wrong here and how can I prevent from this?
Thank you
Matthias
Alan Weiss
Sep 23, 2016, 9:06:03 AM9/23/16
to
not return the best value that it has seen, but instead returns the
final value where it converged. I entered a report in our tracking
database about your observations.
Meanwhile, I think that the situation is similar to the "Solver Lost
Feasibility" section of the documentation:
http://www.mathworks.com/help/optim/ug/when-the-solver-fails.html#burycb6-1
Perhaps (though not likely) you will find some of those suggestions to
be helpful.
I apologize for this behavior, and assure you that it has our attention.
Alan Weiss
MATLAB mathematical toolbox documentation
Matthias
Sep 23, 2016, 9:42:08 AM9/23/16
to
Alan Weiss <awe...@mathworks.com> wrote in message <ns39bm$5c1$1...@newscl01ah.mathworks.com>...
Thank you Alan for trying to help me.
> ... currently, fmincon does
Is there a chance to get informed by your team, when this issue has been solved?
Matthias
> ... currently, fmincon does
> not return the best value that it has seen, but instead returns the
> final value where it converged.
I know constrained optimization is tricky, but what you say means we have a major bug (!), and we have to be even more careful with optimization results than usually.
> final value where it converged.
Is there a chance to get informed by your team, when this issue has been solved?
Matthias
Alan Weiss
Sep 23, 2016, 9:51:02 AM9/23/16
to
attempts to locate a local optimum. Even if the initial point is better
than the final point, there is no guarantee that the initial point is a
local optimum, whereas the final point is. However, the initial point is
better than the final point, so you could reasonably conclude that
fmincon failed.
In any case, the behavior is undesirable. At the very least, fmincon
could notify you that it reached a final point that is worse than some
other points it found, including the initial point.
And I know that it is frustrating for you. All I can say for sure is, if
we change solver behavior, we will notify everyone in the toolbox
release notes:
http://www.mathworks.com/help/optim/release-notes.html
Bruno Luong
Sep 23, 2016, 2:38:09 PM9/23/16
to
If FMINCON can't decrease the cost function, then it is hopeless. Don't count on minor change of bookeeping smallest value to make it works reliable.
Look at your side, such as make the cost function smoother, more quadratic, less nasty constraints, estimate accurately the first guess, feed fmincon with analytic gradient and hessian.
Look at your side, such as make the cost function smoother, more quadratic, less nasty constraints, estimate accurately the first guess, feed fmincon with analytic gradient and hessian.
Matthias
Sep 28, 2016, 8:24:11 AM9/28/16
to
Hello Bruno
"Bruno Luong" <b.l...@fogale.findmycountry> wrote in message <ns3sqb$gsg$1...@newscl01ah.mathworks.com>...
>
> Look at your side, such as make the cost function smoother, more quadratic,
It's a smooth least squares problem
> less nasty constraints,
With the constraints I've to ensure that a certain matrix (derived from the fit parameters) is positive semidefinite. I checked different criteria. 'Principal minors'-criterion is the most reliable. The nonlinear constraints are the heart of the problem. There's no way to get around.
> estimate accurately the first guess
As mentioned before: I actually have a very good first guess, which in any case fulfils the constraints. The problem is that the algorithm walks to a worse value.
> feed fmincon with analytic gradient and hessian.
I offered analytic gradients now for the objective function as well as for the constraints: impact=0
I still claim that leaving a good point and giving a worse point as final result is a bug!
Matthias
"Bruno Luong" <b.l...@fogale.findmycountry> wrote in message <ns3sqb$gsg$1...@newscl01ah.mathworks.com>...
> If FMINCON can't decrease the cost function, then it is hopeless. Don't count on minor change of bookeeping smallest value to make it works reliable.
why shouldn't I do this?
>
> Look at your side, such as make the cost function smoother, more quadratic,
> less nasty constraints,
With the constraints I've to ensure that a certain matrix (derived from the fit parameters) is positive semidefinite. I checked different criteria. 'Principal minors'-criterion is the most reliable. The nonlinear constraints are the heart of the problem. There's no way to get around.
> estimate accurately the first guess
As mentioned before: I actually have a very good first guess, which in any case fulfils the constraints. The problem is that the algorithm walks to a worse value.
> feed fmincon with analytic gradient and hessian.
I still claim that leaving a good point and giving a worse point as final result is a bug!
Matthias
Bruno Luong
Sep 28, 2016, 10:11:09 AM9/28/16
to
Then I suggest you to submit the BUG report.
Matthias
Sep 29, 2016, 10:54:09 AM9/29/16
to
I think I have some new (but minor) insights:
The problem only occurs, when the first iteration step brings me in the infeasible area. I'd expect that when "HonorBounds" is set to "true" (default) such a step would be rejected and a smaller step would be tested until we remain in the feasible area. However, this is not the case. (Why?)
I did some tests with different settings for "initBarrierParam" (when using 'interior-point') and "DiffMaxChange", but without any success.
When using 'interior-point' I also supplied the Hessian. It took me a while to calculate it, but in the end this didn't fix the problem, also.
What currently works best for me:
When the initial guess is better than the final result, I rerun the optimizer, starting with the final result of the first run. This typically brings me back to where I originally started and it finds a local minimum close to the initial guess.
Matthias
The problem only occurs, when the first iteration step brings me in the infeasible area. I'd expect that when "HonorBounds" is set to "true" (default) such a step would be rejected and a smaller step would be tested until we remain in the feasible area. However, this is not the case. (Why?)
I did some tests with different settings for "initBarrierParam" (when using 'interior-point') and "DiffMaxChange", but without any success.
When using 'interior-point' I also supplied the Hessian. It took me a while to calculate it, but in the end this didn't fix the problem, also.
What currently works best for me:
When the initial guess is better than the final result, I rerun the optimizer, starting with the final result of the first run. This typically brings me back to where I originally started and it finds a local minimum close to the initial guess.
Matthias
homphy...@gmail.com
Jul 1, 2019, 12:01:46 PM7/1/19
to
I had this exact problem but realised that I had a misplaced minus sign in my lower bound criterion for one of the parameters. In effect this translated a "<" into a ">". On the occasion that the parameter transgressed this constraint, the solution spiralled down as above.
0 new messages