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

工程优化设计,黄正东二0一二年九月,内容提要,工程优化问题建模优化数学理论一维搜索方法无约束问题直接搜索方法无约束问题间接接搜索方法约束问题直接搜索方法线性规划与二次规划问题求解约束问题间接搜索方法启发式算法优化软件系统,约束问题间接求解方法,间接法:将复杂的约束优化问题转化为一系列简单的、容易解决的子问题。例如，转化为：（1）无约束问题求解；（2）二次规划子问题求解；（3）线性规划子问题或线性约束优化问题。典型的方法有：惩罚函数法拉格朗日乘子法序列二次规划方法序列线性规划方法可行方向法简约梯度法,约束问题间接求解方法,一。惩罚函数法-外点法,min f(x)s.t.hi(x)=0,i=1,2,p gi(x)0,i=1,2,q,基本思想：允许迭代点在可行域外，但违反约束越大，就给出越大惩罚项的目标函数值，这样迫使搜索过程朝可行域方向进行。,0,前一子问题的结果作为后一子问题的初始搜索点，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*)两式相加得，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,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.,约束问题间接求解方法,一。惩罚函数法-外点法,需适当控制rk的初值和增加幅度,约束问题间接求解方法,一。惩罚函数法-外点法,算法：,初始化k=0,xk,rk,eps,beta1.构造无约束目标函数解无约束极值子问题,得xk*.判断xk*是否满足全部约束条件.如果rkG(xk*)eps,x*=xk*,结束;否则,rk+1=beta*rk,xk+1=xk*,k=k+1,转步2.,约束问题间接求解方法,一。惩罚函数法-外点法,算法分析：,优点:(1).迭代过程可以在可行域外进行,易选初值点.(2).对不等式约束和等式约束均适用.(3).可同时用于约束与非约束问题.缺点:(1).理论上证明,只有当rk-时,才有min P(x,rk)-min f(x).随着rk增大,惩罚函数性态变坏(等值线扁平),P(x,rk)不可 避免出现病态,以至子无约束问题难以求解.(2).r0一开始就取得太大,过早出现性态差的P(x,rk),求极值 困难;r0一开始就取得太小,增加迭代次数.一般:r0=1,beta=5-10.,g1(x),P(x,r1),P(x,r2),P(x,r3),适用于中小型一般非线性约束优化问题，但较多用于等式约束优化问题。,约束问题间接求解方法,一。惩罚函数法-内点法,min f(x)s.t.gi(x)0,i=1,2,q,基本思想：内点法的迭代过程在可行域内，目标函数惩罚项在可行域边界筑起一道高墙,使迭代点不能越出可行域.随着惩罚项逐渐变化,高墙越来越陡,从而接近真实约束边界.只适用不等式约束问题.,前一子问题的结果作为后一子问题的初始搜索点，xk*-x*,约束问题间接求解方法,一。惩罚函数法-内点法,例子：min f(x)=x/2 s.t.1-x0,约束问题间接求解方法,一。惩罚函数法-内点法,算法：,初始化k=0,xk,rk,eps,beta1.构造无约束目标函数解无约束极值子问题,得xk*.判断xk*是否满足全部约束条件.如果rkG(xk*)eps,x*=xk*,结束;否则,rk+1=beta*rk,xk+1=xk*,k=k+1,转步2.,约束问题间接求解方法,一。惩罚函数法-内点法,算法分析：,初值点和中间点必须在在可行域内.不能用于等式约束.保持迭代点为可行点的优点是中间点代表可行的设计方案.理论上证明,只有当rk-0,才有min P(x,rk)-min f(x).随着rk减小,惩罚函数变陡,不可避免出现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)s.t.hi(x)=0,i=1,2,m gi(x)0,i=1,2,p,外点拉入,外点拉入,内点保持,0r1r2rk不论x是外点还是内点，都一样计算。,适用于中小型一般非线性约束优化问题。,约束问题间接求解方法,一。惩罚函数法,惩罚函数法总结:,1。能够较好地处理非线性不等式和等式约束。2。约束问题与无约束问题统一处理。3。必需求一序列无约束问题的极值，计算量大。4。随着罚因子变化，出现病态，求极值困难。,约束问题间接求解方法,二。拉格朗日乘子法等式问题解方程方法,min f(x)s.t.hi(x)=0,i=1,2,m,L(x,)=f(x)-ihi(x),解方程组：,n+m个方程，n+m个未知数.方程组的解包含最优问题的解！但是，上述方程非线性时，求解困难。,约束问题间接求解方法,约束问题间接求解方法,二。拉格朗日乘子法一般问题解方程方法,min f(x)s.t.hi(x)=0,i=1,2,m gi(x)0,i=1,2,p,L(x,)=f(x)-ihi(x)-i(gi(x)+wi2),解方程组：,n+m+p个方程，n+m+p个未知数.但是，上述方程非线性时，求解困难。,min f(x)s.t.hi(x)=0,i=1,2,m gi(x)+wi2=0,i=1,2,p,约束问题间接求解方法,二。拉格朗日乘子法求无约束极值点方法,Find x,minimize L(x,),即为K-T条件,该无约束问题的解（x,）满足:,如果K-T方程只有唯一的一组解，且无约束问题的解（x,）存在时，即为原优化问题的解！否则，就不一定！,约束问题间接求解方法,二。拉格朗日乘子法求无约束极值点方法,Find x,minimize L(x,),在Hesse矩阵正定时,K-T方程解唯一，上述无约束问题与与原问题等价。此时，可以用解上述无约束问题的方法，求解原约束优化问题！,约束问题间接求解方法,二。拉格朗日乘子法求无约束极值点方法,实际上,K-T方程是有可能存在多组解。,约束问题间接求解方法,二。拉格朗日乘子法求无约束极值点方法,一般来说，L(x,)的Hesse矩阵不正定时,就可能是这种情况，或者,L(x,)的极小值根本就不存在。,L极值存在，但不相等。L求优方法会得到不正确的解,L极值不存在。L求优方法得不到解！,约束问题间接求解方法,二。拉格朗日乘子法求无约束极值点方法,L(x,)的Hesse矩阵不正定举例：,min f(x)=x12-3x2-x22s.t.x2=0,min L=x12-3x2-x22-x2,非正定的。,所以,拉格朗日乘子法使用的前提:L的Hesse矩阵正定.,约束问题间接求解方法,二。拉格朗日乘子法求平稳点方法,min f(x)s.t.hi(x)=0,i=1,2,m,K-T条件,即为求L(x,)对变量(x,)的平稳点，这里,平稳点包括极值点和马鞍点，一般来说L(x,)不一定存在极小或极大值，例如,L的Hesse矩阵一般不是正定的或负定的。,所以，原问题只能转化为求L(x,)的一般平稳点；即对一些变量求极大值，对一些变量求极小值，对另一些变量解偏导数为零的方程。,Skip it,约束问题间接求解方法,二。拉格朗日乘子法求平稳点方法,然而，一般问题情况下，上述矩阵不是正定的。例如：,对于一般平稳点，缺乏像求极值点一样的有效搜索方法。需要将问题进一步简化。一类特殊平稳点是对一些变量是极小点，对另一些变量是极大点或一般平稳点。例如L(x,)的平稳点可以是对x的极小点，对是一般平稳点，即L=h(x)=0。然而，仍然需要对x的极小点存在，即Hesse矩阵正定：,min f(x)=x12-3x2-x22s.t.x2=0,L=x12-3x2-x22-x2,非正定的。,所以，求极小值与解方程相结合的求L平稳点方法也难于解决问题。,Skip it,约束问题间接求解方法,二。拉格朗日乘子法-增广拉格朗日乘子法,min f(x)s.t.hi(x)=0,i=1,2,m,结合罚函数法与拉格朗日乘子极值法设计出增广拉格朗日乘子法，可以克服罚函数法与拉格朗日乘子极值法的不足。,Find x,minimize M(x,r),r为一充分大的正实数,约束问题间接求解方法,二。拉格朗日乘子法-增广拉格朗日乘子法,Find x,minimize M(x,r),min M=x12-3x2-x22-x2+rx22/2,min f(x)=x12-3x2-x22s.t.x2=0,r2时,半正定,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点完全相同等价。,约束问题间接求解方法,二。拉格朗日乘子法-增广拉格朗日乘子法,所以，如果存在充分大的r使M正定，它的一阶极值条件的点也就是它的真正极值点；从而，求出它的所有极值点也就求出原约束优化问题所有的K-T点；反之，如果不存在充分大的r使M正定（此时，一般是K-T方程有多组解），M优化方法就不一定能找到它的所有一阶极值条件的点，也就不能找到所有K-T点。此时，M方法也可能失效。M方法只在第一种情况改进了L方法，它的应用前提是使M正定的r存在。,约束问题间接求解方法,二。拉格朗日乘子法-增广拉格朗日乘子法,为了减少搜索变量，这里不直接采用针对x和的无约束搜索方法求解M的极值点。而是采用只针对x的无约束搜索方法求解极值点的x分量，同时利用关系计算分量。,即对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正定就行。（克服罚函数法的病态问题）,约束问题间接求解方法,二。拉格朗日乘子法-增广拉格朗日乘子法,算法,1。初始化xk,k,rk,C,rb.2。解无约束问题 min M(x,k,rk)。3。如果k+1=k,|f(xk+1)-f(xk)|rb,rk+1=rb.转步2。,约束问题间接求解方法,二。拉格朗日乘子法-增广拉格朗日乘子法,算法分析,1。克服了罚函数法与普通拉格朗日乘子法的缺点。2。是目前最优秀的约束优化方法之一。3。对中小型、大型约束优化问题均适用，且计算稳定性好。,相同点:都转化为无约束子问题,r为控制参数;不同点:子问题目标函数不同,克服了病态计算问题;,i=i-r*hi(x),约束问题间接求解方法,三。序列二次规划方法（Sequential Quadratic Programming,SQP）,算法思想,用牛顿法解L平稳点方程，每一步迭代又转化为求二次规划问题。,min f(x)s.t.hi(x)=0,i=1,2,m,L平稳点方程,约束问题间接求解方法,三。序列二次规划方法,L平稳点方程的牛顿法,即,根据,得：,即为下列二次规划问题一阶必要条件：,约束问题间接求解方法,三。序列二次规划方法,这样，解此二次规划问题可得d=dx,进而计算xk+1=xk+d.并由A(xk+1)T=g(xk+1)得k+1,从而完成一次牛顿迭代。考虑到xk+1可能出可行域(虽然前面考虑了约束,但近似过程使约束可能没有精确满足)，可改换用罚函数法一维搜索确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=g(xk+1)，A包含h和g（有效约束）的梯度。,约束问题间接求解方法,三。序列二次规划方法,算法分析1。SQP是解非线性约束优化问题得最有效方法之一。2。L的Hesse矩阵可用拟牛顿法中BFGS公式迭代计算。3。方法需要一、二阶导数信息。4。在每一步中，L的Hesse矩阵正定是保证迭代顺利进行的 重要条件。,约束问题间接求解方法,三。序列二次规划方法,i=i-r*hi(x),无约束子问题,r为控制参数;病态计算问题;整体渐近,无约束子问题,r为控制参数;无病态计算问题;整体渐近,约束子问题,无控制参数;需要二阶导数;局部逼近,约束问题间接求解方法,五。序列线性规划法,算法思想,针对非线性约束优化问题，对目标函数和约束函数进行线性化，求解线性规划问题确定每步移动。,min f(x)s.t.hi(x)=0,i=1,2,m gi(x)0,i=m+1,2,p,k:=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方法（局部转化为等式约束）松弛变量转化为等式约束 障碍函数法（传统内点法）混合约束：受限梯度方向搜索法 广义简约梯度法 改进的可行方向法 序列化逼近法 序列线性规划法 序列二次规划法（SQP法、增广SQP法、SQP+方向搜索法）序列凸规划法 序列无约束法（传统的内点法、外点法、混合法；增广L乘子法）序列等式约束法（ActiveSet-KKT混合法（边界法）、障碍-KKT混合法（内点法）,约束问题间接求解方法,总结,约束问题间接求解方法,一般性方法：惩罚函数法序列线性规划方法可行方向法最优秀的方法：增广拉格朗日乘子法序列二次规划方法简约梯度法最常用的方法：序列线性规划方法序列二次规划方法,