origin of this hyperplane formula 1/n

49 Views Asked by At

From a textbook question :

Express the convex set $\{x \in R^2_{+} : x_1x_2 \geq 1\}$ as an intersection of halfspaces.

The given solution states:

The set is the intersection of all supporting halfspaces at points in it's boundary, which is given by $\{x \in R_+^2 :x_1x_2 = 1\}$. The supporting hyperplane at $x = (t, 1/t)$ is given by $$\frac{x_1}{t^2} + x_2 = \frac{2}{t}$$

so we can express the set as:

$$\cap_{t>0} \{x \in R_+^2 :\frac{x_1}{t^2} + x_2 \geq \frac{2}{t}\}$$

I can't figure out why the supporting hyperplane is the formula given. The question is from Stephen Boyd's book on Convex Optimization.

1

There are 1 best solutions below

0
On BEST ANSWER

Since $\frac{x_1}{t^2} + x_2 \geq \frac{2}{t}$ defines a halfspace for all $t>0$, it is enough to show the double inclusion $$ \{x \in R^2_{+} : x_1x_2 \geq 1\}\, \substack{\phantom{|}\subseteq\\\phantom{|}\supseteq}\; \bigcap_{t>0} \{x \in R_+^2 :\frac{x_1}{t^2} + x_2 \geq \frac{2}{t}\}. $$ $\subseteq$: Take $x_1x_2\ge1$. Then observe $$ x_1t^2(\frac{x_1}{t^2} + x_2 - \frac{2}{t})=x_1^2 + x_1x_2t^2 -2x_1t \ge x_1^2 + t^2 -2x_1t = (x_1-t)^2\ge0, $$ with equality attained iff $x_1=t=1/x_2$.

$\supseteq$: Assume, toward a contradiction, that $x_1x_2<1$. Then $$ 0 \le \frac{x_1}{t^2} + x_2 - \frac{2}{t} = \frac{1}{x_1t^2}(x_1^2+x_1x_2t^2 -2x_1t) <\frac{1}{x_1t^2}(x_1^2+t^2 -2x_1t) = \frac{1}{x_1t^2}(x_1-t)^2, $$ which doesn't hold for $t=x_1$.