凸优化问题

求解一般的最优化问题的全局最优解通常是困难的，至少会面临局部极值与鞍点问题，如果对优化问题加以限定，则可以有效地避免这些问遉，保证求得全局极值点

典型的限定问题为凸优化(Convex Optimization)问题

数值优化面临的问题

其于导数的数值优化算法判断收敛的依据是梯度为$\mathbf{0}$，但梯度为$\mathbf{0}$只是函数取得局部极值的必要条件而非充分条件，更不是取得全局极值的充分条件，因此，这类算法会面临如下问题

无法收敛到梯度为$\mathbf{0}$的点，此时算法不收敛
能够收敛到梯度为$\mathbf{0}$的点，但在该点处黑塞矩阵不正定，因此不是局部极值点，称为鞍点问题
能够收敛到梯度为$0$的点，在该点处黑塞矩阵正定，找到了局部极值点，但不是全局极值点

xxx图 4.17$-x^{2}+y^{2}$的击点

对于上图所示的目标函数，如果以$(0,4)$作为初始迭代点，迭代法最后会陷人鞍点$(0,0)$，在$(0,0)$点处梯度为$\mathbf{0}$，黑塞矩阵为

$\left(\begin{array}{cc} -2 & 0 \\ 0 & 2 \end{array}\right)$

该矩阵的特征值为$-2$和2，显然矩阵不定，相比鞍点，判定一个局部极小值点是否为全局极小值点更为困难，因为目标函数可能存在多个局部极值，需要找到所有的局部极值，然后进行比较，通常是一个NP难问题

对于让迭代法如何摆脱局部极小值以及鞍点，梯度下降法的各种改进版本以及随机梯度下降法，均有一定程度解决这两个问题的能力

凸集

定义

对于$n$维空间中的点集$C$，如果对该集合中的任意两点$x$和$y$，以及实数$0 \leqslant \theta \leqslant 1$，都有

$\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y} \in C$

则称该集合为凸集

从直观上来看，凸集的形状是凸的，没有凹进去的地方，把集合中的任意两点用直线连起来，直线段上的所有点都属于该集合

$\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y}$

称为点$\boldsymbol{x}$和$y$的凸组合，下图是凸集和非凸集的示例，左边为凸集，右边为非凸集

xxx图凸集和非凸集示例

下面列举实际应用中常见的凸集

$n$维实向量空间$\mathbb{R}^{n}$是凸集，显然，如果$\boldsymbol{x},\boldsymbol{y} \in \mathbb{R}^{n}$，则有

$\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y} \in \mathbb{R}^{n}$

给定$m \times n$矩阵$\boldsymbol{A}$和$m$维向量$\boldsymbol{b}$，仿射子空间

$\left\{\boldsymbol{A x}=\boldsymbol{b}, \boldsymbol{x} \in \mathbb{R}^{n}\right\}$

是非齐次线性方程组的解，也是凸集

假设$x,y \in \mathbb{R}^{n}$并且$\boldsymbol{A x}=\boldsymbol{b},\boldsymbol{A y}=\boldsymbol{b}$，对于任意$0 \leqslant \theta \leqslant 1$，有

$\boldsymbol{A}(\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y})=\boldsymbol{\theta} \boldsymbol{A} \boldsymbol{x}+(1-\theta) \boldsymbol{A} \boldsymbol{y}=\theta \boldsymbol{b}+(1-\theta) \boldsymbol{b}=\boldsymbol{b}$

因此结论成立

这一结论意味着，由一组线性等式约束条件定义的可行域是凸集

多面体是如下线性不等式组定义的向量集合

$\left\{\boldsymbol{A} \boldsymbol{x} \leqslant \boldsymbol{b}，\boldsymbol{x} \in \mathbb{R}^{n}\right\}$

它也是凸集

对于任意$\boldsymbol{x},\boldsymbol{y} \in \mathbb{R}^{n}$并且$\boldsymbol{A x} \leqslant \boldsymbol{b},\boldsymbol{A} y \leqslant \boldsymbol{b}，0 \leqslant \theta \leqslant 1$，都有

$\boldsymbol{A}(\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y})=\theta \boldsymbol{A} \boldsymbol{x}+(1-\theta) \boldsymbol{A} \boldsymbol{y} \leqslant \theta \boldsymbol{b}+(1-\theta) \boldsymbol{b}=\boldsymbol{b}$

因此结论成立

此结论意味着由线性不等式约束条件定义的可行域是凸集

实际问题中等式和不等式约束通常是线性的，因此它们确定的可行域是凸集

多个凸集的交集也是凸集

假设 $C_{1}，\cdots，C_{k}$ 为凸集，它们的交集为 $\bigcap_{i=1}^{k} C_{i}$ 对于任意点 $\boldsymbol{x},\boldsymbol{y} \in \bigcap_{i=1}^{k} C_{i}$ ，并且 $0 \leqslant \theta \leqslant 1$ ，由于 $C_{1},\cdots,C_{k}$ 为凸集，因此有

$\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y} \in C_{\mathbf{i}}，\forall i=1，\cdots，k$

由此得到

$\theta x+(1-\theta) y \in \bigcap_{i=1}^{k} C_{i}$

这个结论意味着如果每个等式或者不等式约束条件定义的集合都是凸集，那么这些条件联合起来定义的集合还是凸集

凸集的并集不是凸集，这样的反例很容易构造

给定一个凸函数$f(x)$以及实数$\alpha$，此函数的$\alpha$下水平集(Sub-level Set)定义为函数值小于或等于$\alpha$的点构成的集合

$\{f(x) \leqslant \alpha，x \in D(f)\}$

其中$D(f)$为函数$f(\boldsymbol{x})$的定义域，对于下水平集中的任意两点$\boldsymbol{x},\boldsymbol{y}$，它们满足

$f(\boldsymbol{x}) \leqslant \alpha \qquad f(\boldsymbol{y}) \leqslant \alpha$

对于$0 \leqslant \theta \leqslant 1$，根据凸函数的定义有

$f(\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y}) \leqslant \theta f(\boldsymbol{x})+(1-\theta) f(\boldsymbol{y}) \leqslant \theta \alpha+(1-\theta) \alpha=\alpha$

$\theta \boldsymbol{x}+(1-\theta) \boldsymbol{y}$也属于该下水平集，因此下水平集是凸集

下面举例说明，对于如下凸函数

$f(x，y)=x^{2}+y^{2}$

如果$\alpha=1$，则下水平集$x^{2}+y^{2} \leqslant 1$是圆心为原点的单位圆所围成的区域，为凸集；如果$f(\boldsymbol{x})$不是凸函数，则不能保证下水平集是凸集

对于下面的凹函数

$f(x, y)=-x^{2}-y^{2}$

如果$\alpha=1$，则下水平集$-x^{2}-y^{2} \leqslant 1$为二维空间除掉单位圆之后的区域，显然不是凸集

这一结论的用途在于我们需要确保优化问题中一些不等式约束条件定义的可行域是凸集

凸优化问题及其性质

如果一个最优化问题的可行域是凸集且目标函数是凸函数，则该问题为凸优化问题

凸优化问题可以形式化地写成

$\min _{\boldsymbol{x}} f(\boldsymbol{x})，\boldsymbol{x} \in C$

其中$x$为优化变量；$f$为凸目标函数；$C$是优化变量的可行域，为凸集

凸优化问题的另一种通用写法是

$\begin{array}{l} \min _{\boldsymbol{x}} f(\boldsymbol{x}) \\ g_{i}(\boldsymbol{x}) \leqslant 0,\quad i=1,\cdots,m \\ h_{i}(\boldsymbol{x})=0,\quad i=1,\cdots,p \end{array}$

其中 $g_{i}(\boldsymbol{x})$ 是不等式约束函数，为凸函数； $h_{i}(\boldsymbol{x})$ 是等式约束函数，为仿射(线性)函数

上式中不等式的方向非常重要，因为一个凸函数的0下水平集是凸集，对于凹函数则不成立

这些不等式共同定义的可行域是一组凸集的交集，仍然为凸集

通过将大于或等于号形式的不等式两边同时乘以$-1$，可以把不等式统一写成小于或等于号的形式

仿射空间是凸集，因此加上这些等式约束后可行域还是凸集

需要强调的是，如果等式约束不是仿射函数，那么通常无法保证其定义的可行域是凸集

例如等式约束$x^{2}+y^{2}+z^{2}=1$确定的可行域是三维空间的球面，显然不是凸集

凸集证明

上面的定义也给出了证明一个优化问题是凸优化问题的一般性方法，即证明目标函数是凸函数，等式和不等式约束构成的可行域是凸集

对于凸优化问题，所有局部最优解都是全局最优解

这个特性可以保证在求解时不会陷入局部极值问题，如果找到了问题的一个局部最优解，则它一定也是全局最优解，这极大地简化了问题的求解

下面采用反证法证明此结论

假设$\boldsymbol{x}$是一个局部最优解但不是全局最优解，则存在一个可行解$\boldsymbol{y}$，满足

$f(\boldsymbol{x})>f(\boldsymbol{y})$

根据局部最优解的定义，对于给定的邻域半径$\delta$，不存在满足$|\boldsymbol{x}-\boldsymbol{z}|_{2}<\delta$并且$f(\boldsymbol{z})<f(\boldsymbol{x})$的点$z$，选择一个点

$\boldsymbol{z}=\theta \boldsymbol{y}+(1-\theta) \boldsymbol{x}$

其中

$\theta=\frac{\delta}{2\|\boldsymbol{x}-\boldsymbol{y}\|_{2}}$

则有

$\|x-z\|_{2}=\left\|x-\left(\frac{\delta}{2\|x-y\|_{2}} y+\left(1-\frac{\delta}{2\|x-y\|_{2}}\right) x\right)\right\|_{2}=\left\|\frac{\delta}{2\|x-y\|_{2}}(x-y)\right\|_{2}=\frac{\delta}{2}<\delta$

即该点在$\boldsymbol{x}$的$\delta$邻域内，根据凸函数的性质以及前面的假设有

$f(\boldsymbol{z})=f(\theta \boldsymbol{y}+(1-\theta) \boldsymbol{x}) \leqslant \theta f(\boldsymbol{y})+(1-\theta) f(\boldsymbol{x})<f(\boldsymbol{x})$

这与$x$是局部最优解矛盾

如果一个局部最优解不是全局最优解，在它的任何邻域内还可以找到函数值比该点函数值更小的点，这与该点是局部最优解矛盾

之所以凸优化问题的定义要求目标函数是凸函数，并且优化变量的可行域是凸集，是因为缺少其中任何一个条件都不能保证局部最优解是全局最优解，下面来看两个反例

可行域是凸集，目标函数不是凸函数，如下方左图所示，显然，此非凸函数存在多个局部极小值点，但只有一个是全局极小值点
可行域不是凸集，目标函数是凸函数，如下方右图所示，可行域不是凸集，中间有断裂，目标函数是凸函数

左边和右边的曲线各有一个局部极小值点，分别为$x=-1$以及$x=1$，不能保证局部极小值就是全局极小值

xxx图可行域是凸集，目标函数不是凸函数+可行域不是凸集，目标函数是凸函数

可以很容易把这个例子推广到三维空间里的二元函数(曲面)

由于凸函数的黑塞矩阵是半正定的，不存在鞍点，因此凸优化问题也不会出现鞍点问题

带约束的优化问题

拉格朗日乘数法

定义

拉格朗日乘数法(Lagrange Multiplier Method)用于求解带等式约束条件的函数极值，给出了此类问题取得极值的一阶必要条件(First-order Necessary Conditions)，假设有如下极值问题

$\begin{array}{l} \min _{\boldsymbol{x}} f(\boldsymbol{x}) \\ h_{i}(\boldsymbol{x})=0，i=1，\cdots，p \end{array}$

拉格朗日乘数法构造如下拉格朗日乘子函数

$L(\boldsymbol{x}，\boldsymbol{\lambda})=f(\boldsymbol{x})+\sum_{i=1}^{p} \lambda_{i} h_{i}(\boldsymbol{x})$

其中$\boldsymbol{\lambda}$为新引入的自变量，称为拉格朗日乘子(Lagrange Multipliers)

在构造该函数之后，去掉了对优化变量的等式约束

对拉格朗日乘子函数的所有自变量求偏导数，并令其为0，这包括对$x$求导、对$\boldsymbol{\lambda}$求导，得到下列方程组

$\begin{aligned} \nabla_{x} f(x)+\sum_{i=1}^{p} \lambda_{i} \nabla_{x} h_{i}(x) & =0 \\ h_{i}(\boldsymbol{x}) & =0 \end{aligned}$

求解该方程组即可得到函数的候选极值点，显然，方程组的解满足所有的等式约束条件

几何解释

在极值点处目标函数的梯度是约束函数梯度的线性组合

$\nabla_{x} f(x)=-\sum_{i=1}^{p} \lambda_{i} \nabla_{x} h_{i}(x)$

下面用一个实际例子来说明拉格朗日乘数法的使用，求解如下极值问题

$\begin{array}{l} \min _{x,y}\left(x^{2}+2 y^{2}\right) \\ x+y=1 \end{array}$

首先构造拉格朗日乘子函数

$L(x,y, \lambda)=x^{2}+2 y^{2}+\lambda(x+y-1)$

对优化变量、乘子变量求偏导数，并令其为0，得到下面的方程组

$\frac{\partial L}{\partial x}=2 x+\lambda=0 \qquad \frac{\partial L}{\partial y}=4 y+\lambda=0 \qquad \frac{\partial L}{\partial \lambda}=x+y-1=0$

最后解得

$x=\frac{2}{3} \qquad y=\frac{1}{3}$

目标函数的黑塞矩阵为

$\left(\begin{array}{ll} \frac{\partial^{2} f}{\partial x^{2}} & \frac{\partial^{2} f}{\partial x \partial y} \\ \frac{\partial^{2} f}{\partial y \partial x} & \frac{\partial^{2} f}{\partial y^{2}} \end{array}\right)=\left(\begin{array}{ll} 2 & 0 \\ 0 & 4 \end{array}\right)$

黑塞矩阵正定，因此该极值点是极小值点

如果三角形的周长确定，为常数$2 C$，证明当三角形为等边三角形的时候面积最大

假设三角形三个边长度为$x 、 y 、 z$，显然有

$x+y+z=2 C$

根据海伦公式，三角形的面积为

$S=\sqrt{C(C-x)(C-y)(C-z)}$

构造拉格朗日乘子函数

$L(x，y，z，\lambda)=\sqrt{C(C-x)(C-y)(C-z)}+\lambda(x+y+z-2 C)$

对优化变量以及乘子变量求偏导数，并令它们为0，得到下面的方程组

$\begin{array}{l} \frac{\partial L}{\partial x}=-\frac{C(C-y)(C-z)}{2 \sqrt{C(C-x)(C-y)(C-z)}}+\lambda=0 \\ \frac{\partial L}{\partial y}=-\frac{C(C-x)(C-z)}{2 \sqrt{C(C-x)(C-y)(C-z)}}+\lambda=0 \\ \frac{\partial L}{\partial z}=-\frac{C(C-x)(C-y)}{2 \sqrt{C(C-x)(C-y)(C-z)}}+\lambda=0 \\ \frac{\partial L}{\partial \lambda}=x+y+z-2 C=0 \end{array}$

解此方程组可以得到

$x=y=z=\frac{2 C}{3}$

这就证明了面积最大时三角形是等边三角形

应用一线性判别分析

下面介绍拉格朗日乘数法在线性判别分析中的应用，线性判别分析的目标是将向量投影到低维空间，使得同一类样本之间的距离尽可能近，不同类样本之间的距离尽可能远

类内距离由类内散布矩阵描述，类间距离由类间散布矩阵描述

假设 $S_{B}$ 为总类间散布矩阵， $S_{W}$ 为总类内散布矩阵，算法要优化的目标函数为下面的广义瑞利商

$L(\boldsymbol{w})=\frac{\boldsymbol{w}^{\mathrm{T}} \boldsymbol{S}_{B} \boldsymbol{w}}{\boldsymbol{w}^{\mathrm{T}} \boldsymbol{S}_{W} \boldsymbol{w}}$

上式的分母为类内差异，分子为类间差异，$w$为投影方向向量

这个最优化问题的解不唯一，可以证明如果 $\boldsymbol{w}^{*}$ 是最优解，将它乘上一个非零系数 $k$ 之后， $k \boldsymbol{w}^{*}$ 还是最优解

因此可以加上一个约束条件消掉冗余，同时简化问题

$\boldsymbol{w}^{\mathrm{T}} \boldsymbol{S}_{W} \boldsymbol{w}=1$

这样上面的最优化问题转化为带等式约束的极大值问题

$\begin{array}{l} \max _{\boldsymbol{w}}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{S}_{B} \boldsymbol{w}\right) \\ \boldsymbol{w}^{\mathrm{T}} \boldsymbol{S}_{W} \boldsymbol{w}=1 \end{array}$

下面用拉格朗日乘数法求解，构造拉格朗日乘子函数

$L(\boldsymbol{w}, \lambda)=\boldsymbol{w}^{\mathrm{T}} \boldsymbol{S}_{B} \boldsymbol{w}+\lambda\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{S}_{W} \boldsymbol{w}-1\right)$

对$\boldsymbol{w}$求梯度并令梯度为$\mathbf{0}$，可以得到

$\boldsymbol{S}_{B} \boldsymbol{w}+\lambda S_{W} \boldsymbol{w}=\mathbf{0}$

即有

$S_{B} w=\lambda S_{W} w$

如果 $S_{W}$ 可逆，上式两边左乘 $S_{W}^{-1}$ 后可以得到

$S_{W}^{-1} S_{B} w=\lambda w$

即 $\lambda$ 是矩阵 $S_{W}^{-1} S_{B}$ 的特征值， $w$ 为对应的特征向量，假设 $\lambda$ 和 $w$ 是上面广义特征值问题的解，代入目标函数可以得到

$\frac{\boldsymbol{w}^{\mathrm{T}} \boldsymbol{S}_{B} \boldsymbol{w}}{\boldsymbol{w}^{\mathrm{T}} \boldsymbol{S}_{W} \boldsymbol{w}}=\frac{\boldsymbol{w}^{\mathrm{T}}\left(\lambda \boldsymbol{S}_{W} \boldsymbol{w}\right)}{\boldsymbol{w}^{\mathrm{T}} \boldsymbol{S}_{W} \boldsymbol{w}}=\lambda$

这里的目标是要让该比值最大化，因此最大的特征值$\lambda$及其对应的特征向量是最优解

拉格朗日对偶

对偶是求解最优化问题的一种手段，它将一个最优化问题转化为另外一个更容易求解的问题，这两个问题是等价的

先介绍拉格朗日对偶，对于如下带等式约束和不等式约束的优化问题

$\begin{array}{l} \min _{x} f(\boldsymbol{x}) \\ g_{i}(\boldsymbol{x}) \leqslant 0 i=1，\cdots，m \\ h_{i}(\boldsymbol{x})=0 i=1，\cdots，p \end{array}$

仿照拉格朗日乘数法构造广义拉格朗日乘子函数

$L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\nu})=f(\boldsymbol{x})+\sum_{i=1}^{m} \lambda_{i} g_{i}(\boldsymbol{x})+\sum_{i=1}^{p} \nu_{i} h_{i}(\boldsymbol{x})$

称 $\boldsymbol{\lambda}$ 和 $\nu$ 为拉格朗日乘子， $\lambda_{i}$ 必须满足 $\lambda_{i} \geqslant 0$ 的约束，稍后会解释原因

接下来将上面的问题转化为如下所谓的原问题，其最优解为$p^{*}$

$p^{*}=\min _{\boldsymbol{x}} \max _{\lambda，\nu，\lambda_{\lambda} \geqslant 0} L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\nu})=\min _{\boldsymbol{x}} \theta_{P}(\boldsymbol{x})$

上式第一个等号右边的含义是先固定变量$x$，将其看成常数，让拉格朗日函数对乘子变量$\lambda$和$\nu$求极大值；消掉变量$\lambda$和$\nu$之后，再对变量$x$求极小值，为了简化表述，定义如下极大值问题

$\theta_{P}(\boldsymbol{x})=\max _{\lambda,\nu,\lambda_{i} \geqslant 0} L(\boldsymbol{x}，\boldsymbol{\lambda}，\boldsymbol{\nu})$

这是一个对变量$\lambda$和$\nu$求函数$L$的极大值的问题，将$x$看成常数

这样，原始问题被转化为先对变量$\lambda$和$\nu$求极大值，再对$x$求极小值

这个原问题和我们要求解的原始问题有同样的解，下面给出证明，对于任意的$x$，分两种情况进行讨论

1️⃣如果$\boldsymbol{x}$是不可行解，对于某些$i$有$g_{i}(\boldsymbol{x})>0$，即$\boldsymbol{x}$违反了不等式约束条件

我们让拉格朗日乘子 $\lambda_{i}=+\infty$ ，最终使得目标函数值 $\theta_{P}(\boldsymbol{x})=+\infty$

如果对于某些$i$有$h_{i}(\boldsymbol{x}) \neq 0$，违反了等式约束，我们可以让

$\nu_{i}=+\infty \cdot \operatorname{sgn}\left(h_{i}(x)\right)$

从而使得

$\theta_{P}(\boldsymbol{x})=+\infty$

即对于任意不满足等式或不等式约束条件的$\boldsymbol{x}，\theta_{P}(\boldsymbol{x})$的值是$+\infty$

2️⃣如果 $\boldsymbol{x}$ 是可行解，这时 $\theta_{P}(\boldsymbol{x})=f(\boldsymbol{x})$ ，因为有 $h_{i}(\boldsymbol{x})=0$ ，并且 $g_{i}(\boldsymbol{x}) \leqslant 0$

而我们要求 $\lambda_{i} \geqslant 0$ ，因此 $\theta_{P}(\boldsymbol{x})$ 的极大值就是 $f(\boldsymbol{x})$

为了达到这个极大值，我们让 $\lambda_{i}$ 和 $\nu_{i}$ 为0，函数 $f(x)+\sum_{i=1}^{p} \nu_{i} h_{i}(x)$ 的极大值就是 $f(x)$

综合以上两种情况，问题$\theta_{P}(\boldsymbol{x})$和我们要优化的原始问题的关系可以表述为

$\theta_{P}(\boldsymbol{x})=\left\{\begin{array}{ll} f(\boldsymbol{x}),& g_{i}(\boldsymbol{x}) \leqslant 0，h_{i}(\boldsymbol{x})=0 \\ +\infty, & \text { other } \end{array}\right.$

即$\theta_{P}(\boldsymbol{x})$是原始优化问题的无约束版本

对任何不可行的$\boldsymbol{x}$，有$\theta_{P}(\boldsymbol{x})=+\infty$，从而使得原始问题的目标函数值趋向于无穷大，排除掉$\boldsymbol{x}$的不可行区域，最后只剩下可行的$\boldsymbol{x}$组成的区域

这样我们要求解的带约束优化问题被转化成了对$x$不带约束的优化问题，并且二者等价

接下来定义对偶问题与其最优解$d^{*}$

$d^{*}=\max _{\lambda,\nu,\lambda_{1} \geqslant 0} \min _{\boldsymbol{x}} L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\nu})=\max _{\boldsymbol{\lambda},\nu,\lambda_{i} \geqslant 0} \theta_{D}(\boldsymbol{\lambda},\boldsymbol{\nu})$

其中

$\theta_{D}(\boldsymbol{\lambda}，\boldsymbol{\nu})=\min _{\boldsymbol{x}} L(\boldsymbol{x}，\boldsymbol{\lambda}，\boldsymbol{\nu})$

与上面的定义相反，这里是先固定拉格朗日乘子$\lambda$和$\nu$，调整$x$让拉格朗日函数对$x$求极小值；然后调整$\lambda$和$\nu$对函数求极大值

原问题和对偶问题只是改变了求极大值和极小值的顺序，每次操控的变量是一样的

弱对偶定理

如果原问题和对偶问题都存在最优解，则对偶问题的最优值不大于原问题的最优值，即

$d^{*}=\max _{\boldsymbol{\lambda},\nu,\lambda_{i} \geqslant 0} \min _{\boldsymbol{x}} L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\nu}) \leqslant \min _{\boldsymbol{x}} \max _{\lambda,v,\lambda_{i} \geqslant 0} L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\nu})=p^{*}$

这一结论称为弱对偶定理(Weak Duality )

下面给出证明，假设原问题的最优解为 $x_{1}，\lambda_{1}，\nu_{1}$ ，对偶问题的最优解为 $x_{2}，\lambda_{2}，\nu_{2}$ ，由于原问题是先对 $(\lambda，\nu)$ 取极大值，对偶问题是先对 $\boldsymbol{x}$ 取极小值，因此有

$L\left(\boldsymbol{x}_{1},\boldsymbol{\lambda}_{1},\boldsymbol{\nu}_{1}\right) \geqslant L\left(\boldsymbol{x}_{1},\boldsymbol{\lambda}_{2},\boldsymbol{\nu}_{2}\right) \qquad L\left(\boldsymbol{x}_{2},\boldsymbol{\lambda}_{2},\boldsymbol{\nu}_{2}\right) \leqslant L\left(\boldsymbol{x}_{1},\boldsymbol{\lambda}_{2},\boldsymbol{\nu}_{2}\right)$

从而得到

$L\left(\boldsymbol{x}_{1},\boldsymbol{\lambda}_{1},\boldsymbol{\nu}_{1}\right) \geqslant L\left(\boldsymbol{x}_{2},\boldsymbol{\lambda}_{2},\boldsymbol{\nu}_{2}\right)$

首先用矩阵弱对偶的例子解释其直观含义

$\left[\begin{array}{llll}1 & 3 & 2 & 5 \\ 1 & 6 & 9 & 7 \\ 3 & 1 & 8 & 2\end{array}\right]$

假设行方向(水平方向)为$x$方向，列方向(垂直方向)为$\lambda$方向

🌾原问题首先固定$x$，变动$\lambda$求极大值，即取每一列的极大值，得到

$(3 \quad 6 \quad 9 \quad 7)$

然后变动$x$，求上面这个行的极小值，结果为3

🍒对偶问题首先固定$\lambda$，变动$x$，求极小值，即先求每一行的极小值，得到

$\left(\begin{array}{l} 1 \\ 1 \\ 1 \end{array}\right)$

然后求这个列的极大值，结果为1

可以看到原问题的最优解比对偶问题的最优解要大

弱对偶的原理如下图所示

xxx图弱对偶证明过程

图中横轴方向为优化变量$\boldsymbol{x}$，纵轴为乘子变量$\boldsymbol{\lambda}$和$\boldsymbol{\nu}$，为了直观，将这些变量都显示为一维的情况

值得注意的是，弱对偶定理对于所有最优化问题都是成立的

对偶间隙

原问题最优值和对偶问题最优值的差 $p^{*}-d^{*}$ 称为对偶间隙

如果原问题和对偶问题有相同的最优解，那么我们就可以把求解原问题转化为求解对偶问题，此时对偶间隙为0，这种情况称为强对偶

强对偶成立的一种充分条件就是下面要讲述的Slater条件

Slater条件指出，一个凸优化问题如果存在一个候选$x$使得所有不等式约束都是严格满足的，即对于所有的$i$都有$g_{i}(\boldsymbol{x})<0$

也就是说，在不等式约束区域的内部至少有一个可行点(非边界点)，则存在 $\left(x^{*}，\lambda^{*}，\nu^{*}\right)$ 使得它们同时为原问题和对偶问题的最优解

$p^{*}=d^{*}=L\left(\boldsymbol{x}^{*}，\boldsymbol{\lambda}^{*}，\nu^{*}\right)$

Slater条件是强对偶成立的充分条件而不是必要条件

强对偶的意义在于我们可以将求解原成对偶问题，而这个对偶问题怎么求解则是另外一个问题

下面举例说明如何将一个优化问題转化为拉格朗日对偶问题，对于如下的最优化问题

$\begin{array}{l} \min _{x_{1}, x_{2}, x_{3}}\left(x_{1}^{2}+x_{2}^{2}\right) \\ x_{1}+x_{2}+x_{3} \leqslant-1 \\ 2 x_{1}+x_{2}+x_{3} \geqslant 1 \\ x_{1}+2 x_{2}+x_{3} \geqslant 1 \end{array}$

显然目标函数是凸函数，可行域是线性不等式围成的区域，是凸集，因此这是一个凸优化问题

下面的一组解即可使得不等式约束严格满足

$x_{1}=3, x_{2}=3, x_{3}=-7.5$

显然

$\begin{aligned} x_{1}+x_{2}+x_{3} & =3+3-7.5=-1.5<-1 \\ 2 x_{1}+x_{2}+x_{3} & =6+3-7.5=1.5>1 \\ x_{1}+2 x_{2}+x_{3} & =3+6-7.5=1.5>1 \end{aligned}$

因此Slater条件成立

将不等式约束写成标准形式

$x_{1}+x_{2}+x_{3}+1 \leqslant 0 \quad-2 x_{1}-x_{2}-x_{3}+1 \leqslant 0 \quad-x_{1}-2 x_{2}-x_{3}+1 \leqslant 0$

构造广义拉格朗日乘子函数

$\begin{array}{c} L\left(x_{1}, x_{2}, x_{3}, \lambda_{1}, \lambda_{2}, \lambda_{3}\right)=x_{1}^{2}+x_{2}^{2}+\lambda_{1}\left(x_{1}+x_{2}+x_{3}+1\right) \\ \quad+\lambda_{2}\left(-2 x_{1}-x_{2}-x_{3}+1\right)+\lambda_{3}\left(-x_{1}-2 x_{2}-x_{3}+1\right) \end{array}$

原问题为

$\begin{array}{l} \min _{x_{1}, x_{2}, x_{3}} \max _{\lambda_{1}, \lambda_{2}, \lambda_{3}} L\left(x_{1}, x_{2}, x_{3}, \lambda_{1}, \lambda_{2}, \lambda_{3}\right)=x_{1}^{2}+x_{2}^{2}+\lambda_{1}\left(x_{1}+x_{2}+x_{3}+1\right) \\ \quad+\lambda_{2}\left(-2 x_{1}-x_{2}-x_{3}+1\right)+\lambda_{3}\left(-x_{1}-2 x_{2}-x_{3}+1\right) \qquad \lambda_{i} \geqslant 0, i=1, \cdots, 3 \end{array}$

对偶问题为

$\begin{array}{l} \max _{\lambda_{1}, \lambda_{2}, \lambda_{3}} \min _{x_{1}, x_{2}, x_{3}} L\left(x_{1}, x_{2}, x_{3}, \lambda_{1}, \lambda_{2}, \lambda_{3}\right)=x_{1}^{2}+x_{2}^{2}+\lambda_{1}\left(x_{1}+x_{2}+x_{3}+1\right) \\ \quad+\lambda_{2}\left(-2 x_{1}-x_{2}-x_{3}+1\right)+\lambda_{3}\left(-x_{1}-2 x_{2}-x_{3}+1\right) \qquad \lambda_{i} \geqslant 0, i=1, \cdots, 3 \end{array}$

下面求解对偶问题，对$x_{i}$求偏导数并令其为0，可以得到

$\frac{\partial L}{\partial x_{1}}=2 x_{1}+\lambda_{1}-2 \lambda_{2}-\lambda_{3}=0 \quad \frac{\partial L}{\partial x_{2}}=2 x_{2}+\lambda_{1}-\lambda_{2}-2 \lambda_{3}=0 \quad \frac{\partial L}{\partial x_{3}}=\lambda_{1}-\lambda_{2}-\lambda_{3}=0$

解得

$x_{1}=\frac{1}{2}\left(-\lambda_{1}+2 \lambda_{2}+\lambda_{3}\right) \quad x_{2}=\frac{1}{2}\left(-\lambda_{1}+\lambda_{2}+2 \lambda_{3}\right) \quad \lambda_{1}-\lambda_{2}-\lambda_{3}=0$

然后将其代入拉格朗日乘子函数，消掉这些变量

$\begin{array}{c} L\left(x_{1}, x_{2}, x_{3}, \lambda_{1}, \lambda_{2}, \lambda_{3}\right)=\frac{1}{4}\left(-\lambda_{1}+2 \lambda_{2}+\lambda_{3}\right)^{2}+\frac{1}{4}\left(-\lambda_{1}+\lambda_{2}+2 \lambda_{3}\right)^{2} \\ +\lambda_{1}\left(\frac{1}{2}\left(-\lambda_{1}+2 \lambda_{2}+\lambda_{3}\right)+\frac{1}{2}\left(-\lambda_{1}+\lambda_{2}+2 \lambda_{3}\right)+x_{3}+1\right) \\ +\lambda_{2}\left(-\left(-\lambda_{1}+2 \lambda_{2}+\lambda_{3}\right)-\frac{1}{2}\left(-\lambda_{1}+\lambda_{2}+2 \lambda_{3}\right)-x_{3}+1\right) \\ +\lambda_{3}\left(-\frac{1}{2}\left(-\lambda_{1}+2 \lambda_{2}+\lambda_{3}\right)-\left(-\lambda_{1}+\lambda_{2}+2 \lambda_{3}\right)-x_{3}+1\right) \\ =-\frac{1}{2} \lambda_{1}^{2}-\frac{5}{4} \lambda_{2}^{2}-\frac{5}{4} \lambda_{3}^{2}+\frac{3}{2} \lambda_{1} \lambda_{2}+\frac{3}{2} \lambda_{1} \lambda_{3}-2 \lambda_{2} \lambda_{3}+\lambda_{1}+\lambda_{2}+\lambda_{3} \end{array}$

原始问题的拉格朗日对偶问题为

$\begin{array}{l} \max _{\lambda_{1},\lambda_{2},\lambda_{3}}-\frac{1}{2} \lambda_{1}^{2}-\frac{5}{4} \lambda_{2}^{2}-\frac{5}{4} \lambda_{3}^{2}+\frac{3}{2} \lambda_{1} \lambda_{2}+\frac{3}{2} \lambda_{1} \lambda_{3}-2 \lambda_{2} \lambda_{3}+\lambda_{1}+\lambda_{2}+\lambda_{3} \\ \lambda_{1}-\lambda_{2}-\lambda_{3}=0,\lambda_{1} \geqslant 0,\lambda_{2} \geqslant 0,\lambda_{3} \geqslant 0 \end{array}$

这里的等式约束是在消掉原始优化变量的过程中引入的

KKT条件

KKT(Karush-Kuhn-Tucker)条件用于求解带有等式和不等式约束的优化问题，是拉格朗日乘数法的推广

KKT条件给出了这类问题取得极值的一阶必要条件，对于如下带有等式和不等式约束的优化问题

$\begin{array}{l} \min _{\boldsymbol{x}} f(\boldsymbol{x}) \\ g_{i}(\boldsymbol{x}) \leqslant 0 \quad i=1，\cdots，q \\ h_{i}(\boldsymbol{x})=0 \quad i=1，\cdots，p \end{array}$

与拉格朗日对偶的做法类似，为其构造拉格朗日乘子函数消掉等式和不等式约束

$L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu})=f(\boldsymbol{x})+\sum_{j=1}^{p} \lambda_{j} h_{j}(\boldsymbol{x})+\sum_{i=1}^{q} \mu_{i} g_{i}(\boldsymbol{x})$

$\lambda$和$\mu$称为 KKT 乘子，其中$\mu_{i} \geqslant 0,i=1,\cdots,q$

原始优化问题的最优解在拉格朗日乘子函数的鞍点处取得，对于$x$取极小值，对于KKT乘子变量取极大值

最优解$x$满足如下条件

$\nabla_{\boldsymbol{x}} L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu})=\mathbf{0} \qquad \mu_{i} \geqslant 0 \qquad \mu_{i} g_{i}(\boldsymbol{x})=0 \qquad h_{j}(\boldsymbol{x})=0 \qquad g_{i}(\boldsymbol{x}) \leqslant 0$

等式约束 $h_{j}(\boldsymbol{x})=0$ 和不等式约束 $g_{i}(\boldsymbol{x}) \leqslant 0$ 是本身应该满足的约束， $\nabla_{\boldsymbol{x}} L(\boldsymbol{x}，\boldsymbol{\lambda}，\boldsymbol{\mu})=\mathbf{0}$ 和拉格朗日乘数法相同

只多了关于 $g_{i}(\boldsymbol{x})$ 以及其对应的乘子变量 $\mu_{i}$ 的方程

$\mu_{i} g_{i}(\boldsymbol{x})=0$

这可以分两种情况讨论

情况一：如果对于某个$k$有

$g_{k}(\boldsymbol{x})<0$

要满足 $\mu_{k} g_{k}(\boldsymbol{x})=0$ 的条件，则有 $\mu_{k}=0$ ，因此有

$\begin{aligned} \nabla_{\boldsymbol{x}} L(\boldsymbol{x},\boldsymbol{\lambda},\boldsymbol{\mu}) & =\nabla_{\boldsymbol{x}} f(\boldsymbol{x})+\sum_{j=1}^{p} \lambda_{j} \nabla_{\boldsymbol{x}} h_{j}(\boldsymbol{x})+\sum_{i=1}^{q} \mu_{i} \nabla_{\boldsymbol{x}} g_{i}(\boldsymbol{x}) \\ & =\nabla_{\boldsymbol{x}} f(\boldsymbol{x})+\sum_{j=1}^{p} \lambda_{j} \nabla_{\boldsymbol{x}} h_{j}(\boldsymbol{x})+\sum_{i=1,i \neq k}^{q} \mu_{i} \nabla_{\boldsymbol{x}} g_{i}(\boldsymbol{x})=\mathbf{0} \end{aligned}$

这意味着第$k$个不等式约束不起作用，此时极值在不等式约束围成的区域内部取得。这种情兄如下左图所示

xxx图KKT 条件中不等式约束的乘子变量各种取值情况

情况二：如果对于某个$k$有

$g_{k}(\boldsymbol{x})=0$

则$\mu_{k}$的取值自由，只要满足大于或等于0即可，此时极值在不等式围成的区域的边界点处取得，不等式约束起作用

这种情况如上右图所示

需要注意的是，KKT条件只是取得极值的必要条件而非充分条件

如果一个最优化问题是凸优化问题，则KKT条件是取得极小值的充分条件

多目标优化问题

前面讲述的优化算法求解的是单目标函数的极值，对于某些应用，需要同时优化多个目标

例如要设计一个方案使得运输速度最快，而运费又最少

这类问题称为多目标优化(Multi-Objective Optimization)问题

基本概念

多目标优化问题有多个目标函数，也称为向量优化，可以形式化地表述为

$\min _{x}\left(f_{1}(\boldsymbol{x}),f_{2}(\boldsymbol{x}),\cdots,f_{p}(\boldsymbol{x})\right) \qquad x \in X$

其中$X$为优化变量的可行域，$p$为目标函数的数量

所有目标函数的值形成一个$p$维向量，因此多目标优化的目标函数是如下的映射

$\mathbb{R}^{n} \rightarrow \mathbb{R}^{p}: f(\boldsymbol{x})=\left(f_{1}(\boldsymbol{x}), \cdots , f_{p}(\boldsymbol{x})\right)^{\mathbf{T}}$

在单目标优化中很容易定义最优解的概念，但在多目标优化问题中最优解的定义更为因难，因为多个目标函数之间可能存在化突，无法使得它们同时达到最优值

一般情况下，不存在一个最优解$x^{*}$使得所有目标函数在该点处取得极小值，各个解之间可能无法比较优劣

如果有两个可行解 $x_{1}$ 和 $x_{2}$ ，对于任意一个目标函数 $f_{i}(\boldsymbol{x})$ 都有

$f_{i}\left(x_{1}\right) \leqslant f_{i}\left(x_{2}\right)$

并且至少存在一个$i$使得

$f_{i}\left(x_{1}\right)<f_{i}\left(x_{2}\right)$

则称 $x_{1}$ 优于 $x_{2}$ ，即在所有其他目标函数的值不增加的前提下至少有一个目标函数的值更小

这一概念的直观解释是帕累托改进(Pareto Improvement)

对于多目标优化问题，在不降低其他所有目标函数的值的情况下，使得至少一个目标函数的值得到改进，称为帕累托改进

有一个可行解 $\boldsymbol{x}^{*}$ ，如果对于可行域中的任意解 $\boldsymbol{x}$ ， $\boldsymbol{x}^{*}$ 都优于 $\boldsymbol{x}$ ，则称 $\boldsymbol{x}^{*}$ 是最优解

最优解是使所有目标函数同时达到最优的解，对于大多数多目标优化问题，最优解是不存在的

对于下面的问题

$\min _{x}\left((x-2)^{2}+1,(x-2)^{2}+15\right)$

此问题存在最优解，为$x=2$，两个目标函数的最小值点刚好重合，如下左图所示，图中下方的曲线为目标函数$(x-2)^{2}+1$，上方的曲线为目标函数$(x-2)^{2}+15$

xxx图多目标优化问题的最优解+帕累托最优解

对于多目标优化问题，如果 $x^{*}$ 是一个可行解并且不存在比 $x^{*}$ 更优的解，则称其为帕累托最优解(Pareto Optimality)

帕累托最优解只是一个不坏的解，且在很多情况下存在多个帕累托最优解

对于如下优化问题

$\min _{x}\left(0.3(x+2)^{2}+1,0.3(x-2)^{2}+1\right)$

其中目标函数

$f_{1}(x)=0.3(x+2)^{2}+1 \qquad f_{2}(x)=0.3(x-2)^{2}+1$

该问题的最优解不存在，区间$[-2,2]$为帕累托最优解，这一区间内的任意两点之间无法比较优劣

对于该区间的两个不同点 $x_{1}$ 、 $x_{2}$ ，若 $x_{1}<x_{2}$ ，则 $f_{1}\left(x_{1}\right)<f_{1}\left(x_{2}\right)$ 而 $f_{2}\left(x_{1}\right)>f_{2}\left(x_{2}\right)$ ，因此这两个点无法比较优劣

对该区间内的任意点$x_{1}$，均不存在其他点优于该点

如果 $x_{1} \in(-\infty,-2)$ ，则总能找到至少一个 $x_{2}$ 使得 $x_{2}$ 优于 $x_{1}$ ，如 $x_{2}=-2$ 即可满足要求

对于$x_{1} \in(-2,+\infty)$有同样的结论，因此这两个区间内的解不是帕累托最优解

该最优化问题的目标函数如上右图所示

图中 $l_{1}$ 曲线为 $0.3(x+2)^{2}+1$ ， $l_{2}$ 曲线为 $0.3(x-2)^{2}+1$

帕累托最优源自经济学，是资源分配的一种理想状态

给定一群人和一些可分配的资源，如果从一种分配状态到另一种分配状态的变化中，在没有使任何人境况变坏的前提下，使得至少一个人变得更好，则称为帕累托改进，帕累托最优的状态是不可能再有帕累托改进的状态

对于多目标优化问题，一种解决思路是找到帕累托最优解的集合，然后从该集合中选择一解作为问题的解

求解算法

求解多目标优化问题的一种思路是转化为单目标优化问题，包括标量化、$\varepsilon$约束法

标量化

标量化根据多个目标函数设计出单个目标函数，使得单目标优化问题的最优解是多目标优化问题的帕傫托最优解

附加要求是对于某些标量化参数，所有帕累托最优解对于单目标优化问题都是可达的

对于不同的标量化参数，会产生不同的帕累托最优解，对于如下优化问题

$\min _{\boldsymbol{x}}\left(f_{1}(\boldsymbol{x})，f_{2}(\boldsymbol{x}),\cdots,f_{p}(\boldsymbol{x})\right),\quad \boldsymbol{x} \in X$

它的标量化问题可以写成下面的形式

$\min _{\boldsymbol{x}} g\left(f_{1}(\boldsymbol{x}),\cdots,f_{1}(\boldsymbol{x}),\boldsymbol{\theta}\right), \qquad \boldsymbol{x} \in X_{\boldsymbol{\theta}}$

在这里， $g$ 是人工设计的标量化函数，以所有目标函数输出值 $f_{1}(\boldsymbol{x})，\cdots，f_{1}(\boldsymbol{x})$ 以及人工设定的参数向量 $\theta$ 作为输人，输出一个标量值

$X_{\theta} \subseteq X$为标量化问题的可行域，由参数$\theta$以及原始的可行域决定

线性标量化是最简单的标量化，通过对多个目标函数线性加权构造出单目标函数，上式最小化问题线性标量化之后变为

$\min _{\boldsymbol{x}} \sum_{i=1}^{p} w_{i} f_{i}(\boldsymbol{x}), \qquad \boldsymbol{x} \in X$

$w_{i}>0$为权重系数，人工设定

除线性标量化之外，还可以用其他函数将多目标函数合并成单目标函数，如加权乘积法

$\varepsilon$约束法

$\varepsilon$约束法只保留一个目标函数，将其他目标函数转化为不等式约束，转化之后的优化问题变为

$\begin{array}{l} \min _{\boldsymbol{x}} f_{j}(\boldsymbol{x}) \\ f_{i}(\boldsymbol{x}) \leqslant \varepsilon_{i},i \in\{1,\cdots, p\} \backslash j \\ \boldsymbol{x} \in X \end{array}$

参数$\varepsilon$由人工设定

其意义是在保证 $f_{i}(\boldsymbol{x}), i \neq j$ 不太差的前提下优化 $f_{j}(\boldsymbol{x})$ ，求解带不等式约束的优化问题可以得到原始问题的解

应用一多目标神经结构搜索

下面介绍多目标优化在神经结构搜索中的应用，神经结构搜索( Neural Architecture Search，NAS)属于自动化机器学习(AutoML)的范畴，其目标是用算法自动设计出神经网络结构，保证神经网络有高的精度

多目标神经结构搜索(Multi-objective Neural Architecture Search，MONAS)的目标则是用算法设计出高精度且计算量小、占用存储空间小的神经网络结构，需要同时满足多个目标

对于有些应用，模型大小、预测时间也非常重要，尤其是对于计算能力弱的平台，如嵌入式系统、移动㟨

对于这些应用场景，NAS筫法需要者虑精度之外的目标，因此需要多目标NAS算法

多目标NAS可抽象为多目标优化问题

一般采用帕累托最优原则来寻找网络结构，多目标NAS算法以此为准则在各种目标之间做出折中优化

这些算法精度之外的其他因素，常用的有下面一些优化指标

神经网络运行时的功耗，对于能量敏感的场景，功耗是核心指标
神经网络运行时的预测时间，也称为延迟
神经网络的参数数量与模型大小，用于限制对存储空间的占用
神经网络预测时的运算量，典型的是FLOPS，即每秒的浮点运算次数

搜索算法可以采用强化学习、遗传算法、贝叶斯优化

它们以神经网络的结构为优化变量，使得优化目标(如神经网络的预测精度)最优化，以此找到最优的神经网络结构

MONAS

MONAS的目标是同时优化神经网络的精度与能耗，或运算量

整体上采用了和NAS类似的方法，由一个称为Robot Network (RN)的网络生成CNN的超参数序列

在评估阶段，训练此$\mathrm{CNN}$，称为Target Network (TN)，以目标网络的精度，能耗作为RN的奖励值，用强化学习算法对RN进行更新

算法每次迭代时得到一个网络结构，取奖励值最高的网络结构作为搜索算法的返回结果

关键的问题是优化目标(即奖励值)的定义

这里考虑了多个指标，包括精度值、栺型预测时的峰值能耗和平均能耗，奖励函数的计算公式为

$\alpha \times \operatorname{ACC}(m)-(1-\alpha) \times \operatorname{Energy}(m)$

其中$A C C$为神经网络的预测精度值，Energy 为神经网络运行时的能耗，$m$是神经网络模型，为算法的优化变量，$0<\alpha<1$为人工设定的权重系数

它的目标是最大化预测精度的同时最小化能耗，以使得此奖励函数最大化

这种目标函数综合考虑了精度值和能耗值，使用线性标量化将多目标优化问题转化为单目标优化问题

MnasNet

MnasNet用加权乘积法将多目标优化问题标量化，同时优化神经网络的精度与预测时间

给定模型$m$，记$A C C(m)$为它对目标任务的精度，$L A T(m)$为其在目标移动设备上的预测延迟(即预测时间)，$T$为目标延迟

对于本任务，模型是帕累托最优的，当且仅当在不增加延迟时其精度是最高的，或者在不降低精度时其延迟是最小的

MnasNet采用加权乘积法逼近帕累托最优解，目标函数定义为

$\begin{array}{c} \max _{m}\left(A C C(m) \times\left(\frac{L A T(m)}{T}\right)^{w}\right) \\ w=\left\{\begin{array}{ll} \alpha, & \operatorname{LAT}(m) \leqslant T \\ \beta, & L A T(m)>T \end{array}\right. \end{array}$

$\alpha$和$\beta$为与应用相关的常数，根据经验设定它们的值，使得在延迟超过指定阈值时目标函数的值更小

泛函极值与变分法

前面提到的优化问题均为求解函数极值，在实际应用中，有一类最优化问题，其优化变量不是数而是函数，称为泛函极值问题

求解这类问题的经典方法是变分法，由于问题的解是函数，因此可以猜测从取得极值的必要条件所导出的是微分方程

泛函与变分

函数是从数集到数集的映射，如实变函数将实数映射为实数，复变函数将复数映射成复数

泛函(Functional, 也称为泛函数)是对函数的拓展，是从函数集到数集的映射

$y(x) \rightarrow \mathbb{R}$

可将函数看作空间中的”点”，称为函数空间(Function Space)，泛函实现从这种”点”到实数集的映射，因此也称为函数的函数(Functions of Functions)

这里的函数集称为泛函的定义域，需要注意泛函与复合函数的区别，前者将函数映射成实数，后者还是一个将实数映射成实数的函数

下面是一个最简单的泛函

$F[y]=\int_{0}^{1} y(x) \mathrm{d} x$

它对函数计算$[0,1]$内的定积分，对于此区间上任意的可积函数$y(x)$都有一个实数积分值

此泛函的定义域为$[0,1]$上可积分函数的全体，值域为实数集$\mathbb{R}$

给定一个可积分函数可以得到它的泛函的值，如果函数为

$y(x)=x^{2}$

其泛函值为

$F[y]=\int_{0}^{1} x^{2} \mathrm{~d} x=\left.\frac{1}{3} x^{3}\right|_{0} ^{1}=\frac{1}{3}$

如果函数为

$y(x)=\mathrm{e}^{x}$

则泛函的值为

$F[y]=\int_{0}^{1} \mathrm{e}^{x} \mathrm{~d} x=\left.\mathrm{e}^{x}\right|_{0} ^{1}=\mathrm{e}-1$

定积分将可积函数映射成实数，因此通常情况下泛函以定积分的形式出现，如下面的泛函

$F[y]=\int_{a}^{b} y(x) \mathrm{d} x$

被积函数中除函数$y(x)$之外，还可以包括其各阶导数

如区间$[a，b]$内曲线$y(x)$弧长的计算公式是一个泛函，其中包含一阶导数

$S[y]=\int_{a}^{b} \sqrt{1+\left(y^{\prime}\right)^{2}} \mathrm{~d} x$

概率论里介绍的数学期望和方差，信息论里介绍的嫡也是泛函，随机变量$X$的数学期望是如下的积分

$E[X]=\int_{-\infty}^{+\infty} x p(x) \mathrm{d} x$

其中$p(x)$为概率密度函数，与函数类似，可以定义泛函的极值，给定一个函数$y_{0}(x)$，如果对于泛函定义域中任意函数$y(x)$都有

$F[y] \geqslant F\left[y_{0}\right]$

则称$y_{0}(x)$为泛函的极小值，如有

$F[y] \leqslant F\left[y_{0}\right]$

则称 $y_{0}(x)$ 为泛函的极大值，如果对于 $y_{0}(x)$ 邻域内的所有 $y(x)$ 都有上上式成立，则称 $y_{0}(x)$ 为泛函的局部极小值

如果上式成立，则称$y_{0}(x)$为泛函的局部极大值，这里的邻域由函数之间的距离来定义

对于定义在区间 $[a,b]$ 内的两个一阶可导函数 $y_{1}(x),y_{2}(x)$ ，它们的距离可以定义为

$\mathrm{d}\left(y_{1}(x)，y_{2}(x)\right)=\max _{a<x<b}\left\{\left|y_{1}(x)-y_{2}(x)\right|,\left|y_{1}^{\prime}(x)-y_{2}^{\prime}(x)\right|\right\}$

这里用两个函数在区间内所有点处的函数值以及导数值的差衡量它们的差异

除此之外，也可以有其他距离定义方式，函数$y_{0}(x)$的$\delta$邻域定义为

$\left\{y(x) \mid \mathrm{d}\left(y(x)，y_{0}(x)\right)<\delta\right\}$

如果定义在区间 $[a，b]$ 内的两个函数 $y(x)$ 与 $y_{0}(x)$ 在 $a$ 和 $b$ 点处函数值相等，则称 $y(x)-y_{0}(x)$ 为函数 $y(x)$ 在 $y_{0}(x)$ 点处的变分(Variation )，记为 $\delta y$

$\delta y=y(x)-y_{0}(x)$

可将变分类比为微分，与微分不同的是，变分是函数变化、自变量不变所导致的变化；而微分则是函数不变、自变量改变所导致的变化

对于大多数实际问题，泛函可以写成如下的一般形式

$F[y]=\int_{a}^{b} L\left(x,y(x),y^{\prime}(x)\right) \mathrm{d} x$

函数$L$称为泛函的核，它包含了函数的自变量$x$，函数本身$y$以及其一阶导数$y^{\prime}$

在这里，$y$是二阶连续可导的函数，$L$对其自变量$x,y,y^{\prime}$二阶连续可导(将函数$y$以及其一阶导数$y^{\prime}$均看作普通的变量

后面的推导中如不作特殊说明均使用这种形式的泛函

欧拉-拉格朗日方程

计算泛函极值点的问题称泛函极值问题，其最优解为函数而不是函数极值问题中的数

以等周问题为例，对于平面内的封闭曲线，在曲线弧长一定的情况下圆的面积最大

假设曲线经过$(-a，0)$和$(a，0)$两点，此问题的约束条件为

$\int_{-a}^{a} \sqrt{1+y^{\prime 2}} \mathrm{~d} x=C$

它限制曲线的弧长，目标泛函为

$F[y]=\int_{-a}^{a} y \mathrm{~d} x$

是曲线$y(x)$与$x$轴所围成的区域的面积，如果$a=2$，此问题的解为半圆弧线，其方程为

$y=\sqrt{4-x^{2}}$

半圆的曲线如下左图所示

xxx图等周问题的半圆曲线+对函数进行扰动

求解泛函极值问题的经典方法是变分法(Calculus of Variations)，其核心是欧拉-拉格朗日方程

在微积分中，通过求解驻点而得到极值点，在泛函中，通过求解变分为0的点而求解泛函的极值，这里的变分类似于函数的导数(微分)

对于下面的泛函

$F[y]=\int_{a}^{b} L\left(x,y(x),y^{\prime}(x)\right) \mathrm{d} x$

通常限定函数$y(x)$在起点和终点处的函数值，称为边界条件

欧拉-拉格朗日方程(Euler-Lagrange Equation，E-L方程)是一个微分方程，给出了泛函取得极值的必要条件

对于上式的泛函，其取得极值的$y(x)$需要满足

$\frac{\partial L}{\partial y}-\frac{\mathrm{d}}{\mathrm{d} x}\left(\frac{\partial L}{\partial y^{\prime}}\right)=0$

式子左边第一项是泛函的核$L$对$y$求偏导，将$y$当作变量；第二项是$L$先对$y^{\prime}$求偏导数，再对$x$求导

解此微分方程即可得到泛函的极值

该方程的作用类似于费马引理所确定的函数极值

需要注意的是，该方程是泛函取得极值的必要条件而非充分条件

下面对一维情况的欧拉-拉格朗日方程进行推导，其思路是将泛函极值问题转化为函数极值问题

对于上上式的泛函，目标是寻找满足边界条件$y(a)=A$、$ y(b)=B$且使得泛函取极值的$y(x)$

假设$L$二阶连续可微，如果$y(x)$使得泛函取极大值，则对$y(x)$的任何扰动都会导致泛函的值变小

对于泛函取极小值的情况则导致泛函的值变大，假设

$g_{\varepsilon}(\boldsymbol{x})=y(\boldsymbol{x})+\varepsilon \eta(x)$

是对$y(x)$扰动后的结果，其中$\varepsilon \eta(x)$是扰动项；$\varepsilon$是一个很小的实数；$\eta(x)$是可微函数且满足$\eta(a)=\eta(b)=0$，以确保扰动之后还满足边界条件

这种随机扰动的原理如上右图所示，图中中间的曲线为扰动之前的函数$y(x)$，最下方的曲线为扰动函数$\varepsilon \eta(x)$，最上方的曲线为扰动之后的函数$y(x)+\varepsilon \eta(x)$，定义泛函

$F_{\varepsilon}=\int_{a}^{b} L\left(x，g_{\varepsilon}(x)，g_{\varepsilon}^{\prime}(x)\right) \mathrm{d} x=\int_{a}^{b} L_{\varepsilon} \mathrm{d} x$

其中 $L_{\varepsilon}=L\left(x，g_{\varepsilon}(x)，g_{\varepsilon}^{\prime}(x)\right)$ ，要保证在 $y(x)$ 点处泛函取得极值，则对它的任何扰动都会导致泛函值变大或变小，因此必定有 $\varepsilon=0$

将上式的泛函看作$\varepsilon$的函数，对$\varepsilon$求导，则在$\varepsilon=0$点处导数值为$0$，由于求导和求积分可以交换次序，有

$\frac{\mathrm{d} F_{\varepsilon}}{\mathrm{d} \varepsilon}=\frac{\mathrm{d}}{\mathrm{d} \varepsilon} \int_{a}^{b} L_{\varepsilon} \mathrm{d} x=\int_{a}^{b} \frac{\mathrm{d} L_{c}}{\mathrm{~d} \varepsilon} \mathrm{d} x$

根据全导数公式有

$\frac{\mathrm{d} L_{\varepsilon}}{\mathrm{d} \varepsilon}=\frac{\partial L_{\varepsilon}}{\partial x} \frac{\mathrm{d} x}{\mathrm{~d} \varepsilon}+\frac{\partial L_{\varepsilon}}{\partial g_{\varepsilon}} \frac{\mathrm{d} g_{\varepsilon}}{\mathrm{d} \varepsilon}+\frac{\partial L_{\varepsilon}}{\partial g_{\varepsilon}^{\prime}} \frac{\mathrm{d} g_{\varepsilon}^{\prime}}{\mathrm{d} \varepsilon}=\frac{\partial L_{\varepsilon}}{\partial g_{\varepsilon}} \frac{\mathrm{d} g_{\varepsilon}}{\mathrm{d} \varepsilon}+\frac{\partial L_{\varepsilon}}{\partial g_{\varepsilon}^{\prime}} \frac{\mathrm{d} g_{\varepsilon}^{\prime}}{\mathrm{d} \varepsilon}=\frac{\partial L_{\varepsilon}}{\partial g_{\varepsilon}} \eta(x)+\frac{\partial L_{\varepsilon}}{\partial g_{\varepsilon}^{\prime}} \eta^{\prime}(x)$

在这里

$\frac{\mathrm{d} g_{e}}{\mathrm{~d} \varepsilon}=\frac{\mathrm{d}(y(x)+\varepsilon \eta(x))}{\mathrm{d} \varepsilon}=\eta(x)$

以及

$\frac{\mathrm{d} g_{\varepsilon}^{\prime}}{\mathrm{d} \varepsilon}=\frac{\mathrm{d}\left(y^{\prime}(x)+\varepsilon \eta^{\prime}(x)\right)}{\mathrm{d} \varepsilon}=\eta^{\prime}(x)$

因此有

$\frac{\mathrm{d} F_{\varepsilon}}{\mathrm{d} \varepsilon}=\int_{a}^{b}\left(\frac{\partial L_{\varepsilon}}{\partial g_{\varepsilon}} \eta(x)+\frac{\partial L_{\varepsilon}}{\partial g_{\varepsilon}^{\prime}} \eta^{\prime}(x)\right) \mathrm{d} x$

由于在$y(x)$点处，即$\varepsilon=0$是泛函的极值点

根据费马引理，在 $\varepsilon=0$ 点处，函数 $F_{\varepsilon}$ 对 $\varepsilon$ 的导数必定为 $0$ ，在 $\varepsilon=0$ 点处 $L_{\varepsilon}=L$ 、 $g_{\varepsilon}=y$ 、 $g_{\varepsilon}^{\prime}=y^{\prime}$ ，因此有

$\left.\frac{\mathrm{d} F_{\varepsilon}}{\mathrm{d} \varepsilon}\right|_{\varepsilon=0}=\left.\int_{a}^{b}\left(\frac{\partial L_{\varepsilon}}{\partial g_{\varepsilon}} \eta(x)+\frac{\partial L_{\varepsilon}}{\partial g_{\varepsilon}^{\prime}} \eta^{\prime}(x)\right) \mathrm{d} x\right|_{\varepsilon=0}=\int_{a}^{b}\left(\frac{\partial L}{\partial y} \eta(x)+\frac{\partial L}{\partial y^{\prime}} \eta^{\prime}(x)\right) \mathrm{d} x=0$

使用分部积分法，上式第二个等式中的第二项为

$\int_{a}^{b} \frac{\partial L}{\partial y^{\prime}} \eta^{\prime}(x) \mathrm{d} x=\int_{a}^{b} \frac{\partial L}{\partial y^{\prime}} \mathrm{d} \eta(x)=\left.\frac{\partial L}{\partial y^{\prime}} \eta(x)\right|_{a} ^{b}-\int_{a}^{b} \eta(x) \frac{\mathrm{d}}{\mathrm{d} x} \frac{\partial L}{\partial y^{\prime}} \mathrm{d} x$

因此有

$\int_{a}^{b}\left(\frac{\partial L}{\partial y}-\frac{\mathrm{d}}{\mathrm{d} x} \frac{\partial L}{\partial y^{\prime}}\right) \eta(x) \mathrm{d} x+\left.\left(\eta(x) \frac{\partial L}{\partial y^{\prime}}\right)\right|_{a} ^{b}=0$

由于有边值条件$\eta(a)=\eta(b)=0$，因此上式左侧第二项的值为0，上式变为

$\int_{a}^{b}\left(\frac{\partial L}{\partial y}-\frac{\mathrm{d}}{\mathrm{d} x} \frac{\partial L}{\partial y^{\prime}}\right) \eta(x) \mathrm{d} x=0$

由于对任意满足边值条件的$\eta(x)$，上式都成立，根据一元函数微积分中证明的结论，有

$\frac{\partial L}{\partial y}-\frac{\mathrm{d}}{\mathrm{d} x} \frac{\partial L}{\partial y^{\prime}}=0$

通常情况下，Euler-Lagrange方程是一个二阶常微分方程，解此方程可以得到泛函的极值点