Convex Optimization · Problem 2.8

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · polyhedra

Problem

Which of the following sets

S

are polyhedra? If possible, express

S

in the form

S = \{x \mid Ax \preceq b,\, Fx = g\}

. ((a))

S = \{y_1 a_1 + y_2 a_2 \mid -1 \leq y_1 \leq 1,\, -1 \leq y_2 \leq 1\}

, where

a_1, a_2 \in \mathbf{R}^n

. ((b))

S = \{x \in \mathbf{R}^n \mid x \succeq 0,\, \mathbf{1}^T x = 1,\, \sum_{i=1}^n x_i a_i = b_1,\, \sum_{i=1}^n x_i a_i^2 = b_2\}

, where

a_1, \ldots, a_n \in \mathbf{R}

and

b_1, b_2 \in \mathbf{R}

. ((c))

S = \{x \in \mathbf{R}^n \mid x \succeq 0,\, x^T y \leq 1 \text{ for all } y \text{ with } \|y\|_2 = 1\}

. ((d))

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