Lagrangian and Constrained Optimization

Definition

The Lagrangian method converts a constrained optimization problem into an unconstrained one by incorporating constraints into the objective via Lagrange multipliers. The KKT conditions characterise optima of constrained problems.

Intuition

A constraint restricts the feasible region. The Lagrange multiplier $\lambda$ measures the sensitivity of the optimal value to relaxing that constraint — if $\lambda$ is large, tightening the constraint costs a lot; if $\lambda =0$, the constraint is inactive at the optimum. The method works because at a constrained optimum, the gradient of the objective is parallel to the gradient of the active constraint.

Formal Description

Equality Constraints (Classical Lagrange Multipliers)

Problem: $\min f(\mathbf{x})$ subject to $h_j(\mathbf{x})=0$, $j=1,\dots ,p$.

Lagrangian:

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

Necessary condition (Lagrange condition): at a local minimum ${\mathbf{x}}^{\ast }$:

$${\nabla }_{\mathbf{x}}\mathcal{L}=\nabla f({\mathbf{x}}^{\ast })+\sum _j{\nu }_j^{\ast }\nabla h_j({\mathbf{x}}^{\ast })=0$$

Geometrically: $\nabla f$ lies in the span of $\{\nabla h_j\}$.

Inequality Constraints (KKT Conditions)

Problem: $\min f(\mathbf{x})$ s.t. $g_i(\mathbf{x})\le 0$, $i=1,\dots ,m$; $h_j(\mathbf{x})=0$, $j=1,\dots ,p$.

Lagrangian:

$$\mathcal{L}(\mathbf{x},\mathbf{\lambda },\mathbf{\nu })=f(\mathbf{x})+\sum _{i=1}^m{\lambda }_i{g}_i(\mathbf{x})+\sum _{j=1}^p{\nu }_j{h}_j(\mathbf{x})$$

KKT conditions (necessary for local optimum under constraint qualification; sufficient for convex problems):

Condition	Equation
Stationarity	${\nabla }_{\mathbf{x}}\mathcal{L}=0$
Primal feasibility	$g_i({\mathbf{x}}^{\ast })\le 0$, $h_j({\mathbf{x}}^{\ast })=0$
Dual feasibility	${\lambda }_i^{\ast }\ge 0$
Complementary slackness	${\lambda }_i^{\ast }{g}_i({\mathbf{x}}^{\ast })=0$ for all $i$

Complementary slackness means: either the constraint is active ($g_i=0$) or the multiplier is zero (${\lambda }_i=0$). This classifies constraints as active (binding) or inactive.

Dual Problem

The Lagrange dual function: $g(\mathbf{\lambda },\mathbf{\nu })={\inf }_{\mathbf{x}}\mathcal{L}(\mathbf{x},\mathbf{\lambda },\mathbf{\nu })$

Dual problem: ${\max }_{\mathbf{\lambda }\ge 0,\mathbf{\nu }}g(\mathbf{\lambda },\mathbf{\nu })$

• Weak duality: $d^{\ast }\le p^{\ast }$ always holds.
• Strong duality: $d^{\ast }=p^{\ast }$ holds for convex problems satisfying Slater’s condition (feasible interior point exists).

The dual is always concave (max of a concave function) and often easier to solve.

Sensitivity Interpretation

At the optimum, ${\nu }_j^{\ast }=-\partial p^{\ast }/\partial b_j$ where $b_j$ is the RHS of equality constraint $h_j(\mathbf{x})=b_j$. Lagrange multipliers are shadow prices — the marginal value of relaxing a constraint.

Applications

Support Vector Machine (SVM): primal problem is a QP; dual formulation:

$$\underset{\mathbf{\alpha }}{\max }\sum _i{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^{\top }{\mathbf{x}}_j\text{s.t.}\sum _i{\alpha }_i{y}_i=0,0\le {\alpha }_i\le C$$

The kernel trick enters naturally in the dual, replacing ${\mathbf{x}}_i^{\top }{\mathbf{x}}_j$ with $k({\mathbf{x}}_i,{\mathbf{x}}_j)$.

Lasso/Constrained regression: $\min \Vert y-X\beta {\Vert }^2$ s.t. $\Vert \beta {\Vert }_1\le t$ — Lagrangian gives the penalised form.

Portfolio optimisation: maximise expected return subject to variance constraint.

Trade-offs

• KKT conditions identify candidates for optima but do not guarantee finding a global optimum for non-convex problems.
• The dual can be much lower-dimensional than the primal (e.g., SVM dual has $n$ variables, primal has $d+1$).

Links

• Convex Optimization
• Gradient Descent and Variants
• Partial Derivatives
• Kernel Methods (SVM)