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

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

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