celis-dens-apia子问题的最优解

celis-dens-apia子问题的最优解

1总结celis-dense（cdt）问题的形式如下。其中B∈R由于在多个椭球的交集上最小化一个二次函数有许多潜在的应用2cdt子问题的半正当性从文献下面的定理说明当Lagrange乘子不唯一时,全局解处的Lagrange乘子包含在如下集合里:证如果CDT子问题全局解d用反证法,如果(6)式不成立,则ω<0.设(λ正定,则d的解,(-tω,t)(t∈[0,+∞))都是其相应的Lagrange乘子,这与文献当全局解处Hesse矩阵(4)式是半正定时,CDT子问题是容易求解的.本文主要考虑CDT子问题(1)～(3)不存在使Hesse矩阵半正定的全局解的情形.从定理1知道在这种情形Lagrange乘子唯一,即相应的d假设1假设(da)db)相应的Lagrange乘子(λc)Lagrange函数的Hesse矩阵有1个负特征值且非奇异.d)d本文中,我们用‖·‖表示2-范数,上标“*”表示与d3局部最优性条件本节研究满足假设1的CDT子问题的二次最优性条件的性质,并给出局部最优性条件.3.1cdt子问题的最优性条件考虑问题(1)～(3)的最优性条件.首先,回忆集合其中F是文献这两个集合在约束优化的二次最优性条件里起着很重要的作用.对于CDT子问题,这两个集合有特殊的性质,定理2假设(d证由假设1,对于CDT子问题(1)～(3),G显然G对充分小的τ,考虑如下方程组F(τ,v)=0:直接计算可得显然,矩阵J另一方面,由(8)式可得其中v故u由定理2,可得如下推论:推论1若假设1成立,则有(i)如果d(ii)如果d*是问题(1)～(3)的一个局部最小解,则d推论1告诉我们,如果假设1成立,则对于CDT子问题,有可能找到一个更为简单的最优性条件.3.2cdt子问题的最优设计由3.1小节我们知道,对CDT子问题满足假设1的KKT点,其二次最优性条件归结为对应的Hesse矩阵H在一个(n-2)维子空间G引理1假设H∈R引理1的结论是显然的,在此省略证明.定理3假设矩阵H的谱分解为H=QDQ是正交矩阵,对角矩阵D=diag(λ证若v因此可假设v由此可知d另一方面,因为d和y线性独立,不失一般性,假设下面式子成立:定义W∈R其中即直接计算可得进一步,有rank(W)=n-2及对称.通过计算可得这里简单计算可以得到矩阵H推论2假设定理3条件成立,则H在子空间L=span{推论2的证明与定理3相似,在此省略.由此可得本节的主要结论:定理4(i)如果假设1成立,则d(ii)如果假设1成立,且则d证(i)根据CDT子问题的二次必要条件,有其中S因此结论是定理3的直接结果.(ii)可由二次充分条件得到.若成立,则H在子空间L=span{d定理4的必要条件和文献[2]的定理2相似,但本文的充分条件与之不同.与之相比,本文的充分和必要条件没有间隙,这是进一步研究的基础.矩阵的Hesse矩阵,其中我们的结果说明,如果在CDT子问题的一个局部最优解处Hesse矩阵H(λ,μ)有1个负特征值,则对偶函数在相应的Lagrange乘子处既不是凸的,也不是凹的.换句话说,如果Lagrange函数的Hesse矩阵有1个负特征值,则相应的Lagrange乘子是对偶函数的一个鞍点.4cdt子空间在ls-pcr中的假设当为cdt本节研究Hesse矩阵有1个负特征值的KKT点,判断它是否是CDT子问题的一个局部最优解.引理2如果矩阵H只有1个负特征值,则H不可能在一个二维子空间上负定.证用反证法.假设存在一个二维子空间L=span{v根据矩阵的极小极大定理知其中λ利用引理2,我们可以得到下面的结果:引理3如果证因为其中又由已知可得进一步,可以证明如下结论:引理4假设证反证法,假设在KKT点不失一般性,假设(λ把和分别加到不等式(13)的两边,化简可得其中由于CDT子问题的可行域F是凸集,所以因此(14)和(15)式与由上面的引理,可以给出本节的主要结果:定理5如果证根据引理3和4,对偶函数的Hesse矩阵既不正定也不负定,因此由定理4可知5cdt子问题全局解的最优性条件本文考虑了CDT子问题的Lagrange乘子,证明了当CDT子问题不存在相应Hesse矩阵半正定的全局解时,对应的乘子必定唯一.其次,应用一般约束优化的二次最优性条件,给出了CDT子问题没有间隙的二次最优性条件;并证明所有满足Hesse矩阵有1个负特征值的可行KKT点,都是CDT子问题的局部最优解.然而,我们仍然未能给出这种情形下CDT子问题全局解的最优性条件,这将是进一步研究的方向.致谢本文的初稿是作者在中国科学院计算数学与科学工程计算研究所攻读博士学位期间完成的,作者感谢导师袁亚湘研究员不断的帮助和许多有建设性的建议.至多有1个负特征值.另一方面袁亚湘总是包含全局解处的Lagrange乘子,这说明当Lagrange乘子不