2
$\begingroup$

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

The inequality constraints are particularly interesting. We say that a constraint $h^{(i)}(\mathbf{x})$ is active if $h^{(i)}(\mathbf{x}^*) = 0$. If a constraint is not active, then the solution to the problem found using that constraint would remain at least a local solution if that constraint were removed. It is possible that an inactive constraint excludes other solutions. For example, a convex problem with an entire region of globally optimal points (a wide, flat region of equal cost) could have a subset of this region eliminated by constraints, or a nonconvex problem could have better local stationary points excluded by a constraint that is inactive at convergence. Yet the point found at convergence remains a stationary point whether or not the inactive constraints are included. Because an inactive $h^{(i)}$ has negative value, then the solution to $\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}})$ will have $\alpha_i = 0$. We can thus observe that at the solution, $\mathbf{\alpha} \odot \mathbf{h(x)} = \mathbf{0}$. In other words, for all $i$, we know that at least one of the constraints $\alpha_i \ge 0$ or $h^{(i)}(x) \le 0$ must be active at the solution. To gain some intuition for this idea, we can say that either the solution is on the boundary imposed by the inequality and we must use its KKT multiplier to influence the solution to $\mathbf{x}$, or the inequality has no influence on the solution and we represent this by zeroing out its KKT multiplier.

Prior to this section, the authors define the aforementioned functions as follows:

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} = \{ \mathbf{x} | \forall i, g^{(i)}(\mathbf{x}) = 0 \ \text{and} \ \forall j, h^{(j)}(\mathbf{x}) \le 0 \}$. The equations involving $g^{(i)}$ are called the equality constraints, and the inequalities involving $h^{(j)}$ are called the inequality constraints.

So it seems that the $h^{(i)}$ being described here is the "inactive" constraint.

Furthermore, when the authors say that, because an inactive $h^{(i)}$ has negative value, the solution to $\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}})$ will have $\alpha_i = 0$, this is because, in the section prior to saying this, they introduce new variables $\lambda_i$ and $\alpha_j$ for each constraint (these are called KKT multipliers), and define the generalized Lagrangian as

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

So therefore, evidently, if we are calculating $\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}})$, then, in order to satisfy $\max_{\boldsymbol{\mathcal{\alpha, \alpha}}\ge 0}$, we require $\alpha_j = 0$, since, again, $h^{(j)} \le 0$ (that is, it is "inactive").

But this section still leaves me unclear on a number of things:

  1. When the authors refer to "convergence" in this context, they're referring to convergence to the stationary point, right?
  2. Why is it the case that an "inactive" constraint potentially excludes other solutions? Is this just due to the fact that the values being considered during convergence are constrained to $h^{(j)}(\mathbf{x}) \le 0$, and so we are not also considering the values $h^{(j)}(\mathbf{x}) \ge 0$?
  3. I'm not understanding the following explanation and the idea of how the KKT multipliers influence the solution:

To gain some intuition for this idea, we can say that either the solution is on the boundary imposed by the inequality and we must use its KKT multiplier to influence the solution to $\mathbf{x}$, or the inequality has no influence on the solution and we represent this by zeroing out its KKT multiplier.

I would greatly appreciate it if people would please take the time to clarify these points.

$\endgroup$

1 Answer 1

5
$\begingroup$

Let me try: being active or inactive is not a property of the constraint itself, it depends on the constraint and the objective function. What the authors define in that paragraph are general equality/inequality constraints.

For ex, if you are minimizing $f(x,y)=x^2+y^2$ subjected to $h(x,y)=x^2+y^2-1\le 0$ (in the unit disk), the minimum is achieved at $(0,0)$, where $h(0,0)=-1<0$ so the constraint is not active. Now take $f(x,y)=(x-2)^2+y^2$ with the same constraint. The minimum is achieved on the boundary of your domain $\{(x,y):h(x,y)=x^2+y^2-1\le 0\}$, namely at $(1,0)$ ($f$ is just a shifted paraboloid) and this time the constraint is active, since $h(1,0)=0$. Being active implies that the condition for a minimum is not just the unconstrained $\nabla f(P)=0$ but it also involves the constraint and a non-zero Lagrange multiplier appears because what you have is a conditional extremum on the curve $h=0$. At such minimum, it is not true that $\nabla f=0$ but $\nabla f+\lambda\nabla h=0$. In other words, inequality constraints are active for your problem when the max/min happens at a point in the boundary, when $h=0$ and then a Lagrange multiplier appears. There are as many non-zero multipliers as "active" constraints. The language used by the authors is very unclear, very typical of Data science/Machine Learning books (many words to say something that could be explained in one clear line).

$\endgroup$
4
  • $\begingroup$ Your excellent explanation did well in adding credibility to your concluding comment (on the lack of clarity of such textbooks). After reading your answer, I'm surprised at just how unclear the authors' explanation was (even more so than I initially thought!). Thank you for taking the time to clarify all of this for me! $\endgroup$ Jan 14, 2020 at 3:51
  • $\begingroup$ By the way, just one last thing: When the authors refer to "convergence" in this context, they're referring to convergence to the stationary point, right? $\endgroup$ Jan 14, 2020 at 3:53
  • 1
    $\begingroup$ Yes, they do. One more unnecessary word. $\endgroup$
    – GReyes
    Jan 14, 2020 at 6:40
  • $\begingroup$ Beware however, that a Lagrangian multiplier can also be zero, even though its corresponding constraint is "active." Take your last example with instead objective $$f(x,y) = (x-1)^2+y^2,$$ the constraint is active but the multiplier is null. $\endgroup$
    – Cryme
    Jun 15 at 16:27

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.