I got negative Lagrange Multipliers in linprog

Hello,

I got negative Lagrange multipliers in lambda.upper after an successful run of linprog. But as far as I know, the multipliers have to be greater or equal than zero.

Here is my code:

Strassen = [
             1, 8,  9.6, 500;
             8, 7,  6.9, 300;
             7, 3,  7.7, 300;
             7, 9,  5.7, 300;
             8, 9,  8.8,  50;
             1,10, 12.5, 300;
             8,11, 12.5, 500;
             9, 4,  7.4, 200;
             2,10, 12.4, 500;
            10,11,  7.8, 100;
            11, 4, 11.1, 500;
             4,12, 12.5, 400;
            10,14, 14.3, 400;
            11,14,  9.0, 300;
            11,13, 10.1, 200;
            14,13,  8.2, 100;
            13,12,  4.7, 100;
            13, 5, 12.2, 500; % 100;
            12, 5, 11.3, 300;
            14, 6, 10.6, 500;
]; %row: (node_start, node_end, costs, upper_bound)

% build incidence matrix from Strassen(:,1:2)
E = Strassen(:,[1,2]); % matrix of edges (row-wise)

n  = size(E,1); % number of edges
m  = max(max(E)); % largest node = number of nodes (vertices)
Ain = zeros(m,n);
for i=1:n
    Ain(E(i,1),i) = -1; Ain(E(i,2),i) = 1;
end
% now we have our incidence matrix Ain

% set rhs for Ain * x = b
b = [
                  -600;
                  -400;
                   100;
                   200;
                   400;
                   300;
                     0;0;0;0;0;0;0;0;
];


% cost vector
c = Strassen(:,3);

% lower and upper bounds
low = zeros(n,1);
upp = Strassen(:,4);

options = optimoptions('linprog','Algorithm','dual-simplex','display','iter');

% Aufruf des Optimierungsverfahrens
[xstar,fval,exitflag,output,lambda] = linprog(c,[],[],Ain,b,low,upp,[],options);

LP preprocessing removed 0 inequalities, 6 equalities,
9 variables, and 18 non-zero elements.

 Iter      Time            Fval  Primal Infeas    Dual Infeas  
    0     0.008    2.228000e+04   6.928203e+02   0.000000e+00  
    8     0.013    3.845000e+04   0.000000e+00   0.000000e+00  

Optimal solution found.

[lambda.upper, upp-xstar]

ans = 20×2

-20.7000 0 0 50.0000 0 200.0000 0 150.0000 3.8000 0 0 200.0000 0 300.0000 3.6000 0 0 100.0000 -18.9000 0

Can someone explain me this behaviour?

Thank in advance,

Tommy

[Matt J]

Just as concerning, complementary slackness is not satisfied for the interior-point method,

options = optimoptions('linprog','Algorithm','interior-point','display','none');

[xstar,fval,exitflag,output,lambda] = linprog(c,[],[],Ain,b,low,upp,[],options);

comp_slack=[lambda.upper.*(xstar-upp), lambda.lower.*(low-xstar)]

comp_slack = 20×2

1.0e+04 * 0 -2.2013 0 -0.0000 0 0 0 -0.0000 0 0 0 0 -0.0000 0 0 0 0 0 0 -0.4223

Answer 1

[Matt J]

I've changed my answer. I can't be completely sure, but it appears that your constraints have numerically unstable properties, that could explain the weird Lagrange multiplier behavior. If I widen your upper and lower bounds by a very small amount, the Lagrange multipliers change a great deal and (are all non-negative as they should be). Conversely, if I narrow the bounds even the slightest bit, the problem becames infeasible. This suggests that your equality-constrained region very narrowly intersects the box-constrainted region, making things unstable. I suspect that could be the reason for the weird Lagrange multiplier behavior.

options = optimoptions('linprog','Algorithm','dual-simplex','display','iter','ConstraintTol',1e-9);

epsilon=1e-6;

%narrow the bounds - problem becomes infeasible
[xstar,fval,exitflag,output,lambda] = linprog(c,[],[],Ain,b,low+epsilon,upp-epsilon,[],options);

No feasible solution found.

Linprog stopped because no point satisfies the constraints.

%widen the bounds - Lagrange multipliers okay
[xstar,fval,exitflag,output,lambda] = linprog(c,[],[],Ain,b,low-epsilon,upp+epsilon,[],options);

LP preprocessing removed 0 inequalities, 3 equalities,
3 variables, and 6 non-zero elements.

 Iter      Time            Fval  Primal Infeas    Dual Infeas  
    0     0.007    8.910000e+03   9.055385e+02   0.000000e+00  
   13     0.009    3.845000e+04   0.000000e+00   0.000000e+00  

Optimal solution found.

cs=[lambda.upper,(xstar-upp), lambda.lower,(low-xstar)]

cs = 20×4

0 -0.0000 0 -500.0000 0 -50.0000 0 -250.0000 0 -200.0000 0 -100.0000 0 -150.0000 0 -150.0000 3.8000 0.0000 0 -50.0000 0 -200.0000 0 -100.0000 0 -300.0000 0 -200.0000 3.6000 0.0000 0 -200.0000 0 -100.0000 0 -400.0000 1.8000 0.0000 0 -100.0000

[Tommy Etling]

After further investigation, I figured out, that there is only one feasible point with the original upper bounds.

I think this leads to the behaviour.

Thanks for your great hint adding an epsilon!