Chapter 7 Exercises and Solutions

These are the exercises from the end of Chapter 7 of Mathematics for Machine Learning (page 247 of the December 2019 draft), restated in this module’s notation. Eleven of them, and they divide neatly: two on gradient descent, two true-or-false batteries on convexity, three on writing down duals, and four on convex conjugates.

Work each one before opening its solution. Every solution is followed by a NumPy block that checks the answer, and the printed output is what that block actually produced.

§7.1 — Gradient descent

Exercise 7.1

Consider the univariate function

$$f(x) = x^3 + 6x^2 - 3x - 5$$

Find its stationary points and indicate whether they are maximum, minimum, or saddle points.

Solution

Differentiate twice:

$$f'(x) = 3x^2 + 12x - 3 = 3(x^2 + 4x - 1), \qquad f''(x) = 6x + 12$$

Set $f' = 0$. The quadratic $x^2 + 4x - 1$ has roots

$$x = \frac{-4 \pm \sqrt{16 + 4}}{2} = \frac{-4 \pm 2\sqrt5}{2} = -2 \pm \sqrt5$$

so the stationary points are $x = -2 - \sqrt5 = -4.2360680$ and $x = -2 + \sqrt5 = 0.2360680$.

Classify with $f''$:

$x$	$f(x)$	$f''(x)$	verdict
$-2-\sqrt5 = -4.2360680$	$+39.3606798$	$-13.4164079$	maximum
$-2+\sqrt5 = +0.2360680$	$-5.3606798$	$+13.4164079$	minimum

There are no saddle points, and there cannot be. A saddle point needs one direction along which the function increases and another along which it decreases, so it requires at least two dimensions. In one dimension a stationary point is a maximum, a minimum, or degenerate ($f'' = 0$ as well). The question lists “saddle” as an option, and the correct answer is that the option does not apply here.

Two details worth noticing. The two values of $f''$ are $\mp 13.4164079$ — equal in magnitude, opposite in sign — because $f''$ is linear and the two roots are symmetric about $x = -2$, which is exactly where $f'' = 0$. And $x = -2$ is an inflection point, not a stationary point: $f'(-2) = -15$, comfortably nonzero. Confusing “second derivative vanishes” with “first derivative vanishes” is the trap.

verify_7_1.py

import numpy as np
 
f = np.polynomial.Polynomial([-5.0, -3.0, 6.0, 1.0])   # increasing degree
d1, d2 = f.deriv(1), f.deriv(2)
print("f'(x)  =", d1, "  = 3(x^2 + 4x - 1)")
print("f''(x) =", d2)
 
print(f"\nexact roots: -2 +- sqrt(5) = {-2 - np.sqrt(5):.7f}, "
      f"{-2 + np.sqrt(5):.7f}")
for r in np.sort(d1.roots().real):
    kind = "minimum" if d2(r) > 0 else ("maximum" if d2(r) < 0 else "degenerate")
    print(f"  x = {r:+.7f}   f = {f(r):+.7f}   f'' = {d2(r):+.7f}   {kind}")
 
print(f"\ninflection at f''=0, x = -2.0: f' there = {d1(-2.0):+.4f} "
      f"(nonzero, so NOT a stationary point)")

text

f'(x)  = -3.0 + 12.0 x + 3.0 x**2   = 3(x^2 + 4x - 1)
f''(x) = 12.0 + 6.0 x
 
exact roots: -2 +- sqrt(5) = -4.2360680, 0.2360680
  x = -4.2360680   f = +39.3606798   f'' = -13.4164079   maximum
  x = +0.2360680   f = -5.3606798   f'' = +13.4164079   minimum
 
inflection at f''=0, x = -2.0: f' there = -15.0000 (nonzero, so NOT a stationary point)

Where people get stuck: answering “saddle” for one of them because a cubic “looks like” it has one. The S-shape is real, but the flat-looking middle is the inflection at $x = -2$, where the gradient is $-15$ and the function is descending steeply. Nothing is stationary there.

Exercise 7.2

Consider the update equation for stochastic gradient descent (Equation 7.15). Write down the update when we use a mini-batch size of one.

Solution

Equation 7.15 is the full-batch update:

$$\boldsymbol\theta_{i+1} = \boldsymbol\theta_i - \gamma_i\big(\nabla L(\boldsymbol\theta_i)\big)^\top = \boldsymbol\theta_i - \gamma_i\sum_{n=1}^{N}\big(\nabla L_n(\boldsymbol\theta_i)\big)^\top$$

With a mini-batch of size one, pick a single index $n$ uniformly at random from $\{1, \dots, N\}$ and replace the sum by that one term:

$$\boxed{\ \boldsymbol\theta_{i+1} = \boldsymbol\theta_i - \gamma_i\big(\nabla L_n(\boldsymbol\theta_i)\big)^\top,\qquad n \sim \text{Uniform}\{1,\dots,N\}\ }$$

Why this is legitimate is the whole content of §7.1.3. Convergence requires only that the gradient estimate be unbiased, and

$$\mathbb{E}_n\big[N\nabla L_n(\boldsymbol\theta)\big] = N \cdot \frac{1}{N}\sum_{n=1}^{N}\nabla L_n(\boldsymbol\theta) = \nabla L(\boldsymbol\theta)$$

Note the $N$. If you want an unbiased estimate of the sum $\nabla L = \sum_n \nabla L_n$, a single term must be multiplied by $N$; the boxed form above therefore has an effective step size of $\gamma_i/N$ compared with the batch update. Either convention is fine as long as you know which one you are using — that is what page 702 measured as the $N/\lvert B\rvert$ factor, and why changing the batch size can silently change the learning rate.

verify_7_2.py

import numpy as np
 
rng = np.random.default_rng(0)
N, D = 500, 4
X = rng.standard_normal((N, D))
y = X @ rng.standard_normal(D) + 0.4 * rng.standard_normal(N)
theta = rng.standard_normal(D)
 
# L(theta) = sum_n (x_n . theta - y_n)^2, so grad L_n = 2 x_n (x_n.theta - y_n)
grad_full = 2 * X.T @ (X @ theta - y)
grad_one = lambda n: 2 * X[n] * (X[n] @ theta - y[n])
 
trials = 200_000
acc_raw = np.zeros(D)
acc_scaled = np.zeros(D)
for _ in range(trials):
    n = rng.integers(N)
    acc_raw += grad_one(n)
    acc_scaled += N * grad_one(n)
 
print("||full gradient||         =", f"{np.linalg.norm(grad_full):.4f}")
print("mean of one term, x1      : relative error",
      f"{np.linalg.norm(acc_raw / trials - grad_full) / np.linalg.norm(grad_full):.4f}")
print("mean of one term, xN      : relative error",
      f"{np.linalg.norm(acc_scaled / trials - grad_full) / np.linalg.norm(grad_full):.2e}")
print("\nso a single-example gradient is unbiased for the MEAN gradient,")
print("and needs the factor N to be unbiased for the SUM.")

text

||full gradient||         = 2276.9037
mean of one term, x1      : relative error 0.9980
mean of one term, xN      : relative error 3.15e-03
 
so a single-example gradient is unbiased for the MEAN gradient,
and needs the factor N to be unbiased for the SUM.

Read the two error figures against each other. The unscaled average is $99.8\%$ wrong — it is converging, but to $\nabla L / N$ rather than to $\nabla L$, so it is off by the factor $N = 500$. The scaled version is within $3\times10^{-3}$, and that residual is Monte Carlo noise from $200{,}000$ samples rather than bias.

Where people get stuck: writing the update with the sum still present but over a one-element set, which is correct but hides the point; or dropping the $N$ and then being surprised that the effective learning rate depends on $N$.

§7.3 — Convexity, true or false

Exercise 7.3

Consider whether the following statements are true or false:

(a) The intersection of any two convex sets is convex. (b) The union of any two convex sets is convex. (c) The difference of a convex set $A$ from another convex set $B$ is convex.

Solution

(a) TRUE. Take $\mathbf{x}, \mathbf{y} \in A \cap B$ and $\theta \in [0,1]$. Since both lie in $A$ and $A$ is convex, $\theta\mathbf{x} + (1-\theta)\mathbf{y} \in A$. The same argument gives membership in $B$. So the point lies in $A \cap B$.

Note this argument uses nothing about there being only two sets — the intersection of any family of convex sets is convex. That is why a feasible region defined by many convex constraints (Equation 7.38) stays convex however many constraints you add, and it is the single most useful closure fact in the chapter.

(b) FALSE in general. Counterexample: $A = [-1, 1]$ and $B = [3, 4]$. Then $x = 2$ lies on the segment from $1 \in A$ to $3 \in B$ but is in neither set.

Be careful choosing the counterexample. $[-1,1] \cup [0.5, 2]$ is convex, because the intervals overlap and the union is the single interval $[-1, 2]$. The claim is false in general, not always — so the witness must be disjoint.

(c) FALSE in general. Counterexample: $A = [-2, 2]$ and $B = [-1, 1]$ gives $A \setminus B = [-2, -1) \cup (1, 2]$, two pieces. Again, an overlapping-but-not-nested pair can come out convex: $[-1, 1] \setminus [0.5, 2] = [-1, 0.5)$, a single interval.

A cleaner way to see (c): removing a set is intersecting with its complement, and the complement of a convex set is essentially never convex, so nothing in (a) applies.

verify_7_3.py

import numpy as np
 
# A subset of the real line is convex exactly when it is one contiguous run.
ts = np.linspace(-6, 8, 1_400_001)
 
def contiguous(mask):
    idx = np.flatnonzero(mask)
    return bool(idx.size == 0 or np.all(np.diff(idx) == 1))
 
iv = lambda lo, hi: (ts >= lo) & (ts <= hi)
 
cases = [
    ("(a) intersection [-1,1] & [0.5,2]", iv(-1, 1) & iv(0.5, 2), True),
    ("(a) intersection [-1,1] & [3,4] (empty)", iv(-1, 1) & iv(3, 4), True),
    ("(b) union [-1,1] | [0.5,2] (overlapping)", iv(-1, 1) | iv(0.5, 2), True),
    ("(b) union [-1,1] | [3,4] (disjoint)", iv(-1, 1) | iv(3, 4), False),
    ("(c) difference [-1,1] \\ [0.5,2]", iv(-1, 1) & ~iv(0.5, 2), True),
    ("(c) difference [-2,2] \\ [-1,1]", iv(-2, 2) & ~iv(-1, 1), False),
]
for name, mask, expect in cases:
    print(f"  {name:44} convex: {str(contiguous(mask)):5} "
          f"(expected {expect})")
print("\n(a) TRUE always. (b) FALSE in general. (c) FALSE in general.")
print("note: the empty set is convex, so an empty intersection is fine.")

text

  (a) intersection [-1,1] & [0.5,2]            convex: True  (expected True)
  (a) intersection [-1,1] & [3,4] (empty)      convex: True  (expected True)
  (b) union [-1,1] | [0.5,2] (overlapping)     convex: True  (expected True)
  (b) union [-1,1] | [3,4] (disjoint)          convex: False (expected False)
  (c) difference [-1,1] \ [0.5,2]              convex: True  (expected True)
  (c) difference [-2,2] \ [-1,1]               convex: False (expected False)
 
(a) TRUE always. (b) FALSE in general. (c) FALSE in general.
note: the empty set is convex, so an empty intersection is fine.

Where people get stuck: offering an overlapping pair as a counterexample for (b) or (c). Getting the verdict right and the witness wrong is worth no credit, and it is easy to do — as the table shows, four of the six cases tested come out convex.

Exercise 7.4

Consider whether the following statements are true or false:

(a) The sum of any two convex functions is convex. (b) The difference of any two convex functions is convex. (c) The product of any two convex functions is convex. (d) The maximum of any two convex functions is convex.

Solution

(a) TRUE. This is Example 7.4. Add the two instances of Definition 7.3 and regroup:

$$(f_1+f_2)(\theta\mathbf{x} + (1-\theta)\mathbf{y}) \leq \theta\big(f_1(\mathbf{x})+f_2(\mathbf{x})\big) + (1-\theta)\big(f_1(\mathbf{y})+f_2(\mathbf{y})\big)$$

Combined with $\alpha f$ convex for $\alpha \geq 0$, this gives closure under all non-negative weighted sums.

(b) FALSE. With $f_1 = x^2$ and $f_2 = e^{-x}$, both convex, the difference has minimum second derivative $-5.3872$ on $[-2,3]$ and a measured worst chord violation of $0.57535$. The word “non-negative” in (a) is doing real work: subtracting is adding with $\alpha = -1$.

(c) FALSE. The same pair: $x^2 e^{-x}$ has minimum second derivative $-0.4120$ and a chord violation of $0.28093$. Products are simply not a closure operation. (Special cases work — the product of two non-negative, non-decreasing convex functions is convex — but the general claim fails.)

(d) TRUE. For any $\theta \in [0,1]$, apply Definition 7.3 inside each branch and then use “a max of sums is at most the sum of maxes”:

$$\max_i f_i(\theta\mathbf{x} + (1-\theta)\mathbf{y}) \leq \max_i\big(\theta f_i(\mathbf{x}) + (1-\theta)f_i(\mathbf{y})\big) \leq \theta\max_i f_i(\mathbf{x}) + (1-\theta)\max_i f_i(\mathbf{y})$$

Note that the maximum can destroy differentiability — $\max(x^2, e^{-x})$ has a kink where the two cross — without destroying convexity. That is why Definition 7.3, and not the Hessian test, is the real definition. The hinge loss of Exercise 7.11 is exactly this shape.

verify_7_4.py

import numpy as np
 
def min_d2(fn, lo, hi, n=20001):
    xs = np.linspace(lo, hi, n)
    h = (hi - lo) / (n - 1)
    return float(((fn(xs[1:-1] + h) - 2 * fn(xs[1:-1])
                   + fn(xs[1:-1] - h)) / h ** 2).min())
 
rng = np.random.default_rng(7)
def worst_chord(fn, lo, hi, n=300_000):
    a = rng.uniform(lo, hi, n); b = rng.uniform(lo, hi, n)
    t = rng.uniform(0, 1, n)
    return float((fn(t * a + (1 - t) * b)
                  - (t * fn(a) + (1 - t) * fn(b))).max())
 
f1 = lambda x: x ** 2
f2 = lambda x: np.exp(-x)
for tag, name, fn, expect in (
        ("(a)", "f1 + f2", lambda x: f1(x) + f2(x), True),
        ("(b)", "f1 - f2", lambda x: f1(x) - f2(x), False),
        ("(c)", "f1 * f2", lambda x: f1(x) * f2(x), False),
        ("(d)", "max(f1,f2)", lambda x: np.maximum(f1(x), f2(x)), True)):
    d2v, cv = min_d2(fn, -2, 3), worst_chord(fn, -2, 3)
    print(f"  {tag} {name:11} min f'' = {d2v:>10.4f}  worst chord = "
          f"{cv:>10.5f}  convex: {str(cv <= 1e-9):5} (expected {expect})")
print("\n(a) TRUE. (b) FALSE. (c) FALSE. (d) TRUE.")

text

  (a) f1 + f2     min f'' =     2.0498  worst chord =   -0.00000  convex: True  (expected True)
  (b) f1 - f2     min f'' =    -5.3872  worst chord =    0.57535  convex: False (expected False)
  (c) f1 * f2     min f'' =    -0.4120  worst chord =    0.28093  convex: False (expected False)
  (d) max(f1,f2)  min f'' =     0.4951  worst chord =   -0.00000  convex: True  (expected True)
 
(a) TRUE. (b) FALSE. (c) FALSE. (d) TRUE.

Where people get stuck: guessing that (d) is false because the maximum introduces a kink. Kinks break differentiability, not convexity — and the max is one of the most useful convexity-preserving operations there is, since it is how piecewise-linear convex losses get built.

§7.3.1 — Writing down duals

Exercise 7.5

Express the following optimization problem as a standard linear program in matrix notation:

$$\max_{\mathbf{x}\in\mathbb{R}^2,\ \xi\in\mathbb{R}} \mathbf{p}^\top\mathbf{x} + \xi$$

subject to $\xi \geq 0$, $x_0 \leq 0$ and $x_1 \leq 3$.

Solution

Standard form (Equation 7.39) is $\min_{\mathbf{z}} \mathbf{c}^\top\mathbf{z}$ subject to $\mathbf{A}\mathbf{z} \leq \mathbf{b}$. Three changes are needed: stack the variables, flip the maximisation, and flip the one lower bound.

Stack. $\mathbf{z} = (x_0, x_1, \xi)^\top \in \mathbb{R}^3$.

Flip the objective. $\max \mathbf{p}^\top\mathbf{x} + \xi = -\min\big(-(\mathbf{p}^\top\mathbf{x} + \xi)\big)$, so

$$\mathbf{c} = \begin{bmatrix}-p_0\\-p_1\\-1\end{bmatrix}$$

Flip the lower bound. $\xi \geq 0$ is $-\xi \leq 0$. The other two are already the right way round.

$$\mathbf{A} = \begin{bmatrix}1&0&0\\0&1&0\\0&0&-1\end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix}0\\3\\0\end{bmatrix}$$

As printed, this program is unbounded

$\xi$ is bounded below by $0$ and not above, and the objective rewards larger $\xi$. So $\xi \to \infty$ drives the objective to $+\infty$ and no optimum exists. Measured: with $\mathbf{p} = (2, -1)$, the feasible points $(0, 3, 0)$, $(0, 3, 10)$ and $(0, 3, 1000)$ have objective values $3$, $-7$ and $-997$ in minimisation form — falling without limit.

There is a second route to unboundedness that depends on $\mathbf{p}$: since $x_0 \leq 0$ leaves $x_0 \to -\infty$ available, the problem is also unbounded whenever $p_0 < 0$.

The exercise asks only for the matrix form, and none of this is a mistake in the answer — but writing the problem in standard form is precisely what makes the unboundedness visible, since you can read it off $\mathbf{c}$ and $\mathbf{A}$ directly. That is a fair part of the exercise’s point.

verify_7_5.py

import numpy as np
 
p = np.array([2.0, -1.0])            # an arbitrary p, to make it concrete
# z = (x0, x1, xi);  maximise p.x + xi  ==  minimise -(p.x + xi)
c = np.array([-p[0], -p[1], -1.0])
A = np.array([[1.0, 0.0, 0.0],       # x0 <= 0
              [0.0, 1.0, 0.0],       # x1 <= 3
              [0.0, 0.0, -1.0]])     # -xi <= 0, i.e. xi >= 0
b = np.array([0.0, 3.0, 0.0])
 
print("z = (x0, x1, xi)")
print("c =", c.tolist(), "   (minimising -(p.x + xi))")
print("A =", A.tolist())
print("b =", b.tolist())
for z in ([0.0, 3.0, 0.0], [0.0, 3.0, 10.0], [0.0, 3.0, 1000.0]):
    z = np.array(z)
    print(f"  z = {str(z.tolist()):24} feasible: "
          f"{bool(np.all(A @ z <= b + 1e-12))}   objective c.z = {c @ z:10.1f}")

text

z = (x0, x1, xi)
c = [-2.0, 1.0, -1.0]    (minimising -(p.x + xi))
A = [[1.0, 0.0, 0.0], [0.0, 1.0, 0.0], [0.0, 0.0, -1.0]]
b = [0.0, 3.0, 0.0]
  z = [0.0, 3.0, 0.0]          feasible: True   objective c.z =        3.0
  z = [0.0, 3.0, 10.0]         feasible: True   objective c.z =       -7.0
  z = [0.0, 3.0, 1000.0]       feasible: True   objective c.z =     -997.0

Where people get stuck: writing $\xi \geq 0$ as a row of $\mathbf{A}$ without negating it, which silently imposes $\xi \leq 0$ instead — the opposite constraint. Every $\geq$ must become a $\leq$ by negating both the row and the right-hand side.

Exercise 7.6

Consider the linear program illustrated in Figure 7.9,

$$\min_{\mathbf{x}\in\mathbb{R}^2} -\begin{bmatrix}5\\3\end{bmatrix}^\top\begin{bmatrix}x_1\\x_2\end{bmatrix} \quad\text{subject to}\quad \begin{bmatrix}2&2\\2&-4\\-2&1\\0&-1\\0&1\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix} \leq \begin{bmatrix}33\\8\\5\\-1\\8\end{bmatrix}$$

Derive the dual linear program using Lagrange duality.

Solution

Three steps, exactly as in §7.3.1.

Step 1. The Lagrangian, with $\boldsymbol\lambda \in \mathbb{R}^5$, $\boldsymbol\lambda \geq 0$:

$$L(\mathbf{x}, \boldsymbol\lambda) = \mathbf{c}^\top\mathbf{x} + \boldsymbol\lambda^\top(\mathbf{A}\mathbf{x} - \mathbf{b})$$

Step 2. Collect the $\mathbf{x}$ terms:

$$L(\mathbf{x}, \boldsymbol\lambda) = (\mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda)^\top\mathbf{x} - \boldsymbol\lambda^\top\mathbf{b}$$

Step 3. $\partial L/\partial\mathbf{x} = \mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda$. There is no $\mathbf{x}$ in it, so it cannot be solved for $\mathbf{x}$ — instead it is a condition: unless $\mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda = \mathbf{0}$, the Lagrangian is a nonconstant linear function of $\mathbf{x}$ whose infimum is $-\infty$. Hence

$$\max_{\boldsymbol\lambda\in\mathbb{R}^5} -\mathbf{b}^\top\boldsymbol\lambda \qquad\text{subject to}\qquad \mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda = \mathbf{0},\quad \boldsymbol\lambda \geq 0$$

The answer, concretely. The primal optimum is at $\mathbf{x}^\star = (37/3, 25/6)$ with value $-445/6 = -74.166667$, where constraints $0$ and $1$ are active. By complementary slackness only those two multipliers can be nonzero, so solve $\mathbf{A}_{\text{act}}^\top\boldsymbol\lambda_{\text{act}} = -\mathbf{c}$:

$$\begin{bmatrix}2&2\\2&-4\end{bmatrix}\begin{bmatrix}\lambda_0\\\lambda_1\end{bmatrix} = \begin{bmatrix}5\\3\end{bmatrix} \quad\Longrightarrow\quad 6\lambda_1 = 2,\ \ \lambda_1 = \tfrac13,\ \ \lambda_0 = \tfrac{5 - 2/3}{2} = \tfrac{13}{6}$$

Both non-negative, as the dual requires. And

$$-\mathbf{b}^\top\boldsymbol\lambda^\star = -\Big(33\cdot\tfrac{13}{6} + 8\cdot\tfrac13\Big) = -\Big(\tfrac{143}{2} + \tfrac83\Big) = -\tfrac{445}{6}$$

the same value. Gap zero, as strong duality requires for a convex problem.

verify_7_6.py

import itertools
 
import numpy as np
 
c = np.array([-5.0, -3.0])
A = np.array([[2.0, 2.0], [2.0, -4.0], [-2.0, 1.0], [0.0, -1.0], [0.0, 1.0]])
b = np.array([33.0, 8.0, 5.0, -1.0, 8.0])
 
verts = []
for i, j in itertools.combinations(range(5), 2):
    M = A[[i, j]]
    if abs(np.linalg.det(M)) < 1e-12:
        continue
    v = np.linalg.solve(M, b[[i, j]])
    if np.all(A @ v <= b + 1e-9) and not any(
            np.allclose(v, w, atol=1e-9) for w in verts):
        verts.append(v)
verts = np.array(verts)
xs = verts[int(np.argmin(verts @ c))]
 
act = [i for i, q in enumerate(A @ xs - b) if abs(q) < 1e-9]
lam = np.zeros(5)
lam[act] = np.linalg.solve(A[act].T, -c)
 
print("dual: max -b^T lam  s.t.  c + A^T lam = 0, lam >= 0")
print(f"  x*      = ({xs[0]:.6f}, {xs[1]:.6f}) = (37/3, 25/6)")
print(f"  lambda* = {np.round(lam, 6).tolist()} = (13/6, 1/3, 0, 0, 0)")
print(f"  primal {xs @ c:.6f}   dual {-(b @ lam):.6f}   "
      f"gap {abs(xs @ c + b @ lam):.2e}")

text

dual: max -b^T lam  s.t.  c + A^T lam = 0, lam >= 0
  x*      = (12.333333, 4.166667) = (37/3, 25/6)
  lambda* = [2.166667, 0.333333, 0.0, 0.0, 0.0] = (13/6, 1/3, 0, 0, 0)
  primal -74.166667   dual -74.166667   gap 1.42e-14

Where people get stuck: trying to solve $\mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda = \mathbf{0}$ for $\mathbf{x}$. There is no $\mathbf{x}$ in it. That absence is the defining feature of the LP case, and it is what makes the dual another LP rather than a quadratic.

Exercise 7.7

Consider the quadratic program illustrated in Figure 7.4,

$$\min_{\mathbf{x}\in\mathbb{R}^2} \frac12\begin{bmatrix}x_1\\x_2\end{bmatrix}^\top\begin{bmatrix}2&1\\1&4\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix} + \begin{bmatrix}5\\3\end{bmatrix}^\top\begin{bmatrix}x_1\\x_2\end{bmatrix}$$

subject to the box $-1 \leq x_i \leq 1$. Derive the dual quadratic program using Lagrange duality.

Solution

Same three steps, but step 3 goes differently.

Steps 1 and 2:

$$L(\mathbf{x}, \boldsymbol\lambda) = \frac12\mathbf{x}^\top\mathbf{Q}\mathbf{x} + (\mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda)^\top\mathbf{x} - \boldsymbol\lambda^\top\mathbf{b}$$

Step 3. $\partial L/\partial\mathbf{x} = \mathbf{Q}\mathbf{x} + (\mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda) = \mathbf{0}$. This one does contain $\mathbf{x}$, and $\mathbf{Q}$ is positive definite — its eigenvalues are $1.585786$ and $4.414214$ — so it is invertible and

$$\mathbf{x} = -\mathbf{Q}^{-1}(\mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda)$$

Substituting back, and writing $\mathbf{v} = \mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda$, the quadratic and linear terms combine as $\tfrac12\mathbf{v}^\top\mathbf{Q}^{-1}\mathbf{v} - \mathbf{v}^\top\mathbf{Q}^{-1}\mathbf{v} = -\tfrac12\mathbf{v}^\top\mathbf{Q}^{-1}\mathbf{v}$:

$$\max_{\boldsymbol\lambda\in\mathbb{R}^4} -\frac12(\mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda)^\top\mathbf{Q}^{-1}(\mathbf{c} + \mathbf{A}^\top\boldsymbol\lambda) - \boldsymbol\lambda^\top\mathbf{b} \qquad\text{subject to}\qquad \boldsymbol\lambda \geq 0$$

A concave quadratic with no equality constraints — the structural difference from Exercise 7.6.

The answer, concretely. $\mathbf{x}^\star = (-1, -\tfrac12)$ with $f = -4.5$, only the constraint $-x_1 \leq 1$ active, and $\boldsymbol\lambda^\star = (0, 2.5, 0, 0)$. Duality gap exactly zero.

verify_7_7.py

import numpy as np
 
Q = np.array([[2.0, 1.0], [1.0, 4.0]])
c = np.array([5.0, 3.0])
A = np.array([[1.0, 0.0], [-1.0, 0.0], [0.0, 1.0], [0.0, -1.0]])
b = np.ones(4)
Qi = np.linalg.inv(Q)
 
dual = lambda l: -0.5 * (c + A.T @ l) @ Qi @ (c + A.T @ l) - l @ b
xq = np.array([-1.0, -0.5])
 
print(f"Q eigenvalues {np.linalg.eigvalsh(Q).round(6).tolist()} -> invertible")
ts = np.linspace(0, 6, 60001)
dv = np.array([dual(np.array([0.0, t, 0.0, 0.0])) for t in ts])
lq = np.array([0.0, ts[int(np.argmax(dv))], 0.0, 0.0])
print("dual: max -1/2 (c + A^T lam)^T Q^-1 (c + A^T lam) - lam^T b, lam >= 0")
print(f"  lambda* = {np.round(lq, 6).tolist()}")
print(f"  primal {0.5 * xq @ Q @ xq + c @ xq:.9f}   dual {dual(lq):.9f}   "
      f"gap {abs(0.5 * xq @ Q @ xq + c @ xq - dual(lq)):.2e}")
print(f"  x from Eq 7.50 = {np.round(-Qi @ (c + A.T @ lq), 6).tolist()}")

text

Q eigenvalues [1.585786, 4.414214] -> invertible
dual: max -1/2 (c + A^T lam)^T Q^-1 (c + A^T lam) - lam^T b, lam >= 0
  lambda* = [0.0, 2.5, 0.0, 0.0]
  primal -4.500000000   dual -4.500000000   gap 0.00e+00
  x from Eq 7.50 = [-1.0, -0.5]

Where people get stuck: using $\mathbf{Q}^{-1}$ without checking that it exists. Convexity only needs $\mathbf{Q}$ positive semidefinite; this substitution needs it strictly positive definite. State the assumption, as the book does at Equation 7.50.

Exercise 7.8

Consider the convex optimization problem

$$\min_{\mathbf{w}\in\mathbb{R}^D} \frac12\mathbf{w}^\top\mathbf{w} \qquad\text{subject to}\qquad \mathbf{w}^\top\mathbf{x} \geq 1$$

Derive the Lagrangian dual by introducing the Lagrange multiplier $\lambda$.

Solution

Standard form first. The constraint $\mathbf{w}^\top\mathbf{x} \geq 1$ becomes $g(\mathbf{w}) = 1 - \mathbf{w}^\top\mathbf{x} \leq 0$. Then

$$L(\mathbf{w}, \lambda) = \frac12\mathbf{w}^\top\mathbf{w} + \lambda\big(1 - \mathbf{w}^\top\mathbf{x}\big), \qquad \lambda \geq 0$$

Minimise over $\mathbf{w}$. $\partial L/\partial\mathbf{w} = \mathbf{w} - \lambda\mathbf{x} = \mathbf{0}$, so

$$\mathbf{w} = \lambda\mathbf{x}$$

The optimal $\mathbf{w}$ is a multiple of the data point — a one-point version of the representer property that Chapter 12 leans on. Substituting:

$$D(\lambda) = \frac12\lambda^2\lVert\mathbf{x}\rVert^2 + \lambda\big(1 - \lambda\lVert\mathbf{x}\rVert^2\big) = \lambda - \frac12\lambda^2\lVert\mathbf{x}\rVert^2$$

so the dual problem is

$$\boxed{\ \max_{\lambda \geq 0}\ \lambda - \frac12\lambda^2\lVert\mathbf{x}\rVert^2\ }$$

A concave quadratic in one variable. Its unconstrained maximum is at

$$\lambda^\star = \frac{1}{\lVert\mathbf{x}\rVert^2}$$

which is positive, so the constraint $\lambda \geq 0$ is inactive and this is the answer. The optimal value is

$$d^\star = \frac{1}{\lVert\mathbf{x}\rVert^2} - \frac12\cdot\frac{1}{\lVert\mathbf{x}\rVert^4}\lVert\mathbf{x}\rVert^2 = \frac{1}{2\lVert\mathbf{x}\rVert^2}$$

Check against the primal. $\mathbf{w}^\star = \lambda^\star\mathbf{x} = \mathbf{x}/\lVert\mathbf{x}\rVert^2$, so $\tfrac12\lVert\mathbf{w}^\star\rVert^2 = \tfrac12\lVert\mathbf{x}\rVert^2/\lVert\mathbf{x}\rVert^4 = 1/(2\lVert\mathbf{x}\rVert^2)$. Same value. And the constraint is tight: $\mathbf{w}^{\star\top}\mathbf{x} = 1$ exactly.

What this problem is. Minimising $\lVert\mathbf{w}\rVert$ subject to a unit margin is the maximum-margin problem. The margin is $1/\lVert\mathbf{w}\rVert = \lVert\mathbf{x}\rVert$, so shrinking $\lVert\mathbf{w}\rVert$ widens the margin — and the answer says the widest margin achievable with a single point at distance $\lVert\mathbf{x}\rVert$ is $\lVert\mathbf{x}\rVert$. That is the whole SVM, with one data point.

verify_7_8.py

import numpy as np
 
rng = np.random.default_rng(11)
print("L = 1/2 w^T w + lam(1 - w^T x); dL/dw = w - lam x = 0")
print("so w = lam x, and D(lam) = lam - 1/2 lam^2 ||x||^2")
print("maximised at lam* = 1/||x||^2, giving d* = 1/(2||x||^2)")
print(f"\n{'||x||':>10} {'lam*':>12} {'d*':>12} {'primal':>12} {'gap':>10}")
for _ in range(4):
    x = rng.standard_normal(5) * rng.uniform(0.5, 3)
    n2 = x @ x
    lam = 1.0 / n2
    w = lam * x
    primal = 0.5 * w @ w
    dual = lam - 0.5 * lam ** 2 * n2
    assert abs(w @ x - 1.0) < 1e-12            # the constraint is tight
    print(f"{np.sqrt(n2):>10.6f} {lam:>12.6f} {dual:>12.6f} "
          f"{primal:>12.6f} {abs(primal - dual):>10.1e}")
print("the constraint is active at the optimum in every case, and")
print("d* = 1/(2||x||^2) exactly.")

text

L = 1/2 w^T w + lam(1 - w^T x); dL/dw = w - lam x = 0
so w = lam x, and D(lam) = lam - 1/2 lam^2 ||x||^2
maximised at lam* = 1/||x||^2, giving d* = 1/(2||x||^2)
 
     ||x||         lam*           d*       primal        gap
  5.424824     0.033980     0.016990     0.016990    6.9e-18
  4.621385     0.046823     0.023411     0.023411    3.5e-18
  2.195402     0.207478     0.103739     0.103739    1.4e-17
  3.287618     0.092520     0.046260     0.046260    0.0e+00
the constraint is active at the optimum in every case, and
d* = 1/(2||x||^2) exactly.

Where people get stuck: forgetting to rewrite $\mathbf{w}^\top\mathbf{x} \geq 1$ as $1 - \mathbf{w}^\top\mathbf{x} \leq 0$ before forming the Lagrangian. Keep the $\geq$ and you get $+\lambda(\mathbf{w}^\top\mathbf{x} - 1)$, whose stationary point is $\mathbf{w} = -\lambda\mathbf{x}$ and whose dual comes out with the wrong sign.

§7.3.3 — Convex conjugates

Exercise 7.9

Consider the negative entropy of $\mathbf{x} \in \mathbb{R}^D$,

$$f(\mathbf{x}) = \sum_{d=1}^{D} x_d\log x_d$$

Derive the convex conjugate $f^*(\mathbf{s})$, assuming the standard dot product.

Solution

Use separability first. By Example 7.8, since $f$ is a sum of functions of individual coordinates, the conjugate is the sum of the coordinate conjugates:

$$f^*(\mathbf{s}) = \sum_{d=1}^{D} \ell^*(s_d), \qquad \ell(t) = t\log t$$

So there is a single one-dimensional calculation to do.

One coordinate.

$$\ell^*(s) = \sup_{t>0}\ \big(st - t\log t\big)$$

Take the derivative in $t$ and set it to zero — the hint’s instruction:

$$\frac{\mathrm{d}}{\mathrm{d}t}\big(st - t\log t\big) = s - \log t - 1 = 0 \quad\Longrightarrow\quad \log t = s - 1 \quad\Longrightarrow\quad t = e^{\,s-1}$$

Substituting, and this is the pleasing part:

$$\ell^*(s) = s\,e^{\,s-1} - e^{\,s-1}(s - 1) = e^{\,s-1}\big(s - s + 1\big) = e^{\,s-1}$$

Therefore

$$\boxed{\ f^*(\mathbf{s}) = \sum_{d=1}^{D} e^{\,s_d - 1}\ }$$

Two sanity checks. The second derivative of $st - t\log t$ is $-1/t < 0$ for $t > 0$, so the stationary point really is a maximum. And the answer is convex in $\mathbf{s}$ (a sum of exponentials), as every conjugate must be.

Why it is worth knowing. The negative entropy is the objective behind the softmax, and its conjugate being an exponential sum is where $\log\sum_d e^{s_d}$ comes from in classification. The pairing “entropy on one side, log-sum-exp on the other” is this exercise.

verify_7_9.py

import numpy as np
 
tg = np.linspace(1e-9, 60, 600001)
print(f"{'s':>7} {'grid sup':>14} {'exp(s-1)':>14} {'argmax t':>12} "
      f"{'exp(s-1)':>12}")
for s in (-2.0, 0.0, 1.0, 2.5):
    vals = s * tg - tg * np.log(tg)
    k = int(np.argmax(vals))
    print(f"{s:>7.2f} {vals[k]:>14.8f} {np.exp(s - 1):>14.8f} "
          f"{tg[k]:>12.6f} {np.exp(s - 1):>12.6f}")
 
rng = np.random.default_rng(11)
_ = [rng.standard_normal(5) * rng.uniform(0.5, 3) for _ in range(4)]  # same stream
D = 4
sv = rng.standard_normal(D)
grid = np.linspace(1e-9, 40, 200001)
per = np.array([(sv[d] * grid - grid * np.log(grid)).max() for d in range(D)])
print(f"\nvector check, D = {D}:  sum of per-coordinate sups = {per.sum():.9f}")
print(f"                        sum of exp(s_d - 1)        = "
      f"{np.exp(sv - 1).sum():.9f}")

text

      s       grid sup       exp(s-1)     argmax t     exp(s-1)
  -2.00     0.04978707     0.04978707     0.049800     0.049787
   0.00     0.36787944     0.36787944     0.367900     0.367879
   1.00     1.00000000     1.00000000     1.000000     1.000000
   2.50     4.48168907     4.48168907     4.481700     4.481689
 
vector check, D = 4:  sum of per-coordinate sups = 0.558944757
                        sum of exp(s_d - 1)        = 0.558944845

Where people get stuck: attacking the $D$-dimensional supremum directly instead of invoking Example 7.8 first. The vector problem decouples completely, so all the work is one scalar calculus problem — and noticing that is most of the exercise.

Exercise 7.10

Consider the function

$$f(\mathbf{x}) = \frac12\mathbf{x}^\top\mathbf{A}\mathbf{x} + \mathbf{b}^\top\mathbf{x} + c$$

where $\mathbf{A}$ is strictly positive definite, hence invertible. Derive the convex conjugate of $f$.

Solution

$$f^*(\mathbf{s}) = \sup_{\mathbf{x}}\Big(\mathbf{s}^\top\mathbf{x} - \frac12\mathbf{x}^\top\mathbf{A}\mathbf{x} - \mathbf{b}^\top\mathbf{x} - c\Big)$$

Take the gradient in $\mathbf{x}$ and set it to zero:

$$\mathbf{s} - \mathbf{A}\mathbf{x} - \mathbf{b} = \mathbf{0} \quad\Longrightarrow\quad \mathbf{x}^\star = \mathbf{A}^{-1}(\mathbf{s} - \mathbf{b})$$

This is a genuine maximum because the Hessian of the objective in $\mathbf{x}$ is $-\mathbf{A}$, which is negative definite. Write $\mathbf{d} = \mathbf{s} - \mathbf{b}$ and substitute:

$$f^*(\mathbf{s}) = \mathbf{s}^\top\mathbf{A}^{-1}\mathbf{d} - \frac12\mathbf{d}^\top\mathbf{A}^{-1}\mathbf{d} - \mathbf{b}^\top\mathbf{A}^{-1}\mathbf{d} - c$$

The first and third terms combine, since $\mathbf{s}^\top\mathbf{A}^{-1}\mathbf{d} - \mathbf{b}^\top\mathbf{A}^{-1}\mathbf{d} = (\mathbf{s}-\mathbf{b})^\top\mathbf{A}^{-1}\mathbf{d} = \mathbf{d}^\top\mathbf{A}^{-1}\mathbf{d}$, leaving

$$\boxed{\ f^*(\mathbf{s}) = \frac12(\mathbf{s} - \mathbf{b})^\top\mathbf{A}^{-1}(\mathbf{s} - \mathbf{b}) - c\ }$$

Read off the pattern, because it generalises: $\mathbf{A}$ inverts, $\mathbf{b}$ becomes a shift of the argument, and $c$ flips sign. Setting $\mathbf{b} = \mathbf{0}$, $c = 0$ and $\mathbf{A} = \lambda\mathbf{K}^{-1}$ recovers Example 7.7, and setting $\mathbf{A} = 2$, $\mathbf{b} = 0$, $c = 0$ in one dimension recovers $f^*(s) = s^2/4$ for $f(x) = x^2$.

verify_7_10.py

import numpy as np
 
A = np.array([[3.0, 1.0], [1.0, 2.0]])
b = np.array([1.0, -2.0])
c = 0.7
Ai = np.linalg.inv(A)
print(f"A eigenvalues {np.linalg.eigvalsh(A).round(6).tolist()} -> "
      f"strictly positive definite")
 
f_star = lambda s: 0.5 * (s - b) @ Ai @ (s - b) - c
g = np.linspace(-16, 16, 2401)
X1, X2 = np.meshgrid(g, g)
FX = (0.5 * (3 * X1 ** 2 + 2 * X1 * X2 + 2 * X2 ** 2)
      + b[0] * X1 + b[1] * X2 + c)
for s in ([0.0, 0.0], [2.0, 2.0], [-3.0, 4.0]):
    s = np.array(s)
    print(f"  s = {str(s.tolist()):12} grid sup = "
          f"{(s[0] * X1 + s[1] * X2 - FX).max():10.6f}   closed form = "
          f"{f_star(s):10.6f}")

text

A eigenvalues [1.381966, 3.618034] -> strictly positive definite
  s = [0.0, 0.0]   grid sup =   1.100000   closed form =   1.100000
  s = [2.0, 2.0]   grid sup =   3.500000   closed form =   3.500000
  s = [-3.0, 4.0]  grid sup =  18.100000   closed form =  18.100000

Where people get stuck: dropping the cross terms when substituting. It is worth doing the $\mathbf{s}^\top\mathbf{A}^{-1}\mathbf{d} - \mathbf{b}^\top\mathbf{A}^{-1}\mathbf{d}$ combination explicitly rather than by eye — the symmetry of $\mathbf{A}^{-1}$ is what makes it collapse so cleanly.

Exercise 7.11

The hinge loss, used by the support vector machine, is

$$L(\alpha) = \max\{0,\ 1 - \alpha\}$$

If we want to use gradient methods such as L-BFGS and do not want to resort to subgradient methods, we need to smooth the kink. Compute the convex conjugate $L^*(\beta)$. Then add an $\ell_2$ proximal term and compute the conjugate of

$$L^*(\beta) + \frac{\gamma}{2}\beta^2$$

Solution

Part 1: the conjugate.

$$L^*(\beta) = \sup_{\alpha}\ \big(\beta\alpha - \max\{0, 1-\alpha\}\big)$$

Split at $\alpha = 1$, where the max switches branch.

For $\alpha \geq 1$: the loss is $0$, so the expression is $\beta\alpha$. Its supremum over $[1,\infty)$ is $+\infty$ if $\beta > 0$, and $\beta$ (attained at $\alpha = 1$) if $\beta \leq 0$.

For $\alpha < 1$: the loss is $1-\alpha$, so the expression is $\beta\alpha - 1 + \alpha = (\beta+1)\alpha - 1$. Its supremum over $(-\infty, 1)$ is $+\infty$ if $\beta + 1 < 0$, and $\beta$ (approached as $\alpha \to 1^-$) if $\beta + 1 > 0$.

Both branches are finite exactly when $-1 \leq \beta \leq 0$, and both give $\beta$:

$$L^*(\beta) = \begin{cases}\beta & -1 \leq \beta \leq 0\\ +\infty & \text{otherwise}\end{cases}$$

A piecewise-linear function with one kink became a linear function on a box. Kinks in the primal become domain boundaries in the dual.

Part 2: add the proximal term and conjugate back. Let $h(\beta) = L^*(\beta) + \tfrac\gamma2\beta^2$. The infinite values confine the supremum to the box:

$$h^*(\alpha) = \sup_{-1\leq\beta\leq 0}\Big(\alpha\beta - \beta - \frac\gamma2\beta^2\Big) = \sup_{-1\leq\beta\leq 0}\Big(u\beta - \frac\gamma2\beta^2\Big), \qquad u = \alpha - 1$$

The unconstrained maximiser is $\beta = u/\gamma$. Three cases, depending on whether it lands in the box:

$\alpha$	maximiser	$h^*(\alpha)$
$\alpha > 1$, so $u > 0$	$\beta = 0$ (clipped above)	$0$
$1-\gamma \leq \alpha \leq 1$, so $-\gamma \leq u \leq 0$	$\beta = \dfrac{\alpha-1}{\gamma}$	$\dfrac{(1-\alpha)^2}{2\gamma}$
$\alpha < 1-\gamma$, so $u < -\gamma$	$\beta = -1$ (clipped below)	$1 - \alpha - \dfrac\gamma2$

$$\boxed{\ h^*(\alpha) = \begin{cases} 0 & \alpha \geq 1\\[4pt] \dfrac{(1-\alpha)^2}{2\gamma} & 1-\gamma \leq \alpha \leq 1\\[6pt] 1 - \alpha - \dfrac\gamma2 & \alpha \leq 1-\gamma\end{cases}\ }$$

This is the Moreau envelope of the hinge: flat, then a parabola, then linear.

Two properties, both measured at $\gamma = 0.6$.

It is differentiable everywhere. At $\alpha = 1-\gamma$ the left branch has slope $-1$ and the middle branch has slope $-(1-\alpha)/\gamma = -\gamma/\gamma = -1$. At $\alpha = 1$ the middle branch has slope $0$, matching the flat branch. Measured slope jump at both joins: $8.3\times10^{-8}$, which is finite-difference error — a real kink gives a jump of order one. This is what the exercise was for.

It is biased low by exactly $\gamma/2$. On the linear branch, $(1 - \alpha - \tfrac\gamma2) - (1-\alpha) = -\tfrac\gamma2$. Measured maximum deviation from the hinge over $[-3,3]$: $0.300000$, and $\gamma/2 = 0.300000$. So $\gamma$ trades smoothness against fidelity at a fixed rate, and there is no setting that gives both.

verify_7_11.py

import numpy as np
 
gam = 0.6
hinge = lambda a: np.maximum(0.0, 1.0 - a)
smooth = lambda a: np.where(a >= 1, 0.0,
                            np.where(a >= 1 - gam, (1 - a) ** 2 / (2 * gam),
                                     1 - a - gam / 2))
 
# the numeric conjugate of L*(beta) + (gamma/2) beta^2, over the box [-1, 0]
bb = np.linspace(-1.0, 0.0, 40001)
num = lambda a: (a * bb - (bb + 0.5 * gam * bb ** 2)).max()
 
al = np.linspace(-3, 3, 601)
print(f"gamma = {gam}")
print(f"max |numeric - closed form| over 601 alphas: "
      f"{np.abs(np.array([num(a) for a in al]) - smooth(al)).max():.3e}")
fine = np.linspace(-3, 3, 60001)
print(f"max |smoothed - hinge| = {np.abs(smooth(fine) - hinge(fine)).max():.6f}"
      f"   gamma/2 = {gam / 2:.6f}")
h = 1e-7
for a in (1.0 - gam, 1.0):
    dl = (smooth(a) - smooth(a - h)) / h
    dr = (smooth(a + h) - smooth(a)) / h
    print(f"  at alpha = {a:.2f}: slope jump {float(abs(dr - dl)):.1e}")

text

gamma = 0.6
max |numeric - closed form| over 601 alphas: 2.083e-11
max |smoothed - hinge| = 0.300000   gamma/2 = 0.300000
  at alpha = 0.40: slope jump 8.3e-08
  at alpha = 1.00: slope jump 8.3e-08

Where people get stuck: forgetting that $L^*$ is $+\infty$ outside $[-1,0]$ and taking the supremum over all of $\mathbb{R}$ in part 2. The infinite values are what restrict the supremum to the box, and the box is what produces the two clipped branches — without them you would get only the parabola, which is not the answer.

🧪 Try It Yourself

These five run the exercises above rather than restating them, and each one is the step where the solution actually turns.

Exercise 1 – Classify 7.1’s stationary points

pch.exerciseTag pch.exerciseTitle

Exercise 2 – 7.3’s counterexamples must be disjoint

pch.exerciseTag pch.exerciseTitle

Exercise 3 – 7.5 in matrix form, and its unboundedness

pch.exerciseTag pch.exerciseTitle

Exercise 4 – 7.8’s dual, and its tight constraint

pch.exerciseTag pch.exerciseTitle

Exercise 5 – 7.9’s separable conjugate

pch.exerciseTag pch.exerciseTitle

Recall card

• 7.1: f’ = 3(x^2 + 4x - 1) gives stationary points at -2 plus or minus root 5, i.e. -4.2360680 (maximum, f” = -13.4164079) and 0.2360680 (minimum, f” = +13.4164079). No saddle: a saddle needs two dimensions. The inflection at x = -2 has f’ = -15, so it is not stationary.
• 7.2: with a mini-batch of one, theta next equals theta minus gamma times the gradient of a single randomly chosen L_n. Unbiasedness is all convergence needs — and the factor N is what makes one term unbiased for the SUM rather than the mean.
• 7.3: intersection TRUE always and for any family; union and difference FALSE in general. The counterexamples must be DISJOINT — an overlapping union or difference of intervals is convex.
• 7.4: sum TRUE, difference FALSE, product FALSE, maximum TRUE. Measured with x squared and exp(-x): the difference reaches f” = -5.3872 and the product -0.4120. The maximum destroys differentiability, not convexity.
• 7.5: with z = (x0, x1, xi), c = (-p0, -p1, -1) and A rows (1,0,0), (0,1,0), (0,0,-1) against b = (0, 3, 0). Every “greater than or equal” constraint needs BOTH the row and the right-hand side negated. As printed the program is unbounded, since xi has no upper bound.
• 7.6: three steps, and step 3’s condition c + A-transpose lambda = 0 contains no x, so it becomes a constraint and the dual is another LP. lambda-star = (13/6, 1/3, 0, 0, 0), value -445/6 both sides.
• 7.7: the same three steps, but step 3 contains x, so Eq 7.50 substitutes back and the dual is a concave quadratic with only lambda at least zero. lambda-star = (0, 2.5, 0, 0), gap exactly zero. Requires Q strictly positive definite, not merely semidefinite.
• 7.8: rewrite the constraint as 1 - w-transpose x at most 0 FIRST. Then w = lambda x, D(lambda) = lambda - half lambda squared times the squared norm of x, lambda-star = 1 over that norm squared, and d-star = 1/(2||x||^2). This is the maximum-margin problem with one data point.
• 7.9: separable by Example 7.8, so one scalar problem: t = exp(s-1) and the value is exp(s-1) too. Hence f-star(s) = sum of exp(s_d - 1). This pairing of entropy with an exponential sum is where log-sum-exp comes from.
• 7.10: f-star(s) = half (s - b)-transpose A-inverse (s - b) minus c. The pattern generalises: A inverts, b shifts the argument, c flips sign.
• 7.11: L-star(beta) = beta on [-1, 0] and infinite elsewhere — a kink in the primal became a domain boundary in the dual. Adding a proximal term and conjugating back gives three branches (0, then (1-alpha)^2/(2 gamma), then 1 - alpha - gamma/2), differentiable at both joins to 8.3e-8, and biased exactly gamma/2 below the hinge.
• The recurring lesson across 7.5 to 7.8: get the constraint into the form g at most 0 before writing any Lagrangian. Three of the four dual exercises are lost at that step and nowhere else.

Next: everything in one place — Chapter 7 Formula Sheet