Day 25: Unconstrained Optimisation & Convexity

Theory

Conditions for an optimum

For a smooth $f: \mathbb{R}^k \to \mathbb{R}$ :

First-order condition (FOC): at an interior optimum, $\nabla f(x^*) = 0$ .
Second-order condition (SOC): if also $H(x^*)$ is positive definite, $x^*$ is a strict local minimum; negative definite, a strict local maximum; indefinite, a saddle point.

Convexity

A function is convex if the chord lies above the graph:

f(\lambda x + (1 - \lambda)y) \le \lambda f(x) + (1 - \lambda)f(y), \qquad \lambda \in [0, 1].

For smooth functions, convex $\iff$ the tangent plane lies below: $f(y) \ge f(x) + \nabla f(x)^{\top}(y - x)$ $\iff$ $H(x)$ is PSD everywhere. The payoff: for a convex function, any point with zero gradient is a global minimum, and strict convexity makes it unique. Least squares, ridge, lasso and the (negative) logit log-likelihood are all convex.

Algorithms

When the FOC cannot be solved by hand:

Gradient descent: $x_{t+1} = x_t - \eta\nabla f(x_t)$ . Cheap per step; needs a good step size $\eta$ . On a quadratic with Hessian eigenvalues $\lambda_j$ it converges iff $\eta < 2/\lambda_{\max}$ , and slowly when the condition number is large.
Newton's method: $x_{t+1} = x_t - H(x_t)^{-1}\nabla f(x_t)$ . It minimises the local second-order Taylor approximation (Day 23) at each step; it solves a quadratic in one step and converges very fast near the optimum, but each step needs the Hessian.

For maximum likelihood, Newton's method applied to $\ell$ is the classic Newton–Raphson (for the logit it is called iteratively reweighted least squares).

Part 1 · Warm-up

Exercise 1 · A parabola

Minimise $f(x) = x^2 - 6x + 11$ .

Show solution

$f'(x) = 2x - 6 = 0 \Rightarrow x = 3$ ; $f''= 2 > 0$ , a minimum with $f(3) = 2$ .

Exercise 2 · A cubic

Find and classify the critical points of $f(x) = x^3 - 3x$ .

Show solution

Step 1. $3x^2 - 3 = 0 \Rightarrow x = \pm1$ .

Step 2. $f'' = 6x$ : local minimum at $x = 1$ , local maximum at $x = -1$ .

Step 3. Neither is global: $f$ is unbounded in both directions.

Exercise 3 · Two variables

Minimise $f(x, y) = x^2 + xy + y^2 - 3x$ .

Show solution

Step 1. FOC: $f_x = 2x + y - 3 = 0$ and $f_y = x + 2y = 0$ .

Step 2. From the second, $x = -2y$ ; substitute: $-4y + y = 3 \Rightarrow y = -1$ , $x = 2$ .

Step 3. Hessian $\begin{pmatrix}2 & 1\\1 & 2\end{pmatrix}$ has eigenvalues 3 and 1 (Day 21): PD, so $f$ is strictly convex and $(2, -1)$ is the global minimum.

Step 4. $f(2, -1) = 4 - 2 + 1 - 6 = -3$ .

Answer: minimum −3 at $(2, -1)$ .

Exercise 4 · A saddle

Classify the critical point of $f(x, y) = x^2 - y^2$ .

Show solution

$\nabla f = (2x, -2y) = 0$ at the origin; $H = \operatorname{diag}(2, -2)$ is indefinite: a saddle (minimum along $x$ , maximum along $y$ ).

Exercise 5 · Step sizes

Run two steps of gradient descent on $f(x) = x^2$ from $x_0 = 4$ with $\eta = 0.25$ , then with $\eta = 1$ and $\eta = 1.1$ .

Show solution

Step 1. $f'(x) = 2x$ , so $x_{t+1} = x_t - \eta(2x_t) = (1 - 2\eta)x_t$ .

Step 2. $\eta = 0.25$ : factor 0.5, so $4 \to 2 \to 1$ (converges).

Step 3. $\eta = 1$ : factor −1, so $4 \to -4 \to 4$ (oscillates forever).

Step 4. $\eta = 1.1$ : factor −1.2, so $4 \to -4.8 \to 5.76$ (diverges).

Answer: here the Hessian is $\lambda = 2$ , and convergence needs $|1 - 2\eta| < 1$ , i.e. $\eta < 2/\lambda = 1$ (Exercise 10).

Part 2 · Proofs

Exercise 6 · Stationary means optimal under convexity

Prove that if $f$ is convex and differentiable and $\nabla f(x^*) = 0$ , then $x^*$ is a global minimum.

Show solution

By the tangent-plane characterisation, for every $y$ : $f(y) \ge f(x^*) + \nabla f(x^*)^{\top}(y - x^*) = f(x^*)$ .

Exercise 7 · Building convex functions

Prove that the sum of two convex functions is convex, and that $g(x) = f(Ax + b)$ is convex when $f$ is.

Show solution

Step 1. Sum: add the two chord inequalities.

Step 2. Composition: $g(\lambda x + (1 - \lambda)y) = f(\lambda(Ax + b) + (1 - \lambda)(Ay + b)) \le \lambda f(Ax + b) + (1 - \lambda)f(Ay + b)$ .

Step 3. Hence $\|y - X\beta\|^2 + \lambda\|\beta\|^2$ is convex in $\beta$ .

Exercise 8 · Uniqueness

Prove that a strictly convex function has at most one minimiser.

Show solution

Suppose $x \ne y$ both attain the minimum $m$ . Strict convexity gives $f(\tfrac12x + \tfrac12y) < \tfrac12m + \tfrac12m = m$ , contradicting minimality.

Exercise 9 · Newton solves quadratics in one step

Show that Newton's method reaches the minimiser of $f(x) = \frac12x^{\top}Ax - b^{\top}x$ ( $A$ PD) in one step from any start.

Show solution

Step 1. $\nabla f = Ax - b$ , $H = A$ .

Step 2. Then $x_1 = x_0 - A^{-1}(Ax_0 - b) = A^{-1}b$ , which solves $\nabla f = 0$ .

Step 3. So Newton applied to least squares returns $(X^{\top}X)^{-1}X^{\top}y$ immediately.

Exercise 10 · When gradient descent converges

For $f(x) = \frac12x^{\top}Ax$ with $A$ PD, show gradient descent converges to 0 iff $\eta < 2/\lambda_{\max}$ .

Show solution

Step 1. $\nabla f = Ax$ , so $x_{t+1} = x_t - \eta Ax_t = (I - \eta A)x_t$ , and by induction $x_t = (I - \eta A)^tx_0$ .

Step 2. If $Aq_j = \lambda_jq_j$ , then $(I - \eta A)q_j = (1 - \eta\lambda_j)q_j$ : same eigenvectors, eigenvalues $1 - \eta\lambda_j$ .

Step 3. Write $x_0 = \sum_jc_jq_j$ . Then $x_t = \sum_jc_j(1 - \eta\lambda_j)^tq_j$ .

Step 4. $x_t \to 0$ for every start iff $|1 - \eta\lambda_j| < 1$ for all $j$ , i.e. $0 < \eta < 2/\lambda_j$ for all $j$ , i.e. $\eta < 2/\lambda_{\max}$ .

Step 5. Speed: the slowest direction shrinks by $|1 - \eta\lambda_{\min}|$ per step. With $\eta$ near $2/\lambda_{\max}$ and $\lambda_{\min} \ll \lambda_{\max}$ (ill-conditioning), this is close to 1, so progress is slow.

Part 3 · Applied

Exercise 11 · A competitive firm

A firm sells at $p = 10$ , produces $q = 2L^{0.5}$ and pays wage $w = 5$ . Find the profit-maximising labour, output and profit.

Show solution

Step 1. Profit: $\pi(L) = p\,q - wL = 10(2L^{0.5}) - 5L = 20L^{0.5} - 5L$ .

Step 2. FOC: $\pi'(L) = 10L^{-0.5} - 5 = 0 \Rightarrow L^{-0.5} = 0.5 \Rightarrow L = 4$ .

Step 3. SOC: $\pi''(L) = -5L^{-1.5} < 0$ : a maximum.

Step 4. Output $q = 2\sqrt4 = 4$ ; profit $= 40 - 20 = 20$ .

Answer: hire 4 units of labour, produce 4, earn profit 20 (the value of the marginal product equals the wage).

Exercise 12 · Monopoly pricing

Inverse demand $P = 100 - 2Q$ , cost $C = 20Q$ . Find the monopoly quantity, price and profit.

Show solution

Step 1. Profit: $\pi(Q) = (100 - 2Q)Q - 20Q = 80Q - 2Q^2$ .

Step 2. FOC (marginal revenue = marginal cost): $80 - 4Q = 0 \Rightarrow Q = 20$ . SOC: $\pi'' = -4 < 0$ .

Step 3. Price: $P = 100 - 2(20) = 60$ .

Step 4. Profit: $(60 - 20) \times 20 = 800$ .

Answer: $Q = 20$ , $P = 60$ , profit 800.

Exercise 13 · Newton–Raphson for a Poisson MLE

Ten counts have $\sum x_i = 30$ . Starting from $\lambda_0 = 1$ , perform two Newton–Raphson steps on $\ell(\lambda) = \sum x_i\ln\lambda - n\lambda$ .

Show solution

Step 1. Derivatives: $\ell'(\lambda) = 30/\lambda - 10$ and $\ell''(\lambda) = -30/\lambda^2$ . Newton update: $\lambda \leftarrow \lambda - \ell'(\lambda)/\ell''(\lambda)$ .

Step 2. From $\lambda_0 = 1$ : $\ell' = 20$ , $\ell'' = -30$ , so $\lambda_1 = 1 + 20/30 \approx 1.667$ .

Step 3. From $\lambda_1 = 5/3$ : $\ell' = 18 - 10 = 8$ , $\ell'' = -30/(25/9) = -10.8$ , so $\lambda_2 = 1.667 + 8/10.8 \approx 2.407$ .

Step 4. Further steps give 2.883, 2.995, 3.000 (code below).

Answer: the iterates converge to $\hat\lambda = \bar x = 3$ , slowly at first and then very fast near the optimum.

Exercise 14 · Estimating a CES production function

An economist fits a CES production function $\ln Y_i = \ln A + \frac{\nu}{\rho}\ln\big(\delta K_i^{\rho} + (1 - \delta)L_i^{\rho}\big) + \varepsilon_i$ by non-linear least squares. The objective can have several local minima and flat regions (e.g. near $\rho = 0$ , the Cobb–Douglas limit). What should she do?

Show solution

Step 1. Recognise the risk: a gradient method stops at a point with zero gradient, which need not be the global minimum.

Step 2. Start the optimiser from several points (or a grid over $\rho$ and $\delta$ ) and compare the objective values reached.

Step 3. Reparametrise where possible (e.g. profile out $\ln A$ , which enters linearly) and check the curvature (Hessian) at the solution.

Answer: use multiple starts, report sensitivity, and prefer formulations that are convex. This is one reason linear and logit models, whose objectives are convex, dominate applied work.

Exercise 15 · When the MLE does not exist

In a logit of treatment on one covariate, every unit with $x > 5$ is treated and every unit with $x \le 5$ is not. What happens to Newton–Raphson, and what does it mean for propensity-score methods?

Show solution

Step 1. Perfect separation: every unit with $x > 5$ is treated and every unit with $x \le 5$ is not.

Step 2. A steeper slope always fits better: the log-likelihood keeps increasing as $\beta_1 \to \infty$ , so there is no finite maximum.

Step 3. Newton–Raphson therefore diverges, with fitted probabilities heading to exactly 0 and 1 (the code shows the slope growing every iteration).

Answer: no MLE exists. For causal inference this is a failure of overlap: some covariate values have no comparison units, so effects there cannot be estimated without extrapolation (Day 42).

Verify in Python

import numpy as np

# Gradient descent on a quadratic with condition number 100 vs Newton
A = np.diag([1.0, 100.0]); grad = lambda x: A @ x
x = np.array([1.0, 1.0]); eta = 1.9 / 100
for t in range(200):
    x = x - eta * grad(x)
print("GD after 200 steps:", x.round(4), "  (slow along the small-eigenvalue direction)")
x0 = np.array([1.0, 1.0]); print("Newton after 1 step:", x0 - np.linalg.solve(A, grad(x0)))

# Newton-Raphson for the Poisson MLE (Exercise 13)
lam, path = 1.0, []
for _ in range(6):
    lam = lam - (30 / lam - 10) / (-30 / lam**2); path.append(round(lam, 4))
print("Newton path:", path)

# Perfect separation: the logit slope runs away
x = np.arange(1, 11.); T = (x > 5).astype(float); X = np.column_stack([np.ones(10), x]); b = np.zeros(2)
for it in range(8):
    p = 1 / (1 + np.exp(-X @ b)); W = p * (1 - p)
    b = b + np.linalg.solve(X.T @ (X * W[:, None]) + 1e-12 * np.eye(2), X.T @ (T - p))
    print(f"iteration {it + 1}: slope = {b[1]:.2f}")

Key takeaways

FOC finds candidates; the Hessian classifies them; convexity turns local into global.
Gradient descent is cheap but slowed by ill-conditioning; Newton uses curvature and converges fast near the optimum.
Non-existence of an MLE (separation) is a data problem, often an overlap problem, not a software problem.

Day 25. Unconstrained Optimisation & Convexity

Theory

Conditions for an optimum

Convexity

Algorithms

Part 1 · Warm-up

Exercise 1 · A parabola

Exercise 2 · A cubic

Exercise 3 · Two variables

Exercise 4 · A saddle

Exercise 5 · Step sizes

Part 2 · Proofs

Exercise 6 · Stationary means optimal under convexity

Exercise 7 · Building convex functions

Exercise 8 · Uniqueness

Exercise 9 · Newton solves quadratics in one step

Exercise 10 · When gradient descent converges

Part 3 · Applied

Exercise 11 · A competitive firm

Exercise 12 · Monopoly pricing

Exercise 13 · Newton–Raphson for a Poisson MLE

Exercise 14 · Estimating a CES production function

Exercise 15 · When the MLE does not exist

Verify in Python

Key takeaways

Simulation Lab: Gradient Descent vs Newton