[TOC]

1. 凸集

集合$C$被称为凸集，如果C中任意两点间的线段仍然在$C$中。即对于任意$x_1,x_2\in C$和满足$0\leq \theta \leq 1$的$\theta$都有

$\theta x_1+(1-\theta)x_1\in C\\ \tag{1-1}$

2. 凸函数

凸函数的原始定义：

函数$f:{\rm{R}}^n\rightarrow{\rm{R}}$是凸的，如果${\rm dom}\ f$是凸集，且对于任意$x,y\in {\rm dom}\ f$和任意$0\leq \theta\leq 1$，有
$f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta)f(y)\tag{2-1}$

严格凸：上式中当$x\not=y$且$0\leq \theta \leq 1$时，不等式严格成立（即取小于号）
几何意义：上述不等式意味着点$(x,f(x))$和$(y,f(y))$之间的线段在函数$f$的图像上方。

2.1. 凸函数的一阶条件

假设$f$可微（即其梯度$\nabla f$在开集${\rm dom}\ f$内处处存在），则函数$f$是凸函数的充要条件是${\rm dom}\ f$是凸集且对于任意$x,y\in {\rm dom}\ f$，下式成立：
$f(y)\geq f(x)+\nabla f(x)^T(y-x)\tag{2-2}$

几何意义：凸函数的一阶Taylor近似是原函数的一个全局下估计，也即凸函数任意一点处的切线都在原函数图像的下方。反之亦然（充分必要条件）
2.2. 凸函数的二阶条件

假设$f$二阶可微，即对于开集${\rm dom}\ f$内的任意一点，它的Hessian矩阵或者二阶导数$\nabla ^2f$存在，则函数$f$是凸函数的充要条件是其Hessian矩阵是半正定阵：即对于所有的$x\in {\rm dom}\ f$有：
$\nabla^2f(x)\succeq 0\tag{2-3}$

几何意义：函数图像在点$x$处具有正（向上）的曲率。

2.1. 凸函数例子

常见的凸函数：

指数函数：$e^{ax},\forall a \in R$
范数: $\lVert x\rVert_p=\left(\lvert x_1\rvert^p+\lvert x_2\rvert^p+\cdots+\lvert x_n\rvert^p\right)^{1/p},p\geq 1$。${\rm R}^n上的任意范数均为凸函数$。
负熵函数：函数$xlog{x}$在其定义域（$R_{++}或者R_X$）上是凸函数。

3. 凸优化问题

优化问题的标准形式：

$\begin{align*} min\ \ &f_0(x)\\ s.t.\ \ &f_i(x)\leq 0,i=1,2,\cdots,m\\ &h_i(x)=0,i=1,2,\cdots,p\\ \tag{3-1} \end{align*}$

我们称$x\in R^n$为优化变量，称函数$f_0:R^n\rightarrow R$为为目标函数或代价函数；不等式$f_i(x)\leq 0$称为不等式约束，$h_i:R^n\rightarrow R$称为等式约束。优化问题的定义域是目标函数和约束函数的定义域的交集。满足约束条件的定义域中的点称为可行点；所有可行点的集合称为可行集。
问题$(3-1)$的最优值$p^{\star}$定义为:

$\begin{align*} p=\inf\{&f_0(x)|\\ &f_i(x)\leq 0,i=1,2,\cdots,m,h_i(x)=0,i=1,2,\cdots,p\}\\ \tag{3-2} \end{align*}$

如果问题不可行，则$p^{\star}=\infty$

凸优化问题的标准形式

$\begin{align*} min\ \ &f_0(x)\\ s.t.\ \ &f_i(x)\leq 0,i=1,2,\cdots,m\\ &a_i^Tx=b_i,i=1,2,\cdots,p\\ \tag{3-3} \end{align*}$

其中，$f_0,f_1,\cdots,f_m$是凸函数
凸优化问题与一般优化问题的标准形式的区别在于以下三点：

目标函数必须是凸的
不等式约束函数必须是凸的
等式约束函数必须是仿射函数

至于为什么等式约束必须是仿射函数，这里有个直观的解释：等式约束可以看成要同时满足$h_i(x)\leq 0$和$-h_i(x)\leq 0$,为了满足不等式约束的条件，要求$h_i(x)$同时是凸函数和凹函数，这样的函数只能是仿射函数。

凸优化问题有一个很好的性质：任意局部最优解也是全局最优解。
对于无约束条件的凸优化问题，$x$是其最优解的充要条件是：

$\nabla f_0 (x)=0 \\ \tag{3-2}$

4. 对偶

4.1. Lagrange函数与Lagrange对偶

回到前面提到的标准形式的优化问题：

$\begin{align*} min\ \ &f_0(x)\\ s.t.\ \ &f_i(x)\leq 0,i=1,2,\cdots,m\\ &h_i(x)=0,i=1,2,\cdots,p\\ \tag{4-1} \end{align*}$

注意，这里没有要求是凸优化问题。
Lagrange对偶的基本思想是，在目标函数中考虑$(4-1)$的约束条件，即添加约束条件的加权和，得到增广的目标函数，称之为Lagrange函数：

$L(x,\lambda,\nu)=f_0(x)+\sum_{i=1}^{m}{\lambda _if_i(x)} + \sum_{i=1}^{p}{\nu _ih_i(x)}\\ \tag{4-2}$

注意，Lagrange函数的定义域是$D\times R^m\times R^p$，在后面的讨论中，我们会假设$\lambda_i\geq 0$
向量$\lambda$和$\nu$成为对偶变量，或者是问题$(4-1)$的Lagrange乘子向量。
Lagrange对偶函数定义为Lagrange函数关于x取得的最小值：

$\begin{align*} g(\lambda,\nu)&=\mathop{inf}\limits_{x\in D}L(x,\lambda,\nu)\\ &= \mathop{inf}\limits_{x\in D}\left(f_0(x)+\sum_{i=1}^{m}{\lambda _if_i(x)} + \sum_{i=1}^{p}{\nu _ih_i(x)}\right)\\ \tag{4-3} \end{align*}$

Lagrange对偶函数是Lagrange函数的逐点下确界有，有个很重要的性质：无论原问题是不是凸的，Lagrange对偶函数都是凹函数。下面分别从理论上进行证明，以及从几何上形象地解释。
理论证明：
不难看出，$g(\lambda,\nu)$是关于$\lambda,\nu$的仿射函数，为了书写简简洁，我们用一个长的向量$\mu$代表$(\lambda,\nu)$
要想证明$g(\lambda,\nu)$是凹函数，只需证明$\forall \mu_1,\mu_2$下式都成立：

$g(\theta \mu_1+(1-\theta)\mu_2)\geq \theta g(\mu_1)+(1-\theta)g(\mu_2)\\ \tag{4-4}$

下面是证明过程：

$\begin{align*} g(\theta \mu_1+(1-\theta)\mu_2)&=\mathop{min}\limits_{x}L(x,\theta \mu_1+(1-\theta)\mu_2)\\ &=\mathop{min}\limits_{x}\left(\theta L(x, \mu_1)+(1-\theta)L(x, \mu_2)\right)\\ &\geq \mathop{min}\limits_{x}\left(\theta L(x, \mu_1)\right)+\mathop{min}\limits_{x}\left((1-\theta)L(x, \mu_2)\right)\\ &=\theta\mathop{min}\limits_{x}\left( L(x, \mu_1)\right)+(1-\theta)\mathop{min}\limits_{x}\left(L(x, \mu_2)\right)\\ &=\theta g(\mu_1)+(1-\theta)g(\mu_2)\\ \tag{4-5} \end{align*}$

得证！
注意，第一步到第二步是因为$L(x,\mu)$是关于$u$的仿射函数；第二步到第三步是因为，地二步中取得最小值时，括号中两项中的$x$是取相同的值的，而第三步中两项分别取最小值不要求$x$一定取相同值（也即能够比第二步涵盖更多情况），因此第三步可能取到的最小值肯定小于或等于第二步的最小值。
几何解释如下：
由于$L(x,\mu)$是关于$u$的仿射函数，我们将$\mu$退化为1维来形象地解释。$L(x,\mu)$可以看成是许多的直线簇组成。$g(x,\mu)$可以理解成：当$\mu$取某一个值时，取曲线簇在这个值上的最小值，遍历所有$\mu$，将曲线簇的一些最小值作为$g(x,\mu)$的值域。因此，$g(x,\mu)$可以看成下图中黄色区域的边界线，显然是一个凹函数。
逐点下确界几何解释

此外，Lagrange对偶函数还有如下性质：
$\forall \lambda \succeq 0$(每一维都大于0)和$\nu$，都有

$g(\lambda,\nu)\leq p^{\star}\\ \tag{4-6}$

其中$p^{\star}$是原问题的最优值。也即，对偶函数构成了原问题的最优值的下界。

4.2. 共轭函数

设函数$f:R^n\rightarrow R$，定义$f^{\star}:R^n\rightarrow R$为：

$f^{\star}(y)=\mathop{sup}\limits_{x\in dom\ f}\left(y^Tx-f(x)\right)\\ \tag{4-7}$

此函数成为函数$f$的共轭函数。共轭函数是一系列仿射函数的逐点上确界，所以必然是一个凸函数。
对于负熵函数$xlog{x}$，它的共轭函数不难推导出是$f^{\star}(y)=e^{y-1}$,这在后面会用到

4.3. Lagrange对偶问题

由$(4-6)$可以看到，对于任意一组$(\lambda,\nu)$，其中$\lambda \succeq0$,Lagrange对偶函数给出了优化问题$(4-1)$的最优值$p^{\star}$的一个下界。我们来看一下从Lagrange函数得到的最好下界。该问题可以表述为如下优化问题：

$\begin{align*} maximize\ \ g(\lambda,\nu)\\ subject\ to\ \ \lambda\succeq 0 \tag{4-8} \end{align*}$

上述问题被称为原问题的Lagrange对偶问题。
满足$\lambda \succeq 0$和$g(\lambda,\nu)>0$的一组$(\lambda,\nu)$被称为一组对偶可行解。如果一组$(\lambda^{\star},\nu^{\star})$是对偶问题的最优解，那么称它是对偶最优解或者最优Lagrange乘子。
由于$g(\lambda,\nu)>0$必然是凹函数，且约束条件是凸函数，所以问题$(4-8)$必然是一个凸优化问题。
因此Lagrange对偶问题是一个凸优化问题，与原问题的凸性无关

记Lagrange对偶问题的最优值为$d^{\star}$，原问题的最优值为$p^{\star}$。显然有$d^{\star}\leq p^{\star}$，这个性质称为弱对偶性。

4.4. 强对偶性与Slater约束准则

如果前面的有$d^{\star}=p^{\star}$，则强对偶性成立。
强对偶性成立的一个简单的约束条件是：存在一点$x\in relint\ D$使得下式成立：

$f_i(x)< 0,i1,\cdots,m,Ax=b\\ \tag{4-9}$

如果不等式约束函数中有一些是仿射函数时，Slater条件可以进一步改进为：不是仿射函数的那些不等式约束函数需要满足$(4-9)$。换言之，仿射不等式不需要严格成立。
由此可以得到一个推论：当所有约束条件是线性等式或线性不等式且$dom\ f_0$是开集时，改进的Slater条件就是可行性条件。也即只要问题是可行的，强对偶性就成立。
Boyd的《Convex Optimization》一书中，证明了当原问题是凸问题且Slater条件成立时，强对偶性成立。

4.5. 最优性条件

注意，此小节讨论的问题并不要求是凸问题。

4.5.1. 互补松弛性

如果强对偶性成立，则有：

$\begin{align*} f_0(x^{\star})&=g(\lambda^{\star},\nu^{\star})\\ &=\mathop{inf}\limits_{x}\left(f_0(x)+\sum_{i=1}^{m}{\lambda _i^{\star}f_i(x)} + \sum_{i=1}^{p}{\nu _i^{\star}h_i(x)}\right))\\ &\leq f_0(x^{\star})+\sum_{i=1}^{m}{\lambda _i^{\star}f_i(x^{\star})} + \sum_{i=1}^{p}{\nu _i^{\star}h_i(x^{\star})}\\ &\leq f_0(x^{\star})\\ \tag{4-10} \end{align*}$

上式可以得到几个有用的结论：

由于第三个不等式取等号，说明$L(x,\lambda^{\star},\nu^{\star})$在$x^{\star}$处取得局部最小值，也即该点处导数为0
$\lambda_i^{\star}f_i(x^{\star})=0,i=1,2,\cdots,m$，这个称为互补松弛条件，意味着在最优点处，不等式约束要么取等号$(f_i(x^{\star})=0)$，要么它对应的Lagrange乘子为零$\lambda_i^{\star}=0$

4.5.2. KKT最优性条件

这小节讨论的目标函数$f_0$和约束函数$f_1,f_2,\cdots,f_m,h_1,h_2,\cdots,h_p$是可微的，但并不要求它们都是凸函数。
结合上一小节的内容，我们可以推出，对于目标函数和约束函数可微的任意优化问题，如果强对偶性成立，则任一对偶问题的最优解和对偶问题的最优解必须满足下列的式子：

$\begin{align*} f_i(x^{\star})&\leq 0 ,i=1,2,\cdots,m\\ h_i(x^{\star})&=0,i=1,2,\cdots,p\\ \lambda_i^{\star}&\geq 0,i=1,2,\cdots,m\\ \lambda_i^{\star}f_i(x^{\star})&=0,i=1,2,\cdots,m\\ \nabla f_0(x^{\star})+\sum_{i=1}^{m}{\lambda _i^{\star}\nabla f_i(x^{\star})} + \sum_{i=1}^{p}{\nu _i^{\star}\nabla h_i(x^{\star})}&=0\\ \tag{4-9} \end{align*}$

上式被称为非凸问题的KKT条件：
如果原问题是凸问题，则满足KKT条件的点也是原、对偶问题的最优解。这个定理很重要！
上述定理的证明：前面两个条件说明了$x^{\star}$是原问题的可行解；因为$\lambda^{\star}\geq 0$，所以$L(x,\lambda^{\star},\nu^{\star})$是x的凸函数；最优一个条件说明了Lagrange函数在$x^{\star}$处导数为零，也即Lagrange函数取得全局最小值，因此此时有：

$\begin{align*} g(\lambda^{\star},\nu^{\star})&=L(x^{\star},\lambda^{\star},\nu^{\star})\\ &=f_0(x^{\star})+\sum_{i=1}^{m}{\lambda _i^{\star}f_i(x^{\star})} + \sum_{i=1}^{p}{\nu _i^{\star}h_i(x^{\star})}\\ &=f_0(x^{\star})\\ \tag{4-10} \end{align*}$

上述意味着对偶间隙为0，强对偶性成立，因此得证。

4.5.3. 通过解对偶问题求解原问题

由前面可知，如果强对偶性成立，且存在一个对偶最优解$(\lambda^{\star},\nu^{\star})$，那么任意原问题最优点也是$L(x,\lambda^{\star},\nu^{\star})$的最优解。利用这个性质，我们可以从对偶最优方程中去求解原问题最优解。确切的讲，如果强对偶性成立，对偶最优解$(\lambda^{\star},\nu^{\star})$已知，并且下列问题的解唯一：

$min\ f_0(x)+\sum_{i=1}^{m}{\lambda _if_i(x)} + \sum_{i=1}^{p}{\nu _ih_i(x)}\tag{4-11}$

（Lagrange函数是严格凸函数时上述最优化问题的解是唯一的），如果上式问题的解是原问题的可行解，那么它就是原问题的最优解；如果它不是原问题的可行解，那么原问题不存在最优解（或者无法达到）。当对偶问题比原问题更容易求解时，上述方法很有意义。

5. 利用Lagrange对偶求解最优化问题的例子

5.1. 熵的最大化问题

这个例子在机器学习中可能会经常遇到。问题描述如下：

$\begin{align*} min\ f_0(x)&=\sum_{i=1}^{n}{x_ilog{x_i}}\\ s.t.\ Ax&\preceq b\\ 1^Tx&=1\\ \tag{5-1} \end{align*}$

定义域为$R_{++}$
记目标函数为$f_0(x)$Lagrange函数为：

$\begin{align*} L(x,\lambda,\nu)=f_0(x)+\lambda^T(Ax-b)+\nu(\vec 1^Tx-1)\\ \tag{5-2} \end{align*}$

Lagrange对偶函数为：

$\begin{align*} g(\lambda,\nu)&=\mathop{inf}\limits_{x}\ \left(f_0(x)+\lambda^T(Ax-b)+\nu(1^Tx-1)\right)\\ &=-b^T\lambda-\nu+\mathop{inf}\limits_{x}\ \left(f_0(x)+(A^T\lambda+\vec 1\nu)^Tx\right)\\ &=-b^T\lambda-\nu-\mathop{sup}\limits_{x}\ \left(-f_0(x)-(A^T\lambda+\vec 1\nu)^Tx\right)\\ &=-b^T\lambda-\nu-f_0^{\star}\left(-(A^T\lambda+\vec 1\nu)\right)\\ \tag{5-3} \end{align*}$

其中$f_0^{\star}$是$f_0$的共轭函数。对于负熵函数$xlog{x}$，它的共轭函数不难推导出是$f^{\star}(y)=e^{y-1}$，因此不难得出$(5-3)$可进一步化为：

$\begin{align*} g(\lambda,\nu)&=\mathop{inf}\limits_{x}\ \left(f_0(x)+\lambda^T(Ax-b)+\nu(1^Tx-1)\right)\\ &=-b^T\lambda-\nu-\sum_{i=1}^{n}e^{\left(-a_i^T\lambda-\nu-1\right)}\\ \tag{5-3} \end{align*}$

假设原问题可行，也即Slater条件成立（注意这里的约束条件都是仿射函数），那么此时强对偶性成立。因此对Lagrange函数求最小值即可求得原问题的最小值解。注意到Lagrange函数是严格凸函数，很容易求得最小值点

$x_i^{\star}=exp\left(-(a_i^T\lambda^{\star}+\nu^{\star}+1)\right),i=1,2,\cdots,n\\ \tag{5-4}$

其中$a_i$是$A$的列向量，如果$x^{\star}$是原问题的可行解，则必定是原问题的最优解。