Re: [Bug-glpk] Wrong dual value using interior method

[Andrew Makhorin]

On Tue, 2010-10-26 at 19:08 +0200, glpk xypron wrote:
> Hello Andrew,
> 
> > > maximize obj: x + y;
> > > s.t. c1: 0.1 * y + x <= 1.;
> > > s.t. c2: 0.1 * y + x >= 1.;
> > > s.t. d1: y + 0.1 * x <= 5.;
> > > s.t. d2: y + 0.1 * x >= 5.;
> > c1: value = 1, dual = 1.340170
> > c2: value = 1, dual = -0.431079
> > d1: value = 5, dual = 1.326582
> > d2: value = 5, dual = -0.417491
> 
> Of constraints c1 and c2 only one can be active, same for
> d1 and d2.
> 
> I expect the dual of the active constraint to be nonzero,
> and the dual of the inactive constraint to be zero.
> 
> This is what the simplex method returns, but the interior
> method does not.
> 

No. In the simplex method duals of inactive constraints are set to zero,
because this automatically allows to satisfy to the complementarity
slackness conditions. However, this is *not* the only choice when lp is
degenerate. Therefore, in case of optimal interior-point solution you
may only expect that the KKT optimality conditions are met, but not
more.

Consider the following lp:

minimize x
s.t.     x >= 0   (Lagrange multiplier a >= 0)
         x <= 0   (Lagrange multiplier b <= 0)

Obviously, in the primal space there is the only optimum x = 0. *Note*
that for both constraints optimal x is at the bound, so both a and b can
be non-zero as it follows from the complementarity slackness. The dual
system is the following:

a + b = 1

and due to degeneracy it allows multiple solutions. You can take a = 1
and b = 0 (as you expected), but, for example, a = 2 and b = -1 as well
as a = 3 and b = -2 are also satisfy to the optimality conditions. And
the primal-dual interior-point method may report any of these optimal
solutions, which it does in your case.