凸优化笔记

简单凸优化笔记

凸函数和凸集

• 凸函数上方区域为凸集
• 函数上方区域为凸集，则函数为凸函数

凸集

集合$C$任意两点间线段都在集合$C$里，则称集合$C$为凸集
$$\begin{gathered} \forall x_1,x_2\in C,\theta \in [0,1] \\ 则\theta x_1+(1-\theta )x_2\in C \end{gathered}$$
拓展
$$\begin{gathered} \forall x_1,...,x_k\in C,{\theta }_i\in [0,1]且\sum {\theta }_i=1 \\ 则\sum {\theta }_i{x}_i\in C \end{gathered}$$

凸多边形是凸集,边界缺失不是凸集

超平面和半空间

超平面

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

半空间

$$\begin{gathered} \{x|a^{T}x\le b\} \\ \{x|a^{T}x\ge b\} \end{gathered}$$

多面体

多面体是有限个半空间和超平面交集
$$P=\{x|a_j^{T}x\le b_j,c_i^{T}x=d_i\}$$
仿射集（如超平面，直线），射线，线段，半空间都是多面体

多面体是凸集

有界多面体称多胞形

保持凸性运算

• 集合交运算

定义证明

• 仿射变换
  • 伸缩
  • 平移
  • 投影

$$\begin{gathered} f(x)=Ax+b,A\in R^{m\times n},b\in R^m \\ f:R^n\to R^{m}f(S)=\{f(x)|x\in S\} \\ S为凸集\to f(S)为凸集 \\ f(S)为凸集\to S为凸集 \end{gathered}$$

• 透视变换

透视函数对向量进行伸缩（规范）使最后一维的分量为一并舍弃
$$P:R^{n+1}\to R^n,P(z,t)=z/t$$

• 投射变换（线性分式变换）

透视和仿射的复合
$$\begin{gathered} g:R^n\to R^{n+1} \\ g(x)=\left[\begin{array}{c}A\\ c^T\end{array}\right]x+\left[\begin{array}{c}b\\ d\end{array}\right] \\ A\in R^{m\times n},b\in R^m,c\in R^n,d\in R \end{gathered}$$
定义$f$为线性分式函数
$$\begin{gathered} f(x)=\frac{(Ax+b)}{c^{T}x+d} \\ domf=\{x|c^{T}x+d>0\} \end{gathered}$$
若$c=0,d>0$则$f$为普通仿射函数

分割超平面

设$C$和$D$为两个不相交凸集，则存在超平面$P$，$P$可以将$C$和$D$分离
$$\forall x\in C,a^{T}x\le b且\forall x\in D,a^{T}x\ge b$$

注意可以取等号

逆命题

若两个凸集$C$和$D$的分割超平面存在，$C$和$D$不相交为假命题

加强条件

若两个凸集至少有一个是开集，那么当且仅当存在分割超平面，它们不相交

分割超平面构造

距离

两个集合距离为两个集合间元素的最短距离

构造

做距离中垂线

支撑超平面

设集合$C$，$x_0$为$C$边界上的点。若存在$a\ne 0$，满足对任意$x\in C$，都有$a^{T}x\le a^T{x}_0$成立，则称超平面$\{x|a^{T}x=a^T{x}_0\}$为集合$C$在点$x_0$处的支撑超平面

凸集边界任意一点都存在支撑超平面

反之，若一个闭的非中空（内部点不为空）集合，在边界上任意一点存在支撑超平面，则该集合为凸集

凸函数

若函数$f$定义域$domf$为凸集，且满足
$$\forall x,y\in domf,0\le \theta \le 1有f(\theta x+(1-\theta )y)\le \theta f(\theta )+(1-\theta )f(y)$$

一阶可微

若$f$一阶可微，则函数$f$为凸函数当且仅当$f$的定义域$domf$为凸集且
$$\forall x,y\in domf,f(y)\ge f(x)+▽f(x{)}^T(y-x)$$

对于凸函数，其一阶泰勒近似本质为该函数全局估计

反之若一个函数一阶泰勒近似总是其全局下估计，则该函数为凸函数

二阶可微

若函数$f$二阶可微，则函数$f$为凸函数当且仅当$domf$为凸集，且
$${▽}^{2}f(x)\succ =0$$
若$f$为一元函数，上式表示二阶导大于等于$0$

若$f$为多元函数，上式表示二阶导海森矩阵半正定

例子

• $e^{ax}$
• $x^a,x\in R_{+},a\ge 1或a\le 0$
• $-logx$
• $xlogx$
• $||x|{|}_p$
  • $max(x_1,...,x_n)$
  • $x^2/a,a>0$
  • $log(e^{x_1+...+e^{x_n}})$

上境图

函数$f$图像定义为$\{(x,f(x))|x\in domf\}$
函数$f$的上境图定义为
$$epif=\{(x,t)|x\in domf,f(x)\le t\}$$

凸函数与凸集

一个函数是凸函数，当且仅当其上境图是凸集
一个函数为凹函数，当且仅当其亚图是凸集
$$hypof=\{(x,t)|t\le f(x)\}$$

杰森不等式

$f$是凸函数情况下
$$f(\theta x+(1-\theta )y)\le \theta f(x)$$
$$\begin{gathered} 若{\theta }_1...{\theta }_k\ge 0,{\theta }_1+...+{\theta }_k=1 \\ 则f({\theta }_1{x}_1+...+{\theta }_k{x}_k)\le {\theta }_{1}f(x_1)+...+{\theta }_{k}f(x_k) \end{gathered}$$
$$\begin{gathered} 若p(x)\ge 0在S\subseteq domf,{\int }_{S}p(x)dx=1 \\ 则f({\int }_{S}p(x)xdx)\le {\int }_{S}f(x)p(x)dx \\ 或f(Ex)\le E(f(x)) \end{gathered}$$
可由杰森不等式证明
$$D(p||q)=\sum p(x)log\frac{p(x)}{q(x)}=E_{p(x)}log\frac{p(x)}{q(x)}\ge 0$$
等等

保持函数凸性的算子

• 非负加权和
  $$f(x)=w_1{f}_1(x)+...+w_n{f}_n(x)$$
• 与仿射函数复合
  $$g(x)=f(Ax+b)$$
• 逐点最大值，逐点上确界
  $$\begin{gathered} f(x)=max(f_1(x),...,f_n(x)) \\ f(x)=\underset{y\in A}{\sup }g(x,y) \end{gathered}$$

函数逐点上确界函数对应着函数上境图交集

凸优化

优化问题基本形式

$$\begin{gathered} 最小化f_0(x),x\in R^n \\ 不等式约束f_i(x)\le 0,i=1...m \\ 等式约束h_i(x)=0,j=1...p \\ 无约束优化m=p=0 \end{gathered}$$
$$\begin{gathered} 优化问题的域D=\bigcap _{i=1}^{m}dom{f}_i\cap \bigcap _{j=1}^{p}dom{h}_j \\ 可行点（解）x\in D且满足约束条件 \\ 可行域，所有可行点集合 \end{gathered}$$
$$\begin{gathered} 最优化值p^{\ast }=inf\{f_0(x)|f_i(x)\le 0,i=1...m,h_j(x)=0,j=1...p\} \\ 最优化解p^{\ast }=f_0(x^{\ast }) \end{gathered}$$

凸优化问题基本形式

$$\begin{gathered} f_i(x)为凸函数 \\ {h}_j(x)为仿射函数 \end{gathered}$$
重要性质

• 可行域为凸集
• 局部最优解为全局最优解

对偶问题

拉格朗日函数

$$L(x,\lambda ,\upsilon )=f_0(x)+\sum {\lambda }_i{f}_i(x)+\sum {\upsilon }_j{h}_j(x)$$
对固定$x$，拉格朗日函数$L(x,\lambda ,\upsilon )$为关于$\lambda$和$\upsilon$的仿射函数

拉格朗日对偶函数

$$\begin{gathered} g(\lambda ,\upsilon )=\underset{x\in D}{\inf }L(x,\lambda ,\upsilon )=\underset{x\in D}{\inf }(f_0(x)+\sum {\lambda }_i{f}_i(x)+\sum {\upsilon }_j{h}_j(x)) \\ 若无下确界定义g(\lambda ,\upsilon )=-\infty \end{gathered}$$
根据定义有：对$\forall \lambda \ge 0,\forall \upsilon$，原优化问题有最优值$p^{\ast }$，则
$$g(\lambda ,\upsilon )\le p^{\ast }$$
进一步，拉格朗日对偶函数为凹函数

假设$x_0$不可行，即存在$f_i(x)>0$，则选择${\lambda }_i\to \infty$，对于其他乘子${\lambda }_i=0,j\ne i$
假设$x_0$可行，则有$f_i(x)\le 0,i=1...m$，令${\lambda }_i=0,i=1...m$
有
$$\underset{\lambda \ge 0}{\sup }L(x,\lambda )=\underset{\lambda \ge 0}{\sup }(f_0(x)+\sum {\lambda }_i{f}_i(x))=\{\begin{array}{c}{f}_0(x),f_i(x)<0\\ \infty ，other\end{array}$$

原问题为${\inf }_x{f}_0(x)$转变为${\inf }_x{\sup }_{\lambda \ge 0}L(x,\lambda )$
对偶问题是求对偶函数最大值，即
$$\underset{\lambda \ge 0}{\sup }\underset{x}{\inf }L(x,\lambda )$$
而
$$\underset{\lambda \ge 0}{\sup }\underset{x}{\inf }L(x,\lambda )\le \underset{x}{\inf }\underset{\lambda \ge 0}{\sup }L(x,\lambda )$$

强对偶条件

对偶函数最大值为原问题最小值
$$\begin{gathered} f_0(x^{\ast })=g({\lambda }^{\ast }+{\upsilon }^{\ast }) \\ =\underset{x}{\inf }(f_0(x)+\sum {\lambda }_i^{\ast }{f}_i(x)+\sum {\upsilon }_j^{\ast }{h}_j(x)) \\ \le f_0(x^{\ast })+\sum {\lambda }_i^{\ast }{f}_i(x^x)+\sum {\upsilon }_j^{\ast }{h}_j(x^{\ast }) \\ \le f_0(x^{\ast }) \end{gathered}$$
条件
$$\begin{gathered} f_i(x^{\ast })\le 0 \\ {h}_i(x^{\ast })=0 \\ {\lambda }_i^{\ast }\ge 0 \\ {\lambda }_i^{\ast }{f}_i(x^{\ast })=0 \\ i=1...m \\ ▽f_0(x^{\ast })+\sum {\lambda }_i^{\ast }▽f_i(x^x)+\sum {\upsilon }_j^{\ast }▽h_j(x^{\ast })=0 \end{gathered}$$