• 连续可微和强凸条件
• 无约束优化问题
• 牛顿法算法
• 等式约束优化问题

连续可微和强凸条件

考虑满足如下条件的函数$f$：

• 梯度单调性（一阶性质）：$(\nabla f(x)-\nabla f(y))^T(x-y)\geq 0$，$\forall x,y\in\operatorname{dom} f$；

• 梯度Lipschitz连续：$\|\nabla f(x)-\nabla f(y) \|\leq L\|x-y\|$，$\forall x,y\in\operatorname{dom} f$。

由第二条知，如下式子等价：

$\begin{aligned} \frac{1}{L}\|\nabla f(x)-\nabla f(y)\|^2&\leq (\nabla f(x)-\nabla f(y))^T(x-y)\leq L\|x-y\|^2\\ f(y)&\leq f(x)+\nabla f(x)^T(y-x)+\frac{L}{2}\|x-y\|^2\\ \end{aligned}$

函数$f(y)$的上界由二次曲线$f(x)+\nabla f^T(x)(y-x)+\frac{L}{2}\|x-y\|^2$确定，称为quadratic upper bound。

满足如下性质的函数称为m-强凸(m-strongly convex)

$f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta) f(y)-\frac{m}{2}\theta(1-\theta)\|x-y\|^2,$

即存在一个$m>0$使得$\nabla^2 f(x)\geq mI$。有如下式子等价：

$\begin{aligned} &(\nabla f(x)-\nabla f(y))^T(x-y)\geq m\|x-y\|^2\\ &f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{m}{2}\|x-y\|^2\\ \end{aligned}$

函数$f(y)$的下界由二次曲线$f(x)+\nabla f^T(x)(y-x)+\frac{m}{2}\|x-y\|^2$确定，称为quadratic lower bound。

如果将前面定义中的$\frac{m}{2}\|x-y\|^2$换成$\phi(x-y)$，满足$\phi$非负且仅在原点取值为0，则对应的函数$f$为一致凸(uniformly convex)函数^[1]。

无约束优化问题

考虑无约束优化问题$\min \, f(x)$。常用的方法是梯度下降法：

$\dot x=-\nabla f(x).$

令Lyapunov函数为$V = \frac{1}{2}\|f(x)-f(x^*)\|^2$。易证

$\dot V=-(f(x)-f(x^*))^T\nabla f(x)\leq 0.$

该算法对于次梯度也成立，因为次梯度同样满足凸函数的一阶性质。

如果函数$f$连续可微和强凸，那么可用牛顿法：

$\dot x = -\nabla^2f(x)^{-1}\nabla f(x).$

令Lyapunov函数为$V = \frac{1}{2}\|\nabla f(x)\|^2$。易证

$\dot V=-\nabla f(x)^T\nabla^2f(x)\nabla^2f(x)^{-1}\nabla f(x)\leq -2V.$

可见牛顿法相对于梯度下降法，有着更快的收敛速度(指数>渐进)。

牛顿法算法

令最优解为$\epsilon$-optimal，算法描述如下：

其中，$\lambda$称为牛顿衰减率(Newton decrement)，$\lambda(x)=(\nabla x_{nt}^T\nabla ^2f(x)\nabla x_{nt})^{1/2}$。

等式约束优化问题

考虑等式优化问题

$\begin{aligned} \min &\quad f(x)\\ \operatorname{s.t.} &\quad Ax=b. \end{aligned}$

将代价函数近似为在$x$处的二阶泰勒展开

$\begin{aligned} \min &\quad \hat f(x,v)=f(x)+\nabla f(x)^Tv+\frac{1}{2}v^T\nabla^2f(x)v\\ \operatorname{s.t.} &\quad A(x+v)=b. \end{aligned}$

由KKT条件可得

$\begin{bmatrix} \nabla^2 f(x)&A^T\\ A&0 \end{bmatrix}\begin{bmatrix} v_x\\ w_x \end{bmatrix}=\begin{bmatrix} -\nabla f(x)\\ 0 \end{bmatrix},\quad (1)$

称为KKT系统，左边的矩阵称为KKT矩阵。

同样，也可以先写出KKT条件，再一阶泰勒展开得到式(1)：

$\begin{aligned} \nabla f(x+v_x)+A^Tw_x=\nabla f(x)+\nabla^2f(x)v_x+A^Tw_x=0\\ A(x+v_x)=b \Longleftrightarrow Av_x = 0 \end{aligned}$

KKT矩阵非奇异的条件有：

• $N(\nabla^2 f(x))\cap N(A)=\{0 \}$；
• $Ax=0,x\neq 0 \Longrightarrow x^T\nabla^2 f(x)x>0$；
• $F^T\nabla^2 f(x)F>0$，其中$F\in\mathbb R^{n\times(n-p)}$满足$R(F)=N(A)$；
• $\nabla^2 f(x)+A^TQA>0$对有些$Q\geq 0$成立。

如果$\nabla^2 f(x)>0$，则KKT矩阵一定非奇异。

令$F$满足$R(F)=N(A)$且$\operatorname{rank}F=n-p$，令$\hat x$满足$A\hat x=b$。定义

$x=Fz+\hat x，$

则可以消去等式约束，得到无约束优化问题和新的代价函数$\tilde f(z)=f(Fz+\hat x)$，其梯度和Hessian为

$\nabla \tilde f(z)=F^T\nabla f(Fz+\hat x),\quad \nabla^2 \tilde f(z)=F^T\nabla^2 f(Fz+\hat x)F.$

由牛顿法得到，无约束优化问题的$v_z=-\nabla^2\tilde f(z)^{-1}\nabla \tilde f(z)=-(F^T\nabla^2f(x)F)^{-1}F^T\nabla f(x)$.

令$v_x = Fv_z$，即$v_x=-F(F^T\nabla^2f(x)F)^{-1}F^T\nabla f(x)$。则有

$w_x=-(AA^T)^{-1}A(\nabla f(x)+\nabla^2 f(x)v_x).$

代入式(1)，由于$AF=0$，故第二行满足。为了证明第一行，我们观察到

$\begin{bmatrix} F^T\\ A \end{bmatrix}(\nabla^2 f(x)v_x+A^Tw_x+\nabla f(x))=0.$

因为左边第一个矩阵非奇异，故$\nabla^2 f(x)v_x+A^Tw_x+\nabla f(x)=0$，第一行满足。

综上所述，可以令$\dot x = v_x = -F(F^T\nabla^2f(x)F)^{-1}F^T\nabla f(x)$，就能够保证$x$收敛到最优解。