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

1、工程优化设计黄正东二0一二年九月内容提要 工程优化问题建模工程优化问题建模 优化数学理论优化数学理论 一维搜索方法一维搜索方法 无约束问题直接搜索方法无约束问题直接搜索方法 无约束问题间接接搜索方法无约束问题间接接搜索方法 约束问题直接搜索方法约束问题直接搜索方法 线性规划与二次规划问题求解线性规划与二次规划问题求解 约束问题间接搜索方法约束问题间接搜索方法 启发式算法启发式算法 优化软件系统优化软件系统约束问题间接求解方法间接法间接法: : 将复杂的约束优化问题转化为一系列简单的、容易将复杂的约束优化问题转化为一系列简单的、容易解决的子问题。例如，转化为：解决的子问题。例如，转化为：（1 1

2、）无约束问题求解；）无约束问题求解；（2 2）二次规划子问题求解；）二次规划子问题求解；（3 3）线性规划子问题或线性约束优化问题。）线性规划子问题或线性约束优化问题。典型的方法有：典型的方法有：1.1. 惩罚函数法惩罚函数法2.2. 拉格朗日乘子法拉格朗日乘子法3.3. 序列二次规划方法序列二次规划方法4.4. 序列线性规划方法序列线性规划方法5.5. 可行方向法可行方向法6.6. 简约梯度法简约梯度法约束问题间接求解方法一。惩罚函数法一。惩罚函数法-外点法外点法min f(x)s.t. hi(x)=0, i=1,2,p gi(x) 0, i=1,2,q基本思想：基本思想：允许迭代点在可行域

3、外，但违反约束越大，就给出允许迭代点在可行域外，但违反约束越大，就给出越大惩罚项的目标函数值，这样迫使搜索过程朝可行域方向进越大惩罚项的目标函数值，这样迫使搜索过程朝可行域方向进行。行。piqiikikkxgrxhrxfrxP1122)(, 0max()()(),( min0r0r1rk 前一子问题的结果作为前一子问题的结果作为后一子问题的初始后一子问题的初始搜索点，搜索点，xk*-x*约束问题间接求解方法一。惩罚函数法一。惩罚函数法-外点法外点法性质：性质：当当rk+1rk时，时，G(xk+1*) G(xk*). 这里这里P(x,rk)=f(x)+rkG(x)。证明：证明： 设设P(x,rk

4、)的最优点为的最优点为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*)两式相加得，两式相加得， 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-x 0 xf

5、,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- 时，时，xk*-1; P-1/2. 约束问题间接求解方法一。惩罚函数法一。惩罚函数法-外点法外点法xf,pf(x)x*xf,pf(x)x*数值超大数值超大需适当控制需适当控制r rk k的的初值和初值和增加幅度增加幅度约束问题间接求解方法

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

7、现性态差的过早出现性态差的P(x,rk),求极值求极值 困难困难; r0一开始就取得太小一开始就取得太小,增加迭代次数增加迭代次数. 一般一般: 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基本思想：基本思想：内点法的迭代过程在可行域内，目标函数惩罚项内点法的迭代过程在可行域内，目标函数惩罚项在可

8、行域边界筑起一道高墙在可行域边界筑起一道高墙,使迭代点不能越出可行域使迭代点不能越出可行域. 随着随着惩罚项逐渐变化惩罚项逐渐变化,高墙越来越陡高墙越来越陡, 从而接近真实约束边界从而接近真实约束边界.只适用不等式约束问题只适用不等式约束问题.qiikkxgrxfrxP1)(/1)(),( minr0r1rk-0前一子问题的结果作为前一子问题的结果作为后一子问题的初始后一子问题的初始搜索点，搜索点，xk*-x*约束问题间接求解方法一。惩罚函数法一。惩罚函数法-内点法内点法例子：例子：min f(x)=x/2 s.t. 1-x 0 xf,pf(x)x*P(x,r0)P(x,r1)P(x,r2)P

9、(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. 约束问题间接求解方法一。惩罚函数法一。惩罚函数法-内点法内点法算法：算法：1. 初始化初始化k=0, xk,rk,eps,beta1.2. 构造无约束目标函数构造无约束目标函数3. 解无约束极值子问题解无约束极值子问题,得得xk*.4. 判断判断xk*是否满足全部约束条件是否满足全部约束条件. 如果如果rkG(xk*)0,才有才有min P(x,rk)-min f(x). 随着随着r

10、k减小减小,惩罚函数变陡惩罚函数变陡, 不可避免出现不可避免出现1/g(x)- 浮点溢出浮点溢出.5. r0与与beta值对收敛性态有影响值对收敛性态有影响.一般取一般取r0=1, beta=0.1-0.5.6. 对于初始点为非对于初始点为非可行时可行时,需要采用前处理过程需要采用前处理过程,将它将它“拉入拉入”可可 行域内行域内.适用于中小型不等式约束优化问题。适用于中小型不等式约束优化问题。约束问题间接求解方法一。惩罚函数法一。惩罚函数法-内点法内点法初始点生成过程：初始点生成过程：设设I1= i | gi(x) 0, I2= i | gi(x)0 1. k=0, 任取任取xk.2. 计算

11、计算I1和和I2.3. 如果如果I2为空为空, xk为可行为可行,结束结束. 否则否则, 转下步转下步.4. 内点法解内点法解 , rk-05. rk+1=beta*rk, 1beta0, k=k+1, xk+1=xk*, 转步转步2. 12)(/ 1)(),(IiikIiikxgrxgrxP12)(/1)(),(IiikIiikxgrxgrxP拉入拉入保持可行保持可行约束问题间接求解方法一。惩罚函数法一。惩罚函数法-混合法混合法基本思想基本思想min f(x)s.t. hi(x)=0, i=1,2,m gi(x)0, i=1,2,p0)(|,0)(|,)()(, 0max()(11)(),(

12、2112212xgiIxgiIxhrxgrxgrxfrxPiimiikIiIiikikk外点拉入外点拉入外点拉入外点拉入内点保持内点保持0r1r2rk2r2时时, ,半正定半正定, M, M对对x, x, 非严格非严格极值存在极值存在. .r2r2时时, ,正定正定, , 对给定对给定 M M对对x x严格极值存在严格极值存在. .约束问题间接求解方法二。二。拉格朗日乘子法拉格朗日乘子法-增广拉格朗日乘子法增广拉格朗日乘子法所以，当所以，当r充分大时，充分大时，Hesse矩阵正定或半正定。矩阵正定或半正定。即，当即，当r充分大时，充分大时，M对对x, 的极值存在。的极值存在。M的极值点是否是原

13、的极值点是否是原K-T方程的解呢方程的解呢?约束问题间接求解方法miiiimiiimiiimiiixxxhxrhxfxhxhrxhxfxhxhrxLrxM1111)()()()()()()()()(),(),(二。二。拉格朗日乘子法拉格朗日乘子法-增广拉格朗日乘子法增广拉格朗日乘子法当当hi(x)=0时时，x xM= xL.M的一阶极值条件：的一阶极值条件： ,.,2 , 1, 0)(0mixhMMix因为都有因为都有hi(x)=0，所以，满足所以，满足M M的的一阶极值条件的点一阶极值条件的点与原问题与原问题的的K-TK-T点点完全相同等价。完全相同等价。约束问题间接求解方法二。二。拉格朗日

14、乘子法拉格朗日乘子法-增广拉格朗日乘子法增广拉格朗日乘子法所以，如果存在充分大的所以，如果存在充分大的r r使使M M正定，它的正定，它的一阶极值条件的点一阶极值条件的点也就是它的也就是它的真正极真正极值点值点；从而，求出它的；从而，求出它的所有所有极极值点值点也就求出也就求出原约束优化问题原约束优化问题所有的所有的K-T点点；反之，反之，如果不存在充分大的如果不存在充分大的r r使使M M正定（此时，一般是正定（此时，一般是K-T方程方程有多组解有多组解），），M M优化方法就不一定能找到它的优化方法就不一定能找到它的所有所有一阶极值条一阶极值条件的点，也就不能找到所有件的点，也就不能找到所

15、有K-TK-T点。此时，点。此时，M M方法也可能失效。方法也可能失效。M方法方法只在第一种情况改进了只在第一种情况改进了L方法方法，它的应用前提是使，它的应用前提是使M正定正定的的r存在。存在。约束问题间接求解方法二。二。拉格朗日乘子法拉格朗日乘子法-增广拉格朗日乘子法增广拉格朗日乘子法为了减少搜索变量，这里不直接采用针对为了减少搜索变量，这里不直接采用针对x和和的的无约束搜索方法求解无约束搜索方法求解M M的极值点。的极值点。而是采用只针对而是采用只针对x的无约束搜索方法求解极值点的的无约束搜索方法求解极值点的x分量，分量，同时利用关系同时利用关系计算计算分量分量。miiimiiiixxh

16、xfxhxrhxfrxM1*1)()()()()(),(即对x求极值min xM(x,), 对求解方程M(x,)=0 !约束问题间接求解方法0),(*rxMmx二。二。拉格朗日乘子法拉格朗日乘子法-增广拉格朗日乘子法增广拉格朗日乘子法对于对于给定的给定的和和r, ,对对M求极值求极值xm* ，其条件是，其条件是即即xm* *= =xm* *( (, r) )，但一般，但一般h(h(xm*) )0.然而，一旦然而，一旦h(xm*)=0，就有就有=*和和xm*=x*。这里这里x*是原问题的是原问题的解。解。选择序列选择序列(1,r1), (2,r2), (k,rk), ,使使h(xm*)-0,就有

17、就有xm*-x*。由于同时需要由于同时需要k- *，根据根据 miiiixxhxrhxfrxM1)()()(),(知，知，rh(x)-k比比-k更接近更接近-*，所以，取所以，取k+1= k-rh(x).一般来说，一般来说，r rk k也需要递增，但并不需要趋向无穷大，只需也需要递增，但并不需要趋向无穷大，只需要使要使M Mxxxx正定就行。（克服罚函数法的病态问题）正定就行。（克服罚函数法的病态问题）约束问题间接求解方法二。二。拉格朗日乘子法拉格朗日乘子法-增广拉格朗日乘子法增广拉格朗日乘子法算法算法1 1。初始化。初始化x xk k, , k k, , r rk k, C, , C, r

18、rb b. .2 2。解无约束问题。解无约束问题 min M(x, min M(x, k k, , r rk k) )。3 3。如果。如果k+1k+1= =k k, |f(x, |f(xk+1k+1)-f(x)-f(xk k)|)|epseps, |h(x, |h(xk+1k+1)|)| r rb b, r, rk+1k+1= =r rb b. . 转步转步2 2。约束问题间接求解方法miiimiixhxhrxfrxM112)()(2)(),(二。二。拉格朗日乘子法拉格朗日乘子法-增广拉格朗日乘子法增广拉格朗日乘子法算法分析算法分析1 1。克服了罚函数法与普通。克服了罚函数法与普通拉格朗日乘子

19、法的缺点。拉格朗日乘子法的缺点。2 2。是目前最优秀的约束优化方法之一。是目前最优秀的约束优化方法之一。3 3。对中小型、大型约束优化问题均适用，且计算稳定性好。对中小型、大型约束优化问题均适用，且计算稳定性好。miixhrxfrxP12)(2)(),(相同点相同点: :都转化为无约束子问题都转化为无约束子问题,r,r为控制参数为控制参数; ;不同点不同点: :子问题目标函数不同子问题目标函数不同, ,克服了病态计算问题克服了病态计算问题; ;i=i-r*hi(x)约束问题间接求解方法三。三。序列二次规划方法（序列二次规划方法（Sequential Quadratic Programming,

20、 SQP）算法思想算法思想用牛顿法解用牛顿法解L L平稳点方程，每一步迭代又转化为求二次规划平稳点方程，每一步迭代又转化为求二次规划问题。问题。min f(x)s.t. hi(x)=0, i=1,2,m )(),.,(),()(),(),.,(),()( , 0)(),( , 0)()()()(),(21211xhxhxhxAxhxhxhxhxhxLxAxgxhxfxLmTmTTmiiixmiiixhxfxL1)()(),(L L平稳点方程平稳点方程约束问题间接求解方法 )(),(0)()(),(),(),( ,2211kkkxkTkkkxxkkkkkkkkxhxLddxxAxAxLxLddx

21、xLddxxx ,)()(),(1dxAxgxLkkkTkkkkx12,)()(0)()(),(kkkkTkkkxxxhxgdxxAxAxL三。三。序列二次规划方法序列二次规划方法L L平稳点方程的牛顿法平稳点方程的牛顿法即即根据根据得：得：即为下列二次规划问题即为下列二次规划问题一阶必要条件：一阶必要条件：)(0)()( . .),(21)()( min2dxdxhdxAtsdxLdxgddqkkkkxxTkT约束问题间接求解方法三。三。序列二次规划方法序列二次规划方法这样，解此这样，解此二次规划问题可得二次规划问题可得d=dx, 进而计算进而计算xk+1=xk+d.并由并由A(xk+1)T

22、=g(xk+1)得得k+1,从而完成一次牛顿迭代。从而完成一次牛顿迭代。考虑到考虑到xk+1可能出可行域可能出可行域 (虽然前面考虑了约束虽然前面考虑了约束, ,但近似过程使但近似过程使约束可能没有精确满足约束可能没有精确满足) ，可改换用罚函数法一维搜索确，可改换用罚函数法一维搜索确x xk+1k+1=xk+ad。算法：算法：1 1。初始化，。初始化，k=0, xk=0, x0 0, , 0.2。解（解（x xk k, , k）处得二次规划子问题）处得二次规划子问题, ,得得d dk k。3 3。一维搜索。一维搜索 min min P(P(xk+adk), P(x)=f(x)+Mh(x),

23、P(x)=f(x)+Mh(x)2 2, , 得得x xk+1k+1= =xk+adk.4。解解A(xA(xk+1k+1) )T T=g(x=g(xk+1k+1) )得得k+1k+1。5 5。如果收敛，停止；否则，。如果收敛，停止；否则，k=k+1,k=k+1,转步转步2 2。约束问题间接求解方法约束问题间接求解方法约束问题间接求解方法mipmiiiiikkkkkkxxTkTxgxhxfxLgBhAxgdxBxhdxAtsdxLdxfddq11112)()()(),(,.)(,.),(0)()( 0)()( . .),(21)()( min三。三。序列二次规划方法序列二次规划方法-不等式约束问题

24、不等式约束问题min f(x)s.t. hi(x)=0, i=1,2,m gi(x)0, i=m+1,2,pmipmiiixgMxhMxfxP1122)(, 0max()()()(一维搜索一维搜索 min min P(xP(xk k+a+ad d ):):k+1计算计算: A(xk+1)T=g(xk+1)， A包含包含h h和和g g（有效约束）的梯度。（有效约束）的梯度。约束问题间接求解方法三。三。序列二次规划方法序列二次规划方法算法分析算法分析1 1。SQPSQP是解非线性约束优化问题得最有效方法之一是解非线性约束优化问题得最有效方法之一。2。L L的的HesseHesse矩阵可用拟牛顿法

25、中矩阵可用拟牛顿法中BFGSBFGS公式迭代计算。公式迭代计算。3。方法需要一、二阶导数信息。方法需要一、二阶导数信息。4。在每一步中，。在每一步中，L L的的HesseHesse矩阵正定是保证迭代顺利进行的矩阵正定是保证迭代顺利进行的 重要条件。重要条件。约束问题间接求解方法三。三。序列二次规划方法序列二次规划方法miiimiixhxhrxfrxM112)()(2)(),(minmiixhrxfrxP12)(2)(),(mini=i-r*hi(x)0)()( .),(21)()( min2kkkkxxTkTxhdxAtsdxLdxgddq无约束子问题无约束子问题,r,r为控制参数为控制参数;

26、 ;病态计算问题病态计算问题; ;整体渐近整体渐近无约束子问题无约束子问题,r,r为控制参数为控制参数; ;无无病态计算问题病态计算问题; ;整体渐近整体渐近约束子问题约束子问题, ,无控制参数无控制参数; ;需要二阶导数需要二阶导数; ;局部逼近局部逼近约束问题间接求解方法五。五。序列线性规划法序列线性规划法算法思想算法思想 针对非线性约束优化问题，对目标函数和约束函数针对非线性约束优化问题，对目标函数和约束函数进行线性化，求解线性规划问题确定每步移动。进行线性化，求解线性规划问题确定每步移动。min f(x)s.t. hi(x)=0, i=1,2,m gi(x)0, i=m+1,2,pdx

27、xdddxgdxgxhdxhtsxfdxfkkuklkkiTkikiTkikTk1 0)()( 0)()( . .)()( mink:=k+1约束问题间接求解方法算法算法1.1. 初始化初始化 x=xx=x0 0,k=0,k=0，d dk kl l,d dk ku u, r1;, r1;2.2. 计算计算 f(xf(xk k) )、 h hi i(x(xk k) )和和 g gi i(x(xk k) ); ;3.3. 如果如果 f(xf(xk k) )、 h hi i(x(xk k) )和和 g gi i(x(xk k) )满足满足K-TK-T条件条件, , 结束结束. .4.4. 否则否则, ,用单纯形法解上述线性规划问题用单纯形法解上述线性规划问题, ,求求d;d;5.5. x xk+1k+1= =x xk k+d+d, ,更新更新move-limit move-limit d dk kl l=r=r* *d dk kl l,d dk ku u=r=r* *d dk ku u; ;6.6. k=k+1,k=k+1,转步转步2.2.约束问题间接求解方法五。五。序列线性规划法序列线性规划法Move Limit Move Limit 根据线性化有效范围限制根据线性化有效范围限制最