第4章 最优化搜索算法的结构与一维搜索PPT讲稿.ppt

第4章 最优化搜索算法的结构与一维搜索1第1页，共31页，编辑于2022年，星期一4.1 4.1 常用的搜索算法结构常用的搜索算法结构一、收敛性概念：一、收敛性概念：考虑（考虑（fs）设迭代算法产生点列设迭代算法产生点列x(k)S.1.理想的收敛性：设理想的收敛性：设x*S是是g.opt.当当x*x(k)或或 x(k)x*，k，满足满足 时，称算法收敛到最优解时，称算法收敛到最优解 x*。2第2页，共31页，编辑于2022年，星期一4.1 4.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第3页，共31页，编辑于2022年，星期一4.1 4.1 常用的搜索算法结构常用的搜索算法结构一、收敛性概念：一、收敛性概念：考虑（考虑（fs）2.实用收敛性（续）实用收敛性（续）收敛性：设解集收敛性：设解集S*，x(k)为算法产生的为算法产生的点列。下列情况之一成立时，称算法收敛：点列。下列情况之一成立时，称算法收敛：1 x(k)S*;2x(k)S*，k，X(k)任意极限点任意极限点S*。全局收敛：对任意初始点全局收敛：对任意初始点x(1),算法均收敛。算法均收敛。局部收敛：当局部收敛：当x(1)充分接近解充分接近解x*时，算法才收敛。时，算法才收敛。4第4页，共31页，编辑于2022年，星期一4.1 4.1 常用的搜索算法结构常用的搜索算法结构二、收敛速度二、收敛速度 设算法产生点列设算法产生点列x(k),收敛到解收敛到解x*,且且x(k)x*，k，1.线性收敛：线性收敛：当当k充分大时成立。充分大时成立。2.超线性收敛：超线性收敛：3.二阶收敛：二阶收敛：0，是，是 使当使当k充分大时有充分大时有5第5页，共31页，编辑于2022年，星期一4.1 4.1 常用的搜索算法结构常用的搜索算法结构二、收敛速度（续）二、收敛速度（续）定理：设算法点列定理：设算法点列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第6页，共31页，编辑于2022年，星期一4.1 4.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)Rn 均非零，均非零，满足满足d(i)TAd(j)=0,(ij).7第7页，共31页，编辑于2022年，星期一4.1 4.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 1 d(1)+2 2d(2)+m md(m)=0，j=1,2,m，d(j)TAd=jd(j)TAd(j)=0 d(j)TAd(j)0，故，故 j j =0，即线性无关。，即线性无关。超线性收敛和二次终结性常用来讨论算法的优点。超线性收敛和二次终结性常用来讨论算法的优点。正定正定8第8页，共31页，编辑于2022年，星期一4.1 4.1 常用的搜索算法结构常用的搜索算法结构四、下降算法模型四、下降算法模型 考虑（考虑（fs）常用一种线性搜索的方式来求解：迭代中从一常用一种线性搜索的方式来求解：迭代中从一点出发沿下降可行方向找一个新的、性质有改点出发沿下降可行方向找一个新的、性质有改善的点。善的点。下降方向下降方向 ：设设 S，d Rn,d0,若存在若存在 ，使，使 ，称，称d 为为 在在 点的下降方向。点的下降方向。min f(x)s.t.xS9第9页，共31页，编辑于2022年，星期一4.1 4.1 常用的搜索算法结构常用的搜索算法结构四、下降算法模型（续）四、下降算法模型（续）可行方向：设可行方向：设 S，dRn,d0,若存在若存在 ，使，使 ，称，称d 为为 点的可行方向。点的可行方向。同时满足上述两个性质的方向称同时满足上述两个性质的方向称下降可行方向。下降可行方向。10第10页，共31页，编辑于2022年，星期一4.1 4.1 常用的搜索算法结构常用的搜索算法结构l模型算法模型算法线性搜索求线性搜索求 ，新点新点使使x(k+1)S初始初始x(1)S,k=1对对x(k)点选择下降点选择下降可行方向可行方向d(k)是否满足停机条件？是否满足停机条件？停停k=k+1yesno11第11页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索一元函数求极小及线性搜索均为一维搜索。常用于求：一元函数求极小及线性搜索均为一维搜索。常用于求：min f(x(k)+d(k)=()s.t.S S有有3种情况种情况（-，+）或（）或（0，+）或）或a,b一、缩小区间的精确一维搜索：一、缩小区间的精确一维搜索：考虑问题考虑问题(P)min()s.t.,():RR1、不确定区间及单峰函数、不确定区间及单峰函数 不确定区间：不确定区间：,含含()的最小点，但不知其位置的最小点，但不知其位置12第12页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索一、缩小区间的精确一维搜索（续）一、缩小区间的精确一维搜索（续）定义：定义：设设：,R，*,是是在在,上的最小点上的最小点，若对任意，若对任意1,2,1 (2);2 若若1*，则，则(1)(2).则称则称()在在,上上强单峰强单峰。若只有当若只有当(1)(*)，(2)(*)时，时，上述上述1,2 式才成立，式才成立，则称则称()在在,上上单峰单峰。13第13页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索一、缩小区间的精确一维搜索（续）一、缩小区间的精确一维搜索（续）若对任意若对任意1,2,1 (2);2 若若1*，则，则(1)(2).则称则称()在在,上上强单峰强单峰。若只有当若只有当(1)(*)，(2)(*)时，上述时，上述1,2 式才成立，式才成立，则则称称()在在,上上单峰单峰。*12 强单峰强单峰 *单峰单峰14第14页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索一、缩小区间的精确一维搜索（续）一、缩小区间的精确一维搜索（续）定理：设定理：设：RR 在在，上单峰，上单峰，。那么。那么 1若若()()，则，则()()，；如左下图；如左下图 2若若()()，则，则()()，；如右下图；如右下图 15第15页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索一、缩小区间的精确一维搜索（续）一、缩小区间的精确一维搜索（续）Proof.1反证：设反证：设*,为最小点，为最小点，,及及 *，使，使()()()，矛盾（假，矛盾（假设）；设）；l 若若*,），由定义及），由定义及 *，()(),矛盾（条件）；矛盾（条件）；于是结论成立。于是结论成立。2 的证明类似（略）。的证明类似（略）。注：上述定理为缩短区间的算法提供了理论根据。注：上述定理为缩短区间的算法提供了理论根据。16第16页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索一、缩小区间的精确一维搜索（续）一、缩小区间的精确一维搜索（续）2、黄金分割法（、黄金分割法（0.618 法）法）通过上述定理，选二点通过上述定理，选二点0 =+（1-t）(-)=+t(-)-0?No=,=+t(-)yes=,=+（1-t）(-)No 19第19页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索3、中点法：、中点法：设设()在在 ,上可微，且当导数为零时是解。取上可微，且当导数为零时是解。取=(+)2，那，那么么 ()=0 时，时，为最小点，为最小点，=*；()0 时，时，在上升段，在上升段，*，去掉，去掉,；()，去掉，去掉,；(自己画算法框图自己画算法框图)tg 0()tg 0，取，取1=0+，1若若(0)(1),令令=2（步长加倍），（步长加倍），2=0-，若若(2)(0),则停，则停，=2，=1 (图图1)2若若(0)(1),令令=2,2=1+，若若(2)(1),则停，则停，=0，=2 (图图2)2 0 1 向左找2 图图1 0 1 2 向右找2 图图221第21页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索4、进退法求初始不确定区间（续）（自己画算法框图）（自己画算法框图）注意：注意：1 选择要适当。（太大含多个单峰区间，选择要适当。（太大含多个单峰区间，太小迭代次数增加）；太小迭代次数增加）；2（）单调时无结果，（加迭代次数）单调时无结果，（加迭代次数限制）；限制）；3可与中点法结合寻找单调区间（思考）。可与中点法结合寻找单调区间（思考）。22第22页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索二、牛顿法（二、牛顿法（Newton）和插值法）和插值法1、Newton法：法：对对 在在 k 点展开：点展开：()=(k)+(k)(-k)+(1/2)(k)(-k)2 +o(-k)2 取二次式（略去高阶项）：取二次式（略去高阶项）：qk()=(k)+(k)(-k)+(1/2)(k)(-k)2 23第23页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索二、牛顿法（二、牛顿法（Newton）和插值法）和插值法1、Newton法：法：（续）（续）用用qk()作为作为()的近似，当的近似，当(k)0时，其时，其驻点为极小点：驻点为极小点：qk()=(k)+(k)(-k)=0 得得 k+1=k(k)/(k)取取k+1为新的迭代点。为新的迭代点。以上过程即以上过程即Newton法。法。特点：特点：二阶、局部收敛。二阶、局部收敛。（算法框图见下页）（算法框图见下页）24第24页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索Newton法算法框图：法算法框图：初始1,1,2 0k=1 (k)0?N停，失败Yk+1=k-(k)(k)|k+1-k|2 YNk=k+125第25页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索二、牛顿法（二、牛顿法（Newton）和插值法）和插值法1、Newton法：法：（续）（续）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，计算结果如下：，计算结果如下：26第26页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索二、牛顿法（二、牛顿法（Newton）和插值法）和插值法1、Newton法：法：（续）（续）k k (k)1(k)1 2 1.1071 5 2 -3.5357 -1.2952 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)27第27页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索二、牛顿法（二、牛顿法（Newton）和插值法）和插值法2、插值法、插值法：（续）：（续）设二次插值多项式：设二次插值多项式：a2+b+c=()a12+b1+c=(1)a22+b2+c=(2)a32+b3+c=(3)解得解得a,b28第28页，共31页，编辑于2022年，星期一4.2 4.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(x)+f T(x)d 2 f T(x+d)d f T(x)d 其中其中（0，12），），（，1）为取定参数。）为取定参数。实际中常取实际中常取=0.1,=0.7 附近。附近。29第29页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索三、不精确一维搜索：（续）（续）f(x(k)30第30页，共31页，编辑于2022年，星期一4.2 4.2 一维搜索一维搜索三、不精确一维搜索：（续）（续）=1，1是否成立？是否成立？NoYes2是否成立？是否成立？Yes停；停；k=No=(32)=(12)要提高精确度可把要提高精确度可把2改为：改为：2|f T(x+d)d|-f T(x)d当当=0 时变成精确一维搜索。时变成精确一维搜索。此方法一般经几次迭代即可得到满意的此方法一般经几次迭代即可得到满意的k。31第31页，共31页，编辑于2022年，星期一