6
$\begingroup$

Given following set $S = \{ \alpha \in \mathbf{R}^3 \mid \alpha _1 + \alpha _2e^{-t} + \alpha _3e^{-2t} \leq 1.1 \; \mbox{for}\; t \geq 1\}$. I more or less can prove and understand why it is not affine and why it is convex, but I can't prove why it is not polyhedron? This is because it is not linear inequality?

Thanks in advance.

Update: Don't quite understand why this question should be closed, so additional details: I take edx course provided by Stanford, authored by Stephen Boyd, convex optimization. I did this question wrong and because of lack of explanation I decided to ask here. I have hard times to prove that set $S$ is not polyhedron.

$\endgroup$
  • 2
    $\begingroup$ Does "for" in the definition mean "for all" or "for some"? - I suppose "fo all". For each $t$, the inequakity defines a closed half-space, hence $S$ is the intersection of closed half-spaces, as is required for a polyhedron. However, we haev infinitely many half-spaces here. You need to show that finitely many (of these or others) don't suffice $\endgroup$ – Hagen von Eitzen Sep 14 at 1:06
  • 2
    $\begingroup$ What is the rush to close?????? This is not an entirely trivial problem. $\endgroup$ – copper.hat Sep 14 at 21:09
  • 1
    $\begingroup$ Note that we can write $S = \{ \alpha | (1,x,x^2)^T \alpha \le {11 \over 10}, x \in (0,1] \}$. $\endgroup$ – copper.hat Sep 14 at 21:10
  • 1
    $\begingroup$ I am not sure what you mean by that, but it has an uncountable number of extreme points so cannot be a polyhedron (or finitely by half spaces & rays). $\endgroup$ – copper.hat Sep 14 at 21:24
  • 1
    $\begingroup$ It is not that simple. It is not about linearity, I don't know where you are pulling that from. You can create all sorts of odd descriptions of a polyhedron, that does not stop it from being a polyhedron. One way is to show, as I mentioned above, that it has an infinite number of extreme points. $\endgroup$ – copper.hat Sep 14 at 21:31
3
$\begingroup$

Here is a very tedious answer. I imagine there is a much slicker solution, but it escapes me.

Note that we can write $S = \{ x| (1,t,t^2)^T x\le {11 \over 10}, t \in (0,1] \}$. Since $S$ is the intersection of closed halfplanes it is convex and closed.

Let $S_0 = \{ x \in S | x_1 = 0 \}$ and note that if $S$ was polyhedral then $S_0$ would be too. Hence it suffices to show that $S_0$ is not polyhedral.

Just to reduce noise (I am switching use of $x$ here), let $S_0' = \{ (x,y)| tx+t^2 y \le 1.1, t \in (0,1]\} $.

Note that if $(x,y) \in S_0'$ then $(x-h,y) \in S_0'$ for all $h \ge 0$. Furthermore there is some $l>0$ such that $(x+l,y) \notin S_0'$. In addition, for any $y$ there is some $x$ such that $(x,y) \in S_0'$. Hence we can characterise $S_o'$ by computing $f(y) = \max_{(x,y) \in S_0'} x$ (the $\max$ exists because $s_0'$ is closed) and write $S_0' = \{(x,y) | x \le f(y) \}$.

We can write $tx+t^2y \le 1.1$ as $x \le {1.1 \over t} - ty$ and so we see that $f(y) = \inf_{t \in (0,1]} ({1.1 \over t}-t y)$.

If $y \ge 0$ then $t \mapsto {1.1 \over t}-t y$ is decreasing and so $f(y) = 1.1-y$.

If $y < 0$ then $t \mapsto {1.1 \over t}-t y$ is unimodal on $(0,\infty)$ and has a unique $\min$ in $t^* = \sqrt{1.1 \over -y}$.

In particular, for $y \ge - 1.1$, $f(y) = 1.1-y$ and for $y < -1.1$ we have $f(y) = 2 \sqrt{-1.1y}$.

It is straightforward to show from this that $S_0'$ is not polyhedral.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

HINT:

You are dealing with a cone here ( substitute $\alpha_1 \mapsto \alpha_1 - 1.1$), and to see that it is not polyhedral, it is enough to check that its dual it not polyhedral. Now its dual is (by the duality theorem for cones) the closed convex cone generated by $(1,t, t^2)$, with $0< t \le e^{-1}$. The intersection of this cone with the horizontal plane $(1, *, *)$ is the convex hull of $(t, t^2)$, with $0\le t \le e^{-1}$, and it is enough to prove this two dimensional closed convex set is not polyhedral. two dimensional convex set

This two dimensional convex set is not polyhedral, since it has infinitely many extremal points $(t, t^2)$, for $0\le t \le e^{-1}$.

$\bf{Added:}$ It would be interesting to determine in fact the set. Skipping some details, it is related to the polar of the set $\{(t,t^2)\ | \ 0< t \le e^{-1}\}$. Recall that for a set $K\subset \mathbb{R}^2$ the polar $K^{\circ}$ (sometimes called the ${real}$ polar, is the set of pairs $(a,b)$ such that $a x + b y \le 1$ for all $(x,y) \in K$. Now, the polar of a set equals the polar of its convex hull (easy).

We will first determine the polar of $\{(t,t^2) \ | \ t \in \mathbb{R}\}$. It is also the polar of the epigraph (above the graph) of the function $t \mapsto t^2$. It turns out that its polar is the hypograph (below the graph) of the function $s \mapsto \frac{-s^2}{4}$. We can check directly that $$(t, t^2) \cdot (s, -\frac{s^2}{4}) \le 1 $$, that is $1 - s t + \frac{(s t)^2}{4}\ge 0$, with equality if $s\cdot t = 1$. Now, if we want say the polar of just a part of the graph (say from $t=0$ to $t=e^{-1}$), it will be the hypograph of a modification of the function $s\to -\frac{s^2}{4}$, where the function is substituted by is linear approximant given by the tangent at the point $(2e, e^2)$.

We illustrate with the picture of the polar of the set $\{(t,t^2) \ | 0\le t \le 1\}$. Note that the tangent to the lower parabola $(s, -\frac{s^2}{4})$ at point $(2,1)$ is perpendicular to the chord from $(0,0)$ to $(1,1)$. polar of a portion of the parabola

The polar of the portion from $(0,0$ to $(1,1)$ of the upper parabola is the purple region bounded by the lower parabola and the tangent at $(2,-1)$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Nice observation about being a translate of a cone. $\endgroup$ – copper.hat Sep 18 at 1:53
  • $\begingroup$ @copper.hat: Thank you! I added a description of the polar of the $2$-dimensional set we are dealing with. Btw, it seems that $e$ was used as a "generic" number. $\endgroup$ – orangeskid Sep 18 at 10:48
  • $\begingroup$ Nice! The pink set above is the $S_0'$ in my answer, the $f$ is the right boundary of the set. $\endgroup$ – copper.hat Sep 18 at 14:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.