# Duality

PDF of Eric’s written notes are here.

Max-flow via Linear Programming

Variables $f_e$ for every $e\in E$. Objective function: $\max\sum_{\overrightarrow{sz}\in E}f_{sz}$. Constraints: for every $e\in E$, $0\le f_e\le c_e$, for every $v\in V-\{s,t\}$, $\sum_{\overrightarrow{wv}\in E}f_{wv}=\sum_{\overrightarrow{vz}\in E}f_{vz}$.

Standard form for LP

$n$ variables $x=\begin{pmatrix} x_1\\\vdots\\x_n\end{pmatrix}$, $m$ constraints $A=\begin{pmatrix} a_{11} & \cdots & a_{1n}\\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix}$, objectives $c=\begin{pmatrix} c_1\\\vdots\\c_n\end{pmatrix}$, and $b=\begin{pmatrix} b_1\\\vdots\\b_m\end{pmatrix}$. We want to maximize $c^Tx$ subject to $Ax\le b, x\ge 0$. (for example refer to the written notes)

Primal LP                                                    Dual LP

\begin{aligned} \max c^Tx\text{ s.t. }Ax\le b, x\ge 0 &\qquad\overrightarrow{\text{dual}} & \min b^Ty\text{ s.t.}A^ty\ge c, y\ge 0\\ \uparrow\text{ standard form} & & \downarrow\text{ standard form} \\ \min -c^Tx\text{ s.t. }-Ax\ge -b, x\ge 0 &\qquad\underleftarrow{\text{dual}} & \max -b^Ty\text{ s.t.} -A^Ty\le -c, y\ge 0 \end{aligned}

So dual(dual)=primal.

For a LP, optimum is achieved at a vertex of the feasible region except if

• it’s infeasible (e.g.: $x_1\le 100$ & $x_1\ge 200$), so feasible region is empty
• it’s unbounded (e.g.: $\max x_1+x_2$ s.t. $x_1, x_2\ge 0$)

Weak duality theorem

For a LP whose primal and dual are feasible, their optimum $x^*$ and $y^*$ satisfy $c^Tx^*\le b^Ty^*$

Consequence: if we have a feasible $x$ of primal LP and a feasible $y$ of dual LP, and $c^Tx=b^Ty$, then $x$ and $y$ are optimal solutions.

Strong duality theorem

If primal LP has optimal $x^*$ and dual LP has optimal $y^*$, then $c^Tx^*=b^Ty^*$.

If primal LP is unbounded, then dual LP is infeasible.

If dual LP is unbounded, then primal LP is infeasible.

Line fitting

Given points $(x_1,y_1), (x_2,y_2),\dots,(x_n,y_n)$, find the line $y=ax+b$ which minimizes the maximum distance.

Variables: $a, b, e$. Goal: minimize $e$ where for all $I$, $|y_i-(ax_i+b)|\le e$

Example: $(x_1,y_1)=(1,1), (x_2,y_2)=(2,1), (x_3,y_3)=(3,2)$.

LP Problem: variables $a,b,e$, minimize $e$ s.t.

• $|1-a-b|\le e\longrightarrow 1-a-b\le e, 1-a-b\ge -e$
• $|1-2a-b|\le e\longrightarrow 1-2a-b\le e, 1-2a-b\ge -e$
• $|2-3a-b|\le e\longrightarrow 2-3a-b\le e, 2-3a-b\ge -e$

In standard form, maximize $-e$, s.t.

• $-a-b-e\le -1$
• $a+b-e\le 1$
• $-2a-b-e\le -1$
• $2a+b-e\le 1$
• $-3a-b-e\le -2$
• $3a+b-e\le 2$

How to get nonnegative constraints? Make variables $a^+,a^-,b^+,b^-,e^+,e^-$, and replace $a=a^+-a^-, b=b^+-b^-, e=e^+-e^-$.

New LP becomes: maximize $-e^++e^-$ s.t.

• $-(a^+-a^-)-(b^+-b^-)-(e^+-e^-)\le -1$
• $(a^+-a^-)+(b^+-b^-)-(e^+-e^-)\le 1$
• $-2(a^+-a^-)-(b^+-b^-)-(e^+-e^-)\le -1$
• $2(a^+-a^-)+(b^+-b^-)-(e^+-e^-)\le 1$
• $-3(a^+-a^-)-(b^+-b^-)-(e^+-e^-)\le -2$
• $3(a^+-a^-)+(b^+-b^-)-(e^+-e^-)\le 2$
• $a^+,a^-,b^+,b^-,e^+,e^-\ge 0$