# Linear Program Linear program function: $min \sum c_j x_j$, s.t. $\sum a_{ij} x_j \le b_i (\text{linear inequality constraint) or} \sum d_{ij} x_j = f_i (\text{linear equality constraint})$ Matrix notation: $min c^T x$ s.t. $Ax \le b, Dx = f$ where $a_{ij}$ is the $(i,j)^{th}$ element of A Linear program are a subset of convex programs Unbounded linear program: $min x_1, x_1 \le 4$ Infeasible linear program: $minx_1, x_1 \le 3, x_1 > 4$ # Geometry of LPs We have a LP: $min c^T x$ s.t. $Ax \le b, Dx = f$, $Dx=f$ is an intersection of hyperplanes, $Ax \le b$ is an intersection of hyperspaces An intersection of a finite number of half spaces and hyperplanes. Feasible set of an LP is polyhedron and optima occur at extreme points ![[Pasted image 20260916122136.png]] Extreme point: a point X is an extreme point of a polytope P if: definition 1: it is not the convex combination of any two other points in the polytope if $y, z \in P, \lambda \in [0,1], s.t. x=\lambda y + (1-\lambda)z$, then x is **not** extreme definition 2: it is the unique optimum for some cost vector c, $c^Tx<c^Ty$ for any $y \in P$ it is possible for a polyhedron to have no extreme point if LP has a finite optimum and its constraint polytope has at least one extreme point, then there is an extreme point which is optimal ![[Pasted image 20260916122907.png|249]] Basic feasible point (BFS): polytope p ${x|Ax \le b, Dx=f}$ active constraint at x is constraint $a_i$ is active at x if $a_i^Tx=b_i$ active set at x: $Ax = {a_i: a_i^Tx=b_i} \cup {d_i: d_i^T=f_i}$ bfs: x is a bfs if its active set $Ax$ has n linearly independent vectors # Duality For every LP there is an associated alternative LP: that has the same optimal value can guarantee optimality of a particular point provides structural insights into problems provides new algorithms to solve LPs To find dual of LP $min cx, s.t. Ax=b, x\ge 0$: introduce penalty variables: $min \ max \ cx + p(b-Ax)$ interchange max and min $max \ min \ cx + p(b-Ax)$ rewrite and find dual of this LP: $max \ pb, s.t. c-pA \ge 0$ # Weak Duality The way how dual LP comes from the primal LP using penalty variables and exchanging min and max. For the standard primal: $ minc^Tx, s.t. Ax=b, x \ge0 $ derives the dual: $ max p^Tb, s.t. c^T-p^TA \ge 0 $ the result is weak duality: $c^Tx \ge p^Tb$ for any primal-feasible x and any dual-feasible p. in other words, for a primal minimization problem, every dual feasible solution gives a **lower bound** on the primal objective $min_{x} max_{y} f(x,y) \ge max_{y} min_{x} f(x,y)$ so weak duality says: dual optimum $\le$ primal optimum "dual can never beat the primal" ``` Dual side Primal side $70 $80 $90 $110 $130 |----------|----------|------------|----------| lower bounds feasible costs ? optimum ? ``` # Strong Duality For LPs, if the primal and dual are feasible and have optimal solution x and p, then $c^Tx=b^Tp$, this is strong duality. so the relationship becomes: Farkas' Lemma: one of two alternatives occurs: either a vector c can be represented as a nonnegative combination of vectors a, $c=\sum_{i}p_ia_i, p_i \ge 0$ or there exists a separating direction d satisfying $d^Ta_i \ge 0$ for all i, while $d_Tc <0$. "at optimal, dual and primal meet and there is no gap -> strong duality = same optimal value" ``` Dual Primal → → → → → $100 ← ← ← ← ← ↑ OPTIMUM ``` # Complementary Slackness Strong duality tells us that the two optimal objective values are equal. Complementary slackness tells us which constraints and variables must be active at the optimum. we use: $ primal: min_{x}c^Tx, s.t. Ax \ge b, x \ge 0 $ and $ dual: max_{y} b^Ty, s.t. A^Ty \le c, y\ge 0 $ for primal-feasible x and dual-feasible y, they are optimal if and only if the complementary slackness conditions hold. for each primal constraint i: $(b_i-\sum_{j}a_{ij}x_{j})y_{i}=0$ for each primal variable j: $(\sum_{i}a_{ij}y_{i}-c{j})x_{j}=0$ slack x corresponding dual variable = 0 Therefore: - if a primal constraint has slack, its corresponding dual variable must be 0 - if a dual variable is positive, the corresponding primal constraint must be tight - if a primal variable is positive, its corresponding dual constraint must be tight "which constraint matter at the optimum, given we already know optimum under strong duality, complementary slackness helps explain the relationship between the optimal primal and dual solution" # Duality Examples ## Robust LPs start with normal LP $min_{x} c^Tx, s.t. a_{i}^Tx \le b_i$, we assume $c, a_i,b_i$ are known exactly for example $2x_1+3x_2 \le 100$, but suppose we don't know them exactly they could be $2.1x_1+3.2x_2\le 103$, we know the coefficients are into an uncertainty set such as $a_i \in U_a$, the robust constraint becomes: $ a_i^T x \le b_i, \forall a_i \in U_a $ constraints must work for every possible $a_i$ in the uncertainty set. such as $a \in \{(2,3),(2.1,3.2),(1.9,2.8)\}$, so x must survives uncertainty. to solve this, we can think of worst case, $maxa_i^Tx \le b_i$, such as $a_i^Tx \in \{70,80,95,88\}$, then the worst case is 95, and $95 \le 100$, then all others survives. We have an optimization inside an optimization. $ maxa_i^Tx, s.t. D_ia_i \le d_i $ this itself is an LP. and then we take its dual. Dualize the inner worst-case LP as: $ minp_i^Td_i, s.t. D_i^Tp_i = x, p_i \ge 0 $ by strong duality, $\boxed{
\max_{\substack{a_i\\D_i a_i\le d_i}}
a_i^Tx
=
\min_{\substack{p_i\ge0\\D_i^Tp_i=x}}
p_i^Td_i.
}$ so the final optimization becomes and everything is linear again: $ \boxed{
\begin{aligned}
\min_{x,\{p_i\}}\quad
&c^Tx\\
\text{s.t.}\quad
&p_i^Td_i\le b_i,
\qquad \forall i,\\
&D_i^Tp_i=x,
\qquad \forall i,\\
&p_i\ge0,
\qquad \forall i.
\end{aligned}
} $ The whole process is uncertainty $\rightarrow$ Worst case $\rightarrow$ Inner LP $\rightarrow$ Dualize it $\rightarrow$ Ordinary LP ## Two-person zero sum games two players are choosing strategies against each other. one tries to minimize the payoff, the other tries to maximize it. LP strong duality proves that their optimal strategies meet at the same game value. $ A=
\begin{bmatrix}
1 & -1\\
-1 & 1
\end{bmatrix}. $ player 1 choose a row, and player 2 choose a column, if player 1 choose row 1 and player 2 choose row 1, then $A_{11}=1$, meaning player 2 gets 1, because this is zero-sum game, so player 1 get -1. Their goal are opposite: player 1 want to minimize the payoff, player 2 want to maximize the payoff. player 1 should never always choose row 1 or row 2 because player 2 will always try to minimize its output. same way for player 2. they should randomize their selection. then we introduce probability $ player1: x=
\begin{bmatrix}
x_1\\x_2
\end{bmatrix},
\qquad
x_1+x_2=1,
\qquad
x_i\ge0 $ $ player2: y=
\begin{bmatrix}
y_1\\y_2
\end{bmatrix},
\qquad
y_1+y_2=1,
\qquad
y_j\ge0. $ expected payoff to player 2 is $x^TAy=\sum_i \sum_j A_{ij}x_iy_j$ for example, $x=
\begin{bmatrix}
0.5\\
0.5
\end{bmatrix},
\qquad
y=
\begin{bmatrix}
0.5\\
0.5
\end{bmatrix}. $ there are 4 outcomes, each with probability of 0.25 then: $E=0.25(1)+0.25(-1)+0.25(-1)+0.25(1)=0$ For player 1, he will think for every x i choose, what is the worst thing player 2 could do to me: $max_y x^TAy$ Player 1 then choose x that make the worst case value as small as possible: $min_x max_y x^TAy$ For player 2, he think in the opposite direction. then player 2 choose y to $max_y min_x x^TAy$ **Strong duality** shows the dual LP and primal LP optimal are same, then: $\boxed{
\min_x\max_y x^TAy
=
\max_y\min_x x^TAy.
}$ player 1's problem is LP by introducing t, then: $ \boxed{
\begin{aligned}
\min_{x,t}\quad&t\\
\text{s.t.}\quad
&x^TA_j\le t,\qquad\forall j,\\
&x\ge0,\\
&\mathbf 1^Tx=1.
\end{aligned}
} $ similarly, player 2's problem is LP by introducing w as lower bound: $ \boxed{
\begin{aligned}
\max_{y,w}\quad&w\\
\text{s.t.}\quad
&(Ay)_i\ge w,\qquad\forall i,\\
&y\ge0,\\
&\mathbf1^Ty=1.
\end{aligned}
} $ generalize the example, $x=
\begin{bmatrix}
p\\
1-p
\end{bmatrix}$ if player 2 choose column 1: $E=p(1)+(1-p)(-1)
=
2p-1$, if player 2 choose column 2: $E=p(-1)+(1-p)(1)
=
1-2p$, player 2 choose whichever is larger $max\{2p-1,1-2p\}$ , player 1 want to minimize this maximum, so the best thing is $2p-1=1-2p, \rightarrow p=\frac{1}{2}$ ## Max-flow min-cut suppose a network a water pipeline: ``` 5 ┌────────→ A ─────────┐ │ │ 3 │ ↓ SOURCE s SINK t │ ↑ │ │ 4 └────────→ B ─────────┘ 6 ``` max flow = maximum amount that can travel from source to sink we cut pipes so that there is no longer any path from source to t min cut = the cheapest set of edges we can cut to disconnect s from t flow $\le$ cut, this is weak duality # Semidefinite Programming LP constrains numbers, SDP constrain an entire matrix. instead of saying a scalar expression must be nonnegative, like $a^Tx+b \ge 0$ SDP can say a matrix must be positive semidefinite Semidefinite: suppose M is a symmetric matrix, it can be decomposed into eigenvalues and eigenvectors: $M=V * V^T = \sum_i{\lambda_iv_iv_i^T}$, M is semidefinite when $\lambda_i \ge 0$ so all eigenvalues must be non-negtive. For example: $ M=\begin{bmatrix} 1&-1\\ -1&1 \end{bmatrix} $ contains negative entries but its eigenvalues are 0,2 so the equivalent definition is "PSD means the matrix behaves like a nonnegative number in every direction"