Notes on convex sets

Cones

Definition of a cone is quite general:

A set \(C\) is a cone if for every \(x\in C\) and \(\theta\ge 0\), we have \(\theta x \in C\).  (Note that, a subspace is a cone since all (non-negative) combination of points in the subspace belongs to the subspace)

A set \(C\) is a convex cone if it is convex and a cone.

A proper cone on the other hand is more strict.

A cone \(K \subseteq \mathbb{R}^n\) is a proper cone if it satisfies the following

• \(K\) is convex
• \(K\) is closed
• \(K\) is solid, which means it has nonempty interior.
• \(K\) is pointed, which means that it contains no line.

Dual cones and generalized inequalities

Dual cones of a cone \(K\):
\[ K^* = \{y\; |\; y^T x\ge 0 \text{ for all } x \in K \} \]

Dual cones of proper cones are proper, so a dual cone defines generalize inequalities in the dual domain

\[ y \succeq_{K^*} 0 \quad \Longleftrightarrow \quad y^T x\ge 0 \text{ for all } x\succeq_K 0  \]

Characterization of minimum and minimal elements via dual inequalities

minimum element w.r.t. \( \preceq_K\)

Definition: \(x\) is minimum element of \(S\) iff for all \(\lambda \succeq_{K^*} 0\), \(x\) is the unique minimizer of \(\lambda^T z\) over \(S\)

minimal element w.r.t. \( \preceq_K \)

Definitions:

• if \(x\) minimizes \(\lambda^T z\) over \(S\) for some \(\lambda \succ_{K^*} 0\), then \(x\) is minimal
• if \(x\) is a minimal element of a convex set \(S\), then there exists a nonzero \(\lambda \succeq_{K^*} 0\) such that \(x\) minimizes \(\lambda^T z\) over \(S\)