概论

说明

最近在学习机器学习方面的算法知识，发现凸优化是机器学习中重要的数学基础，特地买了本书做学习，这里记录下一些学习心得，先搭个框架，内容会逐步展开，后续会陆续更新。

主要参考资料《凸优化》(Stephen Boyd等著，王书宁等译)[1]这本书。
(各种公式用mathjax语法写的，写的崩溃了…..)

什么是凸优化

不严格的说，凸优化就是在标准优化问题的范畴内，要求目标函数和约束函数是凸函数的一类优化问题。
维基百科的定义：
凸优化，或叫做凸最优化，凸最小化，是数学最优化的一个子领域，研究定义于凸集中的凸函数最小化的问题。凸优化在某种意义上说较一般情形的数学最优化问题要简单，譬如在凸优化中局部最优值必定是全局最优值。凸函数的凸性使得凸分析中的有力工具在最优化问题中得以应用，如次导数等。
凸优化应用于很多学科领域，诸如自动控制系统，信号处理，通讯和网络，电子电路设计，数据分析和建模，统计学(最优化设计），以及金融。在近来运算能力提高和最优化理论发展的背景下，一般的凸优化已经接近简单的线性规划一样直捷易行。许多最优化问题都可以转化成凸优化（凸最小化）问题，例如求凹函数f最大值的问题就等同于求凸函数 -f最小值的问题。

重要性

“凸优化在数学规划领域具有非常重要的地位。”

“一旦将一个实际问题表述为凸优化问题，大体上意味着相应问题已经得到彻底解决，这是非凸的优化问题所不具有的性质。”

——《<凸优化>译者序》

凸优化之所以如此重要，是因为：

其应用非常广泛，机器学习中很多优化问题都要通过凸优化来求解；
在非凸优化中，凸优化同样起到重要的作用，很多非凸优化问题，可以转化为凸优化问题来解决；
如上引用所述，凸优化问题可以看作是具有成熟求解方法的问题，而其他优化问题则未必。

凸优化知识体系

凸集，定义目标函数和约束函数的定义域。
凸函数，定义优化相关函数的凸性限制。
凸优化，中心内容的标准描述。
凸优化问题求解，核心内容。相关算法，梯度下降法、牛顿法、内点法等。
对偶问题，将一般优化问题转化为凸优化问题的有效手段，求解凸优化问题的有效方法。

标准优化问题

$min\qquad f_0(x)$ $s.t.\qquad f_i(x)\le0,\qquad i=1,\cdots m$ $\qquad \qquad h_i(x)\le0,\qquad i=1,\cdots p$ $(1)$

表示在所有满足 $f_i(x)\le0,\qquad i=1,\cdots m$ 及 $h_i(x)=0,\qquad i=1,\cdots p$ 的$x$中找出使 $f_0(x)$ 最小的x.
这里, $x \in \mathbf R^n$ ,函数 $f_0:\mathbf R^n \to \mathbf R$ 称为目标函数。
不等式 $f_i(x)\le0$ 称为不等式约束，相应的 $f_i:\mathbf R^n\to \mathbf R,i=1,2,\cdots m$ 称为不等式约束函数，方程组 $h_i(x)=0$ 称为等式约束，相应的 $h_i:\mathbf R^n\to \mathbf R,i=1,2\cdots p$ 称为等式约束。
如果没有约束，即 $m=p=0$ ,称问题1为无约束问题。
对目标和所有约束函数有定义的点的集合

$\mathcal{D}=\bigcap\limits_{i=0}\limits^{m} domf_i \frown \bigcap\limits_{j=1}\limits^{p} domh_j$

称为优化问题1的定义域

凸优化问题

$min\qquad f_0(x)$ $s.t.\qquad f_i(x)\le0,\qquad i=1,\cdots m$ $a_1^T X=b_i,\qquad i=1,\cdots p$ $(2)$

上述优化问题中， $f_i(x),i=0,1,2\cdots m$ 是凸函数，此类问题被称为凸优化问题。
对比优化问题，也就是说，目标函数和不等式约束同为凸函数，等式约束是仿射函数的优化问题属于凸优化问题。

凸集

定义

直线上的点

$\forall x,y\in \mathbf R^n 且 x\neq y$,那么，

$Z=\theta X+(1-\theta)Y,\theta\in \mathbf R \qquad \qquad \qquad (1)$

是一条穿越X和Y的直线

A,$\theta$=0时，Z=Y
B,$\theta$=1时，Z=X
C,$0\lt \theta \lt 1$时，Z是X和Y之间线段上的点
D,$\theta \lt 0或\theta\gt 1$时，线段上的点Z是X和Y线段之外的点

定义

集合C中任意两点之间的线C中，则称集合C为凸集，也即满足$\forall x,y\in \mathbf C,0\lt \theta \lt 1有\theta x+(1-\theta)y\in \mathbf C$的集合称为凸集。

典型的凸集

线段，射线，直线
超平面，半空间
仿射集
欧几里得球，范数球，椭球等
凸锥，范数锥等

其它相关知识

保凸运算

交集、仿射函数、线性分式函数及透视函数

超平面分离定理

两个不相交的凸集，存在一个超平面将其分离。

凸函数

定义

函数$f:\mathbf R^n \to \mathbf R 定义域domf$是凸集，并且对于$\forall x,y\in domf和\forall \theta 0\lt \theta \lt 1有$

$f(\theta x+(1-\theta)y)\le \theta f(x)+(1-\theta)f(y) \qquad \qquad \qquad \qquad (1)$

则称函数$f$是凸的

性质

一阶条件

可微函数$f$是凸函数的充分必要条件是
A,定义域$domf$是凸集。
B,对于$\forall x,y\in domf有f(y)\ge f(x)+\forall f(x)^T(y-x)$

二阶条件

函数f的二阶偏导称为函数f的Hessian矩阵。
对于函数定义域domf内任意一点，其Hessian矩阵存在，则函数f是凸函数的重要条件是：其Hessian矩阵是半正定阵，也即，对于所有的$x\in domf有\forall^2f(x)\succ=0$
对于R上的函数，可以简化为$f(x)\ge 0$(f上面有两小撇，这个公式暂时没找到)

下水平集

函数f的下水平集$C_a={ x\in domf\mid f(x)\le a}$是其定义域的子集。凸函数的下水平集是凸集。

上境图

函数$f:\mathbf R^n \to \mathbf R$的上境图$epi f=((x,t)\mid x \in domf,f(x)\le t))$,它是空间$\mathbf R+{n+1}$上的子集。一个函数是凸函数，当且仅当其上境图是凸集。

典型凸函数

线性函数和仿射函数
指数函数
负熵
范数

保凸运算

非负加权求和、复合仿射映射、逐点最大和逐点上确界、复合等。

Jensen不等式

Jensen当年提出的不等式相当简单，f是凸函数，则

$f(\frac{x+y}2) \le \frac{f(x)+f(y)}{2}$

Jensen不等式，又叫詹森不等式，以丹麦数学家约翰·詹森(Johan Jensen)命名。

5.1、常规形式

5.2、概率形式

5.3、推广

Jensen不等式用途非常广泛。凸性和Jensen不等式可以构成不等式理论的基础，很多著名的不等式都可以通过Jensen不等式应用于合适的凸函数得到[1]。

例如，算数-几何平均不等式可以由负对数函数利用Jensen不等式得到。

问题求解

凸优化的优势

凸优化之所以如此重要，是因为凸优化的重要特性：凸优化的任意局部最优解也是全局最优解。

最优性准则

对于凸优化问题

$min\qquad f_0(x)$ $s.t.\qquad f_i(x)\le0,\qquad i=1,\cdots m$ $\qquad \qquad a_i^tx=b_i,\qquad i=1,\cdots p$ $(1)$

其中$f_i(x),i=0,\cdots m$是凸函数。
$x^*\in \mathbf X$是可微函数$f_0$的最优解，当且仅当

$\bigtriangledown f_0(x^*)^T(Y-X^*)\le 0,\forall y \in \mathbf X \qquad \qquad \qquad \qquad (2)$

无约束凸优化的最优性准则

无约束凸优化问题（式1中，m=p=0）,$x^* \in \mathbf X$是可微函数f的最优解的重要条件是众所周知的

$\bigtriangledown f(x^*)=0$

等式约束凸优化的最优化准则

等式约束凸优化问题（式1中，m=0）,$x^*\in \mathbf X$是可微函数$f_0$的最优解的重要条件是，
存在$\upsilon=[\upsilon_1,\cdots ,\upsilon_p] \in \mathbf R^p$,使得

$\bigtriangledown f_0(x^*)+\Sigma_{i=1}^{p} \upsilon_i a_i=0$

其中，这里$a_i\in \mathbf R^n$.这个可以通过拉格朗日对偶函数的KKT条件证明得到。
将等式约束凸优化问题描述为矩阵形式

$minf(x)$ $s.t.\mathbf Ax=b$

对应的，$x^*\in \mathbf X$是可微函数f的最优解的重要条件为，存在$\upsilon\in \mathbf R^p$使得

$\bigtriangledown f(x^*)+\mathbf A^T\upsilon=0$

其中：$\mathbf A \in \mathbf R^{p\times n}$

无约束凸优化问题求解

解析解

对于少数一些简单的凸优化问题，可以利用最优性准则通过解析来求解。但对于大多数凸优化问题来讲，是没有办法通过解析来求解的。

下降方法

下降方法将产生一个优化点列$x^{(K)},k=1,2,\cdots $,其中

$x^{(K+1)}=$x^{(K)}+t^{(k)}\Delta x^{(k)},t^{(k)}>0$

使得

$f(x^{(k+1)})<f(x^{(k)})$

$\Delta x^{(k)}$称为搜索方向，$t^{(k)}$称为步长
由凸函数的一阶条件可知，下降方法中的搜索方向必须满足

$\bigtriangledown f(x^{(k)})^T\Delta x^{(k)}<0$

下降方法中，有两个问题需要解决：确定搜索步长和确定搜索方向。确定搜索步长的方法和算法有：固定步长搜索、精确直线搜索和回溯直线搜索。确定搜索方向的方法和算法有：梯度下降方法、最速下降方法和牛顿法。

确定步长的方法

固定步长搜索
步长值根据经验设定，为了防止算法震荡，值应当较小。优点：直观、简单；缺点：收敛速度慢。
精确直线搜索
精确搜索方向确定时，精确直线搜索步长通过沿着射线$x+t\Delta x\mid t \ge 0$
求解如下优化问题确定。
$t=arg min_{s \ge 0}f(x+s\Delta x)$
当其优化成本比较低时，适合精确直线搜索。
回溯直线搜索
比较常用的是回溯直线搜索，大概思路是，用迭代方法求得的步长只要能使目标函数有足够的减少即可。详见第五章。

调整搜索方向的方法

梯度下降方法
最速下降方法
利用目标函数的一阶泰勒展开近似优化过程，进而确定学习方向。详见第六章。
牛顿法
利用目标函数的二阶泰勒展开近似表示目标函数，通过求解这个二次函数的极小值来确定搜索方向。详见第七章。

等式约束凸优化问题求解

通过消除等式求解

任何等式约束优化问题都可以通过消除等式约束转化为等价的无约束优化问题，然后利用无约束的方法求解。

通过Lagrange对偶问题求解

利用无约束优化问题求解对偶问题，然后从对偶解中复原等式约束问题的解。详见第八章。

等式约束的牛顿法

详见《凸优化(七)——牛顿法》。

不等式约束凸优化问题求解

通过Lagrange对偶问题求解

利用无约束优化问题求解对偶问题，然后从对偶解中复原不等式约束问题的解。《凸优化(八)——Lagrange对偶问题》。

内点法

主要思路：引进的惩罚函数的在可行域的边界上设置障碍，使求解的迭代过程始终在可行域内部进行。[2]

这里暂不详述，待有时间再学习整理。

回溯直线搜索

意义

回溯直线搜索是求解无约束凸优化问题中，调整搜索步长非常简单有效的方法，也是实际应用中常用的方法。[2]

考虑固定步长搜索，为防止迭代震荡，一般步长值很小，很多经验值取0.01，这就导致收敛速度过慢。

考虑精确直线搜索，其本身又是一个优化问题，如果这个优化问题很复杂，则这个搜索方法就是没有意义的。

相比以上两种调整搜索步长的方法，回溯直线搜索则简单高效很多。

回溯直线搜索

算法

算法解释

参数解释

(未完待续)
A、参考

[1]、《凸优化》，Stephen Boyd等著，王书宁等译