ADS HT24, Linear programming


Flashcards

Can you state the fundamental theorem of 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

Suppose we have a general linear program:

  • $n$ real variables $x _ 1, \cdots, x _ n$
  • objective function: max/min $c _ 1 x _ 1 + \cdots + c _ n x _ n$
  • $\le$ constraints: $a _ {i1} x _ 1 + \cdots + a _ {in} x _ n \le b _ i$
  • $\ge$ constraints: $a _ {i1} x _ 1 + \cdots + a _ {in} x _ n \le b _ i$
  • $=$ constraints: $a _ {i1} x _ 1 + \cdots + a _ {in} x _ n \le b _ i$

What 4 steps can you take to convert the LP into standard maximum form?


  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$

What does a linear program look like in standard maximum form?


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

Suppose we have a linear program in standard maximum

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

What does the dual linear program look like in standard minimum form, and what are some basic observations?


\[\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

Suppose we have the primal linear program

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

Quickly prove that the corresponding dual linear program is given by

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

  • 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.

Suppose we have the primal linear program

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

and the corresponding dual linear program

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

What is meant by weak duality here? Give an intuitive and then formal definition, and then quickly prove it.


  • 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 we have the primal linear program

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

and the corresponding dual linear program

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

What is meant by strong duality here?


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.

Suppose we have the linear program

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

This induces a polyhedron

\[P = \\{x \in \mathbb R^n \mid Ax \le b\\}\]

What does it mean for $x^\star$ to be an extreme point of $P$?


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

Suppose we have the linear program

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

This induces a polyhedron

\[P = \\{x \in \mathbb R^n \mid Ax \le b\\}\]

What does it mean for $x^\star$ to be a vertex of $P$?


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

Suppose we have the linear program

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

This induces a polyhedron

\[P = \\{x \in \mathbb R^n \mid Ax \le b\\}\]

We also have the two definitions

  • $x^\star$ is an extreme point if $\forall y, z \in P \setminus \{x^\star\}, x^\star \ne \frac{y + z}{2}$.
  • $x^\star$ is a vertex if the set $\{a _ i \mid a _ i^\top x^\star = b _ i\}$ is a linear independent collection of $n$ vectors

Quickly prove that these two notions are equivalent.


$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$.

Quickly describe the simplex algorithm for solving linear programming problems.


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

Formulate the max flow problem on a flow network $G = (V, E, s, t, c)$ with $c : E \to \mathbb Z _ {\ge 0}$ and $f _ e$ denoting the flow on edge $e$ as a linear programming problem.


\[\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}\]

Formulated as an LP, the max-flow problem on a flow network $G = (V, E, s, t, c)$ with $c : E \to \mathbb Z _ {\ge 0}$ and $f _ e$ denoting the flow on edge $e$ as a linear programming problem is:

\[\begin{aligned} \text{max }& \sum_{e \text{ out of }s} f_e\\\\ \text{s.t. }& f_e \ge 0 && \forall e \in E \\\\ &f_e \le c(e) && \forall e \in E \\\\ &\sum_{e \text{ out of }v} f_e - \sum_{e \text{ into } v} f_e = 0 && \forall v \ne s, t \end{aligned}\]

Can you state the dual formulation, and how you can interpret the result?


\[\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.

Suppose we have a dual and primal LP:

\[\begin{align*} \text{maximise} \quad & \mathbf{c}^T \mathbf{x} \\ \text{subject to} \quad & A \mathbf{x} \leq \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \quad & (\text{LP}_1) \end{align*}\] \[\begin{align*} \text{minimise} \quad & \mathbf{b}^T \mathbf{y} \\ \text{subject to} \quad & A^T \mathbf{y} \geq \mathbf{c} \\ & \mathbf{y} \geq \mathbf{0} \quad & (\text{LP}_2) \end{align*}\]

Quickly prove that we have “complementary slackness”, if $\pmb x$ and $\pmb y$ are optimal solutions to the primal and dual, then:

  • For each $i = 1, \cdots, n$, if $A _ {(i)} \pmb x < b _ i$, then $y _ i = 0$
  • For each $j = 1, \cdots, m$, if $\pmb y^\top A^{(j)} > c _ j$, then $x _ j = 0$

Where $A _ {(i)}$ denotes the $i$-th row, and $A^{(j)}$ denotes the $j$-th column.


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.

Proofs




Related posts