工程优化设计约束间接法课件

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

2、(x)0, i=1,2,q基本思想：允许迭代点在可行域外，但违反约束越大，就给出越大惩罚项的目标函数值，这样迫使搜索过程朝可行域方向进行。0r0r1rk前一子问题的结果作为后一子问题的初始搜索点，xk*-x*约束问题间接求解方法一。惩罚函数法-外点法性质：当rk+1rk时，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*) f(xk*)+rkG(xk*) f(xk*)+rk+1G(xk*) f(xk+1*)+rk+1G(xk+1*)两式相

3、加得， rk+1G(xk*)-G(xk+1*) rkG(xk*)-G(xk+1*)由于rk+1rk0, 故满足上式须G(xk*)-G(xk+1*) 0，则有G(xk*) G(xk+1*) 。约束问题间接求解方法一。惩罚函数法-外点法例子：min f(x)=x/2 s.t. 1-x0 xf,pf(x)x*P(x,r0)P(x,r1)P(x,r2)P(x,r3)P(x,rk)=x/2+rkmax(0,1-x)2考虑到此例子问题解在可行域外，直接取：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-

4、 时，xk*-1; P-1/2. 约束问题间接求解方法一。惩罚函数法-外点法xf,pf(x)x*xf,pf(x)x*数值超大需适当控制rk的初值和增加幅度约束问题间接求解方法一。惩罚函数法-外点法算法：初始化k=0, xk,rk,eps,beta1.构造无约束目标函数解无约束极值子问题,得xk*.判断xk*是否满足全部约束条件. 如果rkG(xk*)时,才有min P(x,rk)-min f(x). 随着rk增大,惩罚函数性态变坏(等值线扁平), P(x,rk)不可 避免出现病态,以至子无约束问题难以求解. (2). r0一开始就取得太大, 过早出现性态差的P(x,rk),求极值 困难; r0

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

6、例子：min f(x)=x/2 s.t. 1-x0 xf,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+22rk) /2当rk- 0时，xk*-1; P-1/2. 约束问题间接求解方法一。惩罚函数法-内点法算法：初始化k=0, xk,rk,eps,beta1.构造无约束目标函数解无约束极值子问题,得xk*.判断xk*是否满足全部约束条件. 如果rkG(xk*)0,才有min P(x,rk)-min f(x). 随着rk减小,惩罚函数变陡, 不可避免

7、出现1/g(x)-浮点溢出.r0与beta值对收敛性态有影响.一般取r0=1, beta=0.1-0.5.对于初始点为非可行时,需要采用前处理过程,将它“拉入”可 行域内.适用于中小型不等式约束优化问题。约束问题间接求解方法一。惩罚函数法-内点法初始点生成过程：设I1= i | gi(x)0, I2= i | gi(x)0 k=0, 任取xk.计算I1和I2.如果I2为空, xk为可行,结束. 否则, 转下步.内点法解 , rk-0rk+1=beta*rk, 1beta0, k=k+1, xk+1=xk*, 转步2. 拉入保持可行约束问题间接求解方法一。惩罚函数法-混合法基本思想min f(x

8、)s.t. hi(x)=0, i=1,2,m gi(x)0, i=1,2,p外点拉入外点拉入内点保持0r1r2rk2时,半正定, M对x, 非严格极值存在.r2时,正定, 对给定 M对x严格极值存在.约束问题间接求解方法二。拉格朗日乘子法-增广拉格朗日乘子法所以，当r充分大时，Hesse矩阵正定或半正定。即，当r充分大时，M对x, 的极值存在。M的极值点是否是原K-T方程的解呢?约束问题间接求解方法二。拉格朗日乘子法-增广拉格朗日乘子法当hi(x)=0时，xM= xL.M的一阶极值条件：因为都有hi(x)=0，所以，满足M的一阶极值条件的点与原问题的K-T点完全相同等价。约束问题间接求解方法二

9、。拉格朗日乘子法-增广拉格朗日乘子法所以，如果存在充分大的r使M正定，它的一阶极值条件的点也就是它的真正极值点；从而，求出它的所有极值点也就求出原约束优化问题所有的K-T点；反之，如果不存在充分大的r使M正定（此时，一般是K-T方程有多组解），M优化方法就不一定能找到它的所有一阶极值条件的点，也就不能找到所有K-T点。此时，M方法也可能失效。M方法只在第一种情况改进了L方法，它的应用前提是使M正定的r存在。约束问题间接求解方法二。拉格朗日乘子法-增广拉格朗日乘子法为了减少搜索变量，这里不直接采用针对x和的无约束搜索方法求解M的极值点。而是采用只针对x的无约束搜索方法求解极值点的x分量，同时利用

10、关系计算分量。即对x求极值min xM(x,), 对求解方程M(x,)=0 !约束问题间接求解方法二。拉格朗日乘子法-增广拉格朗日乘子法对于给定的和r,对M求极值xm* ，其条件是即xm*=xm*(, r)，但一般h(xm*)0.然而，一旦h(xm*)=0，就有=*和xm*=x*。这里x*是原问题的解。选择序列(1,r1), (2,r2), (k,rk), ,使h(xm*)-0,就有xm*-x*。由于同时需要k- *，根据 知，rh(x)-k比-k更接近-*，所以，取k+1= k-rh(x).一般来说，rk也需要递增，但并不需要趋向无穷大，只需要使Mxx正定就行。（克服罚函数法的病态问题）约束

11、问题间接求解方法二。拉格朗日乘子法-增广拉格朗日乘子法算法1。初始化xk, k, rk, C, rb.2。解无约束问题 min M(x, k, rk)。3。如果k+1=k, |f(xk+1)-f(xk)|eps, |h(xk+1)| rb, rk+1=rb. 转步2。约束问题间接求解方法二。拉格朗日乘子法-增广拉格朗日乘子法算法分析1。克服了罚函数法与普通拉格朗日乘子法的缺点。2。是目前最优秀的约束优化方法之一。3。对中小型、大型约束优化问题均适用，且计算稳定性好。相同点:都转化为无约束子问题,r为控制参数;不同点:子问题目标函数不同,克服了病态计算问题;i=i-r*hi(x)约束问题间接求解

12、方法三。序列二次规划方法（Sequential Quadratic Programming, SQP）算法思想用牛顿法解L平稳点方程，每一步迭代又转化为求二次规划问题。min f(x)s.t. hi(x)=0, i=1,2,mL平稳点方程约束问题间接求解方法三。序列二次规划方法L平稳点方程的牛顿法即根据得：即为下列二次规划问题一阶必要条件：约束问题间接求解方法三。序列二次规划方法这样，解此二次规划问题可得d=dx, 进而计算xk+1=xk+d.并由A(xk+1)T=g(xk+1)得k+1,从而完成一次牛顿迭代。考虑到xk+1可能出可行域 (虽然前面考虑了约束,但近似过程使约束可能没有精确满足)

13、 ，可改换用罚函数法一维搜索确xk+1=xk+ad。算法：1。初始化，k=0, x0, 0.2。解（xk, k）处得二次规划子问题,得dk。3。一维搜索 min P(xk+adk), P(x)=f(x)+Mh(x)2, 得xk+1=xk+adk.4。解A(xk+1)T=g(xk+1)得k+1。5。如果收敛，停止；否则，k=k+1,转步2。约束问题间接求解方法约束问题间接求解方法约束问题间接求解方法三。序列二次规划方法-不等式约束问题min f(x)s.t. hi(x)=0, i=1,2,m gi(x)0, i=m+1,2,p一维搜索 min P(xk+ad ):k+1计算: A(xk+1)T=

14、g(xk+1)， A包含h和g（有效约束）的梯度。约束问题间接求解方法三。序列二次规划方法算法分析1。SQP是解非线性约束优化问题得最有效方法之一。2。L的Hesse矩阵可用拟牛顿法中BFGS公式迭代计算。3。方法需要一、二阶导数信息。4。在每一步中，L的Hesse矩阵正定是保证迭代顺利进行的 重要条件。约束问题间接求解方法三。序列二次规划方法i=i-r*hi(x)无约束子问题,r为控制参数;病态计算问题;整体渐近无约束子问题,r为控制参数;无病态计算问题;整体渐近约束子问题,无控制参数;需要二阶导数;局部逼近约束问题间接求解方法五。序列线性规划法算法思想针对非线性约束优化问题，对目标函数和约

15、束函数进行线性化，求解线性规划问题确定每步移动。min f(x)s.t. hi(x)=0, i=1,2,m gi(x)0, i=m+1,2,pk:=k+1约束问题间接求解方法算法初始化 x=x0,k=0，dkl,dku, r1;计算f(xk)、hi(xk)和gi(xk);如果f(xk)、hi(xk)和gi(xk)满足K-T条件, 结束.否则,用单纯形法解上述线性规划问题,求d;xk+1=xk+d,更新move-limit dkl=r*dkl,dku=r*dku;k=k+1,转步2.约束问题间接求解方法五。序列线性规划法Move Limit 根据线性化有效范围限制最大移动步长约束问题间接求解方法五。序列线性规划法算法分析线性化范围和此范围随迭代次数的缩小率与可行方向法相比，相同点是都为线性近似；不同点是这里直接确定下一点；那里只确定搜索方向，还需要一维搜索。等式约束： 简约梯度法 惩罚函数法 解KKT方程法（L乘子法、SQP(牛顿法)） 惩罚函数-KKT方程联合法（增广L乘子法、增广SQP法）不等式约束 可行方向法 Active-set方法（局部转化为等式约束） 松弛变量转化为等式约束 障碍函数法（传统内点法） 混合约束： 受限梯度方向