line

All points of the form \(x = \theta x_{1} + \qty(1-\theta) x_{2}\), with \(\theta \in \mathbb{R}\) is a “line through \(x_1\), \(x_2\)”.

affine set

For set \(G\), for all two points \(x_1, x_2 \in G\), all points lying on the line \(x_1, x_2 \in G\). For instance, the solution set of a set of linear equations \(\qty {x \mid A x = b}\).

convex set

convex set,

line segment

all points form \(x = \theta x_{1} + \qty(1-\theta)x_{2}\), with \(0 \leq \theta \leq 1\).

convex combination

A convex combination of points \(x_1 … x_{k}\) has

\begin{equation} x = \theta_{1} x_1 + \theta_{2} x_{2} + \dots \theta_{k} x_{k} \end{equation}

with \(\sum_{j}^{} \theta_{j} = 1\), \(\forall \theta_{j} \geq 0\).

convex hull

set of all convex combination of points in \(S\)

convex cone

Conic combination any combination of the form

\begin{equation} x = \theta_{1} x_{1} + \theta_{2} x_{2} \end{equation}

with \(\forall \theta_{j} \geq 0\).

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

properties of convex cone

• closed under non-negative scaling
• closed under addition

hyperplane

Set of the form:

\begin{equation} \qty {x \mid a^{T} x = b}, a \neq 0 \end{equation}

“the solution set f a single linear equation”. If \(b\) were \(0\), we can think about it as “all the points that are orthogonal to \(a\).

• affine set
• convex set

halfspace

\begin{equation} \qty {x \mid a^{T}x \leq b}, a \neq 0 \end{equation}

• convex set

Euclidian ball

Set of points with \(L_2\) norm smaller than \(r\):

\begin{equation} B\qty(x_{c}, r) = \qty {x \mid \norm{x -x_{c}}_{2} \leq r} = \qty {x_{c} + ru \mid \norm{u}_{2} \leq 1} \end{equation}

ellipsoid

For Symmetric PSD \(P \in S_{++}^{n}\):

\begin{equation} \qty {x \mid \qty(x- x_{c})^{T} P^{-1} \qty(x - x_{c}) \leq 1} \end{equation}

also written as:

\begin{equation} \qty {x_{c} + A u \mid \norm{u}_{2} \leq 1} \end{equation}

for nonsigular \(A\).

norm

properties of the norm

norm ball

\begin{equation} \qty {x \mid \norm{x - x_{c}} \leq r} \end{equation}

norm cone

\begin{equation} \qty {\qty(x,t) \mid \norm{x} \leq t} \end{equation}

polyhedron

\begin{equation} \qty {x \mid Ax \preceq b, Cx = d} \end{equation}

where \(\preceq\) is “elementwise less-than”. You can think of each \(a_{j}^{T}\) as a row of \(A\).

PSD cones

symmetric matrices

positive semidefinite matrices (geometry)

\begin{equation} S_{+}^{n} = \qty {X \in S^{n} \mid X \succeq 0} \end{equation}

this is a convex cone.

positive definite (symmetric) metricies (geometry)

\begin{equation} S^{n}_{++} = \qty {X \in S^{n} \mid X \succ 0} \end{equation}

proper cone

a convex cone \(K \subseteq R^{n}\) is a proper cone if:

• \(K\) is closed
• \(K\) is solid (non-empty interior)
• \(K\) is pointed (contains no line) — \(v\) and \(-v\) can’t both have a line
• \(K\) is non-trivial (not empty)

generalized inequality

For proper cone \(K\):

\begin{equation} x \preceq_{K} y \Leftrightarrow y - x \in K \end{equation}

\begin{equation} x \prec_{k} y \Leftrightarrow y - x \in \text{interior} K \end{equation}

Triangle inequality holds:

\begin{equation} x \preceq_{k} y, u \preceq_{k} v \implies x+u \preceq_{k} y + v \end{equation}

This is not well ordered.