1. convex sets

1.1 Line segmentation 直线分割

$\theta$=1时$y=x_1$,=0时反之，所以称为直线分割

根据式2也可以看做是以x_2为基准。向x_1-x_2延伸的一条线

1.2 affine sets

仿射集C上的任意两点连成的直线属于C
即

扩展到多点上为

其中，对于属于C的子空间是
$V=C-x_0=\{x-x_0|x\in C\}$

意味着标量乘积之和是闭合的

子空间维数=仿射集维数

1.3 affine hull 仿射包

aff$C=\{\theta x_{1}+…+\theta_k x_{k}|x_{1}, x_{2}…x_k\in C, \theta_1+\theta_2+…+\theta_k=1\}$

  1. C中的所有点的仿射组合组成的集合
  2. 仿射集维数=仿射集子空间的维数
  3. 是包含C的最小仿射集合

1.4 相对内部 relative interior

如果集合C的仿射维数小于n,那么aff$C\ne R ^n$
相对内部relint C定义为
$\text { relint } C =\{x \in C \mid B(x, r) \cap \operatorname{aff} C \subseteq C \text { for some } r>0\}$
其中$B(x,y)=\{y| |y-x|\le r\}$(任意范数均可)

（呃呃呃开始不说人话了是吧）

1.5 convex sets 凸集

任意两点的线段都在C中
$\theta x_{1}+(1-\theta) x_{2} \in C$

所有点的凸组合为凸包（convex hull）
conv$C=\{\theta x_{1}+…+\theta_k x_{k}|x_{1}, x_{2}…x_k\in C, \theta_1+\theta_2+…+\theta_k=1, \theta_i\ge 0\}$
凸包是包含C的最小凸集

2. cone 锥

对与任何x属于C以及$\theta$大于等于0，都有
$\theta x\in C$

2.1 凸锥

锥且凸，即
$\theta_1 x_1 + \theta_2 x_2\in C$

2.2 锥包

所有锥组合形成的集合

3. 重要例子

3.1 一些概念

  1. 空集、任意一个点（即单点集）、全空间R”都是Rn的仿射（自然也是凸的)子集。
  2. 任意直线是仿射的。如果直线通过零点，则是子空间，因此，也是凸锥。
  3. 一条线段是凸的，但不是仿射的（除非退化为一个点）。
  4. 一条射线，即具有形式$\{x_0+\theta v|\theta≥0\}$，v≠0的集合，是凸的，但不是仿射的。如果射线的基点$x_0$是0，则它是凸锥。
  5. 任意子空间是仿射的、凸锥（自然是凸的）。

3.2 超平面

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

  • $a\in R^n且不为0, b\in R$
  • 超平面是关于x的线性方程的解空间（因此是仿射集合）

3.3 半空间

$\{x|a^Tx\le b\}$

  • 线性不等式的解空间
  • 凸但不仿射
  • 由超平面切割而成2个半空间

3.4 Euclid球

$\begin{aligned}
B\left(x_{c}, r\right) &=\left\{x \mid\left|x-x_{c}\right|_{2} \leq r\right\} \\
&=\left\{x \mid\left(x-x_{c}\right)^{\top}\left(x-x_{c}\right) \leq r^{2}\right\}
\end{aligned}$

  • $x_c$为球心
  • r是半径

3.5 多面体

$\begin{array}{r}
\mathcal{P}=\left\{x \mid a_{j}^{\top} x-b_{j} \leq 0, j=1, \ldots, m\right. \\
\left.c_{j}^{\top} x-d_{j}=0, j=1, \ldots, p\right\}
\end{array}$

  • 有限个线性等式和不等式的集合（即有限个超平面和半空间的交集）
  • 凸集

4. 凸集间的保凸运算

凸集之间的运算生成新的凸集

4.1 交集

$S=S1 \cap S2 $也为凸

4.2 仿射函数

形同$f(x)=Ax+b$，对于任意点s属于凸集S，$f(s)$为凸
同样若有f(s)属于凸集S，则原象$f^{-1}(s)$也为凸

4.3 透视函数

对于$P(z,t)=z/t$（定义域为dom $P=R^n \times R_{++}$ ）

$R_{++}为正实数$

则对任意x属于凸C，P(x)也为凸

5. 凸函数

$f:R^n \rightarrow R$, 若dom f为凸集，且x,y属于dom f,且$\theta$在0，1之间，则

  • 严格凸函数：无等号
  • 凹函数：当-f是凸

最大值函数就是一个凸函数：

5.1 扩展值延伸 Extended-value extensions

定义：当x不在dom f时，我们认为$f(x)=\infty$

5.2 一阶条件

  1. dom f是凸集
  2. $f(y)\ge f(x)+ \bigtriangledown f(x)^T(y-x) $
  • 右式为f在点x附近的泰勒近似

5.3 二阶条件

$f(x)$的hessian矩阵为半正定，即可认为

$\succeq$指的是矩阵中的不等式

  • 对于在R上的f，我们简单的认为就是二阶导大于等于0

5.4 凸函数间的保凸运算

  • 非负加权求和

  • 复合仿射映射

    f凸时，g凸