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$.