# Convex Optimization

## Cones and generalized inequalities

### Affine set, convex set and cone

• A set $$C$$ is affine if $$\forall x_1, x_2 \in C$$ and $$\forall \theta$$, we have $$\theta x_1 + (1-\theta) x_2 \in C$$.
• subspace: If $$C$$ is an affine set and $$x_0 \in C$$, then $$V = C - x_0 = \{x-x_0\,|x \in C\}$$ is a subspace.
• $$\mathbf{aff}\,C = \{\theta_1 x_1 + \dots + \theta_k x_k\,|\,x_i \in C, \sum_i \theta_i = 1\}$$, the affine hull of $$C$$.
• A set $$C$$ is convex if $$\forall x_1, x_2 \in C$$ and $$\forall \theta$$ satisfying $$0 \leq \theta \leq 1$$, we have $$\theta x_1 + (1 - \theta) x_2 \in C$$.
• $$\mathbf{conv}\,C = \{\theta_1 x_1 + \dots + \theta_k x_k\,|\,x_i \in C, \theta_i \geq 0, \sum_i \theta_i = 1\}$$, the convex hull of $$C$$.
• A set $$C$$ is a cone if $$\forall x \in C$$ and $$\forall \theta \geq 0$$, we have $$\theta x \in C$$.
• convex cone $$C$$: $$\forall x_1, x_2 \in C$$ and $$\forall \theta_1, \theta_2 \geq 0$$, we have $$\theta_1 x_1 + \theta_2 x_2 \in C$$.
• proper cone $$K$$:
• $$K$$ is convex.
• $$K$$ is closed.
• $$K$$ is solid, that is, having nonempty interior.
• $$K$$ is pointed, that is, $$x \in K, -x \in K \implies x = 0$$.
• conic hull of $$C$$: $$\{\theta_1 x_1 + \dots + \theta_k x_k\,|\,x_i \in C, \theta_i \geq 0\}$$

Some examples of proper cones:

• $$\mathbf{S}^n$$, the set of all positive semidefinite matrix, is a convex cone.

### Separating and supporting hyperplanes

• separating hyperplane: For nonempty convex sets $$C$$ and $$D$$ satisfying $$C \cap D=\varnothing$$, there exist $$a \neq 0$$ and $$b$$ such that $$a^T x \leq b, \, \forall x \in C$$ and $$a^T y \geq b, \, \forall y \in D$$. The hyperplane $$\{x\,|\,a^T x=b\}$$ is a separating hyperplane for $$C$$ and $$D$$.
• supporting hyperplane: For $$C \subseteq \mathbb{R}^n$$ and $$x_0 \in \mathbf{bd}\,C = \mathbf{cl}\,C \setminus \mathbf{int}\,C$$, if $$a \neq 0$$ satisfies $$a^T x \leq a^T x_0, \, \forall x \in C$$, then the hyperplane $$\{x\,|\,a^T x = a^T x_0\}$$ is a supporting hyperplane to $$C$$ at $$x_0$$. For any nonempty convex set $$C$$ and any $$x_0 \in \mathbf{bd}\,C$$, there exists a supporting hyperplane to $$C$$ at $$x_0$$.
• strict supporting hyperplane: if the hyperplane is a supporting hyperplane to $$S$$ at $$x_0$$, and intersects $$S$$ only at $$x_0$$.
• If a set is closed, has nonempty interior, and has a supporting hyperplane at every point in its boundary, then it is convex.

### Dual cone

The dual cone of a cone $$K$$ is defined as: $K^* = \{y\,|\,x^T y \geq 0, \, \forall x \in K\}$ Geometrically, $$y \in K^* \Longleftrightarrow -y$$ is the normal of a hyperplane that supports K at the origin.

Dual cone can be also defined for an arbitrary set $$S$$. For example:

• The dual cone of subspace $$V \subseteq \mathbb{R}^n$$ is its orthogonal complement $$V^\perp=\{y\,|\,v^Ty=0, \, \forall v \in V\}$$

The properties of dual cones (given a cone $$K$$):

• $$K^*$$ is closed and convex.
• $$K_1 \subseteq K_2 \implies K_2^* \subseteq K_1^*$$.
• $$K$$ has nonempty interior $$\implies K^*$$ is pointed.
• $$\mathbf{cl}\,K$$ is pointed $$\implies K^*$$ as nonempty interior.
• $$K^{**} = \mathbf{cl}\left(\mathbf{conv}\,K\right)$$. This implies if $$K$$ is a proper cone, then $$K^{**} = K$$.

where $$\mathbf{cl}\,K$$ is the closure of $$K$$, and $$\mathbf{conv}\,K$$ is the convex hull of $$K$$.

### Generalized inequality

Generalized inequality is a partial ordering defined by a proper cone $$K$$: \begin{align} x \preceq_K y &\Longleftrightarrow y - x \in K \\ x \prec_K y &\Longleftrightarrow y - x \in \mathbf{int}\,K \end{align}

where $$\mathbf{int}\,K$$ means the interior of $$K$$. When $$K=\mathbb{R}^n_+$$ ($$\mathbb{R}_+$$ is the non-negative half of $$\mathbb{R}$$), the induced $$\prec_K$$ and $$\preceq_K$$ is the ordinary elementwise inquality in $$\mathbb{R}^n$$.

$$\preceq_K$$$$\prec_K$$
if $$x \prec_K y$$, then $$x \preceq _Ky$$
additiveif $$x \preceq_K y$$ and $$u \preceq_K v$$, then $$x+u \preceq_K y+v$$if $$x \prec_K y$$ and $$u \preceq_K v$$, then $$x+u \prec_K y+v$$
transitiveif $$x\preceq_K y$$ and $$y \preceq _Kz$$, then $$x \preceq_K z$$if $$x\prec_K y$$ and $$y \prec _Kz$$, then $$x \prec_K z$$
reflective$$x \preceq_K x$$$$x \not\prec_K x$$
antisymmetricif $$x \preceq_K y$$ and $$y \preceq_K x$$, then $$x = y$$
preserved under limitsif $$x_i \preceq_K y_i$$ for $$i = 1, 2, \dots$$, $$x_i \to x$$ and $$y_i \to y$$ as $$i \to \infty$$, then $$x \preceq_K y$$
if $$x \prec_K y$$, then $$\exists u, v$$ small enough, s.t. $$x+u \prec_K y+v$$

### Dual generalized inequalities

If $$K$$ is a proper cone, then $$K^*$$ is also proper. The generalized inequality $$\preceq_{K^*}$$ is refered as the dual of the generalized inequality $$\preceq_K$$. We further have:

• $$x \preceq_K y \Longleftrightarrow \lambda^T x \leq \lambda^T y, \, \forall \lambda \succeq_{K^*} 0$$
• $$x \prec_K y \Longleftrightarrow \lambda^T x < \lambda^T y, \, \forall \lambda \succeq_{K^*} 0, \lambda \neq 0$$

### Minimum and minimal elements

• $$x \in S$$ is the minimum element of $$S$$ (w.r.t. $$\preceq_K$$) $$\Longleftrightarrow$$ any one of:
• for every $$y \in S$$, we have $$x \preceq_K y$$
• $$S \subseteq x + K$$
• $$x \in S$$ is a minimal element of $$S$$ (w.r.t. $$\preceq_K$$) $$\Longleftrightarrow$$ any one of:
• $$y \in S$$, $$y \preceq_K x$$ $$\implies$$ $$y=x$$
• $$(x-K)\cap S = \{x\}$$

### Minimum and minimal elements via dual inequalities

• $$x \in S$$ is the minimum element of $$S$$ (w.r.t. $$\preceq_K$$) $$\Longleftrightarrow$$ any one of:
• $$\forall \lambda \succ_{K^*} 0$$, $$x$$ is the unique minimizer of $$\lambda^T z,\,\forall z \in S$$.
• $$\forall \lambda \succ_{K^*} 0$$, the hyperplane $$\{y\,|\,\lambda^T(y-x)=0\}$$ is a strict supporting hyperplane to $$S$$ at $$x$$.
• The necessary and sufficient condition for $$x$$ to be minimal in $$S$$ (w.r.t $$\preceq_K$$):
• For a particular $$\lambda \succ_{K^*} 0$$, if $$x$$ minimizes $$\lambda^T z, \, \forall z \in S \implies x$$ is minimal.
• If $$S$$ is convex, then $$\forall$$ minimal element $$x$$, there $$\exists \lambda \succeq_{K^*}, \, \lambda \neq 0$$, s.t. $$x$$ minimizes $$\lambda^T z, \, \forall z \in S$$.