机械优化设计5约束优化方法

2019/8/41第五章约束优化方法一.约束坐标轮换法二.约束随机方向法三.复合形法四.可行方向法五.罚函数法六.拉格朗日乘子法七.简约梯度法及广义简约梯度法2019/8/42§5-1优化方法的类型2）间接法1）直接法---将迭代点限制在可行域内(可行性),步步降低目标函数值(下降性),直至到达最优点.常用方法有:约束坐标轮换法,约束随机方向法,复合形法,可行方向法,线性逼近法等.---通过变换,将约束优化问题转化为无约束优化问题求解.常用方法有:罚函数法,拉格朗日乘子法等.（可解IP型问题）（可解各类问题）(按对约束条件的处理方法分)2019/8/43§5-2约束坐标轮换法一.基本思路•①可取定步长、加速步长和收缩步长,但不能取最优步长;1.依次沿各坐标轴方向---e1,e2,…,en方向搜索;2.将迭代点限制在可行域内.②对每一迭代点均需进行可行性和下降性检查.2019/8/44二.迭代步骤)3(X)1(X)0(X)4(X)2(X2019/8/45三.存在问题有时会出现死点,导致输出“伪最优点”.*为辨别真伪,要用K-T条件进行检查.2019/8/46§5-3约束随机方向法一.基本思路②若该方向适用、可行，则以定步长前进；坐标轮换法有时会输出“伪最优点”,用随机方向法可克服这一缺点.①若该方向不适用、可行，则产生另一方向；③若在某处产生的方向足够多，仍无一适用、可行，则采用收缩步长；④若步长小于预先给定的误差限则终止迭代。搜索方向----采用随机产生的方向2019/8/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2019/8/48X0=X,F0=Fα=α0,F0=F(X0)F=F（X）j=1K=K+1三.随机方向法的迭代步骤是K=0,j=0SXX0产生随机方向α=0.5α否FF0j=0Kmα≤ε结束X*=X0,F*=F0是否是否是否X∈D是否,,,00mX给定内点)(0步长终止误差限的方向数在一迭代点处允许产生初始步长；m；)0,1()(否则为沿该方向前进过为计数器方向数计数器jK2019/8/49§5-4复合形法一.基本思路在可行域内选取若干初始点并以之为顶点构成一个多面体(复合形),然后比较各顶点的函数值,去掉最坏点,代之以好的新点,并构成新的复合形,以逼近最优点.4XCX3X1X2X•有两种基本运算:1)映射---在坏点的对侧试探新点:先计算除最坏点外各顶点的几何中心,然后再作映射计算.2)收缩---保证映射点的“可行”与“下降”)()(5.01432XXXXXXXCCCX1为最坏点---映射系数常取3.1若发现映射点不适用、可行,则将减半后重新映射.2019/8/410二.初始复合形的构成1.复合形顶点数K的选择建议:nKn21小取大值,大取小值nn2)为避免降维,K应取大些;但过大,计算量也大.*1)为保证迭代点能逼近极小点,应使1nK2019/8/4112.初始复合形顶点的确定1)用试凑方法产生---适于低维情况;2)用随机方法产生①用随机方法产生K个顶点先用随机函数产生个随机数,然后变换到预定的区间中去.n)10(iiiiibxaniiiiiiaabx,...,2,1,)(这便得到了一个顶点,要连续产生K个顶点.2019/8/412②将非可行点调入可行域内ⅰ)检查已获得的各顶点的可行性,若无一可行,则重新产生随机点;若有q个可行,则转下步.ⅱ)计算q个可行点点集的几何中心ⅲ)将非可行点逐一调入可行域内.qjjsXqX1)()(1)(5.0)()1()()1(sqsqXXXX若仍不可行,则重复此步骤,直至进入可行域为止.)(sX)1(qX2019/8/413三.终止判别条件各顶点与好点函数值之差的均方根应不大于误差限2112)(})]()([1{kjLjXFXFk不是十分可靠,可改变重作,看结果是否相同.2019/8/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∈DFRF(XH)2019/8/415§5-5可行方向法*其特点是注意到约束最优点通常在约束边界上：为此，可先找出一个边界点，然后沿边界搜索;---是求解大型约束优化问题的主要方法.一.寻找边界点的方法1.在D内取一初始点,然后沿负梯度方向搜索,直至使迭代点超越D或落在边界上;2.若迭代点在D外,则将它调回到边界上.)2(X)1(X)0(X)2(X2019/8/416二.产生适用可行方向的办法(一)适用可行方向的数学条件1.适用(下降)性条件在迭代点处,目标函数沿该方向的方向导数应小于0:0)]([)()()(kkTkSSXF0)]([)()(kTkSXF)(kS与负梯度方向的夹角应小于900.2019/8/4172.可行性条件在边界迭代点处,实时约束函数沿该方向的方向导数应不小于0:0)]([)()()(kkTkjSSXg0)]([)()(kTkjSXg)(kS与实时约束函数梯度方向的夹角应不大于900.(1)可行方向迭代公式:)()()()1(kkkkSXX只要取适当的,能使仍在D内,则称可行方向.0)(k)1(kX)(kS(2)可行性条件2019/8/418*若迭代点处于J个约束边界的相交处,应同时成立:)(kX0)]([)()(kTkjSXgJj,...,2,1综上所述,适用可行方向的数学条件为:0)]([)()(kTkSXF0)]([)()(kTkjSXgJj,...,2,1几何解释:)(kX)()(kXg)()(kXF2019/8/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--规格化条件2019/8/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f2019/8/4212.调整步长因子(将已出界的迭代点调回到边界上)(1)约束边界容差带在实际计算中,应给约束边界一个允许的误差限:)(0Xgupu,...,2,1式中,通常取0.01-0.001;只要迭代点进入容差带,即认为达到了边界.(2)调整步长因子c因与很接近,可认为在这两点间按线性变化:)1(kX)(kX)(XgjtkjkjkjjXgXgXgXg)()()()()()1()((1)为使新迭代点落在容差带中部,取2)()()()()()()1()()2(ctkjkjkjkjjXgXgXgXgXg(2)于是有tkjkjkjcXgXgXg)()()(2)()1()()()()2(kckkSXX(3)*还需检验该点是否在容差带内.若不满足,则ⅰ)若,则ⅱ)若,则0g0g;)2()1(kkXXct;)2()(kkXXctt重复以上步骤,直至满足时止.0ct)(Xgj)()(kjXg)()1(kjXg2019/8/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?)()(2019/8/423§5-6惩罚函数法一.概述1.基本思想将约束问题转化成无约束问题求解)(minXFnRDX),(min)(krXnRX惩罚函数可调参数*构造惩罚函数的基本要求:)(惩罚项F①惩罚项用约束条件构造;②到达最优点时,惩罚项的值为0;③当约束不满足或未到达最优点时,惩罚项的值大于0.2.分类①内点法----将迭代点限制在可行域内;②外点法----迭代点一般在可行域外;③混合法----将外点法和内点法结合起来解GP型问题.2019/8/424二.SUMT内点法1.惩罚函数的构造原问题:puuRDXXgXFn,...,2,1,0)(),(mins.t.可取)()(),()()(XBrXFrXkk式中,1)puupuuXgXgXB11)](ln[)(1)(或*当X趋于D的边界时,B(X)趋于无穷大,故又称为障碍(围墙)函数;2019/8/4252)罚因子)(kr为使与原问题同解,应使.......)()2()1()0(krrrr.0,)(krk时当*对于一个,求解一个无约束优化问题.前一问题的结果为后一问题的初值,故为系列无约束极小化方法(SequentialUnconstrainedMinimizationTechnique).)(krpuuXg1)(1)()()(),(kkrXFrX2019/8/426输出X*，F*=F（X*）结束是2.SUMT内点罚函数法迭代步骤kXX用无约束方法求的极小点X*),(krX输入X0，r0,c,ε否k=k+1,Xk=X*，rk=crkK=0,Xk=X0,0krr),()(krX构造2019/8/427例:01)(..5.0)(minxxgtsxxf解:惩罚函数15.0),()()(xrxrxkk在D内,对于固定的,)(kr)1(x0)1(5.02)(xr