最优化抄书笔记：信赖域方法(2)

ainatipen

Reference：
[1] 李董辉，童小娇，万中，数值最优化算法与理论.
[2] 马昌凤，最优化方法及其 Matlab 程序设计.

这篇主要补一些理论结果……可能看着没啥意思

一、信赖域方法的适定性


这一部分我们来证明：信赖域算法产生的点列是下降的。

Theorem 1
设 d 是信赖域子问题 \min_{\left\|d\right\|\le\Delta} q_k(d) 的解，且 \nabla f(x_k)\ne 0 ，则 \Delta q_k=q_k(0)-q_k(d)<0 。
Proof
显然 0 是子问题的一个可行点，那么 d 是解意味着 q_k(d)\le q_k(0) ，故只要证明 q_k(d)< q_k(0) 。若不然 q_k(d)=q_k(0) ，则 0 也是子问题的最优解。又 0 是可行域的内点，从而必有 \nabla q_k(0)=0 ，但
\nabla q_k(0)=\nabla(\nabla f(x_k)^Td + \frac{1}{2}d^T\nabla^2 f(x_k)d)|_{d=0}=\nabla f(x_k)
矛盾。□

Theorem 2
由信赖域算法产生的函数值点列 \{f(x_k)\} 是单调递减的。
Proof
若 r_k<0.05 ，则 x_{k+1}=x_k ；否则由Theorem 1可知 \Delta q_k > 0 ，从而必有 \Delta f_k=f(x_{k})-f(x_{k+1})>0 。□

这两个结果说明了信赖域算法的函数值点列一定是单调下降的。但现在我们还不能确定它是不是一定收敛到函数的极小值，还需要进一步的分析。

二、Cauchy点


Definition 1  Cauchy点
设当前迭代点为 x_k ，我们称 d_k^c=-\tau_k\frac{\Delta_k}{\left\|\nabla f(x_k)\right\|}\nabla f(x_k) 为子问题的Cauchy点，其中
\tau _k:=\begin{cases}         1,{g_k}^TB_kg_k\le 0\\ \\         \min \left\{ 1,\displaystyle\frac{\left\| g_k \right\| ^3}{\Delta _k{g_k}^TB_kg_k} \right\} ,{g_k}^TB_kg_k>0\\ \end{cases}  
这里 g_k=\nabla f(x_k) 。

显然Cauchy点满足 \left\|d_k^c\right\|\le\tau_k\Delta_k\le\Delta_k ，从而是可行点。另一方面， d_k^c 平行于负梯度方向，从而是下降方向(如果用下降算法的角度来看的话)。

Theorem 3
在Cauchy点 d_k^c 处满足
q_k\left( 0 \right) -q_k\left( d_{k}^{c} \right) \ge \frac{1}{2}\left\| g_k \right\| \min \left\{ \Delta _k,\frac{\left\| g_k \right\|}{\left\| B_k \right\|} \right\}   
这里 \left\|B_k\right\| 是矩阵的2-范数。
Proof
Case 1： {g_k}^TB_kg_k\le 0 ，此时有
\begin{array}{l}\displaystyle q_k\left( 0 \right) -q_k\left( d_{k}^{c} \right) =-q_k\left( -\frac{\Delta _k}{\left\| g_k \right\|}g_k \right)  \\  \\\displaystyle ={g_k}^T\frac{\Delta _k}{\left\| g_k \right\|}g_k-\frac{1}{2}\frac{\Delta _k}{\left\| g_k \right\|}{g_k}^TB_k\frac{\Delta _k}{\left\| g_k \right\|}g_k \\  \\\displaystyle \ge \frac{\Delta _k}{\left\| g_k \right\|}{g_k}^Tg_k=\Delta _k\left\| g_k \right\| \ge \frac{1}{2}\left\| g_k \right\| \min \left\{ \Delta _k,\frac{\left\| g_k \right\|}{\left\| B_k \right\|} \right\}  \end{array}
Case 2： {g_k}^TB_kg_k>0 ，且  \frac{\left\| g_k \right\| ^3}{\Delta _k{g_k}^TB_kg_k}\le 1  ，此时有
\begin{array}{l}\displaystyle q_k\left( 0 \right) -q_k\left( d_{k}^{c} \right) =-q_k\left( -\frac{\left\| g_k \right\| ^2}{{g_k}^TB_kg_k}g_k \right)  \\  \\\displaystyle ={g_k}^T\frac{\left\| g_k \right\| ^2}{{g_k}^TB_kg_k}g_k-\frac{1}{2}\frac{\left\| g_k \right\| ^2}{{g_k}^TB_kg_k}{g_k}^TB_k\frac{\left\| g_k \right\| ^2}{{g_k}^TB_kg_k}g_k \\  \\\displaystyle =\frac{\left\| g_k \right\| ^4}{{g_k}^TB_kg_k}-\frac{1}{2}\frac{\left\| g_k \right\| ^4}{{g_k}^TB_kg_k}=\frac{1}{2}\frac{\left\| g_k \right\| ^4}{{g_k}^TB_kg_k}\ge \frac{1}{2}\frac{\left\| g_k \right\| ^2}{\left\| B_k \right\|}\ge \frac{1}{2}\left\| g_k \right\| \min \left\{ \Delta _k,\frac{\left\| g_k \right\|}{\left\| B_k \right\|} \right\}  \end{array}
Case 3： {g_k}^TB_kg_k>0 ，且 \frac{\left\| g_k \right\| ^3}{\Delta _k{g_k}^TB_kg_k}> 1 ，则
\begin{array}\displaystyle q_k\left( 0 \right) -q_k\left( d_{k}^{c} \right) =-q_k\left( -\displaystyle\frac{\Delta _k}{\left\| g_k \right\|}g_k \right)  \\  \\\displaystyle ={g_k}^T\frac{\Delta _k}{\left\| g_k \right\|}g_k-\frac{1}{2}\frac{\Delta _k}{\left\| g_k \right\|}{g_k}^TB_k\frac{\Delta _k}{\left\| g_k \right\|}g_k \\  \\\displaystyle =\Delta _k\left\| g_k \right\| -\frac{1}{2}\frac{\Delta _{k}^{2}}{\left\| g_k \right\| ^2}{g_k}^TB_kg_k=\Delta _k\left\| g_k \right\| -\frac{1}{2}\left( \Delta _k\left\| g_k \right\| \right) \frac{\Delta _k{g_k}^TB_kg_k}{\left\| g_k \right\| ^3} \\  \\\displaystyle \ge \Delta _k\left\| g_k \right\| -\frac{1}{2}\Delta _k\left\| g_k \right\| =\frac{1}{2}\Delta _k\left\| g_k \right\| \ge \frac{1}{2}\left\| g_k \right\| \min \left\{ \Delta _k,\frac{\left\| g_k \right\|}{\left\| B_k \right\|} \right\}  \end{array}
综合上述就证好了结论。□
Remark  一个显然的推论是：若 d 是子问题的精确解，则也有
q_k\left( 0 \right) -q_k\left( d \right) \ge \frac{1}{2}\left\| g_k \right\| \min \left\{ \Delta _k,\frac{\left\| g_k \right\|}{\left\| B_k \right\|} \right\}   

三、信赖域方法的全局收敛性


Theorem 4  信赖域方法的全局收敛性
设 f(x) 有下界，在水平集 L(x_0):=\{x:f(x)\le f(x_0)\} 上二阶连续可微， \{x_k\} 是由信赖域方法生成的点列(精确求解子问题或用Cauchy点)。若序列 \{\left\|B_k\right\|\} 一致有界，且把终止条件取为 \left\|\nabla f(x_k)\right\|=0 ，那么或者 \{x_k\} 是有限点列，或者
\liminf\limits_{k\to\infty}\left\|\nabla f(x_k)\right\|=0
Proof
设 \{x_k\} 是无穷点列。我们先来估计 r_k-1 这样一个量：
\left| r_k-1 \right|=\left| \frac{f\left( x_k \right) -f\left( x_k+d_k \right)}{q_k\left( 0 \right) -q_k\left( d_k \right)}-1 \right|=\left| \frac{f\left( x_k+d_k \right) -f\left( x_k \right) -q_k\left( d_k \right)}{q_k\left( 0 \right) -q_k\left( d_k \right)} \right|  
利用Taylor展开：
f\left( x_k+d_k \right) =f\left( x_k \right) +\int_0^1{{d_k}^T\left[ \nabla f\left( x_k+\tau d_k \right) -\nabla f\left( x_k \right) \right]}\mathrm{d}\tau   
从而
\begin{array}{l}\displaystyle \left| f\left( x_k+d_k \right) -f\left( x_k \right) -q_k\left( d_k \right) \right| \\  \\\displaystyle \le \frac{1}{2}{d_k}^TB_kd_k+\left\| d_k \right\| \int_0^1{\left\| \nabla f\left( x_k+\tau d_k \right) -\nabla f\left( x_k \right) \right\|}\mathrm{d}\tau  \\  \\\displaystyle \le \frac{1}{2}M\left\|d_k\right\|^2+o\left( \left\| d_k \right\|^2 \right)  \end{array}
这里 M 是 \{\left\|B_k\right\|\} 的上界。
下面用反证法证明结论，设存在 \varepsilon_0>0 使得任意的 \left\|\nabla f(x_k)\right\|\ge\varepsilon_0 ，那么当 \Delta_k 充分小时，成立
\left| r_k-1 \right|\le \frac{\displaystyle\frac{1}{2}M\left\| d_k \right\| ^2+o\left( \left\| d_k \right\|^2 \right)}{\displaystyle\frac{1}{2}\left\| g_k \right\| \min \left\{ \Delta _k,\frac{\left\| g_k \right\|}{\left\| B_k \right\|} \right\}}\le \frac{\displaystyle\frac{1}{2}M\Delta _{k}^{2}+o\left( \Delta _k^2 \right)}{\displaystyle\frac{1}{2}\varepsilon _0\min \left\{ \Delta _k,\frac{\varepsilon _0}{M} \right\}}=O\left( \Delta _k \right)   
故存在充分小的 \bar\Delta ，对任意 \Delta_k<\bar\Delta ，成立 \left|r_k-1\right|<1-0.75 ，从而 r_k>0.75 ，根据信赖域算法，有 \Delta_{k+1}\ge\Delta_k 。因此，存在正整数 k_0 和常数 \gamma ，使得
\Delta_k\ge\gamma\bar\Delta\quad\color{violet}{\cdots(*)}
对任意的 k\ge k_0 成立。
Case 1：有无穷多个 k 使得 r_k\ge 0.05 。则对于这些 k ，有
f\left( x_k \right) -f\left( x_{k+1} \right) =r_k\left[ q_k\left( 0 \right) -q_k\left( d_k \right) \right] \ge \frac{0.05}{2}\varepsilon _0\min \left\{ \Delta _k,\frac{\varepsilon _0}{M} \right\}   
由于 f 有下界，故上式的左端趋于零，这蕴含了 \Delta_k\to 0 ，和 \color{violet}{(*)} 矛盾。
Case 2：只有有限多个 k 使得 r_k\ge 0.05 ，则当 k 充分大时有 r_k<0.05 ，根据信赖域算法有 \Delta_k\to 0 ，也和 \color{violet}{(*)} 矛盾。
综上，不可能存在 \varepsilon_0>0 使得任意的 \left\|\nabla f(x_k)\right\|\ge\varepsilon_0 。这就证明了
\liminf\limits_{k\to\infty}\left\|\nabla f(x_k)\right\|=0
□
Remark 1  定理表明，只要子问题的解 d_k 的下降量满足
q_k(0)-q_k(d)\ge q_k(0)-q_k(d_k^c)
即比Cauchy点的下降量多，那么信赖域算法就全局收敛。
Remark 2  回顾截断共轭梯度法，可知其产生的子问题的近似解就是Cauchy点。

最后不加证明地给给出信赖域方法的收敛速度估计：

Theorem 5
设 f:\mathbb R^n\to\mathbb R 二阶连续可微有下界，由信赖域算法产生的点列 \{x_k\} 有界，则
(1) 存在 \{x_k\} 的聚点 x^* 满足优化问题 \min f(x) 的一阶必要条件和二阶必要条件；
(2) 若 \nabla ^2f(x^*)>0 ，则
\lim\limits_{k\to\infty} r_k=1,\ \lim\limits_{k\to\infty} x_k=x^*,\ \inf\Delta_k>0
且当 k 充分大时， \left\|d_k\right\|\le \Delta_k ；
(3) 在(2)的条件下， \{x_k\} 超线性收敛到 x^* ；
(4) 若 \nabla^2 f 在 x^* 处Lipschitz连续，则 \{x_k\} 二阶收敛到 x^* 。