运筹学与最优化方法（华南理工）第4章（071）

1、第 三 章,无约束最优化方法,3.1 常用的搜索算法结构,一、收敛性概念： 考虑（fs） 设迭代算法产生点列x(k) S. 1. 理想的收敛性：设x*S是g.opt.当x* x(k) 或 x(k) x*， k，满足 时，称算法收敛到最优解 x*。,3.1 常用的搜索算法结构,由于非线性规划问题的复杂性，实用中建立下列收敛性概念 ： 2. 实用收敛性：定义解集 S* = x | x 具有某种性质 例：S*=x|x-g.opt S*=x|x-l.opt S*=x| f(x)=0 S*=x|f(x) (为给定的实数，称为阈值),3.1 常用的搜索算法结构,一、收敛性概念： 考虑（fs）2.实用收敛性

2、（续） 收敛性：设解集S* ，x(k)为算法产生的点列。下列情况之一时，称算法收敛： 1x(k) S*; 2x(k) S*， k，X(k)任意极限点S* 。 全局收敛：对任意初始点x(1),算法均收敛。 局部收敛：当x(1) 充分接近解x*时，算法才收敛。(P42例),3.1 常用的搜索算法结构,二、收敛速度 设算法产生点列x(k),收敛到解x*,且x(k)x*， k， 1.线性收敛： 当k充分大时成立。 2.超线性收敛： 3.二阶收敛： 0，是 使当k充分大时有,3.1 常用的搜索算法结构,二、收敛速度（续） 定理：设算法点列x(k)超线性收敛于x*,且x(k)x*， k，那么 证明只需注意

3、 | |x(k+1) x* | -| x(k) x* | | |x(k+1) x(k) | |x(k+1) x* | +| x(k) x* | ，除以| x(k) x* | 并令k，利用超线性收敛定义可得结果。,3.1 常用的搜索算法结构,三、二次终结性 一个算法用于解正定二次函数的无约束极小时，有限步迭代可达最优解，则称该算法具有二次终结性。 二次终结性=共轭方向+精确一维搜索。 共轭方向 定义： 设 Ann 对称正定，d (1),d (2) Rn , d (1) 0，d(2) 0，满足d(1)TAd(2)=0, 称d(1),d(2) 关于矩阵A共轭。 ：d(1),d(2), ,d(m) R

4、n 均非零，满足d(i)TAd(j)=0,(ij) ,则向量组d(1),d(2), ,d(m)称为关于 A的共轭向量组,3.1 常用的搜索算法结构,三、二次终结性（续） 当A=I(单位矩阵)时， d(1)TAd(2)= d(1)Td(2)=0，即正交关系。 当d(1),d(2), ,d(m) 关于正定矩阵A两两共轭时， d(1),d(2), ,d(m) 线性无关。 proof: 设d= 1 d(1)+ 2d(2)+ md(m) =0， j=1,2, ,m， d(j)TAd= jd(j)TAd(j)=0 d(j)TAd(j) 0，故j =0，即线性无关。 超线性收敛和二次终结性常用来讨论算法的优

5、点。,3.1 常用的搜索算法结构,四、下降算法模型 考虑（fs） 常用一种线性搜索的方式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改善的点。 下降方向 ： 设 S，d Rn,d0,若存在 ，使 ，称d 为 在 点的下降方向。,3.1 常用的搜索算法结构,四、下降算法模型（续） 可行方向：设 S，dRn,d0,若存在 ，使 ，称d 为 点的可行方向。 同时满足上述两个性质的方向称下降可行方向。,3.1 常用的搜索算法结构,模型算法,线性搜索求 ，得到 新点 使x(k+1)S,yes,no,3.2 一维搜索,一元函数求极小及线性搜索均为一维搜索。常用于求： min f(x(k)+ d

6、(k)=() s.t. S S有3种情况（-，+）或（0， + ）或a,b 一、平均法(二分法) a,b, (P43),3.2 一维搜索,二、缩小区间的精确一维搜索：考虑问题(P) min () s.t. , ():RR 1、不确定区间及单峰函数 不确定区间： , 含()的最小点，但不知其位置,3.2 一维搜索,二、缩小区间的精确一维搜索（续） 定义：设： , R， * , 是在, 上的最小点 ，若对任意1 ,2, 1 (2); 2 若1 * ，则(1) (2). 则称()在, 上强单峰。 若只有当(1) (* )， (2) (* )时，上述1, 2 式才成立，则称()在, 上单峰。,3.2

7、一维搜索,二、缩小区间的精确一维搜索（续） 若对任意1 ,2, 1 (2); 2 若1 * ，则(1) (2). 则称()在, 上强单峰。 若只有当(1) (* )， (2) (* )时，上述1, 2 式才成立，则称()在, 上单峰。,3.2 一维搜索,二、缩小区间的精确一维搜索（续） 定理：设：RR 在， 上单峰， 。那么 1若() ()，则() ()， ，；如左下图 2若() ()，则()()， ， ；如右下图,3.2 一维搜索,二、缩小区间的精确一维搜索（续） Proof. 1反证：设 * ,为最小点，,及*，使 () ()，矛盾（假设）； 若* ,），由定义及 *， ( ) (), 矛

8、盾（条件）； 于是结论成立。 2 的证明类似（略）。 注：上述定理为缩短区间的算法提供了理论根据。,3.2 一维搜索,二、缩小区间的精确一维搜索（续） 2、黄金分割法（0.618 法） 通过上述定理，选二点 ,比较 () 与 ( ),可去掉 ,或者 ,.考虑条件： 1对称： - = - （使“坏”的情况去掉，区间长度不小于“好”的情况） 2保持缩减比 t=(保留的区间长度原区间长度) 不变。 （使每次保留下来的节点， 或 ，在下一次的比较中成为一个相应比例位置的节点 ）。 推导缩减比 t : 如图设第一次保留, (去掉, ),那么第二次保留的长度为, ,则,3.2 一维搜索,二、缩小区间的精确

9、一维搜索 2、黄金分割法（0.618 法）（续） 整理 ： = +t( - ) = +t( - ) 结合式：t2+t-1=0 故 t0.618 注意 上式有 t2=1-t , 故有 = +t( - ) = + （1-t）( - ) （算法框图见下页）,3.2 一维搜索,二、缩小区间的精确一维搜索 之 黄金分割法（0.618 法）（算法）,3.2 一维搜索,3、中点法： 设 ()在 ,上可微，且当导数为零时是解。取=(+) 2，那么 ()=0 时， 为最小点， = * ； ()0 时， 在上升段， * ，去掉 , ； (自己画算法框图),3.2 一维搜索,4、进退法求初始不确定区间 找三点使两端

10、点的函数值大于中间点的函数值。 思路：任取0，步长 0，取1=0 + ， 1若(0 )(0),则停，= 2，= 1 (图1) 2若(0 )(1), 令=2 , 2=1 + ， 若(2 )(1),则停，= 0 ，= 2 (图2),3.2 一维搜索,4、进退法求初始不确定区间（续） （自己画算法框图） 注意：1 选择要适当。（太大含多个单峰区间，太小迭代次数增加）； 2（ ）单调时无结果，（加迭代次数限制）； 3可与中点法结合寻找单调区间（思考）。,3.2 一维搜索,三、牛顿法（Newton）和插值法 1、Newton法： 对 在 k 点展开： ( )= (k )+ (k )(- k ) + (1

11、/2) (k )(- k )2 + o (- k )2 取二次式（略去高阶项）： qk() = (k) +(k)(-k) + (1/2)(k)(-k)2,3.2 一维搜索,二、牛顿法（Newton）和插值法 1、Newton法：（续） 用qk()作为()的近似，当(k) 0时，其驻点为极小点： qk()= (k) +(k)(- k )=0 得 k +1=k (k) /(k) 取k +1为新的迭代点。 以上过程即Newton法。 特点：二阶、局部收敛。 （算法框图见下页）,3.2 一维搜索,Newton法算法框图：,3.2 一维搜索,二、牛顿法（Newton）和插值法 1、Newton法：（续）

12、 Ex. 求 min ()= arctan t d t 解： () =arctan , ()=1(1+ 2) 迭代公式： k +1= k - (1+ 2) arctan k 取1= 1，计算结果： k k (k) 1(k ) 1 1 0.7854 2 2 -0.5708 -0.5187 1.3258 3 0.1169 -0.1164 1.0137 4 -0.001095 -0.001095 4 * =0 取1=2，计算结果如下：,3.2 一维搜索,二、牛顿法（Newton）和插值法 1、Newton法：（续） k k (k) 1(k ) 1 2 1.1071 5 2 -3.5357 -1.29

13、52 13.50 3 13.95 不收敛。 2、插值法： 用()在2 或3 个点的函数值或导数值，构造2 次或3次多项式作为()的近似值，以这多项式的极小点为新的迭代点。 3点2次，2点2次，4点3次，3点3次，2点3次等 以3点2次为例： 取 1， 2，3，求出(1)， (2)， (3),3.2 一维搜索,二、牛顿法（Newton）和插值法 2、插值法：（续） 设二次插值多项式：a2 +b +c= () a12 +b1 +c= (1) a22 +b2 +c= (2) a32 +b3 +c= (3) 解得a,b,3.2 一维搜索,三、不精确一维搜索： min f(x) 考虑从x(k)点出发，沿方向d(k)寻找新迭代点： x(k) +kd(k) 要求: 1f(x(k) +kd(k)0不能太小。 总体希望收敛快，每一步不要求达到精确最小，速度快，虽然步数增加，则整个收敛达到快速。 一个实用方法：为了方便，省去上标： 设 f:RnR。在x 取方向 d , 有f T(x)d0 (即d为下降方向) 求使 1f(x+ d) f