# Correct way to interpret notation used in optimization problem?

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.

• 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\$. – lonza leggiera Nov 25 '19 at 6:35
• @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. – The Pointer Nov 25 '19 at 6:40
• 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\$. – lonza leggiera Nov 25 '19 at 8:13
• @lonzaleggiera Interesting. Thank you for taking the time to explain. – The Pointer Nov 25 '19 at 10:08

$$\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}})$$
• 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}})$? – The Pointer Nov 25 '19 at 22:36