无约束最优化.pdf

无约束最优化 本篇文档主要介绍无约束最优化问题，同时初步介绍解该类问题目前常用的一种算法即 Quasi-Newton Method (拟牛顿法) 。在介绍无约束最优化问题之前，我们首先会从直观上引 入无约束最优化的概念，并在此基础上引入解这类问题的两个重要概念：步长和方向。由步 长的选择引入重要概念 line search，由方向的选择引入重要概念 Quasi-Newton Method 。因此 本篇介绍文档主要分为以下几个部分：无约束最优化问题引入，Line Search ，Quasi-Newton Method 和算法总结。 1．无约束最优化 对无约束最优化不熟悉的读者也许要问，什么是无约束最优化。这里以一个例子来说明 该问题。 f global minimizer local minimizer x 上图所示为一元函数f( x) 的图像，无约束最优化问题，即不对定义域或值域做任何限制的情 况下，求解函数f(x) 的最小值，上面显示两个最小值点：一个为全局最小值点，另一个为局 部最小值点。受限于算法复杂度等问题，目前大部分无约束最优化算法只能保证求取局部最 小值点。这时读者不免要问，既然只能求取局部最小值点，那为什么这类算法还能应用呢。 这是因为实际应用中，许多情形被抽象为函数形式后均为凸函数，对于凸函数来说局部最小 值点即为全局最小值点，因此只要能求得这类函数的一个最小值点，该点一定为全局最小值 点。 理解了上面的无约束最优化问题之后，我们就可以开始介绍无约束最优化的求解过程 了，对于无约束最优化的求解首先我们需要选择一个初始点x_0 ，如下所示： f 初始点 方向 x x_0 x_1 初始点选择好之后，就可以按照各种不同的无约束最优化求解算法，求解最小值点了。求解 过程中主要涉及两个概念，即从初始点开始沿“哪个方向”以及“走多远”到达下一个点处。 所谓“走多远”即之前提的“步长”的概念，“哪个方向”即方向概念。 2 ．Line Search Line search 主要用于解决之前提到的步长的概念，即方向确定好之后，需要确定从当前 点x_k 沿着该方向走多远，以便走到下一个合适的点 x_k+1 。若用p_k 代表从第 k 个点走向 第 k+1 点的方向，x_k 代表当前点，x_k+1 代表下一个点，a_k 代表步长，则存在如下的等 式： x_k+1 = x_k + a_k * p_k (1) 这里简要介绍一下p_k ，大部分 line search 方法要求p_k 为下降方向，即从当前点沿着 p_k 方向移动后导致函数值减少。由于目标是求取一个函数的最小值，因此最优的情况是求 取沿p_k 方向满足f(x_k+1) 为全局最小的 a_k 值，可用下式表示为： Ø (a_k) = f(x_k+1) = f(x_k + a_k * p_k) (2) Ø (a_k) = f(x_k + a_k * p_k) local minimizer global minimizer f (x_k) a_k 由于直接求取满足Ø (a_k)为全局最小值的 a_k 涉及到大量f(x_k + a_k * p_k) 的计算，若从求 导角度计算最小值，还会涉及到▽f _k+1 的计算，计算量较大。因此从计算量角度考虑，可 以采用如下较为折中的策略。