Convex Optimization · Problem 2.34

Convex functions — Boyd & Vandenberghe

Mathematics — Optimization · lexicographic-cone-and-ordering

Problem

The lexicographic cone and ordering. The lexicographic cone is defined as

K_{\mathrm{lex}} = \{0\} \cup \{x \in \mathbf{R}^n \mid x_1 = \cdots = x_k = 0,\, x_{k+1} > 0, \text{ for some } k,\, 0 \leq k < n\},

i.e., all vectors whose first nonzero coefficient (if any) is positive. ((a)) Verify that

K_{\mathrm{lex}}

is a cone, but not a proper cone. ((b)) We define the lexicographic ordering on

\mathbf{R}^n

as follows:

x \leq_{\mathrm{lex}} y

if and only if

y - x \in K_{\mathrm{lex}}

. (Since

K_{\mathrm{lex}}

is not a proper cone, the lexicographic ordering is not a generalized inequality.) Show that the lexicographic ordering is a linear ordering: for any

x, y \in \mathbf{R}^n

, either

x \leq_{\mathrm{lex}} y

y \leq_{\mathrm{lex}} x

. Therefore any set of vectors can be sorted with respect to the lexicographic cone, which yields the familiar sorting used in dictionaries. ((c)) Find

K^*_{\mathrm{lex}}

Browse the problem library