Convex sets -- Convex optimization

Hyperplanes and halfspaces

超平面和半空间的几何理解, 取任意在超平面上的点$x_0$, 那么存在点$x$, 然后向量$x-x_0$与超平面的法向量$a$做对比，乘积为钝角或者锐角即可划分半平面空间了。

$$\{x | a^\intercal x = b\}$$

$$\{x | a^\intercal(x -x_0) = 0\}, a^\intercal x_0=b$$

Hyperplane in $\mathcal{R}^2$, with normal vector a and a point $x_0$ in the hyperplane. For any point x in the hyperplane, $x − x_0$ (shown as the darker arrow) is orthogonal to $a$.

A hyperplane defined by $a^\intercal x = b$ in $\mathcal{R}^2$ determines two halfspaces. The halfspace determined by
$a^\intercal x \geq b$ (not shaded) is the halfspace extending in the direction $a$. The halfspace determined by $a^\intercal x \leq b$ (which is shown shaded) extends in the direction $-a$. The vector a is the outward normal of this halfspace.

The shaded set is the halfspace determined by $a^\intercal (x − x_0) \leq 0$. The vector $x_1 −x_0$ makes an acute angle with a, so $x_1$ is not in the halfspace. The vector $x_2 − x_0$ makes an obtuse angle with a, and so is in the halfspace.

Proper cones and generalized inequalities

• $K$ is pointed, which means that it contains no line (or equivalently, $x \in K, −x \in K \nRightarrow x=0$). 几何意思是一个cone里面不存在直线，使得穿过0点后，既在cone中，又在cone外。

minimum and minimal

极小元,最小元
minimum和minimal的区别: 广义的$x + K$及$x - K$是否与S只是相交于一点。$K$ is a proper cone. 在广义的不等式中,被当做符号来使用$\preceq_K$.
以下是两个重要概念

• 最小元的定义只考察在$K$中的所有广义大于$x$的点，如下图左边子图所示广义大于$x_1$的点组成了浅灰色的区域

$$S \subseteq x + K$$

where $x+K$ denotes all the points that are comparable to $x$ and greater than or equal to $x$ (according to $\preceq K$ ).

• 极小元的定义只考察在$K$中的所有广义小于$x$的点，如下图右边子图所示广义小于$x_1$的点组成了浅灰色的区域

$$(x -K) \cap S = \{x\}$$

where $x − K$ denotes all the points that are comparable to $x$ and less than or equal to $x$ (according to $\preceq K$).

$A \in \mathcal{S}^n_{++}$表示一个圆心在圆点的椭圆

$$\varepsilon_A = \{x | x^\intercal A^{-1}x \leq 1\}$$

且定义$A \preceq B$等价于$\varepsilon_A \subseteq \varepsilon_B$
定义对称矩阵的结合为$S$:

$$S = \{P \in \mathcal{S}^n_{++} | v_i^\intercal P^{-1} v_i, i = 1,...,k\}$$

下图表示：
对比椭圆1和3都经过了图中的两个点，等价于了$A \preceq B$, 但是没有一个椭圆可以被椭圆2包含，且经过图中的那个点（两个椭圆圆心相同）。说明了椭圆2表示的对称矩阵$P$是$S$的最小元, 当$k=1$。