Constrained Optimization

Equality Constraints (Lagrange Multipliers Review)

Inequality Constraints

KKT Conditions (Karush-Kuhn-Tucker)

Active Set Methods

Interior Point Methods

Penalty Methods

Python Implementation

scipy.optimize

from scipy.optimize import minimize, NonlinearConstraint, LinearConstraint
import numpy as np

# Example 1: Equality constraint
# Minimize x^2 + y^2 subject to x + y = 1
def objective(x):
    return x[0]**2 + x[1]**2

def eq_constraint(x):
    return x[0] + x[1] - 1

constraints = [{'type': 'eq', 'fun': eq_constraint}]
result = minimize(objective, x0=[0, 0], constraints=constraints, method='SLSQP')
print(f"Optimal point: {result.x}")       # [0.5, 0.5]
print(f"Optimal value: {result.fun}")     # 0.5
print(f"Multiplier: {result.v}")          # Lagrange multiplier

# Example 2: Inequality constraint
# Minimize (x-2)^2 + (y-1)^2 subject to x + y <= 1
def ineq_constraint(x):
    return 1 - x[0] - x[1]  # g(x) >= 0 for scipy (>= form)

result2 = minimize(objective, x0=[0, 0], constraints={'type': 'ineq', 'fun': ineq_constraint})
print(f"Optimal point: {result2.x}")      # [0.6667, 0.3333]

# Example 3: Multiple constraints with bounds
from scipy.optimize import minimize
bounds = [(0, None), (0, None)]  # x >= 0, y >= 0
constraints_multi = [
    {'type': 'eq', 'fun': lambda x: x[0] + x[1] - 1},
    {'type': 'ineq', 'fun': lambda x: 1 - x[0]**2 - x[1]**2}
]
result3 = minimize(objective, x0=[0.5, 0.5], constraints=constraints_multi, bounds=bounds)
print(f"Optimal point: {result3.x}")

cvxpy

import cvxpy as cp

# Example 1: Simple constrained problem
x = cp.Variable(2)
objective = cp.Minimize(cp.sum_squares(x))
constraints = [cp.sum(x) == 1]
prob = cp.Problem(objective, constraints)
prob.solve()
print(f"Optimal value: {prob.value}")       # 0.5
print(f"Optimal x: {x.value}")              # [0.5, 0.5]
print(f"Shadow price: {constraints[0].dual_value}")  # Lagrange multiplier

# Example 2: SVM-like problem
n_samples, n_features = 100, 5
np.random.seed(42)
X = np.random.randn(n_samples, n_features)
y = np.sign(np.random.randn(n_samples))

w = cp.Variable(n_features)
b = cp.Variable()
loss = cp.sum(cp.pos(1 - cp.multiply(y, X @ w + b)))
reg = 0.01 * cp.sum_squares(w)
prob = cp.Problem(cp.Minimize(reg + loss))
prob.solve()
print(f"SVM accuracy: {np.mean(np.sign(X @ w.value + b.value) == y):.2%}")

# Example 3: Portfolio optimization
n_assets = 5
mu = np.random.randn(n_assets) * 0.05 + 0.1  # expected returns
Sigma = np.random.randn(n_assets, n_assets) * 0.1
Sigma = Sigma @ Sigma.T + np.eye(n_assets) * 0.01  # covariance

w = cp.Variable(n_assets)
ret = mu @ w
risk = cp.quad_form(w, Sigma)
constraints = [cp.sum(w) == 1, w >= 0]  # fully invested, no shorting
prob = cp.Problem(cp.Minimize(risk - 0.5 * ret), constraints)  # risk-averse
prob.solve()
print(f"Portfolio weights: {np.round(w.value, 3)}")

Applications in AI/ML

Support Vector Machines (SVM)

Fairness in Machine Learning

Other ML Applications

Common Mistakes

Mistake	Why It's Wrong	Correct Approach
Ignoring constraint qualifications	KKT conditions may not hold without a valid CQ	Always verify LICQ, MFCQ, or Slater's condition
Forgetting for inequalities	Negative multipliers violate dual feasibility	Check sign of multipliers at the solution
Assuming all constraints are active	Most constraints are typically inactive at the optimum	Use complementary slackness to identify active constraints
Using penalty methods with fixed	A single either gives infeasible or ill-conditioned solutions	Use an increasing sequence of values
Confusing and forms	The sign convention affects the KKT sign conditions	Standardize: write all inequalities as
Not checking feasibility first	Optimizing over an empty feasible set wastes computation	Verify the feasible region is non-empty before solving
Ignoring convexity	Non-convex problems may have local minima that are not global	Check if the problem is convex; if not, use global optimization
Treating equality constraints as inequalities	Equality constraints require different multiplier sign conventions	Keep equality and inequality constraints separate in the KKT system

Interview Questions

Q1: What is the difference between a binding and non-binding constraint? A binding constraint is satisfied with equality at the optimum (). A non-binding constraint is strictly satisfied () and does not affect the optimal solution. Only binding constraints have non-zero Lagrange multipliers.

Q2: Why do we need constraint qualifications for KKT conditions? Constraint qualifications ensure that the feasible region is "well-behaved" near the optimum. Without them, the KKT conditions may fail to hold even at a local minimum. For example, if the active constraint gradients are linearly dependent, the KKT gradient equation may have no solution for the multipliers.

Q3: How do penalty methods differ from augmented Lagrangian methods? Penalty methods add and require for exactness, causing ill-conditioning. Augmented Lagrangian methods add both and , updating at each step. This avoids the need for and maintains better conditioning.

Q4: When should you use interior point vs. active set methods? Interior point methods are preferred for large-scale problems (thousands of variables and constraints) because they have polynomial complexity. Active set methods are faster for small to medium QPs, especially when the active set changes little between iterations. Interior point methods also require a strictly feasible start, which can be hard to find.

Q5: Explain complementary slackness in plain language. Complementary slackness says that at the optimum, each constraint is either "tight" (active, ) or "irrelevant" (its multiplier is zero, ). A constraint cannot be simultaneously loose and influential — if there's slack, the constraint doesn't matter.

Q6: How do SVMs use KKT conditions? The KKT conditions of the SVM dual problem yield support vectors. Complementary slackness ensures that only points on the margin or misclassified points () contribute to the decision boundary. All other points () can be discarded, making SVMs memory-efficient.

Q7: What happens if a constraint qualification fails? If LICQ fails (active constraint gradients are linearly dependent), the KKT multipliers may not exist or may not be unique. The KKT conditions are no longer necessary for optimality. You must use alternative methods or reformulate the problem.

Q8: Can you convert an equality constraint to two inequality constraints? Yes: is equivalent to and . However, this doubles the number of constraints and may violate constraint qualifications at the solution (since both constraints are active with linearly dependent gradients).

Practice Problems

Quick Reference

Cross-References

Previous: 064 - Gradient Descent — unconstrained optimization foundations
Previous: 061 - Linear Algebra for Optimization — matrix operations used in constrained solvers
Related: 066 - Convex Optimization — when KKT conditions become sufficient for global optimality
Related: 059 - Calculus — derivatives and gradients underlying KKT stationarity
Application: 060 - Probability & Statistics — expected values and variance in portfolio optimization
Application: 062 - Information Theory — entropy-constrained coding and rate-distortion theory
Advanced: Semi-definite programming (SDP) extends constrained optimization to matrix-valued constraints
Advanced: Bilevel optimization involves nested constrained problems (leader-follower structure)

Constrained Optimization