Convex Optimization · Problem 2.12

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · convex-sets-examples

Problem

Which of the following sets are convex? ((a)) A slab, i.e., a set of the form

\{x \in \mathbf{R}^n \mid \alpha \leq a^T x \leq \beta\}

. ((b)) A rectangle, i.e., a set of the form

\{x \in \mathbf{R}^n \mid \alpha_i \leq x_i \leq \beta_i,\, i = 1, \ldots, n\}

. A rectangle is sometimes called a hyperrectangle when

n > 2

. ((c)) A wedge, i.e.,

\{x \in \mathbf{R}^n \mid a_1^T x \leq b_1,\, a_2^T x \leq b_2\}

. ((d)) The set of points closer to a given point than a given set, i.e.,

\{x \mid \|x - x_0\|_2 \leq \|x - y\|_2 \text{ for all } y \in S\}

where

S \subseteq \mathbf{R}^n

. ((e)) The set of points closer to one set than another, i.e.,

\{x \mid \mathbf{dist}(x, S) \leq \mathbf{dist}(x, T)\},

where

S, T \subseteq \mathbf{R}^n

, and

\mathbf{dist}(x, S) = \inf\{\|x - z\|_2 \mid z \in S\}

. ((f)) [HUL93, volume 1, page 93] The set

\{x \mid x + S_2 \subseteq S_1\}

, where

S_1, S_2 \subseteq \mathbf{R}^n

with

S_1

convex. ((g)) The set of points whose distance to

a

does not exceed a fixed fraction

\theta

of the distance to

b

, i.e., the set

\{x \mid \|x - a\|_2 \leq \theta \|x - b\|_2\}

. You can assume

a \neq b

and

0 \leq \theta \leq 1