Optimality conditions in linear programming problems with lower- and upper-bounded variables

Question

Background:

According to a paper by Andersen and Andersen (https://www.davi.ws/doc/Andersen.pdf), any linear programming problem can be formulated as:

min $c^Tx$,

s. t. $Ax = b$,

$l \le x \le u$,

$ ...(1)$

where $x, c, l, u \in \Bbb R^n$, $b \in \Bbb R^m$ and $A \in \Bbb R^{m \times n} $, and some of the simple bounds $l_j$ and $u_j$ may be $-\infty$ and $+\infty$ respectively. With $L = \{j: l_j \gt -\infty \}$ and $U = \{j: u_j \gt +\infty \}$, then the optimality conditions to 1) can be stated as follows:

$Ax^* = b$,

$A^Ty^* + z^* = c$,

$(x^*_j - l_j) z^*_j = 0$ $\forall j \in L $,

$(u_j - x^*_j) z^*_j = 0$ $\forall j \in U $,

$z^*_j \ge 0$ $\forall j \in \{j \in L: x^*_j = l_j$ $\land$ $l_j \le u_j \} $,

$z^*_j \le 0$ $\forall j \in \{j \in U: x^*_j = u_j$ $\land$ $l_j \le u_j \} $,

$z^*_j = 0$ $\forall j \notin L\cup U $,

$l \le x^* \le u$,

$...(2)$

where $y \in \Bbb R^m$ and $z \in \Bbb R^n$. $y$ and $z$ are the Lagrange multipliers corresponding to the linear constraints and linear inequalities in (1), respectively.

My problem:

I am having difficulty seeing whether the optimality conditions (2) came from. I have attempted to derive them as follows:

Introduce a new variable $x'= x - l$ and a new (slack) variable $x'' = u - x'$. Then the primal problem can be cast as:

min $c^T(x' + l)$

s. t. $A(x' + l) = b$

$x' + x'' = u - l$

$x', x'' \ge 0$.

That is:

min $c^T x' + c^T l$

s. t. $\bigl( \begin{smallmatrix} A & 0 \\ 1 & 1 \end{smallmatrix} \bigr)$ $\bigl( \begin{smallmatrix} x' \\ x'' \end{smallmatrix} \bigr)$ $=$ $\bigl( \begin{smallmatrix} b - A l \\ u -l \end{smallmatrix} \bigr)$,

$ x', x'' \ge 0$.

Then, with dual variables $y'$ and $y''$, complementary slackness gives, for optimality:

$x' (c - (y'A + y'')) = 0$, and $x''(-y'') = 0$

$...(3)$

Also, for dual feasibility:

$c \ge y'A + y''$, and $0 \ge y''$

$...(4)$

Is my working correct so far, and if it is, how can I derive (2) from (3) and (4)? Or is there a simpler way to prove (2)?

I would be very grateful for any help.

Answer 1

The easiest way is probably directly via the Lagrangian, but your approach is (almost) correct if all variables have upper and lower bounds, and you have almost solved it. The only error is how you defined $x''$ (it should be $u-x$, not $u-x'$).

You just have to add a slack variable $s$ to $c \geq A^Ty + y''$. Then $z$ from the paper is $y'' + s$ (with $y'' < 0$, so $z$ is not restricted in sign). Your (elementwise) complementarity condition $x'(c-A^Ty'+y'')=0$ means that if $x_j'>0$, i.e., $x_j^*>l$, then $s=0$ so $z_j^* \leq 0$. Similarly, the condition $x''(-y'') = 0$ means that if $x_j'' > 0$, i.e., $x_j^*<u$, then $y''=0$, which means $z_j^* \geq 0$.

Answer 2

It occurred to me after posting that the proof can be made much simpler if inequality primal constraints are used, i.e.

$ \begin{pmatrix} A \\ -A \\ 1 \\ -1 \\ \end{pmatrix} x \ge \begin{pmatrix} b \\ -b \\ l \\ -u \\ \end{pmatrix} $

Then with dual variables $y1, ..., y4 \ge 0$, setting $y = y1-y2$ and $z = y3-y4$ yields the desired result directly.