线搜索

2744557306

求解最优化问题的基本方法是迭代算法，即采用逐步逼近的计算方法来逼近问题的精确解的方法。以最小化问题为例，在一个算法中，可先选定一个初始迭代点$x{0}\in \mathbb{R}^n$，在该迭代点处，确定一个函数值下降的方向，再确定在这个方向上的步长，从而求得下一个迭代点，依次类推，产生一个迭代点列{$x{k}$}，{$x{k}$}或其子列应收敛于问题的最优解。当给定的某种终止准则满足时，或者表明$x{k}$已满足要求的近似最优解的精度，或者表明算法已无力进一步改善迭代点，迭代结束。线搜索算法的基本结构如下：

$$
\begin{array}{l}（1） 给定初始点x_{0} \in \mathbb{R^{n}}, k:=0 \\（2）若在x_{k}点终止准则满足，则输出有关信息，停止迭代  \\（3）确定f(x)在x_{k}点的下降方向d_{k} \\（4）计算步长\alpha_{k}，使f(x_{k}+\alpha_{k} d_{k})小于f(x_{k}) \\（5）令x_{k+1}:=x_{k}+\alpha_{k} d_{k} ，k:=k+1,转（2） \\\end{array}
$$

其中包含两个基本要素：一是下降的方向；二是步长。不同的下降方向和步长可构成不同的算法，具有以上结构的最优化方法称为线搜索方法。