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$