Convex Optimization · Problem 2.14

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · expanded-and-restricted-sets

Problem

Expanded and restricted sets. Let S⊆RnS \subseteq \mathbf{R}^n, and let ∥⋅∥\|\cdot\| be a norm on Rn\mathbf{R}^n. ((a)) For a≥0a \geq 0 we define SaS_a as {x∣dist(x,S)≤a}\{x \mid \mathbf{dist}(x, S) \leq a\}, where dist(x,S)=inf⁡y∈S∥x−y∥\mathbf{dist}(x, S) = \inf_{y \in S} \|x - y\|. We refer to SaS_a as SS expanded or extended by aa. Show that if SS is convex, then SaS_a is convex. ((b)) For a≥0a \geq 0 we define S−a={x∣B(x,a)⊆S}S_{-a} = \{x \mid B(x, a) \subseteq S\}, where B(x,a)B(x, a) is the ball (in the norm ∥⋅∥\|\cdot\|), centered at xx, with radius aa. We refer to S−aS_{-a} as SS shrunk or restricted by aa, since S−aS_{-a} consists of all points that are at least a distance aa from Rn∖S\mathbf{R}^n \setminus S. Show that if SS is convex, then S−aS_{-a} is convex.

Browse the problem library