《数值最优化算法与理论》

数值最优化—无约束问题最速下降法和Newton法 和 数值最优化—无约束问题共轭梯度法 中介绍的求解无约束问题的几类算法的共同点是基于方向和步长确定一个下降方向 d ( k ) d^{(k)} d(k)，然后从 x ( k ) x^{(k)} x(k)出发，沿方向 d ( k ) d^{(k)} d(k)进行线性搜索确定步长 α k \alpha _k αk​，得到下一个迭代点 x ( k + 1 ) = x ( k ) + α k d ( k ) x^{(k+1)} = x^{(k)} + \alpha _kd^{(k)} x(k+1)=x(k)+αk​d(k)。称这类算法为线性搜索算法。

下面介绍求解无约束问题： m i n   f ( x ) , ( x ∈ R n ) min \ f(x), \quad (x \in R^n) min f(x),(x∈Rn) 的另一类算法—信赖域算法。信赖域算法的基本思想是：在当前迭代点 x ( k ) x^{(k)} x(k)的附近用一个简单函数近似目标函数 f f f。用该近似函数在 x ( k ) x^{(k)} x(k)的某个邻域内的极小值点作为下一个迭代点。与线性搜索型算法比较，信赖域算法在每次迭代同时确定搜索方向和步长。

由于信赖域方法用 f f f的某个近似函数在 x ( k ) x^{(k)} x(k)邻域的极小值点作为下一个迭代点，因此，设计信赖域算法需要考虑如下相关问题：

考虑到一般非线性函数在任何点的邻域内都可以用二次函数近似，而且二次函数的极小值问题相对容易求解。因此，在信赖域算法中，通常我们采用二次函数作为目标函数 f f f的近似，用该二次函数在 x ( k ) x^{(k)} x(k)某邻域内的极小值点作为下一个迭代点，即 x ( k + 1 ) x^{(k+1)} x(k+1)为下面问题的解： m i n   f ( x ( k ) ) + ∇ f ( x ( k ) ) T ( x − x ( k ) ) + 1 2 ( x − x ( k ) ) T B k ( x − x ( k ) ) min \ f(x^{(k)}) + \nabla f(x^{(k)})^T (x - x^{(k)}) + \frac 1 2 (x - x^{(k)})^T B_k(x - x^{(k)}) min f(x(k))+∇f(x(k))T(x−x(k))+21​(x−x(k))TBk​(x−x(k)) s . t .   ∣ ∣ x − x ( k ) ∣ ∣ ≤ Δ k s.t. \ ||x-x^{(k)}|| \le \Delta _k s.t. ∣∣x−x(k)∣∣≤Δk​ 其中， B k ∈ R n × n B_k \in R^{n \times n} Bk​∈Rn×n是 f f f在 x x x处的Hessian矩阵或其近似，参数 Δ k > 0 \Delta _k > 0 Δk​>0控制 x ( k ) x^{(k)} x(k)的邻域大小。若令 d = x − x ( k ) d = x - x^{(k)} d=x−x(k)，则上面的问题可改写为如下等价的二次函数极小值问题： m i n   f ( x ( k ) ) + ∇ f ( x ( k ) ) T d + 1 2 d T B k d = △ q k ( d ) min \ f(x^{(k)}) + \nabla f(x^{(k)})^T d + \frac 1 2 d^T B_kd \overset {\bigtriangleup } {=} q_k (d) min f(x(k))+∇f(x(k))Td+21​dTBk​d=△qk​(d) s . t .   ∣ ∣ d ∣ ∣ ≤ Δ k s.t. \ ||d|| \le \Delta _k s.t. ∣∣d∣∣≤Δk​ 设 d ( k ) d^{(k)} d(k)是问题的解。则下一个迭代点为 x ( k + 1 ) = x ( k ) + d ( k ) x^{(k+1)} = x^{(k)} + d^{(k)} x(k+1)=x(k)+d(k)。问题中的可行域： D = { d ∈ R n   ∣   ∣ ∣ d ∣ ∣ ≤ Δ k } D = \{d \in R^n \ | \ ||d|| \le \Delta _k \} D={d∈Rn ∣ ∣∣d∣∣≤Δk​} 称为信赖域，参数 Δ > 0 \Delta >0 Δ>0称为信赖域半径，等价的二次函数极小值问题称为信赖域子问题，其中范数可任意选取。本章采用Euclid范数。

信赖域子问题是仅有一个不等式约束的二次函数极小值问题。

由函数的二阶Taylor展开可知，当 Δ k \Delta _k Δk​充分小时，二次函数 q q q在信赖域 D D D中是 f f f的一个很好的近似。另一方面，当 f f f本身是一个二次函数或近似与二次函数时， q q q可能在某一个较大范围内也是 f f f的一个很好的近似。如何确定信赖域半径是信赖域算法的一个重要环节。一方面，我们希望在 D D D中 q q q与 f f f的近似程度好，另一方面希望信赖域半径尽可能大。为了合理确定信赖域半径，我们定义 Δ F k \Delta F_k ΔFk​为 f f f在第 k k k步的实际下降量。即： Δ f k = f ( x ( k ) ) − f ( x ( k ) + d ( k ) ) \Delta f_k = f(x^{(k)}) - f(x^{(k)} + d^{(k)}) Δfk​=f(x(k))−f(x(k)+d(k)) 其中， d ( k ) d^{(k)} d(k)是信赖域子问题的解。令 Δ q k \Delta _{q_k} Δqk​​为对应的预测下降量，即： Δ q k = f ( x ( k ) ) − q k ( d ( k ) ) \Delta _{q_k} = f(x^{(k)}) - q_k(d^{(k)}) Δqk​​=f(x(k))−qk​(d(k)) 注意到 r k r_k rk​从某种程度反映了二次函数 q k ( d ( k ) ) q_k(d^{(k)}) qk​(d(k))与目标函数 f ( x ( k ) + d ( k ) ) f(x^{(k)} + d^{(k)}) f(x(k)+d(k))的近似程度。若 r k r_k rk​接近于1，则可认为二次函数 q k ( d ( k ) ) q_k(d^{(k)}) qk​(d(k))在信赖域 D D D上与目标函数 f ( x ( k ) + d ( k ) ) f(x^{(k)} + d^{(k)}) f(x(k)+d(k))的近似程度很好。反之，若 r k r_k rk​离1较远，我们认为 q k ( d ( k ) ) q_k(d^{(k)}) qk​(d(k))在信赖域 D D D上与目标函数 f ( x ( k ) + d ( k ) ) f(x^{(k)} + d^{(k)}) f(x(k)+d(k))的近似程度不好。基于上述观察，我们可以用 r k r_k rk​与1的近似程度作为对信赖域半径是否合适的准则。即，可通过如下方式调整信赖域半径。

给定常数 η , η 1 , η 2 ∈ ( 0 , 1 ) \eta , \eta _1, \eta _2 \in (0,1) η,η1​,η2​∈(0,1)满足 η < η 1 < η 2 \eta < \eta _1< \eta _2 η \Delta _k Δk+1​>Δk​。

② 若 η 1 < r k < η 2 \eta _1 < r_k 0 ϵ>0。令 k = 0 k=0 k=0。（收敛性检测）若 ∣ ∣ ∇ f ( x ( k ) ) ∣ ∣ ≤ ϵ ||\nabla f(x^{(k)})|| \le \epsilon ∣∣∇f(x(k))∣∣≤ϵ，则算法终止。得问题的解 x ( k ) x^{(k)} x(k)。否则，转2。（子问题求解）解信赖域子问题得解 d ( k ) d^{(k)} d(k)。（信赖域修正）计算 r k r_k rk​。 若 r k > 3 4 r_k>\frac 3 4 rk​>43​，则令 Δ k + 1 = m i n { 2 Δ k , Δ ˉ } \Delta _{k+1} = min\{2\Delta _k,\bar \Delta \} Δk+1​=min{2Δk​,Δˉ}。 若 1 4 < r k < 3 4 \frac 1 4 < r_k0 λ>0充分大使得 B + λ I B+\lambda I B+λI正定，可通过解如下关于 λ \lambda λ的一元非线性方程： ϕ 1 ( λ ) = ∣ ∣ ( B + λ I ) − 1 ∇ f ( x ) ∣ ∣ − Δ = 0 \phi _1(\lambda) = ||(B+\lambda I)^{-1} \nabla f(x)|| - \Delta = 0 ϕ1​(λ)=∣∣(B+λI)−1∇f(x)∣∣−Δ=0 得到解 λ ∗ \lambda ^* λ∗。然后得子问题的解 d ∗ = d ( λ ∗ ) = − ( B + λ I ) − 1 ∇ f ( x ) d^* = d(\lambda ^*) = -(B+\lambda I)^{-1} \nabla f(x) d∗=d(λ∗)=−(B+λI)−1∇f(x)。

基于此求信赖域子问题的方法称为子问题的精确解法。利用矩阵的对角化分解可知， ϕ 1 ( λ ) \phi _1(\lambda) ϕ1​(λ)是非线性程度高的系统。为了简化方程的计算，定义： ϕ 2 ( λ ) = 1 Δ − 1 ∣ ∣ d ( λ ) ∣ ∣ \phi_2(\lambda) = \frac {1} {\Delta} - \frac 1 {||d(\lambda)||} ϕ2​(λ)=Δ1​−∣∣d(λ)∣∣1​ ϕ 2 ( λ ) \phi_2(\lambda) ϕ2​(λ)近似为线性方程系统。该方程可应用牛顿迭代法建立其迭代计算式为： λ l + 1 = λ l − ϕ 2 ( λ l ) ϕ 2 ′ ( λ l ) = λ l + ( ∣ ∣ d l ∣ ∣ ∣ ∣ q l ∣ ∣ ) 2 ( ∣ ∣ d l ∣ ∣ − Δ Δ ) \lambda _{l+1} = \lambda _l - \frac {\phi _2 (\lambda _l)} {\phi _2 ' (\lambda _l)} = \lambda _l + (\frac {||d_l||} {||q_l||})^2 (\frac {||d_l|| - \Delta} {\Delta}) λl+1​=λl​−ϕ2′​(λl​)ϕ2​(λl​)​=λl​+(∣∣ql​∣∣∣∣dl​∣∣​)2(Δ∣∣dl​∣∣−Δ​) 根据如上分析可建立信赖域子问题精确求解的计算步骤如下：

上面介绍的信赖域子问题精确求解计算量较大。而且当 B + λ ∗ I B+\lambda ^* I B+λ∗I非正定时，子问题的求解较为复杂。

我们考虑非精确求解子问题，下面我们介绍非精确求解信赖域子问题的折线方法。有信赖域子问题知其解 d ∗ d^* d∗是信赖域半径 Δ \Delta Δ的函数，记为 d ∗ ( Δ ) d^*(\Delta) d∗(Δ)。几何上为一条曲线，称其为最优解曲线。如下图： 折线法的思想是用一条折线代替精确解曲线 d ∗ ( Δ ) d^*(\Delta) d∗(Δ)。为了构造合适的折线，首先分析子问题解的特性。若 B B B正定且 ∣ ∣ − B − 1 ∇ f ( x ) ∣ ∣ ≤ Δ ||-B^{-1} \nabla f(x)|| \le \Delta ∣∣−B−1∇f(x)∣∣≤Δ，则精确解为： d ∗ ( Δ ) = − b − 1 ∇ f ( x ) = △ d B d^*(\Delta) = -b^{-1} \nabla f(x) \overset {\bigtriangleup } {=} d^B d∗(Δ)=−b−1∇f(x)=△dB 否则，我们可作如下分析。当 Δ \Delta Δ很小时，信赖域子问题中目标函数的二次项的作用不大。因此，可用函数 f ( x ) f(x) f(x)的一次（线性）近似，此时约束在 ∣ ∣ d ∣ ∣ ≤ Δ ||d|| \le \Delta ∣∣d∣∣≤Δ下，子问题的近似解为 d ∗ ( Δ ) ≈ − Δ ∇ f ( x ) ∣ ∣ ∇ f ( x ) ∣ ∣ d^*(\Delta) \approx - \Delta \frac {\nabla f(x)} {||\nabla f(x)||} d∗(Δ)≈−Δ∣∣∇f(x)∣∣∇f(x)​。这显示可采用最速下降方向作为解曲线的近似。基于最速下降的考虑和省略信赖域约束，我们取子问题解的形式为 d = − τ ∇ f ( x ) d = -\tau \nabla f(x) d=−τ∇f(x)。通过目标函数极小化可确定子问题沿最速下降方向的解为： d U = − ∇ f ( x ) T f ( x ) ∇ f ( x ) T B ∇ f ( x ) ∇ f ( x ) d^U = - \frac {\nabla f(x)^Tf(x)} {\nabla f(x)^TB\nabla f(x)} \nabla f(x) dU=−∇f(x)TB∇f(x)∇f(x)Tf(x)​∇f(x) 另一方面，为了得到收敛性能更好的搜索方向，我们可以选择牛顿方向 d B d^B dB。由两方向 d U d^U dU和 d B d^B dB可分段构造折线搜索方向（如上图）。记由上图方式构造出的折线为 d ~ ( τ ) \tilde d(\tau) d~(τ)，数学上的定义为： d ~ ( τ ) = { τ d U , 0 ≤ τ ≤ 1 d U + ( τ − 1 ) ( d B − d U ) , 1 ≤ τ ≤ 2 \tilde d(\tau) = \left\{ \begin{aligned} & \tau d^U ,& 0 \le \tau \le 1\\\\ & d^U + (\tau -1)(d^B - d^U), &1 \le \tau \le 2 \end{aligned} \right. d~(τ)=⎩⎪⎨⎪⎧​​τdU,dU+(τ−1)(dB−dU),​0≤τ≤11≤τ≤2​ 上式说明当 τ \tau τ较小时方向选用最速下降方向 d U d^U dU，否则取 d U d^U dU和 d B d^B dB的组合方向。