# Rewriting a set with two parameters as a polyhedron

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?

• 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 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?
• 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 3 '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 3 '17 at 18:51