Constrained Optimization

Problem

Minimize \( f(\mathbf{x}) \), \( \mathbf{x} \in \mathbb{R}^n \), subject to \( g_j(\mathbf{x}) = 0 \), \( j=1,\ldots,m \) (equality constraints) or \( g_j(\mathbf{x}) \leq 0 \) (inequality constraints).

• Direct Substitution: Solve \( g_j(\mathbf{x}) = 0 \) for some variables, substitute into \( f(\mathbf{x}) \). Simple but limited to explicit solutions.
• Constrained Variation: Optimize along admissible directions satisfying constraints. Complex for nonlinear constraints.
• Lagrange Multipliers: Form \( \mathcal{L}(\mathbf{x}, \mathbf{\lambda}) = f(\mathbf{x}) + \sum \lambda_j g_j(\mathbf{x}) \), solve \( \nabla_{\mathbf{x}} \mathcal{L} = 0 \), \( g_j(\mathbf{x}) = 0 \). General, extends to inequalities via KKT.

Approach

• Solve: Constraint \( g(\mathbf{x}) = 0 \) for one variable.
• Substitute: Into \( f(\mathbf{x}) \) to eliminate the constraint.
• Optimize: The reduced unconstrained problem.

Example

Minimize \( f(x, y) = x^2 + y^2 \) subject to \( x + y = 1 \):

• Substitute: \( y = 1 - x \) into \( f \).
• Solve: \( \frac{d}{dx}(2x^2 - 2x + 1) = 0 \Rightarrow x = 0.5 \).
• Optimal point: \( (0.5, 0.5) \).

Limitations

• Fails: For complex constraints (e.g., \( x + e^y = 1 \)) or multiple constraints.

Approach

• Parameterize: Variables to satisfy \( g(\mathbf{x}) = 0 \).
• Compute: Admissible variations \( \delta \mathbf{x} \) (tangent to constraint).
• Ensure: \( \nabla f(\mathbf{x}) \) has no component along admissible directions.

Example

Minimize \( f(x, y) = x^2 + y^2 \) subject to \( x + y = 1 \):

• Parameterize: \( x = t \), \( y = 1 - t \).
• Optimize: \( f(t) = 2t^2 - 2t + 1 \).
• Solution: Same as Direct Substitution, \( x = 0.5, y = 0.5 \).

Limitations

• Challenges: Manual parameterization; harder for nonlinear/multiple constraints.

Direct Substitution

• Solves: Constraints explicitly.
• Reduces: Problem dimensionality.
• Limited: To simple constraints.

Constrained Variation

• Works: Along constraint surfaces.
• Geometric: Interpretation.
• Harder: For multiple constraints.

General Rule

Use Direct Substitution when possible; resort to Constrained Variation for complex constraints.

Problem Formulation

Minimize \( f(\mathbf{x}) \), \( \mathbf{x} \in \mathbb{R}^n \), subject to \( g_j(\mathbf{x}) = 0 \), \( j=1,\ldots,m \).

• Assumption: \( f \) and \( g_j \) are differentiable, constraints satisfy regularity (e.g., \( \nabla g_j \) linearly independent).

Lagrangian Function

\[ \mathcal{L}(\mathbf{x}, \mathbf{\lambda}) = f(\mathbf{x}) + \sum_{j=1}^m \lambda_j g_j(\mathbf{x}) \]

where \( \mathbf{\lambda} = (\lambda_1, \ldots, \lambda_m) \) are Lagrange multipliers.

Theorem: Necessary Conditions

At a critical point:

\[ \begin{aligned} \nabla_{\mathbf{x}} \mathcal{L} & = \frac{\partial \mathcal{L}}{\partial x_i} = 0 \quad (i=1,\ldots,n) \\ \frac{\partial \mathcal{L}}{\partial \lambda_j} & = g_j(\mathbf{x}) = 0 \quad (j=1,\ldots,m) \end{aligned} \]

Geometric Intuition

At the optimum, \( \nabla f = -\sum_{j=1}^m \lambda_j \nabla g_j \), meaning gradient alignment of \( f \) with constraint gradients.

• Sensitivity: \( \lambda_j \) measures how \( f^* \) changes with constraint perturbations.
• Shadow price: For \( g_j(\mathbf{x}) = b_j \), \( \lambda_j = \frac{\partial f^*}{\partial b_j} \).
• Physical: Represents constraint forces.
• Sign:
  • \( \lambda_j > 0 \): Tightening increases \( f^* \);
  • \( \lambda_j < 0 \): Tightening decreases \( f^* \);
  • \( \lambda_j = 0 \): Inactive constraint.

Example

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

Solution

• Lagrangian: \( \mathcal{L}(x, y, \lambda) = x^2 + y^2 + \lambda (x + y - 1) \).
• Conditions:

  \[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial x} &= 2x + \lambda = 0 \\ \frac{\partial \mathcal{L}}{\partial y} &= 2y + \lambda = 0 \\ \frac{\partial \mathcal{L}}{\partial \lambda} &= x + y - 1 = 0 \end{aligned} \]

• Solution: \( x = y = \frac{1}{2} \), \( \lambda = -1 \).
• Verification: \( f\left(\frac{1}{2}, \frac{1}{2}\right) = \frac{1}{4} \). Hessian positive definite, confirming a minimum.
• Interpretation: Minimum distance from origin to line \( x + y = 1 \) is \( \frac{\sqrt{2}}{2} \) at \( \left(\frac{1}{2}, \frac{1}{2}\right) \).

Problem Formulation

Minimize \( f(\mathbf{x}) \), \( \mathbf{x} \in \mathbb{R}^n \), subject to \( g_j(\mathbf{x}) \leq 0 \), \( j=1,\ldots,m \).

Karush-Kuhn-Tucker (KKT) Conditions

Form Lagrangian: \( \mathcal{L}(\mathbf{x}, \mathbf{\lambda}) = f(\mathbf{x}) + \sum_{j=1}^m \lambda_j g_j(\mathbf{x}) \).

Necessary conditions:

• Stationarity: \( \nabla_{\mathbf{x}} \mathcal{L} = 0 \).
• Primal feasibility: \( g_j(\mathbf{x}) \leq 0 \).
• Complementary slackness: \( \lambda_j g_j(\mathbf{x}) = 0 \).
• Dual feasibility: \( \lambda_j \geq 0 \).

Example

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

• Solution: Check KKT conditions.
• Inactive: If \( x + y < 1 \), \( \lambda = 0 \), minimum at \( (0,0) \), \( f=0 \).
• Active: If \( x + y = 1 \), \( x = y = \frac{1}{2} \), \( f = \frac{1}{4} \).
• Conclusion: Since \( f(0,0) < f\left(\frac{1}{2}, \frac{1}{2}\right) \), minimum is at \( (0,0) \).

• Active constraints: \( g_j(\mathbf{x}^*) = 0 \), \( \lambda_j > 0 \) (binding).
• Inactive constraints: \( g_j(\mathbf{x}^*) < 0 \), \( \lambda_j = 0 \) (non-binding).
• Constraint qualification: E.g., LICQ: Gradients of active constraints are linearly independent.
• Notes: KKT necessary under qualification; sufficient for convex \( f \) and \( g_j \).

Example

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

\[ \begin{aligned} x + y & \leq 2 \\ y & \geq x \end{aligned} \]

Solution

• Rewrite: \( g_1 = x + y - 2 \leq 0 \), \( g_2 = x - y \leq 0 \).
• KKT conditions:

  \[ \begin{aligned} 2(x-1) + \lambda_1 + \lambda_2 &= 0 \\ 2(y-2) + \lambda_1 - \lambda_2 &= 0 \\ \lambda_1 (x + y - 2) &= 0 \\ \lambda_2 (x - y) &= 0 \\ \lambda_1, \lambda_2 & \geq 0 \end{aligned} \]

• Solve: Assume \( \lambda_1 > 0 \), \( \lambda_2 = 0 \). Then \( x + y = 2 \), yielding \( x = 0.5 \), \( y = 1.5 \), \( \lambda_1 = 1 \). Verify: \( y \geq x \), \( \lambda_1 \geq 0 \).
• Solution: \( x = 0.5 \), \( y = 1.5 \), \( \lambda_1 = 1 \), \( \lambda_2 = 0 \).