0
$\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.

My questions concerns the notation used in (4.15):

$$\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}})$$

What specifically is meant by $\min_\limits{\boldsymbol{\mathcal{x}}} \max_\limits{\boldsymbol{\mathcal{\lambda}}} \max_\limits{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0}$? Does this mean that we want to find the $\boldsymbol{\mathcal{\alpha}}\ge 0$ that maximizes $L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}})$, and then the $\boldsymbol{\mathcal{\lambda}}$ that maximizes $L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}})$, and then the $\boldsymbol{\mathcal{x}}$ that minimizes $L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}})$? Or does it mean that we want to find the $\boldsymbol{\mathcal{\alpha}}\ge 0$ that maximizes the term in $L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}})$ that contains $\boldsymbol{\mathcal{\alpha}}$, and then the $\boldsymbol{\mathcal{\lambda}}$ that maximizes the term in $L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}})$ that contains the $\boldsymbol{\mathcal{\lambda}}$, and then the $\boldsymbol{\mathcal{x}}$ that minimizes the term in $L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}})$ that contains $\boldsymbol{\mathcal{x}}$? What is the correct way to interpret this notation in general?

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

EDIT:

Please see my response, in the comments, to Lonza Leggiera. If my first interpretation is correct, and, as Lonza Leggiera says, we maximize/minimize as a function of the other variables, then, in general (not necessarily just this optimization problem in particular), couldn't the value that we select for the first step/variable as a maximizer/minimizer change depending on what is selected for the other variables? This is one of the aspects that I found confusing in my trail of thought.

$\endgroup$
  • 1
    $\begingroup$ Your first is the usual interpretation, although you need to realise than the maximising $\ \alpha\ $ in the first step will in general be a function of both $\ x\ $ and $\ \lambda\ $, and the maximising $\ \lambda\ $ in the second step will in general be a function of $\ x\ $. $\endgroup$ – lonza leggiera Nov 25 '19 at 6:35
  • $\begingroup$ @lonzaleggiera Ahh, yes, that's precisely what I thought. But this then makes it confusing, because how do we maximize/minimize when we have other variables? In general, couldn't the value that we select for the first step as a maximizer/minimizer change depending on what is selected for the other variables? This is what confused me. $\endgroup$ – The Pointer Nov 25 '19 at 6:40
  • 1
    $\begingroup$ Yes, that's right. In the first step, for every relevant value of the variables $\ x\ $ and $\ \lambda\ $, you have to solve the problem of maximising $\ L(x, \lambda, \alpha)\ $, and the solution will in general depend on the values of those other variables. Typically, it may not be possible to find a simple closed-form expression for either the the maximising value of $\ \alpha\ $, or the maximum value of $\ L\ $, in which case you may have to be satisfied with numerical approximations for only a finite number of discrete values of $\ x\ $ and $\ \lambda\ $. $\endgroup$ – lonza leggiera Nov 25 '19 at 8:13
  • $\begingroup$ @lonzaleggiera Interesting. Thank you for taking the time to explain. $\endgroup$ – The Pointer Nov 25 '19 at 10:08
2
$\begingroup$

$$\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}$$

Define $$f(\boldsymbol{\mathcal{x}})=\max_{\boldsymbol{\mathcal{\lambda}}} g(\boldsymbol{\mathcal{x}},\boldsymbol{\mathcal{\lambda}})$$ with $$g(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}) = \max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0} L(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}}, \boldsymbol{\mathcal{\alpha}})$$ 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}}) = \min_{\boldsymbol{\mathcal{x}}} f(\boldsymbol{\mathcal{x}})$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer. Did you mean $f(\boldsymbol{\mathcal{x}})=\max_\limits{\boldsymbol{\mathcal{\lambda}}} g(\boldsymbol{\mathcal{x}}, \boldsymbol{\mathcal{\lambda}})$ rather than $f(\boldsymbol{\mathcal{x}})=\max_\limits{\boldsymbol{\mathcal{\lambda}}} g(\boldsymbol{\mathcal{x}})$? $\endgroup$ – The Pointer Nov 25 '19 at 22:36
  • $\begingroup$ @ThePointer yes! thanks for spotting that $\endgroup$ – LinAlg Nov 26 '19 at 2:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.