Very small feasibility value but very large first-order optimality value

I am solving a large-scale optimzation problem (over 8000 decision variables) with fmincon using interior-point algorithm. My problem consists of a nonlinear objective function and linear as well as nonlinear equality constraints. Upon termination, I get a solution which satisfies all my constraints, but has really poor first-order optimality. Upon further digging, I found the large optimality value is due to the lagrange multipliers (for both the linear and nonlinear equality constraints) having very large values themselves (over 1e28).

Can somebody please help me understand why is this the case? And is there any way to improve the first-order optimality value here? I will appreciate any pointers in this regard. I have attached a screenshot to show the aforementioned problem. Thank you for your time.

Best,

Chaitanya

Answer 1

[Alan Weiss]

This is a very interesting issue; I have never seen anything quite like it before. Apparently, you are providing gradients for both the objective and nonlinear constraints. I would first look there to see whether those nonlinear functions are correct--it is notoriously difficult to get them correct without using a symbolic approach.

If everything is correct, then you might try rerunning the optimization from the solution point but this time with modified options. I'd try HessianApproximation = 'finite-difference' and maybe try setting ScaleProblem to true. And certainly set CheckGradients to true.

Alan Weiss

MATLAB mathematical toolbox documentation

[Chaitanya Awasthi]

Hi Alan,

You are indeed correct in saying that I am providing the gradients for the cost function and the nonlinear constraints. To the best of my ability, I can also attest that my constraint functions are coded correctly.

Also, prior to asking my question, I had already set the ScaleProblem to true and checked my gradients using CheckGradients. However, the one thing that I did not think about was using a different hessian approximation (I had been using lbfgs due to large-scale nature of my problem). As soon as I did that, not only did I get a much better solution, my first-order optimality decreased enormously too (please see the screenshot). I got similarly great results when I instead used the bfgs approximation. Thank you so much for helping me out by pointing me in this direction.

However, a question still remains as to why the lbfgs approximation was so terrible. Do you have any thoughts on this matter?

Answer 2

[Matt J]

That can happen if your objective function or constraints are not continuously differentiable, e.g.,

fmincon(@(x)sqrt(abs(x)),1,[],[],[],[],[],[],[],...
           optimoptions('fmincon','Display','iter','Algorithm','interior-point'))

                                            First-order      Norm of
 Iter F-count            f(x)  Feasibility   optimality         step
    0       2    1.000000e+00    0.000e+00    5.000e-01
    1       4    7.071068e-01    0.000e+00    7.071e-01    5.000e-01
    2       8    6.195833e-01    0.000e+00    8.070e-01    8.839e-01
    3      10    2.953197e-01    0.000e+00    1.693e+00    4.711e-01
    4      13    2.688914e-01    0.000e+00    1.859e+00    1.595e-01
    5      15    1.057901e-01    0.000e+00    4.726e+00    8.349e-02
    6      19    6.155009e-02    0.000e+00    8.123e+00    1.498e-02
    7      22    3.076759e-02    0.000e+00    1.625e+01    4.735e-03
    8      25    2.513630e-02    0.000e+00    1.989e+01    1.578e-03
    9      27    1.539175e-02    0.000e+00    3.248e+01    8.687e-04
   10      30    5.700689e-03    0.000e+00    8.770e+01    2.694e-04
   11      34    4.080285e-03    0.000e+00    1.225e+02    4.915e-05
   12      36    3.463278e-03    0.000e+00    1.443e+02    2.864e-05
   13      38    1.870291e-03    0.000e+00    2.671e+02    1.549e-05
   14      41    1.237146e-03    0.000e+00    4.032e+02    5.029e-06
   15      43    1.222445e-03    0.000e+00    4.080e+02    3.025e-06
   16      45    1.645466e-04    0.000e+00    2.707e+03    1.521e-06
   17      56    1.193397e-04    0.000e+00    3.448e+03    4.132e-08
   18      58    9.435727e-05    0.000e+00    4.022e+03    2.315e-08
   19      60    5.965666e-05    0.000e+00    5.114e+03    1.246e-08
   20      62    5.845842e-05    0.000e+00    5.160e+03    6.976e-09
   21      64    9.283106e-06    0.000e+00    7.593e+03    3.504e-09
   22      74    6.648107e-06    0.000e+00    7.758e+03    1.304e-10
   23      76    4.657401e-06    0.000e+00    7.885e+03    6.589e-11

Local minimum possible. Constraints satisfied.

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

ans = 2.1691e-11

[Chaitanya Awasthi]

Hi Matt,

Thank you for your response. I am not sure if you have seen my reply to Alan's anwer, but if non-differentiability was indeed an issue, why would it only affect the lbfgs hessian approximation and not finite-difference or bfgs approximation?

[Matt J]

I don't think that's the issue. If you were to use, as your initial x0, the solution that you originally obtained with lbfgs, I'd be willing to bet that the algorithm will stay there, no matter what Hessian approximation you use.

[Chaitanya Awasthi]

Hi Matt,

I have got some very surprising results for you. Like you asked, I used the solution of lbfgs as an initial point for not just finite-difference hessian approximation but also (another round of) lbfgs hessian approximation. Interestingly, in both situations, the solver does not stop at the first step, rather it further decreases the cost function. I was less surprised it happens in the case of finite-difference hessian but quite surprised it happened even for lbfgs. Please see the screenshots below. Do you have any thoughts what is going on here?

Hessian approximation: lbfgs

Hessian approximation: finite-difference