工程优化设计-约束间接法

《工程优化设计-约束间接法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、工程优化设计黄正东二0一二年九月内容提要工程优化问题建模优化数学理论一维搜索方法无约束问题直接搜索方法无约束问题间接接搜索方法约束问题直接搜索方法线性规划与二次规划问题求解约束问题间接搜索方法启发式算法优化软件系统约束问题间接求解方法间接法:将复杂的约束优化问题转化为一系列简单的、容易解决的子问题。例如，转化为：（1）无约束问题求解；（2）二次规划子问题求解；（3）线性规划子问题或线性约束优化问题。典型的方法有：惩罚函数法拉格朗日乘子法序列二次规划方法序列线性规划方法可行方向法简约梯度法约束问题间接求解方法一。惩罚函数法---外点法minf(x)

2、s.t.hi(x)=0,i=1,2,…,pgi(x)0,i=1,2,…,q基本思想：允许迭代点在可行域外，但违反约束越大，就给出越大惩罚项的目标函数值，这样迫使搜索过程朝可行域方向进行。0前一子问题的结果作为后一子问题的初始搜索点，xk*->x*约束问题间接求解方法一。惩罚函数法---外点法性质：当rk+1>rk时，G(xk+1*)G(xk*).这里P(x,rk)=f(x)+rkG(x)。证明：设P(x,rk)的最优点为xk*,P(x,rk+1)的最优点为xk+1*.那么，f(xk+1*)+rkG(xk+1*)

3、f(xk*)+rkG(xk*)f(xk*)+rk+1G(xk*)f(xk+1*)+rk+1G(xk+1*)两式相加得，rk+1[G(xk*)-G(xk+1*)]rk[G(xk*)-G(xk+1*)]由于rk+1>rk>0,故满足上式须G(xk*)-G(xk+1*)0，则有G(xk*)G(xk+1*)。约束问题间接求解方法一。惩罚函数法---外点法例子：minf(x)=x/2s.t.1-x0xf,pf(x)x*P(x,r0)P(x,r1)P(x,r2)P(x,r3)P(x,rk)=x/2+rk[max(0,1-x)]2考虑到此例子问题解

4、在可行域外，直接取：P(x,rk)=x/2+rk(1-x)2求导得：1/2-2rk(1-x)=0.xk*=1-1/4rk,P(x,rk)=1/2-1/(16rk)当rk->时，xk*->1;P->1/2.约束问题间接求解方法一。惩罚函数法---外点法xf,pf(x)x*xf,pf(x)x*数值超大需适当控制rk的初值和增加幅度约束问题间接求解方法一。惩罚函数法---外点法算法：初始化k=0,xk,rk,eps,beta>1.构造无约束目标函数解无约束极值子问题,得xk*.判断xk*是否满足全部约束条件.如果rkG(xk*)

5、,结束;否则,rk+1=beta*rk,xk+1=xk*,k=k+1,转步2.约束问题间接求解方法一。惩罚函数法---外点法算法分析：优点:(1).迭代过程可以在可行域外进行,易选初值点.(2).对不等式约束和等式约束均适用.(3).可同时用于约束与非约束问题.缺点:(1).理论上证明,只有当rk->时,才有minP(x,rk)->minf(x).随着rk增大,惩罚函数性态变坏(等值线扁平),P(x,rk)不可避免出现病态,以至子无约束问题难以求解.(2).r0一开始就取得太大,过早出现性态差的P(x,rk),求极值困难;r0一开始就取得太小,

6、增加迭代次数.一般:r0=1,beta=5-10.g1(x)g2(x)x*P(x,r1)P(x,r2)P(x,r3)适用于中小型一般非线性约束优化问题，但较多用于等式约束优化问题。约束问题间接求解方法一。惩罚函数法---内点法minf(x)s.t.gi(x)0,i=1,2,…,q基本思想：内点法的迭代过程在可行域内，目标函数惩罚项在可行域边界筑起一道高墙,使迭代点不能越出可行域.随着惩罚项逐渐变化,高墙越来越陡,从而接近真实约束边界.只适用不等式约束问题.r0>r1>…>rk>…->0前一子问题的结果作为后一子问题的初始搜索点，xk*->x*约

7、束问题间接求解方法一。惩罚函数法---内点法例子：minf(x)=x/2s.t.1-x0xf,pf(x)x*P(x,r0)P(x,r1)P(x,r2)P(x,r3)P(x,rk)=x/2-rk/(1-x)求导得：1/2+rk/(1-x)2=0.xk*=1+2rk,P(x,rk)=(1+22rk)/2当rk->0时，xk*->1;P->1/2.约束问题间接求解方法一。惩罚函数法---内点法算法：初始化k=0,xk,rk,eps,beta<1.构造无约束目标函数解无约束极值子问题,得xk*.判断xk*是否满足全部约束条件.如果rkG(xk*)<

8、eps,x*=xk*,结束;否则,rk+1=beta*rk,xk+1=xk*,k=k+1,转步2.约束问题间接求解方法一。惩罚函数法--