# Notes on Convex Optimization (1): Convex Sets

| Comments

### 1. Affine and Convex Sets

Suppose $x_1\ne x_2$ are two points in $\mathbb{R}^n$.

#### 1.1 Affine sets

line through $x_1$, $x_2$: all points

affine set: contains the line through any two distinct points in the set

#### 1.2 Convex sets

line segment between $x_1$ and $x_2$: all points

with $0\leq\theta\leq1$

convex set: contains line segment between any two points in the set

convex combination of $x_1,\dots,x_k$: any point $x$ of the form

with $\theta_1+\dots+\theta_k=1,\theta_i \geq 0$

convex hull of a set $C$, denoted $\mathbf{conv}\ C$: set of all convex combinations of points in $C$

#### 1.3 Cones

conic combination of $x_1$ and $x_2$: any point of the form

with $\theta_1 \geq 0, \theta_2 \geq 0$

convex cone: set that contains all conic combinations of points in the set

### 2. Some Important Examples

#### 2.1 Hyperplanes and halfspaces

hyperplane: set of the form {$x\mid a^Tx=b$}$(a\ne0)$

halfspace: set of the form {$x\mid a^Tx\leq b$}$(a\ne0)$

• $a$ is the normal vector
• hyperplanes are affine and convex; halfspaces are convex

#### 2.2 Euclidean balls and ellipsoids

(Euclidean) ball with center $x_c$ and radius $r$:

ellipsoid: set of the form

with $P\in \mathbf{S}^n_{++}$ (i.e., P symmetric positive definite)

another representation: {$x_c+Au\mid \lVert u\rVert_2\le1$} with $A$ square and nonsingular

• Euclidean balls and ellipsoids are all convex.

#### 2.3 Norm balls and norm cones

norm: a funtion $\lVert \centerdot \rVert$ that satisfies

• $\lVert x \rVert \geq 0$; $\lVert x \rVert=0$ if and only if $x=0$
• $\lVert tx \rVert = \lvert t \rvert \lVert x \rVert$ for $t\in \mathbb{R}$
• $\lVert x+y\rVert \leq \lVert x \rVert+\lVert y \rVert$

norm ball with center $x_c$ and radius $r: \{x \mid \lVert x-x_c \rVert \leq r\}$

norm cone: $\{(x,t) \mid \lVert x \rVert \leq t\}$

• norm balls and cones are convex
• norm cores (as the name suggest) are convex cones

#### 2.4 Polyhedra

polyhedra: solution set of finitely many linear inequalities and equalities

($A\in \mathbb{R}^{m\times n}$, $C\in\mathbb{R}^{p\times n}$, $\preceq$ is componentwise inequality)

• polyhedron is intersection of finite number of halfspaces and hyperplances

#### 2.5 The positive semidefinite cone

positive semidefinite cone:

• $\mathbf{S}^n$ is set of symmetric $n\times n$ matrices
• $\mathbf{S}^n_+=\{X\in\mathbf{S}^n\mid X\succeq0\}$: positive semidefinite $n\times n$ matrices $X\in\mathbf{S}^n_+ \iff z^TXz \geq 0\ \mathrm{for\ all\ }z$ $\mathbf{S}^n_+$ is a convex cone
• $\mathbf{S}^n_{++}=\{X\in\mathbf{S}^n\mid X\succ0\}$: positive definite $n\times n$ matrices

### 3. Operations that preserve convexity

intersection: the interction of (any number of) convex sets is convex

affine function: suppose $f: \mathbb{R}^n \rightarrow \mathbb{R}^m$ is affine ($f(x)=Ax+b$ with $A\in\mathbb{R}^{m\times n}, b\in\mathbb{R}^m$)

• the image of a convex set under $f$ is convex
• the inverse image $f^{-1}(C)$ of a convex set under $f$ is convex

perspective function $P: \mathbb{R}^{n+1} \rightarrow \mathbb{R}^n$:

images and inverse images of convex sets under perspective are convex

linear-fractional function $f:\mathbb{R}^n \rightarrow \mathbb{R}^m$:

images and inverse images of convex sets under linear-fractional functions are convex

### 4. Generalized Inequalities

#### 4.1 Proper cones and generalized inequalities

a convex cone $K\subseteq\mathbb{R}^n$ is a proper cone if

• $K$ is closed (contains its boundary)
• $K$ is solid (has nonempty interior)
• $K$ is pointed (contains no line)

generalized inequality defined by a proper cone $K$:

#### 4.2 Minimum and minimal elements

$x\in S$ is the minimum element of $S$ with respect to $\preceq_K$ if

$x\in S$ is a minimal element of $S$ with respect to $\preceq_K$ if

### 5. Separating and Supporting Hyperplanes

separating hyperplane theorem: if $C$ and $D$ are disjoint convex sets, then there exists $a\ne0$, $b$ such that

supporting hyperplane to set $C$ at boundary point $x_0$:

where $a\ne0$ and $a^Tx\le a^Tx_0$ for all $x\in C$

supporting hyperplance theorem: if $C$ is convex, then there exists a supporting hyperplane at every boundary point of $C$

### 6. Dual Cones and Generalized Inequalities

#### 6.1 Dual cones

dual cone of a cone $K$:

Dual cons satisfy several properties, such as:

• $K^*$ is closed and convex
• $K_1 \subseteq K_2$ imples $K_2^* \subseteq K_1^*$
• $K^{**}$ is the closure of the convex hull of $K$ (Hence if $K$ is convex and closed, $K^{**}=K$)

Thsese properties show that if $K$ is a proper cone, then so is its dual $K^{*}$, and moreover, that $K^{**}=K$

#### 6.2 Dual generalized inequalities

dual cones of proper cones are proper, hence define generalized inequalities:

Some import properties relating a generalized inequality and its dual are:

• $x\preceq_K y$ iff $\lambda^Tx \le \lambda^Ty$ for all $\lambda \succeq_{K^{*}} 0$
• $x\prec_K y$ iff $\lambda^Tx < \lambda^Ty$ for all $\lambda \succ_{K^{*}} 0, \lambda\ne0$

Since $K=K^{**}$, the dual generalized inequality associated with $\preceq_{K^{*}}$ is $\preceq_K$, so these properties hold if the generalized inequality and its dual are swapped

#### 6.3 Minimum and minimal elements via dual inequalities

dual characterization of minimum element w.r.t. $\preceq_K$: $X$ is minimum element of $S$ iff for all $\lambda \succ_{K^*}0$, $x$ is the unique minimizer of $\lambda^Tz$ over $z\in S$

dual characterization of minimal element w.r.t. $\preceq_K$:

• if $x$ minimizes $\lambda^Tz$ 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^Tz$ over $z \in S$