0

Show that the set $$ S := \left\{ (x_1,x_2) : x_1^2+x_2^2 < 1 \right\} $$ does not have any extreme point.

For the sake of contradiction, assume $z$ is an extreme point in $S$, so for some $A,B\in S$ and $\mu \in (0,1)$ if $z= \mu A+(1-\mu)B$ then this implies that $A=B$,on the other hand:

$$\color{blue}{\mu^2(a_1^2+a_2^2)+(1-\mu)^2(b_1^2+b_2^2)+2\mu(1-\mu)(a_1b_1+a_2b_2)}$$$$=z_1^2+z_2^2<1$$

And $$2\mu(1-\mu)(a_1b_1+a_2b_2)\le\color{blue}{\mu^2(a_1^2+a_2^2)+(1-\mu)^2(b_1^2+b_2^2)+2\mu(1-\mu)(a_1b_1+a_2b_2)}$$

Which implies that $a_1b_1+a_2b_2<\frac{1}{2\mu(1-\mu)}\tag{I}$

On the other hand from $A,B \in S$ we have that $$(a_1+b_1)^2+(a_2+b_2)^2-2(a_1b_1+a_2b_2)<2\tag{II}$$

Combining $(\text{I})$ and $(\text{II})$ shows that $$$$ $$(a_1+b_1)^2+(a_2+b_2)^2<2+\frac{1}{\mu(1-\mu)}$$

From there I was going to show that $(a_1+b_1)^2+(a_2+b_2)^2 \le 0$

and so $a_1 \ne b_1$ and $a_2 \ne b_2$ which shows that $A \ne B $ and that contradicts the assumption,but as it's clear $2+\frac{1}{\mu(1-\mu)}\le 0$ does not have any solution in $(0,1)$, so how to prove the cliam?

Rodrigo de Azevedo
  • 1
masaheb
  • 918
  • 6
  • 16
  • I did not read your proof but it looks far too complicated. It should suffice to use that $S$ is an open set. – Martin R Nov 04 '21 at 10:11
  • @ Martin R, The question itself comes from convex optimization and so we require to prove the claim without using the concept of open/closed sets. – masaheb Nov 04 '21 at 10:14

1 Answers1

1

If $z=(x_1,x_2) \in S$ then $|x_1| <\sqrt {1-x_2^{2}}$. Let $0 <\epsilon < \sqrt {1-x_2^{2}}-|x_1|$ We can write $z=\frac {(x_1+\epsilon,x_2)+(x_1-\epsilon,x_2)} 2$ and I will let you verify that $(x_1 \pm\epsilon,x_2) \in S$. So $z$ is not an extreme point.

Kavi Rama Murthy
  • 311,013
  • Where does $x$ come from? How did you come up with such epsilon? – masaheb Nov 04 '21 at 13:50
  • There was a typo. It was $z$ instead of $x$. If you define $z$ this way you can work backwards and see how small $\epsilon$ should be so that $(x_1\pm \epsilon, x_2)$ lies inside $S$. @masaheb – Kavi Rama Murthy Nov 04 '21 at 23:13
  • What definition of extreme point did you use?Why $(x_1 \pm\epsilon,x_2) \in S$ implies that $z$ is not an extreme point? – masaheb Nov 05 '21 at 09:19
  • I am writing $z$ as a convex combination of two points of $S$. The simplest convex combination of two points $u,v$ is $\frac {u+v} 2$ right? @masaheb – Kavi Rama Murthy Nov 05 '21 at 09:24