1

According to "Convex Optimization" by Boyd and Vandenberghe, a polyhedron is defined as the solution set to a finite number of linear equalities and inequalities:

$$P = \{x \: | \: a_j^T \leq b_j, j = 1, \ldots, m, c_j^T x = d_j, j = 1, \ldots, p\}$$

Geometrically, this corresponds with finitely many intersecting hyperplanes and halfspaces.

Exercise 2.8(d) then goes on to ask whether or not the following set is a polyhedron:

$$S = \{ x \in \mathbb{R}^n \: | \: x \succeq 0, x^T y \leq 1 \text{ for all } y \text{ with } \sum_{i=1}^n |y_i| = 1 \}$$

(where $\succeq$ indicates component-wise vector inequality)

I believe that the answer is Yes.

$x \succeq 0$ can easily be written as finitely many equations explicitly checking each component.

I believe the condition $\{ y | \sum |y_i| = 1\}$ means that $y$ has to be an edge on a unit cube centered around 0 and rotated 45 degrees (e.g. in two dimensions, a square with endpoints $\{ (0, 1), (0, -1), (1, 0), (-1, 0)\}$). This can also be expressed with finitely many hyperplanes.

However, I can't figure out how to express the $x^T y \leq 1$ condition as a linear inequality.

Is my answer on the right track, or totally wrong? How can this be done?

Aleksey Bilogur
  • 245
  • 3
  • 9
  • 2
    Take care, dimension 2 is not a good adviser : ${ y | \sum |y_i| = 1}$ in $\mathbb{R^3}$ is an octahedron, not a cube (it is the dual of a cube) – Jean Marie Dec 03 '17 at 18:16

1 Answers1

1

Sometimes it helps to look at the question in more specificity. In this case, the easiest way to do that is probably to take $n=2$.

You say 'this corresponds with finitely many intersecting hyperplanes and halfspaces'. How many $\vec{y}=\langle y_1,y_2\rangle $ are there with $\left|y_1\right|+\left|y_2\right|=1$? Pick some particular subset of those (for instance, you could just take the set of vectors $\vec{y}=\langle t,1-t\rangle$ for $0\leq t\leq 1$) and for each one of these, look at the set $\mathbb{X}_t$ of all $\vec{x}$ that satisfy the constraint. What does the intersection (over $t$) of these sets $\mathbb{X}_t$ look like?

Steven Stadnicki
  • 51,746
  • Parameterization with $t$ is helpful! $\mathbb{X}{t=0} = {x | x_2 \leq 1}$, and $X{t=1} = { x | x_1 \leq 1}$. The intersection across all $t$ corresponds with ${ x : | : \alpha x_1 + \beta x_2 \leq 1, \alpha + \beta = 1} = { x : | : x_1 \leq 1, x_2 \leq 1}$. Does that seem right? – Aleksey Bilogur Dec 03 '17 at 18:24
  • By considering each side of the $y$ square separately in the $\mathbb{R}^2$ case I ultimately arrived at ${x : | : -1 \leq x_1 \leq 1, -1 \leq x_2 \leq 1}$ – Aleksey Bilogur Dec 03 '17 at 18:51