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

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

常用方法有:约束坐标轮换法,约束随机方向法,复合形法,可行方向法,线性逼近法等.---通过变换,将约束优化问题转化为无约束优化问题求解.

常用方法有:罚函数法,拉格朗日乘子法等.（可解IP型问题）（可解各类问题）(按对约束条件的处理方法分)2024/3/204§5-2约束坐标轮换法一.基本思路①可取定步长、加速步长和收缩步长,但不能取最优步长;1.依次沿各坐标轴方向---e1,e2,…,en方向搜索;2.将迭代点限制在可行域内.②对每一迭代点均需进行可行性和下降性检查.2024/3/205二.迭代步骤2024/3/206三.存在问题有时会出现死点,导致输出“伪最优点”.*为辨别真伪,要用K-T条件进行检查.2024/3/207§5-3约束随机方向法基本思路②若该方向适用、可行，则以定步长前进；坐标轮换法有时会输出“伪最优点”

,用随机方向法可克服这一缺点.①

若该方向不适用、可行，则产生另一方向；③若在某处产生的方向足够多，仍无一适用、可行，则采用收缩步长；④若步长小于预先给定的误差限则终止迭代。搜索方向----采用随机产生的方向2024/3/208二.随机方向的构成1.用RND(X)产生n个随机数2.将(0,1)中的随机数变换到(-1,1)中去;3.构成随机方向变换得:于是例:对于三维问题:2024/3/209X0=X,F0=Fα=α0,F0=F(X0)F=F（X）j=1K=K+1三.随机方向法的迭代步骤是K=0,j=0产生随机方向α=0.5α否F<F0j=0K<mα≤ε结束X*=X0,F*=F0是否是否是否X∈D是否2024/3/2010§5-4复合形法基本思路

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

若发现映射点不适用、可行,则将减半后重新映射.2024/3/2011二.初始复合形的构成1.复合形顶点数K的选择建议:

小取大值,大取小值2)为避免降维,K应取大些;但过大,计算量也大.*1)为保证迭代点能逼近极小点,应使2024/3/20122.初始复合形顶点的确定1)用试凑方法产生---适于低维情况;2)用随机方法产生①用随机方法产生K个顶点

先用随机函数产生

个随机数

,然后变换到预定的区间

中去.这便得到了一个顶点,要连续产生K个顶点.2024/3/2013②将非可行点调入可行域内ⅰ)检查已获得的各顶点的可行性,若无一可行,则重新产生随机点;若有q个可行,则转下步.ⅱ)计算q个可行点点集的几何中心ⅲ)将非可行点逐一调入可行域内.

若仍不可行,则重复此步骤,直至进入可行域为止.2024/3/2014三.终止判别条件各顶点与好点函数值之差的均方根应不大于误差限

不是十分可靠,可改变重作,看结果是否相同.2024/3/2015比较复合形各顶点的函数值，找出好点XL，坏点XHXH=XRα=0.5α找出次坏点XSH

，XH=XSH满足终止条件？X*=XL,F*=F(XL)结束四.复合形法的迭代步骤是否给定K，δ，α，ε，ai,bi

i=1,2,…n产生初始复合形顶点Xj,j=1,2,…,K计算复合形各顶点的函数值F(Xj),j=1,2,…,K是是是否否否XR∈DFR<F(XH)2024/3/2016§5-5可行方向法*其特点是注意到约束最优点通常在约束边界上：为此，可先找出一个边界点，然后沿边界搜索;---是求解大型约束优化问题的主要方法.一.寻找边界点的方法1.在D内取一初始点,然后沿负梯度方向搜索,直至使迭代点超越D或落在边界上;2.若迭代点在D外,则将它调回到边界上.2024/3/2017二.产生适用可行方向的办法(一)适用可行方向的数学条件1.适用(下降)性条件在迭代点处,目标函数沿该方向的方向导数应小于0:与负梯度方向的夹角应小于900.2024/3/20182.可行性条件

在边界迭代点处,实时约束函数沿该方向的方向导数应不小于0:与实时约束函数梯度方向的夹角应不大于900.(1)可行方向迭代公式:只要取适当的

,能使

仍在D内,则

称可行方向.(2)可行性条件2024/3/2019*若迭代点处于J个约束边界的相交处,应同时成立:综上所述,适用可行方向的数学条件为:几何解释:2024/3/2020(二)最有利的适用可行方向

在满足上述适用可行方向的数学条件的同时，使目标函数的方向导数为负且达到最小（处理为线性规划问题）：D:使求*1)---条件余度(>0,一般取为0.01—0.001);2)---方向偏离系数(>=0,对线性约束取为0,其余取为1).--规格化条件2024/3/2021三.步长因子的确定1.最优步长因子(迭代点为内点时使用)

下一迭代点如仍为内点,继续进行,直至迭代点到边界或域外时止.迭代公式:2.试验步长因子将在处作泰勒展开,仅取到线性项:(1)

定义目标函数相对下降量:(2)迭代公式(3)(4)将(2)、(3)代入(1)后整理得:

迭代点在边界附近偏域内一侧时使用,采用最有利的适用可行方向.2)按此法,直至使迭代点进入约束容差带或至域外为止.*1)为保证是的一个邻近点,的值不能取得太大.通常2024/3/20222.调整步长因子(将已出界的迭代点调回到边界上)(1)约束边界容差带

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

,则ⅱ)若

,则

重复以上步骤,直至满足时止.2024/3/2023满足K-T条件？

给定：内点X（0），β，θ，δ，ΔfK=0，M=0

沿负梯度方向一维搜索得极小点X（K+1）求最有利的适用可行方向求试验步长因子αtM=0K=K+1X*=X(K),F*=F(X*)结束是是是否否否求求调整步长因子否四.终止迭代准则

采用K-T条件,对J个起作用约束,求解线性方程组:M=1应为非负五.迭代步骤是2024/3/2024§5-6惩罚函数法一.概述1.基本思想将约束问题

转化成无约束问题

求解惩罚函数可调参数*构造惩罚函数的基本要求:①惩罚项用约束条件构造;②到达最优点时,惩罚项的值为0;③当约束不满足或未到达最优点时,惩罚项的值大于0.2.分类①内点法----将迭代点限制在可行域内;②外点法----迭代点一般在可行域外;③混合法----将外点法和内点法结合起来解GP型问题.2024/3/2025二.SUMT内点法1.惩罚函数的构造原问题:s.t.可取式中,1)*当X趋于D的边界时,B(X)趋于无穷大,故又称为障碍(围墙)函数;2024/3/20262)罚因子为使

与原问题同解,应使*对于一个,求解一个无约束优化问题.前一问题的结果为后一问题的初值,故为系列无约束极小化方法(SequentialUnconstrainedMinimizationTechnique).2024/3/2027

输出X*，F*=F（X*）结束是2.SUMT内点罚函数法迭代步骤用无约束方法求的极小点X*输入X0，r0,c,ε否k=k+1,Xk=X*，rk=crkK=0,Xk=X0,2024/3/2028例:解:惩罚函数在D内

,对于固定的

,令得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.52024/3/2029r(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.52024/3/20301)初始点X0的确定(必须为内点)*用现有机器参数作初值;*用图解法;*用随机方法;*

用内点法求内点.3.应用内点法应注意的问题---X0,r(0),c的确定2024/3/2031k=0,X(k)=X0,r(k)=r0I2为空集计算指标集以X(K)为初始点,求解得X*。输出是否任取X0,给定r0,c,

2024/3/20322）罚因子的初值*过大,会使的最优点比X0

离真正的最优点更远;过小,在域内的惩罚作用小,在接近边界时则突然加大使性态变坏,且有可能使迭代点越出可行域.

Fox推荐3）递减系数C本书推荐0.1—0.5.2024/3/2033三.SUMT外点法1.惩罚函数的构造考虑非线性规划问题:s.t.惩罚函数可取为2)罚因子*1)时,惩罚项为0,不惩罚;时,惩罚项大于0,有惩罚作用.因

边界时,惩罚项中大括号中的值趋于0,为保证惩罚作用,应取2024/3/20342.SUMT外点法的迭代步骤给定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*---初始点,对凸规划可任意给定;*---外点法点距精度;---等式约束允许的误差限;---不等式约束允许的误差限;---罚因子的放大系数;**为使迭代点进入可行域,可设约束容差带:2024/3/2035例:解:惩罚函数在D外

,对于固定的,令得r(k)x*f(x*)11.50.250.5101.909090.826540.909091001.990990.9802960.99009910001.9990010.9980030.999001…2112024/3/20363.外点法与内点法的比较1)外点法可解各类问题,内点法仅适于IP型问题;2)外点法的初始点可任选,内点法的初始点必须为内点;3)外点法的极小点系列一般在D外,内点法的极小点系列在D内(全为可行点);2024/3/2037四.SUMT混合法

有等式约束时内点法不能用,要求迭代点始终满足不等式约束时外点法不能用.此时可将外点法和内点法结合起来解GP型问题.*1)迭代点应始终满足2)Fiacco等人建议2024/3/2038§5-7拉格朗日乘子法一.等式约束问题的拉格朗日乘子法s.t.1.建立拉氏函数2.在最优点处有如下n+q个方程成立其解为2024/3/2039s.t.二.含不等式约束问题的拉格朗日乘子法1.建立拉氏函数

再用前述方法建立拉氏函数

对不等式约束引入松弛变量,使之成为等式约束:2024/3/20402.在最优点处有如下

n+q+2p个方程成立其解为2024/3/2041三.增广拉格朗日乘子法

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

s.t.2.简约梯度1）将问题降维基向量（状态）式中将X分成两部分：2024/3/2043非基向量（决策)对应的系数矩阵也分成两部分式中，B为对应于XB的m阶方阵，且必须为满秩矩阵；C为对应于X