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

KKT Step 1: Equality and Inequality Constraints

The variables $\lambda_{i}$ and $\alpha_{j}$ are added for each constraint, 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

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.

KKT Step 3: Optimizing the Lagrangian

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

Attempts to create and solve a function called the generalized Lagrangian
1) Describe the set, $\mathbb{S}$, in terms of equations and inequalities
2) Introduce the variables $\lambda$ and $\alpha$ to get the generalized Lagrangian
3) Optimize  $min_{x}$ $max_{\lambda}$ $max_{\alpha,\alpha\ge0}$ $\mathop{\mathcal{L}}(x, \lambda, \alpha)$

This approach can be used as a parameter norm penalty by which to regularize the cost function. 

Michigan State University

University of Massachusetts at Amherst

Finding the minimum or maximum value of a function, $f(x)$, over a set of inputs, $\mathbb{S}$.  Points in $\mathbb{S}$ are called feasible points.

Constrained Optimization

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

Learn Before

Related

Learn After