运筹学 非线性规划2

1、xjtu非线性规划1,.kkkkkkkkxpxxxp：给定如何确定移动步长，目使得的()().kkkkf xpf x一般要求：,k选择步长使其满足四 线性搜索方法线性搜索方法的分类:精确线性搜索法不精确线性搜索法直接搜索法插值法精确线性搜索0min ( ) ( )()kkkf xp 0() = min()kkkkkkf xpf xpxjtu非线性规划极值的必由要条件：( )()0)kktkf xpp ( ) 因为难于找到的全局极小点)urry.c(k ：取( )的最小正根作为的极小点准则min()0,0kktkkf xppin practice,( ).f x 除非特殊情况(如为二次函数)，寻

2、求 ( )的精确极小点是不可能在内限步实现的有数值分析 非线性方程求根的方法 newton法 割线法 简单迭代法等k应为下列方程的非负根xjtu非线性规划hesse精确线性搜索往往要用到梯度，二阶阵计算量大 对某些非光滑函数、导数表达式很复杂难于应用搜索区间的确定 , 0,) ka b要求事先知道包含的某个区间.k直接搜索法、插求值法搜索区间 , ( )a b 在上求的(近似)极小点.*( )f xx对一般的(mp),在包含局部最优解 的某个区域上为凸函数*( )()kktf xp 在包含极小点的某个区间上关于 为凸.xjtu非线性规划 , a b确定的基本思想：()(0,)()acb a 假

3、设为连续函数，逐步确定三点使得满足( )( )( ),acb().ab 则 在与之 间 必 有的 一 个 极 小 点001010hh 给定0,计算 (),取步长,令=,计算 ().012121,h 若 ()()，则令=，计算 ();2313,().h 否则,令=计算1( ) ()()kkk 如此继续，因为，局部凸函数，使故必存在某个21021, , abca b 若 ()()，则令 =xjtu非线性规划11, , kkkabca b0101()(),()(or) 若开始时有若，0101()() 令，1010()() ，1010()() ，212().h 令=，计算21()(), 若201,.a

4、bc=2323until for som,():e kh 如否则,令=计算,。此继续1()()kk 11,.kkkabcxjtu非线性规划() 如 果 可 以 利 用的 导 数 ：*() ,xa b 在 包 含的 极 小 点的 区 间的 端 点 处 ， 必 有 ：( )0,( )0ab00,0h给定取初始点，010()0,h 若，则取010()0,h若， 则 取xjtu非线性规划*( ) ).or(ab ：已知包含的极小点的搜索区间 ，要求求为单谷函数要() , a b 函数称为是区间上的单谷函数，*( )ba baa b 若存在， 使得在上 ，严格递减，且在， 上严格递增，区间 ， 称为 (

5、 )的单谷区间.0.618法(黄金分割法)精确线性搜索法不用导数、简单易行直接搜索法defxjtu非线性规划1212 , ,a b:在搜索区间上选取两个对称点，：基本思想1212(), (),b,0.618,a 比较的大小：删除左半区间 ，或右半区间，删除后的新区间的长度是原来的倍,新区间包含原区间中的两个对称点中的一个关于这一点，再选取一个对称点根据新的两个对称点处的函数值来决定新区间的删除直至新区间的长度小于预先指定的精度为止.xjtu非线性规划0000*,( ),kkkkaa bbabkabab 记设区间经 次删除后的区间为的极小点121221, 1kkkkkkkkkkkkababba在

6、中选取两个对称点使（）（）21i.e.kkkkkkkkabbaba12 kkkkkkkkbbaaba（）（）推导过程: from which we have(2)xjtu非线性规划12(),()kk 计算1222211()(),kkkkkkkkkkbaaab 若，删除右半区间(，保留，记111111112,().kkkkkkkab 在新区间上，希望能利用处的函数值故取，再依对称的原则确定+1+1+1+121+1+1+1+1 .kkkkkkkkabbaba同时希望两个新的分点保持原来的比例 ，即+1+1211+1+122()kkkkkkkkkkkkkkaababbaaa而由(1)和(2)得()1

7、()kkkkkkbababaxjtu非线性规划1210 0,51 0.6180339890.618 .2因为故取正根,即令从以上两个等式可得：15.2 每次分割总按比例 =0.618来选点;每次只需计算一个新点处的函数值;新区间的长度是老区间长度的0.618倍.xjtu非线性规划1211() (),)ontheotherhan,d,kkkkkkab 若在开始时删去左半区间，保留，+1+1+1112=kkkkkkabb令，则+1+1+1+12=+kkkkaba（）.12+1+1+1+11211()()kkkkkkba 比较两点，处的函数值，重复上述过程，直到note: , ()na bnba区间经 次缩小后，最终搜索区间的长度为512在古代，人们认为按0.618的比例分割线段是最协调的， 每次区间的收缩 收 比为，故0.618法 胜似黄金，故敛速度是线性称为黄的.的金分割法.xjtu非线性规划00( ) , ,0.618033989,0;a baa bbk 确定的初始搜索区间记给定，011(-)(),kkkkkbba 22(-)(),kkkkkaba 122212111111111111()()()(),(),(),kkkkkkkkkkkkkkkaabbba 若,则,计算转s4;12212+1111211+111112()(),()(),(), ()