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?

  • 2
    $\begingroup$ 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) $\endgroup$ – Jean Marie Dec 3 '17 at 18:16

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?

  • $\begingroup$ 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? $\endgroup$ – Aleksey Bilogur Dec 3 '17 at 18:24
  • $\begingroup$ 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\}$ $\endgroup$ – Aleksey Bilogur Dec 3 '17 at 18:51

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.