Phase 10 - Lesson 10.2
Convex Optimization Problems and Optimality Conditions
Standard form, why local equals global, and the first-order optimality test.
Builds on: 10.1 defined convex sets and functions.
Leads to: 10.3 introduces duality; 10.5 applies this to portfolios.
Leads to: 10.3 introduces duality; 10.5 applies this to portfolios.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- Write a convex optimization problem in standard form and identify its feasible set as convex.
- Prove that any local minimum of a convex problem is a global minimum.
- State the first-order optimality condition over a convex feasible set.
- Specialize optimality to the unconstrained case (\(\nabla f=0\)) and to equality constraints.
- Implement Euclidean projection onto the probability simplex.
Key Vocabulary
- Standard form
- Minimize \(f_0(x)\) s.t. \(f_i(x)\le0\) (convex) and \(Ax=b\) (affine).
- Feasible set
- The set of \(x\) satisfying all constraints; convex when constraints are convex/affine.
- Global vs local minimum
- Global: best over the whole feasible set. Local: best within a neighborhood. For convex problems they coincide.
- Optimality condition
- A test a point must satisfy to be optimal; over a convex set it is a variational inequality.
- Projection
- The nearest feasible point to a given \(z\): \(\Pi_C(z)=\argmin_{x\in C}\|x-z\|_2\); well-defined and unique for convex \(C\).
- Convex program
- An optimization problem with convex objective and convex feasible set.
Intuition & Motivation
Intuition
Solving a general optimization problem is like exploring a mountain range in fog - you can never be sure the valley you found is the deepest. Convexity clears the fog: there is exactly one basin, so ‘can't improve locally’ means ‘can't improve at all’. That single guarantee is why convex problems are considered solved in practice and why so much modeling effort goes into casting problems as convex.
Standard form
\[\min_{x}\ f_0(x)\quad\text{s.t.}\quad f_i(x)\le 0\ (i=1,\dots,m),\quad Ax=b,\] (10.3)
with \(f_0,\dots,f_m\) convex and the equality constraints affine. The feasible set \(\{x:f_i(x)\le0,\ Ax=b\}\) is an intersection of convex sublevel sets and an affine subspace - hence convex.
Theorem - Local minima are global
For a convex problem, every local minimizer \(x^\star\) is a global minimizer.
Proof
Suppose \(x^\star\) is locally optimal but some feasible \(y\) has \(f_0(y)\lt f_0(x^\star)\). For small \(\theta\gt 0\), \(z=\theta y+(1-\theta)x^\star\) is feasible (convex feasible set) and, by convexity, \(f_0(z)\le\theta f_0(y)+(1-\theta)f_0(x^\star)\lt f_0(x^\star)\). As \(\theta\to0\), \(z\to x^\star\), so such \(z\) lie in every neighborhood - contradicting local optimality. Hence no better feasible \(y\) exists.
Theorem - First-order optimality (convex, differentiable)
With convex feasible set \(C\) and differentiable convex \(f_0\), a point \(x^\star\in C\) is optimal iff
\[\nabla f_0(x^\star)^\top(y-x^\star)\ \ge\ 0\quad\text{for all }y\in C.\] (10.4)
Interpretation: from the optimum, every feasible direction points ‘uphill or flat’ - no feasible descent direction exists. Two important specializations:
- Unconstrained (\(C=\R^n\)): (10.4) forces \(\nabla f_0(x^\star)=0\) - the familiar stationarity condition.
- Equality-constrained \(Ax=b\): feasible directions lie in the null space of \(A\), giving \(\nabla f_0(x^\star)\perp\mathcal N(A)\), i.e. \(\nabla f_0(x^\star)=A^\top\nu\) for some \(\nu\) (a preview of Lagrange multipliers).
Worked Example - Minimizing a quadratic on an affine set
1
Problem: \(\min\ \tfrac12\|x\|_2^2\) s.t. \(a^\top x=1\).
2
Optimality (10.4) with equality constraint: \(\nabla f_0=x^\star=\nu a\) for some scalar \(\nu\) (gradient parallel to constraint normal).
3
Enforce feasibility: \(a^\top(\nu a)=1\Rightarrow\nu=1/\|a\|_2^2\), so \(x^\star=a/\|a\|_2^2\).
4
This is the closest point on the hyperplane to the origin - a projection, computed purely from optimality.
Interactive: project onto the simplex
Common Mistakes to Avoid
- Reporting a local minimum as merely local for a convex problem - it is automatically global.
- Applying \(\nabla f=0\) when constraints are active; then the correct condition is the variational inequality (10.4), not stationarity.
- Forgetting feasibility: an optimum must satisfy the constraints, not just the gradient condition.
- Assuming a non-convex objective's stationary point is a minimum - it may be a saddle or maximum.
Quant Practitioner Tips
- Model deliberately for convexity: a convex reformulation buys you a global, certifiable solution.
- For box/simplex constraints, projections have closed forms - the backbone of projected-gradient methods.
- The condition \(\nabla f_0(x^\star)=A^\top\nu\) foreshadows Lagrange multipliers (10.3).
Knowledge Check
Q1 Easy
For a convex optimization problem, a local minimum is:
Q2 Medium
The first-order optimality condition over a convex feasible set \(C\) is:
Q3 Medium
For \(\min\tfrac12\|x\|_2^2\) s.t. \(a^\top x=1\), the optimum is:
Practical Exercise
Consider \(\min\ \tfrac12 x^\top Q x - c^\top x\) with \(Q\succ0\) and no constraints. (a) Write the optimality condition. (b) Solve for \(x^\star\). (c) Why is this the unique global minimizer?
▶ Show full solution
(a) Unconstrained convex + differentiable: \(\nabla f=Qx-c=0\).
(b) \(x^\star=Q^{-1}c\) (well-defined since \(Q\succ0\) is invertible).
(c) \(Q\succ0\) makes \(f\) strictly convex, so any minimizer is unique; and for convex problems the stationary point is the global minimum. Hence \(x^\star=Q^{-1}c\) is THE global optimum.
After the reveal, answer for yourself: How does this generalize the min-variance portfolio you'll solve in 10.5?
Lesson Summary
A convex program minimizes a convex objective over a convex feasible set (convex sublevel sets plus affine equalities). Its defining reward is that every local minimum is global, and optimality reduces to a first-order variational inequality \(\nabla f_0(x^\star)^\top(y-x^\star)\ge0\) - specializing to \(\nabla f_0=0\) unconstrained and to gradient-parallel-to-constraint-normal with equalities. Projections onto simple convex sets solve exactly this way.
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
▶ Show retrieval prompts & answers
Q: Why is a local minimum of a convex problem global?
A: Any feasible point strictly better than \(x^\star\) would, by convexity, make a nearby convex combination even better and feasible, contradicting local optimality.
A: Any feasible point strictly better than \(x^\star\) would, by convexity, make a nearby convex combination even better and feasible, contradicting local optimality.
Q: State the first-order optimality condition and its unconstrained special case.
A: \(\nabla f_0(x^\star)^\top(y-x^\star)\ge0\) for all feasible \(y\); unconstrained it becomes \(\nabla f_0(x^\star)=0\).
A: \(\nabla f_0(x^\star)^\top(y-x^\star)\ge0\) for all feasible \(y\); unconstrained it becomes \(\nabla f_0(x^\star)=0\).
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check
Confidence / mastery rating
Personal notes
Source References
This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.
- Additional Exercises for Convex Optimization (Boyd & Vandenberghe, 2016) current - Ch. 4 - Ch. 4 exercises: convex problems, optimality conditions, equivalent reformulations.
- Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lec. 11 - Least-squares and projection viewpoints underlying constrained quadratic minimization.