Chapter 2.2 Some Important Examples

2.2.1 Hyperplanes and halfspaces

1. A Hyperplane is defined as follows:

   \[\begin{aligned} \{x\vert a^Tx=b\}=\{x\vert a^T(x-x_0)=0\}=x_0 + a^\perp, \end{aligned}\]

   where \(x_0\) is any vector such that \(a^Tx_0=b\), and \(a^\perp=\{v\vert a^Tv=0\}\). The last term gives an geometric interpretation of hyperplane: the hyperplane consists of an offset \(x_0\), plus all vectors orthogonal to the (normal) vector \(a\).

2. One (closed) halfspace associated with the hyperplane is defined as follows:

   \[\begin{aligned} \{x\vert a^Tx \leq b\}=\{x\vert a^T(x-x_0)\leq 0\}. \end{aligned}\]

   The second term gives and geometric interpretation of halfspace: The halfspace consists of \(x_0\) plus any vector that makes an obtuse (or right) angle with the (outward normal) vector \(a\).

2.2.2 Euclidean Balls and Ellipsoids

1. Euclidean Ball with center \(x_c\) and radius \(r\) : \(B(x_c,r)=\{x\vert \|x-x_c\|\leq r\}=\{x_c+ru\vert \|u\|_2\leq 1 \}\). An Euclidean ball is a convex set.

2. Ellipsoid: \(\mathcal{E}=\{x\vert (x-x_c)^TP^{-1}(x-x_c)\leq 1\}\) or \(\mathcal{E}=\{x_c+Au\vert \|u\|_2\leq 1\}\). \(P\) is symmetric and positive definite, and \(A\) is square and non-singular. Let \(P=r^2I\), the ellipsoid becomes a ball.

2.2.3 Norm Balls and Norm Cones

1. The norm ball of center \(x_c\) and radius \(r\) associated with any norm \(\|\cdot\|\) on \(\mathbb{R}^n\) is the set \(\{x\vert \|x-x_c\|\leq r\}\)

2. The norm cone associated with any norm \(\|\cdot\|\) on \(\mathbb{R}^n\) is the set:

   \[\begin{aligned} \{(x,t)\vert \|x\|\leq t\}\subseteq \mathbb{R}^{n+1}. \end{aligned}\]

   The norm cone is a convex cone

2.2.4 Polyhedra

1. A polyhedra is defined as the solution set of a finite number of linear equalities and inequalities:

   \[\begin{aligned} \mathcal{P}&=\{x\vert a_j^Tx\leq b_j , j=1,\ldots,m, c_j^Tx=d_j,j=1,\ldots,p\},\\ \mathcal{P}&=\{x\vert Ax \preceq b, Cx=d \}, \end{aligned}\]

   where \(A=[a_1\ldots a_m]^T\) and \(C=[c_1\ldots c_p]^T\).

2. An important family of polyhedra is called simplex. Let \(v_0,\ldots,v_k\in\mathbb{R}^{n}\) be affinely independent, i.e., \(v_1-v_0,\ldots,v_k-v_0\) are linearly independent, then a simplex is defined as the convex hull of $v_0,\ldots,v_k$$:

   \[\begin{aligned} C={\bf{conv}}\{v_0,\ldots,v_k\}=\{\theta_0 v_0+\ldots+\theta_kv_k\vert \theta\succeq 0, 1^T\theta =1\}. \end{aligned}\]

   The polyhedra form of a simplex is given as follows:

   \[\begin{aligned} \{x\vert A_2x=A_2v_0,A_1x \succeq A_1v_0, 1^TA_1x\leq 1+1^TA_1v_0\}. \end{aligned}\]

   Let \(B=[v_1-v_0 \ldots v_k-v_0]\in\mathbb{R}^{n\times k}\), the affine Independence makes sure that \(rank(B)=k\). \(A_1\in\mathbb{R}^{k\times n }\) and \(A_2\in\mathbb{R}^{(n-k)\times n }\) are chosen such that \(A_1B=I\) and \(A_2B=0\).

2.2.5 The Positive Semidefinite Cone

1. The positive semidefinite set, \({\bf{S}}^{n}_{+}\), is a convex cone. I.e., if \(\theta_1,\theta_2\geq 0\), and \(A,B\in{\bf{S}}^{n}_{+}\), then \(\theta_1A+\theta_2B\in \bf{S}^{n}_{+}\)