Unit 0.1 · Start here

The whole of Part 2 on one page

Sources: L9 §2; L11 §5; L12 intro; every supplied PDF

Part 2 changes the way you design algorithms. Part 1 used divide and conquer, dynamic programming and graph structure. In Part 2 you describe the feasible solutions and the objective mathematically, then use the structure of the resulting optimization problem.

Block	Lectures	The main question
Linear programming	9–11	How do we model a problem with linear constraints? How can we certify that a solution is optimal?
Convex optimization	12–13	What still works when the objective is not linear? How does gradient descent find an approximately optimal solution?
Approximation algorithms	14–15	When exact discrete optimization is hard, how do greedy choices, matchings, LP relaxations and rounding give solutions that are provably within a factor of optimal?

The one idea that ties everything together

Each part of this material has the same two pieces: an algorithm finds a solution, and a certificate proves how good it is.

Read left to right along the top, then back along the bottom row. Each box is a chapter.

1 · LP models

Turn word problems into $\max c\T x$ with $Ax\le b,\ x\ge 0$ . Convert any form into this one.

2 · LP geometry

Feasible regions are convex. If an optimum exists, some optimal point is at a corner. The exact answer needs only polynomially many bits.

3 · Duality

Prices on constraints prove upper bounds. Weak and strong duality, writing duals (an exam question), complementary slackness.

4 · Max-flow = min-cut

The flow dual is a system of edge lengths, and threshold rounding turns lengths into a cut.

5 · Why strong duality holds

Cones, Farkas' lemma, separating hyperplanes, active constraints.

6 · Convexity

Convex functions: chord, tangent and Hessian tests, rules for building them, least squares, and why every local minimum is global.

7 · Gradient descent

Steepest descent, step sizes, and the full $DG/\sqrt T$ proof.

8 · Projections & smoothness (L13)

Projected GD for constraints, β-smoothness, the descent lemma, and the faster $\beta D^2/(2T)$ guarantee for the last iterate.

9 · Approximation algorithms (L14–L15)

α-approximations, greedy vertex cover ( $O(\log n)$ ), maximal matching (factor 2), LP relaxation and threshold rounding (factor 2), the matching dual, integrality gaps, facility location.

10 · Exam toolkit

Proof templates, traps, a decoded formula sheet, and 80+ practice questions with answers.

How to read these notes

Every important formula is in a box like this one, followed by a decoding:

Example of a decoded formula

c^{\top}x \;=\; \sum_{i=1}^{n} c_i x_i

In words"c-transpose-x" is just a weighted sum: multiply each choice by its score and add.

Symbol by symbol

$x_i$	how much of choice $i$ you make (a decision variable)
$c_i$	score (revenue, cost, …) per unit of choice $i$
$\sum_{i=1}^n$	"add up, for $i=1,2,\dots,n$ "

Why it is trueIt is the definition of the dot product.

When you use itEvery LP objective is written this way.

The coloured boxes mean:

Interactive diagrams (tagged Interactive) sit next to the text they explain. Drag points and move sliders, then check the live numbers against the formulas. Your progress (the "I understand this unit" boxes) and the dark-mode choice are saved in this browser. Use ←/→ to move between units and / to search. One page shows everything on a single page for printing or Ctrl+F.

A study routine that works with the pictures

Picture first. Before reading a formula, describe the figure: what moves, what stays feasible, what blocks improvement.
Decode. Read the "In words" line and the symbol table, then cover them and explain the formula aloud.
Re-derive. For every inequality in a proof, say which assumption it uses: feasibility, nonnegativity, convexity, a gradient bound, Cauchy–Schwarz, or "a square is ≥ 0".
Test. Do the quick checks in each unit, then the practice bank before opening the answers.

I understand this unit

Unit 0.2 · Start here

Math toolkit I: vectors, matrices, inequalities

Sources: L9 §3; L12 §2

Almost every formula in Part 2 uses a few pieces of linear algebra. If a formula ever looks unreadable, come back to this unit.

Vectors and coordinatewise inequalities

A vector $x\in\R^n$ is a column of $n$ real numbers $x=(x_1,\dots,x_n)\T$ . Comparisons between vectors are coordinatewise:

Vector inequality

x \ge 0 \iff x_i \ge 0 \text{ for every } i, \qquad Ax\le b \iff (Ax)_j\le b_j \text{ for every row } j.

In wordsA vector inequality is many ordinary inequalities written at once, one per coordinate.

Symbol by symbol

$\R^n$	the set of all lists of $n$ real numbers
$\iff$	"if and only if": the two statements are equivalent
$(Ax)_j$	the $j$ -th entry of the vector $Ax$

When you use itWhenever you see $\le$ between vectors, write out the rows to check signs.

Transpose and the dot product

Dot product (inner product)

\langle u,v\rangle \;=\; u\T v \;=\; \sum_{i} u_i v_i \;=\; \norm{u}\,\norm{v}\cos\alpha

In wordsMultiply matching coordinates and add. Geometrically, it is length × length × cosine of the angle between the vectors.

Symbol by symbol

$u\T$	"u transpose": the column turned into a row, so that row × column gives one number
$\langle u,v\rangle$	other notation for the same number (used in L12)
$\norm{u}=\sqrt{\sum_i u_i^2}$	Euclidean length of $u$ (the 2-norm, sometimes written $\norm{u}_2$ )
$\alpha$	the angle between $u$ and $v$

Why it is trueThe cosine form comes from the law of cosines applied to the triangle with sides $u$ , $v$ , $u-v$ .

When you use itSign of the dot product = which side of a line or plane a vector points to. Positive: acute angle (same general direction). Zero: perpendicular. Negative: obtuse (opposite direction). Farkas, separation and gradient descent all rely on this.

The sign of a dot product tells you whether two vectors point "with" or "against" each other.

Intuitive approach

A dot product is a shadow

Shine a light straight down onto the line through $u$ . The vector $v$ casts a shadow on that line of signed length $\norm v\cos\alpha$ : positive if it falls in $u$ 's direction, negative if it falls behind. The dot product is "length of $u$ × length of $v$ 's shadow on $u$ ":

\langle u,v\rangle=\norm u\cdot(\text{signed shadow of }v\text{ on }u).

Cauchy–Schwarz then says something obvious: a shadow is never longer than the stick, so $\lvert\langle u,v\rangle\rvert\le\norm u\norm v$ . The shadow is as long as the stick (or as negative) only when the stick lies along the line, i.e. $v$ is parallel to $u$ .

The dot product measures how much of

v

points along

u

.

Matrix times vector: the row view and the column view

For $A\in\R^{m\times n}$ ( $m$ rows, $n$ columns) and $x\in\R^n$ , there are two equally correct ways to read $Ax\in\R^m$ :

Rows are restrictions; columns are recipes. Duality swaps the two (the transpose

A\T

turns columns into rows).

Matrix–vector product

(Ax)_j \;=\; \sum_{i=1}^{n} A_{ji}\,x_i \quad (j=1,\dots,m), \qquad (A\T y)_i \;=\; \sum_{j=1}^{m} A_{ji}\,y_j \quad (i=1,\dots,n).

In words $Ax$ runs along a row of $A$ . $A\T y$ runs down a column of $A$ .

Symbol by symbol

$A_{ji}$	entry in row $j$ , column $i$ : how much of resource $j$ one unit of choice $i$ uses
$m$	number of constraints (rows)
$n$	number of variables (columns)
$A\T$	transpose: $(A\T)_{ij}=A_{ji}$ , an $n\times m$ matrix

When you use itDual constraints are $(A\T y)_i\ge c_i$ : one per primal variable, built from a primal column.

Two identities are used constantly:

(A\T y)\T x \;=\; y\T A x \;=\; \sum_{j}\sum_{i} y_j A_{ji} x_i, \qquad (AB)\T = B\T A\T.

In wordsA number equals its own transpose, so you can move $A$ to the other side of the dot product by transposing it.

Why it is trueBoth sides are the same double sum, added in a different order.

When you use itThe weak-duality chain $c\T x\le (A\T y)\T x=y\T Ax\le y\T b$ .

Linear combinations, cones and convex combinations

Name	Form	Allowed weights	Picture of all of them
Linear combination	$\sum_j\lambda_j a_j$	any real $\lambda_j$	a line / plane through 0 (a subspace)
Conic (nonnegative) combination	$\sum_j\lambda_j a_j$	$\lambda_j\ge 0$	a cone (a wedge from 0)
Convex combination	$\sum_j\lambda_j a_j$	$\lambda_j\ge0,\ \sum_j\lambda_j=1$	the filled polygon spanned by the points

A set of vectors is linearly independent if no vector is a linear combination of the others. In $\R^n$ at most $n$ vectors can be independent, and $n$ independent vectors span $\R^n$ : every vector is some linear combination of them. You need this for vertices (Chapter 2).

Lengths and the "expand the square" identity

Expanding a squared norm

\norm{a-b}^2 \;=\; \norm{a}^2 \;-\; 2\langle a,b\rangle \;+\; \norm{b}^2

In wordsThe vector version of $(a-b)^2=a^2-2ab+b^2$ .

Symbol by symbol

$\norm{a}^2=\langle a,a\rangle$	squared length (no square root, easier to handle)

Why it is true $\norm{a-b}^2=\langle a-b,a-b\rangle$ . Expand the inner product like a product of brackets, using $\langle a,b\rangle=\langle b,a\rangle$ .

When you use itTwice: in the separation proof (L11, with $a=p-q$ , $b=\theta(z-q)$ ) and in the gradient-descent proof (L12, with $a=x_t-x^*$ , $b=\eta g_t$ ).

Cauchy–Schwarz inequality

-\norm{u}\,\norm{v} \;\le\; \langle u,v\rangle \;\le\; \norm{u}\,\norm{v}

In wordsA dot product can never be bigger (in absolute value) than the product of the lengths. Equality on the left happens exactly when $v$ points opposite to $u$ (or one of them is $0$ ).

Why it is true $\langle u,v\rangle=\norm u\norm v\cos\alpha$ and $-1\le\cos\alpha\le1$ . The lowest value, $\cos\alpha=-1$ , occurs at $\alpha=180^\circ$ .

When you use itProving that $-\nabla f(x)$ is the steepest descent direction (L12 §4.1).

Quick check: with

A=\begin{pmatrix}1&0&1\\2&1&1\\0&2&1\end{pmatrix}

and

y=(5,0,2)\T

, compute

A\T y

.

Show answer

Go down each column: column 1 gives

1\cdot5+2\cdot0+0\cdot2=5

, column 2 gives

0\cdot5+1\cdot0+2\cdot2=4

, column 3 gives

1\cdot5+1\cdot0+1\cdot2=7

. So

A\T y=(5,4,7)\T

. This is the smoothie dual check from Chapter 3.

I understand this unit

Unit 0.3 · Start here

Math toolkit II: calculus and logic words

Sources: L12 §2–4; Lec12_secB pp.1–4

Gradient and Hessian

Gradient

\nabla f(x) \;=\; \Big(\tfrac{\partial f}{\partial x_1}(x),\ \dots,\ \tfrac{\partial f}{\partial x_d}(x)\Big)^{\!\top} \in \R^d

In wordsCollect all partial derivatives into one vector. It points in the direction of steepest increase, and its length is the steepness.

Symbol by symbol

$f:\R^d\to\R$	a function that takes $d$ numbers and returns one number (a "landscape")
$\partial f/\partial x_i$	rate of change of $f$ if you move only coordinate $i$

When you use itGradient descent moves in direction $-\nabla f$ .

Hessian

\nabla^2 f(x) \;=\; \Big[\tfrac{\partial^2 f}{\partial x_i\,\partial x_j}(x)\Big]_{i,j=1}^{d} \in \R^{d\times d}

In wordsThe matrix of second derivatives: how the slope changes as you move. It measures curvature.

Why it is trueFor a function with continuous second derivatives the matrix is symmetric, since $\partial^2 f/\partial x_i\partial x_j=\partial^2 f/\partial x_j\partial x_i$ .

When you use itTesting convexity: $f$ is convex exactly when $v\T\nabla^2 f(x)v\ge0$ for all $v$ and $x$ (Chapter 6).

Useful gradients to know by heart:

$f(x)$	$\nabla f(x)$	$\nabla^2 f(x)$
$c\T x$ (linear)	$c$	$0$
$\tfrac12\norm{x}^2$	$x$	$I$
$\tfrac12 x\T Qx$ ( $Q$ symmetric)	$Qx$	$Q$
$\tfrac12\norm{Ax-b}^2$ (least squares)	$A\T(Ax-b)$	$A\T A$

First-order Taylor expansion and little-o

Linear approximation

f(x+h) \;=\; f(x) + \langle\nabla f(x),h\rangle + o(\norm h)

In wordsNear $x$ a smooth function looks like a plane (its tangent). The error is negligible compared to the step size $\norm h$ when $h$ is tiny.

Symbol by symbol

$h$	a small step (a vector)
$\langle\nabla f(x),h\rangle$	the predicted change, i.e. the directional derivative times the step
$o(\norm h)$	"little-o": some error term $e(h)$ with $e(h)/\norm h\to0$ as $h\to0$

When you use itDeriving the steepest descent direction. The first-order convexity inequality is the global version: the tangent stays below the graph everywhere, not only nearby.

Logic and set notation used in proofs

Symbol	Read as	Example
$\forall$	for every	$\forall z\in C:\ v\T z\le v\T q$
$\exists$	there exists	$\exists\,y\ge0$ with $A\T y\ge c$
$\iff$ , "iff"	if and only if (both directions)	$f$ convex $\iff$ tangent inequality
$\Rightarrow$	implies (one direction only)	primal unbounded $\Rightarrow$ dual infeasible
$\{x: \dots\}$	the set of all $x$ such that …	$P=\{x:Ax\le b,\ x\ge0\}$
$\arg\min_{x\in K} f(x)$	a point of $K$ where $f$ is smallest (not the value)	$x^\in\arg\min f$ ; $f(x^)$ is the value
$\min$ vs $\inf$	$\inf$ = greatest lower bound, may not be attained	$\inf_{x>0}x=0$ but no minimum
$\max$ vs $\sup$	$\sup$ = least upper bound	$\sup\{x:x<1\}=1$ , no maximum
$\theta\downarrow0$	$\theta$ tends to 0 from above	used in "take the limit" proofs
$\delta^+(S)$	edges leaving set $S$	a directed cut
$\mathcal P$	set of all simple $s$ - $t$ paths	path-flow LP

Sums you will meet in convergence proofs

Harmonic sum

\sum_{t=1}^{T}\frac1t\;\le\;1+\ln T.

In wordsAdding $1+\tfrac12+\tfrac13+\dots+\tfrac1T$ grows only like a logarithm.

Symbol by symbol

$\ln$	natural logarithm (in algorithm analysis $\log$ usually means $\ln$ or $\log_2$ ; they differ by a constant factor)

Why it is trueFor $t\ge2$ , $\frac1t\le\int_{t-1}^{t}\frac{dx}{x}$ because $\frac1x\ge\frac1t$ on $[t-1,t]$ . Summing from $t=2$ to $T$ : $\sum_{t=2}^T\frac1t\le\int_1^T\frac{dx}x=\ln T$ . Add the $t=1$ term.

When you use itStep-size schedules like $\eta_t\propto\frac1t$ produce such sums.

Other standard sums

\sum_{t=1}^T t=\frac{T(T+1)}2,\qquad\sum_{t=0}^{T-1}r^t=\frac{1-r^T}{1-r}\le\frac1{1-r}\ (0\le r<1),\qquad\sum_{t=1}^T\frac1{\sqrt t}\le2\sqrt T.

Why it is trueArithmetic and geometric series; the last one by the same integral comparison as above ( $\int_0^T x^{-1/2}dx=2\sqrt T$ ).

Six proof patterns used again and again

"Weighted sum of valid inequalities is valid": if $a_1\le b_1$ and $a_2\le b_2$ and $y_1,y_2\ge0$ , then $y_1a_1+y_2a_2\le y_1b_1+y_2b_2$ . A negative weight flips the inequality. This one fact is all of LP duality.
"Take a tiny step along a segment": $x+\theta(y-x)$ with $\theta\to0$ . It appears in convexity of sets, the tangent inequality, local ⇒ global, and separation.
"Telescoping": $\sum_{t=0}^{T-1}(R_t-R_{t+1})=R_0-R_T$ . Every middle term cancels. This is the core of the gradient-descent proof.
"Telescoping with changing weights": if each step gives a term $a_tR_t-b_tR_{t+1}$ with nonnegative $R_t$ and coefficients that change with $t$ , regroup by $R_t$ : $\sum_{t=0}^{T-1}(a_tR_t-b_tR_{t+1})=a_0R_0+\sum_{t=1}^{T-1}(a_t-b_{t-1})R_t-b_{T-1}R_T.$ If $a_t\le b_{t-1}$ for every $t$ , each middle term is $\le0$ and can be dropped; if also $b_{T-1}\ge0$ , the whole sum is at most $a_0R_0$ . Choosing step sizes or a potential function $\Phi_t=(\text{weight})\cdot R_t$ so that the coefficients line up is how analyses with time-varying step sizes are done.
"The largest is at least the average" (and the smallest is at most the average): if $a_1+\dots+a_k\ge s$ , some $a_i\ge s/k$ . It proves that a threshold cut is cheap (Chapter 4), that best responses are pure (Chapter 3), and almost every approximation guarantee (Chapter 9). Picture three friends splitting a $30 bill in any way they like: somebody pays at least $10.
"Multiplicative shrinking": if $a_t\le(1-\frac1k)a_{t-1}$ , then $a_t\le(1-\frac1k)^ta_0\le e^{-t/k}a_0$ , using $1-x\le e^{-x}$ (the tangent line of $e^{-x}$ at 0). The quantity falls below any target after about $k\ln(a_0/\text{target})$ steps. Used for greedy vertex cover (unit 9.4).

I understand this unit

Unit 1.1 · Linear programs: models and forms

What is a linear program?

Sources: L9 §3; Lec_9_SecB p.1 (board notes)

A linear program (LP) has real-valued variables, a linear objective, and linear constraints that are equalities or non-strict inequalities. The course writes every LP in one standard shape.

Canonical maximization form (the course convention)

\begin{aligned} \text{maximize}\quad & c\T x \\ \text{subject to}\quad & Ax \le b \\ & x \ge 0 \end{aligned} \qquad A\in\R^{m\times n},\ b\in\R^m,\ c\in\R^n.

In wordsPick $n$ nonnegative numbers $x_1,\dots,x_n$ that make a linear score $\sum_i c_ix_i$ as large as possible, while $m$ linear "budget" rows $\sum_i A_{ji}x_i\le b_j$ all hold.

Symbol by symbol

$x\in\R^n$	the decision variables: what you choose (an $n\times1$ column)
$c\in\R^n$	objective coefficients: score per unit of each variable ( $n\times1$ )
$c\T x=\sum_i c_ix_i$	the objective, the number you maximize
$A\in\R^{m\times n}$	constraint matrix: one row per constraint, one column per variable
$b\in\R^m$	right-hand sides: the limits ( $m\times1$ )
$Ax\le b$	$m$ inequalities $\sum_{i=1}^n A_{ji}x_i\le b_j$ , one for each $j=1,\dots,m$
$x\ge0$	$n$ sign constraints $x_i\ge0$

When you use itEvery LP you meet can be converted to this form (unit 1.5). The dual, complementary slackness, and the strong-duality proof are all stated for it.

Dimension check: an

m\times n

matrix times an

n\times1

vector gives an

m\times1

vector, the same shape as

b

.

The vocabulary, side by side

Word	Meaning	What it proves (max problem)
Feasible point $x$	satisfies all constraints	$\opt\ge c\T x$ (a lower bound)
Optimal point $x^*$	feasible and best	$\opt=c\T x^*$
$\opt$	a number, the best objective value
Certificate $y$ (Chapter 3)	constraint weights	$\opt\le b\T y$ (an upper bound)

Why bother? What LPs give you

Modeling. Real variables and linear constraints express resource allocation, flows and many graph problems.
Algorithms. Rational LPs can be solved in polynomial time (in the bit length of the input). In this course the solver is a black box (unit 2.6).
Certificates. A feasible solution plus a matching dual solution proves optimality without rerunning anything (Chapter 3).
Geometry. At an optimum, tight constraints block every improving direction (Chapter 5).
Rounding. A fractional LP optimum can guide the search for an integral solution. Max-flow/min-cut is an exact example (Chapter 4), and approximation algorithms (Chapter 9) build on this.

I understand this unit

Unit 1.2 · Linear programs: models and forms

How to turn a problem into an LP

Sources: L9 §3–4; added modeling checklist

Decide what each variable means before writing any equation. An equation is only correct if it represents the decisions you intend.

Define the decisions and their units. For example " $x_i$ = liters of smoothie $i$ " or " $f_e$ = flow on edge $e$ ". State whether each variable is $\ge0$ , $\le0$ or free. LP variables are real numbers.
Write the goal as a linear score. If one unit of choice $i$ contributes $c_i$ , the total is $\sum_i c_ix_i$ . Use max for revenue or throughput and min for cost or error.
Write one linear constraint per rule. Usage ≤ supply. Demand served ≥ requirement. Inflow = outflow. Include every bound and sign. Check that units match on both sides.
Check both directions. (a) Every valid real-world plan gives a feasible vector. (b) Every feasible vector describes a valid plan. Failing (a) cuts off good solutions; failing (b) lets the LP "cheat".

What is, and is not, an LP

Expression	Plain LP?	Why
$3x_1-2x_2+7$ as objective	Yes	Affine. The constant 7 shifts every value equally and does not change the optimizer.
$3u-2v\ge 7$	Yes	Linear. Multiply by −1 to get the ≤ form.
$x_1x_2\le1$	No	Product of two variables (nonlinear).
objective $x_1^2+x_2^2$	No	Quadratic. It is a convex optimization problem (Chapter 6), but not an LP.
$x_i\in\{0,1\}$ or $x_i\in\Z$	No	Discrete. This makes an integer program, which is NP-hard in general. Chapter 9 drops the integrality, solves the LP, and rounds.
$x<2$ (strict)	Not allowed	"max $x$ s.t. $x<2$ " has supremum 2 but no maximizing point.
$\|x_1\|\le 3$	Yes, after rewriting	Same as $x_1\le3$ and $-x_1\le3$ .
$\max(x_1,x_2)\le 3$	Yes, after rewriting	Same as $x_1\le3$ and $x_2\le3$ .
$\min(x_1,x_2)\le 3$	No	" $x_1\le3$ or $x_2\le3$ " describes a non-convex region (an L-shape).

I understand this unit

Unit 1.3 · Linear programs: models and forms

Worked model: the smoothie LP

Sources: L9 §3.1, §8; Lec_9_SecB p.2 (A written on board)

This example runs through Chapters 1–3, so it is worth knowing well.

Inventory: 3 oranges, 10 bananas, 6 strawberries. You may make fractional liters.

Smoothie	Oranges	Bananas	Strawberries	Revenue / liter
1	1	2	0	$5
2	0	1	2	$4
3	1	1	1	$6

Let $x_i$ = liters of smoothie $i$ . Each ingredient gives a constraint (a row) and each smoothie gives a variable (a column):

The smoothie LP

\begin{aligned} \max\quad & 5x_1+4x_2+6x_3 \\ \text{s.t.}\quad & x_1+x_3\le 3 &&\text{(oranges)}\\ & 2x_1+x_2+x_3\le 10 &&\text{(bananas)}\\ & 2x_2+x_3\le 6 &&\text{(strawberries)}\\ & x_1,x_2,x_3\ge0. \end{aligned}

In wordsRevenue is $5, $4, $6 per liter. Each row adds up how much of one fruit the whole plan uses and caps it at the stock.

Symbol by symbol

Row "oranges"	smoothie 1 uses 1, smoothie 2 uses 0, smoothie 3 uses 1
Row "bananas"	$2x_1+1x_2+1x_3$ bananas used, at most 10 available
Row "strawberries"	$0x_1+2x_2+1x_3$ used, at most 6

Matrix form

A=\begin{pmatrix}1&0&1\\2&1&1\\0&2&1\end{pmatrix},\qquad b=\begin{pmatrix}3\\10\\6\end{pmatrix},\qquad c=\begin{pmatrix}5\\4\\6\end{pmatrix}.

In wordsRows of $A$ are fruits (orange, banana, strawberry). Columns are smoothies 1, 2, 3. $m=n=3$ .

When you use itThe L9 exercise "write $A,b,c$ " (the instructor wrote this $A$ on the board).

Checking a candidate: $x=(3,3,0)$

Fruit	Usage at $x=(3,3,0)$	Stock	Status
Oranges	$3+0=3$	3	tight (all used)
Bananas	$2\cdot3+3+0=9$	10	slack 1
Strawberries	$2\cdot3+0=6$	6	tight

All variables are ≥ 0, so $x$ is feasible. Its revenue is $5\cdot3+4\cdot3+6\cdot0=27$ . This proves $\opt\ge27$ . It does not yet prove optimality. The matching upper bound is in unit 3.1.

L9 exercise: what changes if smoothies can only be sold in whole-liter batches?

Show answer

Add

x_i\in\Z

(integers). The model becomes an integer program, not an LP. Integer programs are NP-hard in general. Here the LP optimum

(3,3,0)

happens to be integral, so it is also the integer optimum. That is luck, not a rule: an LP with integer data can have only fractional optima (try

\max x_1

s.t.

2x_1\le1

).

Is

x=(1,4,1)

feasible? What about

(0,2,2)

?

Show answer

(1,4,1)

: strawberries

2\cdot4+1=9>6

, so infeasible.

(0,2,2)

: oranges

0+2=2\le3

, bananas

0+2+2=4\le10

, strawberries

4+2=6\le6

. Feasible, with revenue

8+12=20\le27

.

I understand this unit

Unit 1.4 · Linear programs: models and forms

Maximum flow is an LP

Sources: L9 §4.1

Max flow (L8) is our first graph problem written as an LP. Give each directed edge $e$ a real variable $f_e$ , the amount of flow on it.

Edge-flow LP

\begin{aligned} \max\quad & \sum_{(s,v)\in E} f_{sv}\;-\;\sum_{(v,s)\in E} f_{vs} \\ \text{s.t.}\quad & \sum_{(u,v)\in E} f_{uv} \;=\; \sum_{(v,w)\in E} f_{vw} \qquad \forall v\notin\{s,t\} \\ & 0\le f_e\le c_e \qquad \forall e\in E. \end{aligned}

In wordsMaximize the net flow leaving the source. At every vertex other than $s$ and $t$ , what flows in must flow out. Every edge carries between 0 and its capacity.

Symbol by symbol

$E$ , $V$	directed edges and vertices of the network
$f_{uv}$	flow on edge $u\to v$ (a variable)
$c_e$	capacity of edge $e$ (given data, ≥ 0)
$\sum_{(u,v)\in E} f_{uv}$	inflow into $v$ : sum over all edges ending at $v$
$\sum_{(v,w)\in E} f_{vw}$	outflow from $v$ : sum over all edges starting at $v$

Why it is trueEach constraint is linear in the $f$ 's, so this is an LP. The objective uses net outflow because flow that leaves $s$ and later returns to it should not count as throughput.

When you use itSize: $|E|$ variables and $O(|E|+|V|)$ constraints, i.e. polynomial. Compare the path LP in Chapter 4, which can have exponentially many variables.

The running network for Chapters 1 and 4. A label "2 / 3" means flow 2 on an edge of capacity 3. This flow has value 4, so max flow ≥ 4.

I understand this unit

Unit 1.5 · Linear programs: models and forms

Converting any LP to canonical form

Sources: L9 §4.2; Lec11_SecB p.1 (x = max(0,x) − max(0,−x))

Every linear program can be rewritten as $\max c\T x,\ Ax\le b,\ x\ge0$ without changing what it represents.

Feature	Conversion	Why it is equivalent
$\min\ c\T x$	$\max\ (-c)\T x$ , then negate the value	The smallest $c\T x$ is where $-c\T x$ is largest.
$a\T x\ge d$	$-a\T x\le -d$	Multiplying by −1 flips an inequality.
$a\T x=d$	$a\T x\le d$ and $-a\T x\le -d$	Both together force equality.
Free variable $z$	$z=z^+-z^-$ with $z^+,z^-\ge0$	Every real number is a difference of two nonnegative numbers.
Variable $z\le0$	$z=-z'$ with $z'\ge0$	Flip its sign.
$a\T x\le d$ → equality	$a\T x+s=d,\ s\ge0$	The slack variable $s=d-a\T x$ is the unused amount.

Splitting a free variable

z \;=\; z^+ - z^-,\qquad z^+=\max(0,z)\ge0,\qquad z^-=\max(0,-z)\ge0.

In wordsKeep the positive part and the negative part of $z$ as two separate nonnegative numbers.

Symbol by symbol

$z^+$	positive part: $z$ if $z>0$ , else 0
$z^-$	negative part: $-z$ if $z<0$ , else 0

Why it is trueIf $z\ge0$ : $z^+-z^-=z-0$ . If $z<0$ : $z^+-z^-=0-(-z)=z$ . (The instructor wrote this formula on the L11 board.)

When you use itWhenever a variable is "unrestricted" or "free" and you need canonical form, e.g. to take a dual.

Worked exercise (L9): $\min(2u-v)$ s.t. $u-v=3,\ u\ge0,\ v$ free

Free variable: $v=v^+-v^-$ with $v^+,v^-\ge0$ . All variables $u,v^+,v^-$ are now nonnegative.
Min → max: $\max\ -2u+v^+-v^-$ .
Equality → two inequalities: $u-v^++v^-\le3$ and $-u+v^+-v^-\le-3$ .

\max\ -2u+v^+-v^- \quad\text{s.t.}\quad \begin{pmatrix}1&-1&1\\-1&1&-1\end{pmatrix}\begin{pmatrix}u\\v^+\\v^-\end{pmatrix}\le\begin{pmatrix}3\\-3\end{pmatrix},\quad u,v^+,v^-\ge0.

Solve by elimination: $u-v=3$ gives $v=u-3$ , so $2u-v=u+3$ . This is smallest when $u$ is smallest, i.e. $u=0$ . So $v=-3$ and the minimum is $3$ . The transformed maximum is $-3$ , attained for example at $u=0,v^+=0,v^-=3$ .

Standard (equality) form with slack variables

Ax\le b,\ x\ge0 \quad\Longleftrightarrow\quad Ax+s=b,\ x\ge0,\ s\ge0

In wordsAdd one nonnegative slack per row to absorb the unused amount.

Symbol by symbol

$s=b-Ax$	slack vector: $s_j$ is how much of resource $j$ is left over
$s_j=0$	row $j$ is tight (fully used)

When you use itSlacks reappear in complementary slackness: $y_js_j=0$ (unit 3.6).

I understand this unit

Unit 1.6 · Linear programs: models and forms

Modeling tricks: absolute values, max/min objectives, and reductions

Sources: L9 §4.2 (forms); standard LP modeling techniques

Many problems that do not look linear (absolute values, a maximum of several expressions) become LPs with one extra trick: introduce a new variable for the awkward quantity and bound it with linear inequalities.

Trick 1: minimizing an absolute value

Epigraph variable for |e|

\min\ |e(x)| \qquad\leadsto\qquad \min\ t\quad\text{s.t.}\quad t\ge e(x),\quad t\ge -e(x).

In wordsReplace $|e|$ by a new variable $t$ that must sit above both $e$ and $-e$ . Minimizing pushes $t$ down until it equals the larger of the two, which is $|e|$ .

Symbol by symbol

$e(x)$	any affine expression in the variables, e.g. $3x_1-x_2+2$
$t$	new free variable; the two constraints force $t\ge\|e(x)\|$

Why it is trueFeasible $t$ are exactly the numbers $\ge\max\{e,-e\}=|e|$ . At an optimum $t$ is as small as possible, so $t=|e(x)|$ . This is the same as minimizing over the epigraph of $|\cdot|$ (unit 6.2).

When you use itFor a sum $\sum_i|e_i(x)|$ , use one variable $t_i$ per term: $\min\sum_it_i$ , $t_i\ge\pm e_i(x)$ . The number of new variables and constraints is linear in the number of terms, so the LP stays polynomial size.

Worked example

Example: the point closest in total distance

Choose a location $x\in\R$ on a road to minimize the total distance to houses at 1, 4 and 6: $\min|x-1|+|x-4|+|x-6|$ .

\min\ t_1+t_2+t_3\quad\text{s.t.}\quad t_1\ge x-1,\ t_1\ge 1-x,\quad t_2\ge x-4,\ t_2\ge4-x,\quad t_3\ge x-6,\ t_3\ge6-x,\quad x\ \text{free}.

The optimum is the median $x=4$ with value $3+0+2=5$ . Why: moving right from 4 increases the distances to 1 and 4 and decreases only the distance to 6; moving left increases the distances to 4 and 6 and decreases only the distance to 1. Either way two distances grow and one shrinks at the same rate, so the total gets worse: 4 (the median) is best.

Trick 2: minimizing a maximum

One variable for the worst case

\min_x\ \max_{i}\ e_i(x)\qquad\leadsto\qquad \min\ t\quad\text{s.t.}\quad t\ge e_i(x)\ \ \forall i.

In wordsA single variable $t$ must be above every expression. Minimizing $t$ makes it equal the largest one.

Symbol by symbol

$t$	free variable representing the worst (largest) value
$\max_i\|e_i(x)\|$	combine both tricks: $t\ge e_i(x)$ and $t\ge-e_i(x)$ for every $i$

When you use itMinimax ("make the worst case as good as possible") objectives: worst-case error, makespan, bottleneck capacity.

Mirror image: maximizing a minimum

\max_x\ \min_j\ e_j(x)\qquad\leadsto\qquad\max\ v\quad\text{s.t.}\quad v\le e_j(x)\ \ \forall j.

In wordsA variable $v$ that is below every expression, pushed up as far as possible, equals the smallest expression.

When you use itGuaranteed-payoff problems, such as choosing a strategy in a game (unit 3.8).

Reductions: "this LP form can express that one"

A statement like "if we can solve every LP of form 1 in polynomial time, we can solve every LP of form 2" is a reduction. A correct reduction argument has three parts:

Transform an instance of form 2 into an instance of form 1, using only polynomially many new variables and constraints (and numbers of polynomial bit length).
Map solutions both ways. Every feasible solution of the new LP gives a feasible solution of the old one with the same objective value, and vice versa. Then the optimal values agree, and infeasible/unbounded is preserved.
Recover an optimal solution of the original from one of the transformed LP in polynomial time.

The building blocks are the conversions of unit 1.5: split free variables, add slack variables to turn $\le$ into $=$ , write $=$ as two $\le$ , negate to flip $\ge$ or min.

Worked example

Worked reduction: canonical form → equality form

Claim: an algorithm for LPs of the form $\max c\T x$ s.t. $Ax=b,\ x\ge0$ can solve canonical LPs $\max c\T x$ s.t. $Ax\le b,\ x\ge0$ .

Transform: add a slack vector $s\in\R^m$ : $\max c\T x+0\T s$ s.t. $[A\ \ I]\binom{x}{s}=b$ , $x,s\ge0$ . That is $m$ new variables, polynomial size.

Map solutions: if $x$ is feasible for the original, $(x,\,b-Ax)$ is feasible for the new LP (slack ≥ 0) with the same value. If $(x,s)$ is feasible for the new LP, then $Ax=b-s\le b$ , so $x$ is feasible for the original, same value.

Recover: drop $s$ . ∎ (With free variables you would also split them, because the target form insists on $x\ge0$ .)

I understand this unit

Unit 2.1 · The geometry of an LP

Convex sets: every segment stays inside

Sources: L9 §5; Lec_9_SecB p.3 (board pictures)

"Convex" is the property that makes LPs, and later convex optimization, tractable. It says you can blend any two feasible choices and the blend is still feasible.

Definition: convex set

P\subseteq\R^n \text{ is convex} \iff \forall\,x,y\in P,\ \forall\,\lambda\in[0,1]:\quad \lambda x+(1-\lambda)y\in P.

In wordsPick any two points of the set. The whole straight segment between them must also lie in the set.

Symbol by symbol

$\lambda x+(1-\lambda)y$	a blend (convex combination): $\lambda$ parts of $x$ and $1-\lambda$ parts of $y$
$\lambda=1$	gives $x$ ; $\lambda=0$ gives $y$ ; $\lambda=\tfrac12$ gives the midpoint
$\lambda\in[0,1]$	as $\lambda$ sweeps from 0 to 1 the blend traces the whole segment from $y$ to $x$

Why it is trueIt is a definition, so nothing to prove. To show a set is not convex, one pair of points and one $\lambda$ whose blend falls outside is enough.

When you use itLP regions (below), domains of convex functions, the separation theorem, and the local ⇒ global proof.

One pair of points whose segment leaves the set is enough to show a set is not convex.

The one-line proof

A\big(\lambda x+(1-\lambda)y\big) \;=\; \lambda Ax+(1-\lambda)Ay \;\le\; \lambda b+(1-\lambda)b \;=\; b.

In wordsApplying the constraints to a blend gives the same blend of the two constraint values, and both of those are within the limit.

Symbol by symbol

first $=$	matrix multiplication is linear (distributes over sums and scalars)
$\le$	uses $Ax\le b$ , $Ay\le b$ , and that the weights $\lambda$ and $1-\lambda$ are both $\ge0$ , so multiplying keeps the direction of $\le$
last $=$	$\lambda+(1-\lambda)=1$

Why it is trueNonnegativity also survives: each coordinate of the blend is a nonnegative weighting of nonnegative numbers. Equalities survive by the same calculation with $=$ in place of $\le$ .

Operations on convex sets

Operation	Convex?	Reason
intersection $K\cap L$ (even of infinitely many sets)	always	a segment between two points of $K\cap L$ lies in $K$ (convex) and in $L$ (convex), hence in both
union $K\cup L$	not in general	a segment may start in $K$ , end in $L$ , and cross a gap in between
image or preimage under an affine map $x\mapsto Mx+v$	always	affine maps send segments to segments
halfspace $\{a\T x\le d\}$ , hyperplane, ball, box, simplex	always	check the definition directly (for a ball: triangle inequality)
sublevel set $\{x: f(x)\le c\}$ of a convex function	always	$f(\lambda x+(1-\lambda)y)\le\lambda f(x)+(1-\lambda)f(y)\le c$

I understand this unit

Unit 2.2 · The geometry of an LP

Solving a 2-D LP by sliding the objective line

Sources: L9 §5.1; Lec_9_SecB p.4

The running 2-D example:

\max\ 2x_1+3x_2 \quad\text{s.t.}\quad x_1+x_2\le5,\quad x_1\ge1,\quad x_2\ge0.

The feasible region is the triangle with corners $(1,0)$ , $(5,0)$ , $(1,4)$ .

Level lines of the objective

\{x:\ c\T x = q\} \;=\; \{x:\ 2x_1+3x_2=q\}

In wordsEvery point on this line has the same score $q$ . Changing $q$ slides the line parallel to itself. Increasing $q$ moves it in the direction of $c=(2,3)$ .

Symbol by symbol

$q$	the objective value (a number you choose); one line per value
$c=(2,3)$	the normal to the line (perpendicular to it), pointing toward larger $q$ . It is not the slope.

Why it is trueMoving from a point $x$ by a step $h$ changes the objective by $c\T h$ . Steps along the line have $c\T h=0$ , so they are perpendicular to $c$ . A step $h=t\,c$ with $t>0$ changes it by $t\norm{c}^2>0$ , so moving along $c$ increases the score fastest.

When you use itGraphical LP solving: slide the line in direction $c$ until it is about to lose contact with $P$ . The last contact point(s) are optimal.

Vertex	$2x_1+3x_2$	Tight constraints (pin it down)
$(1,0)$	2	$x_1=1$ , $x_2=0$
$(5,0)$	10	$x_1+x_2=5$ , $x_2=0$
$(1,4)$	14	$x_1=1$ , $x_1+x_2=5$

The unique optimum is $(1,4)$ with value 14.

Non-unique optima

With objective $x_1+x_2$ , every point of the edge from $(1,4)$ to $(5,0)$ has value 5, so the whole edge is optimal. The level line is parallel to that edge. The instructor's board note: "Obs: Opt soln need not be unique", with a second example $\max x_1$ s.t. $x_1\le2,\ x_2\le1,\ x\ge0$ , where every point $(2,x_2)$ with $0\le x_2\le1$ is optimal.

I understand this unit

Unit 2.3 · The geometry of an LP

The three possible outcomes of an LP

Sources: L9 §6

Before looking for an optimal point, ask two questions. Is there any feasible point? Is the objective bounded in the direction you optimize?

Outcome	Meaning	Example
Infeasible	No vector satisfies all constraints ( $P=\varnothing$ ).	$x\ge2,\ x\le1$
Unbounded (objective)	Feasible points with arbitrarily large objective exist.	$\max x$ s.t. $x\ge0$
Finite optimum	The best value is finite, and an LP then attains it.	$\max -x$ s.t. $x\ge0$ : $x^*=0$

I understand this unit

Unit 2.4 · The geometry of an LP

Tight constraints and vertices

Sources: L9 §6

Tight (active) constraint

a\T x\le d \ \text{ is tight at } x \iff a\T x = d.

In wordsA constraint is tight when the point sits exactly on its boundary wall. "Tight", "active" and "binding" mean the same thing. The opposite is "slack" or "inactive" ( $a\T x<d$ ).

Symbol by symbol

$a$	the normal vector of the constraint, pointing out of the feasible side (the direction in which $a\T x$ grows)
$d-a\T x$	the slack: zero when tight

Why n independent tight constraints pin down a point

\begin{cases} a_1\T x=d_1\\ \ \vdots\\ a_n\T x=d_n\end{cases}\quad\text{with } a_1,\dots,a_n \text{ independent} \;\Longrightarrow\; Bx=d \text{ has exactly one solution.}

In wordsEach tight equation is a wall through the point. In $\R^n$ , $n$ walls facing genuinely different directions cross at exactly one point. Fewer walls, or dependent walls, cross in a line or a plane.

Symbol by symbol

$B$	the $n\times n$ matrix whose rows are $a_1\T,\dots,a_n\T$
independent rows	$B$ is invertible ( $\det B\ne0$ ), so $x=B^{-1}d$ is unique

When you use itPolynomial bit size (unit 2.6), the box-constraint exercise, and identifying vertices in exam questions.

Smoothie example: which three constraints pin $(3,3,0)$ ?

Tight at $(3,3,0)$ : oranges $x_1+x_3=3$ , strawberries $2x_2+x_3=6$ , and $x_3=0$ (that is, $-x_3\le0$ is tight). Normals $(1,0,1)$ , $(0,2,1)$ , $(0,0,-1)$ are independent: the determinant of the matrix with these rows is $1\cdot(2\cdot(-1)-1\cdot0)-0+1\cdot0=-2\ne0$ . Their only common solution is $(3,3,0)$ , so it is a vertex. Bananas are slack ( $9<10$ ).

I understand this unit

Unit 2.5 · The geometry of an LP

Some optimal solution is at a vertex

Sources: L9 §6

So why not just check every corner?

A vertex is chosen by picking $n$ of the $m+n$ constraints to be tight, so there can be up to $\binom{m+n}{n}$ vertices. That is exponential. A cube in $\R^n$ ( $0\le x_i\le1$ ) already has $2^n$ corners. Even choosing among just 40 constraints gives $2^{40}\approx10^{12}$ subsets, so guessing "which constraints are tight" by brute force is hopeless. Checking every corner is correct but does not scale: real LP algorithms (simplex, ellipsoid, interior point) avoid enumeration.

I understand this unit

Unit 2.6 · The geometry of an LP

Polynomial-time solvability and short exact answers

Sources: L9 §7

The ellipsoid method and interior-point methods are the algorithms behind this theorem. The course uses LP solving as a tool and does not develop them.

Why the answer can be written with polynomially many bits

Pick a vertex optimum and $n$ independent tight constraints. They form a nonsingular square system $Bx=d$ , so $x=B^{-1}d$ . Cramer's rule gives each coordinate:

Cramer's rule

x_i \;=\; \frac{\det(B_i)}{\det(B)},\qquad B_i = B \text{ with column } i \text{ replaced by } d.

In wordsEach coordinate of a vertex is a ratio of two determinants of matrices built from the input numbers.

Symbol by symbol

$\det(B)\neq0$	because the $n$ tight rows are independent
$\det$ of an integer matrix	a sum of $n!$ signed products of $n$ entries

Why it is trueClear denominators so all entries are integers of absolute value at most $2^L$ . Then each product is at most $2^{nL}$ and a sum of $n!\le n^n$ of them is at most $2^{nL+n\log n}$ . That is $O(nL+n\log n)$ bits, polynomial in the input size.

When you use itIt shows an exact optimum is short. It does not tell you which constraints to make tight, so it is not an algorithm.

Exercise (L9): few fractional coordinates

Claim. An LP in $n$ variables with box constraints $0\le x_i\le1$ and only $k$ other linear inequalities: every vertex has at most $k$ coordinates strictly between 0 and 1.

I understand this unit

Unit 3.1 · LP duality

A certificate: an upper bound that meets your solution

Sources: L9 §8; L10 §1; Lec10_SecB p.1 (board)

You found $x=(3,3,0)$ with revenue 27. How can you prove nobody can do better without trying every plan? Combine the constraints into one inequality that bounds the objective from above.

Take 5 × the orange row plus 2 × the strawberry row:

The smoothie certificate

5(x_1+x_3)+2(2x_2+x_3)\;\le\;5\cdot3+2\cdot6 \;=\;27

In wordsWeighted sums of valid "≤" inequalities with nonnegative weights are still valid.

Symbol by symbol

$5$	weight (multiplier) on the orange constraint $x_1+x_3\le3$
$0$	weight on bananas (not used)
$2$	weight on the strawberry constraint $2x_2+x_3\le6$

Why it is trueMultiplying $x_1+x_3\le3$ by $5\ge0$ keeps the direction, and so does multiplying by 2. Adding two valid ≤ inequalities gives a valid ≤.

Expand the left side: $5x_1+4x_2+7x_3$ . Compare it to the objective coefficient by coefficient:

\underbrace{5x_1+4x_2+6x_3}_{\text{objective}} \;\le\; 5x_1+4x_2+7x_3 \;\le\; 27 \quad\text{for every feasible }x.

In wordsThe combined left side beats the objective on every coefficient (5 ≥ 5, 4 ≥ 4, 7 ≥ 6). Since all $x_i\ge0$ , it is at least the objective. So no feasible plan earns more than 27.

Why it is trueFirst $\le$ : $6x_3\le7x_3$ because $x_3\ge0$ ("6 ≤ 7, and $x_3$ is nonnegative"). Second $\le$ : the weighted sum above. Equivalently, add one copy of $-x_3\le0$ to make the left side exactly the objective.

When you use it27 (feasible) ≤ OPT ≤ 27 (certificate), so $\opt=27$ and $(3,3,0)$ is optimal.

When a lower bound and an upper bound meet, both are optimal (L9/L10 figure).

Mirror image: certificates for a minimization LP

For $\min c\T x$ s.t. $Ax\ge b,\ x\ge0$ , a feasible point gives an upper bound on $\opt$ , and the certificate must give a lower bound. Same idea, all directions flipped:

Lower bound from ≥ constraints

y\ge0,\quad A\T y\le c\quad\Longrightarrow\quad c\T x\;\ge\;(A\T y)\T x\;=\;y\T Ax\;\ge\;y\T b\qquad\text{for every feasible }x.

In wordsTake a nonnegative combination of the ≥ rows. If every combined coefficient is at most the cost coefficient, the combination is below the objective, so its right side $b\T y$ is a lower bound on every feasible cost.

Symbol by symbol

$y\ge0$	multiplying a ≥ row by a nonnegative number keeps ≥
$A\T y\le c$	the combination never "overcharges" any variable; with $x\ge0$ this gives $c\T x\ge(A\T y)\T x$
$b\T y$	the lower bound; the best one is $\max b\T y$ , the dual of a min problem

I understand this unit

Unit 3.2 · LP duality

Deriving the dual: optimize over upper bounds

Sources: L10 §2; Lec10_SecB p.2 (lemma on board)

Generalize the smoothie argument to any canonical LP $(P)\ \max c\T x$ s.t. $Ax\le b,\ x\ge0$ . Put a weight $y_j$ on row $j$ and add up.

Step 1: weighted sum of the rows

\sum_{j=1}^{m} y_j\Big(\sum_{i=1}^{n}A_{ji}x_i\Big) \;\le\; \sum_{j=1}^{m} y_j b_j \qquad\text{(valid if every } y_j\ge0)

In wordsMultiply constraint $j$ by $y_j$ and add all $m$ of them.

Symbol by symbol

$y_j$	the multiplier (weight, "price") on constraint $j$
$\sum_i A_{ji}x_i$	left side of row $j$
$\sum_j y_jb_j=b\T y$	the resulting upper bound

Why it is trueEach row satisfies $(Ax)_j\le b_j$ . Multiplying by $y_j\ge0$ keeps $\le$ , and sums of ≤'s are ≤.

Step 2: regroup by variable

\sum_{j}y_j\sum_i A_{ji}x_i \;=\; \sum_{i=1}^{n}\Big(\underbrace{\sum_{j=1}^{m}A_{ji}y_j}_{(A\T y)_i}\Big)x_i

In wordsSwap the order of summation. The coefficient that multiplies $x_i$ is the column- $i$ sum $(A\T y)_i$ . This is where the transpose comes from.

Why it is trueA finite double sum can be added in any order.

Step 3: dominate the objective (the weak-duality chain)

c\T x \;\le\; (A\T y)\T x \;=\; y\T Ax \;\le\; y\T b \qquad\text{if } A\T y\ge c,\ y\ge0,\ x\ge0,\ Ax\le b.

In wordsIf every combined coefficient is at least the objective coefficient, the combination is an upper bound on the objective for every feasible $x$ .

Symbol by symbol

1st $\le$	uses $x\ge0$ and $A\T y\ge c$ : $c_ix_i\le(A\T y)_ix_i$ term by term
$=$	transpose identity: $(A\T y)\T x=y\T Ax$
2nd $\le$	uses $y\ge0$ and $Ax\le b$

The primal–dual pair (canonical form)

(P)\ \ \max\ c\T x\ \ \text{s.t.}\ Ax\le b,\ x\ge0 \qquad\qquad (D)\ \ \min\ b\T y\ \ \text{s.t.}\ A\T y\ge c,\ y\ge0.

In wordsThe dual looks for the cheapest valid set of multipliers, i.e. the tightest upper bound.

Symbol by symbol

$\min$	the smallest upper bound is the most informative one
$A\T y\ge c$	$n$ constraints, one per primal variable (domination)
$y\ge0$	$m$ variables, one per primal constraint (direction kept)

When you use itRemember the duality "dictionary" below. It makes writing duals mechanical.

Primal (max)	Dual (min)
$n$ variables $x_i$	$n$ constraints $(A\T y)_i\ge c_i$
$m$ constraints $(Ax)_j\le b_j$	$m$ variables $y_j\ge0$
objective coefficients $c$	right-hand sides $c$
right-hand sides $b$	objective coefficients $b$
matrix $A$ ( $m\times n$ )	matrix $A\T$ ( $n\times m$ )

I understand this unit

Unit 3.3 · LP duality

Weak duality, the smoothie dual, and prices

Sources: L10 §3 (marked "Optional")

Weak duality

c\T x\;\le\;b\T y\qquad\text{for every primal-feasible } x \text{ and dual-feasible } y.

In wordsAny feasible primal value is at most any feasible dual value. Max-side values never pass min-side values.

Why it is trueIt is the chain from the previous unit. (The proof was marked Optional in class. The one-line chain is all you need.)

When you use it(1) Any dual-feasible $y$ gives an upper bound on $\opt$ . (2) If $c\T x=b\T y$ for a feasible pair, both are optimal. You do not need strong duality for that conclusion.

Why matching values prove optimality

c\T x\;\le\;\opt_P\;\le\;\opt_D\;\le\;b\T y.

In wordsThe primal optimum lies between your feasible value and the dual optimum, which lies below your dual value. If the two ends are equal, everything in between is squeezed to the same number.

The smoothie dual, explicitly

Dual of the smoothie LP

\begin{aligned}\min\quad & 3y_O+10y_B+6y_S\\ \text{s.t.}\quad & y_O+2y_B\ge5 &&\text{(smoothie 1)}\\ & y_B+2y_S\ge4 &&\text{(smoothie 2)}\\ & y_O+y_B+y_S\ge6 &&\text{(smoothie 3)}\\ & y_O,y_B,y_S\ge0.\end{aligned}

In wordsChoose a price per fruit so that the fruit in every smoothie is worth at least what that smoothie sells for, and make the total inventory value as small as possible.

Symbol by symbol

$y_O,y_B,y_S$	prices of an orange, a banana, a strawberry
$3y_O+10y_B+6y_S$	value of the whole inventory at those prices
row "smoothie 1"	1 orange + 2 bananas must be worth ≥ $5

Check $y=(5,0,2)$ : $5+0=5\ge5$ , $0+4=4\ge4$ , $5+0+2=7\ge6$ . Feasible, with value $15+0+12=27$ . This matches the primal 27, so both are optimal.

Economic interpretation

Imagine a buyer offering to purchase your whole inventory at prices $y$ . Each dual constraint says that turning fruit into smoothie $i$ earns no more than selling that fruit directly. So no production plan earns more than the inventory's value $b\T y$ . The dual finds the lowest prices that still make this true.

At the optimum, one banana is left over and the banana price is 0. Smoothie 3's ingredients are worth $7>6$ and it is not produced. These observations become complementary slackness.

Exercise (L10): check that

(y_O,y_B,y_S)=(3,1,2)

is dual feasible. What bound does it give? Why is a feasible certificate not necessarily the best?

Show answer

3+2=5\ge5

,

1+4=5\ge4

,

3+1+2=6\ge6

: feasible. Bound

9+10+12=31

, so

\opt\le31

. It is valid but loose (31 > 27). The dual minimizes over all valid certificates, and

(5,0,2)

is better. Together with

x=(3,3,0)

the pair

(x,y)

only proves

x

is within

31-27=4

of optimal.

I understand this unit

Unit 3.4 · LP duality

Strong duality and what can go wrong

Sources: L10 §4; Lec10_SecB pp.2,4

Primal (max) values approach from below and dual (min) values from above. Weak duality: they never cross. Strong duality: their optima meet.

Result	Statement	What it lets you conclude
Weak duality	$c\T x\le b\T y$ for every feasible pair.	Any dual point is an upper bound. A matching pair is optimal.
Strong duality	Finite optimum ⇒ both optima exist and are equal.	An exact certificate always exists. You can always prove optimality this way.

Infeasible is not the same as unbounded

Primal	Dual can be…	Reason
finite optimum	finite optimum, same value	strong duality
unbounded (above)	infeasible	a feasible $y$ would give a finite upper bound $b\T y$
infeasible	unbounded (below) or infeasible	both are possible (see example)

Symmetrically, if the dual is unbounded below then the primal is infeasible. The possible status pairs are:

Primal \ Dual	finite optimum	unbounded	infeasible
finite optimum	possible (equal values)	impossible	impossible
unbounded	impossible	impossible	possible
infeasible	impossible	possible	possible

I understand this unit

Unit 3.5 · LP duality

★ Exam skill: writing the dual of ANY LP

Sources: L10 §4.1 rulebook (flagged in class as an exam question)

The rulebook for a maximization primal

Primal (max) feature	Dual (min) feature	Why
constraint $a_j\T x\le b_j$	$y_j\ge0$	a nonnegative multiple of a ≤ stays ≤
constraint $a_j\T x\ge b_j$	$y_j\le0$	a nonpositive multiple turns ≥ into ≤
constraint $a_j\T x=b_j$	$y_j$ free	an equality can be multiplied by any number
variable $x_i\ge0$	$(A\T y)_i\ge c_i$	$c_ix_i\le(A\T y)_ix_i$ when $x_i\ge0$
variable $x_i\le0$	$(A\T y)_i\le c_i$	for $x_i\le0$ the inequality flips
variable $x_i$ free	$(A\T y)_i=c_i$	must hold for both signs of $x_i$ , which forces equality

The dual objective is always $\min b\T y$ . The dual of the dual is the primal.

Intuitive approach

Why free ↔ equality: no arbitrage

Think of the dual constraint for

x_i

as comparing the value of product

i

's ingredients,

(A\T y)_i

, with its price

c_i

. If you can only make product

i

(

x_i\ge0

), the trader only needs

(A\T y)_i\ge c_i

: making it must not beat selling the ingredients. If you can also unmake it, i.e. run the recipe backwards (

x_i

free), then a price that is too high would let you profit in the other direction. The only safe price is an exact match,

(A\T y)_i=c_i

. The same logic, with constraints in place of products, explains "equality row ↔ free multiplier": an equality can be used in both directions, so its multiplier may have either sign.

Mnemonic: Sensible – Odd – Bizarre

Call a feature sensible if it is the "natural" one for that kind of problem, odd if it is an equality or free variable, and bizarre if it is the unnatural direction. Then sensible ↔ sensible, odd ↔ odd, bizarre ↔ bizarre.

	in a MAX problem	in a MIN problem
constraint, sensible	$\le$	$\ge$
constraint, odd	$=$	$=$
constraint, bizarre	$\ge$	$\le$
variable, sensible	$\ge0$	$\ge0$
variable, odd	free	free
variable, bizarre	$\le0$	$\le0$

Example: in a max primal, a ≥ constraint is bizarre, so its dual variable is bizarre for the min dual, i.e. $y_j\le0$ . A free primal variable is odd, so its dual constraint is odd: an equality. This works in both directions (min primal → max dual), so you never need a separate table for min problems.

The recipe

Name a dual variable per primal constraint ( $y_1,\dots,y_m$ ). Write its sign using the table (or S-O-B).
Dual objective: $\min\sum_j b_jy_j$ if the primal is max ( $\max\sum_jb_jy_j$ if the primal is min). Coefficients are the primal right-hand sides.
One dual constraint per primal variable $x_i$ : read down column $i$ of the primal: $\sum_jA_{ji}y_j\ \square\ c_i$ , where $\square$ is ≥, ≤ or = from the sign of $x_i$ .
Sanity checks: the counts ( $m$ dual variables, $n$ dual constraints), weak duality on a feasible pair if you have one, and "dual of dual = primal".

Worked example 1 (canonical): the smoothie LP

All three rows are ≤ (max), so $y\ge0$ . All variables are ≥ 0, so every dual constraint is ≥. Columns of $A$ : $(1,2,0)$ , $(0,1,2)$ , $(1,1,1)$ . The result is the dual in unit 3.3.

Worked example 2 (mixed): equality row and a free variable

\max\ 2u+v\quad\text{s.t.}\quad u+v\le4\ \ (\alpha),\qquad u-v=1\ \ (\beta),\qquad u\ge0,\ v\ \text{free}.

Row 1 is ≤ in a max problem: $\alpha\ge0$ . Row 2 is =: $\beta$ free.
Objective: $\min\ 4\alpha+\beta$ .
Column $u$ is $(1,1)$ and $u\ge0$ : $\alpha+\beta\ge2$ . Column $v$ is $(1,-1)$ and $v$ is free: $\alpha-\beta=1$ .

\min\ 4\alpha+\beta \quad\text{s.t.}\quad \alpha+\beta\ge2,\quad \alpha-\beta=1,\quad \alpha\ge0,\ \beta\ \text{free}.

Check with a matching pair: primal $u+v=4,\ u-v=1$ gives $u=2.5,\ v=1.5$ , value 6.5. Dual $\alpha-\beta=1,\ \alpha+\beta=2$ gives $\alpha=1.5,\ \beta=0.5$ , value $6+0.5=6.5$ . Both feasible with equal values, so both are optimal.

Worked example 3 (min primal)

\min\ 3x_1+2x_2\quad\text{s.t.}\quad x_1+x_2\ge4\ (y_1),\qquad x_1-x_2\le2\ (y_2),\qquad x_1\ge0,\ x_2\ \text{free}.

Min primal, so the dual is max $4y_1+2y_2$ .
Row 1 is ≥ in a min problem (sensible): $y_1\ge0$ . Row 2 is ≤ in a min problem (bizarre): $y_2\le0$ .
Column $x_1=(1,1)$ with $x_1\ge0$ (sensible). In a max dual the sensible constraint is ≤: $y_1+y_2\le3$ . Column $x_2=(1,-1)$ , free: $y_1-y_2=2$ .

\max\ 4y_1+2y_2\quad\text{s.t.}\quad y_1+y_2\le3,\quad y_1-y_2=2,\quad y_1\ge0,\ y_2\le0.

Solve both to check. Primal: $x_2\ge\max(4-x_1,\ x_1-2)$ and $x_2$ has positive cost, so take it as small as possible. For $x_1\le3$ the objective is $3x_1+2(4-x_1)=x_1+8$ , minimized at $x_1=0,\ x_2=4$ : value 8. Dual: $y_1=2+y_2$ , so the objective is $8+6y_2$ with $y_2\le0$ , maximized at $y_2=0,\ y_1=2$ . Check $y_1+y_2=2\le3$ . Value 8. They match.

Worked example 4 (everything at once)

\max\ x_1-2x_2+3x_3\ \ \text{s.t.}\ \ \begin{cases}x_1+x_2+x_3\le10 & (y_1)\\ 2x_1-x_3\ge2 & (y_2)\\ x_2+x_3=4 & (y_3)\end{cases}\quad x_1\ge0,\ x_2\le0,\ x_3\ \text{free}.

Signs: $y_1\ge0$ (≤, sensible), $y_2\le0$ (≥, bizarre), $y_3$ free (=). Columns: $x_1\to(1,2,0)$ , $x_2\to(1,0,1)$ , $x_3\to(1,-1,1)$ .

\min\ 10y_1+2y_2+4y_3\ \ \text{s.t.}\ \ \begin{cases}y_1+2y_2\ge1 & (x_1\ge0:\ \text{sensible})\\ y_1+y_3\le-2 & (x_2\le0:\ \text{bizarre})\\ y_1-y_2+y_3=3 & (x_3\ \text{free: odd})\end{cases}\quad y_1\ge0,\ y_2\le0,\ y_3\ \text{free}.

Worked example 5: dual of the dual is the primal

Write $(D)$ as a max problem: $\max(-b)\T y$ s.t. $(-A\T)y\le-c,\ y\ge0$ . This is canonical, with data $(-A\T,-c,-b)$ . Its dual is $\min(-c)\T x$ s.t. $(-A\T)\T x\ge-b,\ x\ge0$ , i.e. $\min -c\T x$ s.t. $-Ax\ge-b$ . That is $\max c\T x$ s.t. $Ax\le b,\ x\ge0$ : the primal again.

I understand this unit

Unit 3.6 · LP duality

Complementary slackness: where the duality gap lives

Sources: L10 §3 (economic interpretation); L11 §4.2

For a feasible pair, the duality gap $b\T y-c\T x$ is a sum of nonnegative "waste" terms. Zero gap means zero waste everywhere, and that gives easy equations to check or find optimal solutions.

Primal and dual slacks

s \;=\; b-Ax\;\ge0,\qquad r\;=\;A\T y-c\;\ge0.

Symbol by symbol

$s_j$	unused amount of resource $j$ (primal slack of row $j$ )
$r_i$	how much the priced cost of product $i$ exceeds its revenue (dual slack of column $i$ ): the "loss per unit" of making product $i$

The gap identity

b\T y-c\T x \;=\; y\T(b-Ax)\;+\;x\T(A\T y-c) \;=\; \sum_{j} y_j s_j \;+\; \sum_{i} x_i r_i.

In wordsEvery dollar of gap is either (a) unused inventory that has a positive price, or (b) production of something whose ingredients are worth more than it sells for.

Why it is trueExpand the right side: $y\T b-y\T Ax+x\T A\T y-x\T c$ . The middle two terms cancel because $x\T A\T y=y\T Ax$ . What remains is $b\T y-c\T x$ .

When you use itEach term is a product of two nonnegative numbers, so each is ≥ 0. The sum is zero exactly when every term is zero.

(⇐) The conditions make the gap zero, so weak duality gives optimality. (⇒) By strong duality optimal values are equal, so the gap is zero, so every term is zero.

If …	then …	meaning
$y_j>0$	primal row $j$ is tight	a resource with positive price is fully used
primal row $j$ is slack	$y_j=0$	leftover resources are worth nothing at the margin
$x_i>0$	dual row $i$ is tight	anything produced has priced cost exactly equal to revenue
dual row $i$ is slack	$x_i=0$	a product whose ingredients are worth more than it sells for is not made

Using slackness to find a solution

From $x$ to $y$ . Suppose $x=(3,3,0)$ is optimal. Bananas are slack, so $y_B=0$ . Since $x_1,x_2>0$ , dual rows 1 and 2 are tight: $y_O+2y_B=5$ and $y_B+2y_S=4$ . Hence $y=(5,0,2)$ . Check the remaining dual row: $5+0+2=7\ge6$ . ✓

From $y$ to $x$ . Start from $y=(5,0,2)$ . Dual row 3 is slack ( $7>6$ ), so $x_3=0$ . $y_O,y_S>0$ force the orange and strawberry rows to be tight: $x_1+x_3=3$ , $2x_2+x_3=6$ . Hence $x=(3,3,0)$ . Check bananas separately: $9\le10$ . ✓

Resource	slack $s_j$	price $y_j$	Smoothie	$r_i$	$x_i$
Oranges	0	5	1	5−5=0	3
Bananas	1	0	2	4−4=0	3
Strawberries	0	2	3	7−6=1	0

Tight does not mean positive: an example (L11 exercise)

$\max x_1$ s.t. $x_1\le1,\ x_2\le0,\ x\ge0$ . The unique optimum is $(1,0)$ , where the second row $x_2\le0$ is tight. The dual is $\min y_1+0\cdot y_2$ s.t. $y_1\ge1,\ y_2\ge0$ . The optimum $y=(1,0)$ puts multiplier 0 on that tight row. This does not contradict complementary slackness: $y_2\cdot\text{slack}_2=0\cdot0=0$ .

I understand this unit

Unit 3.7 · LP duality

Approximate certificates: a small gap bounds your error

Sources: L11 §5.2 exercise

Gap bounds the error

0\;\le\;\opt_P-c\T x\;\le\;b\T y-c\T x \;=:\;\delta

In wordsEven without knowing $\opt$ , a feasible $y$ tells you how far a feasible $x$ can be from optimal: at most the gap.

Symbol by symbol

$\delta$	the duality gap of the pair $(x,y)$ , always ≥ 0 for a feasible pair

Why it is trueLeft: $x$ is feasible, so $c\T x\le\opt_P$ . Right: weak duality gives $\opt_P\le b\T y$ . Subtract $c\T x$ everywhere.

When you use itL11 exercise: "Using only weak duality, show that a feasible pair with $b\T y-c\T x\le\eps$ certifies $\opt-c\T x\le\eps$ ." This is exactly the chain above. Note it is an additive guarantee, not a ratio.

I understand this unit

Unit 3.8 · LP duality

Application: zero-sum games and the minimax theorem

Sources: Standard application of LP duality

LP duality also explains two-player games. This unit gives the definitions and the tools. The proof that max-min equals min-max is a direct application of strong duality.

Expected payoff

p\T Aq=\sum_{i=1}^m\sum_{j=1}^n p_i\,A_{ij}\,q_j

In wordsAverage Alice's payoff over the random row (probabilities $p$ ) and the independent random column (probabilities $q$ ).

Symbol by symbol

$p_i$	probability Alice plays row $i$
$q_j$	probability Bob plays column $j$
$(p\T A)_j=\sum_ip_iA_{ij}$	Alice's expected payoff if Bob plays the pure column $j$
$(Aq)_i$	Alice's expected payoff from pure row $i$ against Bob's mix $q$

Guaranteed values

\underbrace{\max_{p\in\Delta_m}\ \min_{q\in\Delta_n}\ p\T Aq}_{\text{Alice commits first}}\qquad\text{and}\qquad\underbrace{\min_{q\in\Delta_n}\ \max_{p\in\Delta_m}\ p\T Aq}_{\text{Bob commits first}}

In wordsThe first is the most Alice can guarantee even if Bob sees her probabilities. The second is the least Bob can hold Alice to even if Alice sees his. The minimax theorem says they are equal; the common value is the value of the game.

Tool 1: a linear function over the simplex is optimized at a corner

\min_{q\in\Delta_n}\ c\T q\;=\;\min_{1\le j\le n}\ c_j,\qquad\max_{p\in\Delta_m}\ d\T p=\max_{1\le i\le m}d_i.

In wordsAgainst a fixed opponent mix, some pure strategy is a best response: put all probability on the best coordinate.

Why it is true $c\T q=\sum_jc_jq_j$ is a weighted average of the $c_j$ with weights $q_j\ge0$ summing to 1, and an average is never below its smallest entry. Putting $q=e_j$ on the smallest $c_j$ attains it. (Geometrically: the vertices of $\Delta_n$ are the unit vectors $e_j$ , and a linear objective is optimized at a vertex, unit 2.5.)

Tool 2: the easy inequality (weak duality for games)

\max_{p}\min_{q}\ p\T Aq\;\le\;\min_{q}\max_{p}\ p\T Aq.

Why it is trueFor any $p'$ and $q'$ : $\min_qp'^{\top}Aq\le p'^{\top}Aq'\le\max_pp\T Aq'$ . The left side does not depend on $q'$ and the right side does not depend on $p'$ , so maximize the left over $p'$ and minimize the right over $q'$ .

When you use itExactly like weak LP duality: any guarantee for Alice is at most any guarantee for Bob. The minimax theorem is the "strong duality" statement that they meet.

Tool 3: how the LP enters

By Tool 1, Alice's guarantee for a fixed $p$ is $\min_j(p\T A)_j$ , a minimum of linear functions of $p$ . Maximizing a minimum is an LP via the "maximize a minimum" trick of unit 1.6 (a free variable $v$ below every column payoff, plus the simplex constraints on $p$ ). Bob's problem is the same with max and min swapped. Writing the dual of Alice's LP with the rulebook of unit 3.5 (the equality $\sum_ip_i=1$ gives a free dual variable; the free $v$ gives an equality dual constraint) and applying strong duality is how the minimax theorem is proved.

I understand this unit

Unit 4.1 · Max-flow = min-cut via duality

The path-flow LP

Sources: L10 §5.1; Lec10_SecB p.5

L8 proved max-flow = min-cut using residual graphs. L10 reaches the same theorem through LP duality. That route also introduces rounding, the main idea of approximation algorithms.

(P_flow): one variable per s–t path

\max\ \sum_{p\in\mathcal P}x_p \qquad\text{s.t.}\qquad \sum_{p\,\ni\, e}x_p\le c_e\ \ (\forall e\in E),\qquad x_p\ge0\ \ (\forall p\in\mathcal P).

In wordsSend $x_p$ units along each $s$ – $t$ path $p$ . The total flow is the sum. On every edge, the total of all paths using that edge must fit within its capacity.

Symbol by symbol

$\mathcal P$	the finite set of all simple directed $s$ – $t$ paths (can be exponentially many)
$x_p$	how much flow is sent along path $p$
$p\ni e$	"paths $p$ that contain edge $e$ "
$\sum_{p\ni e}x_p$	total flow on edge $e$ contributed by all paths through it
$c_e$	capacity of edge $e$

Why it is trueIts optimum equals the edge-LP optimum (below). There is one constraint per edge and one variable per path.

When you use itIts dual has a clean meaning (edge lengths), which is the point of this formulation.

Two paths with 2 units each give total flow 4. Edge

s\to a

only carries the blue path, so its row reads

x_{sat}\le3

.

Why path LP and edge LP have the same optimum

Path → edge. Set $f_e=\sum_{p\ni e}x_p$ . Each path conserves flow at every interior vertex (one unit in, one unit out), so the sum does too. The capacity rows give $f_e\le c_e$ . The value is $\sum_p x_p$ .

Edge → path (flow decomposition). Any feasible flow of nonnegative value splits into $s$ – $t$ path flows plus cycle flows. Cycles add no value and can be discarded. One way to see it: add an edge $t\to s$ carrying the flow value, which makes every vertex conserve flow (a circulation). Then repeatedly follow positive edges until a cycle closes and subtract its smallest flow. Each round zeroes at least one edge. Cycles through $t\to s$ are $s$ – $t$ paths.

I understand this unit

Unit 4.2 · Max-flow = min-cut via duality

The dual: edge lengths, and every cut is a dual solution

Sources: L10 §5.2; Lec10_SecB p.5

Give the capacity row of edge $e$ the multiplier $y_e\ge0$ (≤ rows in a max problem). Column $x_p$ has a 1 in row $e$ exactly when $e\in p$ , and objective coefficient 1. Applying the recipe:

(D_length)

\min\ \sum_{e\in E}c_e\,y_e\qquad\text{s.t.}\qquad \sum_{e\in p}y_e\ge1\ \ (\forall p\in\mathcal P),\qquad y_e\ge0\ \ (\forall e\in E).

In wordsAssign each edge a nonnegative length $y_e$ so that every $s$ – $t$ path has total length at least 1. Minimize the capacity-weighted total length.

Symbol by symbol

$y_e$	length of edge $e$ (dual variable of its capacity row)
$\sum_{e\in p}y_e\ge1$	dual constraint for variable $x_p$ : path $p$ is at least 1 long
$\sum_ec_ey_e$	"cost" of the length assignment, not the length of any single path

Why it is trueRecipe: dual constraint for $x_p$ = column of $x_p$ (1's on edges of $p$ ) $\cdot\,y\ \ge$ objective coefficient 1. Dual objective = capacities · $y$ .

When you use itThink of $y_e$ as how much of edge $e$ you cut: every $s$ – $t$ path must be cut by a total of at least 1. The dual is a fractional cut: a barrier spread over edges that every path must pay to cross.

Intuitive approach

Three ways to picture the "lengths"

1. Roadblocks. You want to stop all trucks from reaching $t$ . You may block a fraction $y_e\in[0,1]$ of each road (e.g. close some lanes). A route is stopped once the fractions blocked along it add up to at least 1. Blocking a fraction $y_e$ of a road with capacity $c_e$ costs $c_ey_e$ : wide highways are expensive to block. The dual asks for the cheapest way to stop every route. Blocking a road completely ( $y_e=1$ ) on every road leaving a set $S$ is an ordinary cut.

2. Tolls. Charge a toll $y_e$ on each road, such that every route from $s$ to $t$ costs at least $1 in tolls. Your "cost" is the toll revenue you would forgo if every road ran at full capacity, $\sum_ec_ey_e$ . Checking all routes at once is easy: find the cheapest route (Dijkstra, unit 4.5).

3. Stretchy pipes (why "length"). Each road is a pipe whose cross-section is $c_e$ . Choose its length $y_e$ so that $t$ is at least distance 1 from $s$ along every route. The material used is cross-section × length, $\sum_ec_ey_e$ : the dual minimizes the material needed to push $t$ one unit away from $s$ . The cheapest way is to put all the length on thin pipes that every route must pass through: a min cut.

Pipe thickness = capacity. Every route from

s

to

t

passes through exactly one pink pipe, so giving the pink pipes length 1 puts

t

at distance 1. That costs 4 units of material, the same as the maximum flow.

Every s–t cut is a feasible 0/1 dual solution

Cut → lengths

\delta^+(S)=\{(u,v)\in E:\ u\in S,\ v\notin S\},\qquad y_e=\begin{cases}1 & e\in\delta^+(S)\\0&\text{otherwise}\end{cases}\quad\Rightarrow\quad\sum_e c_ey_e=c(\delta^+(S)).

In wordsPut length 1 on edges leaving $S$ and 0 elsewhere. The dual cost is exactly the cut capacity.

Symbol by symbol

$S$	a vertex set with $s\in S$ , $t\notin S$ (an $s$ – $t$ cut)
$\delta^+(S)$	directed edges leaving $S$ ; edges entering $S$ do not count
$c(\delta^+(S))$	capacity of the cut

Why it is trueAny $s$ – $t$ path starts inside $S$ and ends outside, so it must use at least one edge of $\delta^+(S)$ . Its length is ≥ 1, so the solution is feasible.

Example: $S=\{s,a,b\}$ gives the edges $a\to t$ (cap 2) and $b\to t$ (cap 3), so dual value 5.

So far: $\text{max flow} = \opt(D_\text{length}) \le \text{min cut}$ . The first equality is strong duality, the inequality holds because cuts are special dual solutions.

I understand this unit

Unit 4.3 · Max-flow = min-cut via duality

Threshold rounding: from lengths to a cut

Sources: L10 §6–6.1; Lec10_SecB p.6

Treat the lengths as distances from $s$ , and cut the graph at a "radius" $r$ .

Clipped distances and threshold sets

\ell(v)=\min\{d(v),1\},\qquad S_r=\{v:\ \ell(v)\le r\}\quad(0<r<1),\qquad \ell(s)=0,\ \ \ell(t)=1.

In wordsCompute shortest-path distances $d(v)$ from $s$ using lengths $y$ . Cap them at 1. For a threshold $r$ , $S_r$ is the "ball" of all vertices within distance $r$ of $s$ .

Symbol by symbol

$d(v)$	shortest-path distance from $s$ to $v$ with edge lengths $y_e$ ( $+\infty$ if unreachable)
$\ell(v)$	clipped distance, always in $[0,1]$
$S_r$	also written $B_r=\{v: d(s,v)\le r\}$ , a ball around $s$ (same set for $r<1$ )
$\ell(t)=1$	feasibility says every path has length $\ge1$ , so $d(t)\ge1$ (Observation 1)

Why it is true $s\in S_r$ since $\ell(s)=0\le r$ . $t\notin S_r$ since $\ell(t)=1>r$ . So every $S_r$ is an $s$ – $t$ cut.

The running example. Dashed rings are the clipped distances

\ell(a)=0.4

,

\ell(b)=0.7

,

\ell(t)=1

. Any ripple radius strictly between 0 and 1 gives a cut, and the radius decides which one.

Key lemma: an edge is cut for at most y_e of the thresholds

e=(u,v)\in\delta^+(S_r)\iff \ell(u)\le r<\ell(v),\qquad\text{an interval of length}\ \max\{0,\ell(v)-\ell(u)\}\le y_{uv}.

In wordsAs $r$ sweeps from 0 to 1, edge $u\to v$ leaves the cut set only while the "gate" $r$ is past $u$ but not yet past $v$ . That window is at most as long as the edge itself.

Symbol by symbol

$\ell(u)\le r$	tail $u$ is inside the ball
$r<\ell(v)$	head $v$ is outside
$\max\{0,\cdot\}$	if $\ell(v)\le\ell(u)$ the edge never crosses outward

Why it is trueIf $d(u)<1$ : shortest paths satisfy the triangle inequality $d(v)\le d(u)+y_{uv}$ , and clipping at 1 can only shrink a positive difference. If $d(u)\ge1$ or $u$ is unreachable, $\ell(u)=1\ge\ell(v)$ and the window is empty.

When you use itObservation 2: edge $e=(u,v)$ is cut with probability $\le y_e$ . If $r$ is drawn uniformly from $(0,1)$ , the probability that $e$ is cut is the window length, at most $y_e$ .

I understand this unit

Unit 4.4 · Max-flow = min-cut via duality

Averaging: some threshold cut is cheap

Sources: L10 §6.2

Average cut capacity over thresholds

\int_0^1 c\big(\delta^+(S_r)\big)\,dr \;=\;\sum_{(u,v)\in E}c_{uv}\max\{0,\ell(v)-\ell(u)\}\;\le\;\sum_{e\in E}c_ey_e.

In wordsAverage the cut capacity over all thresholds. Each edge contributes its capacity times the fraction of thresholds that cut it, which is at most its length.

Symbol by symbol

$\int_0^1\cdots dr$	average over $r\in(0,1)$ (area under a step function; no calculus is really needed)
equality	swap "sum over edges" and "average over $r$ ": an edge contributes $c_{uv}$ for a window of length $\max\{0,\ell(v)-\ell(u)\}$
$\le$	the key lemma, edge by edge

Why it is trueThe cut only changes when $r$ passes one of the finitely many distances $\ell(v)$ . So the integral is a weighted average of finitely many cut values, weighted by the lengths of the threshold intervals.

Conclusion

\text{some } S_r \text{ satisfies}\quad c\big(\delta^+(S_r)\big)\;\le\;\sum_ec_ey_e.

In wordsSomething is always at most its average: at least one threshold gives a cut no more expensive than the fractional solution.

Why it is trueIf every cut were more expensive than the average, the average would be larger than itself. This "something is at most the average" step is the averaging principle that drives most of the approximation proofs in Chapter 9.

When you use itDeterministic algorithm: compute distances (Dijkstra), sort the distinct clipped values, test one threshold in each interval (at most $|V|-1$ cuts), and keep the cheapest.

The example, computed by hand

Capacities $c_{sa}=3,\ c_{at}=2,\ c_{sb}=2,\ c_{bt}=3$ . Lengths $y_{sa}=.4,\ y_{at}=.6,\ y_{sb}=.7,\ y_{bt}=.3$ . Both paths have length exactly 1, so the solution is feasible. Distances: $\ell(s)=0,\ \ell(a)=.4,\ \ell(b)=.7,\ \ell(t)=1$ .

threshold range	$S_r$	edges leaving	capacity	interval length
$0<r<.4$	$\{s\}$	$s\to a,\ s\to b$	3+2 = 5	.4
$.4\le r<.7$	$\{s,a\}$	$s\to b,\ a\to t$	2+2 = 4	.3
$.7\le r<1$	$\{s,a,b\}$	$a\to t,\ b\to t$	2+3 = 5	.3

\text{average}=.4\cdot5+.3\cdot4+.3\cdot5=4.7,\qquad \sum_ec_ey_e=3(.4)+2(.6)+2(.7)+3(.3)=4.7.

The cut $\{s,a\}$ costs $4\le4.7$ . Since a cut of cost 4 exists, these lengths are feasible but not dual-optimal. The optimal dual is the 0/1 cut solution of value 4, matching the flow of value 4.

I understand this unit

Unit 4.5 · Max-flow = min-cut via duality

Completing max-flow = min-cut, and checking the dual fast

Sources: L10 §6.3 + exercise

The chain

\text{max flow}\;\overset{(1)}{\le}\;\text{min cut}\;\overset{(2)}{\le}\;\opt(D_\text{length})\;\overset{(3)}{=}\;\text{max flow}.

In wordsSqueeze: a quantity that is ≤ something that is ≤ itself must equal it. All three numbers are equal.

Symbol by symbol

(1)	the L8 cut bound: net flow across any cut cannot exceed the capacity of its outward edges
(2)	threshold rounding applied to an optimal length solution gives a cut of no larger cost
(3)	strong LP duality for (P_flow)/(D_length)

For the example: the flow of value 4 and the cut $\{s,a\}$ of capacity 4 certify each other, so max flow = min cut = 4.

Exercise (L10): checking exponentially many path constraints with one Dijkstra run

Given nonnegative lengths

y_e

, how does one Dijkstra run verify every constraint of

D_\text{length}

or exhibit a violated one? Why don't we need to list all paths? What if

t

is unreachable?

Show answer

Run Dijkstra from

s

with lengths

y_e

(valid because

y\ge0

). The shortest

s

–

t

distance

d(t)

is the minimum length over all paths. If

d(t)\ge1

then every path has length ≥ 1, so all (exponentially many) constraints hold at once. If

d(t)<1

, the shortest path found is an explicit violated constraint. We only ever need the minimum path length, not the list. If

t

is unreachable,

d(t)=\infty\ge1

: there are no

s

–

t

paths, so there are no constraints to violate. This "find a violated constraint quickly" idea is called a separation oracle, and it is why exponentially large LPs can still be solvable (via the ellipsoid method).

I understand this unit

Unit 5.1 · Why strong duality holds

The proof plan: tight normals block every improving direction

Sources: L11 §1; Lec11_SecB p.1

Weak duality is one line of algebra. Strong duality says an exact certificate always exists, and that needs real geometry. The whole proof rests on one picture.

At an optimum

x^*

, the objective direction

c

is a nonnegative combination of the outward normals of the constraints that are tight at

x^*

.

Write all primal constraints in one list, including the sign constraints:

All constraints as one list

a_r\T x\le d_r\qquad(r=1,\dots,m+n),\qquad\text{where the last } n \text{ rows are } -x_i\le0.

Symbol by symbol

$r\le m$	original rows: $a_r$ = row $r$ of $A$ , $d_r=b_r$
$r>m$	sign rows: $a_r=-e_i$ (minus the $i$ -th unit vector), $d_r=0$
$S$	the set of rows that are tight at $x^$ : $a_r\T x^=d_r$

The claim to prove

c\;=\;\sum_{r\in S}\lambda_r\,a_r\qquad\text{for some }\lambda_r\ge0.

In wordsThe objective direction lies in the cone generated by the tight outward normals.

Symbol by symbol

$\lambda_r$	nonnegative weights; these will become the dual solution
$S$	only tight constraints are used

Intuitive approach

A ball pushed into a corner by the wind

Put a ball inside the feasible region and let a steady wind blow in direction $c$ (the direction in which the objective increases). The ball is blown as far as it can go and comes to rest at an optimal point $x^*$ , pressed against some walls.

At rest the forces balance. The wind pushes with force $c$ . Each wall the ball touches pushes back along its normal, with force $-\lambda_ra_r$ . Balance: $c=\sum_r\lambda_ra_r$ .
A wall can push but not pull, so $\lambda_r\ge0$ . That is why the coefficients lie in a cone and not in a subspace.
A wall the ball does not touch exerts no force: $\lambda_r=0$ for slack constraints. That is complementary slackness.
The wall forces $\lambda_r$ are the dual variables, or "prices". A wall that pushes hard is a constraint whose loosening would let the ball move further in the wind: a valuable resource.

The proof makes this precise. If the forces could not balance ( $c$ not in the cone), the ball would not be at rest: Farkas gives a direction in which it can still move with the wind.

At the optimum (red ball) the objective direction

c

splits into nonnegative amounts of the touching walls' outward normals. Those amounts are the dual solution.

The three steps

Farkas' lemma: either $c$ is in the cone of tight normals, or there is a direction $v$ that moves "into" every tight wall's allowed side while improving the objective.
Contradiction: a tiny step along such a $v$ is feasible and strictly better, which is impossible at an optimum. So $c$ is in the cone.
Read off the dual: the weights $\lambda_r$ on original rows form a dual-feasible $y$ with $b\T y=c\T x^*$ . Weak duality finishes the proof.

Picture it

Why only the tight constraints matter

Here is why only tight constraints matter at $x^*$ .

A tight constraint $a\T x\le d$ with $a\T x^*=d$ sits right on its wall. Any move $v$ with $a\T v>0$ immediately crosses the wall and becomes infeasible. So tight constraints restrict the direction you can move in: you need $a\T v\le0$ .
A slack constraint has $a\T x^*<d$ . There is a positive gap, so a small enough step in any direction keeps it satisfied. Slack constraints restrict only how far you can go, never which way.

Whether you are at an optimum is a question about directions ("is there an improving direction I am allowed to take?"), so only tight constraints are involved. This is also why inactive constraints get multiplier 0 in the dual (complementary slackness).

I understand this unit

Unit 5.2 · Why strong duality holds

Cones and Farkas' lemma: certificates of infeasibility

Sources: L11 §2; Lec11_SecB p.2

Cone generated by vectors

C=\Big\{\sum_{j=1}^{k}\lambda_j a_j:\ \lambda_j\ge0\Big\}=\{M\lambda:\ \lambda\ge0\},\qquad M=[\,a_1\ \cdots\ a_k\,].

In wordsEverything you can build by adding nonnegative amounts of the generators $a_1,\dots,a_k$ . In 2-D it is a wedge from the origin.

Symbol by symbol

$a_j\in\R^d$	generator vectors, the columns of $M$
$\lambda_j\ge0$	amounts; negative amounts are not allowed (otherwise you would get a whole subspace)
$M\lambda$	the column view: $M\lambda=\sum_j\lambda_ja_j$

When you use it"Is $p$ in the cone?" is the feasibility question " $M\lambda=p,\ \lambda\ge0$ ".

Reading system (II)

M\T w\ge0 \iff a_j\T w\ge0\ \ \forall j,\qquad p\T w<0.

In wordsFind a test direction $w$ such that every generator has a nonnegative dot product with $w$ (all lie on one side of the line $w\T z=0$ ) while $p$ has a negative one ( $p$ is strictly on the other side).

Why it is trueEvery point of the cone, $\sum\lambda_ja_j$ , then also has $w\T(\cdot)=\sum\lambda_j\,a_j\T w\ge0$ . So $p$ cannot be in the cone. $w$ is a short, checkable proof that (I) is infeasible.

Why both cannot hold (the easy half)

p\T w=(M\lambda)\T w=\lambda\T(M\T w)\ \ge\ 0

In wordsIf $p$ were built from the generators, its test value would be a nonnegative mixture of nonnegative numbers, so not negative.

Why it is true $\lambda\ge0$ and $M\T w\ge0$ , so their dot product is ≥ 0. That contradicts $p\T w<0$ .

The substantive half is that when $p\notin C$ , a witness $w$ always exists. That needs separation (next unit).

I understand this unit

Unit 5.3 · Why strong duality holds

The separation theorem: the nearest point gives the wall

Sources: L11 §3; Lec11_SecB p.2

The construction

q\in\arg\min_{z\in C}\norm{p-z},\qquad v=p-q.

In wordsLet $q$ be the point of $C$ closest to $p$ . The arrow $v$ from $q$ to $p$ is the normal of a wall through $q$ that keeps all of $C$ on one side and $p$ on the other.

Symbol by symbol

$q$	nearest point of $C$ to $p$ ; it exists because $C$ is closed and nonempty (restrict to a closed ball around $p$ , which is compact)
$v=p-q$	points from the set toward the outside point
$v\T z\le v\T q$	every point of $C$ lies on or behind the wall $\{z: v\T z=v\T q\}$

Proof: why the nearest point works

Take any $z\in C$ . By convexity the whole segment $q+\theta(z-q)=\theta z+(1-\theta)q$ , $0\le\theta\le1$ , lies in $C$ . Measure its squared distance to $p$ :

Expanding the squared distance

\norm{p-(q+\theta(z-q))}^2 \;=\; \norm{p-q}^2\;-\;2\theta\,v\T(z-q)\;+\;\theta^2\norm{z-q}^2.

In wordsThe distance from $p$ to a point that has moved a fraction $\theta$ toward $z$ is the old distance, minus a term that is linear in $\theta$ , plus a term that is quadratic in $\theta$ .

Symbol by symbol

$a=p-q=v$ , $b=\theta(z-q)$	then $p-(q+\theta(z-q))=a-b$ ; apply $\norm{a-b}^2=\norm a^2-2a\T b+\norm b^2$
$-2\theta v\T(z-q)$	the linear term; it dominates for small $\theta$
$\theta^2\norm{z-q}^2$	the quadratic term; negligible for small $\theta$

Why it is trueIf $v\T(z-q)>0$ , then for small enough $\theta>0$ the negative linear term beats the positive quadratic term ( $\theta^2$ is much smaller than $\theta$ ). The point $q+\theta(z-q)\in C$ would then be closer to $p$ than $q$ , contradicting the choice of $q$ .

When you use itConclusion: $v\T(z-q)\le0$ , i.e. $v\T z\le v\T q$ for all $z\in C$ . Finally $v\T p-v\T q=v\T v=\norm{p-q}^2>0$ because $p\ne q$ .

I understand this unit

Unit 5.4 · Why strong duality holds

From separation to Farkas: the cone case, step by step

Sources: L11 §3.1; Lec11_SecB p.2

Step 0: why a cone is convex (and closed)

Take two cone points $M\lambda$ and $M\mu$ with $\lambda,\mu\ge0$ . For $\theta\in[0,1]$ : $\theta M\lambda+(1-\theta)M\mu=M(\theta\lambda+(1-\theta)\mu)$ , and $\theta\lambda+(1-\theta)\mu\ge0$ . So the blend is again in the cone. Closed: a cone generated by finitely many vectors is closed. This is a standard fact used without proof in the course.

Step 1: apply separation

$p\notin C$ , so there are $v,q$ with $v\T p>v\T q\ge v\T z$ for all $z\in C$ .

Step 2: the upper bound $v\T q$ is at least 0

$0\in C$ (take all $\lambda_j=0$ ), so $v\T q\ge v\T0=0$ .

Step 3: every generator has $v\T a_j\le0$

The scaling argument

t\,a_j\in C\ \ \forall t\ge0\quad\Longrightarrow\quad t\,(v\T a_j)\;\le\;v\T q\ \ \forall t\ge0\quad\Longrightarrow\quad v\T a_j\le0.

In wordsA cone contains every stretched copy of each generator. If some generator had a positive dot product with $v$ , stretching it would push $v\T(ta_j)$ to infinity, past the fixed number $v\T q$ . So no generator can have a positive dot product.

Why it is trueIf $v\T a_j>0$ , choose $t>v\T q/(v\T a_j)$ . Then $t\,v\T a_j>v\T q$ , which contradicts separation.

Step 4: $p$ is strictly on the positive side

By Step 3 every cone point $z=\sum\lambda_ja_j$ has $v\T z=\sum\lambda_j v\T a_j\le0$ . In particular $v\T q\le0$ , and with Step 2, $v\T q=0$ . Separation then gives $v\T p>v\T q=0$ .

Step 5: flip the sign to get the Farkas witness

Orientation

w=-v\quad\Longrightarrow\quad M\T w=(-v\T a_j)_j\ge0,\qquad p\T w=-v\T p<0.

In wordsSeparation's normal points toward $p$ . Farkas orients it the other way, so that generators score ≥ 0 and $p$ scores < 0. Negating $v$ does that.

I understand this unit

Unit 5.5 · Why strong duality holds

Farkas' lemma in other forms, and how to convert between them

Sources: L11 §2 (cone form); standard variants

Farkas' lemma comes in several equivalent versions. Each one says the same thing: a linear system has no solution exactly when some combination of its rows produces an obvious contradiction. You can derive any version from any other with the conversion tools of unit 1.5.

System (I) is infeasible …	… iff this certificate exists	Certificate's sign
(F1) $Ax=b,\ x\ge0$	$A\T y\ge0,\ \ b\T y<0$	$y$ free
(F2) $Ax\le b,\ x\ge0$	$A\T y\ge0,\ \ b\T y<0$	$y\ge0$
(F3) $Ax\le b$ ( $x$ free)	$A\T y=0,\ \ b\T y<0$	$y\ge0$

(F1) is the lecture's version with $M=A$ , $p=b$ , $w=y$ : " $b$ is in the cone of the columns of $A$ , or a witness separates it".

The easy direction is always one line

Example: why (F3)'s two systems can't both hold

0=(A\T y)\T x=y\T Ax\;\le\;y\T b\;<\;0.

In wordsA contradiction, so if the certificate exists the system is infeasible.

Symbol by symbol

first $=$	$A\T y=0$
$\le$	$Ax\le b$ and $y\ge0$ (nonnegative weights keep ≤)
$<$	$b\T y<0$

Worked conversion: (F1) ⇒ (F2)

Rewrite the system in (F1)'s form. Add slacks: $Ax\le b,\ x\ge0$ has a solution iff $Ax+s=b,\ x\ge0,\ s\ge0$ has one, i.e. iff $[A\ \ I]\binom{x}{s}=b$ with $\binom{x}{s}\ge0$ .
Apply (F1) with the matrix $A'=[A\ \ I]$ : infeasible iff some $y$ has $A'^{\top}y\ge0$ and $b\T y<0$ .
Unpack $A'^{\top}y=\binom{A\T y}{y}\ge0$ : that is $A\T y\ge0$ and $y\ge0$ . The slack columns are what force $y$ to be nonnegative. ∎

I understand this unit

Unit 5.6 · Why strong duality holds

If c is outside the cone, there is a better feasible point

Sources: L11 §4–4.1; Lec11_SecB p.3

Suppose the claim $c=\sum_{r\in S}\lambda_ra_r,\ \lambda\ge0$ fails. Apply Farkas with $M=[a_r]_{r\in S}$ (tight normals as columns) and $p=c$ . We get $w$ with $a_r\T w\ge0$ for all tight $r$ , and $c\T w<0$ . Set $v=-w$ :

An improving, feasible direction

a_r\T v\le0\ \ (r\in S),\qquad c\T v>0.

In words $v$ does not push outward through any tight wall, yet it strictly increases the objective.

Symbol by symbol

$a_r\T v\le0$	moving along $v$ does not increase constraint $r$ 's left side, so tight row $r$ stays satisfied
$c\T v>0$	the objective goes up along $v$

Now step from $x^*$ to $x^*+\eps v$ and check every constraint:

Tight constraints stay feasible

a_r\T(x^*+\eps v)=\underbrace{a_r\T x^*}_{=d_r}+\eps\underbrace{a_r\T v}_{\le0}\le d_r\qquad(r\in S).

In words $a_r\T x^*+\eps a_r\T v=d_r+(\text{something}\le0)\le d_r$ : a tight wall is never crossed.

Slack constraints: pick ε small enough

\delta_r=d_r-a_r\T x^*>0\ (r\notin S);\qquad \text{if } a_r\T v>0,\ \text{require}\ \eps\le\frac{\delta_r}{a_r\T v}.

In wordsEach slack constraint has a positive cushion $\delta_r$ . Moving along $v$ uses it up at rate $a_r\T v$ (if positive), so a step of size up to $\delta_r/(a_r\T v)$ is safe.

Symbol by symbol

$\delta_r$	slack (cushion) of inactive row $r$
$a_r\T v\le0$	then row $r$ never gets closer to its wall, so no restriction
finitely many rows	so the minimum of the ratios is a positive number: one $\eps>0$ works for all rows at once, including the sign rows

Contradiction

c\T(x^*+\eps v)=c\T x^*+\eps\,c\T v>c\T x^*.

In wordsA feasible point with a strictly higher objective, which is impossible because $x^*$ is optimal. So the claim holds: $c$ is in the cone of tight normals.

I understand this unit

Unit 5.7 · Why strong duality holds

Turning the cone coefficients into a dual solution

Sources: L11 §4.2, §5; Lec11_SecB p.3

We now have $c=\sum_{r\in S}\lambda_ra_r$ with $\lambda_r\ge0$ . Give every inactive row coefficient 0 (this is the equation $y(a\T x-b)=0$ : an inactive row gets weight 0). Split the coefficients:

Split into original rows and sign rows

c\;=\;\sum_{j=1}^{m}y_j\,(\text{row } j \text{ of } A)\;+\;\sum_{i=1}^{n}z_i\,(-e_i)\;=\;A\T y-z,\qquad y\ge0,\ z\ge0.

In wordsThe weights on the $m$ original constraints are $y$ . The weights on the $n$ sign constraints $-x_i\le0$ are $z$ .

Symbol by symbol

$y_j=\lambda_j$	coefficient of original row $j$ (zero if that row is slack at $x^*$ )
$z_i$	coefficient of the sign row $-x_i\le0$ (zero if $x_i^*>0$ )
$-z$	the normals of sign rows are $-e_i$ , which is why $z$ enters with a minus

y is dual feasible

A\T y=c+z\;\ge\;c,\qquad y\ge0.

In wordsSince $z\ge0$ , the combined coefficients dominate $c$ . This is exactly the dual constraint. And $z=A\T y-c$ is the dual slack vector.

…with the same value as x*

c\T x^*=\sum_{r\in S}\lambda_r\,a_r\T x^*=\sum_{r\in S}\lambda_r\,d_r=b\T y.

In wordsEvery row with a positive weight is tight ( $a_r\T x^*=d_r$ ). Sign rows have $d_r=0$ , so they contribute nothing to the right side. What is left is $\sum_j y_jb_j$ .

Finish: $x^*$ is primal feasible, $y$ is dual feasible, and $c\T x^*=b\T y$ . By weak duality $y$ is dual-optimal and the two optimal values coincide. This is strong duality. ∎

L11 exercise: $\max(-x)$ s.t. $x\le1,\ x\ge0$

Write the dual, find an optimal primal–dual pair, and say which normal supplies the objective direction in the strong-duality proof.

Show answer

A=[1],\ b=1,\ c=-1

. Dual:

\min y

s.t.

y\ge-1,\ y\ge0

, so

y^*=0

. Primal optimum

x^*=0

. Both values are 0, so the pair is optimal. At

x^*=0

the tight row is

-x\le0

(normal

-1

), and

x\le1

is slack (so

y=0

). Decomposition:

c=A\T y-z=0-1

with

z=1

. The nonnegativity normal supplies the objective direction. This is why the bookkeeping must include sign constraints.

What the three LP lectures give you (L11 §5)

Modeling: real variables and linear constraints express resource allocation and graph problems.
Algorithms: polynomial-size rational LPs are solvable in polynomial time in their encoding length.
Certificates: a feasible solution and a matching dual solution prove optimality.
Geometry: at an optimum, tight constraints block every improving direction. Farkas turns this into multipliers.
Rounding: a fractional optimum can guide the search for an integral one. Max-flow/min-cut is an exact example.

I understand this unit

Unit 6.1 · Convex functions

The offline convex optimization problem

Sources: L12 §1; Lec12_secB p.3 ("Now we look at min f(x), K convex")

An LP optimizes a linear function over a convex region. Now the objective may be nonlinear, but we keep the property that makes the problem tractable: convexity.

The problem

\min_{x\in K}\ f(x),\qquad f:\R^d\to\R,\quad K\subseteq\R^d \text{ nonempty and convex}.

In wordsFind the lowest point of a landscape $f$ over an allowed region $K$ .

Symbol by symbol

$d$	dimension (number of variables); L12 uses $d$ where the LP lectures used $n$
$K$	feasible set; in the main L12 theorem $K=\R^d$ (unconstrained)
$x^*$	a minimizer. Writing $x^$ assumes* one exists (e.g. $e^x$ on $\R$ has none)

ε-optimal (additive)

x\in K\quad\text{and}\quad f(x)-f(x^*)\le\eps.

In wordsA feasible answer whose value is at most $\eps$ above the best possible value.

Symbol by symbol

$f(x)-f(x^*)$	the optimality gap (objective error), always ≥ 0
$\eps$	the tolerance you are willing to accept

When you use itGradient descent guarantees this with $\eps=DG/\sqrt T$ . Note it is additive, not a ratio $f(x)/f(x^*)$ , which would be meaningless if $f(x^*)\le0$ .

I understand this unit

Unit 6.2 · Convex functions

Convex functions: the graph lies below every chord

Sources: L12 §1; Lec12_secB p.1 (θ-form and figure)

Definition: convex function

f\big(\theta x+(1-\theta)y\big)\;\le\;\theta f(x)+(1-\theta)f(y)\qquad\forall x,y\in K,\ \ \forall\theta\in[0,1].

In wordsThe value at a blend of two inputs is at most the same blend of the two values. Geometrically, the graph lies on or below the straight chord joining $(x,f(x))$ and $(y,f(y))$ .

Symbol by symbol

$\theta x+(1-\theta)y$	a point on the segment between $x$ and $y$ (in $K$ because $K$ is convex)
$f(\theta x+(1-\theta)y)$	height of the graph above that point
$\theta f(x)+(1-\theta)f(y)$	height of the chord above that point
$K$	domain; it must be convex or the left side might not even be defined

Why it is trueA definition. L12 writes it with $\lambda$ , the board with $\theta$ , sometimes as $(1-\theta)x+\theta y$ . These are all the same statement with the roles of $x,y$ swapped.

When you use itProving local ⇒ global; the many-point (Jensen) inequality for the average iterate; and, in the limit $\theta\to0$ , the tangent inequality.

The board figure: the red gap between chord and graph is never negative for a convex function.

I understand this unit

Unit 6.3 · Convex functions

First-order condition: tangents are global lower bounds

Sources: L12 §2; Lec12_secB pp.1–2 (proof with board annotation (y−x)/(y−x))

Decoding the tangent inequality

\underbrace{f(y)}_{\text{true value at }y}\;\ge\;\underbrace{f(x)+\langle\nabla f(x),y-x\rangle}_{\text{tangent plane at }x\text{, evaluated at }y}

In wordsBuild the tangent line (plane) at any point $x$ . For a convex function it lies below the graph everywhere, not only near $x$ . So local slope information gives a global lower bound.

Symbol by symbol

$f(x)+\langle\nabla f(x),y-x\rangle$	first-order Taylor polynomial ("Taylor of degree 1") of $f$ around $x$
$\langle\nabla f(x),y-x\rangle$	predicted change: slope vector · displacement
$y-x$	the difference between the two points

When you use itPlugging in $y=x^*$ gives the inequality that drives the whole gradient-descent proof.

Proof (⇒): from chords to tangents

Write the blend toward $y$ as $x+\theta(y-x)=\theta y+(1-\theta)x$ . Convexity gives $f(x+\theta(y-x))\le\theta f(y)+(1-\theta)f(x)$ .
Subtract $f(x)$ from both sides: $f(x+\theta(y-x))-f(x)\le\theta\big(f(y)-f(x)\big)$ .
Divide by $\theta>0$ (keeps the direction): $\frac{f(x+\theta(y-x))-f(x)}{\theta}\;\le\;f(y)-f(x).$
Let $\theta\downarrow0$ . The left side is a difference quotient along direction $y-x$ , which converges to the directional derivative $\langle\nabla f(x),y-x\rangle$ . So $\langle\nabla f(x),y-x\rangle\le f(y)-f(x)$ . ∎

Proof (⇐): from tangents to chords

Let $z=\lambda x+(1-\lambda)y$ . Apply the tangent inequality at $z$ , once toward $x$ and once toward $y$ :

f(x)\ge f(z)+\langle\nabla f(z),x-z\rangle,\qquad f(y)\ge f(z)+\langle\nabla f(z),y-z\rangle.

Multiply by $\lambda$ and $1-\lambda$ and add. The gradient terms combine into $\langle\nabla f(z),\ \lambda x+(1-\lambda)y-z\rangle=\langle\nabla f(z),0\rangle=0$ . What remains is $\lambda f(x)+(1-\lambda)f(y)\ge f(z)$ , which is convexity. ∎

The inequality to remember

Objective error ≤ gradient inner product

f(x)-f(x^*)\;\le\;\langle\nabla f(x),\,x-x^*\rangle.

In wordsHow far you are above the optimum in value is at most (your slope) · (your displacement from the optimum).

Symbol by symbol

$x^*$	a minimizer (unknown to the algorithm, but usable in the analysis)
left side	the objective error, ≥ 0
right side	an inner product that appears when you expand a gradient step

Why it is truePut $y=x^*$ in the tangent inequality: $f(x^*)\ge f(x)+\langle\nabla f(x),x^*-x\rangle$ . Move terms: $f(x)-f(x^*)\le-\langle\nabla f(x),x^*-x\rangle=\langle\nabla f(x),x-x^*\rangle$ .

When you use itStep 1 of the gradient-descent proof. It turns "objective error" into "something the update rule controls".

I understand this unit

Unit 6.4 · Convex functions

Second-order test: the Hessian is positive semidefinite

Sources: L12 §3.1; Lec12_secB p.2 (Thm ②)

Positive semidefinite (PSD)

H\succeq0\iff v\T Hv=\sum_{i,j}H_{ij}v_iv_j\ge0\ \ \forall v.

In wordsIn every direction $v$ , the curvature (second derivative along that direction) is nonnegative: the function bends upward or is flat, never downward.

Symbol by symbol

$\nabla^2 f(x)$	Hessian: the matrix of second partial derivatives $\partial^2 f/\partial x_i\partial x_j$
$v\T Hv$	second derivative of $f$ along the line through $x$ in direction $v$
$\succeq0$	"is PSD" (not entrywise ≥ 0!)

Why it is trueRestrict $f$ to a line: $g(t)=f(x+tv)$ . The chain rule gives $g''(t)=v\T\nabla^2 f(x+tv)\,v$ . A 1-D function is convex iff $g''\ge0$ , and $f$ is convex iff its restriction to every line is convex.

When you use itQuick convexity checks: in 1-D just check $f''\ge0$ . For a $2\times2$ symmetric $H=\begin{pmatrix}a&b\\b&c\end{pmatrix}$ : PSD ⇔ $a\ge0,\ c\ge0,\ ac-b^2\ge0$ . In general: PSD ⇔ all eigenvalues ≥ 0.

Worked examples

$f$	Hessian / $f''$	Convex?
$x^2/2$	$1$	yes (strictly)
$e^x$	$e^x>0$	yes (but no minimizer on $\R$ )
$x^3$	$6x$ , negative for $x<0$	no
$(x^2-1)^2$	$12x^2-4$ , negative near 0	no (two local minima at ±1)
$x_1^2+x_1x_2+x_2^2$	$\begin{pmatrix}2&1\\1&2\end{pmatrix}$ : $2\ge0,\ 4-1\ge0$	yes
$x_1^2-x_2^2$	$\begin{pmatrix}2&0\\0&-2\end{pmatrix}$	no (saddle)
$\tfrac12\norm{Ax-b}^2$	$A\T A$ : $v\T A\T Av=\norm{Av}^2\ge0$	yes

I understand this unit

Unit 6.5 · Convex functions

Building convex functions: max, partial minimization, and more

Sources: Lec12_secB p.2 (Remark in red); L12 §3.1 (|x|, max of affine)

This unit covers the instructor's red Remark on the Lec12 board, plus the standard operations that preserve convexity. These rules let you prove convexity without computing any derivatives, which matters when a function is not differentiable.

Proof in one chain

g(\theta x+(1-\theta)y)=\max_i f_i(\theta x+(1-\theta)y)\;\le\;\max_i\big[\theta f_i(x)+(1-\theta)f_i(y)\big]\;\le\;\theta\max_if_i(x)+(1-\theta)\max_if_i(y).

In wordsEach piece is below its own chord. Taking the maximum keeps that, and the maximum of a sum is at most the sum of the maxima.

Symbol by symbol

1st $\le$	convexity of each $f_i$
2nd $\le$	$\theta f_i(x)\le\theta\max_k f_k(x)$ and similarly for $y$ , for every $i$ (uses $\theta,1-\theta\ge0$ )

Why it is trueEpigraph view: the epigraph of $\max_if_i$ is the intersection of the epigraphs, and intersections of convex sets are convex. This is the same reason LP regions are convex.

When you use it $|x|=\max(x,-x)$ ; piecewise-linear $\max_j(a_j\T x+b_j)$ ; $\norm{x}=\max_{\norm u\le1}u\T x$ ; and the "worst case over scenarios" objectives used in LP modeling.

The upper envelope (solid) of three lines (dashed) is convex, even though it has corners.

Proof

g(\theta x_1+(1-\theta)x_2)\;\le\;f\big(\theta x_1+(1-\theta)x_2,\ \theta y_1+(1-\theta)y_2\big)\;\le\;\theta f(x_1,y_1)+(1-\theta)f(x_2,y_2)\;\le\;\theta g(x_1)+(1-\theta)g(x_2)+\eps.

In wordsTake near-optimal partners $y_1,y_2$ for $x_1,x_2$ . Blending them gives a valid (but not necessarily best) partner for the blended $x$ , so the best value at the blend is no worse than the blend of the values.

Symbol by symbol

$y_1,y_2\in Y$	chosen with $f(x_k,y_k)\le g(x_k)+\eps$ (they exist by definition of $\inf$ )
1st $\le$	$\theta y_1+(1-\theta)y_2\in Y$ because $Y$ is convex, and $g$ is an infimum over all $y\in Y$
2nd $\le$	joint convexity of $f$ in the pair $(x,y)$
3rd $\le$	the choice of $y_1,y_2$

Why it is trueThe inequality holds for every $\eps>0$ , so it holds with $\eps=0$ .

When you use itThe distance to a convex set, $\mathrm{dist}(x,C)=\inf_{y\in C}\norm{x-y}$ , is convex because $\norm{x-y}$ is jointly convex. That is the function the separation theorem minimizes.

Partial minimization: minimizing the jointly convex

|x-y|

over

y

in a convex set leaves a convex function of

x

.

The rest of the toolbox

Operation	Result	Reason
$\alpha f+\beta g$ , $\alpha,\beta\ge0$	convex	add the two chord inequalities with nonnegative weights
$f(Ax+b)$ (affine input)	convex	affine maps send segments to segments
any norm $\norm{x}$	convex	triangle inequality + scaling
$\max_i f_i$	convex	Rule 1
$\inf_{y\in Y}f(x,y)$	convex	Rule 2
$\min(f,g)$ , $f\cdot g$ , $f-g$	not in general	$\min(x^2,(x-2)^2)$ has two dips. A product can fail, even when both factors are nonnegative. A difference can fail because $-g$ is concave.

Show

f(x)=\norm{Ax-b}_2+\max(0,\,1-x_1)

is convex.

Show answer

\norm{\cdot}

is convex and

x\mapsto Ax-b

is affine, so the first term is convex.

\max(0,1-x_1)

is a max of two affine functions (Rule 1). A sum of convex functions is convex.

I understand this unit

Unit 6.6 · Convex functions

Least squares, step by step

Sources: L12 §3.1 example

Least squares

f(x)=\tfrac12\norm{Ax-b}_2^2,\qquad \nabla f(x)=A\T(Ax-b),\qquad \nabla^2 f(x)=A\T A.

In wordsFit $x$ so that the predictions $Ax$ match the measurements $b$ as closely as possible in squared error.

Symbol by symbol

$A\in\R^{m\times d}$	$m$ measurements (rows), $d$ unknowns (columns)
$r=Ax-b\in\R^m$	residuals: errors in measurement space
$A\T r\in\R^d$	residuals sent back to the variables responsible for them: the gradient lives in variable space
$\tfrac12$	cosmetic; it cancels the 2 from differentiating a square

Why it is trueWrite $r_j=\sum_iA_{ji}x_i-b_j$ and $f=\tfrac12\sum_jr_j^2$ . The chain rule gives $\partial f/\partial x_i=\sum_jr_j\,\partial r_j/\partial x_i=\sum_jr_jA_{ji}=(A\T r)_i$ . Differentiating again, $\partial^2f/\partial x_i\partial x_k=\sum_jA_{ji}A_{jk}=(A\T A)_{ik}$ .

When you use itConvexity: $v\T A\T Av=\norm{Av}^2\ge0$ , so the Hessian is PSD everywhere.

Each residual is a spring stretched between a data point and the line. Total spring energy is

\tfrac12\norm{Ax-b}^2

. The line comes to rest where the net force is zero:

A\T(Ax-b)=0

, the normal equations.

Normal equations

\nabla f(x)=0\iff A\T Ax=A\T b.

In wordsSetting the gradient to zero (enough for convex $f$ , see the next unit) gives a linear system for the best fit.

Why it is trueIf the columns of $A$ are independent, $A\T A$ is positive definite ( $\norm{Av}^2>0$ for $v\ne0$ ): $f$ is strictly convex with the unique minimizer $x^*=(A\T A)^{-1}A\T b$ . If not, there are many minimizers.

I understand this unit

Unit 6.7 · Convex functions

Every local minimum of a convex function is global

Sources: L12 §3; Lec12_secB p.3

Walk from

\hat x

toward a better point

y

. For small

\theta

the point

z_\theta

is inside the neighbourhood, yet it is better than

\hat x

. Contradiction.

Stationary points and constraints

Unconstrained, differentiable, convex

\nabla f(x)=0\iff x \text{ is a global minimizer (on } \R^d).

In wordsFor convex functions on all of $\R^d$ , "flat" means "best".

Why it is true(⇒) Tangent inequality with $\nabla f(x)=0$ gives $f(y)\ge f(x)$ for all $y$ . (⇐) At an unconstrained minimum every directional derivative must be 0 (otherwise step the other way), so the gradient is 0.

Constrained first-order optimality (added bridge)

x^*\in\arg\min_{x\in K}f(x)\iff\langle\nabla f(x^*),\,y-x^*\rangle\ge0\quad\forall y\in K.

In wordsAt a constrained optimum, every feasible direction goes uphill or level. No feasible direction goes downhill.

Why it is true(⇒) A feasible direction with negative slope would give a nearby better feasible point. (⇐) Tangent inequality: $f(y)\ge f(x^*)+\langle\nabla f(x^*),y-x^*\rangle\ge f(x^*)$ .

When you use itFor an LP ( $f=-c\T x$ ) this is exactly the active-normal picture of Chapter 5: $-\nabla f=c$ must lie in the cone of tight normals.

I understand this unit

Unit 7.1 · Gradient descent

Why step in the negative-gradient direction?

Sources: L12 §4.1; Lec12_secB p.4 (angle α, cos)

Near $x$ a smooth function looks like its tangent plane. Among all short steps, which one lowers the tangent prediction most? The answer is: straight against the gradient.

Step 1: the predicted change of a small step

f(x+h)=f(x)+\langle\nabla f(x),h\rangle+o(\norm h).

In wordsFor a short step $h$ , the change in $f$ is essentially $\langle\nabla f(x),h\rangle$ . To decrease $f$ as fast as possible, make this inner product as negative as possible.

Symbol by symbol

$\langle\nabla f(x),h\rangle$	first-order (linear) prediction of the change
$o(\norm h)$	error, negligible compared with $\norm h$ for small steps

Step 2: the angle picture (board)

-1\;\le\;\cos\alpha=\frac{\langle v,w\rangle}{\norm v\,\norm w}\;\le\;1\qquad\Longrightarrow\qquad\langle v,w\rangle\;\ge\;-\norm v\,\norm w.

In wordsA dot product between two vectors can be as low as minus the product of their sizes, and no lower. It reaches that value exactly when the vectors point in opposite directions ( $\alpha=180^\circ$ ).

Symbol by symbol

$\alpha$	the angle between $v$ and $w$
$\cos\alpha=-1$	opposite directions; the most negative possible inner product

Why it is trueThis is Cauchy–Schwarz (see the toolkit).

Step 3: steepest descent

\langle\nabla f(x),h\rangle\;\ge\;-\norm{\nabla f(x)}\,\norm h\;\ge\;-\rho\,\norm{\nabla f(x)}\qquad\text{for all } \norm h\le\rho,

In wordsWith step length at most $\rho$ , the predicted decrease can never exceed $\rho\norm{\nabla f(x)}$ . It reaches that bound exactly at $h=-\rho\,\nabla f(x)/\norm{\nabla f(x)}$ , pointing straight against the gradient.

Symbol by symbol

$\rho$	allowed step length (a radius)
$\nabla f(x)/\norm{\nabla f(x)}$	unit vector in the gradient direction

Why it is trueCauchy–Schwarz with $v=\nabla f(x),\ w=h$ , then $\norm h\le\rho$ . Equality needs $\cos\alpha=-1$ and $\norm h=\rho$ .

When you use itThere are many directions to move: pick the best one by minimizing this. $-\nabla f$ is the steepest first-order descent direction in Euclidean distance.

I understand this unit

Unit 7.2 · Gradient descent

The algorithm and what the step size does

Sources: L12 §4; Lec12_secB p.4 ("Init x₀, Repeat")

Gradient descent (unconstrained, K = ℝᵈ)

x_{t+1}=x_t-\eta\,\nabla f(x_t),\qquad t=0,1,2,\dots

In wordsStart at $x_0$ . Repeatedly compute the slope where you stand and take a step of size $\eta$ times the slope, downhill.

Symbol by symbol

$x_t$	the iterate (current point) after $t$ steps
$\eta>0$	the step size (learning rate), constant in the L12 theorem
$\nabla f(x_t)$	one oracle call per step

When you use itEvery move goes toward something smaller. How fast? That is what the theorem in unit 7.3 answers.

One dimension: $f(x)=x^2/2$

f'(x)=x\quad\Longrightarrow\quad x_{t+1}=x_t-\eta x_t=(1-\eta)\,x_t\quad\Longrightarrow\quad x_t=(1-\eta)^t\,x_0.

In wordsEach step multiplies the position by the same factor $1-\eta$ . Everything depends on the size and sign of that factor.

Step size	factor $1-\eta$	Behaviour from $x_0\ne0$
$0<\eta<1$	in $(0,1)$	converges, same side ( $\eta=\tfrac12$ : $x_t=2^{-t}x_0$ )
$\eta=1$	$0$	reaches the optimum in one step
$1<\eta<2$	in $(-1,0)$	alternates sides but converges
$\eta=2$	$-1$	$x_t=(-1)^tx_0$ : bounces forever, never improves
$\eta>2$	$\|1-\eta\|>1$	$\|x_t\|$ grows: diverges

Two dimensions: why the zig-zag happens

On a stretched bowl $f(x)=\tfrac12(x_1^2+\kappa x_2^2)$ each coordinate has its own factor: $x_1\gets(1-\eta)x_1$ and $x_2\gets(1-\eta\kappa)x_2$ . Stability needs $\eta<2/\kappa$ for the steep direction, but then the shallow direction shrinks by only $1-\eta$ per step. A badly stretched bowl (large $\kappa$ ) makes gradient descent slow. This is the motivation for the smoothness analysis of L13 (Chapter 8) and for strong convexity.

I understand this unit

Unit 7.3 · Gradient descent

The convergence theorem: statement decoded

Sources: L12 §5; Lec12_secB pp.4–5

Theorem

Gradient descent with bounded gradients

Let $f:\R^d\to\R$ be differentiable and convex with a global minimizer $x^*$ . Assume

\norm{x_0-x^*}\le D,\qquad\norm{\nabla f(x_t)}\le G\ \ \text{at every iterate used } (t=0,\dots,T-1).

Run $T$ steps with one fixed step size $\eta>0$ and return the average of the queried points $\bar x_T=\frac1T\sum_{t=0}^{T-1}x_t$ . Then

f(\bar x_T)-f(x^*)\;\le\;\frac{D^2}{2\eta T}+\frac{\eta G^2}{2}.

With $\eta=\dfrac{D}{G\sqrt T}$ : $\quad f(\bar x_T)-f(x^*)\le\dfrac{DG}{\sqrt T}$ . So $T\ge(DG/\eps)^2$ iterations suffice for additive error $\eps$ .

Every symbol in the theorem

\underbrace{f(\bar x_T)-f(x^*)}_{\text{error of the output}}\;\le\;\underbrace{\frac{D^2}{2\eta T}}_{\text{``start far away'' term}}\;+\;\underbrace{\frac{\eta G^2}{2}}_{\text{``discrete step'' penalty}}

Symbol by symbol

$D$	a known bound on the starting distance to an optimizer ("you don't start from a far-away point"). Not the diameter of a domain.
$G$	a known bound on the gradient length at the iterates: how steep the function can be
$T$	number of gradient steps (= oracle calls), fixed in advance
$\eta$	the constant step size
$\bar x_T$	average of $x_0,x_1,\dots,x_{T-1}$ : the points where gradients were evaluated (not $x_1..x_T$ )
first term	shrinks as $T$ grows (more steps); large when $\eta$ is tiny (slow progress)
second term	does not shrink with $T$ ; large when $\eta$ is big (overshooting)
$DG/\sqrt T$	the balanced bound; halving the error needs 4× the iterations

Why it is trueProved in the next three units: expand one step, telescope, average.

When you use itExam computations: given $D,G,T$ , find $\eta$ and the error. Given $\eps$ , find $T$ .

I understand this unit

Unit 7.4 · Gradient descent

Proof step 1: one update, expanded

Sources: L12 §5.1–5.2; Lec12_secB p.5

We cannot compute $x^*$ , but the analysis can use it. Track the squared distance to the optimizer, sometimes called a potential.

The potential

R_t=\norm{x_t-x^*}^2,\qquad g_t=\nabla f(x_t).

Symbol by symbol

$R_t$	squared distance from the current iterate to the optimizer; $R_0\le D^2$ , and always $R_t\ge0$
$g_t$	the gradient used at step $t$ ; $\norm{g_t}\le G$

Expand one update

R_{t+1}=\norm{x_t-\eta g_t-x^*}^2=\underbrace{\norm{x_t-x^*}^2}_{R_t}\;-\;2\eta\,\langle g_t,\,x_t-x^*\rangle\;+\;\eta^2\norm{g_t}^2.

In wordsNew distance² = old distance² − (a "progress" term) + (an "overshoot" term).

Symbol by symbol

$x_{t+1}-x^=(x_t-x^)-\eta g_t$	substitute the update rule
expansion	$\norm{a-b}^2=\norm a^2-2\langle a,b\rangle+\norm b^2$ with $a=x_t-x^*$ , $b=\eta g_t$
$-2\eta\langle g_t,x_t-x^*\rangle$	progress: positive inner product means the step points toward $x^*$ "on average"
$\eta^2\norm{g_t}^2$	overshoot: the squared length of the step, always ≥ 0

Apply the two assumptions

R_{t+1}\;\le\;R_t-2\eta\big(f(x_t)-f(x^*)\big)+\eta^2G^2.

In wordsConvexity says the progress term is at least the objective error. Bounded gradients cap the overshoot term.

Symbol by symbol

convexity	$\langle g_t,x_t-x^\rangle\ge f(x_t)-f(x^)$ (the key inequality). Multiplying by $-2\eta<0$ flips it: $-2\eta\langle g_t,x_t-x^\rangle\le-2\eta(f(x_t)-f(x^))$
gradient bound	$\norm{g_t}^2\le G^2$

Target one-step inequality (rearranged)

f(x_t)-f(x^*)\;\le\;\frac{R_t-R_{t+1}}{2\eta}+\frac{\eta G^2}{2}.

In wordsThe error at step $t$ is paid for by how much the distance to $x^*$ shrank, plus a fixed penalty for taking discrete steps.

Why it is trueMove $2\eta(f(x_t)-f(x^*))$ to the left and $R_{t+1}$ to the right, then divide by $2\eta>0$ .

I understand this unit

Unit 7.5 · Gradient descent

Proof steps 2–3: telescope, then average

Sources: L12 §5.3; Lec12_secB p.6

Sum the one-step inequalities over t = 0,…,T−1

\sum_{t=0}^{T-1}\big(f(x_t)-f(x^*)\big)\;\le\;\frac1{2\eta}\sum_{t=0}^{T-1}(R_t-R_{t+1})+\frac{\eta G^2T}{2}\;=\;\frac{R_0-R_T}{2\eta}+\frac{\eta G^2T}{2}.

In wordsAdding up, the distance terms cancel in pairs ("telescoping"): $(R_0-R_1)+(R_1-R_2)+\dots+(R_{T-1}-R_T)=R_0-R_T$ .

Symbol by symbol

$\frac{\eta G^2}{2}$ summed $T$ times	$\frac{\eta G^2T}{2}$
$R_0\le D^2$	the starting-distance assumption
$R_T\ge0$	a squared distance; dropping $-R_T$ can only increase the right side

Bound the total, then divide by T

\sum_{t=0}^{T-1}\big(f(x_t)-f(x^*)\big)\le\frac{D^2}{2\eta}+\frac{\eta G^2T}{2}\qquad\Longrightarrow\qquad\frac1T\sum_{t=0}^{T-1}f(x_t)-f(x^*)\le\frac{D^2}{2\eta T}+\frac{\eta G^2}{2}.

In wordsThe average value at the queried points is within the bound.

Step 3: average value → value at the average point (Jensen)

f\Big(\frac1T\sum_{t=0}^{T-1}x_t\Big)\;\le\;\frac1T\sum_{t=0}^{T-1}f(x_t).

In wordsFor a convex function, the value at the average point is at most the average of the values. This is the many-point version of the chord inequality.

Why it is trueInduction on $T$ . For $T=1$ it is trivial. For $T$ points: $\bar x_T=\frac{T-1}{T}\bar x_{T-1}+\frac1Tx_{T-1}$ , a two-point blend with weights $\frac{T-1}T,\frac1T$ . Apply the chord inequality, then the induction hypothesis to $f(\bar x_{T-1})$ . The same induction shows the average of points in a convex set stays in the set (L12 exercise).

When you use itCombine with the previous display: $f(\bar x_T)-f(x^*)\le\frac{D^2}{2\eta T}+\frac{\eta G^2}2$ . ∎

I understand this unit

Unit 7.6 · Gradient descent

Choosing η: balance the two error terms

Sources: L12 §5.4 + exercises

Balancing

\frac{D^2}{2\eta T}=\frac{\eta G^2}{2}\iff\eta^2=\frac{D^2}{G^2T}\iff\eta=\frac{D}{G\sqrt T},\qquad\text{each term}=\frac{DG}{2\sqrt T},\ \ \text{sum}=\frac{DG}{\sqrt T}.

In wordsA tiny step barely overshoots but makes slow progress. A big step makes fast progress but overshoots a lot. The best constant step makes the two costs equal.

Why it is trueCalculus agrees: $\frac{d}{d\eta}\big(\frac{D^2}{2\eta T}+\frac{\eta G^2}2\big)=-\frac{D^2}{2\eta^2T}+\frac{G^2}2=0$ at the same $\eta$ . The sum $a/\eta+b\eta$ is minimized where its two terms are equal.

Iterations for accuracy ε

\frac{DG}{\sqrt T}\le\eps\iff T\ge\Big(\frac{DG}{\eps}\Big)^2.

In wordsError decreases like $1/\sqrt T$ : 10× more accuracy costs 100× more iterations.

L12 exercise:

D=2,\ G=3,\ T=900

. Find the prescribed step size and the guaranteed additive error. How large must

T

be for

\eps=0.1

?

Show answer

\sqrt T=30

.

\eta=\frac{D}{G\sqrt T}=\frac{2}{3\cdot30}=\frac1{45}\approx0.0222

. Error

\le\frac{DG}{\sqrt T}=\frac{6}{30}=0.2

. Check:

\frac{D^2}{2\eta T}=\frac{4}{2\cdot\frac1{45}\cdot900}=\frac{4}{40}=0.1

and

\frac{\eta G^2}2=\frac{9}{90}=0.1

. For

\eps=0.1

:

T\ge(6/0.1)^2=3600

, with

\eta=\frac{2}{3\cdot60}=\frac1{90}

.

I understand this unit

Unit 7.7 · Gradient descent

Worked trajectories you should be able to reproduce

Sources: L12 §6 exercises; added least-squares example

Least squares in one variable

$f(x)=\tfrac52(x-1)^2$ (from $A=b=(1,2)\T$ ), $f'(x)=5(x-1)$ , $x^*=1$ . Start at $x_0=0$ with $\eta=0.1$ :

x_{t+1}=x_t-0.1\cdot5(x_t-1)=0.5x_t+0.5.

$t$	$x_t$	gradient $5(x_t-1)$	$f(x_t)$	$R_t=(x_t-1)^2$
0	0	−5	2.5	1
1	0.5	−2.5	0.625	0.25
2	0.75	−1.25	0.15625	0.0625
3	0.875	−0.625	0.0390625	0.015625

For $T=4$ : $\bar x_4=(0+.5+.75+.875)/4=0.53125$ , and $f(\bar x_4)=2.5\cdot0.46875^2\approx0.5493$ . The average of the four values is $3.3203/4\approx0.8301$ . Jensen says $0.5493\le0.8301$ . ✓

The theorem with $D=1$ , $G=5$ (valid along this trajectory, since $|f'|\le5$ there), $\eta=0.1$ , $T=4$ : $\frac{1}{2\cdot0.1\cdot4}+\frac{0.1\cdot25}{2}=1.25+1.25=2.5$ . That is valid but loose: the actual error is about 0.55. The generic theorem ignores the extra quadratic structure.

L12 exercise: $f(x)=x^2/2$ , $\eta=\tfrac12$ . Check the potential directly

$g_t=x_t$ , $x^*=0$ , $x_{t+1}=x_t/2$ , $R_t=x_t^2$ . Exact expansion:

R_{t+1}=R_t-2\cdot\tfrac12\cdot x_t^2+\tfrac14x_t^2=R_t-R_t+\tfrac14R_t=\tfrac14R_t.

Generic proof: the convexity step replaces the true error $f(x_t)-0=R_t/2$ by the inner product $\langle g_t,x_t-x^*\rangle=R_t$ , twice as large. Using only that inequality would give $R_{t+1}\le R_t-2\cdot\tfrac12\cdot\tfrac{R_t}2+\tfrac14R_t=\tfrac34R_t$ instead of the exact $\tfrac14R_t$ .

Which inequalities in the general proof lose information specific to this quadratic?

Show answer

(1) The convexity inequality

f(x_t)-f(x^*)\le\langle g_t,x_t-x^*\rangle

is off by a factor 2 here (

R_t/2

vs

R_t

). (2) Replacing

\norm{g_t}^2=x_t^2

, which shrinks geometrically, by a uniform

G^2

. (3) Dropping

-R_T\le0

. (4) Averaging: Jensen's

f(\bar x)\le\frac1T\sum f(x_t)

and averaging in the early, bad iterates. Together they turn a geometric rate (

R_t=4^{-t}R_0

) into

1/\sqrt T

. With

x_0=2

:

x_t=2\cdot2^{-t}

,

R_t=4\cdot4^{-t}

, error

=2\cdot4^{-t}

.

I understand this unit

Unit 7.8 · Gradient descent

Scope, caveats, and what comes next

Sources: L12 §6

Additive, not multiplicative

The guarantee is $f(x)-f(x^*)\le\eps$ . A ratio $f(x)/f(x^*)$ can be undefined ( $f(x^*)=0$ ) or misleading ( $f(x^*)<0$ ). The approximation algorithms of Chapter 9 do the opposite: for discrete problems with positive costs they guarantee a ratio, $\text{ALG}\le\alpha\cdot\opt$ .

Count the work per iteration

The theorem counts gradient-oracle calls ( $T$ ). Total time also includes the cost of each gradient and the vector arithmetic. Dense least squares costs $O(md)$ per gradient plus $O(d)$ for the update and running average, so $O(Tmd)$ in total.

The bounds are real assumptions

Convexity alone gives neither $D$ nor $G$ . It is enough to bound gradients at the iterates actually visited, but that bound has to be justified for the problem and the step size (as on the shrinking least-squares trajectory above).

Nonsmooth functions: subgradients (brief extension)

Subgradient

g \text{ is a subgradient of } f \text{ at } x\iff f(y)\ge f(x)+\langle g,y-x\rangle\ \ \forall y.

In wordsAny slope whose tangent line stays below the graph. At a kink there are many. Where $f$ is differentiable, the only one is $\nabla f(x)$ .

Symbol by symbol

$\|x\|$ at $x>0$	$g=1$
$\|x\|$ at $x<0$	$g=-1$
$\|x\|$ at $x=0$	any $g\in[-1,1]$

When you use itReplace $\nabla f(x_t)$ by any subgradient $g_t$ with $\norm{g_t}\le G$ . The proof only used the tangent inequality, so it goes through unchanged. A subgradient step may not decrease $f$ at every step, but the averaged guarantee still holds.

What comes next (L13 covers the first two: see Chapter 8)

Idea	Why it is introduced	Typical gain
Projection	A gradient step may leave a constrained $K$ . Project back to the nearest point of $K$ . Projection does not increase the distance to $x^*\in K$ , so the analysis survives.	constrained problems
Smoothness (gradient changes slowly)	An upper bound on curvature allows larger, safer steps.	$O(1/T)$ instead of $O(1/\sqrt T)$
Strong convexity (curvature bounded below)	A lower curvature bound gives extra progress for free; together with smoothness it forces geometric progress (as in $x^2/2$ ).	$O(\log T/T)$ with bounded gradients; geometric with smoothness

I understand this unit

Unit 8.1 · Projections and smoothness (L13)

Lecture 13 in one page: two upgrades to gradient descent

Sources: Lec13_SecA pp.1, 7

Lecture 12 proved one guarantee: with convexity, a start-distance bound $D$ and a gradient bound $G$ , the average iterate is within $DG/\sqrt T$ of optimal. Lecture 13 makes two upgrades to it.

Upgrade 1 · Constraints

A gradient step can "knock you out of the domain" $K$ . Project back to the nearest point of $K$ . This never moves you farther from $x^*$ , so the whole L12 proof still works.

Upgrade 2 · Speed

If the gradient changes slowly (β-smooth), a step of size $1/\beta$ always decreases $f$ . Then the last iterate satisfies $f(x_T)-f^*\le\beta D^2/(2T)$ , which is $O(1/\eps)$ steps instead of $O(1/\eps^2)$ .

The recap the lecture started from

The one identity behind every GD proof

R_{t+1}=R_t-2\eta\,\langle\nabla f(x_t),\,x_t-x^*\rangle+\eta^2\norm{\nabla f(x_t)}^2,\qquad R_t=\norm{x_t-x^*}^2.

In wordsNew squared distance to the optimum = old one − a "progress" term + an "overshoot" term. Both L13 results start from this line.

When you use itProjected GD: projecting only makes the left side smaller. Smooth GD: rearrange it as $R_t-R_{t+1}=2\eta\langle\cdot\rangle-\eta^2\norm{\cdot}^2$ and combine it with the descent lemma.

Where we end up (the board's closing table)

Assumptions	Output	Step size	Error after $T$ steps	# steps for error $\eps$
convex, $D$ , $G$ (bounded gradients)	average $\bar x_T=\frac1T\sum_{t<T}x_t$	$\eta=\frac{D}{G\sqrt T}$	$\frac{DG}{\sqrt T}$	$\big(\frac{DG}{\eps}\big)^2=O(\eps^{-2})$
convex, $D$ , $\beta$ -smooth	last iterate $x_T$	$\eta=\frac1\beta$	$\frac{\beta D^2}{2T}$	$\frac{\beta D^2}{2\eps}=O(\eps^{-1})$

I understand this unit

Unit 8.2 · Projections and smoothness (L13)

Projection onto a convex set

Sources: Lec13_SecA pp.1–2

Constrained problem: $\min_{x\in K}f(x)$ . A plain step $x_t-\eta\nabla f(x_t)$ may land outside $K$ . How do we recover? Move to the closest point of $K$ .

Definition: projection

\Pi_K(u)\;=\;\arg\min_{z\in K}\ \norm{u-z}^2

In wordsThe projection of $u$ onto $K$ is the point of $K$ nearest to $u$ . If $u$ is already in $K$ , it is $u$ itself.

Symbol by symbol

$K$	the feasible set: convex and compact (closed and bounded) in the lecture. Closed + nonempty is enough for existence.
$u\in\R^d$	any point, typically the unconstrained gradient step
$\Pi_K(u)$	the nearest point. It exists because $K$ is closed and is unique because $K$ is convex.
$\norm{u-z}^2$	squared distance; same minimizer as the distance itself, but easier to differentiate

When you use itProjected gradient descent: $x_{t+1}=\Pi_K\big(x_t-\eta\nabla f(x_t)\big)$ . The method is practical only when $\Pi_K$ is easy to compute, as in the examples below.

Projections you can compute in one line

Box (the lecture example)

K=\prod_{i=1}^{d}[a_i,b_i]\quad\Longrightarrow\quad \Pi_K(u)_i=\min\{\,b_i,\ \max\{a_i,u_i\}\,\}.

In wordsClip every coordinate into its interval independently: too small goes up to $a_i$ , too large comes down to $b_i$ , and in-range values stay put.

Symbol by symbol

$\prod_i[a_i,b_i]$	the box $\{z: a_i\le z_i\le b_i\ \forall i\}$ (a product of intervals)
$\max\{a_i,u_i\}$	push $u_i$ up to at least $a_i$
$\min\{b_i,\cdot\}$	then pull it down to at most $b_i$

Why it is true $\norm{u-z}^2=\sum_i(u_i-z_i)^2$ is a sum of separate 1-D terms, and each $z_i$ has its own interval. So you minimize each term on its own, and the closest point of $[a_i,b_i]$ to $u_i$ is the clipped value.

Set $K$	$\Pi_K(u)$
box $\prod[a_i,b_i]$	clip each coordinate
ball $\{z:\norm z\le r\}$	$u$ if $\norm u\le r$ , else $r\,u/\norm u$ (shrink radially)
halfspace $\{z:a\T z\le d\}$	$u-\frac{\max\{0,\,a\T u-d\}}{\norm a^2}\,a$ (move straight back along the normal)
nonnegative orthant $\{z\ge0\}$	$\max\{0,u_i\}$ coordinatewise (a box with $b_i=\infty$ )

I understand this unit

Unit 8.3 · Projections and smoothness (L13)

The projection inequality: projecting brings you closer to everything in K

Sources: Lec13_SecA pp.2–3

Decoding

\underbrace{\norm{p-z}^2}_{\text{projected point to }z}\;+\;\underbrace{\norm{u-p}^2}_{\text{how far we moved}}\;\le\;\underbrace{\norm{u-z}^2}_{\text{original point to }z}

In wordsThe distance from $p$ to $z$ is smaller than the distance from $u$ to $z$ , for every point $z$ of $K$ . In fact it is smaller by at least the length of the projection move. It reads like Pythagoras with "≤" because the angle at $p$ is at least 90°.

Symbol by symbol

$u$	the point outside (or anywhere)
$p=\Pi_K(u)$	its nearest point in $K$
$z$	any point of $K$ ; in GD we take $z=x^*$
second $\le$	just drops $-\norm{u-p}^2\le0$

Proof (board version, with every step justified)

Move from $p$ toward $z$ . For $\theta\in[0,1]$ the point $p+\theta(z-p)$ is in $K$ , since it lies on the segment between two points of the convex set. Define $f(\theta)=\norm{u-p-\theta(z-p)}^2=\text{squared distance from }u\text{ to that point}.$
It is minimized at $\theta=0$ , because $p$ is the closest point of $K$ to $u$ . So moving right from 0 cannot decrease it: $f'(0^+)\ge0$ (it is increasing).
Differentiate: by the chain rule $f'(\theta)=2\langle u-p-\theta(z-p),\ p-z\rangle$ . At $\theta=0$ : $\langle u-p,\ p-z\rangle\;\ge\;0\qquad\Longleftrightarrow\qquad\langle u-p,\ z-p\rangle\le0.$ This says the angle at $p$ between "back to $u$ " and "toward $z$ " is at least 90°.
Expand (the trick: add and subtract $p$ ): $\norm{u-z}^2=\norm{(u-p)+(p-z)}^2=\norm{u-p}^2+\norm{p-z}^2+2\langle u-p,\ p-z\rangle\;\ge\;\norm{u-p}^2+\norm{p-z}^2.$ The cross term is ≥ 0 by step 3. ∎

I understand this unit

Unit 8.4 · Projections and smoothness (L13)

Projected gradient descent: "went out? just project!"

Sources: Lec13_SecA p.3

Projected gradient descent

y_{t+1}=x_t-\eta\nabla f(x_t),\qquad x_{t+1}=\Pi_K(y_{t+1}).

In wordsTake the ordinary gradient step, which may leave $K$ , then snap back to the nearest feasible point.

Symbol by symbol

$y_{t+1}$	the unconstrained step (the board calls it $x_{t+1}$ before projecting)
$x_{t+1}\in K$	every iterate is feasible

The one new line in the proof

R_{t+1}=\norm{\Pi_K(y_{t+1})-x^*}^2\;\le\;\norm{y_{t+1}-x^*}^2=R_t-2\eta\langle\nabla f(x_t),x_t-x^*\rangle+\eta^2\norm{\nabla f(x_t)}^2.

In wordsProjecting can only bring you closer to $x^*$ . So the potential after projecting is at most what the L12 calculation already bounded.

Symbol by symbol

$\le$	projection inequality with $u=y_{t+1}$ , $p=\Pi_K(y_{t+1})$ , $z=x^*$ (the board labels these p, u, z)
$x^*\in K$	required. Here $x^$ is a minimizer over $K$* , so it is a legal $z$ .
equality	the unconstrained expansion from L12, since $y_{t+1}-x^=(x_t-x^)-\eta\nabla f(x_t)$

Why everything else carries over: the convexity step $\langle\nabla f(x_t),x_t-x^*\rangle\ge f(x_t)-f(x^*)$ holds for any $x_t$ . Telescoping is unchanged. And the average of points of $K$ is in $K$ (convexity of $K$ , L12 exercise), so the output is feasible.

I understand this unit

Unit 8.5 · Projections and smoothness (L13)

β-smoothness: the gradient cannot change too fast

Sources: Lec13_SecA pp.3–4

Definition: β-smooth

\norm{\nabla f(x)-\nabla f(y)}\;\le\;\beta\,\norm{x-y}\qquad\forall x,y\in\R^d.

In wordsThe gradient is β-Lipschitz: moving a distance $r$ changes the gradient by at most $\beta r$ . The slope can't jump, and the curvature is at most $\beta$ .

Symbol by symbol

$\beta>0$	the smoothness constant, an upper bound on curvature
$\norm{\nabla f(x)-\nabla f(y)}$	how much the slope vector changes between two points

Why it is trueFor twice-differentiable $f$ this is equivalent to $-\beta I\preceq\nabla^2 f(x)\preceq\beta I$ : every directional second derivative is between $-\beta$ and $\beta$ . In 1-D, $|f''(x)|\le\beta$ .

When you use itSmoothness is not about convexity but about how the gradient behaves: it is an upper curvature bound. Convexity is a lower one (curvature ≥ 0). The L13 theorem uses both.

$f$	β-smooth?	bounded gradient (G)?
$\tfrac12x^2$	yes, $\beta=1$	no on $\R$ ( $f'=x$ )
$\tfrac12x\T Qx$ , $Q\succeq0$	yes, $\beta=\lambda_{\max}(Q)$	no on $\R^d$
$\tfrac12\norm{Ax-b}^2$	yes, $\beta=\lambda_{\max}(A\T A)$	no on $\R^d$
$\|x\|$	no: slope jumps from −1 to 1	yes, $G=1$
$\log(1+e^x)$ (softplus)	yes, $\beta=\tfrac14$	yes, $G=1$
$x^4$	no ( $f''=12x^2$ unbounded)	no

I understand this unit

Unit 8.6 · Projections and smoothness (L13)

The descent lemma: a quadratic ceiling (and what s is)

Sources: Lec13_SecA p.4

Decoding (★)

\underbrace{f(y)}_{\text{true value}}\;\le\;\underbrace{f(x)+\langle\nabla f(x),y-x\rangle}_{\text{tangent at }x}\;+\;\underbrace{\tfrac\beta2\norm{y-x}^2}_{\text{curvature allowance}}

In wordsThe function never rises above the tangent plus a bowl of curvature $\beta$ . It is a quadratic ceiling touching $f$ at $x$ .

Symbol by symbol

tangent part	the first-order Taylor prediction, as in L12
$\frac\beta2\norm{y-x}^2$	the most the function can bend upward away from its tangent, given curvature ≤ β
no convexity needed	the descent lemma uses only β-smoothness

When you use itCombined with convexity (tangent = floor), smooth convex functions are sandwiched: $f(x)+\langle\nabla f(x),y-x\rangle\le f(y)\le f(x)+\langle\nabla f(x),y-x\rangle+\frac\beta2\norm{y-x}^2$ .

Proof, step by step

Picture it

What is s, and why is it there?

$s$ is a position along the straight segment from $x$ to $y$ . The point $x+s(y-x)$ is $x$ when $s=0$ , $y$ when $s=1$ , and the midpoint when $s=\tfrac12$ . We introduce it to reduce a $d$ -dimensional question to a 1-D function, where calculus is easy:

g(s)=f\big(x+s(y-x)\big),\qquad g(0)=f(x),\quad g(1)=f(y),\quad g'(s)=\big\langle\nabla f(x+s(y-x)),\,y-x\big\rangle.

(The chain rule: the inner point moves with velocity $y-x$ .) Then the fundamental theorem of calculus ("total change = integral of the rate of change") gives

f(y)-f(x)=g(1)-g(0)=\int_0^1 g'(s)\,ds=\int_0^1\big\langle\nabla f(x+s(y-x)),\,y-x\big\rangle\,ds.

Subtract the tangent term. $\langle\nabla f(x),y-x\rangle$ is a constant, so it equals its own integral over $[0,1]$ : $f(y)-f(x)-\langle\nabla f(x),y-x\rangle=\int_0^1\big\langle\nabla f(x+s(y-x))-\nabla f(x),\ y-x\big\rangle\,ds.$ The integrand compares the slope at the moving point with the slope at the start.
Bound the integrand (the two factors explained): $\big\langle\nabla f(x+s(y-x))-\nabla f(x),\ y-x\big\rangle\;\overset{\text{C–S}}{\le}\;\underbrace{\norm{\nabla f(x+s(y-x))-\nabla f(x)}}_{\le\ \beta\norm{s(y-x)}\ =\ \beta s\norm{y-x}}\cdot\underbrace{\norm{y-x}}_{\text{second factor}}.$
- First factor, $\beta s\norm{y-x}$ : the two points $x+s(y-x)$ and $x$ are a distance $\norm{s(y-x)}=s\norm{y-x}$ apart ( $s\ge0$ ). β-smoothness says their gradients differ by at most $\beta$ times that distance.
- Second factor, $\norm{y-x}$ : this is the other vector in the inner product. Cauchy–Schwarz says $\langle a,b\rangle\le\norm a\,\norm b$ , with $a=$ gradient difference and $b=y-x$ .
Integrate: $\displaystyle\int_0^1\beta s\norm{y-x}^2\,ds=\beta\norm{y-x}^2\int_0^1 s\,ds=\beta\norm{y-x}^2\cdot\tfrac12$ . ∎

I understand this unit

Unit 8.7 · Projections and smoothness (L13)

The safe step η = 1/β: guaranteed decrease every time

Sources: Lec13_SecA pp.4–5

Put the gradient step into the descent lemma: $x=x_t$ , $y=x_{t+1}=x_t-\eta\nabla f(x_t)$ , so $y-x=-\eta\nabla f(x_t)$ . Write $g=\nabla f(x_t)$ .

One step, any η

f(x_{t+1})\;\le\;f(x_t)+\langle g,-\eta g\rangle+\frac\beta2\norm{\eta g}^2\;=\;f(x_t)-\eta\Big(1-\frac{\beta\eta}{2}\Big)\norm{g}^2.

In wordsThe tangent predicts a drop of $\eta\norm g^2$ . The curvature can eat back at most $\frac{\beta\eta^2}2\norm g^2$ . The net guaranteed drop is positive whenever $0<\eta<2/\beta$ .

Symbol by symbol

$\langle g,-\eta g\rangle=-\eta\norm g^2$	the first-order decrease
$\frac\beta2\eta^2\norm g^2$	the overshoot allowance
$\eta(1-\beta\eta/2)$	largest at $\eta=1/\beta$ , where it equals $\frac1{2\beta}$

The safe step (board)

\eta=\frac1\beta\quad\Longrightarrow\quad f(x_{t+1})\;\le\;f(x_t)-\frac1\beta\norm{g}^2+\frac1{2\beta}\norm g^2\;=\;f(x_t)-\frac1{2\beta}\norm{\nabla f(x_t)}^2.

In wordsWith $\eta=1/\beta$ , every step lowers $f$ by at least $\norm{\nabla f}^2/(2\beta)$ . Steep spots give big guaranteed progress. Progress only stalls where the gradient is (nearly) zero.

Why it is truePicture: the step $x_t-\frac1\beta\nabla f(x_t)$ is exactly the bottom of the quadratic ceiling $(\star)$ . The function lies below the ceiling, and the ceiling's minimum is $\frac1{2\beta}\norm g^2$ below $f(x_t)$ .

When you use itMakes $f(x_0)\ge f(x_1)\ge f(x_2)\ge\dots$ (monotone). That is why the smooth theorem can return the last iterate.

I understand this unit

Unit 8.8 · Projections and smoothness (L13)

All combined: f(x_T) − f* ≤ βD²/(2T)

Sources: Lec13_SecA pp.5–7

Proof in four steps

Step 1: the distance identity with η = 1/β

R_t-R_{t+1}=2\eta\langle g_t,x_t-x^*\rangle-\eta^2\norm{g_t}^2\quad\overset{\eta=1/\beta}{\Longrightarrow}\quad\frac\beta2\,(R_t-R_{t+1})=\langle g_t,x_t-x^*\rangle-\frac1{2\beta}\norm{g_t}^2.

In wordsRearrange the usual expansion and multiply by $\beta/2$ (the board's boxed line).

Symbol by symbol

$g_t=\nabla f(x_t)$	the gradient at the current point (not at $x^*$ )
$R_t=\norm{x_t-x^*}^2$	squared distance, as always

Step 2: descent lemma, then convexity

\begin{aligned} f(x_{t+1})-f(x^*)\;&\overset{\text{safe step}}{\le}\;f(x_t)-f(x^*)-\frac1{2\beta}\norm{g_t}^2\\ &\overset{\text{convexity}}{\le}\;\langle g_t,x_t-x^*\rangle-\frac1{2\beta}\norm{g_t}^2\\ &\overset{\text{Step 1}}{=}\;\frac\beta2(R_t-R_{t+1}). \end{aligned}

In wordsThe error of the next point is paid for by the decrease in squared distance. Unlike L12, there is no leftover $\eta G^2/2$ penalty: smoothness cancelled it exactly.

Symbol by symbol

1st $\le$	safe-step inequality with $f(x^*)$ subtracted from both sides
2nd $\le$	the L12 key inequality $f(x_t)-f(x^)\le\langle g_t,x_t-x^\rangle$ (red "using convexity!")

Step 3: add both sides (telescope)

\sum_{t=0}^{T-1}\big(f(x_{t+1})-f(x^*)\big)\;\le\;\frac\beta2\,(R_0-R_T)\;\le\;\frac\beta2R_0\;\le\;\frac{\beta D^2}{2}.

Symbol by symbol

telescoping	$\sum_{t=0}^{T-1}(R_t-R_{t+1})=R_0-R_T$
$R_T\ge0$ , $R_0\le D^2$	as in L12

Step 4: the last term is the smallest

T\cdot\big(f(x_T)-f(x^*)\big)\;\le\;\sum_{t=1}^{T}\big(f(x_t)-f(x^*)\big)\;\le\;\frac{\beta D^2}{2}\quad\Longrightarrow\quad f(x_T)-f(x^*)\le\frac{\beta D^2}{2T}.

In words"The LHS is bigger than $T\cdot(f(x_T)-f(x^*))$ " (board, red). The sum has $T$ terms and the last one is the smallest, because the safe step makes $f(x_1)\ge f(x_2)\ge\dots\ge f(x_T)$ .

Why it is trueA sum of $T$ numbers is at least $T$ times its smallest number. This is the only place the monotone decrease is used, and it is what lets us return $x_T$ instead of an average.

Worked example

Worked example: a stretched bowl

$f(x)=\tfrac12(x_1^2+4x_2^2)$ has Hessian $\mathrm{diag}(1,4)$ , so $\beta=4$ , and $x^*=0$ . Start at $x_0=(2,1)$ : $D=\sqrt5$ , $f(x_0)=4$ . With $\eta=\tfrac14$ : $x_1\gets\tfrac34x_1$ and $x_2\gets(1-1)x_2=0$ . So $x_t=(2\cdot0.75^t,0)$ for $t\ge1$ , and $f(x_t)=2\cdot0.5625^t$ .

$T$	actual $f(x_T)$	bound $\beta D^2/(2T)=10/T$
1	1.125	10
4	0.200	2.5
10	0.0063	1

The bound is valid but loose. This function is also strongly convex (curvature ≥ 1), which gives the geometric rate you see. That is the next refinement (unit 8.10) and is not part of the L13 theorem.

I understand this unit

Unit 8.9 · Projections and smoothness (L13)

Comparing the two GD guarantees

Sources: Lec13_SecA p.7 (table)

	Bounded gradients (L12)	Smooth (L13)
Assumptions	convex, $\norm{x_0-x^*}\le D$ , $\norm{\nabla f(x_t)}\le G$	convex, $\norm{x_0-x^*}\le D$ , $\beta$ -smooth
Step size	$\eta=D/(G\sqrt T)$ (needs $T$ in advance)	$\eta=1/\beta$ (no $T$ needed)
Output	average $\bar x_T$ (or best iterate)	last iterate $x_T$
Error after $T$	$DG/\sqrt T$	$\beta D^2/(2T)$
Steps for error $\eps$	$(DG/\eps)^2=O(\eps^{-2})$	$\beta D^2/(2\eps)=O(\eps^{-1})$
Monotone decrease?	no (e.g. $\|x\|$ bounces)	yes, by $\ge\norm{\nabla f}^2/(2\beta)$ each step
Works with projection?	yes (this chapter)	yes, with a modified proof (not covered)
Typical example	$\|x\|$ , hinge losses, max of affine	least squares, softplus/logistic losses

How big is the difference?

\eps=0.01,\ D=2,\ G=3,\ \beta=3:\qquad \Big(\frac{DG}{\eps}\Big)^2=360{,}000\quad\text{vs.}\quad\frac{\beta D^2}{2\eps}=600.

In wordsSquaring $1/\eps$ is very costly. 10× more accuracy costs 100× more steps without smoothness, but only 10× with it.

I understand this unit

Unit 8.10 · Projections and smoothness (L13)

Strong convexity: curvature bounded below

Sources: L12 §6 preview; standard definition

Convexity says the graph is above its tangents. Strong convexity says it is above its tangents plus a bowl. That extra curvature is worth a lot: it forces a unique minimizer and speeds gradient descent up.

Definition: α-strongly convex

f(y)\;\ge\;f(x)+\langle\nabla f(x),\,y-x\rangle+\frac\alpha2\norm{y-x}^2\qquad\forall x,y,\qquad\alpha>0.

In wordsThe function lies above its tangent plus a parabola of curvature $\alpha$ : it curves upward at least as fast as $\tfrac\alpha2\norm{\cdot}^2$ in every direction.

Symbol by symbol

$\alpha>0$	the strong convexity constant, a lower bound on curvature
tangent part	as in the first-order condition (unit 6.3); with $\alpha=0$ this is plain convexity
$\frac\alpha2\norm{y-x}^2$	the guaranteed extra height above the tangent

When you use itMirror image of the descent lemma (unit 8.6). A function that is both α-strongly convex and β-smooth is sandwiched between two parabolas: $\frac\alpha2\norm{y-x}^2\le f(y)-f(x)-\langle\nabla f(x),y-x\rangle\le\frac\beta2\norm{y-x}^2$ , so $\alpha\le\beta$ .

Equivalent tests

Hessian: for twice-differentiable $f$ , α-strongly convex ⇔ $\nabla^2f(x)\succeq\alpha I$ for all $x$ , i.e. $v\T\nabla^2f(x)v\ge\alpha\norm v^2$ (in 1-D: $f''\ge\alpha$ ).
Subtract the bowl: $f$ is α-strongly convex ⇔ $f(x)-\frac\alpha2\norm x^2$ is convex.
Chord form: $f(\lambda x+(1-\lambda)y)\le\lambda f(x)+(1-\lambda)f(y)-\frac\alpha2\lambda(1-\lambda)\norm{x-y}^2$ (no differentiability needed).

$f$	strongly convex?
$\tfrac12x^2$	yes, $\alpha=1$
$\tfrac12x\T Qx$ , $Q\succ0$	yes, $\alpha=\lambda_{\min}(Q)$
$\tfrac12\norm{Ax-b}^2$	yes with $\alpha=\lambda_{\min}(A\T A)$ if the columns of $A$ are independent; otherwise no
$\|x\|$ , any linear function	no (zero curvature)
$e^x$ on $\R$	no: $f''=e^x\to0$ as $x\to-\infty$
$x^4$	no: $f''(0)=0$
convex $g$ + $\tfrac\alpha2\norm x^2$	yes, $\alpha$ ("regularization")

Consequences you can use in proofs

Strengthened key inequality (put y = x*)

f(x)-f(x^*)\;\le\;\langle\nabla f(x),\,x-x^*\rangle-\frac\alpha2\norm{x-x^*}^2.

In wordsThe L12 inequality "error ≤ slope · displacement" gets an extra negative term proportional to the squared distance. In a gradient-descent analysis this term is extra progress for free.

Why it is trueDefinition with $y=x^*$ : $f(x^*)\ge f(x)+\langle\nabla f(x),x^*-x\rangle+\frac\alpha2\norm{x^*-x}^2$ . Rearrange.

Quadratic growth and uniqueness

f(x)-f(x^*)\;\ge\;\frac\alpha2\norm{x-x^*}^2\qquad(\text{unconstrained minimizer }x^*).

In wordsBeing far from the optimum in distance forces being far from it in value. In particular the minimizer is unique.

Why it is trueDefinition at the point $x^*$ with $\nabla f(x^*)=0$ : $f(x)\ge f(x^*)+0+\frac\alpha2\norm{x-x^*}^2$ .

When you use itTurns a bound on the objective error into a bound on the distance $\norm{x-x^*}$ .

One step with a step size that changes over time

x_{t+1}=x_t-\eta_t\nabla f(x_t)\quad\Longrightarrow\quad R_{t+1}=R_t-2\eta_t\langle g_t,x_t-x^*\rangle+\eta_t^2\norm{g_t}^2.

In wordsThe L12 expansion does not care whether $\eta$ is constant: it holds step by step with $\eta_t$ . Rearranged, $\langle g_t,x_t-x^*\rangle=\frac{R_t-R_{t+1}}{2\eta_t}+\frac{\eta_t}{2}\norm{g_t}^2$ .

When you use itWith a varying $\eta_t$ the terms $\frac{R_t-R_{t+1}}{2\eta_t}$ no longer telescope directly. Use the strengthened inequality above together with "telescoping with changing weights" (unit 0.3), and bound sums such as $\sum\frac1t\le1+\ln T$ .

Remember

Rates at a glance

Assumptions	Typical guarantee
convex, $G$	$O(1/\sqrt T)$ (L12)
convex, β-smooth	$O(1/T)$ (L13)
α-strongly convex, $G$ , step $\eta_t\propto\frac1{\alpha t}$	$O\big(\frac{\log T}{T}\big)$ for the average
α-strongly convex, β-smooth, $\eta=\frac1\beta$	geometric: $(1-\frac\alpha\beta)^T$

I understand this unit

Unit 9.1 · Approximation algorithms (L14–L15)

Lectures 14–15 in one page: good answers with a proof of how good

Sources: L14 §1, §4; L15 §1; Lec14_SecB; Lec15_SecB; L14 and L15 recordings

Some discrete problems (vertex cover, facility location, edge-disjoint paths, TSP) have no known fast exact algorithm. Instead of giving up, we design a fast algorithm and prove that its answer is within a factor $\alpha$ of the optimum, even though we never compute the optimum.

Minimization. We cannot see OPT, but we can see a lower bound LB. If ALG ≤ α·LB, then ALG ≤ α·OPT automatically.

The two lectures

L14 · Greedy + combinatorial lower bounds

Definitions (α-approximation, PTAS, FPTAS). Vertex cover: greedy by degree is an $O(\log n)$ -approximation (proof by counting), and taking both endpoints of a maximal matching is a 2-approximation (proof: every cover is at least as large as every matching).

L15 · LP relaxation + deterministic rounding

Write the problem as an integer program, drop integrality, solve the LP, then round. Vertex cover: keep every vertex with $x^*_v\ge\frac12$ , a 2-approximation. The dual LP is fractional matching. Facility location: round using balls of radius $2L_j$ around clients (a 6-approximation).

Every result in this chapter

Problem	Algorithm	Lower bound on OPT used in the proof	Factor	Unit
Vertex cover	greedy: highest remaining degree	OPT vertices share the remaining edges (averaging)	$1+\ln m=O(\log n)$	9.4
Vertex cover	both endpoints of a maximal matching $M$	$\lvert M\rvert\le\opt$	2	9.5
Edge-disjoint paths (max)	greedily route short paths (≤ $\sqrt m$ edges)	charging + counting long paths	$O(\sqrt m)$	9.6
Vertex cover (also weighted)	LP, keep $x^*_v\ge\frac12$	$\opt_{LP}\le\opt$	2	9.9
Covering with ≤ $f$ variables per constraint	LP, keep $x^*\ge\frac1f$	$\opt_{LP}\le\opt$	$f$	9.10
Metric facility location	LP, balls $B_j$ , process clients by increasing $L_j$	$F^+D^\le\opt$	6	9.14, 9.15

Exam focus

What the instructor said about the exam (L15)

At the end of Lecture 15 the instructor said that the exam covers the lectures up to this point. Because the 6-approximation proof for facility location was not finished in class, he said facility location would probably be dropped, or tested only up to the rounding algorithm, and that a formal announcement would follow. Check that announcement. Units 9.2–9.5, 9.7–9.9 and 9.11–9.14 follow what was done in class (9.10 develops the idea flagged below, 9.6 and 9.15 were not presented in class).

He also called one idea "a good idea for a problem in the exam": if some nonnegative numbers add up to at least 1, the largest of them is at least their average, so a threshold at the average catches at least one of them. He said such a problem would be given step by step ("prove this, then this, then this"). This idea is used in units 9.4, 9.9, 9.10 and 9.15. Unit 9.10 shows how far it generalizes.

I understand this unit

Unit 9.2 · Approximation algorithms (L14–L15)

α-approximation, PTAS and FPTAS

Sources: L14 §1; Lec14_SecB pp.1–2; L14 recording

To compare an algorithm with the optimum we need a precise notion of "close". For discrete problems we measure closeness by a multiplicative factor.

Definition: α-approximation

\text{minimization: } A(I)\le\alpha\cdot\opt(I),\qquad\qquad \text{maximization: } A(I)\ge\frac{\opt(I)}{\alpha},\qquad \alpha\ge1.

In wordsOn every input $I$ , the algorithm returns a feasible solution whose cost is at most $\alpha$ times the best possible cost (for a minimization problem), or whose value is at least a $1/\alpha$ fraction of the best value (for a maximization problem).

Symbol by symbol

$I$	an instance (one concrete input, e.g. one graph)
$\opt(I)$	the optimal value for that instance. We never compute it. It only appears in the analysis.
$A(I)$	the value of the solution the algorithm returns on $I$
$\alpha$	the approximation factor (ratio). $\alpha=1$ means exact. Closer to 1 is better.

Why it is trueFor minimization every feasible solution costs at least OPT, so $\opt\le A(I)\le\alpha\opt$ forces $\alpha\ge1$ . The answer lands in the interval $[\opt,\ \alpha\opt]$ .

When you use itEvery theorem of this chapter has this form. To prove it you need a lower bound on $\opt$ that you can reason about, because $\opt$ itself is unknown.

The picture from the board: a minimization problem. No feasible answer is below OPT. An α-approximation is guaranteed to land in the shaded interval.

Approximation schemes: as close to 1 as you want

PTAS and FPTAS

\text{PTAS: for every fixed }\eps>0,\ A_\eps\text{ is a }(1+\eps)\text{-approximation in time poly}(n).\qquad \text{FPTAS: time poly}(n,\ 1/\eps).

In wordsA scheme is a family of algorithms, one for each accuracy $\eps$ . A PTAS (polynomial-time approximation scheme) may pay any price in $\eps$ , for example $n^{1/\eps}$ . An FPTAS (fully polynomial) must keep the dependence on $1/\eps$ polynomial too.

Symbol by symbol

$\eps$	target accuracy. The answer is within a factor $1+\eps$ of OPT (for maximization, at least $(1-\eps)\opt$ )
$A_\eps$	the algorithm of the family that is tuned for accuracy $\eps$
poly $(n)$	polynomial in the input size $n$ when $\eps$ is treated as a constant
poly $(n,1/\eps)$	polynomial in both, e.g. $n^3/\eps$

When you use itKnapsack has an FPTAS (the scaling-and-rounding algorithm from earlier in the course). Halving $\eps$ only doubles a $1/\eps$ factor in the running time.

Running time of $A_\eps$	PTAS?	FPTAS?	Why
$n^2/\eps$	yes	yes	polynomial in $n$ and $1/\eps$
$n^3/\eps^5$	yes	yes	still polynomial in $1/\eps$
$n^{1/\eps}$	yes	no	for fixed $\eps$ it is a polynomial, but the degree grows with $1/\eps$
$2^{1/\eps}\,n$	yes	no	exponential in $1/\eps$
$2^n$	no	no	not polynomial in $n$

A hierarchy of how well problems can be approximated

Level	Example from the course
solvable exactly in polynomial time	LP, max-flow, shortest paths
FPTAS: $1+\eps$ at polynomial price	knapsack
constant factor	vertex cover (factor 2), metric facility location (factor 6 in L15)
factor growing slowly with the input	vertex cover by greedy degree: $O(\log n)$
factor growing polynomially	directed edge-disjoint paths: $O(\sqrt m)$
no good factor at all	general TSP (no triangle inequality)

Q. An algorithm for a minimization problem returns cost at most

\opt+5

on every input. Is it an α-approximation for some constant α?

Show answer

Not necessarily. If OPT can be tiny (say

\opt=1

), the ratio

(\opt+5)/\opt=6

is fine, but if

\opt

can be arbitrarily close to 0 (with real costs) the ratio is unbounded. When costs are positive integers,

\opt\ge1

and

\opt+5\le6\,\opt

, so it is a 6-approximation. Additive and multiplicative guarantees are different statements.

Q. Is "returns all of

V

" an approximation algorithm for vertex cover?

Show answer

It is feasible and fast, but its ratio

n/\opt

can be as large as

n

(a star has

\opt=1

). So it is only an

n

-approximation. The interesting question is always how small α can be made.

I understand this unit

Unit 9.3 · Approximation algorithms (L14–L15)

Vertex cover: the running example

Sources: L14 §2; Lec14_SecB p.2; L14 recording

Vertex cover is easy to state and draw, it is hard to solve exactly, and it shows both greedy and LP techniques. It is the main example of both lectures.

The problem

\text{Input } G=(V,E).\qquad\text{Find } S\subseteq V\text{ with } u\in S\text{ or }v\in S\ \text{ for every edge }\{u,v\}\in E,\ \text{ minimizing } \lvert S\rvert.

In wordsChoose as few vertices as possible so that every edge has at least one chosen endpoint. Think of guards at intersections who must watch every street: a guard at a corner watches all the streets touching it.

Symbol by symbol

$S$	the chosen vertices (the cover)
" $e$ is covered"	at least one endpoint of $e$ is in $S$ (both is allowed)
$n=\lvert V\rvert,\ m=\lvert E\rvert$	number of vertices, number of edges
$\opt$	size of a smallest cover (often written $\lvert S^*\rvert$ )

Why it is true $S=V$ always works, so a cover exists. The difficulty is making it small: no polynomial-time algorithm is known for the exact minimum (the problem is NP-hard).

Graph	$\opt$	Why (an optimal cover, and why nothing smaller works)
a single edge	1	either endpoint
star with $k$ leaves	1	the center touches every edge
triangle	2	one vertex leaves the opposite edge uncovered
path with $n$ vertices	$\lfloor n/2\rfloor$	every second vertex; the $\lfloor n/2\rfloor$ disjoint edges each need their own vertex
cycle with $n$ vertices	$\lceil n/2\rceil$	each vertex covers 2 of the $n$ edges, so at least $n/2$
complete graph $K_n$	$n-1$	if two vertices are both missing, the edge between them is uncovered
complete bipartite $K_{a,b}$	$\min(a,b)$	one whole side; a matching of size $\min(a,b)$ shows nothing smaller works

I understand this unit

Unit 9.4 · Approximation algorithms (L14–L15)

Greedy by degree: an O(log n)-approximation

Sources: L14 §2.1; Lec14_SecB pp.2–3; L14 recording

The natural greedy idea: repeatedly take the vertex that covers the most still-uncovered edges. It is not optimal, but we can prove it is never worse than about $\ln m$ times optimal.

$S\gets\emptyset$ , $E_0\gets E$ (the uncovered edges).
While $E_{t-1}\neq\emptyset$ : pick $v_t$ with the largest degree in the remaining graph $(V,E_{t-1})$ . Add it to $S$ . Remove every edge touching $v_t$ : $E_t=E_{t-1}\setminus\{\text{edges at }v_t\}$ .
Return $S$ . It is a cover because the loop only stops when no edge is left uncovered.

The proof, one idea at a time

Fix an optimal cover $S^*$ with $\lvert S^*\rvert=\opt$ . We never compute it. We only use the fact that it exists. Write $\lvert E_t\rvert$ for the number of uncovered edges after $t$ greedy steps.

Claim (the only real idea): the greedy vertex covers at least an OPT-th of what is left

\deg_{E_{t-1}}(v_t)\;\ge\;\frac{\lvert E_{t-1}\rvert}{\opt}.

In wordsWhatever is left, the $\opt$ vertices of $S^*$ share the work of covering it. Someone in $S^*$ must do at least an average share. The greedy vertex does at least as much as anyone.

Symbol by symbol

$\deg_{E_{t-1}}(v)$	number of remaining edges at $v$ (degree in the remaining graph)
$\lvert E_{t-1}\rvert$	number of edges not yet covered before step $t$
$\opt=\lvert S^*\rvert$	size of an optimal cover of the original graph

Why it is true $S^*$ covers every edge of $E$ , so in particular every edge of $E_{t-1}\subseteq E$ . Each remaining edge has at least one endpoint in $S^*$ , so counting edges at the vertices of $S^*$ counts every remaining edge at least once: $\sum_{c\in S^*}\deg_{E_{t-1}}(c)\ge\lvert E_{t-1}\rvert$ . (Equality if no edge has both endpoints in $S^*$ ; otherwise some edges are counted twice.) The largest term of a sum is at least the average: $\max_{c\in S^*}\deg_{E_{t-1}}(c)\ge\lvert E_{t-1}\rvert/\opt$ . Greedy picks a vertex of maximum degree over all of $V$ , so $\deg_{E_{t-1}}(v_t)\ge\max_{c\in S^*}\deg_{E_{t-1}}(c)$ .

Step 2: the number of uncovered edges shrinks by a constant factor

\lvert E_t\rvert=\lvert E_{t-1}\rvert-\deg_{E_{t-1}}(v_t)\;\le\;\lvert E_{t-1}\rvert-\frac{\lvert E_{t-1}\rvert}{\opt}=\lvert E_{t-1}\rvert\Big(1-\frac1\opt\Big).

In wordsEach step removes at least a $\frac1\opt$ fraction of the remaining edges, so at most a $\big(1-\frac1\opt\big)$ fraction survives.

Why it is trueThe edges removed at step $t$ are exactly those at $v_t$ , and there are $\deg_{E_{t-1}}(v_t)$ of them. Subtracting a larger number gives a smaller result, so the claim (a lower bound on the degree) becomes an upper bound on $\lvert E_t\rvert$ . The minus sign flips the inequality.

Step 3: unroll the recursion

\lvert E_t\rvert\le\Big(1-\frac1\opt\Big)\lvert E_{t-1}\rvert\le\Big(1-\frac1\opt\Big)^2\lvert E_{t-2}\rvert\le\dots\le m\Big(1-\frac1\opt\Big)^t\le m\,e^{-t/\opt}.

In wordsA multiplicative shrink, repeated $t$ times, gives a power. The last step uses $1-x\le e^{-x}$ .

Symbol by symbol

$m=\lvert E_0\rvert$	the original number of edges
$1-x\le e^{-x}$	true for every real $x$ . The line $1-x$ is the tangent of the convex function $e^{-x}$ at $x=0$ , and a tangent is a floor (unit 6.3). Use $x=1/\opt$ and raise both (nonnegative) sides to the power $t$ .

Why it is trueThe lecture used the limit $(1-\frac1k)^k\to\frac1e$ . The inequality $1-x\le e^{-x}$ gives the same conclusion exactly, without a limit.

Step 4: when must the algorithm stop?

t>\opt\cdot\ln m\;\Longrightarrow\;\lvert E_t\rvert\le m\,e^{-t/\opt}<m\,e^{-\ln m}=1\;\Longrightarrow\;\lvert E_t\rvert=0.

In wordsOnce the bound drops below 1, the number of remaining edges, which is a whole number, must be 0.

Why it is true $\lvert E_t\rvert$ counts edges, so it is an integer $\ge0$ . An integer that is strictly less than 1 is 0. (The bound never says $\lvert E_t\rvert=0$ directly, since $m e^{-t/\opt}$ is never 0. Integrality closes the gap.)

When you use itEach loop iteration adds exactly one vertex, so $\lvert S\rvert$ = number of iterations. The loop runs at most $\lfloor\opt\ln m\rfloor+1$ times.

Theorem (log approximation)

\lvert S\rvert\;\le\;\lfloor\opt\ln m\rfloor+1\;\le\;\opt\,(1+\ln m)\;\le\;\opt\,(1+2\ln n)=O(\log n)\cdot\opt.

In wordsThe approximation factor grows with the size of the graph, but only logarithmically: for a million vertices, $1+2\ln n\approx29$ .

Symbol by symbol

$\lfloor\opt\ln m\rfloor+1\le\opt(1+\ln m)$	because $\opt\ge1$ whenever $m\ge1$
$\ln m\le2\ln n$	a simple graph has $m\le n(n-1)/2<n^2$ edges

I understand this unit

Unit 9.5 · Approximation algorithms (L14–L15)

Matchings: a lower bound and a 2-approximation

Sources: L14 §2.2; Lec14_SecB pp.3–4; L14 recording

Taking one vertex per step was too timid. Take an edge and add both endpoints. This sounds wasteful, but it gives a constant factor, because the chosen edges form a structure (a matching) that forces every cover to be large.

Definition: matching

M\subseteq E\ \text{ is a matching }\iff\text{no two edges of }M\text{ share an endpoint.}

In wordsA set of edges that are pairwise disjoint: every vertex touches at most one of them.

Symbol by symbol

maximal matching	you cannot add any edge to $M$ and keep it a matching (every edge of $G$ touches some edge of $M$ )
maximum matching	a matching of the largest possible size

Why it is trueEvery maximum matching is maximal, but not conversely. On the path $a\!-\!b\!-\!c\!-\!d$ , $\{bc\}$ is maximal (both other edges touch it) but $\{ab,cd\}$ is larger.

Claim: every matching is at most every vertex cover

\lvert M\rvert\;\le\;\lvert C\rvert\qquad\text{for every matching }M\text{ and every vertex cover }C.\qquad\text{In particular }\lvert M\rvert\le\opt.

In wordsTo cover the edges of a matching, you need a separate vertex for each of them, since no vertex touches two of them.

Why it is true $C$ covers every edge, in particular every edge of $M$ . Give each edge $e\in M$ one endpoint of $e$ that lies in $C$ . Different matching edges have no common endpoint, so they get different vertices. This is a one-to-one map from $M$ into $C$ , so $\lvert M\rvert\le\lvert C\rvert$ .

When you use itAny matching you can find is a certificate that OPT is at least its size, exactly like a feasible dual solution certifies a bound on a primal LP.

The algorithm

The lecture first suggested a greedier version (pick the edge whose endpoints touch the most uncovered edges), then relaxed it: any uncovered edge works.

$C\gets\emptyset$ , $E'\gets E$ .
While $E'\neq\emptyset$ : pick any $\{u,v\}\in E'$ . Add both $u$ and $v$ to $C$ . Remove from $E'$ every edge touching $u$ or $v$ .
Return $C$ . Equivalently: build a maximal matching $M$ (the picked edges) and return all endpoints of $M$ .

Theorem: the matching algorithm is a 2-approximation

\lvert C\rvert\;=\;2\lvert M\rvert\;\le\;2\,\opt.

Symbol by symbol

$M$	the edges the algorithm picked
$\lvert C\rvert=2\lvert M\rvert$	each picked edge contributes two new vertices, and they are new because edges touching earlier picks were deleted
$\lvert M\rvert\le\opt$	the claim above

Why it is trueM is a matching: after picking $\{u,v\}$ we delete every edge touching $u$ or $v$ , so no later pick shares an endpoint with it. C is a cover (feasibility): an edge is deleted from $E'$ only when one of its endpoints is put in $C$ , and the loop ends only when $E'$ is empty. (Equivalently, $M$ is maximal.) Ratio: $\lvert C\rvert=2\lvert M\rvert\le2\opt$ .

When you use itMaximality gives feasibility. Disjointness gives the lower bound. The algorithm never needs a maximum matching.

Q. Why is

\lvert C\rvert

exactly

2\lvert M\rvert

, and not just at most?

Show answer

When an edge

\{u,v\}

is picked, it is still in

E'

, so neither

u

nor

v

is in

C

yet (otherwise every edge at that vertex, including this one, would already have been deleted). So each pick adds two new vertices.

Q. Does the claim

\lvert M\rvert\le\lvert C\rvert

need

M

maximal or

C

minimal?

Show answer

Neither. It holds for every matching and every cover. Maximality of

M

is only needed to make the algorithm's output a cover.

I understand this unit

Unit 9.6 · Approximation algorithms (L14–L15)

Edge-disjoint paths: greedy plus charging (posted L14 notes)

Sources: L14 notes §3 (posted version); L14 recording (problem posed at the end)

This is a maximization problem: route as many source–sink pairs as possible with paths that never share an edge.

The problem

\text{directed } G=(V,E),\ \ m=\lvert E\rvert,\ \text{pairs }(s_1,t_1),\dots,(s_k,t_k):\ \ \max\ \#\{i:\ s_i\text{ connected to }t_i\}\ \text{ by edge-disjoint paths.}

In wordsEach pair may get at most one directed path. Different chosen paths may share vertices but not edges. Maximize the number of connected pairs.

Why it is trueFor a single source and sink this is max-flow (polynomial). With many different pairs (a multicommodity problem) it becomes computationally hard.

Let $L=\max\{1,\lfloor\sqrt m\rfloor\}$ .
Repeatedly find an unrouted pair that still has a directed path with at most $L$ edges in the remaining graph (BFS finds shortest paths). Route it, delete its edges, and mark the pair as done.
Stop when no such pair remains. Call the routed set $A$ . Also, if $A$ is empty, route any one pair that has some path (if any): this guarantees at least one path whenever $\opt>0$ .

Short optimal paths are charged to greedy paths. Long optimal paths are few, because they are edge-disjoint and each uses more than

L

edges.

Theorem: an O(√m)-approximation

\opt\;\le\;(L+1)\,\lvert A\rvert+\frac{m}{L+1}\;\le\;(2\sqrt m+1)\cdot a,\qquad a=\text{number of paths returned }(\ge1\text{ if }\opt>0).

In wordsFix an optimal solution $O$ and split its paths into short (≤ $L$ edges) and long (> $L$ edges). Short ones are charged to greedy paths, and each greedy path receives at most $L+1$ charges. Long ones are few.

Why it is trueLong paths: they are edge-disjoint and each uses at least $L+1$ edges, so there are at most $m/(L+1)$ of them. Short paths: take a short optimal path $Q$ for pair $i$ . If greedy routed pair $i$ , charge $Q$ to that greedy path. Otherwise $Q$ must share an edge with some greedy path, since if all its edges were still present at the end, greedy would have routed pair $i$ along $Q$ . Charge $Q$ to that path. Charges per greedy path $P$ : $P$ has at most $L$ edges, and each edge lies on at most one optimal path (they are edge-disjoint), so at most $L$ charges come through shared edges, plus at most one for the same pair. So $\lvert O_\text{short}\rvert\le(L+1)\lvert A\rvert$ . Arithmetic: with $L=\lfloor\sqrt m\rfloor$ we have $L+1\le\sqrt m+1$ and $m/(L+1)<m/\sqrt m=\sqrt m$ . Since $a\ge\max(\lvert A\rvert,1)$ , $\opt\le(\sqrt m+1)a+\sqrt m\,a$ .

I understand this unit

Unit 9.7 · Approximation algorithms (L14–L15)

From integer programs to LP relaxations

Sources: L15 §1; Lec15_SecB p.1; L15 recording

LPs can be solved in polynomial time, and they come with duality. Most discrete problems are naturally integer programs, and integer programming is hard. Lecture 15's plan: solve the LP version anyway, then repair the fractional answer.

Integer program and its relaxation

\opt_{IP}=\min\{c\T x:\ Ax\ge b,\ x\ge0,\ x\in\Z^n\}\qquad\ge\qquad\opt_{LP}=\min\{c\T x:\ Ax\ge b,\ x\ge0\}.

In wordsThe relaxation drops " $x$ must be integer". It has more feasible points, so its minimum can only be lower (or equal).

Symbol by symbol

$x\in\Z^n$	every coordinate is an integer (the dots of the picture below)
relaxation	the same LP without the integrality constraint (the whole shaded region)
$\opt_{LP}\le\opt_{IP}$	minimizing over a bigger set gives a smaller or equal value. For a maximization problem the inequality flips: $\opt_{LP}\ge\opt_{IP}$ .

Why it is trueEvery integer feasible point is also LP feasible. So the LP minimum is at most the cost of the best integer point.

When you use it $\opt_{LP}$ is the lower bound we were looking for: we can compute it, and it is $\le\opt$ .

The LP-rounding template

Model the problem as an integer program (IP), usually with 0/1 variables "is this object chosen?". Check that IP solutions correspond to solutions of the problem with the same cost.
Relax: drop integrality and keep $0\le x$ (and $x\le1$ if needed).
Solve the LP in polynomial time: optimum $x^*$ , value $\opt_{LP}\le\opt$ .
Round $x^*$ to an integral $\hat x$ . Prove two things: $\hat x$ is feasible, and $c\T\hat x\le\alpha\,c\T x^*$ .

Why the template proves an approximation factor

c\T\hat x\;\le\;\alpha\,c\T x^*\;=\;\alpha\,\opt_{LP}\;\le\;\alpha\,\opt.

In wordsThe rounding loses at most a factor $\alpha$ compared with the LP, and the LP is no worse than the true optimum.

I understand this unit

Unit 9.8 · Approximation algorithms (L14–L15)

Vertex cover as an integer program

Sources: L15 §2; Lec15_SecB pp.1–2; L15 recording

The integer program

\min\ \sum_{v\in V}x_v\quad\text{s.t.}\quad x_u+x_v\ge1\ \ \forall\{u,v\}\in E,\qquad x_v\ge0,\ \ x_v\in\Z.

In wordsOne variable per vertex: $x_v=1$ means " $v$ is chosen". The objective counts chosen vertices. Each edge demands that at least one of its endpoints is chosen.

Symbol by symbol

$x_v$	1 if $v\in S$ , 0 otherwise (the 0/1 modeling trick for "choose a subset")
$\sum_vx_v=\mathbf 1\T x$	the size of the chosen set, a linear objective
$x_u+x_v\ge1$	with 0/1 values, the two cannot both be 0, so the edge is covered

Claim 1: optimal solutions automatically have x ≤ 1

x^*\text{ optimal (for the IP or the LP)}\ \Longrightarrow\ 0\le x^*_v\le1\ \text{ for every }v.

In wordsThere is no reason to "choose a vertex 1.5 times". Lowering it to 1 keeps every edge satisfied and saves cost.

Why it is trueSuppose $x_v>1$ . Replace it by 1. Every constraint containing $x_v$ still holds, since $1+x_u\ge1$ because $x_u\ge0$ . Constraints without $x_v$ are unchanged. The objective strictly decreases. So a point with some $x_v>1$ is never optimal. With integrality this means $x^*\in\{0,1\}^V$ , so we do not need to write $x\le1$ .

Claim 2: the IP is exactly vertex cover

S\text{ a vertex cover}\ \Longrightarrow\ x^S_v=\begin{cases}1&v\in S\\0&v\notin S\end{cases}\ \text{ is feasible with }\sum_vx^S_v=\lvert S\rvert;\qquad x\in\{0,1\}^V\text{ feasible}\ \Longrightarrow\ \{v:x_v=1\}\text{ is a cover.}

Why it is trueFor an edge $\{u,v\}$ , " $u\in S$ or $v\in S$ " is the same as " $x_u+x_v\ge1$ " for 0/1 values. Both directions keep the cost equal, so the minimum of the IP equals the minimum cover size: $\opt_{IP}=\opt$ .

When you use itThis two-way correspondence is the same check as when modeling any problem as an LP (unit 1.2).

The LP relaxation

\opt_{LP}=\min\ \sum_vx_v\quad\text{s.t.}\quad x_u+x_v\ge1\ \ \forall\{u,v\}\in E,\quad x\ge0\qquad\Longrightarrow\qquad\opt_{LP}\le\opt.

In wordsNow a vertex may be chosen "halfway". By Claim 1, optimal LP solutions still lie in $[0,1]^V$ .

Graph	An optimal LP solution	$\opt_{LP}$	$\opt$	Proof that the LP cannot do better
single edge $uv$	$(1,0)$ or $(\frac12,\frac12)$	1	1	the one constraint says $x_u+x_v\ge1$
triangle	all $\frac12$	$\frac32$	2	add the 3 edge constraints: $2\sum x\ge3$
$K_n$	all $\frac12$	$\frac n2$	$n-1$	add all edge constraints: $(n-1)\sum x\ge\binom n2$
star, $k$ leaves	center 1, leaves 0	1	1	one edge constraint
$K_{n,n}$	one side 1, or everything $\frac12$	$n$	$n$	add the constraints of a perfect matching

I understand this unit

Unit 9.9 · Approximation algorithms (L14–L15)

Threshold rounding: a 2-approximation from the LP

Sources: L15 §2; Lec15_SecB p.2; L15 recording

The rounding rule

\hat x_v=\begin{cases}1&\text{if }x^*_v\ge\frac12\\[2pt]0&\text{otherwise}\end{cases}\qquad\qquad\hat C=\{v:\ x^*_v\ge\tfrac12\}.

In wordsSolve the LP. Keep every vertex that the LP chose at least halfway. Throw away the rest.

Symbol by symbol

$x^*$	an optimal solution of the LP relaxation (computed in polynomial time)
$\hat x$	the rounded 0/1 vector; $\hat C$ is the corresponding set of vertices
$\frac12$	the threshold. It comes from the constraints (two variables per constraint), not from "round to the nearest integer"

Lemma: the rounded set is a vertex cover

x^*_u+x^*_v\ge1\ \Longrightarrow\ \max\{x^*_u,x^*_v\}\ge\tfrac12\ \Longrightarrow\ \hat x_u=1\ \text{ or }\ \hat x_v=1.

In wordsTwo numbers that add up to at least 1 cannot both be below $\frac12$ . The larger one is at least the average, so it survives the threshold.

Why it is true $2\max\{x^*_u,x^*_v\}\ge x^*_u+x^*_v\ge1$ . Equivalently, by contradiction: if edge $uv$ were uncovered, then $x^*_u<\frac12$ and $x^*_v<\frac12$ , so $x^*_u+x^*_v<1$ , contradicting LP feasibility.

Theorem: threshold rounding is a 2-approximation

\lvert\hat C\rvert=\sum_v\hat x_v\;\le\;\sum_v2x^*_v\;=\;2\,\opt_{LP}\;\le\;2\,\opt.

In wordsRounding at most doubles each variable, so it at most doubles the LP cost, and the LP cost is a lower bound on OPT.

Symbol by symbol

$\hat x_v\le2x^*_v$	if $\hat x_v=1$ then $x^_v\ge\frac12$ , so $2x^_v\ge1$ . If $\hat x_v=0$ then $2x^*_v\ge0$ . True for every $v$ .
$\sum_vx^*_v=\opt_{LP}$	$x^*$ is an optimal LP solution
$\opt_{LP}\le\opt$	relaxation (unit 9.7)

Why it is trueThe lecture wrote the same chain by splitting the sum: $\sum_v2x^*_v=\sum_{\hat x_v=1}2x^*_v+\sum_{\hat x_v=0}2x^*_v\ge\sum_{\hat x_v=1}1+0=\sum_v\hat x_v$ , and $\sum_v2x^*_v\le2\lvert S^*\rvert$ because $x^{S^*}$ is LP-feasible.

When you use itRunning time: one LP solve plus one pass over the vertices.

I understand this unit

Unit 9.10 · Approximation algorithms (L14–L15)

The same idea, one level up: weights and bigger constraints

Sources: L15 recording (averaging idea flagged for the exam); standard extensions

The instructor singled out the idea behind the last unit as good exam material: numbers that add up to something have a largest member at least as big as their average, so a threshold at the average keeps at least one of them. Here is how far it reaches.

The averaging principle

a_1,\dots,a_k\ge0,\quad a_1+\dots+a_k\ge1\quad\Longrightarrow\quad\max_ia_i\ge\frac1k.

In wordsIf $k$ nonnegative numbers add up to at least 1, at least one of them is at least $\frac1k$ .

Why it is trueIf every $a_i<\frac1k$ , the sum would be $<k\cdot\frac1k=1$ .

When you use itPart 2 used it again and again: the greedy-degree claim (some OPT vertex has degree ≥ the average), the max-flow averaging argument (some threshold cut is at most the average cut, unit 4.4), the best response in a game (a weighted average is at least its minimum, unit 3.8), vertex cover rounding, and the facility-location proof (the cheapest facility is at most the average cost).

Extension 1: weighted vertex cover

Weights change nothing in the rounding proof

\min\sum_vw_vx_v\ \text{ s.t. }x_u+x_v\ge1,\ x\ge0\qquad\Longrightarrow\qquad\sum_vw_v\hat x_v\le\sum_vw_v\,2x^*_v=2\,\opt_{LP}\le2\,\opt.

In wordsEach vertex has a cost $w_v\ge0$ , and we minimize the total cost of the cover. Same LP constraints, same threshold, same per-vertex inequality $\hat x_v\le2x^*_v$ , now multiplied by $w_v\ge0$ .

Extension 2: constraints with up to f variables

f-approximation by rounding at 1/f

\min\ c\T x\ \text{ s.t. }\sum_{v\in T_e}x_v\ge1\ \ \forall e,\ \ x\ge0,\quad\lvert T_e\rvert\le f\qquad\Longrightarrow\qquad\hat x_v=\mathbb 1\big[x^*_v\ge\tfrac1f\big]\ \text{ is feasible and }\ c\T\hat x\le f\cdot\opt.

In wordsA covering problem where every requirement $e$ can be satisfied by at most $f$ different objects (the set $T_e$ ). Keep every object the LP chose to an extent of at least $\frac1f$ .

Symbol by symbol

$T_e$	the objects able to satisfy requirement $e$ . Vertex cover: $T_e$ is the 2 endpoints of edge $e$ , so $f=2$ .
$f$	the largest $\lvert T_e\rvert$ (in set cover: the maximum number of sets containing one element, its "frequency")
$c\ge0$	object costs

Why it is trueFeasible: the $\le f$ values $x^*_v$ , $v\in T_e$ , add up to at least 1, so by the averaging principle one of them is $\ge\frac1f$ and is kept. Cost: $\hat x_v\le f\,x^*_v$ for every $v$ (if kept, $fx^*_v\ge1$ ), so $c\T\hat x\le f\,c\T x^*=f\,\opt_{LP}\le f\,\opt$ .

Worked example

Hitting all lines of the Fano plane

Points

1,\dots,7

. Lines (requirements):

\{1,2,3\},\{1,4,5\},\{1,6,7\},\{2,4,6\},\{2,5,7\},\{3,4,7\},\{3,5,6\}

. Choose few points so that every line contains a chosen point. Here

f=3

. Each point lies on 3 lines, so adding the 7 constraints gives

3\sum x\ge7

:

\opt_{LP}\ge\frac73

, attained by all

x_v=\frac13

. Rounding at

\frac13

keeps all 7 points, and

7\le3\cdot\frac73

as promised. The true optimum is 3 (any line meets every other line), so here the ratio is

\frac73

. Note that a threshold of

\frac12

would keep nothing, which is infeasible: the threshold must match

f

.

I understand this unit

Unit 9.11 · Approximation algorithms (L14–L15)

The dual of the vertex cover LP is fractional matching

Sources: L15 §2; Lec15_SecB p.3; L15 recording

Lecture 14 used matchings as lower bounds. Lecture 15 used the LP. Duality shows they are the same idea: the dual of the vertex cover LP is a matching problem.

Primal (vertex cover LP) and its dual

\text{(P)}\ \min\sum_{v\in V}x_v\ \ \text{s.t. } x_u+x_v\ge1\ \ \forall e=\{u,v\}\in E,\ \ x\ge0\qquad\qquad\text{(D)}\ \max\sum_{e\in E}y_e\ \ \text{s.t. }\sum_{e\ni v}y_e\le1\ \ \forall v\in V,\ \ y\ge0.

In wordsOne dual variable $y_e$ per edge (each primal constraint is an edge). One dual constraint per vertex (each primal variable is a vertex): the edges at $v$ may carry total weight at most 1.

Symbol by symbol

$y_e$	weight on edge $e$ , the multiplier of the constraint $x_u+x_v\ge1$
$e\ni v$	the edges that have $v$ as an endpoint
$\sum_{e\ni v}y_e\le1$	comes from column $v$ of the constraint matrix: $x_v$ appears (with coefficient 1) exactly in the rows of the edges at $v$

Why it is trueRules for a min primal (unit 3.5): ≥ rows give multipliers $y_e\ge0$ ; variables $x_v\ge0$ give "≤ cost" constraints, here cost 1; the objective of the dual is the right-hand sides, all 1. Certificate view: multiply each edge constraint by $y_e\ge0$ and add: $\sum_ey_e(x_u+x_v)=\sum_vx_v\sum_{e\ni v}y_e\ge\sum_ey_e$ . If every $\sum_{e\ni v}y_e\le1$ , then $\sum_vx_v\ge\sum_vx_v\sum_{e\ni v}y_e$ (because $x\ge0$ ), so $\sum_vx_v\ge\sum_ey_e$ .

The primal matrix is the edge–vertex incidence matrix. Each edge row has two 1s (its endpoints). Transposing gives one row per vertex, with a 1 for each edge at that vertex.

Integral dual solutions are exactly matchings

y\in\{0,1\}^E\ \text{ dual feasible}\iff M=\{e:y_e=1\}\text{ is a matching},\qquad\text{value }\sum_ey_e=\lvert M\rvert.

In words"Total weight at most 1 at every vertex" with 0/1 weights means "at most one chosen edge at every vertex", which is the definition of a matching. Fractional dual solutions are fractional matchings.

Why it is trueIf two chosen edges shared a vertex $v$ , the constraint at $v$ would read $1+1\le1$ .

Everything in one chain

\lvert M\rvert\;\le\;\opt_{D}\;=\;\opt_{LP}\;\le\;\opt\;\le\;\lvert\hat C\rvert\;\le\;2\,\opt_{LP},\qquad\opt\le\lvert C_{\text{matching alg}}\rvert=2\lvert M\rvert.

In wordsLecture 14's lower bound (a matching) is an integral dual solution. Lecture 15's lower bound (the LP optimum) is the best fractional one. Weak duality is what makes both of them lower bounds.

Symbol by symbol

$\lvert M\rvert\le\opt_D$	a matching is a feasible dual solution (integral)
$\opt_D=\opt_{LP}$	strong duality (both LPs are feasible: $x=\mathbf 1$ , $y=0$ )
$\opt_{LP}\le\opt$	relaxation

I understand this unit

Unit 9.12 · Approximation algorithms (L14–L15)

Integrality gaps: how good can an LP lower bound be?

Sources: L15 §2 (integrality gap); Lec15 notes; standard facts

Definition (minimization problems)

\text{integrality gap}=\sup_{\text{instances }I}\ \frac{\opt_{IP}(I)}{\opt_{LP}(I)}\;\ge\;1.

In wordsThe worst ratio between the true optimum and the LP lower bound, over all instances.

When you use itAny proof of the form "ALG ≤ α· $\opt_{LP}$ " must have $\alpha\ge$ the gap, since on the worst instance even $\opt$ itself is that far above $\opt_{LP}$ . The gap limits what this LP can certify, whatever rounding you use.

Vertex cover on the complete graph: the gap approaches 2

\opt(K_n)=n-1,\qquad\opt_{LP}(K_n)=\frac n2,\qquad\frac{n-1}{n/2}=2-\frac2n\ \xrightarrow{n\to\infty}\ 2.

Why it is trueAll $x_v=\frac12$ is feasible, so $\opt_{LP}\le\frac n2$ . Adding all $\binom n2$ edge constraints, each vertex appears in $n-1$ of them: $(n-1)\sum_vx_v\ge\frac{n(n-1)}2$ , so $\sum_vx_v\ge\frac n2$ for every feasible $x$ . The integral optimum is $n-1$ (unit 9.3).

Remember

Three different statements about the number 2

Statement	Evidence	What it rules out
The analysis of this algorithm is tight	single edge, $K_{n,n}$	proving a better factor for the same algorithm
The LP has integrality gap 2	$K_n$ : $2-\frac2n$	any algorithm whose proof compares only with $\opt_{LP}$
The problem is hard to approximate	complexity theory (beyond this course)	every polynomial-time algorithm

For vertex cover, nobody knows a polynomial-time

(2-\eps)

-approximation. It is known to be NP-hard to approximate within some constant above 1 (currently about

\sqrt2

), and it is conjectured that 2 is the true limit. The instructor's remark that "improving the 2 unlocks many wonders" refers to this.

Q. The triangle has

\opt=2

and

\opt_{LP}=\frac32

. What does this say about rounding?

Show answer

Every integral solution costs at least

2=\frac43\opt_{LP}

, so any rounding of the LP loses at least a factor

\frac43

on the triangle. Rounding cannot be lossless here, unlike max-flow/min-cut, where the rounding lost nothing (unit 4.5).

I understand this unit

Unit 9.13 · Approximation algorithms (L14–L15)

Facility location: the model

Sources: L15 §3; Lec15_SecB pp.3–4; L15 recording

Facilities (say coffee shops) can be opened at a cost, and every client must be served by an open facility, paying a connection cost (think: distance). Open too few and clients travel far. Open too many and opening costs add up.

The problem

\min_{S\subseteq F,\ S\neq\emptyset}\ \ \sum_{i\in S}f_i+\sum_{j\in C}\ \min_{i\in S}d_{ij}.

In wordsChoose which facilities to open. Each client then goes to its nearest open facility. Pay the opening costs plus every client's distance.

Symbol by symbol

$F,\ C$	candidate facilities, clients
$f_i\ge0$	cost of opening facility $i$
$d_{ij}\ge0$	cost of serving client $j$ from facility $i$ (a distance)
metric	distances come from a metric on $F\cup C$ , so the triangle inequality holds: $d(a,c)\le d(a,b)+d(b,c)$ . The proof uses chains like client → facility → client → facility.

Why it is trueThe triangle inequality is a "physical" assumption: going through an intermediate point is never shorter than going directly. Without it, a facility could be close to two clients that are very far from each other, which breaks the geometric reasoning of the algorithm.

Integer program

\min\ \sum_{i\in F}f_ix_i+\sum_{i\in F,\,j\in C}d_{ij}y_{ij}\quad\text{s.t.}\quad\sum_{i\in F}y_{ij}=1\ \ \forall j,\qquad y_{ij}\le x_i\ \ \forall i,j,\qquad x_i,y_{ij}\in\{0,1\}.

In words $x_i=1$ : facility $i$ is open. $y_{ij}=1$ : client $j$ is assigned to facility $i$ . Pay for open facilities and for each assignment.

Symbol by symbol

$\sum_iy_{ij}=1$	every client is assigned to exactly one facility
$y_{ij}\le x_i$	"you cannot be assigned to a closed facility": if $x_i=0$ then $y_{ij}$ is forced to 0. If $x_i=1$ the constraint allows $y_{ij}\in\{0,1\}$ .
$\{0,1\}$	dropped in the relaxation, replaced by $x,y\ge0$ . Upper bounds of 1 are not needed: $y_{ij}\le1$ follows from $\sum_iy_{ij}=1$ , and any $x_i$ can be lowered to $\max_jy_{ij}\le1$ without breaking a constraint or increasing the cost.

Why it is trueThe constraint $y_{ij}\le x_i$ is the contrapositive of "assigned ⇒ open". It is the standard way to link two families of 0/1 variables. Any choice of open facilities plus assignments gives a feasible 0/1 point with the same cost, and conversely, so the IP solves facility location.

The LP relaxation and the numbers it gives us

(x^*,y^*)\text{ optimal for the LP},\qquad F^*=\sum_if_ix^*_i,\qquad D^*=\sum_{i,j}d_{ij}y^*_{ij},\qquad\opt_{LP}=F^*+D^*\le\opt.

In wordsIn the "fractional universe" facility $i$ is open to an extent $x^*_i$ , and client $j$ spends a fraction $y^*_{ij}$ of its time at facility $i$ , never more than the facility is open. $F^*$ is the fractional opening cost, and $D^*$ the fractional travel cost.

A client's fractional average distance

L_j=\sum_{i\in F}d_{ij}\,y^*_{ij},\qquad\sum_{j\in C}L_j=D^*.

In wordsThe $y^*_{ij}$ for a fixed client add up to 1, so $L_j$ is a weighted average distance: how far client $j$ travels on average in the LP solution.

I understand this unit

Unit 9.14 · Approximation algorithms (L14–L15)

Facility location rounding: balls around clients

Sources: L15 §3.1–3.2; Lec15_SecB pp.5–6; L15 recording

The rounding is geometric. Each client looks only at facilities within twice its LP average distance. Clients with small balls (tight budgets) choose first, and clients whose balls overlap an earlier ball share that earlier client's facility.

The ball of a client

B_j=\{i\in F:\ d_{ij}\le2L_j\}.

In wordsAll candidate facilities within twice client $j$ 's average LP distance.

Lemma (in Lec15_SecB): every ball contains at least half a facility

\sum_{i\in B_j}y^*_{ij}\;\ge\;\tfrac12\qquad\text{and therefore}\qquad\sum_{i\in B_j}x^*_i\;\ge\;\tfrac12.

In wordsAt most half of a client's LP "time" can be spent at facilities more than twice its average distance away. This is Markov's inequality: a nonnegative quantity exceeds twice its average with probability at most one half.

Why it is trueFor $i\notin B_j$ we have $d_{ij}>2L_j$ , i.e. $1<\frac{d_{ij}}{2L_j}$ . Multiply by $y^*_{ij}\ge0$ and add over those $i$ : $\sum_{i\notin B_j}y^*_{ij}\le\sum_{i\notin B_j}\frac{d_{ij}}{2L_j}y^*_{ij}\le\frac1{2L_j}\sum_{i\in F}d_{ij}y^*_{ij}=\frac{L_j}{2L_j}=\frac12$ . Since $\sum_iy^*_{ij}=1$ , the rest, $\sum_{i\in B_j}y^*_{ij}$ , is at least $\frac12$ . Finally $x^*_i\ge y^*_{ij}$ for each $i$ (the LP constraint), so $\sum_{i\in B_j}x^*_i\ge\frac12$ . (If $L_j=0$ , all of client $j$ 's LP mass sits at distance 0, inside $B_j$ , and the sum is 1.)

When you use itTwo consequences: $B_j$ is never empty, and opening the cheapest facility of $B_j$ costs at most twice the fractional opening cost inside the ball (next unit).

The algorithm

Sort the clients so that $L_{j_1}\le L_{j_2}\le\dots$ (small balls first). Set $R=\emptyset$ (the "representatives", clients that open a facility) and $S=\emptyset$ (open facilities).
For each client $j$ $j$ in this order:
- If $B_j\cap B_r=\emptyset$ for every $r\in R$ : open the cheapest facility $i_j\in\arg\min_{i\in B_j}f_i$ , add $j$ to $R$ , and assign $j$ to $i_j$ .
- Otherwise pick some $r\in R$ with $B_j\cap B_r\neq\emptyset$ , and assign $j$ to $i_r$ , the facility opened for $r$ .
Return the open facilities and the assignments. Several clients may share a facility.

I understand this unit

Unit 9.15 · Approximation algorithms (L14–L15)

Why it is a 6-approximation (the proof promised for the next lecture)

Sources: Completes L15 §3 (stated, proof deferred in class); standard argument

Opening cost: at most 2F*

f_{i_r}\;\le\;\frac{\sum_{i\in B_r}f_ix^*_i}{\sum_{i\in B_r}x^*_i}\;\le\;2\sum_{i\in B_r}f_ix^*_i\qquad\Longrightarrow\qquad\sum_{r\in R}f_{i_r}\le2\sum_{r\in R}\sum_{i\in B_r}f_ix^*_i\le2F^*.

In wordsThe cheapest facility in a ball costs at most the weighted average cost in that ball. The weights inside each representative's ball add up to at least $\frac12$ , so the average costs at most twice the fractional cost spent in the ball. Representatives' balls are disjoint, so no fractional cost is counted twice.

Symbol by symbol

first $\le$	a minimum is at most any weighted average (the averaging principle, with weights $x^*_i$ )
second $\le$	the denominator is $\ge\frac12$ by the lemma
last $\le$	the balls $B_r$ , $r\in R$ , are disjoint, so the double sum counts each facility at most once, and $\sum_if_ix^_i=F^$

Connection cost: every client pays at most 6 L_j

j\in R:\ d(j,i_j)\le2L_j;\qquad j\notin R:\ d(j,i_r)\le d(j,i)+d(i,r)+d(r,i_r)\le2L_j+2L_r+2L_r\le6L_j.

In wordsA representative is served inside its own ball. Any other client walks to a shared facility $i\in B_j\cap B_r$ , then to the representative $r$ , then to $r$ 's open facility: three legs, each at most twice an average distance, and $L_r\le L_j$ .

Symbol by symbol

$i\in B_j\cap B_r$	exists because the balls intersect. So $d(j,i)\le2L_j$ and $d(r,i)\le2L_r$
$d(r,i_r)\le2L_r$	$i_r\in B_r$
$L_r\le L_j$	$r$ was processed earlier (sorting)
triangle inequality	applied twice along the path $j\to i\to r\to i_r$

Why a non-representative client is never far from its facility.

Theorem: a 6-approximation

\text{cost}\;\le\;2F^*+\sum_j6L_j\;=\;2F^*+6D^*\;\le\;6\,(F^*+D^*)\;=\;6\,\opt_{LP}\;\le\;6\,\opt.

In wordsOpening costs lose a factor 2, connection costs lose a factor 6, so overall at most 6 times the LP lower bound.

I understand this unit

Unit 9.16 · Approximation algorithms (L14–L15)

The approximation toolbox: patterns, proofs and traps

Sources: Synthesis of L14–L15

The proof skeleton (minimization)

Feasibility. Why is the output a valid solution? (Loop stops only when everything is covered; the averaging principle keeps a variable in every constraint; every client gets an open facility.)
A lower bound $LB\le\opt$ . Name it and prove it.
Compare. Show $\text{ALG}\le\alpha\cdot LB$ , usually term by term.
Chain. $\text{ALG}\le\alpha\,LB\le\alpha\,\opt$ . For maximization, flip: an upper bound $UB\ge\opt$ and $\text{ALG}\ge UB/\alpha$ .

Where lower bounds come from

Lower bound	Why it is ≤ OPT	Used for
counting / averaging over an optimal solution	the optimal solution must do the work, so one of its parts does an average share	greedy degree (9.4), edge-disjoint paths (9.6)
a disjoint structure (matching)	each disjoint piece needs its own element of any solution	maximal matching (9.5)
LP relaxation value	the LP minimizes over a larger set	threshold rounding (9.9, 9.10), facility location (9.14)
any feasible dual solution	weak duality	matching = integral dual (9.11)

Proof moves to recognize

Move	Formula	Where
largest ≥ average	$\sum_{i=1}^ka_i\ge1\Rightarrow\max_ia_i\ge\frac1k$	greedy claim, rounding feasibility
smallest ≤ weighted average	$\min_if_i\le\frac{\sum f_ix_i}{\sum x_i}$	cheapest facility in a ball
multiplicative shrink	$a_t\le(1-\frac1k)a_{t-1}\Rightarrow a_t\le a_0e^{-t/k}$	greedy degree
integer below 1 is 0	$0\le a_t<1,\ a_t\in\Z\Rightarrow a_t=0$	stopping time of greedy
per-variable rounding loss	$\hat x_v\le\frac1\tau x^*_v$	any threshold rounding
Markov	mass beyond $c\times$ average $\le\frac1c$	facility balls
charging	map each optimal piece to an algorithm piece; bound the load per algorithm piece	edge-disjoint paths
balancing two losses	$L$ vs $m/L\Rightarrow L=\sqrt m$	edge-disjoint paths (like choosing η)

Traps

The ratio is for every instance, and the output must be feasible.
Minimization: $\alpha\ge1$ and ALG ≤ α·OPT. Maximization: ALG ≥ OPT/α. Don't mix the directions of the bounds.
For minimization the relaxation gives $\opt_{LP}\le\opt$ (a lower bound). For maximization, $\opt_{LP}\ge\opt$ .
Degrees in greedy are in the remaining graph, and the proof uses the original optimal cover.
Maximal ≠ maximum. The 2-approximation only needs maximal.
$\lvert M\rvert\le\lvert C\rvert$ holds for every matching and every cover.
A tight example for an algorithm is not a hardness result for the problem.
Threshold above $\frac12$ can make the vertex cover rounding infeasible. With $f$ variables per constraint the threshold must be $\frac1f$ .
The matching algorithm does not handle weights. LP rounding does.
PTAS: polynomial for each fixed $\eps$ (e.g. $n^{1/\eps}$ is allowed). FPTAS: polynomial in $1/\eps$ too.
Facility location: the 6 needs the triangle inequality and the processing order by $L_j$ .

I understand this unit

Unit 10.1 · Exam toolkit

Choose the argument before writing algebra

Sources: Synthesis of L9–L15

Task	Argument to use	Checks to include
Model a problem as an LP	variables (with units) → objective → one constraint per rule → two-way correspondence	real vs integer; signs of variables; polynomial size
Prove a candidate is optimal	feasible $x$ + feasible $y$ + equal values (weak duality)	check every row and sign of both
Write the dual	one multiplier per row (sign from table/S-O-B) → one constraint per column → objective from RHS	max↔min, transpose, counts, equality↔free
Find / explain an optimal point	complementary slackness forces equations; solve; verify the rest	products are zero, not "exactly one factor"
Show an LP is infeasible	Farkas witness $w$ (or contradictory combination of rows)	signs of the multipliers
Show an LP is unbounded	feasible $x_0$ + ray $v$ with $Av\le0,\ v\ge0,\ c\T v>0$	stays feasible for all $t\ge0$
Max-flow = min-cut	flow ≤ cut; rounding: cut ≤ dual; strong duality: dual = flow	directed edges; nonnegative lengths; clipped distances
Strong duality	if $c\notin$ cone of tight normals, Farkas ⇒ improving feasible direction ⇒ contradiction	include $-x_i\le0$ ; one $\eps$ for all slack rows; build $y,z$
Prove a function is convex	chord definition / tangent / Hessian PSD / composition rules (max, inf, sum, affine)	domain convex; joint convexity for inf
Local = global	assume strictly better feasible $y$ → segment → arbitrarily close better points	convex $f$ and convex $K$
Analyze gradient descent	expand $R_{t+1}$ → convexity + $G$ → telescope → $R_0\le D^2,\ R_T\ge0$ → Jensen → balance $\eta$	which points are averaged; fixed $\eta$ ; additive error
Analyze projected GD	same as L12, plus one line: $\norm{\Pi_K(y)-x^}^2\le\norm{y-x^}^2$ (projection inequality with $z=x^*$ )	$x^*\in K$ ; $K$ convex; output average is in $K$
Analyze smooth GD	descent lemma → safe step $-\frac1{2\beta}\norm{g}^2$ → convexity → $\frac\beta2(R_t-R_{t+1})$ → telescope → monotone ⇒ last iterate	$\eta=1/\beta$ ; no $G$ needed; index $t+1$ on the left
Prove a projection/nearest-point fact	move from $p$ toward $z\in K$ : $f(\theta)$ minimized at 0 ⇒ $f'(0^+)\ge0$ ⇒ $\langle u-p,z-p\rangle\le0$ ⇒ expand the square	uses convexity of $K$ (segment stays in $K$ )
Prove a lower bound for a min LP	nonnegative combination of ≥ rows whose coefficients are $\le$ the costs	$x\ge0$ is what lets you compare coefficients
Linearize an objective with $\|\cdot\|$ or max/min	new variable per awkward term, bounded by linear inequalities	only in the convex direction (min of convex, max of concave)
Show one LP form expresses another	transform → map feasible solutions both ways with equal value → recover	polynomial size; signs of new variables
Derive a Farkas variant	rewrite the system with slacks / split variables → apply the known version → read off each column block	slack columns ⇒ $y\ge0$ ; $\pm$ columns ⇒ equality
Analyze a zero-sum game	best responses are pure (linear over simplex) → max-min as an LP → dual is the other player's LP	which variables are free; the simplex equality row
GD with strong convexity / varying $\eta_t$	expand $R_{t+1}$ with $\eta_t$ → strengthened key inequality → weighted telescoping → bound the sum	coefficients must line up; harmonic sum; Jensen
Prove an α-approximation (min)	feasibility → name a lower bound $LB\le\opt$ → show $\text{ALG}\le\alpha\,LB$	every instance; polynomial time; direction of the ratio (max: $\text{ALG}\ge\opt/\alpha$ )
Analyze a greedy that removes a share of what is left	"OPT's pieces share the remaining work" → greedy step removes $\ge\frac1\opt$ of it → $a_t\le a_0(1-\frac1\opt)^t\le a_0e^{-t/\opt}$ → integer below 1 is 0	degrees in the remaining instance; use the original optimum
Lower-bound OPT combinatorially	find disjoint structures (a matching): each needs its own element of any solution	"every matching ≤ every cover"; maximal suffices for the algorithm
Design and analyze LP rounding	IP with 0/1 variables (check both directions) → relax → $\opt_{LP}\le\opt$ → rounding rule → feasibility (largest ≥ average) → per-variable loss $\hat x_v\le\alpha x^*_v$ → chain	threshold $=\frac1f$ for $f$ variables per constraint; costs $\ge0$
Dual of a covering LP	one multiplier per covering row, one ≤-cost row per variable (transpose the incidence matrix); integral dual = packing (matching)	weak duality ⇒ any dual solution is a lower bound
Show a factor cannot be improved	tight example for the algorithm (single edge, $K_{n,n}$ ); integrality gap for the LP ( $K_n$ )	tight algorithm ≠ hard problem

How to write a contradiction proof (used three times in Part 2)

State what you assume fails (e.g. " $\hat x$ is not a global min", " $c$ is not in the cone").
Produce a witness of the failure: a better point $y$ , or a Farkas vector $w$ .
Use the witness to build an object the hypotheses forbid: a better point arbitrarily close to $\hat x$ , or a better feasible point $x^*+\eps v$ .

The sentence that keeps proofs honest

After every inequality write "this uses ___". In Part 2 the blank is almost always one of: nonnegative multipliers, $x\ge0$ , coordinatewise feasibility, the tangent (first-order convexity) inequality, the chord inequality, Cauchy–Schwarz, $\norm{g}\le G$ , $R_0\le D^2$ , $R_T\ge0$ , or "a square is ≥ 0". If you cannot fill it in, check the direction of the inequality.

I understand this unit

Unit 10.2 · Exam toolkit

The traps, all in one place

Sources: Collected from every chapter

Feasible ≠ optimal. A feasible point gives only a lower bound (for max).
Vector inequalities are coordinatewise.
Negative coefficients are allowed in an LP. Products of variables are not. Strict inequalities are not allowed.
"Unbounded" refers to the objective, not the region.
Vertex = $n$ independent tight constraints, counting sign constraints. Not " $n$ tight constraints".
Some optimal solution is a vertex. Not every one, and not necessarily a unique one.
Short answer ≠ fast algorithm (Cramer). Polynomial in bit length, not in magnitudes (knapsack is pseudo-polynomial).
Dual constraints come from columns (transpose).
Don't use the max-primal sign table on a min primal. Use S-O-B.
Equality ↔ free.
Weak duality alone proves a matching feasible pair optimal.
Primal infeasible does not imply dual unbounded (both can be infeasible).
Complementary slackness: "tight ⇒ positive multiplier" is false. The product is zero.
Verify feasibility after using slackness to generate a candidate.
Gap bounds are additive.
Path LP is exponential. Don't propose enumerating paths as an algorithm.
Only edges leaving $S$ count in a directed cut.
Two integrality facts: 0/1 optimal dual (any real capacities) vs integral flow (integer capacities).
Dijkstra needs nonnegative lengths.
Farkas sign orientation: $w=-v$ . Generators score ≥ 0, $p$ scores < 0, and $w$ is free in sign.
Cone weights are ≥ 0, not > 0. Conclusions are $v\T a_j\le0$ , not < 0.
Include $-x_i\le0$ normals in the active-constraint argument.
Convex set ≠ convex function. Local ⇒ global needs both.
Tangent is a floor: $f(x)-f(x^*)\le\langle\nabla f(x),x-x^*\rangle$ (≤, not ≥).
PSD ≠ nonnegative entries.
Min of convex functions is not convex. Max is. Partial minimization needs joint convexity.
Boundary optimum ⇒ gradient need not be 0.
Convex ≠ unique minimizer, and convex ≠ a minimizer exists.
Multiplying an inequality by $-2\eta$ flips it.
GD theorem bounds the average of $x_0..x_{T-1}$ (or the best iterate), not the last iterate.
$D$ and $G$ are assumptions, not consequences of convexity.
$\eta=D/(G\sqrt T)$ is constant for a fixed horizon, not $\eta_t\propto1/\sqrt t$ .
$T$ iterations ≠ $O(T)$ time. Multiply by the cost of a gradient.
Telescoping requires $R_t-R_{t+1}$ , not $R_t-R_{t-1}$ .
Projection needs a convex $K$ and $x^*\in K$ (a minimizer over $K$ , not over $\R^d$ ).
β-smooth is not convex ( $\sin x$ is 1-smooth). Smoothness bounds curvature from above, convexity from below.
Bounded gradient and smooth are different: $x^2/2$ is smooth but has unbounded gradient; $|x|$ has $G=1$ but is not smooth.
Last iterate is only guaranteed in the smooth theorem, because the safe step makes $f(x_t)$ monotone.
Rates: bounded gradients need $O(\eps^{-2})$ steps; smooth needs $O(\eps^{-1})$ . Not $O(\sqrt{\eps^{-1}})$ .
Safe step is $\eta=1/\beta$ ; any $\eta<2/\beta$ still decreases $f$ , and $\eta>2/\beta$ can diverge.
Min-LP certificates flip everything: $y\ge0$ on ≥ rows and combined coefficients $\le c$ give a lower bound.
Linearization tricks only work in the convex direction. You cannot maximize $|x|$ with an LP.
Intersections of convex sets are convex; unions need not be.
Products and differences of convex functions need not be convex; sums with nonnegative weights and maxima are.
Farkas variants differ in the certificate's sign: free for equality systems, $\ge0$ for inequality systems; $A\T y=0$ when $x$ is free.
$p\T Aq$ is not jointly linear in $(p,q)$ . Fix one player, then the best response is a pure strategy.
Strong convexity + a global gradient bound can only hold on a bounded region or at the visited iterates.
Approximation ratios are multiplicative and hold for every instance; the output must always be feasible.
Min: ALG ≤ α·OPT with α ≥ 1. Max: ALG ≥ OPT/α. The relaxation is a lower bound for min ( $\opt_{LP}\le\opt$ ) and an upper bound for max.
Greedy degree: degrees are in the remaining graph, and the proof uses the original optimal cover.
Maximal ≠ maximum. The 2-approximation needs only a maximal matching; $\lvert M\rvert\le\lvert C\rvert$ holds for every matching and every cover.
Rounding threshold: above $\frac12$ the vertex cover rounding can be infeasible; with $f$ variables per constraint use $\frac1f$ . Nearest-integer rounding is not feasible in general.
The matching algorithm ignores weights; LP rounding handles weighted vertex cover.
Tight example ≠ integrality gap ≠ hardness. They limit one algorithm, one LP, and all algorithms respectively.
PTAS allows $n^{1/\eps}$ ; FPTAS must be polynomial in $1/\eps$ too.
Facility location's 6 needs the triangle inequality, balls of radius $2L_j$ , and processing clients by increasing $L_j$ . Balls are sets of facilities.

I understand this unit

Unit 10.3 · Exam toolkit

Formula sheet, decoded

Sources: All lectures

Formula	In words	Valid when
$\max c\T x,\ Ax\le b,\ x\ge0$	canonical primal	any LP after conversion
$\min b\T y,\ A\T y\ge c,\ y\ge0$	its dual: cheapest valid row weights	canonical primal
$c\T x\le x\T A\T y=y\T Ax\le b\T y$	weak duality chain	$x$ , $y$ both feasible
$\max c\T x=\min b\T y$	strong duality	either side has a finite optimum
$b\T y-c\T x=y\T s+x\T r$	gap = priced leftovers + losses on produced items	feasible pair; $s=b-Ax,\ r=A\T y-c$
$y_j s_j=0,\ x_ir_i=0$	complementary slackness	iff both optimal
$\opt-c\T x\le b\T y-c\T x$	gap bounds the error	feasible pair
rank of tight normals $=n$	vertex test	include sign rows
$x_i=\det B_i/\det B$	Cramer: vertices have short encodings	$B$ nonsingular
$M\lambda=p,\lambda\ge0$ XOR $M\T w\ge0,p\T w<0$	Farkas: in the cone, or a witness	any real $M,p$
$v\T p>v\T q\ge v\T z\ \forall z\in C$	separation, $v=p-q$ , $q$ nearest	$C$ closed, convex, nonempty; $p\notin C$
$c=\sum_{r\in S}\lambda_ra_r=A\T y-z$	objective in cone of tight normals → dual	at an optimum $x^*$
$\max\sum_px_p:\sum_{p\ni e}x_p\le c_e$	path-flow LP	$x\ge0$
$\min\sum_ec_ey_e:\sum_{e\in p}y_e\ge1$	length dual	$y\ge0$
$\ell(v)=\min\{d(v),1\},\ S_r=\{\ell\le r\}$	threshold rounding	$r\in(0,1)$
$\int_0^1c(\delta^+(S_r))dr\le\sum c_ey_e$	average cut ≤ fractional cost	feasible lengths
$f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y)$	convex: below chords	$x,y\in K$ , $\theta\in[0,1]$
$f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle$	tangent is a global floor	$f$ differentiable convex
$f(x)-f(x^)\le\langle\nabla f(x),x-x^\rangle$	error ≤ slope · displacement	same
$v\T\nabla^2f(x)v\ge0$	Hessian PSD ⇔ convex	$f\in C^2$
$\max_if_i$ , $\inf_{y\in Y}f(x,y)$	convexity-preserving operations	$f_i$ convex; $f$ jointly convex, $Y$ convex
$\nabla\tfrac12\norm{Ax-b}^2=A\T(Ax-b)$ , Hessian $A\T A$	least squares	always
$\langle v,w\rangle\ge-\norm v\norm w$	Cauchy–Schwarz ⇒ $-\nabla f$ steepest	always
$x_{t+1}=x_t-\eta\nabla f(x_t)$	gradient descent	$K=\R^d$
$R_{t+1}=R_t-2\eta\langle g_t,x_t-x^*\rangle+\eta^2\norm{g_t}^2$	one-step expansion	always (algebra)
$f(x_t)-f^*\le\frac{R_t-R_{t+1}}{2\eta}+\frac{\eta G^2}2$	one-step inequality	convex, $\norm{g_t}\le G$
$f(\bar x_T)-f^*\le\frac{D^2}{2\eta T}+\frac{\eta G^2}2$	GD theorem	convex, minimizer, $D$ , $G$ , fixed $\eta$
$\eta=\frac{D}{G\sqrt T}\Rightarrow\le\frac{DG}{\sqrt T}$ ; $T\ge(DG/\eps)^2$	balanced step; iteration count	same
$\Pi_K(u)=\arg\min_{z\in K}\norm{u-z}^2$	projection = nearest point	$K$ convex, closed
box: $\Pi_K(u)_i=\min\{b_i,\max\{a_i,u_i\}\}$	clip each coordinate	$K=\prod[a_i,b_i]$
$\norm{p-z}^2\le\norm{u-z}^2-\norm{u-p}^2$	projecting brings you closer to all of $K$	$p=\Pi_K(u)$ , $z\in K$ , $K$ convex
$x_{t+1}=\Pi_K(x_t-\eta\nabla f(x_t))$	projected GD; same $DG/\sqrt T$ bound	$x^*\in K$
$\norm{\nabla f(x)-\nabla f(y)}\le\beta\norm{x-y}$	β-smooth (gradient β-Lipschitz)	⇔ $\|f''\|\le\beta$ in 1-D
$f(y)\le f(x)+\langle\nabla f(x),y-x\rangle+\frac\beta2\norm{y-x}^2$	descent lemma: quadratic ceiling	β-smooth (no convexity needed)
$f(x_{t+1})\le f(x_t)-\frac1{2\beta}\norm{\nabla f(x_t)}^2$	safe step $\eta=1/\beta$	β-smooth
$f(x_T)-f^*\le\frac{\beta D^2}{2T}$ ; $T\ge\frac{\beta D^2}{2\eps}$	smooth GD theorem, last iterate	convex, β-smooth, $D$ , $\eta=1/\beta$
$y\ge0,\ A\T y\le c\Rightarrow c\T x\ge b\T y$	lower-bound certificate for $\min c\T x,\ Ax\ge b,\ x\ge0$	$x$ feasible
$\min\|e\|\leadsto\min t,\ t\ge\pm e$ ; $\min\max_ie_i\leadsto\min t,\ t\ge e_i$	linearization tricks	minimizing convex piecewise-linear objectives
$Ax\le b$ infeasible ⇔ $\exists y\ge0:\ A\T y=0,\ b\T y<0$	Farkas (inequality form)	$x$ free
$Ax\le b,\ x\ge0$ infeasible ⇔ $\exists y\ge0:\ A\T y\ge0,\ b\T y<0$	Farkas (canonical form)	always
$\min_{q\in\Delta_n}c\T q=\min_jc_j$	best response is pure	$\Delta_n$ = probability simplex
$\max_p\min_qp\T Aq\le\min_q\max_pp\T Aq$ (equality by duality)	weak / strong minimax	mixed strategies
$f(y)\ge f(x)+\langle\nabla f(x),y-x\rangle+\frac\alpha2\norm{y-x}^2$	α-strongly convex	⇔ $\nabla^2f\succeq\alpha I$
$f(x)-f^\le\langle\nabla f(x),x-x^\rangle-\frac\alpha2\norm{x-x^*}^2$	strengthened key inequality	α-strongly convex
$\sum_{t=1}^T\frac1t\le1+\ln T$	harmonic sum	always
$A(I)\le\alpha\opt(I)$ (min), $A(I)\ge\opt(I)/\alpha$ (max)	α-approximation	every instance, feasible output, poly time
PTAS: $(1+\eps)$ , poly $(n)$ per fixed $\eps$ ; FPTAS: poly $(n,1/\eps)$	approximation schemes	a family $A_\eps$
$\deg_{E_{t-1}}(v_t)\ge\lvert E_{t-1}\rvert/\opt$	greedy picks at least an OPT-th of what is left	max-degree greedy for vertex cover
$\lvert E_t\rvert\le m(1-\frac1\opt)^t\le me^{-t/\opt}$	multiplicative shrink, $1-x\le e^{-x}$	⇒ $\lvert S\rvert\le\opt(1+\ln m)$
$\lvert M\rvert\le\lvert C\rvert$ ; $\lvert C_{alg}\rvert=2\lvert M\rvert\le2\opt$	matching lower bound; 2-approximation	$M$ any matching, $C$ any cover; $M$ maximal for the algorithm
$\opt\le(L+1)\lvert A\rvert+\frac m{L+1}\le(2\sqrt m+1)a$	edge-disjoint paths, short/long split	$L=\lfloor\sqrt m\rfloor$
$\opt_{LP}\le\opt_{IP}$	relaxation is a lower bound	minimization
$\min\sum x_v,\ x_u+x_v\ge1,\ x\ge0$	vertex cover LP	optimal $x\in[0,1]^V$
$\hat x_v=\mathbb 1[x^_v\ge\frac12]\le2x^_v$	threshold rounding ⇒ $\lvert\hat C\rvert\le2\opt_{LP}\le2\opt$	also weighted ( $w\ge0$ )
$\sum_{i=1}^ka_i\ge1\Rightarrow\max_ia_i\ge\frac1k$	averaging principle ⇒ threshold $\frac1f$ gives an $f$ -approximation	$a_i\ge0$ ; $\le f$ variables per covering row
$\max\sum_ey_e,\ \sum_{e\ni v}y_e\le1,\ y\ge0$	dual of the vertex cover LP = fractional matching	integral $y$ = matching
$\opt(K_n)/\opt_{LP}(K_n)=\frac{n-1}{n/2}\to2$	integrality gap of the vertex cover LP	all $x_v=\frac12$
$\min\sum f_ix_i+\sum d_{ij}y_{ij},\ \sum_iy_{ij}=1,\ y_{ij}\le x_i$	facility location LP; $F^+D^\le\opt$	$x,y\ge0$
$L_j=\sum_id_{ij}y^_{ij}$ , $B_j=\{i:d_{ij}\le2L_j\}$ , $\sum_{i\in B_j}x^_i\ge\frac12$	average distance, ball, Markov	any feasible LP solution
$\text{cost}\le2F^+6D^\le6\opt$	facility location rounding	metric distances; clients by increasing $L_j$

I understand this unit

Unit 10.4 · Exam toolkit

Practice A: LP models, geometry, duality

Sources: L9–L10 exercises + added questions

Try each one before opening the answer. Questions marked ★ are new practice beyond the lecture exercises.

A1. Which are plain LP constraints/objectives:

3u-2v\ge7

;

uv\le5

; objective

u^2+v^2

;

v

free;

u\in\{0,1\}

;

u<2

?

Show answer

3u-2v\ge7

: yes (flip to ≤).

uv\le5

: no (product).

u^2+v^2

: no (quadratic, though convex).

v

free: yes, via

v=v^+-v^-

.

u\in\{0,1\}

: no (integer program).

u<2

: no (strict; the optimum might not be attained).

A2. Convert

\min(2u-v)

s.t.

u-v=3,\ u\ge0,\ v

free to canonical form and solve.

Show answer

See unit 1.5:

\max -2u+v^+-v^-

s.t.

u-v^++v^-\le3,\ -u+v^+-v^-\le-3

, all variables ≥ 0. Optimum

u=0,\ v=-3

, original min value 3.

A3. For

\max2x_1+3x_2

with

x_1+x_2\le5,\ x_1\ge1,\ x_2\ge0

: list the vertices, two independent tight constraints at each, and the optimum. What changes for objective

x_1+x_2

?

Show answer

(1,0)

:

x_1=1,\ x_2=0

, value 2.

(5,0)

:

x_1+x_2=5,\ x_2=0

, value 10.

(1,4)

:

x_1=1,\ x_1+x_2=5

, value 14 (optimum). For

x_1+x_2

the whole edge

(1,4)

–

(5,0)

is optimal with value 5. Two optimal vertices, infinitely many optimal points.

A4. Prove: with box bounds

0\le x_i\le1

and

k

other inequalities, any vertex has at most

k

fractional coordinates.

Show answer

See unit 2.6: rank count

n\le(n-q)+k

.

A5. Write

A,b,c

and the dual of the smoothie LP. Verify

x=(3,3,0),\ y=(5,0,2)

. Explain the unused banana and the missing smoothie 3 with complementary slackness.

Show answer

See unit 3.3 and 3.6. Both have value 27. Bananas are slack, so

y_B=0

. Smoothie 3's dual row is slack (

7>6

), so

x_3=0

.

A6. Verify

y=(3,1,2)

for the smoothie dual. What additive error guarantee does it give for

x=(3,3,0)

?

Show answer

Feasible (5≥5, 5≥4, 6≥6), value 31. Gap

31-27=4

, so

x

is within 4 of optimal, using this pair alone.

A7. Dual of

\max2u+v

s.t.

u+v\le4,\ u-v=1,\ u\ge0,\ v

free, and a matching pair.

Show answer

\min4\alpha+\beta

s.t.

\alpha+\beta\ge2,\ \alpha-\beta=1,\ \alpha\ge0,\ \beta

free. Pair:

(u,v)=(2.5,1.5)

,

(\alpha,\beta)=(1.5,0.5)

, value 6.5.

A8. Give an LP with a unique optimum and a tight primal row whose multiplier is 0 in an optimal dual. Why is this consistent with complementary slackness?

Show answer

\max x_1

s.t.

x_1\le1,\ x_2\le0,\ x\ge0

. Optimum

(1,0)

. Row 2 is tight, and the dual optimum

y=(1,0)

gives it multiplier 0. The product

0\cdot0=0

is fine. Slackness only forbids both factors being positive.

A9 ★. Write the dual of

\min2x_1+3x_2+x_3

s.t.

x_1+x_2+x_3\ge6,\ x_1-x_3=1,\ x_1,x_2\ge0,\ x_3\le0

. Solve both and check complementary slackness.

Show answer

Dual (max, by S-O-B): $\max6y_1+y_2$ s.t. $y_1+y_2\le2$ (col $x_1$ , sensible), $y_1\le3$ (col $x_2$ ), $y_1-y_2\ge1$ (col $x_3\le0$ , bizarre → ≥ in a max), $y_1\ge0$ (≥ row in a min, sensible), $y_2$ free.

Primal: $x_1=1+x_3$ with $x_3\in[-1,0]$ . Row 1: $x_2\ge5-2x_3$ . Cost $\ge17-3x_3$ , minimized at $x_3=0$ : $x=(1,5,0)$ , value 17. Dual: $y=(3,-1)$ : $3-1=2\le2$ , $3\le3$ , $3+1=4\ge1$ . Value $18-1=17$ . ✓ Slackness: $x_1,x_2>0$ and their dual rows are tight. ✓

A10 ★.

\max3x_1+2x_2

s.t.

x_1+x_2\le4,\ x_1+3x_2\le6,\ x_1\le3,\ x\ge0

. Someone claims

x=(3,1)

is optimal. Use complementary slackness to find a certificate.

Show answer

All three rows are tight at

(3,1)

(4, 6, 3), value 11.

x_1,x_2>0

force the dual rows tight:

y_1+y_2+y_3=3

,

y_1+3y_2=2

. This is degenerate (more tight rows than needed), so try

y_2=0

:

y_1=2,\ y_3=1

, all ≥ 0. Dual value

4\cdot2+6\cdot0+3\cdot1=11

. Matches, so

(3,1)

is optimal. (

y_3=0

would force

y_2=-\tfrac12<0

, which is infeasible. With degeneracy, try another choice.)

A11 ★. True or false? (a) Primal infeasible ⇒ dual unbounded. (b) If both primal and dual are feasible, both have optimal solutions with equal value. (c) Every optimal solution of an LP is a vertex. (d) If some optimal

y^*

has

y^*_j>0

, then row

j

is tight at every optimal

x

. (e) A vertex in

\R^n

has exactly

n

tight constraints.

Show answer

(a) False: both can be infeasible. (b) True: weak duality bounds both, so neither is unbounded. A feasible LP with a bounded objective attains its optimum, and strong duality makes the values equal. (c) False (optimal edges). (d) True: any optimal

x

and any optimal

y

form a zero-gap pair, so complementary slackness applies to every such pair. (e) False: at least

n

independent ones. Degenerate vertices have more.

A12 ★. Diet LP: foods

i

cost

c_i

per unit and contain

A_{ji}

units of nutrient

j

. You need at least

b_j

of each nutrient. Write the LP and its dual, and interpret the dual.

Show answer

Primal:

\min c\T x

s.t.

Ax\ge b,\ x\ge0

. Dual:

\max b\T y

s.t.

A\T y\le c,\ y\ge0

. Interpretation: a pill seller sets a price

y_j

per unit of nutrient

j

. To stay competitive, the nutrients in each food must not cost more than the food (

A\T y\le c

). The seller maximizes revenue

b\T y

from selling exactly your requirements. Strong duality: the best pill revenue equals the cheapest diet.

A13 ★. Show that

\max x_1+x_2

s.t.

x_1-x_2\le1,\ -x_1+x_2\le1,\ x\ge0

is unbounded, and conclude something about its dual without writing it.

Show answer

x_0=(0,0)

and ray

v=(1,1)

:

Av=(0,0)\le0

,

v\ge0

,

c\T v=2>0

. So

x_0+tv

is feasible for all

t\ge0

with objective

2t\to\infty

. By weak duality the dual must be infeasible. Check: the dual requires

y_1-y_2\ge1

and

-y_1+y_2\ge1

, whose sum is

0\ge2

, impossible.

A14 ★. A farmer mixes feeds: feed 1 costs $2/kg and has 3 units of protein and 1 of fat; feed 2 costs $5/kg and has 2 protein and 4 fat. The mix needs at least 12 protein and 8 fat. Write the LP, find a feasible plan, and prove it is optimal with a nonnegative combination of the constraints.

Show answer

\min 2x_1+5x_2

s.t.

3x_1+2x_2\ge12

,

x_1+4x_2\ge8

,

x\ge0

. Corners:

(0,6)

costs 30,

(8,0)

costs 16, and the intersection

3x_1+2x_2=12,\ x_1+4x_2=8

gives

x=(3.2,1.2)

, cost

6.4+6=12.4

. Certificate: at

(3.2,1.2)

both rows are tight and both

x_i>0

, so by complementary slackness try making both "coefficient" conditions tight:

3y_1+y_2=2

,

2y_1+4y_2=5

, giving

y=(0.3,1.1)\ge0

. Then

0.3(3x_1+2x_2)+1.1(x_1+4x_2)=2x_1+5x_2\ge0.3\cdot12+1.1\cdot8=12.4

for every feasible

x

. Optimal.

A15 ★. Write an LP for

\min_{x\in\R^2}\ |x_1-x_2|+|x_1+x_2-4|+|x_2-1|

. How many variables and constraints?

Show answer

\min t_1+t_2+t_3

s.t.

t_1\ge x_1-x_2

,

t_1\ge x_2-x_1

,

t_2\ge x_1+x_2-4

,

t_2\ge4-x_1-x_2

,

t_3\ge x_2-1

,

t_3\ge1-x_2

, with

x_1,x_2,t

free. 5 variables and 6 constraints. (Optimum 0 is impossible here, since it would need

x_1=x_2=1

and

x_1+x_2=4

. For example

x=(2,2)

gives

0+0+1=1

, and

x=(3,1)

gives

2+0+0=2

.)

A16 ★. Write an LP that finds

x\in\R^n

with

Ax\le b

minimizing the largest coordinate

\max_ix_i

.

Show answer

\min t

s.t.

x_i\le t

for all

i

,

Ax\le b

, with

t

and

x

free. At the optimum

t=\max_ix_i

.

A17 ★. Show that an algorithm for canonical LPs (

\max c\T x,\ Ax\le b,\ x\ge0

) can solve LPs of the form

\max c\T x

s.t.

Ax=b,\ x\ge0

.

Show answer

Replace

Ax=b

by

Ax\le b

and

-Ax\le-b

, i.e. the matrix

\binom{A}{-A}

and right side

\binom{b}{-b}

. The feasible sets are identical, so values and optimal solutions coincide. The size doubles, which is polynomial.

I understand this unit

Unit 10.5 · Exam toolkit

Practice B: flows, Farkas, strong duality

Sources: L10–L11 exercises + added questions

B1. What does primal unboundedness imply about the dual, and dual unboundedness about the primal? Can both be infeasible? Give the lecture example.

Show answer

Primal unbounded ⇒ dual infeasible. Dual unbounded ⇒ primal infeasible. Yes, both can be infeasible:

\max2x_1-x_2

s.t.

x_1-x_2\le1,\ -x_1+x_2\le-2,\ x\ge0

, whose dual needs

y_1-y_2\ge2

and

y_1-y_2\le1

.

B2. Write the edge-flow LP and the path-flow LP. Why do they have the same optimum? Which one has polynomial size?

Show answer

See 1.4 and 4.1. Path → edge by summing paths; edge → path by flow decomposition (cycles discarded). The edge LP is polynomial (

|E|

variables). The path LP can have exponentially many variables.

B3. Why does every

s

–

t

cut give a feasible

y\in\{0,1\}^E

? Why doesn't that alone finish max-flow/min-cut?

Show answer

Every path crosses out of

S

at least once, so it has length ≥ 1. This shows

\opt(D)\le

min cut. To get equality we must show some cut costs at most the fractional optimum, which is the threshold-rounding step.

B4. On

s\to a\to t

,

s\to b\to t

with

c_{sa}=3,c_{at}=2,c_{sb}=2,c_{bt}=3

and lengths

.4,.6,.7,.3

: compute the clipped distances, all threshold cuts, the average capacity, and a matching max flow.

Show answer

\ell=(0,.4,.7,1)

for

(s,a,b,t)

. Cuts 5, 4, 5 on intervals of length .4, .3, .3. Average 4.7 =

\sum c_ey_e

. Best cut

\{s,a\}

= 4. Flow 2+2 = 4 matches.

B5. How does one shortest-path computation verify all path constraints of

D_\text{length}

? What if

t

is unreachable?

Show answer

Dijkstra with lengths

y\ge0

. If

d(t)\ge1

, all constraints hold. Otherwise the shortest path is a violated constraint. Unreachable

t

means

d(t)=\infty

: there are no paths and nothing is violated.

B6. For

a_1=(1,0),\ a_2=(1,1),\ p=(0,1)

show

p\notin

cone and give a witness.

Show answer

Cone points have first coordinate ≥ second.

w=(1,-1)

:

a_1\T w=1

,

a_2\T w=0

,

p\T w=-1

.

B7 ★. Same generators,

p=(-1,2)

. In the cone? If not, give a witness and the nearest cone point.

Show answer

(\lambda_1+\lambda_2,\lambda_2)=(-1,2)

forces

\lambda_2=2,\ \lambda_1=-3<0

, so not in the cone. Witness

w=(1,-1)

:

1\ge0,\ 0\ge0

,

p\T w=-3<0

. Nearest point: project

p

onto the ray of

a_2

:

\frac{p\T a_2}{\norm{a_2}^2}a_2=\tfrac12(1,1)

. Then

v=p-q=(-1.5,1.5)

and

-v=(1.5,-1.5)

is a positive multiple of

w

.

B8 ★. Separation:

C

= unit disk,

p=(3,4)

. Find

q

,

v

, and check

v\T z\le v\T q

for all

z\in C

.

Show answer

q=p/\norm p=(0.6,0.8)

,

v=(2.4,3.2)

.

v\T q=1.44+2.56=4

. Over the disk

\max v\T z=\norm v=4

(Cauchy–Schwarz), so

v\T z\le4

.

v\T p=7.2+12.8=20>4

.

B9. Rebuild the strong-duality proof: at an optimal

x^*

, suppose

c

is not a nonnegative combination of active normals. What does Farkas give, how do you choose

\eps

, and how does the cone identity produce a dual of the same value?

Show answer

Farkas:

w

with

a_r\T w\ge0

(tight

r

),

c\T w<0

. Set

v=-w

. Then

\eps=\min\{\delta_r/a_r\T v:\ r\text{ slack},\ a_r\T v>0\}

(or any positive number if no such row), and

x^*+\eps v

is feasible and better, a contradiction. So

c=A\T y-z

with

y,z\ge0

supported on tight rows. Then

y

is dual feasible and

c\T x^*=b\T y

. See 5.6–5.7.

B10 ★. Why must the strong-duality argument include the normals of

-x_i\le0

? Give an example.

Show answer

\max(-x)

s.t.

x\le1,\ x\ge0

: at

x^*=0

the only tight constraint is

-x\le0

with normal

-1

, and

c=-1

is in its cone. Without it, the tight set is empty, the cone is

\{0\}

, and

c\notin\{0\}

would wrongly "prove"

x^*

is not optimal.

B11 ★. Explain in one paragraph why rounding loses nothing for min-cut but might for other problems.

Show answer

For cuts, the averaging argument shows that a random threshold's expected cut cost is at most the fractional cost, so some threshold cut is no worse and the 0/1 and fractional optima coincide. For problems like vertex cover, the LP optimum can be strictly smaller than every integral solution (a triangle has fractional cover

3/2

and integral cover 2). Then any rounding must lose something, and approximation algorithms bound the loss by a factor.

B12 ★. Show that

x_1+x_2\le2,\ -x_1\le-2,\ -x_2\le-1

(with

x

free) is infeasible by giving a Farkas certificate of the form (F3).

Show answer

Take

y=(1,1,1)\ge0

.

A\T y

: first column

(1,-1,0)\cdot y=0

, second

(1,0,-1)\cdot y=0

. So

A\T y=0

.

b\T y=2-2-1=-1<0

✓. Adding the three rows gives

0\le-1

.

B13 ★. Find the value and optimal mixed strategies of the game

A=\begin{pmatrix}2&-1\\-1&1\end{pmatrix}

(Alice picks the row).

Show answer

Alice plays row 1 with probability

p

. Her payoff against column 1 is

2p-(1-p)=3p-1

, against column 2 it is

-p+(1-p)=1-2p

. Her guarantee is

\min(3p-1,1-2p)

, maximized where they are equal:

p=\tfrac25

, value

\tfrac15

. Bob plays column 1 with probability

q

: row payoffs

3q-1

and

1-2q

, and the max is minimized at

q=\tfrac25

, also

\tfrac15

. Both guarantees are

\tfrac15

: the value is

\tfrac15

, with

p^*=q^*=(\tfrac25,\tfrac35)

.

B14 ★. Why is

\min_{q\in\Delta_n}c\T q=\min_jc_j

? Why does this matter for writing a game as an LP?

Show answer

c\T q

is a weighted average of the

c_j

(weights

q_j\ge0

, sum 1), so it is at least

\min_jc_j

, with equality at

q=e_{j^*}

. It replaces a minimization over infinitely many mixed strategies by finitely many linear constraints (one per pure column).

I understand this unit

Unit 10.6 · Exam toolkit

Practice C: convexity and gradient descent

Sources: L12 exercises + added questions

C1. Prove the first-order inequality from the chord definition, then set

y=x^*

.

Show answer

See 6.3. Divide by

\theta

and let

\theta\downarrow0

. Result:

f(x)-f(x^*)\le\langle\nabla f(x),x-x^*\rangle

.

C2. Prove local ⇒ global for convex

f,K

. Must a constrained differentiable optimum satisfy

\nabla f=0

?

Show answer

See 6.7. No:

\min_{[0,1]}x

is at 0 with

f'(0)=1

.

C3. Gradient and Hessian of

\tfrac12\norm{Ax-b}^2

. Prove convexity and explain the transpose.

Show answer

A\T(Ax-b)

and

A\T A

.

v\T A\T Av=\norm{Av}^2\ge0

. The transpose maps residuals (

m

-dimensional) back to variable space (

d

-dimensional).

C4. For

f(x)=x^2/2

, classify all

\eta>0

.

Show answer

(0,1)

: monotone convergence.

1

: one step.

(1,2)

: alternating convergence.

2

: oscillation.

>2

: divergence.

C5. Reproduce the convergence proof, stating which iterates are averaged.

Show answer

See 7.4–7.5. Average of

x_0,\dots,x_{T-1}

.

C6.

D=2,G=3,T=900

: find

\eta

and the error.

T

for

\eps=0.1

?

Show answer

\eta=1/45

, error ≤ 0.2.

T\ge3600

,

\eta=1/90

.

C7. Prove that the average of

T

points in a convex set is in the set, and prove the many-point convexity inequality.

Show answer

Induction.

\bar x_T=\frac{T-1}T\bar x_{T-1}+\frac1Tx_{T-1}

is a two-point blend, so it stays in the set and

f(\bar x_T)\le\frac{T-1}Tf(\bar x_{T-1})+\frac1Tf(x_{T-1})\le\frac1T\sum f(x_t)

.

C8. A student claims: "convexity alone gives a bounded

G

; the theorem guarantees the last iterate;

T

iterations means

O(T)

total time; the approximation is multiplicative." Fix all four.

Show answer

(1) No:

x^2/2

has unbounded gradient.

G

is an assumption on the iterates. (2) No: average (or best) of the queried points. (3) No:

T\times

(cost per gradient +

O(d)

), e.g.

O(Tmd)

for least squares. (4) No: additive,

f(\bar x)-f(x^*)\le\eps

.

C9 ★. Which are convex on their domain? (a)

\max(x^2,1-x)

(b)

e^x+|x|

(c)

x_1x_2

on

\R^2

(d)

-\log x

on

x>0

(e)

\min(x,0)

(f)

\mathrm{dist}(x,[0,1])

(g)

x^2-|x|

Show answer

(a) yes (max of convex). (b) yes (sum). (c) no: Hessian

\begin{pmatrix}0&1\\1&0\end{pmatrix}

has eigenvalue −1. (d) yes (

f''=1/x^2>0

). (e) no: it is concave (min of linear functions), with a corner pointing up. (f) yes (partial minimization). (g) no: two dips at

\pm\tfrac12

.

C10 ★. Is

f(x,y)=x^2+3xy+y^2

convex?

Show answer

H=\begin{pmatrix}2&3\\3&2\end{pmatrix}

.

\det=4-9<0

, so one eigenvalue is negative and

f

is not convex. Direction

v=(1,-1)

:

v\T Hv=2-6+2=-2<0

.

C11 ★.

D=10

,

G=1

, target

\eps=0.01

. How many iterations and which

\eta

?

Show answer

T\ge(10\cdot1/0.01)^2=10^6

.

\eta=10/(1\cdot1000)=0.01

.

C12 ★. Subgradient descent on

f(x)=|x|

from

x_0=0.25

with

\eta=0.1

, using

g=\operatorname{sign}(x)

(and

g=1

at 0). Compute a few iterates. What do the last iterate, the best iterate and the average do? Compare with the bound.

Show answer

0.25\to0.15\to0.05\to-0.05\to0.05\to-0.05\dots

The last iterate never converges (it bounces with error 0.05). The best iterate has error 0.05. The average tends to ≈ 0. Bound with

D=0.25,\ G=1

:

\frac{0.0625}{0.2T}+0.05

. The floor

\eta G^2/2=0.05

is exactly the bounce size, the "discrete step penalty" made visible. To shrink it, take smaller

\eta

(and more steps).

C13 ★. Why can the analysis use

x^*

though the algorithm cannot?

Show answer

The algorithm's steps only use gradients at its own iterates.

x^*

appears only in the potential

R_t

used to reason about those iterates. Any fixed reference point is allowed in a proof. We pick a minimizer because that turns the inner product into the objective error.

C14 ★. Show that

\eta=D/(G\sqrt T)

minimizes

h(\eta)=\frac{D^2}{2\eta T}+\frac{\eta G^2}2

. What happens to the bound if you use

2\eta^\star

instead?

Show answer

h'(\eta)=-\frac{D^2}{2\eta^2T}+\frac{G^2}2=0

gives

\eta^\star

, and

h''>0

. With

2\eta^\star

: first term

\frac{DG}{4\sqrt T}

, second

\frac{DG}{\sqrt T}

, total

1.25\frac{DG}{\sqrt T}

, only 25% worse. The bound is not very sensitive to a constant-factor error in

\eta

.

I understand this unit

Unit 10.7 · Exam toolkit

Practice D: projections and smoothness (L13)

Sources: Lec13 + added questions

D1. Project

u=(5,-1)

onto the box

[0,2]\times[0,3]

, and

u=(3,4)

onto the unit ball.

Show answer

Box: clip each coordinate:

\min\{2,\max\{0,5\}\}=2

,

\min\{3,\max\{0,-1\}\}=0

, so

(2,0)

. Ball:

\norm u=5>1

, so

u/\norm u=(0.6,0.8)

.

D2. Prove: if

p=\Pi_K(u)

for convex

K

, then

\norm{p-z}^2\le\norm{u-z}^2-\norm{u-p}^2

for all

z\in K

.

Show answer

See unit 8.3:

f(\theta)=\norm{u-p-\theta(z-p)}^2

is minimized at

\theta=0

over

[0,1]

(convexity keeps

p+\theta(z-p)\in K

), so

f'(0^+)=2\langle u-p,p-z\rangle\ge0

. Expand

\norm{u-z}^2=\norm{u-p}^2+\norm{p-z}^2+2\langle u-p,p-z\rangle

.

D3. Why does projected GD keep the L12 bound? Where exactly is

x^*\in K

used? Why is the output feasible?

Show answer

Only the first line changes:

R_{t+1}=\norm{\Pi_K(y_{t+1})-x^*}^2\le\norm{y_{t+1}-x^*}^2

, the projection inequality with

z=x^*

. That needs

x^*\in K

. The rest of the proof (convexity,

G

, telescoping, Jensen) is identical. The average of points of the convex set

K

lies in

K

.

D4. Projected GD:

\min_{x\in[0,1]}(x-3)^2

,

x_0=0

,

\eta=0.25

. Compute two steps. Is the gradient zero at the optimum?

Show answer

f'(x)=2(x-3)

.

t=0

:

y=0-0.25\cdot(-6)=1.5

, projected to 1.

t=1

:

y=1-0.25\cdot(-4)=2

, projected to 1. The method sits at

x^*=1

, where

f'(1)=-4\neq0

: a boundary optimum with nonzero gradient.

D5. Which are β-smooth on

\R

, and with which β?

x^2/2

,

|x|

,

\tfrac52(x-1)^2

,

\log(1+e^x)

,

x^4

,

\sin x

.

Show answer

x^2/2

: β=1.

|x|

: no.

\tfrac52(x-1)^2

: β=5. Softplus: β=1/4.

x^4

: no (

f''

unbounded).

\sin x

: β=1, but it is not convex.

D6. Prove the descent lemma. What is

s

and why is it there?

Show answer

See unit 8.6.

s\in[0,1]

parametrizes the segment from

x

to

y

, turning

f

into the 1-D function

g(s)=f(x+s(y-x))

, so the fundamental theorem of calculus applies. Then Cauchy–Schwarz and smoothness bound the integrand by

\beta s\norm{y-x}^2

, and

\int_0^1 s\,ds=\tfrac12

.

D7. For which step sizes does the descent lemma guarantee

f(x_{t+1})<f(x_t)

(when

\nabla f(x_t)\neq0

)? Which step maximizes the guaranteed decrease?

Show answer

f(x_{t+1})\le f(x_t)-\eta(1-\beta\eta/2)\norm{g}^2

. The decrease is positive for

0<\eta<2/\beta

. The factor

\eta(1-\beta\eta/2)

is maximized at

\eta=1/\beta

, with value

1/(2\beta)

.

D8. Reproduce the proof of

f(x_T)-f^*\le\beta D^2/(2T)

. Where are convexity, smoothness and monotonicity each used?

Show answer

Smoothness: safe step

f(x_{t+1})\le f(x_t)-\frac1{2\beta}\norm{g_t}^2

. Convexity:

f(x_t)-f^*\le\langle g_t,x_t-x^*\rangle

. Algebra:

\langle g_t,x_t-x^*\rangle-\frac1{2\beta}\norm{g_t}^2=\frac\beta2(R_t-R_{t+1})

. Telescope to

\frac\beta2R_0\le\frac{\beta D^2}2

. Monotonicity (from the safe step): the sum of

T

errors is

\ge T(f(x_T)-f^*)

.

D9.

\beta=4

,

D=3

,

\eps=0.01

. How many steps does smooth GD need? How many would the bounded-gradient method need if

G=2

?

Show answer

Smooth:

T\ge\beta D^2/(2\eps)=36/0.02=1800

. Bounded gradients:

T\ge(DG/\eps)^2=(6/0.01)^2=360{,}000

.

D10. A summary table claims the bounded-gradient method needs

O(\sqrt{\eps^{-1}})

steps. Is that right? Explain.

Show answer

DG/\sqrt T\le\eps\iff T\ge(DG/\eps)^2

, so

O(\eps^{-2})

. It must be slower than the smooth

O(\eps^{-1})

, because it uses weaker assumptions.

D11. GD with

\eta=1/\beta

on

f=\tfrac12(x_1^2+4x_2^2)

from

x_0=(2,1)

: compute

x_1,x_2

, their errors, and the bound.

Show answer

\beta=4

,

\eta=1/4

:

x_1=(1.5,0)

,

f=1.125

;

x_2=(1.125,0)

,

f\approx0.633

.

D^2=5

, bound

\beta D^2/(2T)=10/T

: 10 and 5. Valid but loose.

D12. True or false? (a) β-smooth ⇒ convex. (b) For convex β-smooth

f

with

\eta=1/\beta

,

f(x_t)

is nonincreasing. (c) The smooth theorem needs a gradient bound

G

. (d) The projection argument works for any closed set. (e) The safe step needs

T

in advance.

Show answer

(a) False (

\sin x

). (b) True (safe-step inequality; convexity not even needed). (c) False. (d) False: it needs convexity (the segment from

p

to

z

must stay in

K

). (e) False:

\eta=1/\beta

does not depend on

T

, unlike

D/(G\sqrt T)

.

D13 ★. Give the strong convexity constant α (or say "not strongly convex"):

3x^2

;

x^2+|x|

;

\tfrac12(x_1^2+9x_2^2)

;

\log(1+e^x)

;

\tfrac12\norm{Ax-b}^2

with

A=\begin{pmatrix}1&0\\0&2\end{pmatrix}

.

Show answer

3x^2

:

f''=6

, α=6.

x^2+|x|

:

x^2

is 2-strongly convex and

|x|

is convex, so α=2.

\tfrac12(x_1^2+9x_2^2)

: Hessian diag(1,9), α=1 (and β=9). Softplus:

f''\to0

at ±∞, not strongly convex.

A\T A=\mathrm{diag}(1,4)

, α=1.

D14 ★.

f

is 2-strongly convex with unconstrained minimizer

x^*

, and

f(x)-f(x^*)\le0.01

. How close is

x

to

x^*

?

Show answer

Quadratic growth:

\frac\alpha2\norm{x-x^*}^2\le f(x)-f(x^*)\le0.01

, so

\norm{x-x^*}^2\le0.01

and

\norm{x-x^*}\le0.1

.

D15 ★. Prove that an α-strongly convex differentiable

f

on

\R^d

has at most one minimizer.

Show answer

If

x^*

and

y^*

both minimize, then

\nabla f(x^*)=0

and the definition gives

f(y^*)\ge f(x^*)+\frac\alpha2\norm{y^*-x^*}^2

. Since

f(y^*)=f(x^*)

, this forces

\norm{y^*-x^*}=0

.

D16 ★. Verify the regrouping identity

\sum_{t=0}^{T-1}(a_tR_t-b_tR_{t+1})=a_0R_0+\sum_{t=1}^{T-1}(a_t-b_{t-1})R_t-b_{T-1}R_T

and say when the middle terms can be dropped.

Show answer

Shift the index in the second sum:

\sum_{t=0}^{T-1}b_tR_{t+1}=\sum_{t=1}^{T}b_{t-1}R_t

. Collect the coefficient of each

R_t

. The middle terms are

\le0

(droppable in an upper bound) when

a_t\le b_{t-1}

and

R_t\ge0

. The last term

-b_{T-1}R_T\le0

can be dropped when

b_{T-1}\ge0

.

I understand this unit

Unit 10.8 · Exam toolkit

Practice E: approximation algorithms (L14–L15)

Sources: L14–L15 + added questions

Questions marked ★ go beyond the lecture examples. None of them needs anything outside Chapter 9.

E1. State what an α-approximation is for a minimization and for a maximization problem. Why is α ≥ 1? What does a 3-approximation for a maximization problem guarantee?

Show answer

Min: on every instance the output is feasible and costs

A(I)\le\alpha\,\opt(I)

. Max: value

A(I)\ge\opt(I)/\alpha

. For min, every feasible solution costs at least OPT, so

\opt\le A(I)\le\alpha\opt

forces

\alpha\ge1

(similarly for max). A 3-approximation for max returns at least a third of the optimal value on every input.

E2. Which are PTAS running times, and which are FPTAS? (a)

n^{2/\eps}

(b)

n^4/\eps^2

(c)

3^{1/\eps}n^2

(d)

(n/\eps)^3

Show answer

(a) PTAS, not FPTAS (degree grows with

1/\eps

). (b) FPTAS. (c) PTAS, not FPTAS (exponential in

1/\eps

). (d) FPTAS. Every FPTAS is also a PTAS.

E3 ★. Run greedy-by-degree on the spider with four legs

c-a_i-b_i

,

i=1,\dots,4

. Compare with OPT and check the claim

\deg(v_t)\ge\lvert E_{t-1}\rvert/\opt

at every step.

Show answer

m=8

,

\opt=4

(

\{a_1,\dots,a_4\}

; the four edges

a_ib_i

are a matching, so no cover is smaller). Step 1:

c

has degree 4 (unique max) ≥ 8/4 = 2 ✓. Then 4 disjoint edges remain; each step picks degree 1, and

1\ge\lvert E\rvert/4

for

\lvert E\rvert=4,3,2,1

✓. Greedy uses 5 vertices. The bound

8(3/4)^t

drops below 1 at

t=8

, consistent with

\lfloor4\ln8\rfloor+1=9

.

E4. Prove: if

S^*

is an optimal cover and

E'

is any set of remaining edges, some vertex has at least

\lvert E'\rvert/\opt

edges of

E'

.

Show answer

Every edge of

E'

has an endpoint in

S^*

, so

\sum_{c\in S^*}\deg_{E'}(c)\ge\lvert E'\rvert

. The largest of these

\opt

numbers is at least their average,

\lvert E'\rvert/\opt

.

E5. From

\lvert E_t\rvert\le m\,e^{-t/\opt}

, show the greedy loop runs at most

\lfloor\opt\ln m\rfloor+1

times. Why is integrality needed?

Show answer

For

t=\lfloor\opt\ln m\rfloor+1>\opt\ln m

we get

m e^{-t/\opt}<me^{-\ln m}=1

, so

\lvert E_t\rvert<1

. The bound itself is never 0. Only because

\lvert E_t\rvert

is a nonnegative integer can we conclude

\lvert E_t\rvert=0

, i.e. the loop has stopped. Each iteration adds one vertex, so

\lvert S\rvert\le t

.

E6. On the path

a-b-c-d

, what can the matching algorithm return? Compare with OPT and with the maximum matching.

Show answer

If it picks

bc

first, both other edges are removed:

C=\{b,c\}

, size 2 = OPT, but

\lvert M\rvert=1<2=

maximum matching. If it picks

ab

first,

cd

remains and is picked:

C=\{a,b,c,d\}

, size 4 = 2·OPT. Both outcomes respect

\lvert M\rvert\le\opt\le\lvert C\rvert=2\lvert M\rvert

.

E7. Prove that every matching is at most every vertex cover. Does this need the cover to be minimal or the matching to be maximal?

Show answer

Each matching edge has an endpoint in the cover. Choose one such endpoint per edge. Distinct matching edges share no endpoint, so the chosen vertices are distinct: an injection from

M

into

C

. Neither minimality nor maximality is needed.

E8 ★. Give an infinite family of graphs on which the matching algorithm always returns exactly 2·OPT, whatever edges it picks.

Show answer

k

disjoint edges: the algorithm must pick every edge (each is its own component), returns

2k

, while

\opt=k

. Another family:

K_{n,n}

, where every maximal matching is perfect, so the output is all

2n

vertices and

\opt=n

.

E9 ★. Show that any maximal matching

M

has at least half as many edges as a maximum matching

M^*

.

Show answer

Every edge of

M^*

shares an endpoint with some edge of

M

(maximality). An edge

\{u,v\}\in M

has two endpoints, and each endpoint lies on at most one edge of

M^*

, so at most 2 edges of

M^*

are charged to it. Hence

\lvert M^*\rvert\le2\lvert M\rvert

: the same disjointness argument gives a 2-approximation for maximum matching.

E10. Write the IP and the LP relaxation for vertex cover, and prove that an optimal LP solution never has a coordinate above 1.

Show answer

\min\sum_vx_v

s.t.

x_u+x_v\ge1

for each edge,

x\ge0

, plus

x\in\Z^V

for the IP. If

x_v>1

, lowering it to 1 keeps every constraint (

1+x_u\ge1

) and strictly lowers the objective, so such a point is not optimal. (With weights

w_v\ge0

: lowering never increases the cost, so some optimal solution lies in

[0,1]^V

.)

E11. Find

\opt_{LP}

and OPT for the 5-cycle and for

K_4

. What does threshold rounding return from the all-½ solution? Check the 2-approximation bound.

Show answer

C_5

: all ½ gives 5/2. Summing the 5 edge constraints gives

2\sum x\ge5

, so

\opt_{LP}=\frac52

. OPT = 3. Rounding keeps all 5 vertices:

5\le2\cdot\frac52=5\le2\cdot3

.

K_4

:

\opt_{LP}=2

(all ½; summing the 6 constraints gives

3\sum x\ge6

), OPT = 3, rounding keeps 4 ≤ 4.

E12. Why can a threshold of 0.6 make vertex cover rounding infeasible? What happens with 0.4?

Show answer

An edge may have

x^*_u=x^*_v=\frac12

(e.g. a single edge or a triangle). With threshold 0.6 both endpoints are dropped and the edge is uncovered. With 0.4 the rounding is still feasible (the larger value is ≥ ½ ≥ 0.4), but each kept vertex now only satisfies

\hat x_v\le x^*_v/0.4

, so the guarantee weakens to 2.5.

E13. Write the dual of the weighted vertex cover LP

\min\sum_vw_vx_v

s.t.

x_u+x_v\ge1,\ x\ge0

. Interpret it.

Show answer

\max\sum_ey_e

s.t.

\sum_{e\ni v}y_e\le w_v

for every vertex,

y\ge0

. Edges receive "payments"

y_e

, and the total payment at a vertex cannot exceed its weight. Any such

y

lower-bounds the cheapest cover by weak duality. With unit weights and integral

y

it is a matching.

E14. Derive the vertex cover dual by the multiplier method (no rulebook) and explain where

\sum_{e\ni v}

comes from.

Show answer

Multiply each edge constraint

x_u+x_v\ge1

by

y_e\ge0

and add:

\sum_ey_e(x_u+x_v)\ge\sum_ey_e

. Regroup the left side by vertex:

x_v

appears once for every edge at

v

, giving

\sum_vx_v\sum_{e\ni v}y_e

. If

\sum_{e\ni v}y_e\le1

for all

v

, then

\sum_vx_v\ge\sum_vx_v\sum_{e\ni v}y_e

(as

x\ge0

), so

\sum_vx_v\ge\sum_ey_e

. The best such bound is the dual.

E15 ★. Is the odd cycle

C_{2k+1}

a good example of a large integrality gap for vertex cover?

Show answer

No.

\opt_{LP}=\frac{2k+1}2

(all ½, and summing the constraints gives

2\sum x\ge2k+1

) and

\opt=k+1

, so the ratio

\frac{2k+2}{2k+1}\to1

. The complete graph

K_n

gives

\frac{n-1}{n/2}\to2

.

E16 ★. In a set cover instance every element lies in at most

f

sets. Give an LP-rounding

f

-approximation in steps.

Show answer

(1) IP:

\min\sum_Sc_Sx_S

s.t.

\sum_{S\ni e}x_S\ge1

for each element

e

,

x\in\{0,1\}

. (2) Relax to

x\ge0

and solve:

\opt_{LP}\le\opt

. (3) Round

\hat x_S=1

iff

x^*_S\ge\frac1f

. (4) Feasible: the at most

f

values in each row add up to ≥ 1, so the largest is ≥

\frac1f

. (5) Cost:

\hat x_S\le fx^*_S

, so

\sum c_S\hat x_S\le f\opt_{LP}\le f\opt

.

E17. In the facility location IP, explain

y_{ij}\le x_i

and

\sum_iy_{ij}=1

. Why are upper bounds

x,y\le1

unnecessary in the relaxation?

Show answer

y_{ij}\le x_i

: a client cannot be assigned to a closed facility (

x_i=0\Rightarrow y_{ij}=0

).

\sum_iy_{ij}=1

: every client is assigned to exactly one facility.

y_{ij}\le1

follows from the sum constraint and

y\ge0

, and any

x_i>\max_jy_{ij}

can be lowered to

\max_jy_{ij}\le1

without increasing the cost.

E18. Prove that at least half of client

j

's LP assignment lies in

B_j=\{i:d_{ij}\le2L_j\}

.

Show answer

For

i\notin B_j

,

d_{ij}>2L_j

, so

y^*_{ij}\le\frac{d_{ij}}{2L_j}y^*_{ij}

. Summing over

i\notin B_j

:

\sum_{i\notin B_j}y^*_{ij}\le\frac1{2L_j}\sum_id_{ij}y^*_{ij}=\frac12

. Since the

y^*_{ij}

sum to 1,

\sum_{i\in B_j}y^*_{ij}\ge\frac12

, and

x^*_i\ge y^*_{ij}

gives the same for

x^*

. (If

L_j=0

, all mass is at distance 0, inside

B_j

.)

E19 ★. In the facility location rounding, which step breaks if clients are processed in an arbitrary order instead of by increasing

L_j

?

Show answer

The connection bound for a non-representative:

d(j,i_r)\le2L_j+2L_r+2L_r

. Sorting gives

L_r\le L_j

, hence

\le6L_j

. In another order

L_r

could be much larger than

L_j

, and client

j

could be sent far away. The opening-cost bound (disjoint balls, ball mass ≥ ½) does not need the order.

E20 ★. Why does the edge-disjoint paths algorithm use the cutoff

L\approx\sqrt m

?

Show answer

Each greedy path can block about

L

short optimal paths (charging), and there are at most

m/(L+1)

long optimal paths (edge-disjointness). The bound

\opt\le(L+1)a+\frac m{L+1}

is smallest in order of magnitude when

L\approx m/L

, i.e.

L\approx\sqrt m

, giving

O(\sqrt m)

.

I understand this unit

Unit 10.9 · Exam toolkit

Coverage checklist

Sources: Lec_9_SecB, Lec10_SecB, Lec11_SecB, Lec12_secB, Lec12_Unmarked, Lec13_SecA, Lec13_Unmarked, Lec14_SecB, Lec14 unmarked, Lec15_SecB, Lec15_Unmarked, L14 and L15 recordings, Part 2 class notes (60 pp.), Homework 3

Use this page to check that you can do everything Part 2 asks for. Each line links to the unit that covers it.

1 · Sources and where they are covered

Source	Content	Units
Lecture 9	Part 2 overview; LP definition and dimensions; smoothie model; max-flow LP; equivalent forms; convex sets; 2-D picture; three outcomes; tight constraints and vertices; basic optimal solution; polynomial solvability and Cramer; box-constraint exercise; first certificate	0.1, 1.1–1.5, 2.1–2.6, 3.1
Lecture 10	certificates; dual derivation; weak and strong duality; smoothie dual and prices; infeasible vs unbounded; dual rulebook (exam question); path LP; length dual; threshold rounding; averaging; max-flow = min-cut; Dijkstra check	3.1–3.7, 4.1–4.5
Lecture 11	proof plan; free-variable split; cones and Farkas; separation; cone case; active-constraint argument; dual construction; summary; exercises	1.5, 5.1–5.7, 3.6
Lecture 12 (typed + board)	offline problem; convex functions; first-order and Hessian tests; max of convex and partial minimization; least squares; local = global; steepest descent; step sizes; bounded-gradient theorem and proof; subgradients; scope	6.1–6.7, 7.1–7.8
Lecture 13 (board + typed)	projection and box example; projection inequality; projected GD; β-smoothness; descent lemma; safe step; smooth convex theorem; comparison table; caveats	8.1–8.9
Lecture 14 (board, typed, recording)	α-approximation; PTAS/FPTAS; hierarchy and TSP remark; vertex cover; greedy by degree and the $O(\log n)$ proof; matchings as lower bounds; maximal-matching 2-approximation; tight example; duality connection; edge-disjoint paths (posted notes)	9.1–9.6
Lecture 15 (board, typed, recording)	IP vs LP picture; rounding template; vertex cover IP and claims; threshold rounding and its proof; averaging idea flagged for the exam; dual = matching; integrality gap; facility location model, $L_j$ , balls, Markov lemma, rounding algorithm (6-approximation stated); exam-scope announcement	9.7–9.14
Homework 3 topics	min-LP certificates; LP modeling tricks and reductions; Farkas variants; zero-sum games; operations on convex sets/functions; strong convexity and varying step sizes	3.1, 1.6, 5.5, 3.8, 2.1, 6.5, 8.10

2 · Skills checklist

You should be able to do each of these without looking.

Skill	Where
Read any LP formula: rows vs columns, dimensions, coordinatewise inequalities, transpose	0.2, 1.1
Model a word problem as an LP (max or min), and justify the model both ways	1.2, 1.3, 1.4
Linearize $\|\cdot\|$ , $\max$ , $\min$ objectives; know when this is impossible	1.6
Convert between LP forms; argue a reduction between forms is correct and polynomial	1.5, 1.6
Prove a set is convex / give a counterexample; intersections, unions, affine images	2.1
Solve a 2-D LP graphically; identify vertices by independent tight constraints	2.2, 2.4
Classify an LP as infeasible / unbounded / finite; prove unboundedness with a ray	2.3
Explain why an optimal vertex exists and why the answer has polynomial bit length	2.5, 2.6
Prove optimality with a certificate, for max and min problems	3.1
Derive the dual from scratch and with the rulebook / S-O-B, for any mixed form	3.2, 3.5
State and prove weak duality; state strong duality; know the possible status pairs	3.3, 3.4
Use complementary slackness to find or verify optimal solutions	3.6
Use a duality gap as an additive error certificate	3.7
Set up zero-sum games, mixed strategies, max-min vs min-max; best responses are pure	3.8
Write the path LP and length dual; turn a cut into a dual solution	4.1, 4.2
Threshold rounding and the averaging argument; prove max-flow = min-cut via duality	4.3–4.5
Check exponentially many constraints with a separation oracle (Dijkstra)	4.5
State Farkas' lemma (all forms), give certificates, convert between forms	5.2, 5.5
Prove separation from the nearest point; derive Farkas from separation	5.3, 5.4
Reproduce the strong duality proof (tight normals, ε step, dual construction)	5.1, 5.6, 5.7
Prove a function is convex (chord, tangent, Hessian, operations) or refute it, without assuming differentiability	6.2–6.5
Prove the first-order condition (both directions) and local = global	6.3, 6.7
Compute gradients and Hessians (least squares and other quadratics)	0.3, 6.6
Explain steepest descent and step-size behaviour	7.1, 7.2
Prove the $DG/\sqrt T$ theorem; compute η, error and T	7.3–7.6
Projections (box, ball, halfspace), the projection inequality, projected GD	8.2–8.4
Smoothness, descent lemma, safe step, the $\beta D^2/(2T)$ theorem	8.5–8.8
Strong convexity: definition, tests, consequences, varying step sizes, harmonic sums, weighted telescoping	8.10, 0.3
Define α-approximation (min and max), PTAS, FPTAS; classify running times	9.2
Run greedy-by-degree; prove the $\opt(1+\ln m)$ bound (claim, shrink, $1-x\le e^{-x}$ , integrality)	9.4
Prove every matching ≤ every cover; analyze the maximal-matching 2-approximation; give tight examples	9.5
Model a selection problem as a 0/1 IP, relax it, and explain $\opt_{LP}\le\opt$	9.7, 9.8
Threshold rounding for vertex cover (feasibility + cost); generalize to weights and to $f$ variables per constraint	9.9, 9.10
Write the dual of the vertex cover LP; explain why integral duals are matchings	9.11
Integrality gap of $K_n$ ; distinguish tight examples, gaps, and hardness	9.12
Facility location: IP, relaxation, $L_j$ , balls, the ball lemma, the rounding algorithm (and the 6-approximation proof)	9.13–9.15

3 · Homework 3 map (concepts only, no solutions)

Problem	What you need	Units
Fruit-party LP (write it, feasible point, lower bound)	modeling a min LP with ≥ constraints; checking feasibility; lower-bound certificate from a nonnegative combination	1.2, 3.1, 3.6
LP equivalent formulations	free-variable split, slack variables, the three parts of a reduction argument	1.5, 1.6
Farkas A ⇒ B	the variants table, the conversion recipe (slack columns force $y\ge0$ , split columns force equality)	5.2, 5.5
ℓ₁ and ℓ∞ regression LPs and their duals	absolute-value and min-max tricks; free variables; dual rulebook (free ↔ equality)	1.6, 3.5
Minimax theorem via LP duality	mixed strategies, linear functions over the simplex, max-min trick, writing the dual of a mixed-form LP, strong duality, reading optimal solutions as strategies	3.8, 1.6, 3.5, 3.4
Convex sets and functions (∩, ∪, +, ×, max)	definitions via segments and chords (no derivatives); operations tables; how to refute with one counterexample	2.1, 6.2, 6.5
GD for strongly convex functions	strong convexity, strengthened key inequality, one-step expansion with $\eta_t$ , weighted telescoping, $\sum1/t\le1+\ln T$ , Jensen for the average	8.10, 0.3, 7.5

4 · Not covered here

Lectures after 15 (randomized rounding, hardness of approximation) were not available. Strong convexity combined with smoothness (the geometric rate) is stated but not proved. Exam scope for facility location and edge-disjoint paths: see the notes at the top of 9.1, 9.6 and 9.15.

5 · Material added beyond the lecture notes

The math toolkit; the modeling checklist and tricks; worked reductions; S-O-B mnemonic and worked duals; min-problem certificates; full complementary-slackness derivation; zero-sum games; numeric threshold sweep; separation-oracle remark; Farkas variants; set-operation table; convexity-preserving rules beyond the board remarks; extra projection formulas; strong convexity; the spider and bipartite-trap greedy examples; $1-x\le e^{-x}$ in place of the limit; weighted vertex cover and the $f$ -approximation; the Fano-plane example; the multiplier derivation of the matching dual; tightness/gap/hardness comparison; the 6-approximation proof and the $c=\frac43$ variant; hardness remarks; all ★ practice questions. These explain the material. They do not claim to report anything said in class that is not in the lecture notes.

I understand this unit

The whole of Part 2 on one page

The one idea that ties everything together

How to read these notes

A study routine that works with the pictures

Math toolkit I: vectors, matrices, inequalities

Vectors and coordinatewise inequalities

Transpose and the dot product

Matrix times vector: the row view and the column view

Linear combinations, cones and convex combinations

Lengths and the "expand the square" identity

Math toolkit II: calculus and logic words

Gradient and Hessian

First-order Taylor expansion and little-o

Logic and set notation used in proofs

Sums you will meet in convergence proofs

Six proof patterns used again and again

What is a linear program?

The vocabulary, side by side

Why bother? What LPs give you

How to turn a problem into an LP

What is, and is not, an LP

Worked model: the smoothie LP

Checking a candidate: x=(3,3,0)x=(3,3,0)x=(3,3,0)

Maximum flow is an LP

Converting any LP to canonical form

Worked exercise (L9): min⁡(2u−v)\min(2u-v)min(2u−v) s.t. u−v=3, u≥0, vu-v=3,\ u\ge0,\ vu−v=3, u≥0, v free

Standard (equality) form with slack variables

Modeling tricks: absolute values, max/min objectives, and reductions

Trick 1: minimizing an absolute value

Trick 2: minimizing a maximum

Reductions: "this LP form can express that one"

Convex sets: every segment stays inside

Operations on convex sets

Solving a 2-D LP by sliding the objective line

Non-unique optima

The three possible outcomes of an LP

Tight constraints and vertices

Smoothie example: which three constraints pin (3,3,0)(3,3,0)(3,3,0)?

Some optimal solution is at a vertex

So why not just check every corner?

Polynomial-time solvability and short exact answers

Why the answer can be written with polynomially many bits

Exercise (L9): few fractional coordinates

A certificate: an upper bound that meets your solution

Mirror image: certificates for a minimization LP

Deriving the dual: optimize over upper bounds

Weak duality, the smoothie dual, and prices

The smoothie dual, explicitly

Economic interpretation

Strong duality and what can go wrong

Infeasible is not the same as unbounded

★ Exam skill: writing the dual of ANY LP

The rulebook for a maximization primal

Mnemonic: Sensible – Odd – Bizarre

The recipe

Worked example 1 (canonical): the smoothie LP

Worked example 2 (mixed): equality row and a free variable

Worked example 3 (min primal)

Worked example 4 (everything at once)

Worked example 5: dual of the dual is the primal

Complementary slackness: where the duality gap lives

Using slackness to find a solution

Tight does not mean positive: an example (L11 exercise)

Approximate certificates: a small gap bounds your error

Application: zero-sum games and the minimax theorem

Tool 1: a linear function over the simplex is optimized at a corner

Tool 2: the easy inequality (weak duality for games)

Tool 3: how the LP enters

The path-flow LP

Why path LP and edge LP have the same optimum

The dual: edge lengths, and every cut is a dual solution

Every s–t cut is a feasible 0/1 dual solution

Checking a candidate: $x=(3,3,0)$

Worked exercise (L9): $\min(2u-v)$ s.t. $u-v=3,\ u\ge0,\ v$ free

Smoothie example: which three constraints pin $(3,3,0)$ ?