Constrained Optimization and KKT Conditions

Most real optimization problems are constrained: probabilities lie on a simplex, weights satisfy budgets, flows conserve mass, embeddings have unit norm. This chapter develops Lagrangians, KKT conditions, dual problems, and the geometry of active constraints—the toolkit behind SVM duals, resource allocation, and projected training.

1. Problem form

\[ \begin{aligned} \min_{x\in\mathbb{R}^n} &\quad f(x) \\ \text{s.t.} &\quad g_i(x) \le 0, \quad i=1,\ldots,m, \\ &\quad h_j(x) = 0, \quad j=1,\ldots,p. \end{aligned} \]

Assume \(f,g_i,h_j\) continuously differentiable unless stated. Feasible set:

\[ \mathcal{F} = \{x: g_i(x)\le 0\ \forall i,\ h_j(x)=0\ \forall j\}. \]

Active set at \(x\): \(\mathcal{A}(x)=\{i: g_i(x)=0\}\). Equality constraints are always “active.”

Worked example 1 — projection onto a ball

\(\min_x \|x-y\|_2^2\) s.t. \(\|x\|_2\le 1\). If \(\|y\|_2\le 1\), solution is \(y\). Else \(x^\star=y/\|y\|_2\). Constraint active on the boundary case.

2. Equality constraints and Lagrange multipliers

Unconstrained case recap

For smooth unconstrained \(f\), \(\nabla f(x^\star)=0\) is necessary for a local min (and sufficient under convexity).

One equality

\(\min f(x)\) s.t. \(h(x)=0\).

Lagrangian:

\[ \mathcal{L}(x,\nu) = f(x) + \nu\, h(x). \]

Necessary condition (regular points): there exists \(\nu^\star\) such that

\[ \nabla_x \mathcal{L}(x^\star,\nu^\star)=\nabla f(x^\star)+\nu^\star\nabla h(x^\star)=0, \quad h(x^\star)=0. \]

Geometry: \(\nabla f\) is normal to the constraint surface; level sets of \(f\) are tangent to \(\{h=0\}\).

Worked example 2 — classic textbook problem

Minimize \(f(x,y)=x^2+y^2\) subject to \(h(x,y)=x+y-1=0\).

\(\mathcal{L}=x^2+y^2+\nu(x+y-1)\).

Stationarity: \(2x+\nu=0\), \(2y+\nu=0\), and \(x+y=1\).

Thus \(x=y\) and \(2x=1\Rightarrow x=y=\frac12\), \(\nu=-1\). Minimum value \(\frac12\).

Check: on the line, \(f(x,1-x)=x^2+(1-x)^2=2x^2-2x+1\), vertex at \(x=\frac12\).

Worked example 3 — entropy maximization

\(\max -\sum_i p_i\log p_i\) s.t. \(\sum_i p_i=1\), \(p_i\ge 0\) (ignore inequalities first via substitution). Lagrange for equality yields the uniform distribution on a finite alphabet—maximum entropy.

3. Inequality constraints and KKT

For inequalities \(g_i(x)\le 0\), multipliers \(\lambda_i\) enter with sign conventions matching the inequality direction.

Lagrangian:

\[ \mathcal{L}(x,\lambda,\nu) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^p \nu_j h_j(x). \]

Karush–Kuhn–Tucker (KKT) conditions (necessary at a local min under a constraint qualification, e.g. LICQ: active constraint gradients linearly independent):

1. Stationarity: \(\nabla_x \mathcal{L}(x^\star,\lambda^\star,\nu^\star)=0\)
2. Primal feasibility: \(g_i(x^\star)\le 0\), \(h_j(x^\star)=0\)
3. Dual feasibility: \(\lambda_i^\star \ge 0\) for all \(i\)
4. Complementary slackness: \(\lambda_i^\star g_i(x^\star)=0\) for all \(i\)

Complementary slackness: either the constraint is active (\(g_i=0\)) or its multiplier is zero (inactive constraints do not affect stationarity).

Geometric reading

At the optimum, \(-\nabla f(x^\star)\) lies in the cone generated by active inequality gradients and the span of equality gradients (outward/inward depending on sign conventions). You cannot decrease \(f\) without leaving the feasible region.

Worked example 4 — inequality active vs inactive

\(\min (x-3)^2\) s.t. \(x\le 1\). Unconstrained min at \(x=3\) is infeasible. Optimum \(x^\star=1\), \(g=x-1\), \(\lambda>0\), stationarity \(2(x-3)+\lambda=0\Rightarrow \lambda=4\) at \(x=1\).

If constraint were \(x\le 10\), unconstrained \(x=3\) is feasible, \(\lambda=0\), constraint inactive.

4. Constraint qualifications (why they matter)

Without regularity, KKT may fail to hold at a true optimum.

Example pathology. Minimize \(x\) s.t. \(x^3\le 0\)… actually a standard example is \(f(x,y)=x\) with \(g_1=-y\le 0?\) Classic: minimize \(x\) subject to \(x^2+y^2\le 0\) forces \((0,0)\) but gradients can be degenerate depending on formulation.

LICQ: \(\{\nabla g_i(x^\star):i\in\mathcal{A}(x^\star)\}\cup\{\nabla h_j(x^\star)\}\) linearly independent.

Slater’s condition (for convex problems): exists \(x\) with \(g_i(x)<0\) all \(i\) and \(h_j(x)=0\). Ensures strong duality.

5. Duality

Lagrange dual function:

\[ q(\lambda,\nu) = \inf_x \mathcal{L}(x,\lambda,\nu). \]

\(q\) may be \(-\infty\) for some multipliers. For \(\lambda\ge 0\), weak duality says \(q(\lambda,\nu)\le f(x)\) for every feasible \(x\).

Dual problem:

\[ \max_{\lambda\ge 0,\ \nu} q(\lambda,\nu). \]

Weak duality: dual optimal \(\le\) primal optimal always.

Strong duality: equality of optimal values. Holds for convex problems under Slater-type conditions.

Duality gap: \(f(x^\star)-q(\lambda^\star,\nu^\star)\). Zero under strong duality.

Worked example 5 — SVM dual intuition

Hard-margin SVM primal is a QP with inequalities \(y_i(w^\top x_i+b)\ge 1\). Dual involves multipliers \(\alpha_i\ge 0\) with \(\sum_i \alpha_i y_i=0\) and objective depending on Gram matrix \(y_i y_j x_i^\top x_j\). Support vectors are points with \(\alpha_i>0\) (active margins)—complementary slackness in action.

Worked example 6 — equality-constrained QP

\(\min \frac12 x^\top Px + c^\top x\) s.t. \(Ax=b\) with \(P\succ 0\). KKT system is a linear saddle-point system:

\[ \begin{bmatrix} P & A^\top \\ A & 0 \end{bmatrix} \begin{bmatrix} x \\ \nu \end{bmatrix} = \begin{bmatrix} -c \\ b \end{bmatrix}. \]

Solved by factorization / Schur complements in numerical optimization and graphics (constrained least squares).

6. Methods that enforce constraints

Method	Idea	Notes
Elimination	Solve equalities, reduce variables	Best when \(h\) linear simple
Projection	GD step then project onto \(\mathcal{F}\)	Needs cheap projection
Barrier / interior-point	Add \(-\mu\sum\log(-g_i)\)	Central path; LP/QP/SOCP/SDP
Penalty	Add \(\rho\sum \max(g_i,0)^2\)	Simple; need \(\rho\to\infty\) carefully
Augmented Lagrangian	Penalty + multiplier updates	Robust practical method
Active-set	Guess active inequalities, solve EQ	Classic QP solvers

Worked example 7 — projection onto simplex

Euclidean projection onto \(\{x:x\ge 0,\mathbf{1}^\top x=1\}\) can be done by sorting / thresholding (standard algorithm). Used in probability simplex constrained models and some attention normalizations (conceptually).

Worked example 8 — projected gradient on a box

\(\mathcal{F}=[L,U]^n\). Projection is coordinatewise clipping. Extremely common in bound-constrained least squares.

7. Convex constrained problems

If \(f\) convex, \(g_i\) convex, \(h_j\) affine, the problem is a convex optimization problem. Then:

• Any local min is global
• KKT conditions are also sufficient for optimality (under standard setup)
• Strong duality often holds (Slater)

This is the theoretical home of logistic regression with linear constraints, ridge with linear equalities, SDP relaxations, etc.

Worked example 9 — water-filling sketch

Maximize \(\sum_i \log(1+p_i/\sigma_i^2)\) s.t. \(\sum_i p_i = P\), \(p_i\ge 0\) (power allocation). KKT yields \(p_i=\max(0,\ \mu-\sigma_i^2)\)—allocate power to better channels first.

8. CS/ML applications

• SVM / kernel machines: constrained QP + dual kernels
• Optimal transport (basic): coupling constraints; dual potentials
• Portfolio / risk: budget and inequality risk constraints
• Fairness constraints: demographic parity as linear constraints on predictors
• MPC / control: constrained quadratic programs in real time
• Phase retrieval / nonconvex QCQP: hard; relaxations or projected methods

9. Pitfalls

1. Wrong inequality direction flips multiplier signs and dual feasibility.
2. Forgetting complementary slackness when interpreting support vectors / active resources.
3. Applying unconstrained Newton inside a constrained region without projection/barriers.
4. Nonconvex constraints (\(\|x\|_2=1\) equality is nonconvex as a set? The sphere is nonconvex; the constraint function \(h=x^\top x-1\) is nonconvex as equality manifold optimization needs care). Unit-norm sphere requires Riemannian or penalty methods.
5. Strong duality assumed outside convexity—gap may be nonzero.
6. Numerical KKT residuals: check stationarity, feasibility, and complementarity separately when debugging solvers.

10. Checkpoint

• Form Lagrangians for equality and inequality problems
• State all four KKT blocks and interpret complementary slackness
• Solve simple 2-variable equality problems by hand
• Explain weak vs strong duality in one paragraph
• Name three algorithmic strategies for enforcing constraints

Exercises

Easy

1. Minimize \(x^2+y^2\) s.t. \(x+2y=1\). Find \((x,y,\nu)\).
2. Minimize \((x-2)^2\) s.t. \(x\ge 0\). Write KKT and solve.
3. Explain why \(\lambda_i\ge 0\) is required for inequalities \(g_i\le 0\) in standard form.
4. For \(\min \|x\|_2^2\) s.t. \(a^\top x=1\), find closed form \(x^\star\) via Lagrange.
5. Give an example where the unconstrained minimizer is feasible, so all inequality multipliers are zero.

Medium

6. Derive the KKT system for \(\min \frac12\|x-y\|_2^2\) s.t. \(x\ge 0\) (nonnegative projection). Show \(x^\star=\max(y,0)\) coordinatewise.
7. Prove weak duality: for \(\lambda\ge 0\) and feasible \(x\), \(q(\lambda,\nu)\le f(x)\).
8. Soft-margin SVM primal: identify which constraints become active for support vectors vs margin violators (qualitative is OK with definitions).
9. Convert \(\max f\) with \(g_i\ge 0\) into standard \(\min\) / \(g\le 0\) form carefully.
10. Explain LICQ for \(g_1(x,y)=x\), \(g_2=-x\), at \((0,0)\)—are gradients independent?

Challenge

11. Solve \(\min c^\top x\) s.t. \(Ax=b\), \(x\ge 0\) (LP) dual derivation sketch; interpret complementary slackness economically.
12. Show that for convex problem with Slater condition, KKT \(\Rightarrow\) global optimality ( sufficiency sketch).
13. Implement (pseudocode) projected gradient for \(\min f(x)\) on the probability simplex; state a step-size rule under \(L\)-smoothness.
14. For \(\min_w \frac12\|w\|_2^2\) s.t. \(y_i w^\top x_i \ge 1\ \forall i\) (hard-margin, separable), write dual and identify the role of \(\alpha_i\).
15. Discuss why \(\|X\|_*=1\) nuclear-norm ball constraints are convex and how they differ from \(\mathrm{rank}(X)\le k\).

Summary

Constraints turn stationarity into a balance between objective gradients and constraint gradients. KKT packages feasibility, multiplier signs, and complementary slackness into necessary (and, for convex programs, sufficient) optimality conditions. Duality supplies certificates and often simpler dual algorithms—central in ML and resource allocation.