于海波，王希云，李 亮(太原科技大学，太原 030024)

信赖域算法是求解非线性优化问题的一类重要的数值计算方法，信赖域算法以其较强的适定性和全局收敛性受到最优化研究者们的广泛关注，一直以来是非线性规划的研究热点。对于求解如下无约束优化问题[1]，信赖域算法是一种重要的数值方法。

考虑无约束优化问题：

minF(x),x∈Rn

(1)

其中F(x)∶Rn→R是目标函数，二次连续可微，x∈Rn为待求变量。

信赖域方法的关键是每次迭代时都要求解下面形式的信赖域子问题：

(2)

其中g∈Rn为目标函数在当前迭代点的梯度，B∈Rn×n为目标函数在当前迭代点的Hessian矩阵或其近似，△∈R为信赖域半径，δ∈Rn为待求变量。当△变化时，上述信赖域子问题(2)的解δ*就形成一条空间曲线，称为最优曲线[2]。

基于信赖域子问题精确求解方法的思想，得到最优曲线的参数方程如下：

δ=-(B+μI)-g(μ≥0)

(3)

定义函数y=f(μ)=‖δ‖2=‖-(B+μI)-1g‖2，(μ≥0).则信赖域子问题的解δ*为：

当μ=0时，解δ*=-B-1g；当μ>0时，通过求解一元非线性方程：

f(μ)-△=‖-(B+μI)-1g‖2-△=0

分段割线法的思想是在B正定的前提下，利用函数f(μ)的单调减性，当给定的信赖域半径△≥‖B-1g‖2时，令μ=μ0=0，得到子问题的最优解δ*=-B-1g；当给定的信赖域半径△<‖B-1g‖2时，以适当的步长不断增大μ，从而缩小函数f(μ)的值，最终找到一个最小的正整数m，使得f(μm)-△≤0，得到方程f(μ)-△=0的有根区间[μm-1,μm].通过对节点[μk,f(μk)]，(k=0,1,…,m)进行线性插值构造m条直线，连接所有直线构成分段割线，最后在插值点[μm-1,f(μm-1)]和[μm,f(μm)]之间利用线性插值构造的线性函数代替f(μ)来求解方程f(μ)-△=0的根μ*，从而求得子问题的解δ*=-(B+μ*I)-1g.

分段割线法的缺点是：在节点处分段线性插值函数一般不具有光滑性，出现尖点，并且与函数f(μ)的误差较大。

为了克服分段割线法的上述缺陷，本文利用分段三次Hermite插值函数在节点处光滑，且与被插值函数的误差较小的优点，提出了一种求解信赖域子问题的分段Hermite插值法。

1 分段三次Hermite插值法的思想

分段Hermite插值法的思想是在分段割线法的基础上……