An inequality constraint is active when $h^{(j)} (x) = 0$. This means that the optimum might change were that constraint removed.

Active Constraints

In the Karush-Kuhn-Tucker (KKT) approach, the variables $$\lambda_{i}$$ and $$\alpha_{j}$$ are added for each constraint; these are called the KKT multipliers. With these, we can build the generalized Lagrangian as follows: $$\mathop{\mathcal{L}}(x, \lambda, \alpha) = f(x) + \sum_{i} \lambda_{i} g^{(i)}(x)+ \sum_{j} \alpha_{j} h^{(j)}(x)$$

KKT Step 2: KKT Multipliers and the Generalized Lagrangian

Describe $\mathbb{S}$ with $m$ functions $g^{(i)}$ and $n$ functions $h^{(j)}$ s.t. $\mathbb{S}=\{x | \forall i, g^{(i)} (x) = 0$ and $\forall j, h^{(j)} (x) \le 0 \}$.

Equations with $g^{(i)}$ are equality constraints. Equations with $h^{(j)}$ are inequality constraints

Michigan State University

The Karush-Kuhn-Tucker (KKT) approach is used for constrained optimization and attempts to create and solve a function called the generalized Lagrangian. The process involves: 1) Describing the feasible set, $$\mathbb{S}$$, in terms of equations and inequalities; 2) Introducing the variables $$\lambda$$ and $$\alpha$$ to formulate the generalized Lagrangian; and 3) Optimizing $$\min_{x} \max_{\lambda} \max_{\alpha,\alpha\ge0} \mathop{\mathcal{L}}(x, \lambda, \alpha)$$. This approach can also be used as a parameter norm penalty by which to regularize the cost function.

Karush-Kuhn-Tucker Approach (KKT)

Goodfellow, I., Bengio, Y., & Courville, A. (2016). $\mathit{Deep \ Learning.}$ MIT Press. Retrieved from [www.deeplearningbook.org](https://www.deeplearningbook.org) 

Deep Learning

KKT Step 1: Equality and Inequality Constraints

A parameter norm penalty such as KKT imposes a constraint on cost function weights. This allows us to roughly grow or shrink our constraint region.



Pros and Cons of KKT/Norm Penalties for Constrained Optimization

Finally, optimize $$\min_{x} \max_{\lambda} \max_{\alpha,\alpha\ge0} \mathop{\mathcal{L}}(x, \lambda, \alpha)$$, as it has the same optimal objective function value and set of optimal points as $$\min_{x \in \mathbb{S}} f(x)$$. This works because $$\max_{\lambda} \max_{\alpha,\alpha\ge0} \mathop{\mathcal{L}}(x, \lambda, \alpha) = f(x)$$ while the constraints are satisfied and $$\infty$$ elsewhere.

Learn Before

Related

Learn After