M.2.6 Advanced Extensions

Basic Prerequisites: 04 · Constrained Optimization (KKT, multipliers) and 05 · Gradient & Newton (iterative solvers).

---

1. Intuition & Practical Objective

This page collects the three ideas that turn the calculus of the previous pages into a toolbox a practitioner can trust, and shows each one doing finance work:

1. Convexity is the property that makes the difference between “the solver found an answer” and “the solver found the answer.” Convex objective and convex feasible set $\Rightarrow$ every stationary point is a global optimum, and KKT is sufficient. It is also a fragility: the moment you add a cardinality cap or a non-convex cost, the guarantee evaporates.
2. Duality turns a constrained problem into an unconstrained one and, in the convex case, gives a certificate of optimality (zero duality gap). Its by-product - the dual variables - are the shadow prices of page 04, recovered here as the slope of the value function (the envelope theorem) and as the engine of the efficient frontier.
3. Regularisation (ridge, lasso) is constrained optimisation in disguise: the Lagrangian of “minimise the loss subject to a budget on the coefficients” is “minimise loss $+$ penalty,” and the lasso’s solution - soft-thresholding - is read off the KKT conditions rather than computed.

The three examples below are deliberately the ones a quant meets in week one: a convex QP (portfolio), a duality/envelope check, and a lasso fit by coordinate descent.

---

2. Mathematical Ground Truth & Derivations

Convex sets and functions. A set $C\subseteq {\mathbb{R}}^n$ is convex if $x,y\in C\Rightarrow \theta x+(1-\theta )y\in C$ for all $\theta \in [0,1]$. A function $f$ is convex if its domain is convex and

$$f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y).$$

For $C^2$ functions on a convex domain there is a computable test: $f$ convex $⟺{\nabla }^{2}f(x)⪰0$ for all $x$. A convex optimisation problem is $\min f_0(x)$ s.t. $f_i(x)\le 0$ ($f_i$ convex), $h_j(x)=0$ ($h_j$ affine). The two facts that make convex problems tractable:

• Every local minimum is global. (If $x^{\ast }$ is locally optimal and $y$ is feasible with $f(y)<f(x^{\ast })$, convexity along the segment contradicts local optimality.)
• KKT is sufficient (and, with Slater’s condition, necessary): any KKT point is globally optimal with zero duality gap (Boyd §5.5.3).

Strong convexity (${\nabla }^{2}f⪰mI$, Boyd eq. 9.7) additionally makes the minimiser unique and gives the linear rate of page 05.

Lagrangian duality. For $\min f_0(x)$ s.t. $f_i(x)\le 0,h_j(x)=0$, the Lagrangian is $\mathcal{L}(x,\lambda ,\nu )=f_0(x)+{\sum }_i{\lambda }_i{f}_i(x)+{\sum }_j{\nu }_j{h}_j(x)$ with $\lambda \ge 0$, and the dual function is $g(\lambda ,\nu )={\inf }_x\mathcal{L}(x,\lambda ,\nu )$. The dual problem is ${\max }_{\lambda \ge 0,\nu }g$. Two facts:

• Weak duality always: $g(\lambda ,\nu )\le p^{\ast }$ for every feasible dual $(\lambda ,\nu )$ - the dual gives a lower bound on the primal optimum, i.e. a certificate.
• Strong duality for convex problems (Slater): $d^{\ast }=p^{\ast }$ - the bound is tight and the dual optimum can be found instead of the primal.

The envelope theorem / shadow prices. Differentiating $p^{\ast }(b)$ where $b$ is the constraint level: $\frac{d{p}^{\ast }}{db}={\nu }^{\ast }$ (Simon & Blume §19.2). In the Markowitz problem, differentiating ${\sigma }^2(r_0)$ along the efficient frontier: the derivative of the frontier is the dual variable of the return constraint. The frontier is convex (concave in return–variance space), and its slope is the price of risk implied by the constraints.

Regularisation as constrained optimisation. Elastic-net / lasso (ESL §3.4):

$$\hat{\beta }=\arg \underset{\beta }{\min }\frac{1}{2}\Vert y-X\beta {\Vert }_2^2+\lambda \Vert \beta {\Vert }_1\text{(lagrangian form of }\min \frac{1}{2}\Vert y-X\beta {\Vert }_2^2\text{s.t. }\Vert \beta {\Vert }_1\le t\text{)}.$$

For an orthonormal design ($X^{\top }X=I$) the solution is the soft-threshold operator, and it is read directly off the KKT conditions:

$${\hat{\beta }}_j=S(z_j,\lambda )=\mathrm{sign}(z_j)(|z_j|-\lambda {)}_{+},z=X^{\top }y,$$

because the first-order condition $0\in {\hat{\beta }}_j-z_j+\lambda \partial |{\hat{\beta }}_j|$ has the subdifferential $\partial |\beta |=\mathrm{sign}(\beta )$ for $\beta \ne 0$ and $[-1,1]$ at $\beta =0$. Ridge is the $L_2$ analogue: $\hat{\beta }=(X^{\top }X+\lambda I{)}^{-1}{X}^{\top }y$ (ESL eq. 3.44), the shrinkage factor $d_j^2/(d_j^2+\lambda )$ on the SVD direction (eq. 3.47) - a smooth, differentiable, convex problem, the clean case; the lasso is convex but non-smooth, which is exactly why its solution is sparse (it can sit exactly at $0$).

Where convexity is lost. Cardinality (“at most $k$ names”), fixed transaction costs, non-convex risk measures, and integer constraints all destroy convexity. The KKT conditions still hold at any local optimum, but a global certificate is gone.

---

3. Computational Implementation - convex vs non-convex, duality, and the lasso KKT

Stdlib only. (A) gradient descent from several starts on a convex and a non-convex objective, showing global uniqueness versus basin-dependence; (B) a duality/envelope check; (C) soft-thresholding solving the lasso KKT and coordinate descent recovering it.

Read the output. (A) The convex objective converges to the same point $0$ from every start - global uniqueness in action. The non-convex $x^4-3x^2+x$ has two basins: starts at $-2$ and $-1.5$ land at $-1.300840$, starts at $1$ and $2$ land at $+1.130901$. Same code, same objective, different answers depending on the start - the failure mode convexity is there to prevent. (B) The best dual value equals the primal optimum $1.0$ to six decimals (gap $0$), so strong duality holds; and the envelope theorem’s ${\lambda }^{\ast }=2$ is exactly the numeric $dV/dc$. (C) The soft-threshold estimate has a KKT residual of exactly zero - it is the optimum, read off the first-order condition - and coordinate descent reproduces it. Here both $|z_j|>>\lambda$, so both coefficients are merely shrunk ($0.7\to 0.4$ and $-0.4\to -0.1$); had a $|z_j|$ fallen below $\lambda =0.3$, soft-thresholding would have set that coefficient to exactly zero. That sparsity is a consequence of the non-smooth $L_1$ penalty (the KKT condition has a whole interval $[-1,1]$ of subgradients at $0$), not of any explicit selection rule.

---

4. Failure Modes & First-Principles Breakdowns

1. Convexity is a guarantee you can lose in one constraint. Experiment (A) is the whole point: “at most $k$ names,” fixed costs, or a non-convex risk measure make the objective multi-basin, and every gradient method becomes start-dependent. Report the basin, not just the answer.
2. Weak duality is not strong duality. For a non-convex problem the dual only gives a lower bound; the gap $p^{\ast }-d^{\ast }$ can be strictly positive, so a dual solution is not a primal optimum. Always confirm convexity (or Slater) before treating the dual as the answer.
3. KKT at a local optimum is not a global certificate. KKT holds at every local min of a smooth problem. It is the convexity that upgrades it to a global statement - the conditions alone do not.
4. Shadow prices change sign and meaning with the constraint’s direction. A "$\ge$" floor and a "$\le$" cap on the same quantity have opposite-signed multipliers; and a multiplier of zero means slack, not irrelevant. Misreading a dual from a solver is a classic and expensive bug.
5. $L_1$ regularisation is non-smooth. The gradient does not exist at ${\beta }_j=0$; plain gradient descent cannot handle it (use subgradient, proximal/soft-threshold, or coordinate descent). Conversely the ridge problem is smooth and convex - the reason it has a closed form and lasso does not.
6. Elastic-net/penalty scale is a data-unit decision. $\lambda$ penalises raw coefficients; if the predictors are not standardised, the effective penalty differs per feature and the “sparsity” is an artefact of units, not of signal (ESL §3.4). Standardise first.
7. Convex problems can still be numerically hard. Convexity says the optimum exists and is reachable; it says nothing about the conditioning. An ill-conditioned convex QP is still slow and unstable (page 05, failure mode 2).

---

5. References

• Boyd & Vandenberghe: Convex Optimization
• Simon & Blume: Mathematics for Economists
• Hastie, Tibshirani & Friedman: The Elements of Statistical Learning (2nd ed.)
• Rockafellar, R. T.: Convex Analysis (1970)
• Bertsekas, Dimitri P.: Nonlinear Programming (3rd ed.)

---

6. Connected Graph Bridges

• Back: 05 · Gradient & Newton · Index Hub
• Applied: Mean–Variance Optimization (the efficient frontier and its slope) · Machine Learning (ridge/lasso, gradient boosting) · Covariance Shrinkage & Denoising (when inputs are uncertain and the problem is ill-conditioned)
• Base: Linear Algebra & Matrices (positive-definite matrices, SVD, quadratic forms) · 04 · Constrained Optimization (KKT, shadow prices)