02无约束最优化方法的基本结构

Lingfeng2024-09-19

02无约束最优化方法的基本结构

1. 收敛性和收敛速度

Definition (收敛速度)

时,称算法是线性收敛的;当时,称算法是超线性收敛的。
其中为任意常数,此时称算法是二阶收敛的。

2. 线搜索准则

2.1 精确线搜索准则

Definition (精确线搜索)

当迭代方向已知时,精确线搜索准则使沿关于步长取极小值,即

Theorem (精确线搜索性质)

达到精确线搜索时,令,此时有

证明

注意到由链式法则
即得

2.2 非精确线搜索准则

Definition (Armijo准则)

Definition (Goldstein准则)

Definition (Wolfe准则)

Definition (强Wolfe准则)

3. 线搜索求步长

3.1 0.618方法

Definition (0.618方法)

  1. 通过进退法求得初始区间,其包含的极小点。
  2. 得到初始区间后,按照0.618比例不断缩小,使极小点始终包含在缩小的区间中,直至区间足够小。

是区间上的单峰函数,,选择两个点使得

其中。此时若,则,取,反之取另一区间。

此时我们需要使用相同比例缩小区间,并且使得是重合的。此时有

因此
即得到

3.2 多项式插值法

Definition (多项式插值法)

  1. 构造近似的多项式函数,求其极小点,检验是否满足非精确线搜索准则。
  2. 若不满足,根据新信息构造新的多项式函数,如此反复。

Definition (两点二次插值法)

已知在,且不满足准则。此时构造

计算出极小点

Definition (三点三次插值法)

已知在三个点有,且不满足准则。此时构造

计算出极小点

4. 信赖域方法

4.1 定义

Definition (信赖域方法)

设定信赖域半径,在领域内根据泰勒展开式用二次函数近似,即

此时求出在领域内的极小点
此时,重复以上步骤。

其中定义比值

  • 接近1(),则增大)。
  • 接近0(),则缩小)。
  • ,则)。
  • ,则令,缩小,重新求解。

4.2 信赖域子问题求解

Definition (Dogleg方法)

  1. 给出
  2. 计算,若,则
  3. 如果,则
  4. 否则,计算,使得
Last Updated 12/13/2025, 12:57:16 PM