how to prove that, given a set defined as
$S_{k}$ = {y: y = Ax, $\|x\|_{\infty}\leq$ 1}
its convex hull conv($S_{k}$) has its vertices defined by those vectors $x$ such that $\|x\|_{\infty}$ = 1. How to do it?
Thank you for your help!
Asked
Active
Viewed 341 times
2
-
Except I'm missing something in your statements, the claim is false (is there a miswrite somewhere ?). Take for example $A = 2I$. Then $S$ can't have a vertex with $|x|_\infty = 1$. BTW, note that $\mathrm{conv}(S) = S$ because $S$ is convex, being the linear image of a convex set. – dohmatob Nov 13 '15 at 22:18
-
@dohmatob, why isn't $y=2x$ for any $|x|_\infty=1$ a vertex in that case? – Michael Grant Nov 13 '15 at 23:28
-
Oops! I commented @MichaelGrant comment but, i can't see it (my response) here anymore. Anyways, ok, yes I misread buzz's problem. MichaelGrant's comment / question, clarified what i was missing in the original question. Thanks to both of you, and ignore my first remark. – dohmatob Nov 14 '15 at 09:50
-
@buzz: I propose you reformulate your problem to precisely reflect the fact that your claim is that $vertices({Ax| |x|\infty \le 1}) \subseteq {Ax | |x|\infty = 1}$. There is nothing more confusing than an imprecisely stated problem :) – dohmatob Nov 14 '15 at 09:58
-
@dohmatob: yes, I agree with you. In fact in this post I've not been precise, but I will in my dissertation :) thank you for your help – buzz Nov 14 '15 at 09:59
-
OK, in that case, check my answer below, wherein we show that $vertices({Ax| |x|\infty \le 1}) \subseteq {Ax | |x|\infty = 1}$ indeed. – dohmatob Nov 14 '15 at 10:03
1 Answers
2
So, the set under study is a linear image $S := A\mathbb{B}_\infty$, of $\mathbb{B}_\infty := \{x | \|x\|_\infty \le 1\}$, the unit ball for the $\ell_\infty$-norm . We're interested in the vertices of $S$, namely $V(S)$. Define \begin{equation}V_0 := \{Ax | \|x\|_\infty = 1\}. \end{equation} The aim is to show that $V(S) \subseteq V_0$.
Suppose on the contrary that $S$ has a vertex $ v = Ax$, with $\|x\|_\infty < 1$. We'll produce a contradiction. Now, by definition of $v$ as a vertex of $S$, there exists a half-space $H^+ := \{y|\langle w, y\rangle \le \lambda\}$ which contains $S$ and such that the intersection of its boundary $\partial H^+ = \{y | \langle w, y\rangle = \lambda\}$ with $S$ is the singleton $\{v\}$. Now, by the Cauchy-Schwarz inequality, \begin{equation} Ax \in \partial H^+ \land \|x\|_\infty < 1 \implies \lambda = \langle w, Ax\rangle = \langle A^*w, x\rangle \le \|A^*w\|_1\|x\|_\infty < \|A^*w\|_1. \end{equation} Finally, invoking the above inequality, the compacity of $\mathbb{B}_\infty$, and using the fact that $H^+ \supseteq S$, one has $\langle w, Az\rangle \le \lambda < \|A^*w\|_1 $ for all $z \in \mathbb{B}_\infty$, and so $\max_{z \in \mathbb{B}_\infty} \langle A^*w, z\rangle < \|A^*w\|_1$, i.e $\|A^*w\|_1 < \|A^*w\|_1$, a contradiction.
dohmatob
- 9,535
-
Thank you for your help :) just one question: doesn't your proof prove that V(S) and $V_{0}$ coincide (which is our aim)? In fact you show that there is no possibility to have a vertex with $|x|_{\infty}$ < 1 – buzz Nov 14 '15 at 09:56
-
Yeah, but this doesn't in itself prove that "once we have $|x|_\infty = 1$ then $Ax$ must be a vertex of $S$". The other direction of the inclusion is a whole different business :). Please consider rewriting your (original) question as precisely and formally as you can, including all the details. – dohmatob Nov 14 '15 at 10:07
-
I think that your proof is what I was searching for. Just one thing: it is not given for granted that all vectors $x$ with $|x|{\infty}$ = 1 will define a vertex of S, but no $x$ such that $|x|{\infty}$ < 1 can. Again, thank you! – buzz Nov 14 '15 at 10:15
-
Yes, you get it: the last part of the 2nd sentence in your statement is precisely what has been proved, but nothing more :). – dohmatob Nov 14 '15 at 10:18
-