Convex Optimization · Problem 2.25

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · inner-outer-polyhedral-approximations

Problem

Inner and outer polyhedral approximations. Let

C \subseteq \mathbf{R}^n

be a closed convex set, and suppose that

x_1, \ldots, x_K

are on the boundary of

C

. Suppose that for each

i

a_i^T(x - x_i) = 0

defines a supporting hyperplane for

C

x_i

, i.e.,

C \subseteq \{x \mid a_i^T(x - x_i) \leq 0\}

. Consider the two polyhedra

P_{\text{inner}} = \mathbf{conv}\{x_1, \ldots, x_K\}, \qquad P_{\text{outer}} = \{x \mid a_i^T(x - x_i) \leq 0,\, i = 1, \ldots, K\}.

Show that

P_{\text{inner}} \subseteq C \subseteq P_{\text{outer}}

. Draw a picture illustrating this.