ADS HT24, Linear programming

For any linear programming, exactly one of the following holds:

1. It is infeasible
2. It is feasible but unbounded
3. It is feasible, bounded, and there exists a solution that achieing the optimal

1. Convert objective function to maximum (e.g. by negating)
2. Replace equality constraints with two identical “$\le$” and “$\ge$” constraints
3. Replace “$\ge$” constraints with “$\le$” by negating
4. Make all variables non-negative by replacing $x$ with $x^+ - x^-$ where $x^+, x^- \ge 0$

\[\begin{aligned} \text{max }& c^\top x \\\\ \text{s.t. }& Ax \le b \\\\ &x\ge 0 \end{aligned}\]

\[\begin{aligned} \text{min }& b^\top y \\\\ \text{s.t. }& A^\top y \ge c \\\\ &y\ge 0 \end{aligned}\]

Observations:

• max becomes min
• $n$ variables, $m$ constraints in primal $\implies$ $m$ variables and $n$ constraints in dual
• $b _ j$s and $c _ i$s switch
• Rows of $A$ become columns in the dual

• Multiply all constraints by new variables $y _ i$
• Add new constraints that mean we can the sum as a bound for the original objective

Expanding out, we have

\[\begin{aligned} \text{max }& \sum^n_{i = 1} c_i x_i \\\\ \text{s.t. }& \sum_{j=1}^n a_{ij} x_j \le b_i \quad\text{for }i = 1, \ldots, m \\\\ &x_1, \cdots, x_n \le 0 \end{aligned}\]

We introduce new variables nonnegative $y _ i$ in hopes of using the information in the constraints to place an upper bound on the objective function. To do this, consider

\[\begin{aligned} S &:= \sum^m_{i = 1} y_i \left( \sum^n_{j = 1} a_{ij} x_j \right) \\\\ &= \sum^n_{j = 1} x_j \left( \sum^m_{i = 1} a_{ij} y_i \right) \end{aligned}\]

and the corresponding inequalities

\[\sum^m_{i = 1} a_{ij} y_i \ge c_j\]

Here, the intuition is that we are considering the sum of all possible linear combinations of constraints, and by using the new inequality, we ensure that the original objective function is bounded above by $S$, since

\[\sum^n_{i = 1} c_i x_i \le \sum^n_{j = 1} x_j \left( \sum^m_{i = 1} a_{ij} y_i \right)\]

The value that $S$ gives us is bounded by

\[\sum^m_{i = 1} b_i y_i\]

(since this is just the RHS) and so to get the best possible estimate on the value of the original objective function, we want to minimise this. Putting it all together, we see that this is equivalent to

\[\begin{aligned} \text{min }& \sum^m_{i = 1} b_i y_i \\\\ \text{s.t. }& \sum^m_{i = 1} a_{ij} y_i \ge c_j \\\\ &y \ge 0 \end{aligned}\]

or, in matrix notation

\[\begin{aligned} \text{min }& b^\top y \\\\ \text{s.t. }& A^\top y \ge c \\\\ &y\ge 0 \end{aligned}\]

as required.

• Informally, any feasible solution to the dual problem gives an upper bound on the solution to the primal problem.
• Formally, let $x \in \text{Feasible(Primal)}$ and $y \in \text{Feasible(Dual)}$. Then $c^\top x \le b^\top y$

Quick proof:

\[c^\top x = x^\top c \le x^\top A^\top y = (Ax)^\top y \le b^\top y\]

Suppose that one of the primal or dual programs is bounded and feasible. Then both are and the optimal solution for one equals the optimal solution for the other.

\[\forall y, z \in P \setminus \\{x^\star\\}, x^\star \ne \frac{y + z}{2}\]

The set $\{a _ i \mid a _ i^\top x^\star = b _ i\}$ is a linear independent collection of $n$ vectors

$x^\star$ is an extreme $\implies$ $x^\star$ is a vertex

• Let $I = \{i \in \mathbb N \mid a^\top _ i x^\star = b _ i\}$ and $A = \{a _ i \mid i \in I\}$.
• We want to show that $A$ is a collection of $n$ linearly independent vectors. Suppose it were not.
• Then $\exists w \ne 0$ s.t. $a _ i^\top w = 0$ $\forall i \in I$ (slightly confusing notation, this is a way of stating that the system $Aw = 0$ has a nontrivial solution, rather than a statement about a linear combination that make zero)
• But then we can find two vectors $x^\star \pm \varepsilon w \in P$, since
  • $\forall i \notin I$, $a _ i^\top x^\star < b _ i \implies \exists \varepsilon \text{ s.t. } a _ i^\top(x^\star \pm \varepsilon w) < b _ i$ (where the inequality stems from the original linear program)
  • $\forall i \in I$, $a _ i^\top (x^\star \pm \varepsilon w) = 0$
  • …hence $x^\star \pm \varepsilon w \in P$
• This is a contradiction, because these average to $x^\star$, contradicting the fact $x^\star$ is an extreme point

$x^\star$ is a vertex $\implies$ $x^\star$ is an extreme point

• Let $y, z \in P$ be such that $x^\star = \frac{y+z}{2}$. We aim to show $x^\star = y = z$
• Let $I = \{i \in \mathbb N \mid a _ i^\top x^\star = b _ i\}$ and $A = \{a _ i \mid i \in I\}$.
• $A$ contains $n$ linearly indepedent vectors, since $x^\star$ is a vertex
• $x^\star = \frac{y + z}{2} \implies a _ i^\top x^\star = \frac{a _ i^\top y + a _ i^\top z}{2}$.
• Since $a _ i^\top x^\star = b _ i$ but also $a _ i^\top y \le b _ i$ and $a _ i^\top z \le b _ i$, the only way this can be true if $a _ i^\top y$ and $a _ i^\top z$ both equal $b _ i$ also.
• Then $x^\star, y, z$ are solutions to the system $\{i \in I \mid a _ i^\top x = b _ i\}$. Since this system consists of $n$ linearly independent constraints, the solution must be unique and hence $x^\star = y = z$.

Start from an arbitrary vertex of the induced polyhedron, and then keep moving to neighbours with bigger values.

\[\begin{aligned} \text{max }& \sum_{e \text{ out of }s} f_e\\\\ \text{s.t. }& f_e \ge 0 \quad \text{for all edges e} \\\\ &f_e \le c(e) \quad \text{for all edges e} \\\\ &\sum_{e \text{ out of }v} f_e - \sum_{e \text{ into } v} f_e = 0 \end{aligned}\]

\[\begin{aligned} \min &\sum_{e \in E} c(e) z_e \\\\ \text{s.t. } &z_{u,v} \ge y_u - y_v &&\forall e = (u, v) \\\\ &z_e \ge 0 &&\forall e = (u, v) \\\\ &y_s = 1, y_t = 0 \end{aligned}\]

We interpret any integer optimal solution $(\pmb y^\star, \pmb z^\star)$ to the LP as forming a cut

\[(\\{u \mid y_u \ge 1\\}, \\{v \mid y_v \le 0\\})\]

and $z _ e = 1$ if the edge crosses the cut.

By using the inequalities, we have

\[\pmb c^\top \pmb x \le y^\top A \pmb x \le \pmb y^\top \pmb b\]

By strong duality, we have that $\pmb c^\top \pmb x$ and that $\pmb y^\top \pmb b$. So these are actually equalities:

\[\pmb c^\top \pmb x = y^\top A \pmb x = \pmb y^\top \pmb b\]

Rearranging, we see

\[\pmb y^\top (\pmb b - \pmb A \pmb x) = \pmb 0\]

Then we can rewrite as

\[\sum^n_{i = 1} y_i (b_i - A_{(i)}\pmb x) = 0\]

Since $\pmb x$ is a feasible solution to the LP, all the summands are nonnegative (since $A\pmb x \le \pmb b)$. Hence if $A _ {(i)}\pmb x < b _ i$ for some $i \in \{1, \cdots, n\}$, then $y _ i = 0$.

For the dual program, the argument is symmetric.