Convex Optimization

Finding a point that is better than its neighbors does not usually prove that it is the best point overall. Convex optimization studies problems where local optimality does imply global optimality. Begin with:

1. convex sets and functions;
2. standard problem forms and transformations;
3. optimality conditions;
4. Lagrange duality and constrained optimality;
5. first- and second-order methods;
6. applications in statistics and machine learning.

Stanford EE364A and Boyd and Vandenberghe's Convex Optimization provide the full course and proofs.

Minimum working vocabulary

This map introduces the assumptions behind global guarantees; the full treatment of duality and algorithms remains in Boyd and Vandenberghe, Chapters 2–5 and 9.

Open full-size image

Check the whole segment, not just its endpoints. On the left, both endpoints belong to the set but part of the segment leaves it, which disproves convexity. In each of the other two sets, every segment joining two points stays inside. One successful segment alone would not prove that property.

Zhang et al., Dive into Deep Learning, Figure 12.2.1. · CC BY-SA 4.0

A set $C$ is convex if the segment $(1-t)x+ty$ stays in $C$ for every $x,y\in C$ and $0\le t\le1$. A function is convex on a convex domain if

$$f((1-t)x+ty)\le(1-t)f(x)+tf(y).$$

The graph lies below its chords. Strict convexity makes this inequality strict for distinct points and $0<t<1$; it implies at most one minimizer, not existence. For example, $e^x$ is strictly convex on $\mathbb R$ but has no minimizer, only infimum zero.

For a differentiable convex function, the supporting-plane inequality is

$$f(y)\ge f(x)+\nabla f(x)^T(y-x).$$

Thus an unconstrained stationary point is globally minimizing. More generally, for a feasible $x_*\in C$ in a convex set $C$, the first-order condition $\nabla f(x_*)^T(y-x_*)\ge0$ for every $y\in C$ is necessary and sufficient. For $f(x)=x$ on $[0,1]$, $x_*=0$ satisfies it despite $f'(0)=1$. Every local minimum of a convex problem is global: if a better feasible point existed, points arbitrarily close along its segment would improve the objective, contradicting local minimality.

A standard convex problem minimizes a convex objective subject to convex inequalities $g_i(x)\le0$ and affine equalities $Ax=b$. A convex objective on a nonconvex feasible set does not suffice. For example, minimizing $x^2$ on $\{-1,2\}$ makes $2$ a local but nonglobal minimum because it is isolated.

Returns, Diversification, and Portfolio Risk applies this form to a long-only mean–variance problem and calculates how expected returns change optimal weights.

For twice continuously differentiable functions on an open convex domain, convexity is equivalent to a positive-semidefinite Hessian. The gradient and curvature guide defines the Hessian and positive definiteness through second derivatives and quadratic forms. For least squares, $H=2X^TX/n\succeq0$; full column rank gives positive definiteness and a unique solution. Convexity alone does not make arbitrary gradient steps converge: smoothness and step size still matter.

Where duality fits

The Lagrangian is $\mathcal L(x,\lambda,\nu)=f(x)+\sum_i\lambda_i g_i(x)+\nu^T(Ax-b)$, with $\lambda_i\ge0$. Taking $\inf_x\mathcal L$ gives a lower bound on the primal minimum; maximizing that bound is the dual problem. A primal feasible value and dual bound give an optimality gap, unlike a small iterate change.

The Karush–Kuhn–Tucker conditions combine primal feasibility, dual feasibility, stationarity of the Lagrangian, and complementary slackness $\lambda_i g_i(x)=0$. For differentiable convex problems they are sufficient for global optimality when satisfied. Necessity and a zero duality gap require suitable regularity, such as Slater’s condition (a relative-interior feasible point satisfying the inequalities strictly). They are not unconditional guarantees for arbitrary constrained or neural-network problems.

My reading · Opened notes are remembered in this browser.