### 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

**norm cone**:

- 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
- : positive semidefinite $n\times n$ matrices $\mathbf{S}^n_+$ is a convex cone
- : 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$