nonlinear programming - first order conditions

Hi all

I want to solve the following problem: max: f(x)=x'Ax+b'x, where x=[x1;x2;x3],

A=[2 -5 -10;-5 3 -5;-10 -5 4] and b'=[400 295 55]

under the linear constraints: 2x1+x2+x3=40, 3x1-x2+x3=50, x1,x2,x3>=0. Solving the above problem with fmincon provides the following optimum vector:

x*=[18;4;0;169.8;30.8] (the last two values are the lagrange multipliers).

However when I try to solve the problem by hand there is only one vector: x*=[10;0;20;5;10] that sutisfies the first order conditions: gradL=0, where gradL is the 5x1 gradient vector of the lagrangian function. The vector that MATLAB provides is a better local minimum than the one calculated by hand, thus I was wondering how MATLAB calculates its optimum vector? Does it use other conditions than gradL=0 and if yes, which are they? PS: MATLAB's optimum vector sutisfies the 4 out of five equations of the first order conditions, it violates only the third equation: dL/dx(3) = 0.

I provide my codes for the interested reader:

function fval=TR2(x)
y=2*x(1)^2+3*x(2)^2+4*x(3)^2-10*x(1)*x(2)-10*x(2)*x(3)-20*x(1)*x(3)+400*x(1)+295*x(2)+55*x(3);
fval=-y;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

x0=[12 1 15]';
Aeq=[2 1 1;3 -1 1];
beq=[40 50]';
lb=-10^(-10)*ones(3,1);
options = optimset('Algorithm','Interior-Point','Display','iter');
[x,fval,exitflag,output,lambda,grad,hessian] = fmincon('TR2',x0,[],[],Aeq,beq,lb,[],[],options);

thanks!

Answer 1

[Marcelo Marazzi]

Hi Manthos:

The fmincon algorithm interior-point is not entirely based on solving the optimality conditions. Please see this section of the documentation for an overview of the algorithm.

Because your problem is a QP you may want to consider the interior-point-convex algorithm in quadprog. Notice that this solver assumes that the objective is of the form 1/2 x'*A*x + b'*x, so you would have multiply your Hessian matrix by 2 to eliminate the 1/2 factor. Also, your QP is non-convex so fmincon interior-point may be the best algorithm after all.

In your description you show the values of two Lagrange multipliers, which I assume are the ones associated with the linear equality constraints. However, the multipliers associated with the non-negativity constraints also enter the optimality conditions when these inequalities are active, as in the two vector x* that you show (where either the 3rd or 2nd element in x* is zero).

-Marcelo