Unit 5.1 · about 5 h
80 / 324Convexity, optimality conditions and conditioning
An optimizer's behavior starts with the objective's geometry. These conditions tell you which local evidence certifies a global solution and which does not.
- derive
You can now
- Prove the first- and second-order characterizations of a differentiable convex function on an open convex domain.
- Distinguish stationary points, local minima and global minima, including degenerate Hessians.
- Read smoothness, strong convexity and conditioning from a quadratic's eigenvalues.
Covers
- Convex sets, convex functions and geometric intuition
- First- and second-order optimality conditions
- Smoothness, strong convexity and conditioning
Study, in this order
3 steps
- EE364a: convex sets and convex functionsStanford EE364a - Convex Optimization
Lecture 2 notes: Convex set (slide 2-3), Convex combination and convex hull (2-4), Hyperplanes and halfspaces (2-6), and Intersection (2-12)
Depth · Read these headings only. Use the book below for the proofs; leave separation and generalized inequalities aside.
- EE364a: derivative tests for convexityStanford EE364a - Convex Optimization
Lectures 3 and 4 notes: First-order condition (slide 3-7), Second-order conditions (3-8), and Examples (3-9): quadratic and least-squares functions
- Convexity proofs and curvature boundsConvex Optimization
Sections 2.1.4 (pp. 23 to 25), 3.1.1 to 3.1.4 (pp. 67 to 71), 4.2.3 through Unconstrained problems (pp. 139 to 141), and 9.1.2 (pp. 459 to 463)
Depth · Prove the derivative tests using restrictions to lines. In 9.1.2 focus on the lower and upper quadratic models and the ratio \(M/m\), not the width calculation.
Focus on
- A convex set contains every segment between its points. A convex function has a convex domain and lies below each chord; its tangent planes lie below its graph.
- For \(C^2\) functions on an open convex domain, a PSD Hessian everywhere characterizes convexity. At one stationary point, a PSD Hessian is only a necessary local-minimum condition; a PD Hessian is sufficient.
- For \(f(x)=x^\top Qx/2\) with symmetric positive definite \(Q\), \(\mu=\lambda_{\min}(Q)\), \(L=\lambda_{\max}(Q)\), and \(\kappa=L/\mu\). The gradient is \(L\)-Lipschitz and the lower quadratic model uses \(\mu/2\).
Reproduce closed-book
float64 arrays, np.linalg.eigvalsh(Q) and np.linalg.cond(Q); scalar absolute differences from [1,9], 9 and 5 must be below 1e-12. No random draws are needed.Traps
- Dropping the convex-domain assumption: \(1/x^2\) has positive second derivative on its disconnected domain, but that domain is not convex.
- Calling every stationary point a minimum: \(x^2-y^2\) has a saddle at the origin.
- Equating strict and strong convexity: \(x^4\) is strictly convex on \(\mathbb{R}\) but has no positive global lower curvature bound.
Practice
Convex Optimization: Exercise 3.8, Second-order condition for convexity
Exercise 3.8, printed p. 114
Attempt both directions before looking back at the first-order proof on p. 70. Give the disconnected-domain counterexample as well.
Self-test
-
Where are the assumptions used in the first-order proof?
Convexity of the domain keeps \(x+t(y-x)\) inside it. Convexity of \(f\) supplies the chord inequality; divide by positive \(t\) and use differentiability as \(t\) tends to zero. Conversely, apply the tangent inequality at \(z=\theta x+(1-\theta)y\) to \(x\) and \(y\). Nonnegative weights preserve inequalities and cancel the derivative terms; domain convexity ensures \(z\) exists. At \(\theta=0\) or \(1\) the chord statement is equality. -
Why does a zero gradient certify a global minimum only in the convex case?
The convex tangent lower bound becomes \(f(y)\ge f(x)\) for every feasible \(y\). Without convexity that lower bound need not hold; \(-x^2\) has zero derivative at its maximum. -
Does a zero Hessian at a stationary point settle local optimality?
No. At zero, \(x^4\) has a minimum and \(-x^4\) has a maximum; both have zero derivative and zero second derivative. -
Why is \(\mu>0\) needed for uniqueness?
The strong-convexity midpoint inequality subtracts \(\mu\|x-y\|_2^2/8\). Two distinct minimizers would therefore give a midpoint below the optimal value. Convexity keeps the midpoint feasible; \(\mu>0\) makes the subtraction strictly positive.
Completion criterion
Stop when
You can prove both derivative tests with their domain assumptions, classify the three stationary-point counterexamples, and recover the quadratic's curvature bounds without notes.
Mark passed, then open 5.2 Only mark this when you can do it without notes.Leads to
- 2.2 Conditioning, basis expansions, ridge, lasso and elastic net Apply curvature and conditioning to ridge regression.
Comes after
- 2.2 Jacobians, Hessians and Taylor approximationsHessian definiteness becomes the second-order optimality condition.
Resources for this unit
- Stanford EE364a - Convex Optimization Follow lectures 1-9 and 15-16; use lecture 17 only for KKT systems. Leave full interior-point treatment for later.
- Convex Optimization Read Chapters 1-5 and 9 with the course; use Chapter 10 only for equality-constrained Newton steps.
Also in this section
- D2L - Optimization Algorithms Use the convexity, GD, SGD, minibatch, momentum, AdaGrad, RMSProp, Adam and scheduler sections for ML derivations and code.
- Fundamentals of Numerical Computation Study §§1.1-1.4, 2.7-2.8, 3.2-3.4 and 4.2-4.3 for floating point, conditioning, stability, least squares and iteration error, in the Python edition.
- CVXPY basic and DCP tutorials Use as the solver oracle after deriving a constrained problem and its KKT conditions by hand.
- Proximal Algorithms Read Sections 1.1, 4.2 and the elementwise soft-thresholding formula in 6.5.2, then the lasso formulation on p. 196. Skip 7.1.1's penalty-scaling and Gram-rewrite errors on p. 197; derive the update from 4.2 and 6.5.2.
- PyTorch optimizer and gradient-clipping contracts Use AdamW's algorithm and
clip_grad_norm_'s parameters to locate weight decay and clipping precisely. Inspectstate_dictfor optimizer restart; no network training is assigned. - SciPy minimize: BFGS Read the BFGS method description and
gtol,maxiter,c1andc2options. Supply an analytic gradient and compare residuals and evaluation counts, not just iterations. - PyTorch numerical type information Read
torch.finfo'seps,maxandsmallest_normalfields and its subnormal note; inspectfloat64,float32,float16andbfloat16on CPU. - The Accuracy of Floating Point Summation Read Section 2's recursive-sum error bound and Section 3's pairwise and compensated summation algorithms. Leave the statistical error models and historical machine details aside.
- Accurately computing running variance Read the Welford mean and centered-sum recurrences. Prove the centered-sum invariant and translate the recurrence to NumPy; skip the C++ class.