《《搜索算法结构教学》PPT课件》由会员分享，可在线阅读，更多相关《《搜索算法结构教学》PPT课件（66页珍藏版）》请在金锄头文库上搜索。
1、3.1 3.1 3.1 3.1 搜索算法结构搜索算法结构搜索算法结构搜索算法结构一、下降算法模型一、下降算法模型 考虑（考虑（NP） 常用一种线性搜索的方式来求解：迭代中从常用一种线性搜索的方式来求解：迭代中从一点出发沿一点出发沿下降可行方向下降可行方向找一个新的、性找一个新的、性质有改善的点。质有改善的点。迭代计算：其中 为第 次迭代的搜索方向， 为沿 搜索的最佳步长因子（通常也称作最佳步长）。min f(x) s.t. xS第三章第三章 常用的一维搜索方法常用的一维搜索方法可行方向：设可行方向：设 S，dRn,d0,若存在若存在 ，使，使 ，称，称d 为为 点的点的可行方向。可行方向。同时
2、满足上述两个性质的方向称同时满足上述两个性质的方向称下降可行方向下降可行方向。下降方向下降方向 ： 设设 S，d Rn,d0,若存在若存在 ，使，使 ，称，称d 为为 在在 点的下降方向。点的下降方向。l模型算法模型算法线性搜索求线性搜索求 ，新点新点使使x(k+1)S初始初始x(1) S, k =1对对x(k)点选择下降点选择下降可行方向可行方向d(k)是否满足停机条件？是否满足停机条件？停停k=k+1yesno531二、二、收敛性收敛性概念概念： 考虑（考虑（NP）设迭代算法产生点列设迭代算法产生点列x(k) S.1. 理想的收敛性：设理想的收敛性：设x*S是是(全局最优解全局最优解).当
3、当x* x(k) 或或 x(k) x*， k，满足满足 时，称算法收敛到最优解时，称算法收敛到最优解 x*。 min f(x) s.t. xS 由于非线性规划问题的复杂性，实用中建立下列收由于非线性规划问题的复杂性，实用中建立下列收敛性概念敛性概念 ：2. 实用收敛性：定义解集实用收敛性：定义解集 S* = x | x 具有某种性质具有某种性质 例：例：S*= S*= S*=x| f(x)=0 S*=x|f(x) (为给定的实数阈值为给定的实数阈值)2.实用收敛性（续）实用收敛性（续）收敛性：设解集收敛性：设解集S* ，x(k)为算法产生的点为算法产生的点列。下列情况之一成立时，称算法收敛：列
4、。下列情况之一成立时，称算法收敛： 1 x(k) S*; 2x(k) S*， k，x(k)的任意极限点的任意极限点x* S* 。 全局收敛全局收敛：对任意初始点：对任意初始点x(1),算法均收敛。算法均收敛。 局部收敛局部收敛：当：当x(1) 充分接近解充分接近解x*时，算法收敛。时，算法收敛。有限步终止有限步终止三、收敛速度三、收敛速度 设算法产生点列设算法产生点列x(k) 收敛到解收敛到解x*，且，且x(k)x*, k，关于算法的收敛速度，有关于算法的收敛速度，有1.线性收敛：线性收敛： 当当k充分大时成立。充分大时成立。2.超线性收敛：超线性收敛： 3.二阶收敛：二阶收敛： 0，是是 使
5、当使当k充分大时有充分大时有三、收敛速度（续）三、收敛速度（续）定理：设算法点列定理：设算法点列x(k)超线性收敛于超线性收敛于x*,且且x(k)x*， k，那么那么证明：证明：只需注意只需注意| |x(k+1) x* | -| x(k) x* | | |x(k+1) x(k) | |x(k+1) x* | +| x(k) x* | ，除以，除以| x(k) x* | 并令并令k，利用超线性收敛定义可得结果。利用超线性收敛定义可得结果。该结论导出算法的停止条件可用：该结论导出算法的停止条件可用：四、二次终结性四、二次终结性一个算法用于解正定二次函数的无约束极小一个算法用于解正定二次函数的无约束
6、极小时，有限步迭代可达最优解，则称该算法具时，有限步迭代可达最优解，则称该算法具有有二次终结性二次终结性。问题描述：问题描述：问题描述：问题描述：已知并且求出了处的可行下降方向从出发， 沿方向求如下目标函数的最优解，或者选取使得：常用的一维搜索算法常用的一维搜索算法常用的一维搜索算法常用的一维搜索算法设其最优解为（叫精确步长因子），所以线性搜索是求解一元函数的最优化问题（也叫一维最优化问题或一般地，一维优化问题可描述为：于是得到一个新点：一维搜索）。或解一般地，线性搜索算法分成两个阶段：第一阶段确定包含理想的步长因子（或问题最优解）的搜索区间；第二阶段采用某种分割技术或插值方法缩小这个区间。
7、搜索区间的确定搜索区间的确定 黄金分割法黄金分割法法法) 二次插值法二次插值法 Newton法法要点：要点：单峰函数的消去性质、进退算法基本思想、黄金分割单峰函数的消去性质、进退算法基本思想、黄金分割法基本思想、重新开始、二次插值法要求、极小化框架、法基本思想、重新开始、二次插值法要求、极小化框架、Newton法基本思想、方法比较。法基本思想、方法比较。我们主要介绍如下一些搜索方法：我们主要介绍如下一些搜索方法：学习的重要性：学习的重要性：1、工程实践中有时需要直接使用；工程实践中有时需要直接使用；2、多变量最优化的基础，迭代中经常要用到。多变量最优化的基础，迭代中经常要用到。方法分类：方法分
8、类：1、直接法：、直接法：迭代过程中只需要计算函数值；迭代过程中只需要计算函数值；2、微分法：、微分法：迭代过程中还需要计算目标函数的导数；迭代过程中还需要计算目标函数的导数；f(x)xab3.2 搜索区间的确定搜索区间的确定 常用的一维直接法有常用的一维直接法有消去法消去法和和近似法近似法两类。它们都是从两类。它们都是从某个初始搜索区间出发，利用某个初始搜索区间出发，利用单峰函数的消去性质单峰函数的消去性质，逐步缩，逐步缩小搜索区间，直到满足精度要求为止。小搜索区间，直到满足精度要求为止。3.2.1 单峰函数单峰函数 连续单峰函数连续单峰函数f(x)xab不连续单峰函数不连续单峰函数f(x)
9、xab离散单峰函数离散单峰函数f(x)xa 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)xab(I) 消去消去a, x1 x*
10、x1x2f(x)xab(II) 消去消去x2, bx*x2x1(II) (II) 若若f(x1) f(x2), x*a,x2在单峰函数的区间内，计算两个点的函数值，比较大小后，就在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，若再计算另一点的函数值，比较后就可进一步缩小搜索区间若再计算另一点的函数值，比较后就可进一步缩小搜索区间 .（I） 若若f(x1)f(x2)，x*x1,b3.2.2 进退算法进退算法 (或称成功或称成功-失败失败法法)如何确定包含极小点在内的初始区间如何确定包
11、含极小点在内的初始区间 ?（一）（一）基本思想：基本思想：由单峰函数的性质可知，函数值在极小点左边严格下降，在右由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升。边严格上升。f(x)xabx*x0 x1x2从某个初始点出发，沿函数值下降的方向前进，直至发现函数从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。值上升为止。由由两边高，中间低的三点两边高，中间低的三点，可确定极小点所在的初始区间。，可确定极小点所在的初始区间。（二）（二）算法算法1、选定初始点选定初始点a 和步长和步长h;f(x) x2、计算并比较计算并比较f(a)和和f(a+h)；有前进；有前进(
12、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+3hf(x) xaa+ha+7ha1b1a-ha-3ha-7ha1b1 则将步长改为则将步长改为h。计算。计算f(ah), 若若f(ah) f(a)， 令令 a1=ah, a2=a+h, 停止运算；否则将步长加倍，继续后
13、退。停止运算；否则将步长加倍，继续后退。仅仅找区间！若进一步找仅仅找区间！若进一步找最小点，参阅最小点，参阅P44!(三三) 几点说明几点说明缺点：效率低；缺点：效率低；优点：可以求搜索区间；优点：可以求搜索区间；注意：注意：h 选择要适当，选择要适当，初始步长不能选得太小初始步长不能选得太小； 3.3 区间消去法黄金分割法区间消去法黄金分割法 消去法的思想：消去法的思想：反复使用单峰函数的消去性质，不断缩小包含极小点的反复使用单峰函数的消去性质，不断缩小包含极小点的搜索区间，直到满足精度为止。搜索区间，直到满足精度为止。 消去法的优点：消去法的优点：只需计算函数值，通用性强。只需计算函数值，
14、通用性强。 消去法的设计原则：消去法的设计原则：（1）迭代公式简单；（）迭代公式简单；（2）消去效率高；）消去效率高；（3）对称：）对称： x1 a = b-x2 ；（4）保持缩减比：）保持缩减比：=(保留的区间长度保留的区间长度原区间长度原区间长度) 不变。（使每次保留下来的节点，不变。（使每次保留下来的节点， x1或或 x2 ，在下一次的，在下一次的比较中成为一个相应比例位置的节点比较中成为一个相应比例位置的节点 ）。）。 （一）（一）黄金分割黄金分割 xabL LL ( (1 1) )L L取 “ ”， （二）（二）黄金分割法的基本思想黄金分割法的基本思想 黄金分割重要的黄金分割重要的消
15、去性质消去性质: x2abL LL ( (1 1) )L Lx1 LL ( (1 1) )L L设设x1 ，x2 为为a, b 中对称的两个黄金分割点，中对称的两个黄金分割点，x1为为a,x2的的黄金分割点黄金分割点x2为为x1,b的黄金分的黄金分割点割点 在在进进行行区区间间消消去去时时，不不管管是是消消去去a, x1，还还是是消消去去x2，b，留留下下来来的的区区间间中中还还含含一一个个黄黄金金分分割割点点，只只要要在在对对称称位位置置找找另另一一个个黄黄金金分分割割点点，又可以进行下一次区间消去。又可以进行下一次区间消去。 每次消去后，新区间的长度是原区间的倍，经过每次消去后，新区间的长
16、度是原区间的倍，经过n次消去后次消去后，保，保留下来的留下来的区间长度为区间长度为nL，需，需计算函数值的次数仅为计算函数值的次数仅为n+1。 黄金分割比黄金分割比 ，所以此法也称为法。，所以此法也称为法。 （三）（三）算法算法 开始开始b-x1 x2 a 给定给定a0 , b0 , a=a0 ,b= b0 , =0.618034x2 =a+ (b-a), x1 =a+bx2f2 =f(x2), f1 =f(x1) f1 f2是是否否a=x1, x1= x2, f1 =f2 x2 =a+b- x1, f2 =f(x2) 否否b=x2, x2= x1, f2 =f1 x1 =a+b- x2, f1 =f(x1) 否否x*a, x2x*x1, bx*=x1, f*=f1结束结束是是x*=x2, f*=f2是是abx2x1x1 x2 = ab! 在迭代过程中，四个点的顺序始终应该是在迭代过程中，四个点的顺序始终应该是 ax1 x2 b但在计算第二个分割点时使用但在计算第二个分割点时使用x1 =a+bx2 或或 x2 =a+b x1, 由于舍入误差的由于舍入误差的影响，可能破坏影响，可能破坏a
