Why do I obtain incorrect Lagrange multipliers when using the LINPROG function within the Optimization Toolbox 2.2 (R13)?

The following example shows that LINPROG may return incorrect Lagrange multipliers (it can be shown that the outputs "x" and "lambda" do not satisfy the optimality conditions because "lambda" is wrong).

clear;

f=[-1039.75;-914.25;-1304;-4540;-7460;-297;-2000;-300;-1200;-8];

A=[0 0 1 0 0 1 0 1 0 0;0 0 0 1 1 0 1 0 1 0;-2190 -3650...

   14016 23360 35040 0 0 0 0 0;91.25 91.25 2100 1600 2800 0 0 0 0 1];

b=[1;1;0;3000];

lb=zeros(10,1);

ub=[inf;inf;inf;inf;inf;inf;inf;inf;inf;inf];

[x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb,ub);

I find that the Langrange multipliers returned within "lambda" violate the optimality conditions, and are therefore wrong.

Answer 1

[MathWorks Support Team]

This is a bug in the LINPROG function within the Optimization Toolbox 2.2 (R13) in the way it calculates the Lagrange multipliers using the large-scale method. This bug has been fixed in the LINPROG function within the Optimization Toolbox 2.3 (R13SP1).

As a workaround, either upgrade to the newest version of the Optimization Toolbox, or use the medium-scale simplex method. The medium-scale method can be specified using an options argument. For example,

clear;

f = [-1039.75;-914.25;-1304;-4540;-7460;-297;-2000;-300;-1200;-8];

A = [0 0 1 0 0 1 0 1 0 0;0 0 0 1 1 0 1 0 1 0;-2190 -3650 ...

14016 23360 35040 0 0 0 0 0;91.25 91.25 2100 1600 2800 0 0 0 0 1];

b = [1;1;0;3000];

lb = zeros(10,1);

ub = [inf;inf;inf;inf;inf;inf;inf;inf;inf;inf];

options = optimset('LargeScale', 'off');

[x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb,ub,[],options);

In this example, we find the LINPROG function returns Lagrange multipliers that satisfy the optimality constraints.