In some cases, explicit constraints and reprojection may be more useful than penalties. This can be achieved by modifying approaches such as Stochastic Gradient Descent. One problem with the norm penalty approach is that, for small Theta, nonconvex optimization procedures might get stuck in local minima.

Non-Penalty Approaches

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.



University of Massachusetts at Amherst

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. 

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

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.

Learn Before

Related

Learn After