【文档说明】机械优化设计之约束优化方法讲义课件.pptx，共(48)页，785.735 KB，由精品优选上传

转载请保留链接：https://www.ichengzhen.cn/view-260571.html

以下为本文档部分文字说明：

2023/7/41第五章约束优化方法一.约束坐标轮换法二.约束随机方向法三.复合形法四.可行方向法五.罚函数法六.拉格朗日乘子法七.简约梯度法及广义简约梯度法2023/7/42§5-1优化方法的类型2）间接法1）直接法---将迭代点限制在

可行域内(可行性),步步降低目标函数值(下降性),直至到达最优点.常用方法有:约束坐标轮换法,约束随机方向法,复合形法,可行方向法,线性逼近法等.---通过变换,将约束优化问题转化为无约束优化问题求解.常用方法有:罚函数法,拉格朗日乘子法等.（可解IP型问题）（可解各类问题）(按

对约束条件的处理方法分)2023/7/43§5-2约束坐标轮换法一.基本思路•①可取定步长、加速步长和收缩步长,但不能取最优步长;1.依次沿各坐标轴方向---e1,e2,…,en方向搜索;2.将迭代点限制在可行域内.②对每一迭代点均需进行可行性和下降性检查.2023/7/

44二.迭代步骤2023/7/45三.存在问题有时会出现死点,导致输出“伪最优点”.*为辨别真伪,要用K-T条件进行检查.2023/7/46§5-3约束随机方向法一.基本思路②若该方向适用、可行，则以定步长前进；坐标轮换法有时会

输出“伪最优点”,用随机方向法可克服这一缺点.①若该方向不适用、可行，则产生另一方向；③若在某处产生的方向足够多，仍无一适用、可行，则采用收缩步长；④若步长小于预先给定的误差限则终止迭代。搜索方向----采用随机

产生的方向2023/7/47二.随机方向的构成1.用RND(X)产生n个随机数)10(,...,2,1,=iini2.将(0,1)中的随机数变换到(-1,1)中去;i12−=iiyni,...,2,1=3.构成随机方向

==nniiyyyyS...12112变换得:6.0,2.0,6.0321==−=yyy于是−=−++−=6882.02294.06882.06.02.06.06.02.0)6.0(1222S例:对于三维问题:8.0,6.0,2.0321===

2023/7/48X0=X,F0=Fα=α0,F0=F(X0)F=F（X）j=1K=K+1三.随机方向法的迭代步骤是K=0,j=0SXX+=0产生随机方向α=0.5α否F<F0j=0K<mα≤ε结束X*=X0,F*=F0是否是否是否X∈D是否,,,00m

X给定内点)(0步长终止误差限的方向数在一迭代点处允许产生初始步长−−−−−−；m；)0,1()(否则为沿该方向前进过为计数器方向数计数器−−−−jK2023/7/49§5-4复合形法一.基本思路在可行域内选取若干初始点并以之为

顶点构成一个多面体(复合形),然后比较各顶点的函数值,去掉最坏点,代之以好的新点,并构成新的复合形,以逼近最优点.4X3X1X2X•有两种基本运算:1)映射---在坏点的对侧试探新点:先计算除最坏点外各顶点的几何中心,然后再作映射计算.2)收缩---保证映射点的“可行”与“

下降”)()(5.01432XXXXXXXCCC−+=+=X1为最坏点---映射系数常取3.1=若发现映射点不适用、可行,则将减半后重新映射.2023/7/410二.初始复合形的构成1.复合形顶点数K的选择建议:nKn21+小取大值,大取小值nn2)为避免降维,K应取大些;但过大

,计算量也大.*1)为保证迭代点能逼近极小点,应使1+nK2023/7/4112.初始复合形顶点的确定1)用试凑方法产生---适于低维情况;2)用随机方法产生①用随机方法产生K个顶点先用随机函数产生个随机

数,然后变换到预定的区间中去.n)10(iiiiibxaniiiiiiaabx,...,2,1,)(=+−=这便得到了一个顶点,要连续产生K个顶点.2023/7/412②将非可行点调入可行域内ⅰ)检查已获

得的各顶点的可行性,若无一可行,则重新产生随机点;若有q个可行,则转下步.ⅱ)计算q个可行点点集的几何中心ⅲ)将非可行点逐一调入可行域内.==qjjsXqX1)()(1)(5.0)()1()()1(sqsqXXXX−+=++若仍不可

行,则重复此步骤,直至进入可行域为止.)(sX)1(+qX2023/7/413三.终止判别条件各顶点与好点函数值之差的均方根应不大于误差限−=2112)(})]()([1{kjLjXFXFk不是十分可靠,可改变重作,看结果是否相同.2023/7/414比较复

合形各顶点的函数值，找出好点XL，坏点XHXH=XRα=0.5α找出次坏点XSH，XH=XSH满足终止条件？X*=XL,F*=F(XL)结束四.复合形法的迭代步骤是否=−=KjjCHjXKX1,11)(),(RRHCCRXFFXXXX=−+=给定K，δ，α，ε，ai,bii=1,2,…

n产生初始复合形顶点Xj,j=1,2,…,K计算复合形各顶点的函数值F(Xj),j=1,2,…,K是是是否否否XR∈DFR<F(XH)2023/7/415§5-5可行方向法*其特点是注意到约束最优点通常在约束边界上：为此，可先找出一个边界点，然后沿边界搜索;-

--是求解大型约束优化问题的主要方法.一.寻找边界点的方法1.在D内取一初始点,然后沿负梯度方向搜索,直至使迭代点超越D或落在边界上;2.若迭代点在D外,则将它调回到边界上.)2(X)1(X)0(X)2(X2023/7/416二.产生适用可行方向的办法(一)适用可行方向

的数学条件1.适用(下降)性条件在迭代点处,目标函数沿该方向的方向导数应小于0:0)]([)()()(kkTkSSXF0)]([)()(−kTkSXF)(kS与负梯度方向的夹角应小于900.2023/7/4172.可行

性条件在边界迭代点处,实时约束函数沿该方向的方向导数应不小于0:0)]([)()()(kkTkjSSXg0)]([)()(kTkjSXg)(kS与实时约束函数梯度方向的夹角应不大于900.(1)可行方向迭代公式:)()()()1(

kkkkSXX+=+只要取适当的,能使仍在D内,则称可行方向.0)(k)1(+kX)(kS(2)可行性条件2023/7/418*若迭代点处于J个约束边界的相交处,应同时成立:)(kX0)]([)()(kTkjSXgJj,...,2,1=综

上所述,适用可行方向的数学条件为:0)]([)()(−kTkSXF0)]([)()(kTkjSXgJj,...,2,1=几何解释:)(kX)()(kXg)()(kXF−2023/7/419(二)最有利的适用可行方向在满足上述

适用可行方向的数学条件的同时，使目标函数的方向导数为负且达到最小（处理为线性规划问题）：)()()(21)()]([)(min...kTkkTnkSXFSsssS==nkRDS)(0)]([)()(−−kTkSXF0)]([)()(−jkTkjSXgJj,...

,2,1=11−isni,...,2,1=D:使求*1)---条件余度(>0,一般取为0.01—0.001);2)---方向偏离系数(>=0,对线性约束取为0,其余取为1).j--规格化条件2023/7/420三.步长因子的确定1.最优步长因子(迭代点为内点时使用)下一迭代点如

仍为内点,继续进行,直至迭代点到边界或域外时止.迭代公式:)()()()1(kkkXFXX−=+2.试验步长因子t)(kX)1(+kX将在处作泰勒展开,仅取到线性项:)(XF)(kX)()()()()()1()()()1(kkTkkkXXXFXFXF−

+++(1)定义目标函数相对下降量:)()()()()1()(kkkfXFXFXF+−=(2)迭代公式)()()1(ktkkSXX+=+(3)(4)将(2)、(3)代入(1)后整理得:)()()()()(kTkkftSXFXF−=迭代点在边界附近偏域内一侧时使用,采用最有利

的适用可行方向.)(kS2)按此法,直至使迭代点进入约束容差带或至域外为止.*1)为保证是的一个邻近点,的值不能取得太大.通常)1(+kX)(kXf1.005.0→=f2023/7/4212.调整步长因子(将已出界的迭代点调回到边界上)(1)约束边界容差带在实际计算中,应给约

束边界一个允许的误差限:)(0Xgupu,...,2,1=式中,通常取0.01-0.001;只要迭代点进入容差带,即认为达到了边界.(2)调整步长因子c因与很接近,可认为在这两点间按线性变化:)1(+kX)(kX)(Xgjtkj

kjkjjXgXgXgXg)()()()()()1()(−+=+(1)为使新迭代点落在容差带中部,取2)()()()()()()1()()2(=−+==++ctkjkjkjkjjXgXgXgXgX

g(2)于是有tkjkjkjcXgXgXg)()()(2)()1()(−−=+)()()2(kckkSXX+=+(3)*还需检验该点是否在容差带内.若不满足,则ⅰ)若,则ⅱ)若,则0g0g;)2()1(++

kkXXct;)2()(+kkXXctt−重复以上步骤,直至满足时止.0ct)(Xgj)()(kjXg)()1(+kjXg2023/7/422满足K-T条件？给定：内点X（0），β，θ，δ，ΔfK=0，M=0沿负梯度方

向一维搜索得极小点X（K+1）求最有利的适用可行方向求试验步长因子αtM=0K=K+1X*=X(K),F*=F(X*)结束是是是否否否求puKujXgg,...,2,1)()(min==jg0求调整步长因子否)()(

)(KCKKSXX+=)()()(KtKKSXX+=四.终止迭代准则采用K-T条件,对J个起作用约束,求解线性方程组:0)()(=−=XgXFuJiuuM=1应为非负五.迭代步骤是puXgku,...,2,1?)()(=2023/7/423§5-6惩罚函数法一.概述1

.基本思想将约束问题转化成无约束问题求解)(minXFnRDX),(min)(krXnRX惩罚函数可调参数*构造惩罚函数的基本要求:)(惩罚项+=F①惩罚项用约束条件构造;②到达最优点时,惩罚项的值为0;③当约束不满足或未到达最优

点时,惩罚项的值大于0.2.分类①内点法----将迭代点限制在可行域内;②外点法----迭代点一般在可行域外;③混合法----将外点法和内点法结合起来解GP型问题.2023/7/424二.SUMT内点法1.惩罚函数的构造原问题:puuRD

XXgXFn,...,2,1,0)(),(min=s.t.可取)()(),()()(XBrXFrXkk+=式中,1)==−=puupuuXgXgXB11)](ln[)(1)(或*当X趋于D的边界时,B(X)趋

于无穷大,故又称为障碍(围墙)函数;2023/7/4252)罚因子)(kr为使与原问题同解,应使.......)()2()1()0(krrrr.0,)(→→krk时当*对于一个,求解一个无约束优化问题.前一问题的结果为后一问题的初值,故为系列无约束极小化方法(Sequ

entialUnconstrainedMinimizationTechnique).)(kr=puuXg1)(1)()()(),(kkrXFrX+=2023/7/426输出X*，F*=F（X*）结束是2.SUMT内点罚函数法迭代步骤−kXX用无约束方法求的极小点X*),(krX输入X

0，r0,c,ε否k=k+1,Xk=X*，rk=crkK=0,Xk=X0,0krr=),()(krX构造2023/7/427例:01)(..5.0)(min−==xxgtsxxf解:惩罚函数15.0),()()(−+=xrxrxkk在D内,对于固定的,)(kr)1(

x0)1(5.02)(=−−=xrdxdk令)(21krx+=得r(k)x*f(x*)B(x*)1/22111.51/101.44720.72362.23610.94721/501.20.650.7…1/62501.01790.508955.90170.5179…010.50.5),(

)(krx2023/7/42815.0),()()(−+=xrxrxkk)(21krx+=r(k)x*f(x*)B(x*)1/22111.51/101.44720.72362.23610.9472

1/501.20.650.7…1/62501.01790.508955.90170.5179…010.50.5),()(krxxxf5.0=5.17.00322.115.0)(=kr02.0)(=kr2023/7/4291)初始点X0的

确定(必须为内点)*用现有机器参数作初值;*用图解法;*用随机方法;*用内点法求内点.3.应用内点法应注意的问题---X0,r(0),c的确定2023/7/430k=0,X(k)=X0,r(k)=r0I2为空集计算指标集pikipikiXgiIXgiI,...,2,1)(2,..

.,2,1)(1,0)(,0)(====以X(K)为初始点,求解得X*。0)(..])(min[2−−XgtsXgiIii1Ii*)()()(1XXcrrkkkkk==+=输出)(0kXX=是否任取X0,给定r0,c,2023/7/43

12）罚因子的初值)()(),()()(XBrXFrXkk+=),()(krX)0(r*过大,会使的最优点比X0离真正的最优点更远;过小,在域内的惩罚作用小,在接近边界时则突然加大使性态变坏,且有可能使迭代点越出可行域.)0(rFFox推荐)()()0()0()0(XBr

XF=3）递减系数C本书推荐0.1—0.5.2023/7/432三.SUMT外点法1.惩罚函数的构造考虑非线性规划问题:qvvpuuRDXXhXgXFn,...,2,1,...,2,1,0)(,0)(),(min===s.t.惩罚函数可取为++===pu

qvvukkXhXgrXFrX1122)()()]([))](,0[min()(),(2)罚因子)(kr.......)()2()1()0(krrrr.,)(→→krk时当*1)时,惩罚项为0,不惩罚;时,惩罚项大于0,有

惩罚作用.DXDX因边界时,惩罚项中大括号中的值趋于0,为保证惩罚作用,应取DXk→)(2023/7/4332.SUMT外点法的迭代步骤给定X0，c,r0,ε1,ε2,ε3k=0,r(k)=r0,X(K)=

X0输出X*，F*=F（X*）结束是是是否否否puXgu,...,2,1?*)(1=−qvXhv,...2,1*)(2=3)(*−KXX求解得极小点X*),(min)(KrXk=k+1r(k)=cr(k)X(k)=X*---初始点,对凸规划可任意给定;0X*---外点法点距

精度;3---等式约束允许的误差限;2---不等式约束允许的误差限;1---罚因子的放大系数;C21001010−−→通常取r**为使迭代点进入可行域,可设约束容差带:0)(:)(:,)()(111−−−XgXgXgXguuuu即则有改为将),()(kr

X构造2023/7/434x2)1(−=xf5.00320.11例:02)(..)1()(min2−=−=xxgtsxxf解:惩罚函数在D外,对于固定的,)(kr)2(x0)2(2)1(2)(=−+−=xrxdxdk令)()(121kkrrx++=得r(k)x*f(x*)11.50.

250.5101.909090.826540.909091001.990990.9802960.99009910001.9990010.9980030.999001…211),()(krx−+−−=−+−=2)(222)(2)()2()1()1()]2,0[min()1(),

(xrxxxrxrxkkk)2()2(xx2023/7/4353.外点法与内点法的比较1)外点法可解各类问题,内点法仅适于IP型问题;2)外点法的初始点可任选,内点法的初始点必须为内点;3)外点法

的极小点系列一般在D外,内点法的极小点系列在D内(全为可行点);2023/7/436四.SUMT混合法有等式约束时内点法不能用,要求迭代点始终满足不等式约束时外点法不能用.此时可将外点法和内点法结合起来解GP型问题.=+=puukkXg

rXFrX1)()()(1)(),(=+qvvkXhM12)()]([*1)迭代点应始终满足puugkXgXDX,...,2,1)(,0)(==2)Fiacco等人建议)()(1kkrM=2023/7/437§5-7拉

格朗日乘子法一.等式约束问题的拉格朗日乘子法qvvRDXXhXFn,...,2,1,0)(),(min==s.t.=+=qXhXFXL1)()(),(1.建立拉氏函数2.在最优点处有如下n+q个方程成立===

=qvvniiLxL,...,2,1,...,2,1,0,0其解为),(X2023/7/438qvvpuuRDXXhXgXFn,...,2,1,...,2,1,0)(,0)(),(min===s.t.二.含不等式约束问题的拉格朗

日乘子法1.建立拉氏函数再用前述方法建立拉氏函数对不等式约束引入松弛变量,使之成为等式约束:uz0)(2=−uuzXgpu,...,2,1=])([)()(),,,(211uupuuqzXgXhXFZXL−++===2023/7/4392.在

最优点处有如下n+q+2p个方程成立=−==−========puuuupuuuuqvvvniizzLzXgLXhLxL,...,2,1,...,2,12,...,2,1,...,2,1)02(,0)0)((,0)0)((,0,0其解为),,

,(ZX])([)()(),,,(211uupuuqzXgXhXFZXL−++===2023/7/440三.增广拉格朗日乘子法采用拉格朗日乘子法时求解有难度,而罚函数法当迭代点接近边界时函数常有病态,此法的思路是把两者结合起来

.其增广拉格朗日函数为:22121)()(])([])([),,,,(),,,,(uupuqkkzXgXhrZXLZrXA−++===特点:1.初始点可为非可行点;,2.因增加了可调参数,其收敛速度和稳定性都优于罚函数法.2023/7/441§5-8简约

梯度法及广义简约梯度法思路：利用约束条件消去非独立变量，使问题简化，再沿简化后的目标函数的负梯度方向搜索.一简约梯度法1.问题0)(min=XbAXXFs.t.nRDX)1(−nmRbm2.简约梯度1）将问题降维

基向量（状态）021=TBmBBBxxxX式中TNBXXX,=将X分成两部分：2023/7/4420)(21=−TmnNNNNxxxX非基向量（决策)对应的系数矩阵也分成两部分CBA,=式中，B为对应于XB的m阶方阵，且必须为满秩矩阵；C为对应于XN的阶矩阵；)

(mnm−于是，NBNBCXBbBXbCXBX11−−−==+（1）故)()),((),()(NNNBNBXXXXFXXFXF====87654321321xxx=+8763542

1321xxx2023/7/4432）求简约梯度)()(][)()()]([)()(1NBTNBTNBNNXFXFCBXFXFXXXXG+−=+==−（2）式中,TmnNNBmBTNBxFxFxFxFXFXFXF]......[)](),([)()(

11−==3.迭代计算1）迭代公式)()()1(kNkNkNSXX+=+)()()(kNkNXGX−=（3）)()),((),()(NNNBNBXXXXFXXFXF===NBCX

BbBX11−−−=2023/7/444*(1)在迭代中需保证各分量值大于或等于零;(2)当且时,因,必有,不可行.0)(=kNlx0)()(kNlXg00)1(+kNlx写成分量的形式：=+)1(kNix)

()()(kNikNiXgx−)(,...,2,1,0mni−=（4）迭代方向应作修正：−=)(0)()(kNikNiXgs0)(=kNlx0)()(kNlXg(当,时)(在一般情况下)（5

）2023/7/4452）步长因子的确定=+)1(kix)()(kikisx+ni,...,2,1=•(1)若各分量值大于零,则只要均能保证变量非负,此时可取最优步长0)(kis.(2)若,由于必须使0)(kis=+)1(kix0

)()(+kikisx（6）故)()(kikisx−,于是有]min[0)()(max)(时当−=kiskikisx.0,max之间进行只能在故作一维搜索时→=2023/7/4463）确定的方法)1(+kBX)(11)(kNkBCXBbBX−−−=由(1)有*通过

(3)和(7)可完成一次完整的迭代.)1(11)1(+−−+−=kNkBCXBbBX)()()(11kNkNSXCBbB+−=−−)()()(1)(kBkBkNkBSXSCBX+=−=−（7）由(3)

)()(1)(kNkBSCBS−−=)()()1(kNkNkNSXX+=+)()()(kNkNXGX−=2023/7/447(允许部分变量的上下界为)→−二广义简约梯度法简介1.问题iiivuxlXhX

F=0)()(mins.t.nRDXmv,...,2,1=ni,...,2,1=(可引入松弛变量将不等式约束变为等式约束)2.解法特点1)和之间的关系难以用简单的式子表达,一般采用牛顿迭代法解非线性方程组获得;BXNX2)求简约梯度用到的可用复合函数求导的方法求得.)(N

BXX