3
$\begingroup$

I would like to understand what is known as Slater's condition for the closedness of the linear image of a closed, convex cone.

Let $V=\mathbb{R}^n$ and $W=\mathbb{R}^m$ (i.e. finite dimensional real inner product spaces), let $A:V\rightarrow W$ be a linear map, and let $K\subseteq V$ be a closed convex cone.

First some notation:

  • The dual cone of $K$ is the set $$ K^* = \{v\in V \,:\, \langle v,x\rangle \geq 0\}. $$
  • The adjoint map of $A$ is the unique linear map $A^*:W\rightarrow V$ such that $\langle A x,y\rangle = \langle x, A^* y\rangle$ for all $x,y$.
  • The interior of $K^*$ is denoted $\mathrm{int}(K^*)$ and can be defined as follows: For $v\in\mathrm{int}(K^*)$ and $x\in K$, if $\langle v,x\rangle = 0$ then $x=0$.
  • The image of $K$ under $A$ will be denoted $$ A(K) = \{Ax \,:\, x\in K\}. $$

What I would like to prove is the following:

Theorem. Suppose there exists a $y\in W$ such that $A^*y\in\mathrm{int}(K^*)$. Then $A(K)$ is closed.

Here is my attempt to prove:

Let $\{y_i\}$ be a Cauchy sequence in $A(K)$, and let $\overline{y}\in W$ such that $y_i\rightarrow \overline{y}$. (We want to show that $\overline{y}\in A(K)$ to show that $A(K)$ is closed.) Since $y_i\in A(K)$, we can find $x_i\in K$ such that $Ax_i=y_i$. Since $\{y_i\}$ is Cauchy, it is bounded so there exists a $c\geq 0$ such that $$ \langle A^*y,x_i\rangle = \langle y,y_i\rangle \leq c $$ for all $i$. We can assume without loss of generality that each $y_i\neq 0$, then each $x_i$ also satisfies $$ 0<\langle A^*y,x_i\rangle $$ since $x_i\in K$ and we assume $A^*y\in\mathrm{int}(K^*)$. Thus, each $x_i$ satisfies $$ 0<\langle A^*y,x_i\rangle \leq c. $$ Somehow this implies that the sequence $\{x_i\}$ must be bounded? This is what I do not understand and I might be missing something.

Finally, since $\{x_i\}$ is a bounded sequence in a closed $K$, it has an accumulation point $x$ which satisfies $Ax=\overline{y}$.

All that I do not understand is how to show that $\{x_i\}$ is bounded. Any help is appreciated.

(Note: The existence of $y$ such that $A^*y\in\mathrm{int}(K^*)$ is known as Slater's condition).

$\endgroup$
7
  • $\begingroup$ Essentially, what I want is to prove Proposition 1.3 on page 7 of these notes (which is given there as an exercise). $\endgroup$ Jun 13, 2017 at 16:48
  • $\begingroup$ Do you know how this connects to what is normally called Slater's​ condition in convex optimization? $\endgroup$
    – littleO
    Jun 13, 2017 at 19:40
  • $\begingroup$ Can this result be used to prove that $\{Ax \mid x\geq 0\}$ is closed? (Some proofs of this fact are given here:math.stackexchange.com/questions/1831401/… ) $\endgroup$
    – littleO
    Jun 13, 2017 at 19:43
  • $\begingroup$ Something you call here relative interior is not actually relative interior of $K^*$. They don't coincide! See en.wikipedia.org/wiki/Relative_interior for definition of relint $\endgroup$
    – Red shoes
    Jun 13, 2017 at 20:58
  • $\begingroup$ @Ashkan. You're right. I suppose I really just mean the true interior, not the relative interior. The interior of the dual cone does in fact coincide with the set I describe. $\endgroup$ Jun 14, 2017 at 15:02

1 Answer 1

1
$\begingroup$

I've figured it out. It appears to be a fairly standard argument in duality theorems for conic programming.


Suppose instead that $\{x_i\}$ is unbounded. We will derive a contradiction.

Define the sequence $\tilde x_i = \frac{x_i}{\lVert x_i\rVert}$, which is in $K$. It is clearly bounded so it converges (or at least has a convergent subsequence) $\tilde x_i \rightarrow\tilde x $ to some $\tilde x\in K$ and $\tilde x \neq 0$. Hence $$ 0<\langle A^*y, \tilde x_i \rangle\leq \frac{1}{\lVert x_i\rVert}c $$
for all $\tilde x_i$. Since $\{x_i\}$ is unbounded, it follows that $\langle A^*y, \tilde x_i \rangle\rightarrow 0$. Hence $$ \langle A^*y, \tilde x \rangle = \lim_{i\rightarrow\infty}\langle A^*y, \tilde x_i \rangle =0. $$ But $A^*y\in\mathrm{int}(K^*)$ implies that $\tilde x=0$, a contradiction.

$\endgroup$
2
  • $\begingroup$ I can see only how to prove what you said when we are actually looking for $\text{int}(K^{*})$, but not $\text{relint} (K*)$. See PROPOSITION 1.1.4. of the book global.oup.com/academic/product/… $\endgroup$ Sep 14, 2023 at 10:49
  • $\begingroup$ His answer does not hold when $\text{int} (K^{*})$ is substituted by $\text{relint} (K^*)$. For the relint version, I recommend following the article "On the closedness of the linear image of a closed convex cone." Directly finding yourself proof is not something one should pursue due to its difficulty. Instead, the article I recommended would enlighten your ideas even more than finding a proof by yourself. Sometimes, we need to stand on the shoulders of giants $\endgroup$ Sep 19, 2023 at 9:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .