Convex Optimization

The single most consequential fact in optimization is the divide between convex and non-convex problems. It is not a divide of difficulty in the usual sense, it is the divide between problems you can provably solve to global optimality, efficiently and reliably, and problems where you are forever unsure whether a better solution is hiding somewhere you didn't look. Nearly every well-posed quant problem, mean–variance portfolios, ridge and Lasso regression, SVMs, model calibration, is deliberately formulated to be convex, because convexity is what makes the answer trustworthy. Understanding why is the difference between using a solver and knowing what it guarantees.

Convex sets and convex functions

A set $C \subseteq \mathbb{R}^n$ is convex if the line segment between any two of its points stays inside: for $x, y \in C$ and $\theta \in [0,1]$, $\theta x + (1-\theta)y \in C$. Half-spaces, balls, the Positive Semidefinite Matrices cone, and any intersection of these are convex; the feasible region of linear constraints (a polyhedron) is convex.

A function $f: \mathbb{R}^n \to \mathbb{R}$ is convex if its graph lies below its chords: $f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta) f(y), \qquad \theta \in [0,1].$ Equivalently (for smooth $f$), the first-order condition $f(y) \ge f(x) + \nabla f(x)^\top(y - x)$, the function sits above every tangent plane, or the second-order condition that the Hessian is positive semidefinite everywhere, $\nabla^2 f(x) \succeq 0$. That last test is the operational one and the direct payoff of PSD theory: a quadratic $f(x) = \tfrac12 x^\top A x + b^\top x$ is convex iff $A \succeq 0$. This is why portfolio variance $w^\top\Sigma w$, with $\Sigma$ necessarily PSD, is automatically a convex objective.

Why convexity matters: local = global

The reason to care is a single theorem with enormous consequences. For a convex objective over a convex feasible set, every local minimum is a global minimum. Proof sketch: if $x^\star$ were a local but not global minimum, some feasible $y$ has $f(y) < f(x^\star)$; convexity along the segment gives $f(\theta y + (1-\theta)x^\star) \le \theta f(y) + (1-\theta)f(x^\star) < f(x^\star)$ for $\theta$ small, contradicting local optimality. So there are no "traps", no spurious local minima, no dependence on the starting point, no wondering if more search would help. Gradient descent, interior-point methods, and their kin converge to the answer. Contrast non-convex optimization (training deep nets, combinatorial problems), where local minima proliferate and global optimality is generally intractable. Convexity is, bluntly, the boundary of what you can solve with confidence, which is why quants invest heavily in reformulating problems to expose hidden convexity.

The first-order optimality condition makes this concrete: for an unconstrained differentiable convex $f$, $x^\star$ is optimal iff $\nabla f(x^\star) = 0$. Over a convex feasible set $C$, the condition generalizes to $\nabla f(x^\star)^\top(y - x^\star) \ge 0$ for all $y \in C$, the objective cannot decrease in any feasible direction.

The canonical form and duality

A convex optimization problem is $\min_{x}\ f_0(x) \quad \text{s.t.}\quad f_i(x) \le 0\ (i=1,\dots,m), \quad Ax = b,$ with all $f_i$ convex and the equality constraints affine. The Lagrangian absorbs the constraints with multipliers ("prices") $\lambda \ge 0$ and $\nu$: $\mathcal{L}(x, \lambda, \nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \nu^\top(Ax - b).$ Minimizing over $x$ gives the dual function $g(\lambda,\nu) = \inf_x \mathcal{L}$, and the dual problem is to maximize $g$ over $\lambda \ge 0$. Two results give duality its power:

• Weak duality (always). The best dual value lower-bounds the primal optimum: $g(\lambda,\nu) \le f_0(x^\star)$ for any feasible dual point. The gap $p^\star - d^\star \ge 0$ is the duality gap. This holds even for non-convex problems, so the dual always certifies a bound.
• Strong duality (under convexity + Slater's condition). For a convex problem with a strictly feasible point, the gap closes: $p^\star = d^\star$. Solving the dual solves the primal, and the optimal multipliers are exactly the Lagrange Multipliers & KKT Conditions that characterize the solution.

The economic content of duality is what makes it indispensable: the multiplier $\lambda_i^\star$ is the shadow price of constraint $i$, the marginal improvement in the objective per unit relaxation of that constraint. In a portfolio problem, the multiplier on a risk budget is the marginal return you forgo per unit of risk limit, i.e. the implied price of risk. Duality also underlies robust optimization (worst-case-over-a-set reformulated as a tractable dual) and regularization (ridge/Lasso as the dual of norm-constrained fits, see Ridge and LASSO Regularization).

Worked example, minimum-variance portfolio

The cleanest convex problem in finance: find fully-invested weights minimizing variance, $\min_{w}\ \tfrac12\, w^\top \Sigma\, w \quad \text{s.t.}\quad \mathbf{1}^\top w = 1.$ The objective is convex because $\Sigma \succeq 0$; the constraint is affine, a textbook convex program, so any stationary point is the global optimum. Forming the Lagrangian $\mathcal{L} = \tfrac12 w^\top\Sigma w - \lambda(\mathbf{1}^\top w - 1)$ and setting $\nabla_w\mathcal{L} = \Sigma w - \lambda\mathbf{1} = 0$ gives $w = \lambda\Sigma^{-1}\mathbf{1}$, and normalizing to sum to 1, $w^\star = \frac{\Sigma^{-1}\mathbf{1}}{\mathbf{1}^\top \Sigma^{-1}\mathbf{1}}.$ Because the problem is convex, this closed form is the global minimum-variance portfolio, no local-optimum caveats, no starting-point sensitivity. Add a return target $\mu^\top w = r$ and you get the full MPT (Harry Markowitz) efficient frontier, still convex, still globally solvable. The whole tractability of mean–variance investing rests on $\Sigma$ being PSD.

Failure modes and subtleties

• Non-convex reformulations sneak in. Cardinality constraints ("hold at most $k$ names"), integer lots, and minimum-position thresholds make portfolio problems non-convex (combinatorial); the convex machinery no longer guarantees global optimality, and you need branch-and-bound or convex relaxations.
• Convexity is not robustness. A convex problem is solved exactly, but if $\Sigma$ and $\mu$ are estimated with error, the exact solution to the wrong problem is confidently wrong, the notorious error-maximizing behavior of Markowitz. Convex solvability and statistical stability are different concerns; the fix is shrinkage, constraints, or robust (still-convex) reformulations.
• Strong duality needs a constraint qualification. Slater's condition (a strictly feasible point) is what closes the gap; degenerate or infeasible problems can have a positive duality gap even when convex.
• Ill-conditioning slows solvers. A near-singular $\Sigma$ (tiny eigenvalues) makes the problem numerically flat in some directions; the optimum is technically unique but practically unstable, regularize.
• "Convex" depends on formulation. Maximizing the Sharpe ratio is not convex as written but becomes a convex (or quasi-convex) problem after a clever change of variables; recognizing when a disguised problem is secretly convex is the real skill.

In interviews

The headline you must own: for convex problems, local optima are global, and know why (the chord/segment argument). Be able to state the Hessian-PSD test for convexity and connect it to why $w^\top\Sigma w$ is convex (Positive Semidefinite Matrices). The minimum-variance derivation via a Lagrangian is a standard whiteboard problem, produce $w^\star = \Sigma^{-1}\mathbf{1}/(\mathbf{1}^\top\Sigma^{-1}\mathbf{1})$ and note the convex problem guarantees it's global. Expect duality questions: weak duality always holds, strong duality needs convexity plus Slater, and the multiplier is a shadow price. A sharp interviewer probes the limits: "is Markowitz convex?" (yes) "then why does it produce crazy weights?" (estimation error, not optimization failure). This flows straight into Lagrange Multipliers & KKT Conditions, which supplies the exact optimality conditions for the constrained case.