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$

Leave a comment Cancel reply