%run ../initscript.py
toggle()

show code

Linear Programming

For \(A \in \Re^{m \times n}\), \(b \in \Re^{m}\), \(c \in \Re^{n}\) and \(x \in \Re^{n}\)

\begin{align*} p^* = \max_x \ & c^\intercal x \\ \text{s.t. } & Ax = b \\ & x \ge 0 \end{align*}

Lagrangian Relaxation

For any \(y \in \Re^{m}\),

\begin{align*} p^* & \le \max_{x \ge 0} \left( c^\intercal x - y^\intercal (Ax - b) \right) \equiv \max_{x \ge 0} \mathcal{L}(x, y) \end{align*}

hide_comment()

show comment

Let \(x^*\) be the optimal solution for the primal problem. Then, for any \(y \in \Re^m\),

\begin{align*} p^* = \left( c^\intercal x^* - y^\intercal (Ax^* - b) \right) \end{align*}

because \(Ax^* = b\). Since \(x^*\) is feasible to the Lagrangian Relaxation,

\begin{align*} p^* & \le \max_{x \ge 0} \left( c^\intercal x - y^\intercal (Ax - b) \right) \equiv \max_{x \ge 0} \mathcal{L}(x, y) \end{align*}

Alternative formulation: \begin{align*} p^* = \max_x & \quad c^\intercal x \\ \text{s.t.} & \quad Ax \le b \\ & \quad x \ge 0 \end{align*}

For any \(y \in \Re_+^{m}\), \(y^\intercal (Ax - b) \le 0\) \begin{align*} p^* & \le \max_{x \ge 0} \left( c^\intercal x - y^\intercal (Ax - b) \right) \equiv \max_{x \ge 0} \mathcal{L}(x, y) \end{align*}

where \(y^\intercal (Ax - b)\) minimizes the violation of the constraint. We have \begin{align*} p^* & \le \min_{y \geq 0} \max_{x \ge 0} \left( c^\intercal x - y^\intercal (Ax - b) \right)\\ & = \min_{y \geq 0} \max_{x \ge 0} \left( (c^\intercal - y^\intercal A) x + y^\intercal b \right) \\ & = \min_{y \geq 0} \begin{cases} y^\intercal b & c^\intercal - y^\intercal A \le \mathbf{0} \text{ with } x^* = \mathbf{0}\\ \infty & \text{Otherwise} \end{cases} \end{align*}

\(\blacksquare\)

Thus, we have

\begin{align*} p^* & \le \min_{y} \max_{x \ge 0} \left( c^\intercal x - y^\intercal (Ax - b) \right)\\ & = \min_{y} \max_{x \ge 0} \left( (c^\intercal - y^\intercal A) x + y^\intercal b \right) \\ & = \min_{y} \begin{cases} y^\intercal b & c^\intercal - y^\intercal A \le \mathbf{0} \text{ with } x^* = \mathbf{0}\\ \infty & \text{Otherwise} \end{cases} \end{align*}

hide_comment()

show comment

Note that \(c^\intercal - y^\intercal A\) is a vector. Given \(y\), if

\begin{align*} \text{$(c^\intercal - y^\intercal A)_i$ is positive} \end{align*}

then, the inner maximization problem is unbounded by letting \(x_i = \infty\). If

\begin{align*} \left(c^\intercal - y^{\intercal} A\right)_i < 0, \end{align*}

then the optimal solution for the inner maximization problem has \(x^*_i = 0\). If

\begin{align*} \left(c^\intercal - y^{\intercal} A\right)_i = 0, \end{align*}

then \(x^*_i\) can take arbitrary value, i.e. complementarity condition.

\(\blacksquare\)

\begin{align*} p^* & \le \min_{y} \begin{cases} y^\intercal b & c^\intercal - y^\intercal A \le \mathbf{0} \\ \infty & \text{Otherwise} \end{cases} \end{align*}

We have weak duality

\begin{align*} p^* \le \min \ & y^\intercal b \\ \text{s.t. } & y^\intercal A \ge c^\intercal \end{align*}

Farkas’ Lemma

For \(A \in \Re^{m \times n}\) and \(b \in \Re^{m}\), there exactly one of the following two systems holds:

\begin{align*} \text{(I)} \quad \exists x \in \Re^n & &&&&& \text{(II)} \quad \exists y \in \Re^m &\\ \text{s.t. } Ax &= b &&&&& \text{s.t. } A^\intercal y & \ge 0 \\ x &\ge 0 &&&&& y^\intercal b & < 0 \end{align*}

hide_comment()

show comment

Proof of not both

Suppose \(x\) satisfies \(\text{(I)}\) and \(y\) satisfies \(\text{(II)}\). Then \(0 > y^\intercal b = y^\intercal A x \ge 0\), a contradiction.

Proof of at least one

Suppose \(\text{(I)}\) infeasible. We will show \(\text{(II)}\) feasible.

1. Consider \(S = \{ A x : x \ge 0 \}\) so that \(S\) is closed, convex and \(b \notin S\).

2. Let \(y \in \Re^m\) and \(\alpha \in \Re\) define a hyperplane that separates \(b\) from \(S\): \(y^\intercal b < \alpha\), but \(y^\intercal s \ge \alpha\) \(\forall s \in S\).

3. \(0 \in S \Rightarrow \alpha \le 0 \Rightarrow y^\intercal b < 0\).

4. \(y^\intercal A x \ge \alpha\) \(\forall x \ge 0\) implies \(y^\intercal A \ge 0\) since \(x\) can be arbitrarily large.

\(\blacksquare\)

Alternative

For \(A \in \Re^{m \times n}\) and \(b \in \Re^{m}\), there exactly one of the following two systems holds:

\begin{align*} \text{(I)} \quad \exists x \in \Re^n & &&&&& \text{(II)} \quad \exists y \in \Re^m & \\ \text{s.t. } Ax & \le b &&&&& \text{s.t. } A^\intercal y & \ge 0\\ x &\ge 0 &&&&& y^\intercal b & < 0 \\ &&&&&& y & \ge 0 \end{align*}

hide_comment()

show comment

Proof of alternative

Apply Farkas’ lemma to

\begin{align*} \text{(I)} \quad \exists x \in \Re^n & &&&&& \text{(II)} \quad \exists y \in \Re^m & \\ \text{s.t. } Ax + \texttt{I} s & \le b &&&&& \text{s.t. } A^\intercal y & \ge 0 \\ x,\ s &\ge 0 &&&&& \texttt{I} y &\ge 0 \\ &&&&&& y^\intercal b & < 0 \end{align*}

\(\blacksquare\)

Strong Duality

We have \(p^* = d^*\) if both primal and dual problems are feasible where

\begin{align*} p^* = \max_x \ & c^\intercal x &&&&& d^* = \min \ & y^\intercal b \\ \text{s.t. } & Ax = b &&&&& \text{s.t. } & y^\intercal A \ge c^\intercal \\ & x \ge 0 \end{align*}

hide_comment()

show comment

\(p^* \le d^*\) follows the weak duality.

Proof of \(p^* \ge d^*\)

Suppose \(p^* < \alpha\). We show \(d^* < \alpha\).

\begin{align*} \text{(I)} \quad \exists x \in \Re^n & &&&&& \text{(II)} \quad \exists y \in \Re^m,\ & z \in \Re\\ \text{s.t. } Ax & = b &&&&& \text{s.t. } y^\intercal A - z c^\intercal & \ge 0\\ -c^\intercal x + s & = - \alpha &&&&& y^\intercal b -z \alpha & < 0\\ s, x & \ge 0 &&&&& z & \ge 0 \end{align*}

where \(s, z \in \Re\).

The matrix form of \(\text{(I)}\) and \(\text{(II)}\): \begin{align*} \left( \begin{array}{ll} A & \mathbf{0} \\ -c^\intercal & 1 \end{array} \right)_{(m+1) \times (n+1)} \left( \begin{array}{l} x \\ s \end{array} \right) &= \left( \begin{array}{l} b \\ -\alpha \end{array} \right) \\ \left( y^\intercal, z \right)\left( \begin{array}{ll} A & \mathbf{0} \\ -c^\intercal & 1 \end{array} \right) & \ge 0 \\ \left( y^\intercal, z \right)\left( \begin{array}{l} b \\ -\alpha \end{array} \right) & < 0 \end{align*}

Proof of \(p^* \ge d^*\)

Definition of \(\alpha\) \(\Rightarrow\) \(\text{(I)}\) is infeasible \(\Rightarrow\) \(\text{(II)}\) is feasible by Farkas’ Lemma. Let \(y, z\) be a solution to \(\text{(II)}\). If \(z \le 0\)

• then \(\{y \in \Re^m: A^\intercal y \ge 0, y^\intercal b < 0\}\) is feasible.

• Farkas’ Lemma (alternative) \(\Rightarrow \{x \in \Re^n: Ax = b, x \ge 0\}\) is infeasible.

• contradiction since primal problem is assumed to be feasible.

Then \(z > 0\).

• We scale \(y,\ z\) so that \(y\) satisfies \(\text{(II)}\) and \(z = 1\).

• Thus \(y\) is feasible to the dual problem and \(y^\intercal b < \alpha\).

\(\blacksquare\)

Algorithms

\begin{align*} p^* = \max_x \ & c^\intercal x &&&&& d^* = \min \ & y^\intercal b \\ \text{s.t. } & Ax = b &&&&& \text{s.t. } & y^\intercal A \ge c^\intercal \\ & x \ge 0 \end{align*}

Consider basis and non-basis decomposition \begin{align*} A x &= (A_B, A_N) \left( \begin{array}{c} x_B \\ x_N \end{array} \right) = A_B x_B + A_N x_N = A_B ( x_B + A^{-1}_B A_N x_N ) = b \\ \Rightarrow x_B &= A^{-1}_B b - A^{-1}_B A_N x_N \\ c^\intercal x &= (c_B, c_N)^\intercal \left( \begin{array}{c} x_B \\ x_N \end{array} \right) = c^\intercal_B x_B + c^\intercal_N x_N = c^\intercal_B ( A^{-1}_B b - A^{-1}_B A_N x_N ) + c^\intercal_N x_N \\ y^\intercal A &= y^\intercal (A_B, A_N) \ge (c_B, c_N)^\intercal \Rightarrow y^\intercal A_B \ge c_B^\intercal \text{ and } y^\intercal A_N \ge c_N^\intercal \end{align*}

\begin{align*} p^* = c^\intercal_B A^{-1}_B b + \max \ & (c^\intercal_{N} - c^\intercal_B A^{-1}_B A_{N}) x_N &&&&& d^* = \min \ & y^\intercal b \\ \text{s.t. } & x_B + A^{-1}_B A_N x_N = A^{-1}_B b &&&&& \text{s.t. } & y^\intercal A_B \ge c^\intercal\\ & x_B, x_N \ge 0 &&&&& & y^\intercal A_N \ge c^\intercal \end{align*}

Potentially, we have

• primal solution \((x_B, x_N) = (A^{-1}_B b, 0)\) and

• dual solution \(y^\intercal = c^\intercal_B A^{-1}_B\)

The basis \(A_B\) is

• primal feasible if \(A^{-1}_B b \ge 0\) and

• dual feasible if \(c_B A^{-1}_B A_{N} \ge c_{N}\).

If \(A_B\) is both primal and dual feasible, the primal and dual objective values are \(c^\intercal_B A^{-1}_B b\). Thus we get an optimal solution.

hide_comment()

show comment

LP basis formulation

\begin{align*} p^* = c^T_B A^{-1}_B b + \max & \quad \underbrace{(c_{N} - c_B A^{-1}_B A_{N})}_{\bar{c}} x_N \\ \text{s.t.} & \quad x_B + \underbrace{A^{-1}_B A_N}_{\bar{a}} x_N = A^{-1}_B b { = \bar{b}} \\ & \quad x_B, x_N \ge 0 \end{align*}

Primal and dual simplex algorithm (Phase 2)

Algorithm:		primal simplex		dual simplex
Initial:		A primal feasible basis \(A_B\)		A dual feasible basis \(A_B\)
Optimality:		if \(A_B\) is dual feasible		if \(A_B\) is primal feasible
Pricing:		select \(r \in N\) with \(\bar{c}_r > 0\)		select \(s \in B\) with \(\bar{b}_s < 0\)
		unbounded if \(\bar{a}_r \le 0\)		infeasible if \(\bar{a}_{sj} \geq 0\) \(\forall j \in N\)

\(\blacksquare\)

A solution \((x,y,s) \in \Re^n \times \Re^m \times \Re^m\) is optimal if it satisfies \(Ax = b,\ y^\intercal A - s^\intercal = c^\intercal\) and

\begin{eqnarray} s^Tx = 0 \label{eqn:lp_1}\\ x \ge 0 \label{eqn:lp_2}\\ s \ge 0 \label{eqn:lp_3} \end{eqnarray}

Solutions along the search path of all algorithms satisfy all (in)equalities, except

• primal simplex: \eqref{eqn:lp_3} is relaxed initially and optimum is found until it is satisfied.

• dual simplex: \eqref{eqn:lp_2} is relaxed initially and optimum is found until it is satisfied.

• primal-dual: \eqref{eqn:lp_1} is relaxed initially and optimum is found until it is satisfied.

Suppose we have a subroutine which can find a solution of a set of linear equations. Design an algorithm to solve the optimization problem \(\max \{c^\intercal x : Ax = b, x \in \mathcal{R}^n\}\).

hide_comment()

show comment

We can solve the system of linear equations

\begin{align*} c^\intercal x &= b y^\intercal \\ Ax &= b \\ y^\intercal A - s^\intercal &= c^\intercal \\ x \ge 0, s &\ge 0 \end{align*}

Interior point method

\begin{eqnarray*} A^T y - s & = & c \\ A x & = & b \\ x_i s_i & = & 0, i=1,\ldots, n\\ (x,s) & > & 0 \end{eqnarray*}

\begin{align*} F(x,y,s) = \left[ \begin{array}{c} A^T y - s - c \\ Ax - b \\ XSe \end{array} \right] = 0, (x,s) > 0 \end{align*}

Newton’s method implies

\begin{align*} J(x,y,s) \left[\begin{array}{c} \Delta x \\ \Delta y \\ \Delta s \end{array} \right] = \left[\begin{array}{ccc} 0 & A^T & -I \\ A & 0 & 0 \\ S & 0 & X \end{array} \right] \left[\begin{array}{c} \Delta x \\ \Delta y \\ \Delta s \end{array} \right]= -F(x,y,s) = \left[ \begin{array}{c} 0 \\ 0 \\ -XSe \end{array} \right] \end{align*}

\(\blacksquare\)