本章进入凸优化问题的求解、算法阶段。

无约束优化问题

本文讨论一下无约束问题：

其中，f$f$是二次可微凸函数。假定该问题可解，即存在最优解x⋆$x^{\star }$，用p⋆$p^{\star }$表示最优值为：infxf(x)=f(x⋆)$\underset{x}{inf}f(x)=f(x^{\star })$。

因为f$f$可微，则最优点x⋆$x^{\star }$满足以下条件：

在特殊情况下，我们可以通过解析法求解最优性方程，但大多数情况下没有办法求得解析解。因此，最常见的方法是使用迭代法。

我们需要计算点列：x(0),x(1),..$x^{(0)},x^{(1)},..$，使得k→∞,f(x(k))→p⋆$k\to \mathrm{\infty },f(x^{(k)})\to p^{\star }$。使用ϵ$ϵ$表示容许误差值，当f(x(k))−p⋆≤ϵ$f(x^{(k)})-p^{\star }\le ϵ$时，算法终止。

例子p438${}_{p_{438}}$

二次优化

很容易我们可以对其求导得到Px⋆+q=0$P{x}^{\star }+q=0$。

因此，若P$P$为正定矩阵，则存在唯一解x⋆=−P−1q$x^{\star }=-P^{-1}q$。

若此方程无解，则优化问题无下界。

最小二乘

作为二次优化的特例：

其最优性解为其正规方程：

强凸性

强凸是指：

对任意x∈S$x\in S$都成立。这里的▽2f(x)${▽}^{2}f(x)$表示Hessian矩阵。

我们可以通过强凸性推导出有意义的方程。

次优性条件

当m=0$m=0$时，上式变为凸性的基本不等式（一阶可微），当m≥0$m\ge 0$时，对f(y)$f(y)$的下界得到了更好的估计结果。

对上式进行求导可得：

因此，带入原式可得：

既然该式子对任意y∈S$y\in S$都成立，则：

由于||▽f(x)||2≤(2mϵ)1/2$||▽f(x)|{|}_2\le (2mϵ{)}^{1/2}$，因此带入可得到次优性条件：

我们也可以得到x$x$与任意最优解x⋆$x^{\star }$之间的距离与||▽f(x)||2$||▽f(x)|{|}_2$的关系：

关于▽2f(x)${▽}^{2}f(x)$的上界

由于||▽2f(x)||$||{▽}^{2}f(x)||$的最大特征值是x$x$在S$S$上的连续函数，因此他在S$S$上有界，即存在常数M$M$，使得(没懂)：

与上面类似，我们可以得到p⋆$p^{\star }$的上界：

对比p⋆$p^{\star }$的上界：

下水平集的条件数

从之前的分析我们可以得到：

因此，比值M/m$M/m$是矩阵▽2f(x)${▽}^{2}f(x)$的条件数的上界，这是影响其计算效率的重要因素。

下降方法

我们讨论的所有方法都是下降方法，只要不是最优点则应该满足：

而优化点列为：

由凸性可知▽f(x(k))T(y−k(k))≥0$▽f(x^{(k)}{)}^T(y-k^{(k)})\ge 0$意味着f(y)≥f(x(k))$f(y)\ge f(x^{(k)})$，因此，一个下降方法的搜索方向必须满足：

这将作为我们判断后面下降算法的条件之一。

通用下降算法

1. 确定下降方向Δx$\mathrm{\Delta }x$
2. 直线搜索。选择步长t>0$t>0$
3. 修改。x:=x+tΔx$x:=x+t\mathrm{\Delta }x$
4. 直到满足停止条件

精确直线搜索p444${}_{p_{444}}$

t$t$值是通过沿着射线{x+t△x|t≥0}$\{x+t\mathrm{△}x|t\ge 0\}$优化f$f$而确定的：

当求解式中的单变量优化问题的成本比计算搜索方向的成本低时，采用精确直线搜索。

特殊情况可以用解析的方法确定最优解。

回溯直线搜索

很多时候我们并不需要找到一个最小的t$t$，只需要f$f$有“足够的”减少即可。

常用的方法为：

1. 给定下降方向Δx$\mathrm{\Delta }x$,参数α∈(0,0.5),β∈(0,1)$\alpha \in (0,0.5),\beta \in (0,1)$
2. 设定初始t=1$t=1$
3. iff(x+t△x)>f(x)+αt▽f(x)T△x,thent:=βt$iff(x+t\mathrm{△}x)>f(x)+\alpha t▽f(x{)}^T\mathrm{△}x,thent:=\beta t$

回溯算法从单位步长开始，按比例逐渐减小，直到满足停止条件。

由于Δx$\mathrm{\Delta }x$是下降方向，▽f(x)TΔx<0$▽f(x{)}^T\mathrm{\Delta }x<0$，所以只要t$t$足够小，一定有：

因此回溯算法一定会停止。

梯度下降方法

梯度下降利用△x=−▽f(x)$\mathrm{△}x=-▽f(x)$，是一种自然的选择。

算法过程

1. 给定初始点x∈domf$x\in domf$，Δx:=▽f(x)$\mathrm{\Delta }x:=▽f(x)$
2. 直线搜索。通过精确或回溯直线搜索确定步长t$t$
3. 修改x:=x+tΔx$x:=x+t\mathrm{\Delta }x$
4. 直到满足停止准则

收敛性分析

我们可以推导得出：

其中c=1−m/M<1$c=1-m/M<1$，因此最多经过log(f(x(0))−p⋆)/ϵlog(1/c)$\frac{\log (f(x^{(0)})-p^{\star })/ϵ}{\log (1/c)}$次迭代，可以收敛到次优性条件。

例子

R2$R^2$空间中的二次问题

考虑二次目标函数

其中γ$\gamma$大于0。很容易得到其Hessian矩阵为常数，特征值为1和γ$\gamma$，因此其下水平集的条件数都等于：

我们选取初始点x(0)=(γ,1)$x^{(0)}=(\gamma ,1)$，可以计算：

最速下降方法p454${}_{p_{454}}$

对f(x+v)$f(x+v)$在x$x$处进行一阶Taylor展开：

其中▽f(x)Tv$▽f(x{)}^{T}v$是f$f$在x$x$在沿着方向v$v$的方向导数，若其为负数，则v$v$为下降方向。

如何选择v$v$使得其方向导数尽可能小（下降最快），我们定义一个规范化的最速下降方向：

我们也可以考虑将最速下降方向乘以一个特殊的比例因子，从而考虑非规范化的最速下降方向：

其中||⊙||⋆$||\odot |{|}_{\star }$定义为对偶范数（||z||⋆=sup{zTx|||x||≤1}$||z|{|}_{\star }=sup\{z^{T}x|||x||\le 1\}$）。

对于这种最速下降步径，我们有：

Newton方法p462${}_{p_{462}}$

Newton步径

Δxnt=−▽2f(x)−1▽f(x)$\mathrm{\Delta }{x}_{nt}=-{▽}^{2}f(x{)}^{-1}▽f(x)$

由▽2f(x)${▽}^{2}f(x)$的正定性可知（凸函数的二阶条件），除非▽f(x)=0$▽f(x)=0$，否则：

因此，Δxnt$\mathrm{\Delta }{x}_{nt}$与负梯度方向为锐角，Δ$\mathrm{\Delta }$x_{nt}是下降方向。

可以从以下几个方面来了解Newton步径。

二阶近似的最优解

考虑函数f$f$在x$x$处的二阶Taylor近似为：

这是v$v$的二次凸函数，在v=Δxnt$v=\mathrm{\Delta }{x}_{nt}$处达到最小值。

因此，将x$x$加上Newton步径Δxnt$\mathrm{\Delta }{x}_{nt}$能够极小化f$f$在x$x$处的二阶近似。

如果函数是二次的，那么使用Newton步径是f$f$的精确最优解。若函数近似二次，则x+Δxnt$x+\mathrm{\Delta }{x}_{nt}$是f$f$的最优解，即x⋆$x^{\star }$的很好的估计值。

Hessian范数下的最速下降方向

若定义Hessian矩阵▽2f(x)${▽}^{2}f(x)$定义的二次范数，即：

那么可以通过最速下降方向推出Δxnt$\mathrm{\Delta }{x}_{nt}$。

线性化最优性条件的解

若我们在x$x$附近对最优性条件▽f(x⋆)=0$▽f(x^{\star })=0$进行线性化，可得到：

其解就是我们的Newton步径。

Newton减量p464${}_{p_{464}}$

λ(x)$\lambda (x)$称为Newton减量，可以用来设计停止准则。

将Δxnt$\mathrm{\Delta }{x}_{nt}$带入f(x+tΔx)$f(x+t\mathrm{\Delta }x)$得：f(x+tΔx)=f(x)−12▽Tf(x)▽2f(x)−1▽f(x)$f(x+t\mathrm{\Delta }x)=f(x)-\frac{1}{2}{▽}^{T}f(x){▽}^{2}f(x{)}^{-1}▽f(x)$

因此：f(x)−f(x+tΔx)=12▽Tf(x)▽2f(x)−1▽f(x)=12λ(x)2$f(x)-f(x+t\mathrm{\Delta }x)=\frac{1}{2}{▽}^{T}f(x){▽}^{2}f(x{)}^{-1}▽f(x)=\frac{1}{2}\lambda (x{)}^2$

因此，λ/2${\lambda }^{/}2$是f$f$在x$x$处的二阶近似对f(x)−p⋆$f(x)-p^{\star }$作出的估计。

我们也可以将Newton减量表示为λ=(ΔxTnt▽2f(x)Δxnt)1/2$\lambda =(\mathrm{\Delta }{x}_{nt}^T{▽}^{2}f(x)\mathrm{\Delta }{x}_{nt}{)}^{1/2}$，表明λ$\lambda$是Newton步径的二次范数，该范数由Hessian矩阵定义。

Newton减量也出现在回溯直线搜索中，因为我们可以得到：

Newton方法

1. 给定初始点x∈domf$x\in domf$，误差阈值ϵ>0$ϵ>0$
2. 计算Newton步径和减量
3. 停止准则：如果λ2/2≤ϵ${\lambda }^2/2\le ϵ$，退出
4. 直线搜索，根据回溯直线搜索确定步长t$t$
5. 改进：x:=x+tΔxnt$x:=x+t\mathrm{\Delta }{x}_{nt}$