Lecture 14: LP Duality

Last Time

• Introduced the definition of linear programs (LPs).
• Standard form LP: $\min c^Tx$, s.t., $Ax=b, x\geq 0$.
• Analyzed the structure of optimal solutions of such LP.
• Proved that there is always a basic feasible solution (BFS) and its bit complexity is not too large.

  $\Rightarrow$ The decision problem $LP-Dec$: for a given $v$, does there exists $x$ s.t. $c^Tx\leq v, Ax=b, x\geq 0$, is in $NP$. (If such $x$ exists, then the optimal BFS $x^*$ is a succinct certificate that can be checked in polynomial time.)

• How about $LP-Dec\in co-NP$? Is there always a succinct certificate of infeasibility of an LP?

Duality

Checking feasibility of a given solution is easy. Motivating question: How to certify optimality of a given solution?

• Key notion: Duality - strongest result in the theory of LP.
• Enable one to give a (succinct) proof of optimality.
• Recovers a lot of classic results: max-flow min-cut theorem, prices for min-cost flow, existence of a Nash equilibrium in every two-player zero-sum game, lots other stuff.

Want: Find a lower bound on $v^*:=\min \set{c^Tx \mid Ax=b, x \ge 0}$.

• Standard approach: try adding up linear combinations of existing equations.

  $\Rightarrow$ Try multiplying each constraint $A_i x = b_i$ by some $y_i$ and adding all of them together.

  $\Rightarrow$ We will always have that $yAx=yb$.

• If find $y$ s.t. $y^TA=c^T$, then $y^Tb=y^TAx=c^Tx$. So, every feasible solution $x$ has the same value $v^*$!
• But, in general, cannot hope that such $y$ exists - $c$ might not be in the span of $A^T$.
• Instead, let us focus on a looser goal: find $y$ s.t. $y^TA \le c^T$.

  $\Rightarrow$ We can lower bound $v^*$ by noting that $y^T b= y^TAx \le c^Tx$, for any feasible $x$. (The inequality holds as $x\geq 0$.)

• How about getting the best lower bound to be gotten this way?
• Write an LP for that!
• Dual LP: $\max b^Ty$ s.t. $A^Ty\leq c$. (Note that the dual LP is defined in a completely syntactic way - no thinking involved!)
• Let $w^*:=\max \set{b^Ty \mid A^Ty \le c}$.
• We just have shown weak duality: $w^*\leq v^*$.

Important observation (and a sanity check): The dual of the dual LP gives the primal LP.

• Let the primal LP be $\min c^Tx$ s.t. $Ax=b, x\ge 0$.
• Its dual LP is $\max b^Ty$ s.t. $A^Ty\leq c$.
• Let us transform the latter LP into a standard form: \[ \max b^Ty \text{ s.t. } A^Ty \le c \] $\Rightarrow$ \[ - \min -b^Ty \text{ s.t. } A^Ty + I s = c, s\geq 0 \] $\Rightarrow$ \[ - \min (-b)^T(y^+-y^-) \text{ s.t. } A^Ty^+- A^Ty^-+ I s = c, s, y^+, y^-\geq 0 \] $\Rightarrow$ In matrix form, this LP dual becomes $$ \begin{eqnarray*} -\min \left( \begin{array}{ccc} -b&b&0 \end{array} \right) \left( \begin{array}{c} y^+\\y^-\\s \end{array} \right) \text{ s.t. } &&\left(\begin{array}{ccc} A^T&-A^T&I \end{array} \right) \left(\begin{array}{c} y^+\\ y^-\\ s \end{array} \right) = c\\ &&y^+,y^-,s \ge 0\\ \end{eqnarray*} $$
• The dual of the above LP is then: \[ -\max c^T z \text{ s.t. } \left(\begin{array}{ccc} A^T&-A^T&I \end{array} \right)^T z \le \left( \begin{array}{ccc} -b&b&0 \end{array} \right)^T\\ \] $\Rightarrow$ \[ \min -c^T z \text{ s.t. } A(-z)=b, z\leq 0 \] $\Rightarrow$ Setting $x=-z$, we get \[ \min c^T x \text{ s.t. } Ax=b, x\geq 0, \] as desired.

A simple corollary of weak duality and the above observation: If $P$ is the primal LP and $D$ is the dual LP then either

• Both $P$ and $D$ are feasible and bounded.
• if $P$ is feasible, $D$ either infeasible or bounded.
• If $P$ is feasible and unbounded (i.e., $v^*=-\infty$), $D$ infeasible.
• (Similarly, if $D$ feasible and unbounded (i.e., $w^*=\infty$), $P$ is infeasible.)
• In fact, together with strong duality (see below), this implies that we can have only four possibilities: both $P$ and $D$ bounded and feasible, one of them unbounded and one of them infeasible,, both of them infeasible.

Strong Duality

Weak duality described below is just a tip of an iceberg. Strong duality (key theorem of LP): If $P$ and $D$ feasible then $v^*=w^*$.

“Proof” by picture:

• Consider a “dual” problem $\min b^Ty$ s.t. $A^Ty \ge c$, which we obtain by flipping the sign of $y$ in our above dual problem formulation.
• Suppose $b$ points straight up.
• Imagine that $y$ is the position of a ball that falls down subject to gravity and the constraints correspond to “floors” that limit how far the ball can fall.

  $\Rightarrow$ Minimizing $b^T y$ subject to our constraints corresponds here exactly to minimizing the height of the ball given the limitations posed by the floor.

  $\Rightarrow$ Let $y^*$ be the minimum height position the ball settles in (according to physics). This is also the optimal solution for our dual LP.

• Why does the ball stay in position $y^*$?
• The forces exerted on the ball by the floors are canceling the “gravity” $-b$.

  $\Rightarrow$ Force exerted by the floor $i$ has to be normal (i.e., perpendicular) to the surface of that floor. That is, it is equal to $A_i x_i$, for some scaling factor $x_i$, where $A_i$ is the $i$-th column of $A$.

• Equilibrium condition: $\sum_i A_i x_i = b$. That is, $Ax=b$.
• Also, the force exerted by the floors can be only pushing the ball away. So, $x_i\geq 0$, for each $i$.

  $\Rightarrow$ $x\geq 0$.

• In other words, $x$ is feasible (but not necessarily optimal) for the “primal” LP $\min c^x$ s.t. $Ax=b, x\geq 0$.
• Furthermore, physics tells us that the floors that do not touch the ball, i.e., all floors $i$ with $A_i^T y^{*} >c_i$, do not exert any force. So, $x_i=0$ for them.

  $\Rightarrow$ Compact way of writing that: $(c_i-A_i^Ty^{*})x_i=0$, for all $i$. (This is complementary slackness condition!)

• Thus we have that $c^T x = \sum_i (A_i^T y^{*}) x_i = x^T A^T y^{*} = (Ax)^Ty^{*}=b^Ty^{*}$.
• So, by weak duality, $x$ is indeed optimal and $v^*=c^Tx=b^Ty^*=w^*$.

Formal proof:

• Consider the optimum solution $y^*$ to the $\min b^Ty$ s.t. $A^Ty \ge c$. (The sign of $y$ is still flipped.)
• Let us choose a subset $S$ of constraints that are tight, i.e., $A_i^Ty^*=c$, and linearly independent. (Recall that $A_i$ is the $i$-th column of $A$.)
• Note that $|S|$ is at most $m$, where $m$ is the dimension of $y^*$.
• Let $A_S$ and $c_S$ be the matrix $A$ and the vector $c$ after dropping the rows/entries corresponding to the constraints not in $S$.

  $\Rightarrow$ The matrix $A_S^T$ is of full column rank and $A_S^T y^*=c_S$.

• Also, we still have that $b^Ty^*=w^*=\min b^Ty$ s.t. $A_S^Ty\geq c_S$.
• Thus, if we prove strong duality wrt to $A_S$, i.e., that there exists $x_S^*$ s.t. $A_Sx_S^*=b$, $x_S^*\geq 0$, and $c_S^T x_S^*=b^T y^*=w^*$, then we recover strong duality for the original LP by just considering $x^*$ being $x_S^*$ with all the coordinates not in $S$ padded with zeros. Specifically, we will have that $c^Tx^*=c_S^Tx_S^*=w^*$, $Ax^*=A_Sx_S^*=b$ and $x^*\geq 0$, as desired.
• So, let us drop the reference to $S$ and assume from now on wlog that $A^T$ is of full column rank and $A^Ty^*=c$.

Claim: There exists $x^*$ such that $Ax^*=b$.

• Suppose not? Then, by the “duality” for linear equalities we considered earlier, tells us there exists a vector $z$ with $A^Tz=0$ but $b^Tz\ne 0$.
• Wlog assume $b^Tz< 0$. (Else, we just take $-z$.)
• Consider a solution $y'=y^*+z$.
• It is feasible since $A^Ty'=A^Ty^*+A^Tz=A^Ty^*$.
• Also, we have that $b^Ty'=b^T(y^*+z)=b^Ty^*+b^Tz< b^Ty^*=w^*$. Solution $y'$ is strictly better than the optimum. Contradiction!
• (This formalizes our idea that if the forces are not in balance, the ball will fall further down.)

Claim: We have that $b^Ty^*=c^Tx^*$.

• We know that $Ax^*=b$ and $A^Ty^*=c$.
• So $b^Ty^*=(Ax^*)^Ty^*=(A^Ty^*)^Tx^*=c^Tx^*$.

Claim: It is the case that $x^* \ge 0$.

(Formalizes the intuition that barriers have to push ball not pull it.)

• Suppose not, i.e., some $x_i^* < 0$.
• Let $c'=c+e_i$, where $e_i$ is a vector with all-zeros except a $1$ at coordinate $i$. (This corresponds to tightening the $i$-th constraint, i.e., moving it “upwards”.)
• Consider solution to $A^T y'=c'$. (Such a solution has to exist as $A^T$ has a full column rank.)
• Clearly, $c' \ge c$, and thus $A^Ty'=c'\geq c$.

  $\Rightarrow$ $y'$ is feasible for the original constraints $A^Ty\ge c$.

• The value of the objective is $b^Ty'=(Ax^*)^Ty'=(A^Ty')^Tx^*=(c')^Tx^*$.
  • We assumed $x_i^* < 0$, and increased $c_i$.
  • So $b^Ty'=(c')^Tx^* < c^Tx^* =b^Ty^*$.
  • Again, got a feasible solution $y'$ with a better value than optimum. Contradiction!
• Intuition: $x_i^*$ is telling us how much the value of the optimum will change if we “tighten” $i$-th constraint.

  $\Rightarrow$ Making constraint tighter should increase opt (as it corresponds to a minimization problem).

  $\Rightarrow$ $x_i^*$ should be thus non-negative.

Interesting corollary (of strong duality): For LPs, finding a solution that is merely feasible is algorithmically equivalent to finding a solution that is optimal.

• Given an LP optimizer, we can find a feasible solution by optimizing with an arbitrary cost vector.
• Given an LP feasible solution finding algorithm, can compute the optimal solution by combining primal and dual. Specifically, suffices to find a feasible solution to the following set of LP constraints: \[ \{ Ax=b, x\geq 0, c^Tx=b^Ty, A^Ty\leq c\}, \] with $x$ and $y$ being the variables.

Rules for Taking Duals

• So far we defined a dual LP only when the primal LP was in standard form.
• Since every LP can be converted to standard form, this was sufficient.
• Still, having to go through the standard form to figure out the dual is a bit painful. \item Thus, below, we provide a general rules for taking a dual of an arbitrary LP.

• Consider a primal LP to be as follows: $$ \begin{eqnarray*} v^* &= &\min c_1x_1+c_2x_2+c_3x_3\\ A_{11}x_1+A_{12}x_2+A_{13}x_3 &= &b_1\\ A_{21}x_1+A_{22}x_2+A_{23}x_3 &\ge &b_2\\ A_{31}x_1+A_{32}x_2+A_{33}x_3 &\le &b_3\\ x_1 &\ge &0\\ x_2 & \le &0\\ x_3 &&UIS, \end{eqnarray*} $$ Here, we split the cost vector $c$ and the variables $x$ into the parts corresponding to different sign constraints. (UIS emphasizes the fact that the variables are unrestricted in sign.) Also, every submatrix of $A$ corresponds to a different combination of the sign of the variable and the constraint.
• The corresponding dual LP is: $$ \begin{eqnarray*} w&=&\max y_1b_1+y_2b_2+y_3b_3 \\ A_{11}^Ty_1+A_{21}^Ty_2+A_{31}^Ty_3 &\le &c_1\\ A_{12}^Ty_1+A_{22}^Ty_2+A_{32}^Ty_3 &\ge &c_2\\ A_{13}^Ty_1+A_{23}^Ty_2+A_{33}^Ty_3 &= &c_3\\ y_1 &&UIS\\ y_2 &\ge &0\\ y_3 &\le &0 \end{eqnarray*} $$
• In general, variable corresponds to constraint (and vice versa):

  PRIMAL	minimize	maximize	DUAL
  	$\ge b_i$	$\ge 0$
  constraints	$\le b_i$	$\le 0$	variables
  	$= b_i$	UIS
  	$\ge 0$	$\le c_j$
  variables	$\le 0$	$\ge c_j$	constraints
  	UIS	$= c_j$

Some observations:

• Adding primal constraints creates a new dual variable: more dual flexibility.
• The tighter the primal constraint, the looser the dual variable (and vice versa). In particular, equality primal constraints introduces a dual variable with an unrestricted sign.
• If constraint is in “natural” direction opposing the minimization/maximization, dual variable is positive (and vice versa).

Complementary Slackness

Duality leads to another idea: complementary slackness:

• Given feasible solutions $x$ and $y$, we define their duality gap as \[ c^Tx-b^Ty. \]
• Duality gap measures “how far off” our dual objective is from the primal objective. That is, how far from being optimal the solutions $x$ and $y$ are.
• Note: By weak duality we know that duality gap is always non-negative. Also, by strong duality, we know that when $x$ and $y$ is optimal the gap is zero.
• Let us rewrite our dual LP by changing inequalities into equalities by introducing additional variables: \[ \max b^T y \text{ s.t. } A^Ty+s=c, s\geq 0. \]
• The variables $s$ are called slack variables.
• Observe that \[ c^Tx-b^Ty = (A^Ty+s)^Tx-b^Ty = y^TAx+s^Tx-y^Tb=s^Tx. \]
• So, $x$ and $y$ are optimal iff $c^Tx-b^Ty=s^Tx=\sum_i s_i x_i$ is equal to $0$.
• Observe that $s,y\geq 0$. So, $\sum_i s_i x_i=0$ iff $s_ix_i=0$ for each $i$.

  $\Rightarrow$ Complementary slackness condition: Feasible primal and dual solutions $x$ and $y$ are optimal iff $x_is_i=0$, for each $i$.

• Note that $x_is_i=0$ implies that at most one of these variables can be non-zero.

  $\Rightarrow$ Either a primal variable $x_i$ is zero or its corresponding dual constraint is tight (i.e., $s_i=0$, which means that $A_i^Ty=c_i$).

Insights on Specific Problems via LP Duality

• The derivation of the LP dual is completely automatic/”brain-dead”.
• Still, understanding what problem the dual LP captures can bring a lot of non-trivial insight into the problem corresponding to the primal LP.
• This is the real power of LP duality!
• Nonetheless: Knowing the actual optimal dual solution may be useless for finding the primal optimum solution!

  $\Rightarrow$ More formally: if your algorithm runs in time $T$ to find primal optimal solution given an optimal dual solution, it can be adapted to run in time $O(T)$ and find the primal optimal solution without having to know the optimal dual solution!

  $\Rightarrow$ (See the problem set.)

• Let us take a look at the strong duality “in action” on a couple of example problems we studied before.

Shortest Paths Problem

• Let us formulate shortest paths as a “dual” (i.e., maximization) LP: $$ \begin{eqnarray*} w^*&=&\max d_t-d_s\\ \text{s.t.} && \\ d_j-d_i &\le &c_{e} \quad \quad\quad\quad\quad \text{ $\forall_{e=(i,j)}$} \end{eqnarray*} $$
• The constraint matrix $A$ has one row per each edge and one column per each vertex.
• The solution $d$ corresponds to embedding of vertices on the real line.

  $\Rightarrow$ All the constraints and the cost vector are “shift-invariant”, i.e., shifting each $d_i$ by the same value does not change anything.

  $\Rightarrow$ We can assume wlog $d_s=0$ and then $d_i$ is just the distance of vertex $i$ from vertex $s$ in this line embedding.

• Each constraints is just a triangle inequality imposed by edge $e$.
• Optimal solution sets $d_t$ to be the shortest $s$-$t$ path distance with all the constraints corresponding to the edges on this path being tight.
• What is the dual LP?
• One variable $y_e$ per each edge constraint. As these are upperbounding constraints, the variables $y_e$ are non-negative (see the correspondence table above - note that our dual LP here is “primal” from the point of view of the table as our primal LP corresponds to maximization).
• One constraint per each variable $d_i$. Since variables were unbounded, the constraint is an equality constraints. (Again, see the table above.)
• End result: $$ \begin{eqnarray*} v^*&=&\min \sum_e c_e y_e\\ \text{ s.t.} & &\\ \sum_{j} \left(y_{ji}-y_{ij}\right) & = & {\begin{cases} -1 & \text{if $i=s$}\\ 1 & \text{if $i=t$}\\ 0 & \text{otherwise} \end{cases}}\\ y &\ge &0\\ \end{eqnarray*} $$
• So, the dual of the shortest path problem is the task of sending one unit of flow from $s$ to $t$ while minimizing the cost (and having no capacity constraints).
• This makes a lot of sense and might seem not too profound but the key point is: we got this via purely syntactic manipulations!

Maximum Flow Problem

• Given our maximum flow instance, let us change it into a circulation problem by adding an edge from $t$ to $s$ and make it have infinite capacity, i.e., $u_{ts}=\infty$.
• Our goal then becomes to find a circulation that preserves all capacity constraints and maximizes the flow on the added “back edge” from $t$ to $s$.
• Our primal LP becomes: $$ \begin{eqnarray*} w^*& = &\max x_{ts}\\ \text{ s.t.} & &\\ \sum_w x_{vw}-x_{wv} &= &0 \quad \quad\quad\quad\quad \text{ $\forall_{v}$}\\ x_{e} &\le &u_{e} \quad \quad\quad\quad\quad \text{$\forall_{e}$}\\\ x &\ge &0, \end{eqnarray*} $$ with each variable $x_e$ encoding the flow on edge $e$.
• In our dual problem we have two types of variables: $z_v$ corresponding to each flow conservation constraint; and $y_e$ corresponding to each capacity constraint.
• One constraint per each variable $x_e$.
• The resulting dual LP is: $$ \begin{eqnarray*} v^*&=&\min \sum_{e} u_e y_{e}\\ \text{ s.t.} & &\\ z_v-z_w+y_{vw} &\ge &0 \quad \quad\quad\quad\quad \text{ $\forall_{(v,w)\neq (t,s)}$}\\ z_t-z_s+y_{ts} &\ge &1\\ y &\ge &0 \end{eqnarray*} $$
• Think of $y_{e}$ as “lengths”
• Note: Can wlog assume that $y_{ts}=0$ since otherwise dual infinite due to the fact that $u_{ts}=\infty$.
• So, we actually need to have that $z_t-z_s \ge 1$.
• Observe: Variables $z_v$ can be viewed as “distances” and the corresponding constraints are just triangle inequality constraints for them wrt lengths given by $y$s.
• Since the occurrences of $z$s are shift-invariant can assume wlog that $z_s=0$ and thus $z_v$ is again the distance of $v$ from $s$ in the line embedding given by $z$.
• So, our goal is to choose edge lengths $y$ so as the sink $t$ is at distance of at least $1$ from $s$ wrt lengths $y$ while minimizing the total volume of the edges.
• Side note: This gives good justification for shortest augmenting path argument and blocking flows. This is not unusual: many primal-dual algorithms leverage dual solution to indicate the best way to optimize the primal solution.
• How to solve our optimization task?
• One approach: find the minimum $s$-$t$ cut $S^*$, assign lengths $1$ to all the edges leaving it and $0$ to all the remaining ones.

  $\Rightarrow$ Our volume will be equal to the capacity of this cut $u(S^*)$. So, by weak duality, we get $w^*\leq u(S^*)$, i.e., that the maximum flow value $w^*$ is at most the capacity of the minimum $s$-$t$ cut!

• Would like use strong duality to also get the max flow min cut theorem, but to this end need to argue that $v^*=w^*\geq u(S^*)$, i.e., the dual “volume” problem does not have a better solution that the one given by the minimum $s$-$t$ cut.
• To do that, consider the optimal dual solution $y^*$, $z^*$.
• Define a cut $S=\{v \mid z_v^* < 1\}$.

  $\Rightarrow$ Need to have that $s\in S$ and $t\notin S$. So, $S$ is an $s$-$t$ cut.

• We now use complementary slackness:
  • If $(v,w)$ leaves $S$, then $y_{vw}^* \ge z_w^*-z_v^* > 0$

    $\Rightarrow$ the corresponding primal constraints $x_{vw}^* \leq u_{vw}$ corresponding to the dual variable $y_{vw}^*$ has to be tight, i.e., $x_{vw}^*=u_{vw}$ for any primal optimal solution $x^*$.

  • If $(v,w)$ enters $S$, then $z_v^*>z_w^*$. Also, we know $y_{vw}^*\ge 0$

    $\Rightarrow$ $z_v^*+y_{vw}^*>z_w^*$ i.e. the dual constraint corresponding to the primal variable $x_{vw}^*$ is not tight.

    $\Rightarrow$ $x_{vw}^*=0$.

  • So, in other words, in the optimal solution $x^*$ all edges leaving $S$ are saturated, all edges entering $S$ are empty.

    $\Rightarrow$ The value of the flow $w^*$ is equal to the capacity $u(S)$ of $S$, which is at least the capacity $u(S^*)$.

• We indeed recovered the max-flow min-cut theorem!

Minimum Cost Circulation Problem

• Can adapt our maximum flow formulation. Just need to add costs on edges (and make it be minimization instead of maximization problem).
• The resulting primal LP: $$ \begin{eqnarray*} v^*&=&\min \sum_e c_{e} x_{e}\\ \text{ s.t.} & &\\ \sum_w x_{vw}-x_{wv} &= &0 \quad \quad\quad\quad\quad \text{ $\forall_{v}$}\\ x_{e} &\le &u_{e} \quad \quad\quad\quad\quad \text{$\forall_{e}$}\\\ x &\ge &0, \end{eqnarray*} $$
• The dual LP almost the same as before, except our right-side constraints changed (as our primal cost vector changed) and changing the primal problem to be a minimization one flipped the sign constraints on variables $y$.
• The resulting dual LP: $$ \begin{eqnarray*} w^*&=&\max \sum_{e} u_e y_{e}\\ \text{ s.t.} & &\\ z_v-z_w+y_{vw} &\le & c_{vw} \quad \quad\quad\quad\quad \text{ $\forall_{(v,w)}$}\\ y &\le &0 \end{eqnarray*} $$
• Changing variables $p_v=-z_v$ and rearranging the constraints gives us: $$ \begin{eqnarray*} w^*&=&\max \sum_{e} u_e y_{e}\\ \text{ s.t.} & &\\ y_{vw} &\le & c_{vw} +p_v -p_w \quad \quad\quad\quad\quad \text{ $\forall_{(v,w)}$}\\ y &\le &0 \end{eqnarray*} $$
• But $c_{vw} +p_v -p_w $ is just the reduced cost $c^{(p)}_{vw}$ of the edge $(v,w)$!
• Note: Optimum $\le 0$ since $y=0$ is a feasible solution. (Put differently: zero circulation is feasible.)
• Note: $y\le 0$ says the objective function is the sum of the negative parts of the reduced costs. (Positive ones get truncated to $0$.)
• Let $x^*$ and $y^*$ (and prices $p^*$) be the primal and dual optimal solutions.
• Invoking complementary slackness tells us that:
  • If $x_{vw}^*< u_{vw}$ then the corresponding dual variable $y_{vw}^*$ is equal to $0$.

    $\Rightarrow$ $c_{vw}^{(p^*)}\ge 0$.

  • If $c_{vw}^{(p^*)}< 0$ then $x_{vw}^*=u_{vw}$.
  • This means that all edges with negative reduced cost have to be saturated!
  • On the other hand, if $c_{vw}^{(p^*)} > 0$

    $\Rightarrow$ the constraint on $y_{vw}^*$ is slack (as $y^*\leq 0$).

    $\Rightarrow$ The corresponding variable $x_{vw}^*=0$.

  • So, all the edges with positive reduced cost need to carry no flow!