0
$\begingroup$

I'm reading Convex Optimization by Boyd and Vandenberghe. This is how they describe Slater's condition:

enter image description here

What I don't understand is why it is necessary to enforce that $x$ be in the relative interior of $\mathcal{D}$, where

$$ \mathcal{D} := \bigcap_{i = 1}^m \text{dom}(f_i), $$

i.e., it is the intersection of the domains of the $f_i$'s. Doesn't the fact $f_i(x) < 0$ for all $i$ immediately imply that $x \in \text{relint}(\mathcal{D})$? So why state the theorem this way?


As a side note, Wikipedia gives the exact same seemingly extraneous condition:

enter image description here


Please let me know what I'm misunderstanding. Why is this additional condition necessary? Thank you!


EDIT: I probably have some fundamental misunderstanding, so I'm adding this edit to be more clear about what I'm thinking. If I'm not wrong, the fact that the constraints $f_i$ are convex means that the intersection of the spaces spelled out by $f_i(x) \le 0$ for all $i = 1, \dots, m$ is convex. The feasible region is then the intersection of this convex space with an affine space, that being the affine space spelled out by $Ax = b$.

It seems to me that any point $x$ that satisfies $f_i(x) < 0$ will not only be in $\text{relint} \mathcal{D}$, it will even be in the relative interior of the feasible region described above. This is just because the convex functions $f_i(x) = 0$ form the boundary of the feasible region (in a semi-intuitive sense). The fact that $x$ satisfies $f_i(x) < 0$ for all $i$ means that it will be an interior point since it doesn't lie on the boundary.

$\endgroup$
7
  • $\begingroup$ How does the sign of f(x*) imply that it is in relint D? The points belonging to relint D are determined by D and the space in which it is embedded, not by the values of f in any way. $\endgroup$ May 16 '21 at 8:42
  • $\begingroup$ @AmitHochman I just added a clarifying edit at the end to better show what I'm thinking. Please let me know what I'm misunderstanding. Maybe my intuition that strict inequalities --> interior point is wrong in a general setting? $\endgroup$
    – nkyraf33
    May 16 '21 at 15:58
  • $\begingroup$ Are you sure that's an extra condition and not just the authors explaining the condition? (Also, Wikipedia most likely just copied from that standard reference.) $\endgroup$ May 16 '21 at 21:22
  • $\begingroup$ To be clear: the relint condition is the general condition that holds in for an arbitrary constraint $x \in \mathcal{D}$, even in Banach spaces. For the special case that the constraint consists of finitely many scalar inequalities, (5.26) is indeed sufficient. $\endgroup$ May 16 '21 at 21:25
  • $\begingroup$ Also, recall the definition of $\mathcal{D}$, which includes the equality constraints $h_i$ (which is why the relint is important) as well as the objective function $f_0$! $\endgroup$ May 16 '21 at 21:27

Your Answer

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

Browse other questions tagged or ask your own question.