5.约束优化方法.ppt

《5.约束优化方法.ppt》由会员分享，可在线阅读，更多相关《5.约束优化方法.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章第五章第五章 约束优化方法约束优化方法约束优化方法约束优化方法一一.约束坐标轮换法约束坐标轮换法二二.约束随机方向法约束随机方向法三三.复合形法复合形法四四.可行方向法可行方向法五五.罚函数法罚函数法六六.拉格朗日乘子法拉格朗日乘子法七七.简约梯度法及广义简约梯度法简约梯度法及广义简约梯度法12/20/202215-1 5-1 5-1 5-1 优化方法的类型优化方法的类型优化方法的类型优化方法的类型 2 2）间接法间接法 1 1）直接法）直接法 -将迭代点将迭代点限制在可行域内限制在可行域内(可行性可行性),),步步步步降低目标函数值降低目标函数值(下降性下降性),),直至到达最优

2、点直至到达最优点.常用方法有常用方法有:约束坐标轮换法约束坐标轮换法,约束随机方向法约束随机方向法,复合形法复合形法,可行方向法可行方向法,线性逼近法等线性逼近法等.-通过变换通过变换,将约束优化问题转化为无约束优将约束优化问题转化为无约束优化问题求解化问题求解.常用方法有常用方法有:罚函数法罚函数法,拉格朗日乘子法等拉格朗日乘子法等.（可解（可解IPIP型问题）型问题）（可解各类问题）（可解各类问题）(按对约束条件的处理方法分按对约束条件的处理方法分)12/20/202225-2 5-2 5-2 5-2 约束坐标轮换法约束坐标轮换法约束坐标轮换法约束坐标轮换法一一.基本思路基本思路 可取定步

3、长、加速步长和收缩步长可取定步长、加速步长和收缩步长,但不能取最但不能取最优步长优步长;1.1.依次沿各坐标轴方向依次沿各坐标轴方向-e-e1 1,e,e2 2,e,en n方向搜索方向搜索;2.2.将迭代点限制在可行域内将迭代点限制在可行域内.对每一迭代点均需进行可行性和下降性检查对每一迭代点均需进行可行性和下降性检查.12/20/20223二二.迭代步骤迭代步骤12/20/20224三三.存在问题存在问题有时会出现死点有时会出现死点,导致输出导致输出“伪最优点伪最优点”.*为辨别真伪为辨别真伪,要用要用K-TK-T条件条件进行检查进行检查.12/20/202255-3 5-3 5-3 5-

4、3 约束随机方向法约束随机方向法约束随机方向法约束随机方向法一.一.基本思路基本思路若该方向适用、可行，则以定若该方向适用、可行，则以定步长前进；步长前进；坐标轮换法有时会输出坐标轮换法有时会输出“伪最优点伪最优点”,用随机方向法可克服这一缺点用随机方向法可克服这一缺点.若该方向不适用、可行，则产若该方向不适用、可行，则产生另一方向；生另一方向；若在某处产生的方向足够多，若在某处产生的方向足够多，仍无一适用、可行，则采用收缩仍无一适用、可行，则采用收缩步长；步长；若步长小于预先给定的误差限若步长小于预先给定的误差限则终止迭代。则终止迭代。搜索方向搜索方向-采用随机产生的方向采用随机产生的方向1

5、2/20/20226二二.随机方向的构成随机方向的构成1.1.用用RND(X)RND(X)产生产生n n个随机数个随机数2.将将(0,1)中的随机数中的随机数 变换到变换到(-1,1)中去中去;3.构成随机方向构成随机方向变换得变换得:于是于是例例:对于三维问题对于三维问题:12/20/20227X0=X,F0=F=0,F0=F(X0)F=F（X）j=1K=K+1三三.随机方向法随机方向法 的迭代步骤的迭代步骤是是K=0,j=0产生随机方向产生随机方向=0.5否否FF0j=0K m结结 束束X*=X0,F*=F0是是否否是是否否是是否否XDD是是否否12/20/202285-4 5-4 5-4

6、 5-4 复合形法复合形法复合形法复合形法一一.基本思路基本思路 在可行域内选取若干初始点并以之为顶点构成一个多在可行域内选取若干初始点并以之为顶点构成一个多面体面体(复合形复合形),),然后比较各顶点的函数值然后比较各顶点的函数值,去掉最坏点去掉最坏点,代代之以好的新点之以好的新点,并构成新的复合形并构成新的复合形,以逼近最优点以逼近最优点.有两种基本运算有两种基本运算:1)映射映射-在坏点的对侧试探新点在坏点的对侧试探新点:先计算除最坏点外各顶点的几何中先计算除最坏点外各顶点的几何中心心,然后再作映射计算然后再作映射计算.2)收缩收缩-保证映射点的保证映射点的“可行可行”与与“下降下降”X

7、1为最坏点为最坏点-映射系数映射系数常取常取 若发现映射点不适用、可行若发现映射点不适用、可行,则将则将 减半后重新映射减半后重新映射.12/20/20229二二.初始复合形的构成初始复合形的构成1.复合形顶点数复合形顶点数K K的选择的选择建议建议:小取大值小取大值,大取小值大取小值2)为避免降维为避免降维,K K应取大些应取大些;但过大但过大,计算量也计算量也大大.*1)为保证迭代点能逼近极小点为保证迭代点能逼近极小点,应使应使12/20/2022102.初始复合形顶点的确定初始复合形顶点的确定 1)用试凑方法产生用试凑方法产生-适于低维情况适于低维情况;2)用随机方法产生用随机方法产生用

8、随机方法产生用随机方法产生K K个顶点个顶点 先用随机函数产生先用随机函数产生 个随机数个随机数 ,然后变换到预定的区间然后变换到预定的区间 中去中去.这便得到了一个顶点这便得到了一个顶点,要连续产生要连续产生K K个顶点个顶点.12/20/202211 将非可行点调入可行域内将非可行点调入可行域内)检查已获得的各顶点的可行性检查已获得的各顶点的可行性,若无一可行若无一可行,则重新产生随机点则重新产生随机点;若有若有q q个可行个可行,则转下步则转下步.)计算计算q q个可行点点集的几何中心个可行点点集的几何中心)将非可行点逐一调入可行域内将非可行点逐一调入可行域内.若若仍不仍不可行可行,则重

9、则重复此步骤复此步骤,直至进入直至进入可行域为止可行域为止.12/20/202212三三.终止判别条件终止判别条件各顶点与好点函数值之差的均方根应不大于误差限各顶点与好点函数值之差的均方根应不大于误差限 不是十分可靠不是十分可靠,可改变可改变 重作重作,看结果是否相同看结果是否相同.12/20/202213比比较较复复合合形形各各顶顶点点的的函函数数值值，找出好点找出好点XL，坏点坏点XHXH=XR=0.5找出次坏点找出次坏点XSH，XH=XSH满足终止条件满足终止条件？X*=XL,F*=F(XL)结结 束束四四.复合形法的复合形法的 迭代步骤迭代步骤是是否否给定给定K，ai,bi i=1,2

10、,n产生初始复合形顶点产生初始复合形顶点Xj,j=1,2,K计算复合形各顶点的函数值计算复合形各顶点的函数值F(Xj),j=1,2,K是是是是是是否否否否否否XRDDFR0,一般取为一般取为0.010.001);2)-方向偏离系数方向偏离系数(=0,对线性约束取为对线性约束取为0,其余取为其余取为1).-规格化条件规格化条件12/20/202219三三.步长因子的确定步长因子的确定1.最优步长因子最优步长因子(迭代点为内点时使用迭代点为内点时使用)下一迭下一迭代点代点如仍为内点如仍为内点,继续进行继续进行,直至迭代点到边界或域外时止直至迭代点到边界或域外时止.迭代公式迭代公式:2.试验步长因子

11、试验步长因子将将 在在 处作泰勒展开处作泰勒展开,仅取到仅取到线性项线性项:(1)定义目标函数相对下降量定义目标函数相对下降量:(2)迭代迭代公式公式(3)(4)将将(2)、(3)代入代入(1)后整理后整理得得:迭迭代代点在边界附近偏域内一侧时使点在边界附近偏域内一侧时使 用用,采用最有利的适用可行方向采用最有利的适用可行方向.2)按此法按此法,直至使迭代点进入约直至使迭代点进入约束容差带或至域外为止束容差带或至域外为止.*1)为保证为保证 是是 的一个邻近的一个邻近点点,的值不能取得太大的值不能取得太大.通常通常12/20/2022202.调整步长因子调整步长因子(将已出界的迭代点调将已出界

12、的迭代点调回到边界上回到边界上)(1)约束边界容差带约束边界容差带 在实际计算中在实际计算中,应给约束边界一个允应给约束边界一个允许的误差限许的误差限:式中式中,通常取通常取0.01-0.001;只要迭代点进入只要迭代点进入容差带容差带,即认为达到了边界即认为达到了边界.(2)调整步长因子调整步长因子因因 与与 很接近很接近,可认为可认为 在这两点间按线性变化在这两点间按线性变化:(1)为使新迭代点落在容差带中部为使新迭代点落在容差带中部,取取(2)于是有于是有(3)*还需检验该点是否在容差带内还需检验该点是否在容差带内.若不满足若不满足,则则)若若 ,则则)若若 ,则则 重复以上步骤重复以上

13、步骤,直至满足时止直至满足时止.12/20/202221满足满足K-TK-T条件条件？给定给定：内点内点X（0），f fK=0，M=0 沿负梯度方向一维搜索得极小点沿负梯度方向一维搜索得极小点X（K+1）求最有利的适用可行方向求最有利的适用可行方向求试验步长因子求试验步长因子tM=0K=K+1X*=X(K),F*=F(X*)结束结束是是是是是是否否否否否否求求求调整步长因子求调整步长因子否否四四.终止迭代准则终止迭代准则 采用采用K-TK-T条件条件,对对J J个起作用约束个起作用约束,求解求解线性方程组线性方程组:M=1应为非负应为非负五五.迭代步骤迭代步骤是是12/20/2022225-6

14、 5-6 5-6 5-6 惩罚函数法惩罚函数法惩罚函数法惩罚函数法一一.概述概述1.基本思想基本思想将将约束问题约束问题 转化成无约束问题转化成无约束问题 求解求解惩罚函数惩罚函数可调参数可调参数*构造惩罚函数构造惩罚函数 的基本要求的基本要求:惩罚项用约束条件构造惩罚项用约束条件构造;到达最优点时到达最优点时,惩罚项的值为惩罚项的值为0 0;当约束不满足或未到达最优点时当约束不满足或未到达最优点时,惩罚项惩罚项的值的值大于大于0 0.2.分类分类 内点法内点法-将迭代点限制在可行域内将迭代点限制在可行域内;外点法外点法-迭代点一般在可行域外迭代点一般在可行域外;混合法混合法-将外点法和内点法

15、结合起来解将外点法和内点法结合起来解GPGP型问型问题题.12/20/202223二二.SUMT.SUMT内点法内点法1.1.惩罚函数的构造惩罚函数的构造原原问题问题:s.t.可取可取式中式中,1)*当当X X趋于趋于D D的边界时的边界时,B(X)趋于无穷大趋于无穷大,故又称故又称为为障碍障碍(围墙围墙)函数函数;12/20/2022242)罚因子罚因子为为使使 与原问题同解与原问题同解,应使应使*对对于于一一个个 ,求求解解一一个个无无约约束束优优化化问问题题.前前一一问问题题的的结结果果为为后后一一问问题题的的初初值值,故故为为系系列列无无约约束束极极小小化化方方 法法(Sequenti

16、al(Sequential Unconstrained Unconstrained Minimization Minimization Technique).Technique).12/20/202225 输出输出X*，F*=F（X*）结结束束是是2.SUMT2.SUMT内点罚函数法迭代步骤内点罚函数法迭代步骤用无约束方法求用无约束方法求 的极小点的极小点X*输入输入X0，r0,c,否否k=k+1,Xk=X*，rk=crkK=0,Xk=X0,12/20/202226例例:解解:惩罚函数惩罚函数在在D D内内 ,对于固定对于固定的的 ,令令得得r(k)x*f(x*)B(x*)1/22111.51

17、/101.4472 0.7236 2.2361 0.94721/501.20.650.71/6250 1.0179 0.508955.90170.5179010.50.512/20/202227r(k)x*f(x*)B(x*)1/22111.51/101.4472 0.7236 2.2361 0.94721/501.20.650.71/6250 1.0179 0.508955.90170.5179010.50.512/20/2022281)初始点初始点X0的确定的确定(必须为内点必须为内点)*用现有机器参数作初值用现有机器参数作初值;*用图解法用图解法;*用随机方法用随机方法;*用内点法求内点

18、用内点法求内点.3.应用内点法应注意的问题应用内点法应注意的问题-X0,r(0),c 的确定的确定12/20/202229k=0,X(k)=X0,r(k)=r0I2为空集为空集计算指标集计算指标集以以X X(K)(K)为初始点为初始点,求解求解得得X X*。输出输出是是否否任取任取X0,给定给定 r0,c,12/20/2022302）罚因子的初值罚因子的初值*过大过大,会使会使 的最优点的最优点比比 X X0 0 离真正的最优点更远离真正的最优点更远;过过小小,在域内的惩罚作用小在域内的惩罚作用小,在接近边在接近边界时则突然加大使性态变坏界时则突然加大使性态变坏,且有且有可能使迭代点越出可行域

19、可能使迭代点越出可行域.Fox Fox 推荐推荐3）递减系数递减系数C C本书推荐本书推荐0.10.5.0.10.5.12/20/202231三三.SUMTSUMT外点法外点法1.惩罚函数的构造惩罚函数的构造考虑非线性规划问题考虑非线性规划问题:s.t.惩罚函数可取为惩罚函数可取为2)罚因子罚因子*1)时时,惩罚项为惩罚项为0 0,不惩罚不惩罚;时时,惩罚项大于惩罚项大于0 0,有惩罚作用有惩罚作用.因因 边边界界时时,惩惩罚罚项项中中大大括括号号中中的的值值趋趋于于0 0,为为保保证证惩惩罚罚作用作用,应取应取12/20/2022322.SUMTSUMT外点法的迭代步骤外点法的迭代步骤给定给

20、定X0，c,r0,1,2,3k=0,r(k)=r0,X(K)=X0输出输出X*，F*=F（X*）结束结束是是是是是是否否否否否否求解求解 得极小点得极小点X*k=k+1r(k)=cr(k)X(k)=X*-初始点初始点,对凸规划可任意给定对凸规划可任意给定;*-外点法点距精度外点法点距精度;-等式约束允许的误差限等式约束允许的误差限;-不等式约束允许的误差限不等式约束允许的误差限;-罚因子的放大系数罚因子的放大系数;*为使迭代点进入可行域为使迭代点进入可行域,可设可设约约束容差带束容差带:12/20/202233例例:解解:惩罚函数惩罚函数在在D D外外 ,对于固定的对于固定的 ,令令得得r(k

21、)x*f(x*)11.50.250.5101.909090.826540.909091001.990990.9802960.99009910001.9990010.9980030.99900121112/20/2022343.外点法与内点法的比较外点法与内点法的比较1)1)外点法可解各类问题外点法可解各类问题,内点法仅适于内点法仅适于IPIP型问题型问题;2)2)外点法的初始点可任选外点法的初始点可任选,内点法的初始点必须为内点内点法的初始点必须为内点;3)3)外点法的极小点系列一般在外点法的极小点系列一般在D D外外,内点法的极小点系列内点法的极小点系列 在在D D内内(全为可行点全为可行点

22、););12/20/202235四四.SUMTSUMT混合法混合法 有有等等式式约约束束时时内内点点法法不不能能用用,要要求求迭迭代代点点始始终终满满足足不不等等式式约约束束时时外外点点法法不不能能用用.此此时时可可将将外外点点法法和和内内点点法法结结合合起起来来解解GPGP型问题型问题.*1)1)迭代点应始终满足迭代点应始终满足 2)2)FiaccoFiacco等人建议等人建议12/20/2022365-7 5-7 5-7 5-7 拉格朗日乘子法拉格朗日乘子法拉格朗日乘子法拉格朗日乘子法一一.等式约束问题的拉格朗日乘子法等式约束问题的拉格朗日乘子法s.t.1.1.建立拉氏函数建立拉氏函数2.

23、2.在最优点处有如下在最优点处有如下n+q n+q 个方程成立个方程成立其解为其解为12/20/202237s.t.二二.含不等式约束问题的拉格朗日乘子法含不等式约束问题的拉格朗日乘子法1.1.建立拉氏函数建立拉氏函数 再用前述方法建立拉氏函数再用前述方法建立拉氏函数 对不等式约束引入松弛变量对不等式约束引入松弛变量 ,使之成为等式约束使之成为等式约束:12/20/2022382.2.在最优点处有如下在最优点处有如下 n+q+2p n+q+2p 个方程成立个方程成立其解为其解为12/20/202239三三.增广拉格朗日乘子法增广拉格朗日乘子法 采采用用拉拉格格朗朗日日乘乘子子法法时时求求解解有

24、有难难度度,而而罚罚函函数数法法当当迭迭代代点点接接近近边边界界时时函函数数常常有有病病态态,此此法法的的思思路路是是把把两两者者结结合起来合起来.其增广拉格朗日函数为其增广拉格朗日函数为:特点特点:1.初始点可为非可行点初始点可为非可行点;2.因因增增加加了了可可调调参参数数 ,其其收收敛敛速速度度和和稳稳定定性性都都优于罚函数法优于罚函数法.12/20/2022405-8 5-8 5-8 5-8 简约梯度法及广义简约梯度法简约梯度法及广义简约梯度法简约梯度法及广义简约梯度法简约梯度法及广义简约梯度法思思路路：利利用用约约束束条条件件消消去去非非独独立立变变量量，使使问问题题简简化化，再再沿

25、沿简简化化后后的的目目标函数的负梯度方向搜索标函数的负梯度方向搜索.一一 简约梯度法简约梯度法1.1.问题问题 s.t.2 2.简约梯度简约梯度1）将问题降维将问题降维基向量（状态）基向量（状态）式中式中将将X X分成两部分分成两部分：12/20/202241非基向量非基向量（决策决策)对应的系数矩阵也分成两部分对应的系数矩阵也分成两部分式中式中，B B为对应于为对应于X XB B的的m m 阶方阵阶方阵，且必须为满秩矩阵且必须为满秩矩阵；C C为为对应于对应于X XN N的的 阶矩阵阶矩阵；于是于是，（1 1）故故12/20/2022422 2）求简约梯度）求简约梯度（2 2）式中式中,3

26、3.迭代计算迭代计算1 1）迭代公式）迭代公式（3 3）12/20/202243*(1)在迭代中需保证各分量值大于或等于零在迭代中需保证各分量值大于或等于零;(2)当当 且且 时时,因因 ,必有必有 ,不可行不可行.写成分量的形式：写成分量的形式：（4 4）迭代方向应作修正迭代方向应作修正：(当当 ,时时)(在在一般情况下一般情况下)（5 5）12/20/2022442 2）步长因子的确定）步长因子的确定(1)若各分量值若各分量值 大于零大于零,则只要则只要 均能保证变均能保证变量量 非负非负,此时可取最优步长此时可取最优步长 (2)若若 ,由于必须使由于必须使（6 6）故故,于是有于是有12

27、/20/2022453）确定确定 的方法的方法由由(1)(1)有有*通过通过(3)(3)和和(7)(7)可完成一次完整的迭代可完成一次完整的迭代.（7 7）由由(3)(3)12/20/202246(允许部分变量的上允许部分变量的上下界为下界为 )二二 广义简约梯度法简介广义简约梯度法简介1 1.问题问题s.t.s.t.(可可引入松弛变量将不引入松弛变量将不等式约束变为等式约束等式约束变为等式约束)2 2.解法特点解法特点1)1)和和 之间的关系难以用简单的式子表达之间的关系难以用简单的式子表达,一般采用牛一般采用牛顿迭代法解非线性方程组获得顿迭代法解非线性方程组获得;2)2)求简约梯度用到的求简约梯度用到的 可用复合函数求导的方法求得可用复合函数求导的方法求得.12/20/202247