10
$\begingroup$

I would like to "grok" Slater's condition and other constraint qualification conditions in optimization.

Slater's condition is only one of many different constraint qualifications in the optimization literature. Which one is the most fundamental? Which one tells me "what's really going on"? What is the basic idea at the heart of this?

Also, constraint qualifications appear in both convex and non-convex optimization. Is there a unifying viewpoint that shows it is the same simple, basic idea in all cases?

I'd be interested in any insights or viewpoints that lead to a deeper understanding of constraint qualifications in optimization.


Edit: Here is one possible viewpoint. Buried on p. 223 (chapter 23) of Rockafellar's Convex Analysis, we find the following fundamental and vital fact.

Let $f_1,\ldots,f_m$ be proper convex functions on $\mathbb R^n$, and let $f = f_1 + \cdots + f_m$. If the convex sets $\text{ri}(\text{dom } f_i), i = 1,\ldots m$, have a point in common, then $$ \partial f(x) = \partial f_1(x) + \cdots + \partial f_m(x). $$ This condition for equality can be weakened slightly if certain of the functions, say $f_1,\ldots, f_k$, are polyhedral: then it is enough if the sets $\text{dom } f_i, i = 1,\ldots,k$ and $\text{ri}(\text{dom } f_i), i = k+1,\ldots,m$ have a point in common.

This subdifferential sum rule can be used to derive optimality conditions for various convex optimization problems, including the KKT conditions for convex problems. For example, the optimization problem

\begin{align} \text{minimize} & \quad f(x) \\ \text{subject to } & \quad x \in C \end{align} where $f$ is a closed convex functin and $C$ is a closed convex set, is equivalent to the problem $$ \text{minimize} \quad f(x) + I_C(x) $$ where $I_C$ is the indicator function for $C$. The optimality condition for this problem is $$ 0 \in \partial (f + I_C)(x) = \partial f(x) + \partial I_C(x), $$ but for the equality to be valid the "overlapping relative interior" condition must be satisfied. So, we need the relative interior of $C$ to have a point in common with the relative interior of $\text{dom } f$. This is a "constraint qualification" for the problem of minimizing $f$ subject to the constraint that $x \in C$.

So is this "overlapping relative interiors" condition appearing in the subdifferential sum rule the ultimate, most fundamental constraint qualification?

Can Slater's condition be viewed as a special case of this "overlapping relative interior" condition?

The "overlapping relative interior" condition apparently has nothing to do with non-convex optimization problems. Is there a unifying viewpoint that applies to both convex and non-convex problems?

$\endgroup$
  • 1
    $\begingroup$ You can basically reduce them to "make Lagrangian multiplier rule work (be necessary)". Or more technical, to make the tangential cone equal the linearized tangential cone (or other kind of approximation). Notice that the tangential cone is purely geometric, but most approximations are analytic an depends on the set description. $\endgroup$ – user251257 Dec 30 '16 at 4:01
  • $\begingroup$ @user251257 Does the "make the tangent cone equal the linearized tangent cone" interpretation still work for convex optimization problems with nondifferentiable objective and constraint functions? $\endgroup$ – eternalGoldenBraid Dec 30 '16 at 5:08
  • $\begingroup$ @user251257 Your comment was helpful, by the way, thank you. $\endgroup$ – eternalGoldenBraid Dec 30 '16 at 14:13
  • $\begingroup$ On your edit: You state a subgradient-sum theorem which allows functions to take infinite values, but requires existence of points where the functions are all finite. This makes sense as a requirement since we cannot evaluate subgradients at points where the function value is $\infty$. This seems to be a minor detail that does not (directly) relate to Slater's condition, since Slater's condition applies to problems with functional inequality constraints (and does not necessarily involve a sum of functions). $\endgroup$ – Michael Sep 22 '17 at 0:24
  • $\begingroup$ @Michael I think the subdifferential sum rule might be at the heart of one way of understanding the KKT conditions, though. The most fundamental optimality condition, for minimizing a function $f$, is $0 \in \partial f(x)$. The problem of minimizing $f(x)$ subject to $x \in C$ can be expressed as minimizing $f(x) + I_C(x)$, and the optimality condition is $0 \in \partial f(x) + \partial I_C(x)$. Now the next step is that if $C$ is determined by a bunch of inequality constraints, we can describe $\partial I_C(x)$ much more explicitly, and as a result obtain (hopefully) the KKT conditions. $\endgroup$ – eternalGoldenBraid Sep 23 '17 at 7:06
4
+50
$\begingroup$

Slater's condition relates to existence of Lagrange multipliers in a convex program. Lagrange multipliers exist when there is a nonvertical supporting hyperplane that passes through a point on the boundary of a related convex set. Intuitively, nonvertical hyperplanes can only fail to exist when constraints of the convex program can only be achieved at "edge" type points of the set...Slater ensures constraints can be achieved at "non-edge" type points.

Discussions with pictures can be found in various places, such as Convex Analysis and Optimization by Bertsekas, Nedic, and Ozdaglar. The Slater result is very simple to derive and below I summarize a math derivation that may also give intuition.


The convex program

Mathematically we have a general convex program:

\begin{align} \mbox{Minimize:} \quad & f(x) \\ \mbox{Subject to:} \quad & g_i(x) \leq 0 \quad , \forall i \in \{1, \ldots, k\} \\ & x \in \mathcal{X} \end{align} where $\mathcal{X} \subseteq \mathbb{R}^n$ is a convex set and $f, g_1, ..., g_k$ are convex functions defined over $\mathcal{X}$. Let us suppose there is (at least one) $x^* \in \mathcal{X}$ that is an optimal solution to the above convex program.

Lagrange multipliers

Define the set $\mathcal{A}$: $$ \mathcal{A} = \{(y_0, y_1, ..., y_k) : y_0 \geq f(x), y_1 \geq g_1(x), ..., y_k \geq g_k(x) \mbox{ for some $x \in \mathcal{X}$} \}$$

It can be shown that $\mathcal{A}$ is a convex set and the point $(f(x^*), 0, 0, ..., 0)$ is a boundary point of the set. By the hyperplane separation theorem it follows there are real numbers $\theta_0, \theta_1, ..., \theta_k$, not all zero, such that $$ \theta_0y_0 + \sum_{i=1}^k \theta_i y_i \geq \theta_0f(x^*) \quad \forall (y_0, ..., y_k) \in \mathcal{A} $$ By nature of the set $\mathcal{A}$ (namely, any point that dominates a point in $\mathcal{A}$ is also in $\mathcal{A}$), it is easy to show the above can only hold if $\theta_i \geq 0$ for all $i \in \{0, 1, ..., k\}$. Since for any $x \in \mathcal{X}$ we have $(f(x), g_1(x), ..., g_k(x)) \in \mathcal{A}$, a special case of the above inequality is: $$ \theta_0f(x) + \sum_{i=1}^k \theta_i g_i(x) \geq \theta_0f(x^*) \quad \forall x \in \mathcal{X} \quad (Eq. 1)$$

We say the hyperplane is nonvertical if $\theta_0 \neq 0$, in which case we can define $\mu_i = \theta_i/\theta_0 \geq 0$ for all $i \in \{1, ..., k\}$ and we call these Lagrange multipliers because they are nonnegative and: $$ \theta_0 \neq 0 \implies f(x) + \sum_{i=1}^k \mu_i g_i(x) \geq f(x^*) \quad, \forall x \in \mathcal{X}$$ Assuming $\theta_0 \neq 0$, the above inequality implies that $x^*$ is a minimizer of $f(x) + \sum_{i=1}^k \mu_ig_i(x)$ over all $x \in \mathcal{X}$, the minimum value is $f(x^*)$, and $\mu_i g_i(x^*)=0$ for all $i \in \{1, ..., k\}$.

Slater's condition

Slater's condition: Suppose there is an $s \in \mathcal{X}$ such that $g_i(s) < 0$ for all $i \in \{1, ..., k\}$. (So all constraints can be achieved with positive slackness.)

Claim: If Slater's condition holds, then $\theta_0 \neq 0$ and hence Lagrange multipliers exist.

Proof: Assume $\theta_0=0$ and plug $s \in \mathcal{X}$ into Eq. 1 to get a contradiction (recalling that not all $\theta_i$ are zero). $\Box$

I do not fill in the details here since I sometimes give these details as a homework exercise (Exercise VIII-B.8 on page 40 here):

http://ee.usc.edu/stochastic-nets/docs/network-optimization-notes.pdf

Fig. 19 on page 55 of those notes gives a simple counter-example where a nonvertical hyperplane does not exist, and this is also useful to get intuition on Slater's condition. These examples are standard and similar ones can be found in the Bertsekas book.

Further intuition

Going back to the set $\mathcal{A}$ and the boundary point $(f(x^*), 0, 0, ..., 0)$, intuitively we see that if Slater's condition holds then any vertical hyperplane that passes through this boundary point would chop $\mathcal{A}$ into two pieces (with points of $\mathcal{A}$ lying strictly on one side of the vertical hyperplane, and other points lying strictly on the other side). Hence, if Slater's condition is true, then a vertical hyperplane would fail to be a supporting hyperplane. [Again refer to Fig. 19 in the above notes to visualize.]

$\endgroup$

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.