M.2.4 Constrained Optimization

Basic Prerequisites: 03 · Multivariable Calculus (gradients, Hessians, quadratic forms).

---

1. Intuition & Practical Objective

Unconstrained optimisation (“set the gradient to zero”) is almost never the problem a practitioner faces. Portfolios must be fully invested ($1^{\top }w=1$), meet a return floor (${\mu }^{\top }w\ge r_0$), respect position caps, hit a target duration, match a benchmark beta. Every one of those is an equality or inequality constraint, and constraints change the first-order condition from "$\nabla f=0$" to a bordered condition.

This page builds the machinery for optima under constraints:

• Lagrange multipliers for equality constraints - the geometric picture is “at the optimum the objective’s level set is tangent to the constraint surface,” so their gradients are parallel: $\nabla f=\lambda \nabla g$.
• The multiplier is a shadow price - ${\lambda }^{\ast }$ is the marginal improvement in the objective per unit of constraint relaxation. This is the single most useful output of a constrained optimisation after the answer itself.
• KKT conditions for inequality constraints - the generalisation that adds complementary slackness: a constraint either binds (and has a positive multiplier) or is slack (and has a zero multiplier), never both.

The canonical finance instance, used as the worked example below, is Markowitz mean–variance: minimise $w^{\top }\Sigma w$ subject to ${\mu }^{\top }w=r_0$ and $1^{\top }w=1$. Its KKT system is a linear system, which makes it the cleanest possible illustration of everything on this page.

---

2. Mathematical Ground Truth & Derivations

Equality-constrained optimisation (Lagrange). Consider $\min f(x)$ subject to $h_j(x)=0$, $j=1,\dots ,p$. Form the Lagrangian

$$\mathcal{L}(x,\nu )=f(x)+\sum _{j=1}^p{\nu }_j{h}_j(x).$$

At a regular optimum $x^{\ast }$ (constraint gradients $\{\nabla h_j\}$ linearly independent - the constraint qualification) there exist multipliers ${\nu }^{\ast }$ such that

$${\nabla }_x\mathcal{L}(x^{\ast },{\nu }^{\ast })=\nabla f(x^{\ast })+\sum _j{\nu }_j^{\ast }\nabla h_j(x^{\ast })=0,h_j(x^{\ast })=0\forall j.$$

Geometrically: at the optimum $\nabla f$ lies in the span of the constraint gradients - the objective can improve no further while staying on the constraint surface.

KKT conditions (inequalities + equalities). For $\min f_0(x)$ subject to $f_i(x)\le 0$ and $h_j(x)=0$ (Boyd eq. 5.49; Simon & Blume §18.6), form

$$\mathcal{L}(x,\lambda ,\nu )=f_0(x)+\sum _i{\lambda }_i{f}_i(x)+\sum _j{\nu }_j{h}_j(x).$$

At an optimum, with the constraint qualification holding, there are ${\lambda }^{\ast },{\nu }^{\ast }$ with the four KKT blocks:

$$\underset{\text{primal feasibility}}{\underbrace{f_i(x^{\ast })\le 0,h_j(x^{\ast })=0}},\underset{\text{dual feasibility}}{\underbrace{{\lambda }_i^{\ast }\ge 0}},\underset{\text{complementary slackness}}{\underbrace{{\lambda }_i^{\ast }{f}_i(x^{\ast })=0}},\underset{\text{stationarity}}{\underbrace{\nabla f_0(x^{\ast })+\sum _i{\lambda }_i^{\ast }\nabla f_i(x^{\ast })+\sum _j{\nu }_j^{\ast }\nabla h_j(x^{\ast })=0}}.$$

Dropping the inequalities leaves the Lagrange conditions exactly. Under convexity of $f_0,f_i$ and affinity of $h_j$ (with Slater’s condition), KKT is necessary and sufficient: any point satisfying KKT is globally optimal with zero duality gap (Boyd §5.5.3).

The multiplier is a shadow price (envelope theorem). Replace $h(x)=0$ by $h(x)=b$ and let $V(b)$ be the optimal value. Then at the optimum

$$\frac{dV}{db}={\nu }^{\ast }.$$

Relaxing (or tightening) the constraint by one unit changes the objective by the multiplier. This is the envelope theorem (Simon & Blume §19.2), and it is why dual variables are read off a solver as “prices”: the portfolio’s return-constraint multiplier is the marginal cost in variance of demanding one more unit of expected return.

Complementary slackness as a decision rule. ${\lambda }_i^{\ast }{f}_i(x^{\ast })=0$ says: a constraint is either slack (then ${\lambda }_i^{\ast }=0$ - it costs nothing to relax) or binding (then ${\lambda }_i^{\ast }\ge 0$ may be positive - it is doing work). With inequality caps on positions, this is precisely the statement “an asset is either at its cap (${\lambda }_i>0$) or interior (${\lambda }_i=0$).”

Second-order conditions. Equality- and inequality-constrained problems need a bordered Hessian test (Simon & Blume §16.3, §19.3): for $\min$, the Hessian of the Lagrangian restricted to the constraint tangent space must be positive definite; the bordered Hessian

$$\left(\begin{array}{cc}0& \nabla h^{\top }\\ \nabla h& {\nabla }_{xx}^2\mathcal{L}\end{array}\right)$$

must have a specific alternating-sign pattern. The plain definiteness of ${\nabla }^{2}f$ is not the right test under constraints.

Worked example - the Markowitz KKT system. $\min \frac{1}{2}{w}^{\top }\Sigma w$ s.t. ${\mu }^{\top }w=r_0,1^{\top }w=1$. The Lagrangian is $\mathcal{L}=\frac{1}{2}{w}^{\top }\Sigma w-{\lambda }_1({\mu }^{\top }w-r_0)-{\lambda }_2(1^{\top }w-1)$, and KKT stationarity ${\nabla }_w\mathcal{L}=0$ gives $\Sigma w={\lambda }_1\mu +{\lambda }_{2}1$, which together with the two equality constraints is the linear system

$$\left(\begin{array}{ccc}\Sigma & -\mu & -1\\ {\mu }^{\top }& 0& 0\\ 1^{\top }& 0& 0\end{array}\right)\left(\begin{array}{c}w\\ {\lambda }_1\\ {\lambda }_2\end{array}\right)=\left(\begin{array}{c}0\\ r_0\\ 1\end{array}\right).$$

This is Boyd’s Example 5.1 (equality-constrained convex QP) with the sign convention of the Lagrangian; it can be solved by Gaussian elimination from scratch.

---

3. Computational Implementation - Lagrange and the Markowitz KKT system

Stdlib only. Part (a) verifies the elementary Lagrange result $\max xy$ s.t. $x+y=10$; part (b) assembles and solves the Markowitz KKT system with a hand-written Gaussian elimination, then verifies stationarity, the constraints, and the shadow price via the envelope theorem.

Read the output. The Lagrange result is exact and the brute-force check ($x=3,\dots ,7$) confirms $25$ is the maximum. In (b): the weights sum to $1$ and deliver ${\mu }^{\top }w=0.16$ to ten decimals; the KKT stationarity residual is $1.9\times 10^{-17}$ (machine zero), so $\Sigma w={\lambda }_1\mu +{\lambda }_{2}1$ holds exactly. The multiplier ${\lambda }_1=0.288000$ is the shadow price of the return constraint, and the envelope check confirms it: bumping $r_0$ upward raises $\frac{1}{2}{w}^{\top }\Sigma w$ at exactly rate $0.288$ per unit of return. That is the number a portfolio manager reads as “the marginal variance cost of demanding more return.”

---

4. Failure Modes & First-Principles Breakdowns

1. The multiplier can fail to exist if the constraint qualification fails. If the active constraint gradients are linearly dependent at $x^{\ast }$ (Simon & Blume §19.5), the Lagrange/KKT system may have no solution even though an optimum exists. A common occurrence: two constraints that are “the same” (redundant caps), or a constraint with zero gradient at the point (an active bound of the form $x\le c$ hit at a degenerate point).
2. Sign conventions destroyed the shadow-price reading. Whether the Lagrangian is $f+\lambda h$ or $f-\lambda h$ flips the sign of $\lambda$. Get it wrong and the “shadow price” points the wrong way. (Here ${\lambda }_2=-0.006$: the budget constraint’s multiplier is small and negative under this convention.)
3. KKT is necessary only under convexity - otherwise it finds local optima. Add a cardinality cap or a non-convex cost and KKT still holds at a local optimum, but a different, better feasible point may exist elsewhere (page 06).
4. Complementary slackness is easy to misread. A zero multiplier does not mean the constraint is irrelevant; it means it is slack at the optimum. Numerical solvers return tiny nonzero duals for active constraints with approximate tolerance - never threshold duals naively.
5. The second-order condition is the bordered Hessian, not the Hessian. A point can satisfy KKT and have ${\nabla }^{2}f\succ 0$ yet be a constrained maximum, or be a constrained minimum while ${\nabla }^{2}f$ is indefinite. Testing the wrong matrix gives the wrong answer (Simon & Blume §19.3).
6. Ill-conditioned constraint systems amplify error. The KKT matrix in (b) is a saddle-point (indefinite) system - it is symmetric-indefinite, so a naive Cholesky fails and the multipliers can lose digits if the constraint rows are nearly collinear. The stationarity residual is the honest health check.

---

5. References

• Simon & Blume: Mathematics for Economists
• Boyd & Vandenberghe: Convex Optimization
• Nocedal, J. & Wright, S. J.: Numerical Optimization (2nd ed.)
• Bertsekas, Dimitri P.: Nonlinear Programming (3rd ed.)

---

6. Connected Graph Bridges

• Back: 03 · Multivariable Calculus · Index Hub
• Next: 05 · Gradient & Newton (solving the stationarity system iteratively) → 06 · Convexity & Applications
• Applied: Mean–Variance Optimization (the QP solved here) · Pricing Formulas (hedging as a constrained problem)
• Base: Linear Algebra & Matrices (linear systems, saddle-point structure)