2026-10-07 Online Opt Scribe
Linear Programming (Recap)
Last class we say that Maxflow problem $$Bf = Fb$$ subject to $$0 \le f_e \le c_e, \forall e\in E$$
We also saw how this can be turned into its dual form.
We also saw more Primal-Dual pairs and how the dual version of an optimization problem itself is a meaningful optimization problem. The key point is meaningful. Every primal problem has a dual but whether this dual represents something is a different question.
We also saw the Duality theorem - both weak and strong
The strong one - Primal = Dual - can only be applied if either one of them are feasible. But for practical purposes, we only care about feasible problems anyway, hence, strong duality can be used in all the problems we care about.
Still, as it is good to be exhaustive, we shall see the primal-dual values in different regimes
| Primal\Dual | Feasible | Infeasible |
|---|---|---|
| Feasible | P=D\in$(-\infty, +\infty)$ | P=D=$\infty$ |
| Infeasible | P=D=$-\infty$ | P=$\infty$, D=$-\infty$ |
When we discuss strong duality, we are usually concerned with the scenario where both are feasible. If only one of them is feasible, though technically satisfies the constraint, the optimization problem is moot as it implies unboundedness in the direction that we care about.
Proof
Let us first write down the problems
| Primal | Dual |
|---|---|
| $\min c^Tx$ | $\max b^Ty$ |
| $Ax \ge b$ | $A^Ty \le c$ |
| $x\succeq 0$ | $y \preceq 0$ |
Let us assume that the Primal problem is feasible i.e $\exists$ an $x$ that satisfies the constraints.
Then we can rewrite the objective function as $\min_{x \ge 0} c^T x$. I have just move the constraint on to the objective function itself.
What we want to prove is the following
Optimizing this $$\min_{x \ge 0}\max_{y \ge 0} c^Tx - y^T (Ax - b)$$ also optimizes our original problem
It is not clear now how that might occur, but seeing the you can instantly spot shades of minimax theorem which is what we are going to use.
Proof of constraints remaining intact
Lets suppose, towards contradiction, that there $\exists x$ such that $Ax \prec b$, that is we violated the constraint. That implies that there was at least one coordinate where $(Ax - b)_i \lt 0$. Then we can set $y_i \rightarrow \infty$ and make the whole objective explode to infinity there by making that $x$ not a minimizer.
Notice what we’ve accomplished. We have converted an inequality into a single objective function where breaking that inequality will never lead to an optimum.
We can visualize the modified objective function as a 2-player game where the second player “punishes” us whenever we violate a constraint.
This also establishes $y\succeq 0$ as the max player wants to maximize.
Hence, the modified objective function is equivalent to the primal problem as it enforces all the same constraints.
Similarly we can write the dual problem as
$$\max_{y\ge 0}\min_{x \ge 0} b^Ty - x^T(A^Ty - c)$$
A carbon-copy argument can be made as to how this enforces the constraints.
Ohhh, it is the same function as the primal version. We have converted both the primal and the dual into a single objective function played by 2 players.
This solidifies the path - minimax theorem - that we’re gonna take. Recall from previous classes that we used No-Regret algorithms extensively to prove minimax results. We cannot quite do that here as the sets ($x\ge 0, y \ge 0$) are not bounded.
This way of solving Linear programming problems using No-Regret is further discussed in HW2.
This is not the preferred way of solving LP. There are other methods that are much more accurate. A summary is as follows:
| Method | Complexity | Pros/Cons |
|---|---|---|
| Interior | Poly(m, n, $\log(\frac{1}{\epsilon})$) | High accuracy |
| Simplex | $O(e^x)$ | High accuracy |
| Ellipsoid | Poly(m, n, $\log(\frac{1}{\epsilon})$) | Mainly Theoretical, not used |
| No-Regret | (m’, n’, $\frac{1}{E}$, Time of Best Response Oracle) | Cheap but not accurate |
Where,
- m = #(constants)
- n = #(Variables)
- m’ = #(Variables in difficult constraints)
No-Regret for LP
Recall that
$$\min c^T x$$ subject to $$Ax \ge b$$ $$x \in \mathcal{K}$$ We’ve swapped $x \succeq 0$ with some convex set $\mathcal{K}$
- First we split the problem into two independent problem
Finding $\min_{x \in K}c^Tx$ is very fast
If we cannot find easy constraints to put into $\mathcal{K}$ just set it to be $\mathcal{K} = [-B, B]^d$
Even this is easy as we are minimizing a linear function the minima is guaranteed to be in the boundaries. Specifically
$$ \min g^Tx = \begin{cases} g_i \ge 0 \implies x_i = -B\ g_i \lt 0 \implies x_i = B\ \end{cases} $$
This still doesn’t solve our problem. After converting to the combined form
$$ \min_{x \in \mathcal{K}}\max_{y \ge 0} c^Tx - y^T (Ax - b) $$
$y$ is still unbounded.
To solve this we convert it to be a Feasibility problem rather than a minimization problem