一、介绍
习题建议
Chapter 2
2.1、2.2、2.5、2.7、2.10、2.16、2.18、2.19
Chapter 3
3.1、3.2、3.5、3.13、3.18、3.21、3.32、3.33、3.36、3.43
Chapter 4
4.3、4.9、4.22、4.24、4.59、4.62
Chapter 5
5.5、5.20、5.27
基本概念
凸优化：优化的一种，是优化中比较容易的问题。其中目标函数是凸函数，约束是一个凸集（约束由若干个凸函数组成）
优化：从一个可行解的集合中，寻找出最优的元素
数学形式：
其中 $X=[x_1,x_2,…,x_n]^T$ 为优化变量， $f_0:R^n\rightarrow R$ 为目标函数， $f_i:R^n\rightarrow R$ 为不等式约束， $X^*$ 为最优解
线性函数： $f(\alpha x+\beta y)=\alpha f(x)+\beta f(y)$
凸函数： $f(\alpha x+\beta y)\leq \alpha f(x)+\beta f(y),\alpha,\beta\geq 0,\alpha+\beta=1$
光滑函数：各阶导数存在且连续的函数
连续 / 离散：取决于可行域是连续区域还是离散点
范数： $R^n$ 空间的范数 $P(x),x\in R^n$ ，满足
-
$P(ax)=|a|P(x)$
-
三角不等式： $P(x+y)\leq P(x)+P(y)$
-
$P(x)=0\Leftrightarrow x=0$
谱范数： $||A(x)||_2$ 表示矩阵 $A(x)$ 最大的奇异值
经典不等式：
-
三角不等式： $||a+b||\leq ||a||+||b||$ ，对任意范数成立
-
柯西-施瓦茨不等式 (Cachy-Schwartz)： $|\langle x,y\rangle|^2\leq \langle x,x\rangle\cdot\langle y,y\rangle$ ，变形 $\langle a,b\rangle + \|a\|*\|b\|\geq 0$
-
min-max 不等式： $\sup_{z\in S_z}\inf_{w\in S_w}f(w,z)\leq \inf_{w\in S_w}\sup_{z\in S_z}f(w,z)$
二、凸集
仿射集 (Affine Sets)
基本概念
直线方程：（ $y$ 为直线上任意一点）
线段方程：
仿射组合：
- 设 $x_1,…,x_k\in c,\theta_1,…,\theta_k\in R,\theta_1+…+\theta_k=1$ ，则 $\theta_1x_1+…+\theta_kx_k$ 为一个仿射组合
仿射包：
-
$\{\theta_1x_1+…+\theta_kx_k|\forall x_1,…,x_k\in c,\forall \theta_1,…,\theta_k\in R,\theta_1+…+\theta_k=1\}$
-
包含 $x_1,…,x_k$ 的最小的仿射集
仿射集：
-
【简单定义】一个集合 $c$ 是仿射集，则 $\forall x_1,x_2\in c$ ，连接 $x_1,x_2$ 的直线上的点也都在集合内
-
【泛化定义】一个集合 $c$ 是仿射集，则 $\forall x_1,…,x_k\in c$ ，其仿射组合 $\in c$
-
【注意】上述两个定义是等价的
与 $c$ 相关的子空间：
-
$c$ 是一个仿射集， $\forall x_0\in c$ ，则 $V=c-x_0={x-x_0|x\in c}$ 是一个与 $c$ 相关的子空间，不能直接称其为子空间
-
【性质 1】与 $c$ 相关的子空间一定经过原点
-
【性质 2】 $\forall v_1,v_2\in V$ ，则 $\forall \alpha,\beta,\alpha v_1+\beta v_2\in V$
举例
线性方程组的解集等价于仿射集
正向 - 线性方程组的解集 $c$ 是仿射集：
-
$c=\{x|Ax=b\},A\in R^{m\cdot n}, b\in R^m, x\in R^n$
-
【证明】 $\forall x_1,x_2\in c$ ，则 $Ax_1=Ax_2=b$ ，且 $A(\theta x_1+(1-\theta)x_2)=b$
逆向 - 任意一个仿射集 $c$ 都可以写成一个线性方程组的解集：
子空间是仿射集的平移，子空间是仿射集对应线性变换 A 的零空间 / 核
线性方程组的解集 $c$ 的子空间 $V$ 是 $A$ 的化零空间：
仿射集 $c$ 与子空间 $V$ 的关系：
-
$c=\{x|Ax=b\},\forall x_0\in c,V=\{x-x_0|A(x-x_0)=0\}$
-
任意一个仿射集 $c$ 将其平移到至少有一个点落到原点上，则这个新的集合一定是一个仿射集，且为与 $c$ 相关的子空间。
$Ax=0$ 与 $Ax=b$ 的关系：
凸集 (Convex Sets)
基本概念
凸集：
-
【简单定义】一个集合 $c$ 是凸集，当任意两点之间的线段仍然在 $c$ 内
-
【数学定义】 $\forall x_1,x_2\in c,\forall \theta \in [0,1],\theta x_1+(1-\theta)x_2\in c$
-
【泛化定义】任意元素凸组合 $\in c$
-
仿射集要求的是直线，凸集要求的是线段，因此仿射集一定是凸集
凸组合：
- 设 $x_1,…,x_k\in c,\theta_1,…,\theta_k\in [0,1],\theta_1+…+\theta_k=1$ ，则 $\theta_1x_1+…+\theta_kx_k$ 为一个凸组合
凸包：
-
$\{\theta_1x_1+…+\theta_kx_k|\forall x_1,…,x_k\in c,\forall \theta_1,…,\theta_k\in [0,1],\theta_1+…+\theta_k=1\}$
-
包含 $x_1,…,x_k$ 的最小的凸集
典型凸集
-
$R^n$ 空间
-
$R^n$ 空间的子空间，即过原点的、加乘封闭的空间
-
任意直线、线段
-
超平面 (Hyperplane)： ${x|a^Tx=b,a,x\in R^n,b\in R}$
-
半空间 (half space)：超平面将 $R^n$ 分成两个半空间
-
球： ${x|||x-x_c||_2 \leq r}$
-
椭球： ${x|(x-x_c)^TP^{-1}(x-x_c)\leq 1},x_c\in R^n,P\in S^n_{++}$ ，即 $n$ 维对称正定矩阵
-
多面体： ${x|a_j^Tx\leq b_j,j=1,…,m;a_j^Tx=d_j,j=1,…,p}$ ，若干个半空间和超平面的交集
-
单纯形： $R^n$ 空间中选择 $v_0,…,v_k$ 共 k+1 个点， $v_1-v_0,…,v_k-v_0$ 线性无关，则与上述点相关的单纯形为 $c=\text{Conv}\{v_0,…,v_k\}=\{\theta_0v_0+…+\theta_kv_k|\theta\geq 0,I^T\theta=1\}$ ，任何一个单纯形都是多面体
-
对称矩阵集合、对称半正定矩阵集合
凸集性质
-
任意多个凸集的交集是凸集
-
凸集经过仿射函数变换后仍是凸集，仿射函数 $f:R^n\rightarrow R^m,f(x)=Ax+b$
-
凸集经过透视函数变换后仍是凸集，透视函数 $f:R^{n+1}\rightarrow R^n,f(R^n,R_{++})=\displaystyle\frac{R^n}{R_{++}}$
-
凸集经过线性分式函数后仍是凸集， $f:R^n\rightarrow R^{m+1},g(x)=[A \ c^T]^Tx+[b\ d]^T,A\in R^{m\cdot n},b\in R^m,c\in R^n,d\in R$
锥 (Cone)
锥：
-
$c$ 是锥 $\Leftrightarrow \forall x\in c,\theta \geq 0$ ，有 $\theta x\in c$
-
在二维空间中，类似于若干根以原点为连接点的火柴
凸锥：
- $c$ 是凸锥 $\Leftrightarrow x_1,x_2\in c,\theta_1,\theta_2\geq 0$ ，有 $x_1\theta_1+x_2\theta_2\in c$
凸锥组合：
- 设 $x_1,…,x_k\in c,\theta_1,…,\theta_k\geq 0$ ，则 $\theta_1x_1+…+\theta_kx_k$ 为一个凸锥组合
凸锥包：
-
$\{\theta_1x_1+…+\theta_kx_k|\forall x_1,…,x_k\in c,\forall \theta_1,…,\theta_k\geq 0\}$
-
包含 $x_1,…,x_k$ 的最小的凸锥
总结
-
仿射组合： $\forall \theta_1,…,\theta_k,\theta_1+…+\theta_k=1$
-
凸组合： $\forall \theta_1,…,\theta_k,\theta_1+…+\theta_k=1,\theta_1,…,\theta_k\in [0,1]$
-
凸锥组合： $\forall \theta_1,…,\theta_k,\theta_1,…,\theta_k\geq 0$
-
空集是仿射集、凸集、凸锥