celis-dens-apia子問題的最優(yōu)解

celis-dens-apia子問題的最優(yōu)解

1總結(jié)celis-dense（cdt）問題的形式如下。其中B∈R由于在多個橢球的交集上最小化一個二次函數(shù)有許多潛在的應(yīng)用2cdt子問題的半正當(dāng)性從文獻(xiàn)下面的定理說明當(dāng)Lagrange乘子不唯一時,全局解處的Lagrange乘子包含在如下集合里:證如果CDT子問題全局解d用反證法,如果(6)式不成立,則ω<0.設(shè)(λ正定,則d的解,(-tω,t)(t∈[0,+∞))都是其相應(yīng)的Lagrange乘子,這與文獻(xiàn)當(dāng)全局解處Hesse矩陣(4)式是半正定時,CDT子問題是容易求解的.本文主要考慮CDT子問題(1)～(3)不存在使Hesse矩陣半正定的全局解的情形.從定理1知道在這種情形Lagrange乘子唯一,即相應(yīng)的d假設(shè)1假設(shè)(da)db)相應(yīng)的Lagrange乘子(λc)Lagrange函數(shù)的Hesse矩陣有1個負(fù)特征值且非奇異.d)d本文中,我們用‖·‖表示2-范數(shù),上標(biāo)“*”表示與d3局部最優(yōu)性條件本節(jié)研究滿足假設(shè)1的CDT子問題的二次最優(yōu)性條件的性質(zhì),并給出局部最優(yōu)性條件.3.1cdt子問題的最優(yōu)性條件考慮問題(1)～(3)的最優(yōu)性條件.首先,回憶集合其中F是文獻(xiàn)這兩個集合在約束優(yōu)化的二次最優(yōu)性條件里起著很重要的作用.對于CDT子問題,這兩個集合有特殊的性質(zhì),定理2假設(shè)(d證由假設(shè)1,對于CDT子問題(1)～(3),G顯然G對充分小的τ,考慮如下方程組F(τ,v)=0:直接計算可得顯然,矩陣J另一方面,由(8)式可得其中v故u由定理2,可得如下推論:推論1若假設(shè)1成立,則有(i)如果d(ii)如果d*是問題(1)～(3)的一個局部最小解,則d推論1告訴我們,如果假設(shè)1成立,則對于CDT子問題,有可能找到一個更為簡單的最優(yōu)性條件.3.2cdt子問題的最優(yōu)設(shè)計由3.1小節(jié)我們知道,對CDT子問題滿足假設(shè)1的KKT點(diǎn),其二次最優(yōu)性條件歸結(jié)為對應(yīng)的Hesse矩陣H在一個(n-2)維子空間G引理1假設(shè)H∈R引理1的結(jié)論是顯然的,在此省略證明.定理3假設(shè)矩陣H的譜分解為H=QDQ是正交矩陣,對角矩陣D=diag(λ證若v因此可假設(shè)v由此可知d另一方面,因為d和y線性獨(dú)立,不失一般性,假設(shè)下面式子成立:定義W∈R其中即直接計算可得進(jìn)一步,有rank(W)=n-2及對稱.通過計算可得這里簡單計算可以得到矩陣H推論2假設(shè)定理3條件成立,則H在子空間L=span{推論2的證明與定理3相似,在此省略.由此可得本節(jié)的主要結(jié)論:定理4(i)如果假設(shè)1成立,則d(ii)如果假設(shè)1成立,且則d證(i)根據(jù)CDT子問題的二次必要條件,有其中S因此結(jié)論是定理3的直接結(jié)果.(ii)可由二次充分條件得到.若成立,則H在子空間L=span{d定理4的必要條件和文獻(xiàn)[2]的定理2相似,但本文的充分條件與之不同.與之相比,本文的充分和必要條件沒有間隙,這是進(jìn)一步研究的基礎(chǔ).矩陣的Hesse矩陣,其中我們的結(jié)果說明,如果在CDT子問題的一個局部最優(yōu)解處Hesse矩陣H(λ,μ)有1個負(fù)特征值,則對偶函數(shù)在相應(yīng)的Lagrange乘子處既不是凸的,也不是凹的.換句話說,如果Lagrange函數(shù)的Hesse矩陣有1個負(fù)特征值,則相應(yīng)的Lagrange乘子是對偶函數(shù)的一個鞍點(diǎn).4cdt子空間在ls-pcr中的假設(shè)當(dāng)為cdt本節(jié)研究Hesse矩陣有1個負(fù)特征值的KKT點(diǎn),判斷它是否是CDT子問題的一個局部最優(yōu)解.引理2如果矩陣H只有1個負(fù)特征值,則H不可能在一個二維子空間上負(fù)定.證用反證法.假設(shè)存在一個二維子空間L=span{v根據(jù)矩陣的極小極大定理知其中λ利用引理2,我們可以得到下面的結(jié)果:引理3如果證因為其中又由已知可得進(jìn)一步,可以證明如下結(jié)論:引理4假設(shè)證反證法,假設(shè)在KKT點(diǎn)不失一般性,假設(shè)(λ把和分別加到不等式(13)的兩邊,化簡可得其中由于CDT子問題的可行域F是凸集,所以因此(14)和(15)式與由上面的引理,可以給出本節(jié)的主要結(jié)果:定理5如果證根據(jù)引理3和4,對偶函數(shù)的Hesse矩陣既不正定也不負(fù)定,因此由定理4可知5cdt子問題全局解的最優(yōu)性條件本文考慮了CDT子問題的Lagrange乘子,證明了當(dāng)CDT子問題不存在相應(yīng)Hesse矩陣半正定的全局解時,對應(yīng)的乘子必定唯一.其次,應(yīng)用一般約束優(yōu)化的二次最優(yōu)性條件,給出了CDT子問題沒有間隙的二次最優(yōu)性條件;并證明所有滿足Hesse矩陣有1個負(fù)特征值的可行KKT點(diǎn),都是CDT子問題的局部最優(yōu)解.然而,我們?nèi)匀晃茨芙o出這種情形下CDT子問題全局解的最優(yōu)性條件,這將是進(jìn)一步研究的方向.致謝本文的初稿是作者在中國科學(xué)院計算數(shù)學(xué)與科學(xué)工程計算研究所攻讀博士學(xué)位期間完成的,作者感謝導(dǎo)師袁亞湘研究員不斷的幫助和許多有建設(shè)性的建議.至多有1個負(fù)特征值.另一方面袁亞湘總是包含全局解處的Lagrange乘子,這說明當(dāng)Lagrange乘子不