Why are the first order necessary conditions of optimality not satisfied for this problem?

I am trying to find the optimal Lagrange multipliers for this problem:

min 100*(V4 - V2 + (V1 - V3)^2)^2 + (V3 - V1 + 1)^2
s.t 
[V5 - (V1 - V3)*(V2 - V4) + 1;  V3 - V1 + V6 - (V2 - V4)^2; V1 - V3 + V7 - 1/2]=0
[V1;V2;V3;V4;V5;V6;V7] >=0

The optimal minimizer that I am getting is:

V =

      0.5000
      2.0687
      0.0000
      0.0687
     -0.0000
      4.5000
      0.0000

MATLAB is giving me the Lagrange multipliers:

      lambda.eqnonlin=

1.0e+03 *

       -0.7000
        0.0000
        1.7510

    lambda.lower= 

1.0e+03 *

           0
           0
           0
           0
      0.7000
           0
      1.7510

However, when I take the gradient of the Lagrangian function at the optimal solution V, the answer is not 0!

Any idea why?

[Matt J]

Floating point precision? Inexact convergence? What did you get for the Lagrangian gradient and what code did you use to calculate it?

[Del]

I used the gradient of the Lagrangian formula:

gradient_f(V)+((lambda.eqnonlin')*Jacobian_h (V))+(lambda.lower'* (-I))

where h is the vector function of the equality constraints; and I is the identity matrix.

for LAMBDA= lambda.eqnonlin, and MU= lambda.lower, it's giving me the answer:

grad_f+((LAMBDA')*Jacobian_h)-MU' =

ans =

   1.0e+03 *

    2.8000    0.7000   -2.8000   -0.7000   -1.4000    0.0000   -0.0000

which as you can see is not close to the zero vector (within any reasonable tolerance).

[Matt J]

What solver are you using? Are you sure that the optimization succeeded/completed? What exitflag did it return? Are you sure your gradient and Jacobian functions are correct (it would help to show them)? Did the optimization use them or did you use the default finite difference differentiation?

[Del]

I used fmincon, starting with the value V0=zeros(7,1), it returned the exitflag 4. I checked the gradient and jacobian functions by hand, and they are correct. I only used fmincon to find the minimizer V, and to find the optimal Lagrange multipliers. I just calculated the gradient and Jacobian so that I could use them in the gradient lagrangian function, and I was hoping to get 0.

[Del]

Here is what was written: "fmincon stopped because the size of the current search direction is less than twice the default value of the step size tolerance and constraints are satisfied to within the default value of the constraint tolerance."

and

grad_f_V'=

 2*V1 - 2*V3 + 200*(2*V1 - 2*V3)*(V4 - V2 + (V1 - V3)^2) - 2
                           200*V2 - 200*V4 - 200*(V1 - V3)^2
 2*V3 - 2*V1 - 200*(2*V1 - 2*V3)*(V4 - V2 + (V1 - V3)^2) + 2
                           200*V4 - 200*V2 + 200*(V1 - V3)^2
                                                           0
                                                           0
                                                           0

Jacobian_h_V =

[ V4 - V2,     V3 - V1, V2 - V4,     V1 - V3, 1, 0, 0]
[      -1, 2*V4 - 2*V2,       1, 2*V2 - 2*V4, 0, 1, 0]
[       1,           0,      -1,           0, 0, 0, 1]

Answer 1

[Matt J]

Here is what was written: "fmincon stopped because the size of the current search direction is less than twice the default value of the step size tolerance and constraints are satisfied to within the default value of the constraint tolerance."

which means you didn't converge with respect to the first order optimality measure. Your objective is a variant of Rosenbrock, so presumably it's supposed to be hard to converge to a proper solution. Try increasing MaxIter to something ridiculously large and make sure you get an exitflag=1.

[Del]

alright, how to change/Increase MaxIter ?

[Del]

Here is what I am typing:

options = optimset( 'MaxIter', Inf);
V0=zeros(7,1);lb=zeros(7,1);

[V,fval,exitflag,output,lambda,grad]  =  fmincon(@function_TEST2_V,V0,[],[],[],[],lb,[],@constraints_TEST2_V)

I am not sure if that is what I am supposed to do, however, it is not making any difference, the exit flag is still 4

[Matt J]

Try also setting TolX=0 and MaxFunEvals=Inf.