The Lumenary · Advanced undergraduate

Optimisation

Name: ______________________

Date: ______________________

You will learn to

Formulate linear programs, solve them with the simplex method, and interpret the dual problem through weak and strong duality, complementary slackness and shadow prices
Prove that every local minimum of a convex function is a global minimum, and recognise convex sets and functions
Apply Lagrange multipliers and the KKT conditions, and prove that the KKT conditions are sufficient for convex problems
Implement gradient descent and prove its $O(1/k)$ rate for convex functions with Lipschitz gradient; compare it with Newton's method
Treat least-squares data fitting as a convex optimisation problem

1.
Maximise $2x + y$ subject to $x + y \le 4$ , $x \le 3$ , $x, y \ge 0$ . What is the optimal value?
2.
Which of these functions $\mathbb{R} \to \mathbb{R}$ are convex? (Choose all that apply.)
- A. $x^2$
- B. $|x|$
- C. $e^x$
- D. $x^3$
- E. $x^4 - x^2$
- F. $\max(x, 0)$
3.
In the workshop problem ( $\max 3x + 5y$ subject to $x \le 4$ , $2y \le 12$ , $3x + 2y \le 18$ , $x, y \ge 0$ ) the optimal dual solution is $y = (0, \tfrac32, 1)$ . By how much does the maximum profit increase if workshop C gets one extra hour (so $3x + 2y \le 19$ )?
4.
In the proof of weak duality, $c^{\mathsf T}x \le (A^{\mathsf T}y)^{\mathsf T}x = y^{\mathsf T}(Ax) \le y^{\mathsf T}b$ . Which hypotheses justify the last inequality $y^{\mathsf T}(Ax) \le y^{\mathsf T}b$ ?
- A. $Ax \le b$ and $y \ge 0$
- B. $x \ge 0$ and $A^{\mathsf T}y \ge c$
- C. $Ax \le b$ alone
- D.Optimality of $x$
5.
Minimise $(x - 3)^2 + (y - 1)^2$ subject to $x + y \le 2$ . Which point is the minimiser?
- A. $(2, 0)$
- B. $(3, 1)$
- C. $(1, 1)$
- D. $(0, 0)$
6.
The Lean theorem local_min_convex_global assumes hf : ConvexOn ℝ Set.univ f and hx : IsLocalMin f x and concludes f x ≤ f y. Which function and point show that the convexity hypothesis hf cannot be dropped?
- A. $f(x) = x^3 - 3x$ at $x = 1$
- B. $f(x) = x^2$ at $x = 0$
- C. $f(x) = x^4 - x^2$ at $x = 1/\sqrt2$
- D. $f(x) = e^x$ at $x = 0$
7.
Gradient descent with step $1/L$ is run on a convex $L$ -smooth function with $L = 4$ , starting at distance $\|x_0 - x^*\| = 3$ from a minimiser. Using Theorem 9, what is the smallest number of steps $k$ that guarantees $f(x_k) - f(x^*) \le 0.01$ ?
8.
Write gradient_descent(grad, x0, step, iters) that applies $x \mapsto x - \text{step} \cdot \text{grad}(x)$ to a number x0 iters times and returns the final value. Then use it on $f(x) = 2(x - 3)^2$ , whose gradient is $4(x - 3)$ (so $L = 4$ ), and observe that steps below $2/L = 0.5$ converge while larger steps diverge.
Computational — Practice

Answer key — Optimisation

1.
At the vertices $(0, 0)$ , $(3, 0)$ , $(3, 1)$ , $(0, 4)$ the objective is $0, 6, 7, 4$ , so the optimum is $7$ at $(3, 1)$ . A dual certificate: $y = (1, 1)$ for the two constraints satisfies $y_1 + y_2 = 2 \ge 2$ and $y_1 = 1 \ge 1$ , with $b^{\mathsf T}y = 4 + 3 = 7$ , proving optimality by Corollary 2(a).
2.
Convex: $x^2$ , $|x|$ , $e^x$ , $\max(x, 0)$ . Not convex: $x^3$ (concave for $x < 0$ ) and $x^4 - x^2$ (concave near $0$ ). Note that convexity does not require differentiability: $|x|$ and $\max(x, 0)$ have kinks.
3.
The shadow price of C is $y_3 = 1$ . Directly: the new optimum is at $y = 6$ , $3x = 19 - 12$ , so $x = 7/3$ and profit $3 \cdot 7/3 + 30 = 37 = 36 + 1$ . (Shadow prices are valid for small changes, while the same constraints stay tight.)
4.
$y^{\mathsf T}b - y^{\mathsf T}(Ax) = \sum_i y_i\,(b - Ax)_i \ge 0$ because each $y_i \ge 0$ and each $(b - Ax)_i \ge 0$ . This is also where complementary slackness comes from: equality forces every product $y_i (b - Ax)_i$ to be $0$ .
5.
The constraint must be tight. KKT gives $x = 3 - \mu/2$ , $y = 1 - \mu/2$ ; then $x + y = 4 - \mu = 2$ , so $\mu = 2 \ge 0$ and $(x, y) = (2, 0)$ , with value $2$ . Geometrically $(2, 0)$ is the projection of $(3, 1)$ onto the line $x + y = 2$ . The problem is convex, so by Theorem 7(a) this KKT point is the global minimiser.
6.
$f(x) = x^3 - 3x$ has a local minimum at $x = 1$ (value $-2$ ) but is unbounded below, so it is not a global minimum. The Lean proof fails exactly at the step hf.2 …: the convexity inequality $f((1 - t)x + ty) \le (1 - t)f(x) + tf(y)$ is false for this $f$ .
7.
$\frac{L\|x_0 - x^*\|^2}{2k} = \frac{18}{k} \le 0.01$ exactly when $k \ge 1800$ . This is a worst-case guarantee; on a particular function (like the experiment's quadratic) the gap may shrink much faster, and accelerated methods guarantee $O(1/k^2)$ .
8.
```
def gradient_descent(grad, x0, step, iters):
    x = x0
    for _ in range(iters):
        x = x - step * grad(x)
    return x
```
The error $e = x - 3$ evolves as $e \mapsto (1 - 4\eta)e$ . It shrinks when $|1 - 4\eta| < 1$ , i.e. $0 < \eta < 0.5 = 2/L$ , vanishes in one step at $\eta = 1/L = 0.25$ , and grows like $1.2^k$ at $\eta = 0.55$ .