考虑常用一种迭代搜索的方式来求解迭代中从一点出发沿下.ppt

考虑 常用一种迭代搜索的方式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。迭代计算： 其中 为第 次迭代的搜索方向， 为沿 搜索的最佳步长因子（通常也称作最佳步长）。 min f(x) s.t. ） x∈S 第八章 非线性优化—一维搜索 下降算法模型 无约束优化求解过程 一维搜索求 ， 新点 使x(k+1)∈S 初始x(1) ∈S, k =1 对x(k)点选择下降 可行方向d(k) 是否满足停机条件？ 停 k=k+1 Y N 已知 并且求出了 处的可行下降方向 从 出发， 沿方向 求如下目标函数的最优解， 或者选取 使得： 一维搜索 搜索区间的确定 黄金分割法(0.618法) 二分法 二次插值法 要点：单峰函数的消去性质、进退算法基本思想、黄金分割法基本思想、二分法、二次插值法要求、极小化框架。 我们主要介绍如下一些搜索方法： 学习的重要性： 1、工程实践中有时需要直接使用； 2、多变量最优化的基础，迭代中经常要用到。 方法分类： 1、直接法：迭代过程中只需要计算函数值； 2、微分法：迭代过程中还需要计算目标函数的导数； f(x) x a b §1 搜索区间的确定 常用的一维直接法有消去法和近似法两类。它们都是从某个初始搜索区间出发，利用单峰函数的消去性质，逐步缩小搜索区间，直到满足精度要求为止。 §1.1 单峰函数 连续单峰函数 f(x) x a b 不连续单峰函数 f(x) x a b 离散单峰函数 f(x) x a b 非单峰函数 定义：如果函数f(x)在区间[a,b]上只有一个极值点, 则称f(x)为 [a, b]上的单峰函数。 单峰函数具有一个重要的消去性质 定理：设f(x)是区间[a,b]上的一个单峰函数，x*∈[a,b]是其极小点， x1 和x2是[a, b]上的任意两点，且ax1 x2b，那么比较f(x1)与f(x2)的值后，可得出如下结论： f(x) x a b (I) 消去[a, x1 ] x* x1 x2 f(x) x a b (II) 消去[x2, b] x* x2 x1 (II) 若f(x1) f(x2), x*∈[a,x2] 在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，若再计算另一点的函数值，比较后就可进一步缩小搜索区间 . （I） 若f(x1)≥f(x2)，x*∈[x1,b] §1.2 进退算法 (或称成功-失败法) 如何确定包含极小点在内的初始区间 ? （一）基本思想： 由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升。 f(x) x a b x* x0 x1 x2 从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。 由两边高，中间低的三点，可确定极小点所在的初始区间。 （二）算法 1、选定初始点a 和步长h; f(x) x 2、计算并比较f(a)和f(a+h)；有前进(1)和后退(2)两种情况： (1) 前进运算：若f(a) ≥f(a+h), (2) 后退运算：若f(a) f(a+h), a a+h 则步长加倍，计算f(a+3h)。若f(a+h) ≤f(a+3h)， 令 a1=a, a2=a+3h, 停止运算；否则将步长加倍，并重复上述运算。 a+3h f(x) x a a+h a+7h a1 b1 a-h a-3h a-7h a1 b1 则将步长改为－h。计算f(a－h), 若f(a－h) ≥ f(a)， 令 a1=a－h, a2=a+h, 停止运算；否则将步长加倍，继续后退。 ——仅仅找区间！ (三) 几点说明 缺点：效率低； 优点：可以求搜索区间； 注意：h 选择要适当，初始步长不能选得太小； §2 区间消去法－黄金分割法 消去法的思想：反复使用单峰函数的消去性质，不断缩小包含极小点的搜索区间，直到满足精度为止。 消去法的优点：只需计算函数值，通用性强。 消去法的设计原则：（1）迭代公式简单；（2）消去效率高； （3）对称： x1 – a = b-x2 ；（4）保持缩减比：λ=(保留的区间长度／原区间长度) 不变。（使每次保留下来的节点， x1或 x2 ，在下一次的比较中成为一个相应比例位置的节点 ）。 （一）黄金分割 x a