互补约束问题的松弛规划

互补约束问题的松弛规划

1mpcc的算法相互限制问题（pmc）是一种特殊的限制优化问题。与一般限制优化问题相比，其基本限制不仅包括等式限制和等式限制，还包括相对复杂的相互限制。mpc的一般形式如下。且假设f,g,h,G,H均二次连续可微.互补约束问题因其特殊的约束条件,使得它与一般约束最优化问题具有很大的区别[1,2],象MFCQ,LICQ等一般约束最优化问题的约束规范条件在MPCC中已不再成立,而且MPCC的可行域结构也复杂得多,我们不能简单地应用已有的求解约束最优化问题的方法和理论去求解MPCC.因此,解决此类问题的算法成为近几年运筹学研究的热点,出现了象内点罚算法(PIPA)[3],磨光二次规划(SSQP)算法[4],分片逐步二次规划(PSQP)算法[3]以及牛顿捆集信赖域算法(Newton,Trust-Region)并得到如下收敛性质:设z与H.Scheel和S.Scholtes不同,G.H.Lin和M.Fukushima(2005)通过技巧性地同时改造两个约束条件(3)与(4)式,在ε>0的情况下,得到了一种新的松弛规划子问题(二)[8]:并在较弱的条件下得到了与(一)相同的收敛结果.在以上松弛规划算法的启发下,本文运用乌力吉关于互补问题乘子法的思想[9,10],构造了一种全新的松弛子问题.与以上松弛算法中所用到的松弛子问题相比,该子问题的约束条件都有明显的减少.接下来,文中引入了一种基于逐步二次规划(SQP)方法的新算法,通过对该松弛子问题有技巧地应用SQP方法,在不需要迭代序列的聚点满足严格互补的较弱条件下获得了该算法的全局收敛性.贯穿全文,我们约定:下标表示向量的分量,上标表示迭代序列的序号.设F(z)为向量函数,定义集合D2般约束优化问题在本节,首先给出MPCC的一些常用一阶最优性条件:(1)B稳定点[11]:前面提到,对于MPCC问题,一般约束优化问题的约束规范条件LICQ和MFCQ等均不再成立.事实上,若我们把MPCC看成一般约束优化问题,在可行点线性无关.注意到(2)W稳定点[12]:设易见,若当可行点z满足条件(10)-(12)时,称为MPCC的W稳定点,其中μ=(μ(3)C稳定点[12]:可行点(4)M稳定点[13]:可行点(5)S-B稳定点[12]:可行点命题2.1设3种新的松弛子问题我们在R称λ为乘子参数,称为关于函数min(u,v)在变量u(或v)的乘子.引入残量函数再引入乘子参数的残量这样,(13)也可写成命题3.2函数l(u,v,λ)和证明l(u,v,λ)的连续可微性以及▽l(u,v,λ)的形式(14)易见.由(13)式易见φ(u,v,λ)为了书写方便,以下我们记一般互补问题为NCP(G,H).定义函数L(z,λ),χ(z),φ(z,λ),μ(z,λ)和θ(z,λ)如下且称χ(z)为NCP(G,H)在z的乘子,由引理3.1易见命题3.3(ⅰ)(ⅱ)命题3.4函数L(z,λ)和θ(z,λ)在R证明由命题3.2知,函数l(u,v,λ)和υ(u,v,λ)连续可微,又由假设函数F(z),G(z)也连续可微,注意到L(z,λ)和θ(z,λ)是由l(u,v,λ),υ(u,v,λ)与F(z),G(z)复合而成,故由复合函数的求导法则,我们很容易得到函数L(z,λ)和θ(z,λ)的连续可微性.且由式(14),有由命题3.3及函数θ(z,λ)的表达式,我们考虑MPCC问题的如下松弛子问题:其中δ>0称为松弛迭代参数,λ称为乘子迭代参数.设F为MPCC问题的可行域,从命题3.3容易看出,对任意z∈F和δ>0,只要在(Re(δ))中取λ=χ(z),则(z,λ)∈F,这里Fδ表示问题Re(δ)的可行域.因此,我们称Re(δ)为MPCC问题的松弛形式.4基于二次规划的松弛问题基于MPCC的松弛子问题Re(δ),我们给出求解MPCC问题的一种松弛算法.该算法的基本思想是对松弛子问题Re(δ)实施逐步二次规划法.首先,我们来讨论求解目标函数下降方向的子问题.在第k个迭代步,设参数为δk,并令解得,其中Q由于二次规划Sub(δ为构造以下算法,我们考虑松弛子问题Re(δ)的如下L算法4.1(一般互补约束问题的松弛逐步二次规划算法)步0(初始步)给出初始点(z步1(终止准则)若满足给定的终止条件,则算法停止;否则转步2.步2(确定下降方向及其乘子)从子问题Sub(δ步4(线搜索)确定步长t步5(产生新的迭代点)步6(修正松弛迭代参数)并修正其中的参数步7(修正矩阵并循环)修正Q5关于线性时值的证明本节证明算法4.1的全局收敛性.首先给出如下两个基本假设[4]假设1存在正常数α,γ,对每个k,对称正定矩阵满足不等式假设2存在充分大的下标在算法4.1中,由于对称正定矩阵Q引理5.1在算法4.1的迭代过程中,当d证明为书写方便,记w=(z,λ),并令由函数g,h,L,θ的连续可微性易知,罚函数由于d我们再对(23)式两边同时乘以d而由(24)-(25)及(27),(29)有又从算法4.1步3注意到σ于是,由Q引理5.2在假设1和假设2成立的条件下,设证明由假设2知,乘子序列{μ所以序列{Q从而‖d引理5.3若则证明我们对(23)-(29)同时取极限,因为函数f,h,g,G,H连续可微,所以此时成立.由于函数f,g,h,L,θ的连续可微性,我们可以得到以下引理:引理5.4设则必存在K证明易见,与函数T复合而成.由于函数Y为关于t的凸函数,因此必存在一个向量又由凸分析的知识[14],我们知道序列{η由函数Y的凸性及函数T的连续可微性,我们有引理5.5在假设1和假设2成立的条件下,若证明由算法4.1中步6可知,0<J由算法的迭代过程可知,此时集合{k|‖d利用引理5.2及假设1和假设2,由于序列{Q所以由算法4.1,我们必有否则,设当k>C时,由步5可得设集合因为K否则有此时我们仍取所以由(41),(42),对(43)两边同时取极限,得又由假设(40)知,上式左边为+∞而右边为一个实数,这样我们得出矛盾.所以假设(40)不成立,我们有结论(39).当此时与最初的假设(38)式矛盾.设数列即由引理5.3,引理5.4,我们可找到K由于0<a<1,所以与(38)式矛盾综上,由(44)以及(45)得假设(38)不成立,所以定理5.6在假设1和假设2成立的条件下,令下标集合即以及由Γ的选取易知与引理5.3的证明过程相同,我们