nonlinear programming - first order conditions
1 次查看(过去 30 天)
显示 更早的评论
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!
0 个评论
回答(1 个)
Marcelo Marazzi
2011-12-20
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
0 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Linear Least Squares 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!