Convex Optimization · Problem 2.38

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · convex-cones-from-sets

Problem

[Roc70, pages 15, 61] Convex cones constructed from sets. ((a)) The barrier cone of a set

C

is defined as the set of all vectors

y

such that

y^T x

is bounded above over

x \in C

. In other words, a nonzero vector

y

is in the barrier cone if and only if it is the normal vector of a halfspace

\{x \mid y^T x \leq \alpha\}

that contains

C

. Verify that the barrier cone is a convex cone (with no assumptions on

C

). ((b)) The recession cone (also called asymptotic cone) of a set

C

is defined as the set of all vectors

y

such that for each

x \in C

x - ty \in C

for all

t \geq 0

. Show that the recession cone of a convex set is a convex cone. Show that if

C

is nonempty, closed, and convex, then the recession cone of

C

is the dual of the barrier cone. ((c)) The normal cone of a set

C

at a boundary point

x_0

is the set of all vectors

y

such that

y^T(x - x_0) \leq 0

for all

x \in C

(i.e., the set of vectors that define a supporting hyperplane to

C

x_0

). Show that the normal cone is a convex cone (with no assumptions on

C

). Give a simple description of the normal cone of a polyhedron

\{x \mid Ax \preceq b\}

at a point in its boundary.