3
$\begingroup$

My textbook, Deep Learning by Goodfellow, Bengio, and Courville, says the following in a section on constrained optimization:

The Karush-Kuhn-Tucker (KKT) approach provides a very general solution to constrained optimization. With the KKT approach, we introduce a new function called the generalized Lagrangian or generalized Lagrange function.

To define the Lagrangian, we first need to describe $\mathbb{S}$ in terms of equations and inequalities. We want a description of $\mathbb{S}$ in terms of $m$ functions $g^{(i)}$ and $n$ functions $h^{(j)}$ so that $\mathbb{S} = \{ \boldsymbol{\mathcal{x}} \mid \forall i, g^{(i)}(\boldsymbol{\mathcal{x}}) = 0 \ \text{and} \ \forall j, h^{(j)} (\boldsymbol{\mathcal{x}}) \le 0 \}$. The equations involving $g^{(i)}$ are called the equality constraints, and the inequalities involving $h^{(j)}$ are called inequality constraints.

We introduce new variables $\lambda_i$ and $\alpha_j$ for each constraint, these are called the KKT multipliers. The generalized Lagrangian is then defined as

$$L(\boldsymbol{\mathcal{x}}, \boldsymbol{\lambda}, \boldsymbol{\alpha}) = f(\boldsymbol{\mathcal{x}}) + \sum_i \lambda_i g^{(i)} (\boldsymbol{\mathcal{x}}) + \sum_j \alpha_j h^{(j)}(\boldsymbol{\mathcal{x}}) \tag{4.14}$$

We can now solve a constrained minimisation problem using unconstrained optimization of the generalized Lagrangian. As long as at least one feasible point exists and $f(\boldsymbol{\mathcal{x}})$ is not permitted to have value $\infty$, then

$$\min_{\boldsymbol{\mathcal{x}}} \max_{\boldsymbol{\mathcal{\lambda}}} \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}}) \tag{4.15}$$

has the same optimal objective function value and set of optimal points $\boldsymbol{\mathcal{x}}$ as

$$\min_{\boldsymbol{\mathcal{x}} \in \mathbb{S}} f(\boldsymbol{\mathcal{x}}). \tag{4.16}$$

This follows because any time the constraints are satisfied,

$$\max_{\boldsymbol{\mathcal{\lambda}}} \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}}) = f(\boldsymbol{\mathcal{x}}),$$

while any time a constraint is violated,

$$\max_{\boldsymbol{\mathcal{\lambda}}} \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}}) = \infty$$

these properties guarantee that no infeasible point can be optimal, and that the optimum within the feasible points is unchanged.

I'm having difficulty understanding how $$\min_{\boldsymbol{\mathcal{x}}} \max_{\boldsymbol{\mathcal{\lambda}}} \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}})$$

has the same optimal objective function value and set of optimal points $\boldsymbol{\mathcal{x}}$ as

$$\min_{\boldsymbol{\mathcal{x}} \in \mathbb{S}} f(\boldsymbol{\mathcal{x}})$$

Specifically, I am not seeing how the latter claim that any time the constraints are satisfied,

$$\max_{\boldsymbol{\mathcal{\lambda}}} \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}}) = f(\boldsymbol{\mathcal{x}}),$$

while any time a constraint is violated,

$$\max_{\boldsymbol{\mathcal{\lambda}}} \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}}) = \infty$$

I would greatly appreciate it if people could please take the time to clarify this.

$\endgroup$

2 Answers 2

3
+100
$\begingroup$

Starting with:

$$L(\boldsymbol{\mathcal{x}}, \boldsymbol{\lambda}, \boldsymbol{\alpha}) = f(\boldsymbol{\mathcal{x}}) + \sum_i \lambda_i g^{(i)} (\boldsymbol{\mathcal{x}}) + \sum_j \alpha_j h^{(j)}(\boldsymbol{\mathcal{x}}) \tag{4.14}$$

If the constraints are satisfied, then $g^{(i)}(x)=0$ and $h^{(j)}(x)\leq0$. Therefore, the terms with $\lambda$ all vanish, and the terms with $\alpha$ attain their maximum over $\alpha_j$ at $\alpha_j=0$ (because the last term cannot be positive), so also those terms vanish, leaving you with $f(x)$.

On the other hand, suppose a constraint is not satisfied. If $g^{(i)}(x)\neq 0$ for some $i$, you can let $\lambda_i g^{(i)}(x)$ go to infinity by letting $\lambda_i$ go to $\infty$ if $g^{(i)}(x)>0$, and $\lambda_i \to -\infty$ otherwise. Similarly, if $h^{(j)}(x)>0$ for some $i$, you can let $\alpha_j h^{(j)}(\boldsymbol{\mathcal{x}})$ go to $\infty$ by letting $\alpha_j \to \infty$.

$\endgroup$
0
$\begingroup$

If $x\in S$ then $f(x) \ge L(x,\lambda,\alpha)$ for all $\lambda,\alpha$ with $\alpha\ge0$.

If $x\not\in S$ then one of the constraints is violated,i.e., $h_i(x)\ne0$ or $g_j(x)\>0$ for some $i$ or $j$. By taking the corresponding multiplier $\lambda_i$ or $\alpha_j$ large enough, one see $\sup_{\lambda,\alpha\ge0} L(x,\lambda,\alpha)=+\infty$.

$\endgroup$
6
  • $\begingroup$ But how do you reconcile your first claim with the claim that $\max_{\boldsymbol{\mathcal{\lambda}}} \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}}) = f(\boldsymbol{\mathcal{x}})$? $\endgroup$ Oct 8, 2019 at 14:05
  • $\begingroup$ But that still contradicts $\max_{\boldsymbol{\mathcal{\lambda}}} \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}}) = f(\boldsymbol{\mathcal{x}})$, doesn't it? That's why I'm confused. $\endgroup$ Oct 8, 2019 at 14:08
  • $\begingroup$ Also with regards to your second claim, why must it be true? It isn't obvious to me that a violation constraint necessarily results in $\max_{\boldsymbol{\mathcal{\lambda}}} \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}}) = \infty$, as is claimed? $\endgroup$ Oct 8, 2019 at 14:10
  • $\begingroup$ If $x$ is feasible the $f(x) \ge L(x,\dots)$ and equality is attained for $\lambda$ and $\alpha$ being zero $\endgroup$
    – daw
    Oct 8, 2019 at 14:10
  • 1
    $\begingroup$ Equality is between $f(x)$ and $\max_{\alpha,\lambda} L$ not between $f(x)$ and $L$ for arbitrary values of $\lambda,\alpha$. $\endgroup$
    – daw
    Oct 10, 2019 at 11:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .