Constrained Optimization

⛓️ Constrained Optimization

Most real-world problems involve constraints (e.g., budget limits, physical boundaries, or resource capacities). Constrained optimization provides the tools to solve these problems rigorously.

---

🟢 1. Equality Constraints

To minimize $f(x)$ subject to $g(x) = 0$, we use the method of Lagrange Multipliers.

The Lagrangian Function

We define the Lagrangian as: $\mathcal{L}(x, \lambda) = f(x) + \lambda g(x)$ The necessary condition for an optimum is that the gradient of the Lagrangian is zero: $\nabla_x \mathcal{L} = 0 \implies \nabla f(x) + \lambda \nabla g(x) = 0$ $\nabla_\lambda \mathcal{L} = 0 \implies g(x) = 0$ Geometrically, this means the gradient of the objective function must be parallel to the gradient of the constraint.

---

🟡 2. Inequality Constraints (KKT)

When we have inequality constraints $h(x) \le 0$, we use the Karush-Kuhn-Tucker (KKT) conditions, which generalize Lagrange multipliers.

The KKT Conditions

For a point $x^*$ to be optimal, there must exist multipliers $\lambda$ and $\mu$ such that:

1. Stationarity: $\nabla f(x^*) + \sum \lambda_i \nabla g_i(x^*) + \sum \mu_j \nabla h_j(x^*) = 0$
2. Primal Feasibility: $g_i(x^*) = 0$ and $h_j(x^*) \le 0$
3. Dual Feasibility: $\mu_j \ge 0$
4. Complementary Slackness: $\mu_j h_j(x^*) = 0$

Note

Complementary Slackness means that either the constraint is active ($h(x) = 0$) or the multiplier is zero ($\mu = 0$). This is fundamental in Support Vector Machines (SVMs), where only “support vectors” have non-zero multipliers.

---

🔴 3. Penalty and Barrier Methods

Sometimes it is easier to convert a constrained problem into an unconstrained one.

Penalty Methods

Add a term to the objective function that penalizes constraint violations: $\text{minimize } f(x) + \rho \|g(x)\|^2$ As $\rho \to \infty$, the solution approaches the true constrained optimum.

Interior-Point Methods (Barrier)

Use a logarithmic “barrier” to keep the solution inside the feasible region: $\text{minimize } f(x) - \frac{1}{t} \sum \log(-h_j(x))$ As $t$ increases, the barrier becomes steeper, and the solution converges to the boundary if necessary.

Tip

In Software Engineering, Linear Programming (LP) is a specific type of constrained optimization used for task scheduling and network flow problems.