最优化笔记

[toc]

凸性

集合

凸集

【定义】集合$C\subseteq \mathbb R^n$凸，指的是$\forall x_0,x_1\in C,\forall \theta\in [0,1],(1-\theta)x_0+\theta x_1\in C$。

其中，「$(1-\theta)x_0+\theta x_1$」指的是「$x_1,x_0$两点连接成的线段」，这是一个常用的表述技巧。那么，凸集的定义的人话版本，就是「一个集合中任意两点连接成的线段，也在集合中」。

对于一些凸集 $\{C_i\}_{i\in I}$，以下运算的结果仍然是凸集，这样的运算叫「保凸运算」：

【交】$C=\cup_{i\in I}C_i$是凸集。即：任意个凸集的交集是凸集。这里的「任意个」可以是不可数无穷个。
【直积】$C=C_1\times C_2=\{(\boldsymbol {x_1,x_2})\mid \boldsymbol x_1\in C_1,\boldsymbol x_2\in C_2\}$ 是$\mathbb R^{n_1+n_2}$上的凸集。
【加权和】如果 $C_i$ 都是$\mathbb R^n$上的凸集，$\beta\in \mathbb R$，那么 \[ C=\sum_{i=1}^I \beta_iC_i=\{\beta_1 x_1+\beta_2 x_2+\cdots +\beta_Ix_I,x_i\in C_i\} \] 是凸集。
【仿射】如果$C$是$\mathbb R^n$上的凸集，$A\in \mathbb R^{m\times n},b\in \mathbb R^m$，则$D=\{Ax+b,x\in C\}$是凸集。其实，所谓仿射，也就是线性变换再加上一个平移。

有一些比较常见的凸集，需要知道他们的表示方法：

【超平面】$H=\{x\in \mathbb R^n\mid w^\top x=b\}$，其中$w\in \mathbb R^n,b\in \mathbb R$。称$w$为超平面的法向量。
【半空间】$H=\{x\in \mathbb R^n\mid w^\top x\geq b\}$，也就是一个超平面把空间分成两个半空间（以及超平面自身）
【多面体】$H=\{x\in \mathbb R^n\mid Ax\leq b\}$，也就是有限多个半空间的交集。
【子空间】$L\in \mathbb R^n,\forall x,y\in L,\alpha x+\beta y\in L$.这个和高代里面的子空间是一个意思，也就是元素的线性组合仍在子空间中。
【仿射集/线性流形/仿射子空间】对于子空间$L$，存在$\alpha\in\mathbb R^n$，$M=\alpha+L$，则$M$是仿射集。称$L$的线性维数为$M$的仿射维数，记作$\dim M$。其实就是说，子空间不是必须要通过$0$点吗，那么把子空间平移了以后，它不通过$0$点了，虽然不再是子空间了，但是仍然是线性的，也是凸集。

例如： \[ M=\{x\in R^n\mid Ax=b\}\\\\ L=\{x\in R^n\mid Ax=0\} \] $\alpha$ 为 $Ax=b$ 的任意一个特解。$\dim M=n-\text{rank} A$。所以说，一般来说可以用一个非齐次线性方程组$Ax=b$的解集来表示仿射集。
【球体】$H=\{x\in \mathbb R^n\mid ||x-\alpha||\leq r\}$，其中$||\cdot||$是范数，$\alpha\in\mathbb R^n,r\in \mathbb R$.
【椭球体】$H=\{x\in \mathbb R^n\mid x^\top Ex\leq r\}$，其中$E$是对称正定矩阵，$r\geq 0$。

例如：$S=\{x\in \mathbb R^2\mid x_1^2+ix_1x_2+i^2x_2^2\leq 1\}$

令 \[ E_i=\begin{pmatrix} 1 & \dfrac i2\\ \dfrac i2 & i^2 \end{pmatrix} \] 则$E_i$是对称正定矩阵，且$S=\{x\in \mathbb R^2\mid x^\top E_xx\leq 1\}$，故$S$是凸集。
【凸函数的下水平集】$H=\{x\in S\mid f(x)\leq \alpha\}$，其中$f$是凸函数，$S$是凸集，$\alpha\in R$

还有一类特殊的集合，叫做「锥」。

【定义】称$K\in \mathbb R^n$为「锥形的」，当且仅当$\forall x\in K,\forall \alpha>0,\alpha x\in K$。如果$K$还是凸集，称$K$为「锥」。

常见的锥有：

【第一卦限】$K=\{x\in \mathbb R^n\mid \forall i,x_i>0\}$
【二阶锥】$K=\{x\in \mathbb R^n\mid x_n\geq\sqrt{\sum_{i=1}^{n-1} x_i^2}\}$
【对称矩阵、半正定矩阵、正定矩阵】

集合的内部和闭包

集合的闭包记作$cl X$，指的是集合中的点列的极限的集合。

例如：对于集合$x>0$，点列$1/n$，其极限为$\lim_{n\to \infty} \dfrac 1n=0$，所以$0$在集合$X$的闭包中。

闭包是包含$X$的最小闭集。

集合的内部记作$\text{int} X$，指的是集合中，存在以其为中心的球体也在集合中的点构成的集合。

例如：对于集合$x>0$，对于点$0$，无论半径$r$取何值，球体中的一点$r$总是大于$0$，从而不在集合中，所以$0$不在$X$的内部。

内部是包含在$X$中的最大开集。

但是有时候，对于一个凸集，其内部是空集。比如在$R^3$中的平面。此时，无法用内点来对$X$进行分析，但是就直观来看，$X$并不是一个很「空」的集合。这时候需要定义「相对内部」，也就是在$X$的仿射包中定义$X$的内部。例如，在$R^3$中有一个集合$X$，它是一个圆形。那么它的仿射包就是包含这个圆形的二维平面。在$R^3$中，这个圆形集合的内部是空集。但是如果只在仿射包中看，这个圆形集合的内部就不是空集了。从仿射包看的所谓「内部」，就是「相对内部」。

对于集合$X\in \mathbb R^n$，其仿射包为$M$，定义相对内部： \[ \text{ri }X=\left\{x\in X\mid \exists r_x>0 s.t.\{y\in M\mid ||y-x||_2<r_x)\subseteq X\} \right\} \] 看这个可能很晕。其实就是说，在$X$中存在一些点，它们满足一个条件，这个条件就是「在$M$中存在以这些点为中心的球包含于$X$」。我们把这些点的集合称为$X$的相对内部。相对内部和内部的区别，就是把「球」所存在的空间，从$\mathbb R^n$变成了$X$的仿射包。

组合和包

点$x_1\cdots x_k\in \mathbb R^n$的凸组合指的是： \[ \sum_{i=1}^k \theta_i x_i \] 其中$\theta>0,\sum \theta=1$。有没有发现这个定义特别像前面「凸集定义」的一部分。在二维空间中，凸组合可以看作经过两个点的线段。所以凸集的定义也可以表示为：$C$中的点的凸组合也都属于$C$，那么$C$是凸集。

如果集合$X$不是凸集，那么称包含$X$的最小凸集$C$为$X$的凸包，记作$C=\text{conv} X$。可以证明： \[ \text{conv} X=\left\{\sum_{i=1}^k\theta_ix_i\mid k\in \mathbb Z_{++}，x_i\in X,\sum_{i=1}^k\theta_i=1\right\} \] 看着很复杂，其实就是$X$中的任意有限个点的凸组合的集合。

点$x_1\cdots x_k\in \mathbb R^n$的仿射组合指的是： \[ \sum_{i=1}^k \theta_i x_i \] 其中$\sum \theta=1$.相比于「凸组合」，「仿射组合」只是删去了「$\theta>0$」的条件。在二维空间中，仿射组合相当于经过两个点的直线。

对于仿射包的定义和生成，也和凸包类似。仿射包记作$C=\text{aff} X$。

通过仿射包，可以定义任意集合的维数。对于任意非空集合$X\in \mathbb R^n$，称其仿射包$\text {aff}X$的仿射维数是$X$的仿射维数，记作$\dim X$。

点$x_1\cdots x_k\in \mathbb R^n$的锥组合指的是： \[ \sum_{i=1}^k \theta_i x_i \] 其中$\theta>0$.相比于「凸组合」，「锥组合」只是删去了「$\sum\theta=1$」的条件。在二维空间中，锥组合相当于经过两个点的射线。

对于锥包的定义和生成，也和凸包类似。锥包记作$C=\text{cone} X$。

可以总结一下：

组合类型	系数限制	集合名称	样例
线性组合	无限制	向量子空间	$\mathbb R^n$
仿射组合	$\sum \theta=1$	仿射集/线性流形/仿射子空间	仿射超平面
锥组合	$\theta>0$	锥	第一卦限
凸组合	$\theta>0,\sum \theta=1$	凸集	单纯形

凸函数

梯度和海森矩阵

这俩东西后面有用。

梯度： \[ \nabla f(\boldsymbol{x})=\left[\begin{array}{c} \frac{\partial f}{\partial x_1} \\ \vdots \\ \frac{\partial f}{\partial x_n} \end{array}\right] \] 海森矩阵： \[ \nabla^2 f(\boldsymbol{x})=\left[\begin{array}{ccc} \frac{\partial^2 f}{\partial x_1^2} & \cdots & \frac{\partial^2 f}{\partial x_n \partial x_1} \\ \vdots & \ddots & \vdots \\ \frac{\partial^2 f}{\partial x_1 \partial x_n} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{array}\right] \] 简单理解，梯度就是一阶导，海森矩阵就是二阶导（曲率）。

常见函数的梯度：

$f(x)$	$\nabla f(x)$	$\nabla ^2 f(x)$
$a^\top x$	$a$	$O$
$x^\top Ax$	$(A^\top +A)x$	$A^\top +A$
$r(x)^\top r(x)$，其中$r(x)$是依赖于$x$的$m$维向量，$r(x)^=A$	$2A(x)^\top r(x)$	$2 \sum_{i=1}^m r_i(\boldsymbol{x}) \nabla^2 r_i(\boldsymbol{x})+2 \boldsymbol{A}(\boldsymbol{x})^\top \boldsymbol{A}(\boldsymbol{x})$

凸函数

对于凸集$S$上的函数$f$，如果： \[ f(\theta x_0+(1-\theta)x_1)\leq \theta f(x_0)+(1-\theta)f(x_1) \] 其实就是：函数线上的两点之间的连线，一定在函数线以上。

凸函数的性质有：

函数$f$在凸集$S$上是凸函数，等价于其上镜图是凸集。 \[ \text{epi} f=\{(x,r)\in S\times \mathbb R\mid r\geq f(x)\} \]
函数$f$在凸集$S$上是凸函数，则有Jensen不等式： \[ f\left(\frac{\sum_{i=1}^m \alpha_i \boldsymbol{x}_{\boldsymbol{i}}}{\sum_{s=1}^m \alpha_s}\right) \leq \frac{\sum_{i=1}^m \alpha_i f\left(\boldsymbol{x}_{\boldsymbol{i}}\right)}{\sum_{s=1}^m \alpha_s} \] 其中$x_i\in S,\alpha>0$。

证明：令 \[ \theta_i=\frac{\alpha_i}{\sum_{i=1}^m \alpha_i} \] 因为$f$是凸函数，所以其上镜图是凸集，所以其上镜图上的点的凸组合是在上镜图里，有： \[ \begin{align} &\sum_{i=1}^m\theta_i(x_i,f(x_i))\in \text{epi} f\\ &\to \left(\sum_{i=1}^m \theta x_i,\sum_{i=1}^m \theta_i f(x_i)\right)\in \text{epi} f\\ &\to f\left(\sum_{i=1}^m \theta_i x_i\right)\leq \sum_{i=1}^m \theta_i f(x_i) \end{align} \]
函数$f$在$\mathbb R^n$上凸，当且仅当，$\forall x_0\in \mathbb R^n,\forall d\in \mathbb R^n,\phi(\alpha)=f(x_0+\alpha d)$关于$\alpha$在$\mathbb R$上凸。
函数$f$在凸集$S$上是凸函数，则其在$S$的相对内部上连续。如果有界闭集$K\subset \text{ri }S$，那么$f$在$K$上Lipschitz连续（比一致连续更强的连续）。
函数$f$一阶偏导连续，那么它在凸集$S$上是凸函数，当且仅当 \[ f(y)\geq f(x)+\nabla f(x)^\top (y-x),\forall xy\in S \]
函数$f$二阶偏导连续，那么它在内部非空的凸集$S$上是凸函数，当且仅当$\nabla ^2f(x)$半正定。
函数$f$在凸集$S$上是凸函数，有：$\forall c\in \mathbb R,\{x\in S\mid c\geq f(x)\}$是凸集。即：使得$f(x)$小于一个定值的$x$的取值范围是凸集，这个范围叫做下水平集。
函数$f$在凸集$S$上是凸函数，则$f$的所有局部极小点都是全局极小点，而且局部极小点组成的集合是凸集。如果$f$是严格凸的，那么最多有一个极小点。

和凸集一样，有时候直接确定函数是不是凸函数比较难，因此可以利用保凸运算：

【锥组合】凸函数的锥组合是凸函数。即：对于$\mathbb R^n$上的凸函数$f_i(x)$，$\forall \alpha_i>0$，$F(x)=\sum_i \alpha_if_i(x)$是凸函数。
【仿射替换】对于$\mathbb R^n$上的凸函数$f_i(x)$，$x=Ay+b$是$\mathbb R^m\to\mathbb R^n$的仿射，则$h(y)=f(Ay+b)$是$\mathbb R^m$上的凸函数。
【上确界】对于$\mathbb R^n$上的凸函数$f_i(x)$，$h(x)=\max _{i}f_i(x)$是凸函数。
【单调复合】$f(x)$在$\mathbb R^n$上凸，$h(y)$在$\mathbb R$上凸且单增，则$h(f(x))$在$\mathbb R^n$上凸。

解和算法的基本性质

本节主要讨论无约束最优化问题 \[ \min_{x\in S}f(x) \] 其中$f(x)$是$n$元实函数，$S$是$R^n$的子集（在本章，$S$在大部分情况下就是$R^n$）。

可行方向和一阶条件

优化的基本思想是目标函数沿着某个方向可以看作一元函数，于是就可以利用一元函数的微积分。对于向量$x,d$，如果存在$\bar \alpha$，使得$\forall \alpha\in [0,\bar \alpha],x+\alpha d\in S$，那么称$d$是$x$处的可行方向。此时，多元函数转化为一元函数$\phi(a)=f(x*+ad)$，其导数（方向导数）为： \[ \phi'(a)=\langle \nabla f(x*+ad),d\rangle \] 【一阶必要条件】设$S\subset R^n$，$f$是连续可微的，如果$x*$是局部极小点，那么对于$x*$处的任何可行方向$d$，有： \[ \langle \nabla f(x*),d\rangle\geq 0 \] 梯度向量的方向是函数增长最快的方向，其与可行方向的内积非负，表示从$x*$出发，在所有可行方向上移动，$f(x)$都会增长。

特别的，如果$x*$是$S$的内点，此时所有方向都是可行方向，所以对所有的$d$都有一阶必要条件条件，容易发现这时的一阶必要条件实际上是 \[ \nabla f(x*)=0 \]

对于一元函数来说，它就是「一阶导数为零」。

将满足这种条件的点称为「驻点」。

二阶条件

【二阶必要条件】设$S\subset R^n$，$f$是二阶连续可微的，如果$x*$是局部极小点，那么对于$x*$处的任何可行方向$d$，有：

$\langle \nabla f(x*),d\rangle\geq 0$
如果$\langle \nabla f(x*),d\rangle= 0$，则$d^\top \nabla^2f(x*)d\geq 0$

如果$x*$是集合的内点，这两个条件就变成

$\langle \nabla f(x*),d\rangle= 0$
$\nabla^2f(x*)$半正定

如果$\nabla ^2f(x*)$正定，那么$x*$是严格局部极小点。

线搜索法

线搜索法指的是在当前迭代点处，根据收集到的信息选择一个有待进一步探测的方向，然后在这个方向上进行一维搜索得到合适的步长，进而得到下一个迭代点的过程。后续的梯度下降法、共轭梯度法、牛顿法、拟牛顿法都是线搜索法。

已知初始估计 $\boldsymbol{x}_0, k=0$.设 $\boldsymbol{x}_k$ 处 $\boldsymbol{g}_k=\nabla f\left(\boldsymbol{x}_k\right) \neq \mathbf{0}$ ，则第 $k$ 次迭代:

根据某种近似函数确定设 $\boldsymbol{x}_k$ 处的搜索方向设 $\boldsymbol{d}_{\boldsymbol{k}}$,
线搜索: 求解关于 $\alpha$ 的一元函数极小化问题

\[ \min _\alpha \phi(\alpha)=f\left(\boldsymbol{x}_k+\alpha \boldsymbol{d}_k\right) \]

得到步长 $\alpha_k$

置 $\boldsymbol{x}_{k+1}=\boldsymbol{x}_k+\alpha_k \boldsymbol{d}_k$

不同的线搜索法之所以不同，核心区别在于$\boldsymbol{d}_k$的选取。具体来说，由函数的二次近似 \[ f(x) \approx f\left(\boldsymbol{x}_k\right)+\boldsymbol{g}_k^\top \left(\boldsymbol{x}-\boldsymbol{x}_k\right)+\frac{1}{2}\left(\boldsymbol{x}-\boldsymbol{x}_k\right)^\top \boldsymbol{B}_k\left(\boldsymbol{x}-\boldsymbol{x}_k\right) \] 只要$\boldsymbol{B}_k$正定，那么$\boldsymbol{d}_k$就一定是下降方向。正是不同的$\boldsymbol{B}_k$导致了不同的搜索方向。

所谓的精确线搜索，指的是精确求解$\min _\alpha \phi(\alpha)=f\left(\boldsymbol{x}_k+\alpha \boldsymbol{d}_k\right)$。其重要性质为： \[ \nabla f(\boldsymbol{x}_{k+1})^\top \boldsymbol{d}_k=0 \] 精确线搜索的运算量经常很大，所以大多数情况下都会用非精确线搜索，即不精确求解$\min _\alpha \phi(\alpha)=f\left(\boldsymbol{x}_k+\alpha \boldsymbol{d}_k\right)$，转而使用别的方法确定$\alpha_k$。如果$\alpha_k$的选择不合理，则可能会出现算法无法找到最优解的情况。

对于一元函数$f(x)=x^2$，想要求其最小值。选取初始点$x_0=2$。

左图中有$d_k=-1,\alpha_k=2+\dfrac 3 {2^{k+1}}$，算法收敛于$1$。

右图中有$d_k=(-1)^{k+1},\alpha_k=\dfrac{1}{2^{k+1}}$，算法有两个聚点$1,-1$。

假设$\bar \alpha$是使得$\phi(\alpha)=\phi(0)$，即$f(\boldsymbol{x}+\alpha\boldsymbol{d})=f(\boldsymbol{x})$成立的最小正数，从上述两个例子可以看出，$\alpha$的选择不能太过靠近区间$[0,\bar \alpha]$的两个端点。有一些法则给出了选取$\alpha$需要满足的条件。

Armijo条件

定义一次函数 \[ l(\alpha)=\phi(0)+\rho \phi'(0)\alpha \] 其中$\rho$是由设计者自由选定的参数。于是这个一次函数是一条完全由$\rho$确定的直线，称为「$\rho$线」。

如果$\alpha$对应的函数值在$\rho$线以下，则认为$\alpha$不太大。再选取参数「缩短因子」$\lambda<1$，如果将$\alpha$扩大$\lambda ^{-1}$倍以后，对应的函数值不再在$\rho$线以下，则认为$\alpha$不太小。写成数学表达式，有： \[ \begin{cases} \phi(\alpha) &\leq \phi(0)+\rho \phi^{\prime}(0) \alpha \\ \phi(\alpha / \gamma)&>\phi(0)+\rho \phi^{\prime}(0) \alpha / \gamma \end{cases} \]

Goldstein测验

「不太大」的条件不变，将「不太小」的条件改为： \[ \phi(\alpha) \geq \phi(0)+(1-\rho) \phi^{\prime}(0) \alpha \] 这要求$\rho \in (0,\dfrac 12)$。在上面的图中，也就是两条经过$(0,\phi(0))$的虚线之间的范围，即$[b,c]$。

Wolfe准则

如果$\phi$不是二次函数，则Goldstein测验可能使得真正的极小点不满足条件（看上面的图）。此时仍然保持「不太大」条件不变，把「不太小」条件改为 \[ \phi'(\alpha)\geq \sigma\phi'(0) \] 这就是Wolfe准则。

无约束优化方法

梯度下降法

梯度下降法的基本格式是： \[ \boldsymbol{x}_{k+1}=\boldsymbol{x}_k-\alpha_k \nabla f(\boldsymbol{x}_k) \] 即线搜索法中让$\boldsymbol{d}_k$是$f$在$\boldsymbol{x}_k$处的负梯度。

梯度下降法是怎么想到的呢？其实有两种解释。

函数值在负梯度方向下降最快
极小化函数在$\boldsymbol{x}_k$附近的二次泰勒展开 \[ x_{k+1}=\underset{x\in \mathbb{R}^n}{\arg \min} f\left(\boldsymbol{x}_k\right)+\nabla f\left(\boldsymbol{x}_k\right)^\top \left(\boldsymbol{x}-\boldsymbol{x}_k\right)+\frac{1}{2 \alpha_k}\left\|\boldsymbol{x}-\boldsymbol{x}_k\right\|_2^2 \]

梯度下降法有全局收敛性：假设与初始点 $x_0$ 关联的 $f$ 的下水平集

\[ S=\left\{\boldsymbol{x}: f(\boldsymbol{x}) \leq f\left(\boldsymbol{x}_0\right)\right\} \]

是紧的(有界闭集), 并且 $f$ 在包含 $S$ 的某开集上连续可微. 那么对于步长满足Armijo法则的梯度下降法来说，

迭代轨迹不离开 $S: \boldsymbol{x}_i \in S \forall i$
除非得到驻点；否则 $\left\{f\left(\boldsymbol{x}_i\right)\right\}$ 严格单调递减
轨迹有聚点, 并且每个聚点均是 $f$ 的驻点.

接下来分析$f(\boldsymbol{x})$在满足三种特殊情况的条件下，梯度下降法的复杂性。所谓的复杂性一般指的是一个不等式，衡量了迭代$k$步时，所得到的值有多接近局部极小点。这三种特殊情况分别是：

任何具有Lipschitz（李普希茨）梯度的函数
任何具有李普希茨梯度的凸函数
任何具有李普希茨梯度的强凸函数

在此之前，需要定义「李普希茨梯度」和「强凸函数」。

【Lipschitz梯度】设 $L \geq 0$. 称函数 $f$ 的梯度在开集 $U$ 上是 $L-$ Lipschitz的，如果

\[ \|\nabla f(\boldsymbol{x})-\nabla f(\boldsymbol{y})\| \leq L\|x-y\| \forall x, y \in U . \]

称 $f$ 的梯度在集合 $S$ 上是 $L-$ Lipschitz的，如果存在开集 $U \supseteq S$使得 $f$ 的梯度在开集 $U$ 上是 $L-$ Lipschitz的.

Lipschitz梯度这个名字可能有点容易让人误解。它并不是一种特殊的梯度，而指的是函数的梯度满足某种条件。

如果函数的梯度满足$L-$Lipschitz条件，也称为这个函数是$L-$光滑的。函数是$L-$光滑的等价于函数的Hesse矩阵的谱范数不大于$L$，即： \[ \forall \boldsymbol{x},||\nabla ^2f(\boldsymbol{x})||_2\leq L \] 从直观上来说，$L$-光滑性质保证了函数的梯度的变化速率是受限的，可以理解为函数的斜率在任意两点之间的变化都有一个上界，这使得优化算法在更新变量时，能对目标函数的变化有一定的控制。

【强凸函数】设 $l>0$. 称定义在凸集 $S$ 上的函数 $f($ 关于范数 $\|\cdot\|)$是 $l$ —强凸的(strong convex), 如果对每个 $x_0, x_1 \in S$ 和每个$\theta\in(0,1)$ \[ \quad f\left((1-\theta) x_0+\theta x_1\right) \leq(1-\theta) f\left(x_0\right)+\theta f\left(x_1\right)-\frac{l}{2} \theta(1-\theta)\left\|x_0-x_1\right\|^2 . \] 其实就是比凸函数的定义多了一个$\dfrac{l}{2} \theta(1-\theta)\left\|x_0-x_1\right\|^2 .$

从直观上来说，强凸性是凸性的加强版，它要求函数不仅仅是凸的，还得有一定的曲率（例如：$|x|$不是强凸函数），这样的曲率保证了函数在全局上有唯一的最优解，一般来说，强凸函数的$l$越大，函数的「盆地」越深，优化算法收敛的也越快。

具有Lipschitz（李普希茨）梯度的函数

【二次上界】：设$f$的梯度是L-Lipschitz的，那么： \[ f(\boldsymbol{y}) \leq f(\boldsymbol{x})+\nabla f(\boldsymbol{x})^\top (\boldsymbol{y}-\boldsymbol{x})+\frac{L}{2}\|\boldsymbol{y}-\boldsymbol{x}\|^2 \forall \boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^n . \] 如果设$\phi(\alpha)=f(\boldsymbol{x}+a(\boldsymbol{y-x}))$，则上面的式子可以写作（按项对应）： \[ \phi(1)\leq \phi(0)+\phi'(0)+\frac L2\|\boldsymbol{y-x}\|^2 \] 由二次上界，可以得到关于梯度下降法的两个结论：

对于常数步长$\alpha\in \left(0,\dfrac 2L\right)$，梯度下降法是下降算法
对于常数步长$\alpha\in\left(0,\dfrac 1L\right)$，梯度下降法满足 \[ f\left(\boldsymbol{x}_{s+1}\right) \leq f\left(\boldsymbol{x}_s\right)-\frac{\alpha}{2}\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\|^2 \quad \forall s \geq 0 \]

为了证明这个结论，只需要让二次上界定理中的$\boldsymbol{x}=\boldsymbol{x}_s,y=\boldsymbol{x}_{s+1}=\boldsymbol{x}_s-\alpha_s \nabla f(\boldsymbol{x}_s)$即可。 \[ f\left(\boldsymbol{x}_{s+1}\right)-f\left(\boldsymbol{x}_s\right) \leq \alpha\left(\frac{\alpha L}{2}-1\right)\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\|^2 \quad \forall s \geq 0 \] 当$\alpha\leq \dfrac 2L$，右式为负；当$\alpha\leq \dfrac 1L$，$\dfrac {\alpha L}{2}\leq \dfrac 12$。

由这两个结论，可以推出具有Lipschitz（李普希茨）梯度的函数上梯度下降法的复杂度：

设 $f$ 的梯度是 $L-$ Lipschitz的, 且 $f$ 存在极小点 $\boldsymbol{x}_*$.记 $f_*=f\left(\boldsymbol{x}_*\right)$, 则步长为 $1 / L$ 的 GD 迭代满足

\[ \min _{0 \leq s \leq k-1}\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\| \leq \sqrt{\frac{2 L}{k}\left(f\left(\boldsymbol{x}_0\right)-f_*\right)} \] 这里的「复杂度」是用「前$k-1$步中函数的梯度的最小范数」表示的。当这个范数是零时，意味着找到了驻点。这个范数越小，就越接近驻点。

将$\alpha=1/L$代入$f\left(\boldsymbol{x}_{s+1}\right) \leq f\left(\boldsymbol{x}_s\right)-\dfrac{\alpha}{2}\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\|^2$,有： \[ \frac{1}{2 L}\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\|^2 \leq f\left(\boldsymbol{x}_s\right)-f\left(\boldsymbol{x}_{s+1}\right) \] 对于$s=0\sim k-1$，写出这个不等式然后求和，消除中间的项，有： \[ \begin{align} f(\boldsymbol{x}_0)-f(\boldsymbol{x}_s)&\geq \frac 1{2L}\sum_{s=0}^{k-1}\|\nabla f(\boldsymbol{x}_s)\|^2\\ &\geq \frac k{2L} \min _{0 \leq s \leq k-1}\left\|\nabla f\left(\boldsymbol{x}_s\right)\right\| ^2 \end{align} \] 证毕。

具有李普希茨梯度的凸函数

设 $f$ 是凸函数, 梯度是 $L-$ Lipschitz的, 且 $\boldsymbol{x}_*$ 是它的极小点. 那么步长为 $1 / L$ 的 GD迭代满足

\[ f\left(\boldsymbol{x}_k\right)-f\left(\boldsymbol{x}_*\right) \leq \frac{L\left\|\boldsymbol{x}_0-\boldsymbol{x}_*\right\|^2}{2 k}, k \geq 1 . \] 这里的「复杂度」是用「当前迭代点的函数值和局部极小值的差」表示的。这个差越小，就越接近驻点。

具有李普希茨梯度的强凸函数

关于强凸函数有如下结论：

$f$ 是 $l$ 强凸的当且仅当 $f(\boldsymbol{x})-\frac{l}{2}\|\boldsymbol{x}\|^2$ 是凸的.
设 $f \in C^1$. 则 $f$ 在凸集 $S$ 上是1强凸的当且仅当

\[ f(\boldsymbol{y}) \geq f(\boldsymbol{x})+\nabla f(\boldsymbol{x})^\top (\boldsymbol{y}-\boldsymbol{x})+\frac{l}{2}\|\boldsymbol{y}-\boldsymbol{x}\|^2, \quad \forall \boldsymbol{x}, \boldsymbol{y} \in S . \]

设 $f \in C^2$. 则 $f$ 在内部非空的凸集 $S$ 上是 $l$-强凸的当且仅当

\[ \nabla^2 f(\boldsymbol{x}) \succeq l \boldsymbol{I}, \quad \forall \boldsymbol{x} \in S . \]

设 $f$ 是 $l$-强凸的, 它的梯度是 $L-$ Lipschitz的, 且 $\boldsymbol{x}_*$ 是 $f$ 的极小点. 那么步长为 $1 / L$ 的 GD迭代满足

\[ \left\|\boldsymbol{x}_k-\boldsymbol{x}_*\right\|^2 \leq\left(1-\frac{1}{k}\right)^k\left\|\boldsymbol{x}_0-\boldsymbol{x}_*\right\|^2 \quad \forall k \geq 1, \]

其中 $\kappa=L / l$.

牛顿法

考虑二次连续可微的函数，对其进行泰勒展开： \[ f(x)\approx q_k(x)=f(\boldsymbol{ x_k})+(\boldsymbol{x-x_k})^\top \nabla f(\boldsymbol{x_k})+\dfrac 12 (\boldsymbol{x-x_k})^\top \nabla^2f(\boldsymbol{x}_k)(\boldsymbol{x-x_k}) \] 当$\nabla^2f(x_k)$正定时，$q_k$有唯一极小点。将极小点作为新迭代，由此得到基本牛顿法： \[ \boldsymbol{x_{k+1}}=\boldsymbol {x}_k-(\nabla ^2f(\boldsymbol{x}_k))^{-1}\nabla f(\boldsymbol x_k) \] 关于牛顿法，有二次收敛定理：假设 $\nabla^2 f(\boldsymbol{x})$ 在 $\mathbb{R}^n$ 上是 $M$-Lipschitz的，且局部极小点 $x_*$ 处的Hesse矩阵 $\nabla^2 f\left(x_*\right)$ 正定, 即存在 $l>0$ 使得 $\nabla^2 f\left(x_*\right) \geqslant l I$. 如果初始点 $x_0$ 满足

\[ \left\|x_0-x_*\right\| \leq \frac{l}{2 M} \]

那么 $\forall k \geq 0$, 牛顿法是良定义的, 且由它产生的序列至少二次收敛到 $\boldsymbol{x}_*$.

但是在使用上，基本牛顿法存在一些问题。

$\nabla^2f(x_k)$正定，但是牛顿增量很大，导致局部二次近似失效
$\nabla f(x_k)$不正定

在这两种情况下，基本牛顿法会失效，因此需要寻求将其修正的方法。常用方法是对于$\epsilon_k>0$，取 \[ M_k=[\nabla^2f(x_k)+\epsilon_kI]^{-1} \] 计算$\nabla^2f(x_k)$的特征值，设$\epsilon_k$是让$[\nabla^2f(x_k)+\epsilon_kI]$特征值大于常数$\delta$的最小非负整数，然后沿方向 \[ d_k=-M_k\nabla f(x_k) \] 进行线搜索。

共轭梯度法

【定义：$G-$正交/共轭】已知对称正定矩阵$G$，定义两个向量的$G-$内积： \[ \langle\boldsymbol{u}, \boldsymbol{v}\rangle_G=\boldsymbol{u}^\top \boldsymbol{G} \boldsymbol{v} \] 如果两个向量的$G-$内积为$0$，则称其为$G-$正交或者$G-$共轭向量。

共轭方向法的提出是为了求解正定的非齐次线性方程组： \[ Gx=b \] 其等价于下面的优化问题： \[ \arg\min \frac 12 x^\top Gx-b^\top x \] 求解的步骤如下：

给定初始点$x_0$和共轭方向$\{d_0,d_1\cdots,d_{n-1}\}$，令： \[ x_{k+1}=x_k+\alpha_kd_k \] 其中， \[ \begin{align} \alpha_k=\arg\min\phi(\alpha):= f(x_k+\alpha d_k) \end{align} \] 即求解： \[ \phi'(\alpha)=0 \] 有： \[ \begin{align} \phi'(\alpha)&=\nabla f(x_k+\alpha d_k)^\top d_k\\ &=(G(x_k+\alpha d_k)+c)^\top d^k\\ &=(Gx_k+c)^\top d_k+\alpha d_k^\top Gd_k \end{align} \] 那么有： \[ \alpha=-\frac{(Gx_k+c)^\top d_k}{d_k^\top Gd_k}=-\frac{\nabla f(x_k)^\top d_k}{d_k^\top Gd_k} \] 将共轭方向组写成矩阵：$S=\{d_0,\cdots,d_{n-1}\}$那么有：

$S$可逆（因为$d$是线性无关组）
$S^\top GS$是对角矩阵，对角线元素是$d_i^\top Qd_i$，其余是零（因为$d$是共轭方向组）
$I=S^{-1}\{d_0,\cdots,d_n\}$，即$S^{-1}d_i=e_i$，其中$e_i$是第$i$个分量为一，其余分量是零的单位坐标向量

设： \[ x=S\hat x,\ \hat x=S^{-1}x \] 则有： \[ \hat f(\hat x)=\frac 12 \hat xS^\top GS\hat x+(S^\top c)^\top \hat x \] 因为$S^\top GS$是对角阵，所以这是一个变量可分离的二次函数。

考虑迭代出的最终$x$： \[ \begin{align} x^*&=x_0+\alpha_0d_0+\alpha_1d_1+\cdots+\alpha_{n-1}d_{n-1}\\ \hat x^*&=S^{-1}x_0+\alpha_0S^{-1}d_0+\alpha_1S^{-1}d_1+\cdots+\alpha_{n-1}S^{-1}d_{n-1}\\ &=S^{-1}s_0+\alpha_0e_0+\alpha_1e_1+\cdots+\alpha_{n-1}e_{n-1} \end{align} \] 即：在$x$空间的共轭方向法，实际上就是在$\hat x$空间按坐标轴搜索，而且在$\hat x$空间的$\hat f$函数是变量可分离的二次函数。于是，点列$\{x_k\}$有如下特征：

$\nabla f(x_k)^\top d_i=0,i=1,\cdots,k-1$
$x_k=\arg\min \left\{\dfrac 12x^\top Gx+c^\top x,x\in X^k\right\}$，其中，$X^k$是共轭方向组的前$k$个向量张成的线性子空间，平移$x_0$后得到的仿射空间。

共轭方向法的问题是在求解前需要给出共轭方向组。共轭梯度法则是利用梯度构造共轭方向组。共轭梯度法的基本结构如下：

给定初始点$x_0$，记$d_0=-\nabla f(x_0)$，开始迭代
如果函数梯度已经足够小，即$\|\nabla f(x_k)\|\leq \epsilon$，终止
计算： \[ \alpha=-\frac{(Gx_k+c)^\top d_k}{d_k^\top Gd_k}=-\frac{\nabla f(x_k)^\top d_k}{d_k^\top Gd_k} \]
令$x_{k+1}=x_k+\alpha_kd_k$，计算$d_{k+1}$，使得它和之前的所有方向都共轭。 \[ d_{k+1}=-\nabla f(x_{k+1})+??? \]

现在的问题就是$d_k$怎么算。可以借助矩阵理论中的施密特正交化方法，容易想到，$???$其实是在之前的方向的线性组合，即： \[ d_{k+1}=-\nabla f(x_{k+1})+\sum_{i=0}^k \beta_id_i \] 有： \[ \left(-\nabla f(x_{k+1})+\sum_{i=0}^k \beta_id_i\right)^\top Gd_i=0,\forall i=0,\cdots,k \] 因为共轭性，其它项都一定是零，即： \[ (-\nabla f(x_{k+1})+\beta_id_i)^\top Gd_i=0 \] 有： \[ \beta_i=\frac{\nabla f(x_{k+1})^\top Gd_i}{d_i^\top Gd_i},i=0,\cdots,k \] 注意到：$i\neq k$时，$\beta_i=0$

分析分子$\nabla f(x_{k+1})^\top Gd_i$，因为$\alpha_id_i=x_{i+1}-x_i$，有： \[ \begin{align} Gd_i&=G(x_{i+1}-x_i)\frac 1{\alpha_i}\\ &=(\nabla f(x_{i+1})-\nabla f(x_i))\frac 1{\alpha_i} \end{align} \] 代入： \[ \nabla f(x_{k+1})^\top Gd_i=\nabla f(x_{k+1})(\nabla f(x_{i+1})-\nabla f(x_i))\frac 1{\alpha_i} \] 因为 \[ d_{i+1}=-\nabla f(x_{i+1})+\sum_{i=1}^i \beta_j d_j \] 所以 \[ \nabla f(x_{i+1})=-d_{i+1}+\sum_{i=1}^i \beta_j d_j \] 因为$\nabla f(x_k)^\top d_i=0,i=1,\cdots,k-1$

所以$i\neq k$时，$\beta_i=0$

所以有： \[ d_{k+1}=-\nabla f(x_{k+1})+\frac{\nabla f(x_{k+1})Gd_k}{d_k^\top Gd_k}d_k \] 而且，步长公式可以化简为： \[ \alpha=-\frac{\nabla f(x_k)^\top d_k}{d_k^\top Gd_k}=\frac{\nabla f(x_k)^\top \nabla f(x_k)}{d_k^\top Gd_k} \] 进一步简化$\beta_k$:

\[ \begin{align} \beta_k&=\frac{\nabla f(x_{k+1})^\top Gd_k}{d_k^\top Gd_k}\\ &=\frac 1{\alpha_i} \frac{\nabla f(x_{k+1})^\top (\nabla f(x_{k+1})-\nabla f(x_k))}{d_k^\top Gd_k}\\ &=\frac{d_k^\top Gd_k}{\nabla f(x_k)^\top \nabla f(x_k)}\frac{\nabla f(x_{k+1})^\top (\nabla f(x_{k+1})-\nabla f(x_k))}{d_k^\top Gd_k}\\ &=\frac{\nabla f(x_{k+1})^\top \nabla f(x_{k+1})}{\nabla f(x_{k})^\top \nabla f(x_{k})}\\ \end{align} \]

这个简化的目的是排除原问题$\arg\min \frac 12 x^\top Gx-b^\top x$的影响，以便适用于任何函数（但是这时$\alpha$只能改用其它精确线搜索法）

共轭梯度法的过程如下：

次梯度

为了讨论次梯度和次微分，引入扩展实值函数：

设 $S \subseteq \mathbb{R}^n, f: S \rightarrow[-\infty,+\infty]$. 称

\[ \{(\boldsymbol{x}, r): \boldsymbol{x} \in S, r \in \mathbb{R}, r \geq f(x)\} \]

是 $f$ 的上镜图(epigraph),记作$\text{epi} f$. 如果$\text{epi} f$是 $\mathbb{R}^{n+1}$ 中的凸集，称 $f$ 是 $S$ 上的凸函数. 称 $\mathrm{epi} f$ 在 $\mathbb{R}^n$ 上的投影是 $f$ 在 $S$ 上的有效域(effective domain), 记作$\text{dom} f$ 。

简单来说，上镜图就是函数图像上面的部分，有效域就是函数的「定义域」。

如果凸函数满足有效域非空，且$\forall x,f(x)>-\infty$，那么称这个函数为「正常凸函数」，这个假设叫做「正常假设」。

设函数$f$在凸集$S$上凸，则其扩展实值表示为： \[ \tilde{f}(\boldsymbol{x})=\left\{\begin{array}{cc} f(\boldsymbol{x}), & \text { 如果 } \boldsymbol{x} \in S \\ +\infty, & \text { 否则 } \end{array}\right. \] 从这个函数可以看出有效域和定义域的区别，在这里，定义域是$R^n$，有效域是$S$。

【次梯度】称向量 $\boldsymbol{g}$ 是凸函数 $f: \mathbb{R}^n \rightarrow(-\infty,+\infty]$ 在点 $\boldsymbol{x}$ 的次梯度(subgradient), 如果

\[ f(\boldsymbol{y}) \geq f(\boldsymbol{x})+\boldsymbol{g}^\top (\boldsymbol{y}-\boldsymbol{x}), \quad \forall \boldsymbol{y} \in \mathbb{R}^n . \]

$f$ 在 $x$ 的次梯度的全体称作 $f$ 在 $x$ 处的次微分(subdifferential),记作 $\partial f(x)$. 如果 $\partial f(x) \neq \varnothing$, 称 $f$ 在 $x$ 处次可微 (subdifferentiable).

其中$h(\boldsymbol{y})=f(\boldsymbol{x})+\boldsymbol{g}^\top (\boldsymbol{y}-\boldsymbol{x}), \quad$是一个关于$\boldsymbol{y}$的仿射函数，次梯度中不等式的含义，就是这个仿射函数的图像是$f$上镜图$\text{epi} f$在点$(x,f(x))$处的非竖直支撑超平面。

示意图

其中$g_1,g_2$是$f$在$x_1$处的次梯度，$g_3$是$f$在$x_2$处的次梯度。

对于凸函数$f$，$x\in \text{dom}f$，如果$f$在$x$处可微，那么$\partial f(x)=\{\nabla f(x)\}$，反之，如果$f$在$x$处的次梯度唯一，那么$f$可微。

设 $f$ 是凸函数. 那么 $\forall \boldsymbol{x}, \partial f(\boldsymbol{x})$ 是闭凸集. 对于 $\boldsymbol{x} \notin \operatorname{dom} f, \partial f(\boldsymbol{x})=\emptyset$. 对于 $\boldsymbol{x} \in \operatorname{ri}(\operatorname{dom} f), \partial f(\boldsymbol{x})$ 非空, 这时 $f$ 沿方向 $\boldsymbol{d}$ 的方向导数存在，并且

\[ f^{\prime}(\boldsymbol{x} ; \boldsymbol{d})=\max _{\boldsymbol{g} \in \partial f(\boldsymbol{x})} \boldsymbol{d}^\top \boldsymbol{g} \]

最后， $\partial f(\boldsymbol{x})$ 是非空有界闭凸集当且仅当 $\boldsymbol{x} \in \operatorname{int}(\operatorname{dom} f)$.此时对每个 $d, f^{\prime}(\boldsymbol{x} ; \boldsymbol{d})$ 有限.

如果忘了，这里的$\text{ri}$是「相对内部」，$\text{int}$是「内部」。

最优性条件:设 $f: \mathbb{R}^n \rightarrow(-\infty,+\infty]$ 是凸的.

则 $\boldsymbol{x}_*$ 是 $f$ 的极小点当且仅当 $0 \in \partial f\left(\boldsymbol{x}_*\right)$.
设 $C \subseteq \mathbb{R}^n$ 是非空凸集，则 $x_*$ 是 $f$ 在 $C$ 上的极小点的充分条件是：存在 $\boldsymbol{u} \in \partial f\left(\boldsymbol{x}_*\right)$ 使得 $-\boldsymbol{u} \in N_C\left(\boldsymbol{x}_*\right)$ 。如果ri $(\operatorname{dom} f)$ 与 ri $C$ 相交, 或者当 $C$ 是多面体时 ri( $\operatorname{dom} f)$ 与C相交, 该条件是必要的.

约束优化问题（KKT条件）

【特别注意】课件和PPT里的KKT条件和拉格朗日函数，$\lambda$是乘以等式约束$h$的，$\mu$是乘以不等式约束$g$的，我这个笔记一开始写错了，后来将错就错，全部是相反的。

考虑有如下格式的优化问题： \[ \begin{align} \text{minimize}\ \ &f(x)\\ \text{s.t.}\ \ &h_i(x)=0,i=1,\cdots,m\\ &g_i(x)\leq 0,i=1,\cdots,l\\ &x \in X \end{align} \] 其中，所有的$f,g_i,h_i$都是可微的。$h_i(x)$称为等式约束、$g_i(x)$称为不等式约束、$X$称为集合约束。

把常用的不可微分函数转变为可微分函数的技巧：

$\max\{f,g\}\leq 0\to f\leq0$且$g\leq 0$

$\min\{f,g\}\geq 0 \to f\geq 0$且$g\geq 0$

$|f|=\max\{-f,f\}$

假如$x*$是问题的局部最优解，而且在$x*$处满足某个「适当的条件」，则存在$\lambda,\mu$使得： \[ \begin{align} \nabla f(x^*)+\sum_{i=1}^m \lambda_i \nabla g_i(x^*)+\sum_{i=1}^l \mu_i\nabla h_i(x^*)&=0\\ \lambda_i&\geq 0\\ g_i(x^*)&\leq 0\\ h_i(x^*)&= 0\\ \lambda_ig_i(x^*)&=0 \end{align} \] 这一组条件被称为KKT条件。为了对KKT条件建立一个直观印象，有：

考虑如图所示的二维平面优化问题。红色的曲线是三个约束函数$g_i(x)\leq0$的$0$等值线，绿色虚线是$f(x)$等值线，在最左边这个点取到最小值。那么，在这个点，观察三条蓝色的向量。可以发现，$-\nabla f$即$f$的负梯度应当是$\nabla g_1,\nabla g_2$的线性组合，而且组合系数都是正数。这就是KKT条件的第一条式子的来历。我们发现，$g_3(x)\leq0$这个条件目前并没有「起作用」，所以它的梯度对应的线性组合系数是零。KKT条件的第五条式子，即 \[ \lambda_ig_i(x^*)=0 \] 正是在标记哪些条件在「起作用」。如果起作用了，那么$\lambda_i\geq 0,g_i(x^*)=0$；否则，如果没起作用，那么$g_i(x^*)\neq0$，此时有$\lambda_i=0$。我们管「起作用」了的约束条件叫做「积极约束」。用记号： \[ A(x^*)=\{j\mid g_j(x^*)=0,j=1,\cdots,l\} \] 表示积极约束（的标号）的集合。

KKT条件是「一阶必要条件」，即凡是局部最优解都满足KKT条件，但是满足KKT条件的不一定是局部最优解。

简单介绍一下证明KKT条件的思路：

如果$x^*$是局部最优解，那么$D(x^*)\cap T(x^*)=\emptyset$。其中，$D,T$都是一些方向的集合。

$D$是使得目标函数下降的方向的集合，即和目标函数的梯度的内积小于零： \[ D(x^*)=\{d\mid \nabla f(x^*)d\leq 0\} \] $T$是「切向锥」,即从$x^*$开始，往哪些方向稍微挪动一点，不会离开可行域的范围： \[ T(x^*)=\left\{\alpha d\mid \alpha>0,d=\lim_{k\to \infty}\frac{x_k-x^*}{\|x_k-x^*\|}\mid x_k\to x^*\right\} \]

因为$T$很难求，所以另外定义一个「看起来像可行的方向的集合」 \[ F_1(x^*)=\{d\mid \nabla g_i(x)^\top d\leq 0,\nabla h_j(x)^\top d=0\mid i\in A(x^*) ,j=1,\cdots,l\} \] 构造它的方法是「排除显然不可能的方向」，例如，让$g_i(x)$上升的方向（$\nabla g_i(x)^\top d>0$）以及让$h_i(x)$变化的方向$\nabla h_i(x)^\top d\neq 0$

在某些「适当的条件」下，有$T(x^*)=F_1(x^*)$。此时，有： \[ D(x^*)\cap F_1(x^*)=\emptyset \] 这其实是KKT条件的某种等价表述。

之前提到的那个「适当的条件」叫做「约束品性」，常见的约束品性有：

正则性（线性无关约束品性，LICQ）：设点$x^*$满足$h(x^*)=0,g(x^*)\leq 0$，对于$x^*$处的所有$h$和积极约束$g$，如果梯度向量$\nabla h_1(x^*),\cdots,\nabla h_n(x^*),\nabla g_j(x^*),j\in A(x^*)$是线性无关的，称$x^*$是约束$h(x^*)=0,g(x^*)\leq 0$的正则点。如果$x^*$是局部最优解而且是正则点，那么KKT条件成立。
Slater条件。若Salter条件成立，原问题的最优解是KKT点，相应的乘子是对偶问题的最优解。
MFCQ：如果$x*$是集合约束$X$的内点且是局部极小点、$f,g,h$都是一阶连续函数、如果梯度$\nabla h_1(x^*),\cdots,\nabla h_n(x^*)$线性无关，且存在向量$d$使得 \[ \nabla h_i(x^*)^\top d=0,\nabla g_j(x^*)^\top d<0,\forall i=1\sim n,j\in A(x^*) \] 则$x^*$ 满足MFCQ。
线性CQ：如果$x*$是集合约束$X$的内点且是局部极小点，$f,g$都是一阶连续函数，如果$h$是仿射函数、$g_j$都是凸函数，那么$x*$满足KKT条件。

如果满足：

$f,g_i$都是凸函数
$h_i$是线性函数

那么，原问题是凸问题，而且KKT点就是全局最优点。

现在的问题是，这两个条件实在是太强了，有没有弱一点的条件，也能说明KKT点是最优点？

二阶必要条件

假设对于KKT点$x^*$： \[ \begin{align} \nabla f(x^*)+\sum_{i=1}^m \lambda_i \nabla g_i(x^*)+\sum_{i=1}^l \mu_i\nabla h_i(x^*)&=0\\ \lambda_i&\geq 0\\ g_i(x^*)&\leq 0\\ h_i(x^*)&= 0\\ \lambda_ig_i(x^*)&=0 \end{align} \] 考虑一个函数： \[ L(x,\lambda,\mu)=f(x)+\sum_{i=1}^m \lambda_ig_i(x)+\sum_{i=1}^l \mu_ih_i(x) \] 注意，因为满足了KKT条件，所以这个函数里面只有$x$是变量，$\lambda,\mu$都是常量。这个函数$L(x)$有什么性质？

$\nabla L(x^*)=0$。这就是KKT条件的第一条
$L(x^*)=f(x^*)$。因为KKT条件的第五条，所以第二项是零；因为KKT条件的第四条，所以第三项是零。
$\forall x\in S,L(x)\leq f(x)$，其中$S$是原问题的可行解集。因为在可行解集里总有$\sum_{i=1}^m \lambda_ig_i(x)\leq 0$。

由2和3知：如果$x^*$的$L(x)$的最优解（最小值），那么$x^*$是原问题的最优解。

对于无约束问题$\text{minimize}\ \ L(x)$，其二阶条件有：

$\nabla^2L(x)$半正定，那么$x^*$是原问题的全局最优解
$\nabla ^2L(x)$在$S$中的一个$x^*$的邻域里半正定，那么$x^*$是原问题的局部最优解
$\nabla^2L(x^*)$正定，那么$x^*$是原问题的严格局部最优解。

接下来重点考虑第三项。正定，也就是说有二次型： \[ d^\top \nabla^2L(x^*)d>0,\forall d \] 那么这个条件能不能再弱一点呢？这个二次型或许不需要对任何$d$都正定。回忆证明KKT条件时用的的$F_1(x^*)$集合，它是「看起来像可行的方向的集合」。只要$d$看起来不是可行方向，那么就可以不考虑这个$d$。于是，有： \[ d^\top \nabla^2L(x^*)d>0,d\in F_1(x^*) \] 那么这个条件能不能再再弱一点呢？对于大于$0$的$\lambda_i,i\in A(x^*)$，如果$\nabla g_i(x^*)^\top d< 0$，则$x*$沿着$d$移动，会导致$g_i(x)$小于零，而这意味着目标函数的值上升。定义 \[ F_2(x^*)=\{d\mid \nabla g_i(x)^\top d= 0,\nabla h_j(x)^\top d=0\mid i\in A^+(x^*) ,j=1,\cdots,l\} \] 其中， \[ A^+(x^*)=\{j\mid g_j(x^*)=0,\lambda_j\neq0,j=1,\cdots,l\} \] 二阶必要条件的最终表述为：

假如$x^*$满足KKT条件，$\lambda,\mu$为相应的乘子， \[ L(x,\lambda,\mu)=f(x)+\sum_{i=1}^m \lambda_ig_i(x)+\sum_{i=1}^l \mu_ih_i(x) \] $\nabla L(x^*)=0$，若$d^\top \nabla^2L(x^*)d>0,\forall x\in F_2(x^*)$，则$x^*$是原问题的严格最优解。

灵敏度分析

对于一般的约束问题$(P)$，有局部正则点$x^*$，加入松弛变量$(c,d)$: \[ \begin{align} \text{minimize}\ \ &f(x)\\ \text{s.t.}\ \ &h_i(x)=c,i=1,\cdots,m\\ &g_i(x)\leq d,i=1,\cdots,l\\ &x \in X \end{align} \] 设函数$p(c,d)=f(x(c,d))$，即在加入松弛变量后，问题的最优值关于松弛变量的函数。则有： \[ \nabla_c p(0,0)=-\mu,\nabla_dp(0,0)=-\lambda \]

【例】问题 \[ \begin{align} \text{minimize}\ \ &\dfrac{1}{2}(x_1^2+x_2^2)-x_2\\ s.t.\ \ &x_2=c \end{align} \] 原问题的最优解显然是$(0,0)$，此时等式约束对应的系数$\mu=1$新问题的最优解是$(0,c)$，那么有 \[ p(c)=-\dfrac12 c^2-c \] 对C求导，有： \[ p'(0)=-1=-\mu \]

对偶问题

考虑一般的约束问题$(P)$: \[ \begin{align} \text{minimize}\ \ &f(x)\\ \text{s.t.}\ \ &h_i(x)=0,i=1,\cdots,m\\ &g_i(x)\leq 0,i=1,\cdots,l\\ &x\in X \end{align} \] 记录可行集，即满足所有约束条件的集合为$S$。

如果$(P)$问题比较难于求解，例如$(P)$是非凸问题，我们试图寻找一个和$(P)$关系紧密，又比较简单的问题$(D)$。

引入拉格朗日函数： \[ L(x,\lambda,\mu)=f(x)+\sum_{i=1}^m \lambda_ig_i(x)+\sum_{i=1}^l \mu_ih_i(x) \] 和对偶函数，即在集合约束满足的前提下对拉格朗日函数求最小值： \[ d(\lambda,\mu)=\min_{x\in X}\left\{f(x)+\sum_{i=1}^m \lambda_ig_i(x)+\sum_{i=1}^l \mu_ih_i(x)\right\} \] 给一组$\lambda,\mu$，在$X$里面就有一个$L(x,\lambda,\mu)$的最小值；给另一组$\lambda,\mu$，就会对应另一个最小值，这样一来，我们把这个最小值写成$\lambda,\mu$的函数$d(\lambda,\mu)$。接下来研究 $d$ 函数的特征，有： \[ \begin{align} \forall \lambda,\mu,\lambda>0,d(\lambda,\mu)&=\min_{x\in X}\left\{f(x)+\sum_{i=1}^m \lambda_ig_i(x)+\sum_{i=1}^l \mu_ih_i(x)\right\}\\ &\leq \min_{x\in S}\left\{f(x)+\sum_{i=1}^m \lambda_ig_i(x)+\sum_{i=1}^l \mu_ih_i(x)\right\}\\ & \leq \min_{x\in S}\left\{f(x)\right\}=v(P) \end{align} \] 其中，$v(P)$表示$(P)$问题的最优值，即$(P)$问题最优值的下界。由此，我们可以说，$d(\lambda,\mu)$是对$(P)$问题的下界的估计。对下界的估计必然是越大越好，于是，有： \[ \begin{align} \text{maximize}\ \ &d(\lambda,\mu)\\ \text{s.t.}\ \ &\lambda_i\geq 0,i=1,\cdots ,m \end{align} \]

我们把这个问题叫做「对偶问题」，记作$(D)$。因为对偶函数$d$一定是一个凹函数，所以极大化凹函数的对偶问题一定是一个凸问题。接下来分析一下对偶问题和原问题的关系。对偶问题可以写作： \[ \max_{\lambda\geq 0,\mu}\min_{x\in X}L(x,\lambda,\mu) \] 如果我们把两个求最值换一下顺序： \[ \min_{x\in X}\max_{\lambda\geq 0,\mu}L(x,\lambda,\mu) \] 其中，$\max_{\lambda>0,\mu}L(x,\lambda,\mu)$是很容易取到正无穷的。因为如果$g(x)>0$，因为$\lambda$无上界，所以可以取到正无穷。如果$h(x)\neq0$，因为$\mu$无上下界，所以也可以取到正无穷。那么有： \[ \max_{\lambda>0,\mu}L(x,\lambda,\mu)=\begin{cases} f(x),&g_i(x)\leq 0,h_i(x)=0\\ +\infty,&\text{otherwise} \end{cases} \] 然后求外层的最小值，显然我们不关心正无穷的情况，那么有： \[ \begin{align} \text{minimize}\ \ &f(x)\\ \text{s.t.}\ \ &h_i(x)=0,i=1,\cdots,m\\ &g_i(x)\leq 0,i=1,\cdots,l\\ &x\in X \end{align} \] 我们发现，这就是原问题$(P)$。

【例】考虑线性规划问题： \[ \begin{align} \text{minimize}\ \ &c^\top x\\ \text{s.t.}\ \ &Ax=b\\ &-x\leq 0\\ &x\in \mathbb R^n \end{align} \]

\[ L(x,\mu)=c^\top x+\mu^\top (b-Ax) \]

\[ d(\mu)=\min_{x\geq0}\{(c-A^\top \mu)^\top x+b^\top \mu\} \]

有： \[ d(\mu)=\begin{cases} b^\top \mu,&c-A^\top \mu\geq 0\\ -\infty,&\text{otherwise} \end{cases} \] 对偶问题为： \[ \begin{align} \text{maximize}\ \ &b^\top \mu\\ \text{s.t.}\ \ &A^\top \mu\leq c \end{align} \]

接下来，讨论一下对偶问题的几何解释。$x$为点$(y,z)$。$f(x)=x_1=z$，即取向量的第一个分量；$g(x)=x_2=y$，即取坐标的第二个分类。考虑原问题： \[ \begin{align} \text{minimize}\ \ &z\\ \text{s.t.}\ \ &y\leq 0\\ &(y,z)\in G \end{align} \] 那么有： \[ d(\lambda)=\min_{(y,z)\in G}\{z+\lambda y\} \] 对偶问题为： \[ \begin{align} \text{maximize}\ \ &d(\lambda)\\ \text{s.t.}\ \ &\lambda\geq 0 \end{align} \]

如图所示是原问题的解。红色阴影区域即原问题的可行区域，绿色的点就是原问题的最优解。

那么已知$\lambda$，如何求$d(\lambda)$？假如说，有$d(\lambda)=\alpha$，那么有直线： \[ z+\lambda y=\alpha \] 我们尽可能地把直线往下移动，而且让其至少有一部分在$G$以内，

蓝色圆圈处的点就是已知$\lambda$时的$d(\lambda)$。

现在，我们要改变$\lambda$，求$\lambda>0$时的$d(\lambda)$最大值，有：

图中，浅蓝色的直线表示了不同$\lambda$时$d(\lambda)$的计算过程。最终，$d(\lambda)$在深蓝色直线处取得最大值，我们发现它刚好是$v(P)$，即有：$v(D)=v(P)$。

那么这是巧合吗，是否永远有$v(D)=v(P)$呢？很遗憾，这是巧合。这是因为我们的$G$集合刚好是一个性质特别特别好的集合。如果它长得丑一点，比如：

如图所示是原问题的解。红色阴影区域即原问题的可行区域，绿色的点就是原问题的最优解。

接下来在这个附近变化$\lambda$，观察一下对偶问题的解。浅蓝色直线$1$是$\lambda$过小的情况，自不必说；深蓝色直线是最优解的情况。这时如果有人问，如果继续增大$\lambda$，那么不会和$z$轴交在更高的地方吗？这里我画出了继续增大$\lambda$的灰色直线，我们发现，这时，它和$z$轴的交点并不是$d(\lambda)$（请复习$d(\lambda)$的计算方法），而与他平行的下面那条蓝色直线$2$才是和$d(\lambda)$对应的真正的直线。

我们可以发现： \[ v(D)\leq v(P) \]

这个结论叫「弱对偶定理」。关于$v(D)=v(P)$的条件，有如下充分条件：

原问题是凸问题：即$f(x),g(x)$是凸函数、$h(x)$是线性函数、$G$是凸集
（Slater条件）在集合约束$X$的内部存在一点$x$，使得$\forall ij,g_i(x)<0,h_j(x)=0$，或：
（松弛Slater条件）在集合约束$X$的相对内部中存在一点$x$，使得对所有非仿射的$g$有$g(x)<0$，对所有仿射的$g$有$g(x)\leq 0$，且$h_j(x)=0$.

为了理解这个条件，观察下面的两个图像：

（a）图中虽然满足第一个条件（问题是凸问题），但是不满足第二个条件，这样的话，其对偶问题无解。

（b）图中虽然不满足第一个条件（$G$不是凸集），但仍然是强对偶的，这说明了上述的条件只是充分条件，而非必要条件。

罚函数法

对于只有等式约束的优化问题： \[ \begin{align} \text{minimize} \ \ &f(x)\\ s.t. \ \ &h_i(x)=0 \end{align} \] 如果约束函数$h(x)$是非线性函数，会导致求解的困难。这时，我们考虑把约束优化问题转换为无约束优化问题。主要思路是给目标函数增加一个和约束有关的惩罚项，当$x$离可行点越远，惩罚项就越大。

一个直观的想法是增加二次惩罚项，则问题变成： \[ \min f(x)+\frac \sigma 2 \sum_{i=1}^n h_i(x)^2 \] 这个无约束优化问题的解是约束优化问题的下界。假设这个无约束优化问题的最小值是$\theta(\sigma)$。显然，$\theta(\sigma)$是关于$\sigma$的单调递增函数。

记罚函数项目为$P(x)$，产生的无约束优化问题的目标函数为$q(x,\sigma)$。

【例】利用罚函数法求解： \[ \begin{align} \text{minimize}\ \ &x_1+x_2\\ s.t.\ \ & x_2-x_1^2=0 \end{align} \] 对应的无约束优化问题为： \[ \min x_1+x_2+\sigma(x_2-x_1^2)^2 \] 求其一阶必要条件，即$\nabla f(x)=0$，有： \[ \begin{cases} \dfrac{\partial q(x)}{\partial x_1}=1+2\sigma(x_2-x_1^2)(-2x_1)=0\\ \dfrac{\partial q(x)}{\partial x_2}=1+2\sigma(x_2-x_1^2)=0\\ \end{cases} \] 解得 \[ \begin{cases} x_1=-\dfrac {1}{2}\\ x_2=\dfrac{1}{4}-\dfrac{1}{2\sigma} \end{cases} \] 经验证，其海森矩阵是正定矩阵。将$\sigma\to \infty$，有： \[ \begin{cases} x_1=-\dfrac {1}{2}\\ x_2=\dfrac{1}{4} \end{cases} \]

可以看出，由罚函数法得到原问题的关键步骤就是$\sigma\to \infty$。

用计算机计算的算法一般如下：

取初始迭代点$x_0$，初始参数$\sigma_1>0$，终止条件$\epsilon$为一较小正数，迭代计数器$k=0$，更新倍数$\beta\in [4,10]$
以$x_{k-1}$为初始点，计算无约束优化问题： \[ \min f(x)+\sigma_kP(x) \] 得到解$x_k$
如果$\sigma_kP(x)\leq \epsilon$，说明惩罚项已经足够小，算法终止。
更新$\sigma_{k+1}=\beta \sigma_k,k=k+1$，转第2步

假如步骤2每次都可以得到无约束优化问题的全局最优解，那么这个算法有以下的性质：

【性质1】对于迭代形成的点列$\{x_k\}$，有

无约束优化问题目标函数序列$\{q(x_k,\sigma_k)\}$单调递增
罚函数序列$\{P(x_k)\}$（在常用的二次罚函数情况下，也可以写成$\{h(x_k)^\top h(x_k)\}$）单调递减
约束优化问题目标函数序列$\{f(x_k)\}$单调递增

【性质2】点列$\{x_k\}$的任意一个聚点都是约束优化问题的全局最优解。

【性质3】现在无需步骤2每次都可以得到无约束优化问题的全局最优解，只需要得到平稳点，即$\nabla _xq(x_k,\sigma_k)=0$，产生点列$\{x_k\}$，其聚点为$\bar x$，假设$\nabla h_i(\bar x)$线性无关，那么$\bar x$是约束优化问题的KKT点。

对于一般的约束优化问题： \[ \begin{align} \text{minimize}\ \ &f(x)\\ \text{s.t.}\ \ &h_i(x)=0,i=1,\cdots,m\\ &g_i(x)\leq 0,i=1,\cdots,l\\ &x \in X \end{align} \] 可以定义罚函数为： \[ P(x)=\sum_{i=1}^l \left[\max \{g_i(x),0\}\right]^2+\sum_{i=1}^m h^2_i(x) \]

乘子法

在罚函数法的运算中，为了收敛，有时$\sigma$会取到非常大的值，这对数值计算来说是不利的。为什么会出现这样的现象呢？我们考虑真正意义上的收敛的情况，即$P(x)=0$时。此时，对无约束优化问题： \[ \min f(x)+\sigma_k\sum_{i=1}^m h_i^2(x) \] 所求解出来的点一定满足一阶条件，即$\nabla q(x,\sigma_k)=0$，即： \[ \nabla f(x)+2\sigma_k\sum_{i=1}^mh_i(x)\nabla h(x)=0 \] 因为$P(x)=\sum_{i=1}^m h_i^2(x)=0$，所以后项为零，则有： \[ \nabla f(x)=0 \] 对比一般约束优化问题的KKT条件： \[ \nabla f(x)+\sum_{i=1}^m\mu_i\nabla h_i(x)=0 \] 可以发现，为了罚函数法收敛，我们提了一个比KKT条件强得多的要求（即$\nabla f(x)=0$），这在绝大多数的约束优化问题中都是不现实的。因此，我们可以做一个「妥协」，即放松这个最终的条件，以期待罚函数法有更好的收敛性能。

考虑增广拉格朗日函数： \[ L_c(x,\mu)=f(x)+\mu_k^\top h(x)+\sigma \sum_{i=1}^m h_i^2(x) \] 利用增广拉格朗日函数求解的计算机算法步骤如下：

取初始迭代点$x_0$，初始参数$\sigma_1>0,\mu_1>0$，终止条件$\epsilon$为一较小正数，迭代计数器$k=0$，更新倍数$\beta\in [4,10]$
以$x_{k-1}$为初始点，计算无约束优化问题： \[ \min L_c(x,\mu):=f(x)+\mu_k^\top h(x)+\sigma \sum_{i=1}^m h_i^2(x) \] 得到解$x_k$
如果$\sigma \sum_{i=1}^m h_i^2(x)$，说明惩罚项已经足够小，算法终止。
更新$\sigma_{k+1}=\beta \sigma_k,\mu_{k+1}=?,k=k+1$，转第2步.

算法的核心问题是如何更新$\mu$。我们的最终目标是在收敛时满足KKT条件，即 \[ \nabla f(x)+\sum_{i=1}^m\mu_i\nabla h_i(x)=0 \] 在算法第2步，得到$\nabla_x L_c(x,\mu)=0$，即： \[ \nabla f(x_k)+\sum_{i=1}^m \mu_{i,k}\nabla h_i(x_k)+2\sigma_k\sum_{i=1}^m h_i(x_k)\nabla h_i(x_k)=0 \] 整理一下，有： \[ \nabla f(x_k)+\left(\sum_{i=1}^m \mu_{i,k}+2\sigma_k\sum_{i=1}^m h_i(x_k)\right)\nabla h_i(x_k)=0 \] 对比它和KKT条件，很容易想到： \[ \mu_{i,k+1}= \mu_{i,k}+2\sigma_kh_i(x_k) \] 写成向量形式，就是： \[ \mu_{k+1}=\mu_k+2\sigma_kh(x(\mu_k)) \] 有定理：假如$x^*\in \text{int} X$且满足二阶充分条件，则存在$\bar \sigma$使得对任意$\sigma>\bar \sigma$，$x^*$是$L_c(x,\mu^*)$在$X$上的严格局部极小点。

障碍法(内点法)

障碍法(也称内点法)，用所谓的“障碍函数”代替不等式约束，并将它加到优化问题的目标函数中。如果一个集合存在内部，而且可以从内部逼近任何边界点，我们称这样的集合为「稳健的」。

假设约束优化问题的可行域$S$是稳健的，其内部为$\text{int} S$，定义障碍函数$B:\text{int}S\to R$，满足：

连续
随着$x$趋向于$S$的边界，$B(x)$趋向于正无穷

称$B(x)$是$S$的障碍函数。常用的障碍函数有： \[ B(x)=-\sum_i \ln(-g_i(x)) \]

\[ B(x)=-\sum_i\frac 1{g_i(x)} \]

约束$g_i(x)\leq 0$要求$g_i(x)$是负数。当$g_i(x)$越来越靠近$0$，即$x$越来越靠近边界时，$B(g(x))$趋向于无穷大。以下默认讨论对数障碍函数。

与之相关的一个概念叫解析中心，它是问题： \[ \min_{x\in \text{int} S}-\sum_i \ln(-g_i(x)) \] 的最优解。

将约束优化问题改写为： \[ \min f(x)+\mu B(x) \] 因为目标函数在$S$的边界处的值接近无穷大，所以适用于无约束优化问题的迭代下降法等方法可以用来求解这个问题。

在$\mu$越来越小时，函数的图像越「尖锐」

因此，构造一个越来越小，趋向于0的正数$\mu_k$序列，找到序列$x_k$使得： \[ x_k\in \arg\max_{x\in \text{int}S}f_{\mu_k}(x) \] 就是一种可行的算法。这称为「原始内点法」。这个序列$x_k$的每个聚点都是原始约束优化问题的全局极小点。

本站的运行成本约为每个月5元人民币，如果您觉得本站有用，欢迎打赏：

笔记

#最优化

最优化笔记

https://suzumiyaakizuki.github.io/2024/10/03/最优化/

作者

SuzumiyaAkizuki

发布于

2024年10月3日

许可协议

矩阵理论笔记上一篇

怎么在2024年给CentOS7的gcc升级下一篇

\(f(x)\)	\(\nabla f(x)\)	\(\nabla ^2 f(x)\)
\(a^\top x\)	\(a\)	\(O\)
\(x^\top Ax\)	\((A^\top +A)x\)	\(A^\top +A\)
\(r(x)^\top r(x)\)，其中\(r(x)\)是依赖于\(x\)的\(m\)维向量，$r(x)^=A$	\(2A(x)^\top r(x)\)	\(2 \sum_{i=1}^m r_i(\boldsymbol{x}) \nabla^2 r_i(\boldsymbol{x})+2 \boldsymbol{A}(\boldsymbol{x})^\top \boldsymbol{A}(\boldsymbol{x})\)