（應用數(shù)學專業(yè)論文）線性二次半定規(guī)劃問題若干研究.pdf

福建師范大學康志林碩士學位論文 記號與約定 尼n ，尺似n ，r + + ：分別表示m 維歐氏空間，n 階實矩陣構成的集合，全體正實數(shù) s ”：禮x 釓階實對稱矩陣空間 s ( n l ，) ：分塊對角矩陣空間且各分塊的維數(shù)為n l i 一， 咒：半正定矩陣錐 k o ：錐k 的極錐 z , j ：矩陣x 上的( i ，j ) 元素 x t ：矩陣x 的轉置 x ，x t ：分別表示矩陣x 的逆矩陣，m o o r e p e n r o s e 廣義逆 x 三o ( x - 0 ) ：矩陣x 是半正定( 正定) 的 x 考， x ：半正定矩陣x 的對稱方根 v e c ( x ) ：死階矩陣x 的列疊成的n 2 維列向量 m a t ：v e c 的逆算子，表示艫維列向量排成n 階矩陣 i | x 怯：矩陣x 肝艦的f r o b e n i u s 范數(shù) e ：舒中的n 維向量，且e = ( 1 ，1 ) t ：鏟中的標準內積 圓：標準k r o n e c k e r 積 t r ( x ) ，r a n k ( x ) ：矩陣x s “的跡，矩陣x 的秩 4 ：s ”到胛上的線性算子，且4 x = 【a i x ，a 。x ra i 為給定對稱陣 a + ：線性算子4 的伴隨算子，且有y = y i a i 厶，：n 階單位矩陣 d i a g ( x 1 ，z n ) ：對角元為x 1 ，的n 階對角矩陣 d i a g ( x ) ：矩陣x 對角元構成的n 維向量 a 。囂( x ) ：矩陣義的最大特征值。 a ( x ) ：矩陣x 實特征值組成的向量即a ( x ) = ( a 1 ，a n ) r c = m a x a ，6 ) ：c 中第i 個分量c i = m a x a i ，執(zhí)】- ，其中a ，b 是肝中禮維向量 a r gm i n f ( z ) ：o x ) ：y ( z ) 在x 上的最小值解集 v ，( z ) ：1 ( 2 7 ) 在點z 的梯度 + 。：正無窮大 i n t s ，r i s ，o s ：分別是集合s 的內部，相對內部和邊界 ：定理或命題證畢，例子求解完畢 v i 福建師范大學學位論文使用授權聲明 本人( 姓名)康志林 學號 至q q 墨魚曼q 專業(yè)應用數(shù)學所呈交的論文( 論文題 目：線性二次半定規(guī)劃問題若干研究) 是我個人在導師指導下 進行的研究工作及取得的研究成果盡我所知，除了文中特別加以標注 和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果 本人了解福建師范大學有關保留、使用學位論文的規(guī)定，即：學校有權 保留送交的學位論文并允許論文被查閱和借閱；學?？梢怨颊撐牡娜?部或部分內容；學?？梢圆捎糜坝?、縮印或其他復制手段保存論文 ( 保密的論文在解密后應遵守此規(guī)定) 學位論文作者簽名婢指導教師簽名一 簽名日期 福建師范大學康志林碩士學位論文 摘要 本文主要探討線性二次半定規(guī)劃問題( l - q s d p ) 的結構特征及其求解算法，主 要由三部分組成第一部分，先討論線性二次半定規(guī)劃問題的對偶性理論及其最優(yōu) 性條件，進而討論該規(guī)劃問題的原始對偶內點算法。給出了基于? 搜索方向唯一 性的證明數(shù)值試驗上，對禮= 3 的情況，給出具體算例，并在m a t l a b7 。0 1 上進 行數(shù)值模擬，驗證了算法的可行性同時，進一步探討了該二次半定規(guī)劃與半定最小 二乘問題的聯(lián)系，給出了在一定條件下它們之間的轉換關系第二部分，拓廣了半定 最小二乘問題模型( s d l s ) 的定義，提出了變量有界半定最小二乘問題( b v - s d l s ) ， 同時給出了任意實對稱矩陣在由有界約束矩陣變量構成的閉凸集上的精確投影表示 式，并在此投影基礎上，探討了該( b v s d l s ) 的求解算法，即投影擬牛頓算法，給 出了其算法框架最后在m a t l a b7 0 1 上進行數(shù)值試驗，并與原始對偶內點算法 比較，進一步說明算法的可行性及有效性第三部分，進一步考慮( b v - s d l s ) 模 型的拓廣形式，探討了一些特殊情形以及施加某種限制下的投影顯式，并考慮它相 應的求解算法 關鍵詞：二次半定規(guī)劃半定最小二乘內點算法 變量有界投影擬牛頓 算法 福建師范大學康志林碩士學位論文 a b s t r a c t i nt h i sp a p e r ，w ed i s c u s st h ef e a t u r ea n ds o l v i n ga l g o r i t h m sf o rt h el i n e a r q u a d r a t i cs e m i - d e f i n i t ep r o g r a m m i n g ( l - q s d p ) t h i sp a p e rm a i n l yc o n s i s t so ft h r e e s e c t i o n s i nt h ef i r s ts e c t i o n ，w ee s t a b l i s ht h ed u a l i t yt h e o r ya n dt h eo p t i m a l i t yc o n d i t i o n s i nt h ep r o b l e mo fl - q s dp a n ds t u d yt h ep r i m a ld u a li n t e r i o rp o i n tm e t h o df o rt h i s p r o b l e m m e a n w h i l e ，w eg i v et h ep r o o fo ft h eu n i q u es o l u t i o nb a s e do nt h en t s e a r d ld i r e c t i o n f u r t h e r m o r e w em a k et h em a t l a bc o d ef o re x p e r i m e n tw h e n t h en u m b e ro fd i m e n s i o nn = 3 ，a n dg i v et h en u m e r i c a ls i m u l a t i o ni nm a t l a b7 0 1 ， w h i c hv e r i f yi t sf e a s i b i l i t y f i n a l l y , w ed i s c u s st h er e l a t i o nb e t w e e nt h eq u a d r a t i c s e m p d e f i n i t ep r o g r a m m i n ga n dt h es e m i - d e f i n i t el e a s ts q u a r e sp r o b l e m ，a n dt h e n p r o v i d et h ec o n v e r s i o nr e l a t i o n s h i pb e t w e e nt h e mu n d e rs o m ec o n d i t i o n s i nt h es e c o n ds e c t i o n ，w ce x t e n dt h ed e f i n i t i o no ft h es e m i d e f i n i t el e a s ts q u a r e s p r o b l e m ( s d l s ) ，a n dp r o p o s et h es e m i d e f i n i t el e a s ts q u a r e sp r o b l e mw i t hb o u n d e d v a r i a b l e s ( b v - s d l s ) a tt h es a j n et i m e ，w eg i v et h ep r o j e c t i o no fs y m m e t r i cm a t r i x o n t ot h ec l o s e dc o n v e xs e t w h i c hi sc o m p o s e do ft h eb o u n d a r yc o n s t r a i n s w e a l s os t u d yt h es o l v i n ga l g o r i t h mf o r ( b v s d l s ) b a s e do nt h i sp r o j e c t i o n ，i e t h e p r o j e c t e dq u a s i n e w t o na l g o r i t h m ，a n dg i v et h ea l g o r i t h mf r a m ef o rt h i sp r o b l e m i n t h ee n d ，w em a k ea ne x p e r i m e n ti nm a t l a b7 0 1 。a n dc o m p a r en u m e r i c a lr e s u l t s w i t ht h a to ft h ep r i m a ld u a li n t e r i o rp o i n tm e t h o d n u m e r i c a lr e s u l t ss h o wt h a tt h e e x t e n d e da p p r o a c hi sf e a s i b l ea n dv a l i d i t y i nt h et h i r ds e c t i o n ，w ef u r t h e rd i s c u s st h ee x t e n s i o no f ( b v - s d l s ) ，a n dp r o p o s e t h ee x p l i c i tp r o j e c t i v ef o r m u l ai nc e r t a i np a r t i c u l a rc i r c u m s t a n c e s 。m o r e o v e r ，w ea l s o s t u d yi t ss o l v i n ga l g o r i t h m k e y w o r d s ：q u a d r a t i cs c m i d e f i n i t ep r o g r a m m i n g ，s e m i - d e f i n i t el e a s ts q u a r e s ， i n t e r i o rp o i n tm e t h o d ，b o u n d e dv a r i a b l e s ，p r o j e c t e dq u a s i - n e w t o na l g o r i t h m 。 i i 福建師范大學康志林碩+ 學位論文 中文文摘 本文主要探討二次半定規(guī)劃問題的特征和求解算法，研究的理論依據(jù)主要是對 稱矩陣論及非線性規(guī)劃的對偶理論文章的結構安排如下 第一章概括了目前國內外關于( 二次) 半定規(guī)劃問題的研究情況和主要成果， 指出( 二次) 半定規(guī)劃數(shù)學模型廣泛的實際應用背景及其重要的理論意義 第二章研究一類特殊的二次半定規(guī)劃問題的結構，其目標函數(shù)中的半正定自伴 隨線性算子q ( x ) = 只x 只，r 三0 ，即 z x r a i s n 。i l x i = 1 只x r + c x s ta x = b x 一o 其中c s n , x s n , 4 x = ( a a x ，a m x ) ，a s ”，且集合 a d i = 1 ，2 ，m ) 中各矩陣元素線性無關同時，討論該線性二次半定規(guī)劃問題的對偶 性理論及其最優(yōu)性條件，在此基礎上。進而考慮該規(guī)劃問題的原始對偶內點算法。 給出了當x 。z 正定時，系統(tǒng) ( 一杰c 蘭 只，h 三ti 。) ( i a 塞a 1 ni 、) 2 ( 囊) ill i 、7 ij p l l 一( 只 只)i - l 砌i i =i ijii m0 八、叱c 口厶，r c 福建師范大學康志林硬士學位論文 與半定最小二乘問題的聯(lián)系及其轉換關系，主要結論是命題2 4 1 ，命題2 4 2 ，命題 2 4 3 第三章中，我們從第二章中二次半定規(guī)劃問題出發(fā)繼續(xù)深入探討特殊的二次 半定規(guī)劃問題( z = 1 ，p = 厶) ，即半定最小二乘問題( s d l s ) ，并在此基礎上，提出 了比( s d l s ) 更一般化的變量有上限約束半定最小二乘問題( b v - s d l s ) x m 秒i n 劃i x c 幅 s ta x ：b( b v s d l s ) 0 墨x 墨8 j n 本章主要工作是，先對半正定矩陣錐趿進一步拓廣，定義一閉凸矩陣集合 q p = f x s n05x5p 厶) ，其中p 0 ，并給出了任意實對稱矩陣c 釅在該 閉凸集護上的精確投影表示式 r 口( g ) = 僻= p c d i a g m a x o ，r a i n f i e ，a ( c ) ) ) ) 露 以及c 到閉凸集q 口的半平方距離( h a l f - s q u a r e dd i s t a n c e ) d n p ( c ) 2 x r a n i n 口1 i x c l l ；- = i 1 ( 執(zhí)一繆) 2 + 礙) t 口a t o 其中凡是實對稱矩陣c 的特征值主要結論有定理3 2 1 0 及其推論3 2 1 l ，推論 3 2 1 2 在上述投影的基礎上，進而探討了變量有界半定最4 - - 乘問題( b v - s d l s ) 的求解算法，即投影擬牛頓算法，并給出了其算法框架。邵算法0 0 1 ( 文中算法3 3 1 ) 算法0 0 1 投影擬牛頓算法 給定初始點y o 艘，初始h e s s i a n 逆近似矩陣風s m ，0 - o 基于該問題的廣泛性，人們就希望能夠通過分析半定規(guī)劃的內部結構，尋求一 種求解s d p 問題的有效算法 1 9 8 4 年，k a r m a r k a r 9 l 提出了求解線性規(guī)劃的多 項式時間內點算法，至此以后的幾年里，內點算法發(fā)展迅速并日趨成熟，同時也為 s d p 的發(fā)展奠定了必要的基礎，1 9 8 8 年，n e s t e r o v 和n e m i r o v s k i i l l o ，l l j 通過引 入自調和函數(shù)( s e l f - c o n c o r d a n tf u n c t i o n ) 提出了用內點算法解決凸規(guī)劃問題的方法 框架。同時說明凸集上線性函數(shù)的最小化。可借助子該集上的自調和障礙函數(shù)在” 多項式時間”內完成特別指出，線性規(guī)劃，含凸二次約束的凸二次規(guī)劃，半定規(guī) 劃都有明確且易于計算的自調和障礙函數(shù)，因此它們都可以在”多項式時間”內完 成由于半定規(guī)劃是線性規(guī)劃的拓展許多學者就考慮將線性規(guī)劃的內點算法推廣 至半定規(guī)劃，1 9 9 2 年，a l i z a d e h 1 2 】直接將求解線性規(guī)劃的多項式時間的內點算法 推廣至半定規(guī)劃，自此以后的十幾年里，諸多學者就一直熱衷于研究半定規(guī)劃問題 的內點算法，包括j a r r e i l 3 】，a l i z a d e h ，h a e b e r l y , a n do v e r t o n i l 4 j ，k o j i m a ，s h i n d o h ，a n d h a r e 1 5 】，n e s t e r o va n dt o d d 1 6 l 等等值得注意的是，半定規(guī)劃的內點算法不同于線 性規(guī)劃，依k k t 系統(tǒng)給出的搜索方向并不能滿足對稱性，故有必要先對k k t 系統(tǒng) 中的互補松弛條件對稱化經(jīng)過幾年的發(fā)展和完善，現(xiàn)今的對稱化方法主要有a h o 方向1 1 4 ，k s h 方向【1 5 】，丁方向1 1 6 1 ，經(jīng)驗表明使用j v 丁方向相比于a h o ，k s h 方 向會更加穩(wěn)健( r o b u s t ) 1 6 j 可以發(fā)現(xiàn)，自上世紀9 0 年代以來的十幾年里，半定規(guī)劃的求解更多的是考慮用 內點算法，但在一定條件下對矩陣變量的維數(shù)死足夠大，約束超過7 0 0 0 個的問題 2 n 妨i i 仉一 一u以( 14 仉 n 、， 11 口 一 ，o r t ， 1 4 第1 章引言 時，內點算法就顯得無能為力了，而在實際工程運用中，經(jīng)常遇到大規(guī)模的問題， 故有效解決大規(guī)模半定規(guī)劃問題已經(jīng)成為迫切需要解決的問題基于此，c h r i s t o p h h e l m b e r g 等1 1 7 1 【7 l 于1 9 9 7 年將削甲面算法用于線性半定規(guī)劃的松弛問題，并得到 了很好的效果至此，割平面算法也成為了求解線性半定規(guī)劃的熱門研究話題，直 至今日，割平面算法主要有三種不同類型的方法：譜叢方法【1 8 1 ，線性規(guī)劃割平面方 法【1 9 1 ，解析中心割平面算法( a c c p m ) 2 0 1 2 0 0 1 年，k a n z o w 和n a g e l 【2 l 】1 2 2 】將擾 動的互補松弛條件等價改寫為非線性映射西：p 釅r + _ s n ：( x ，s ，7 - ) = 0 ， 在此主要討論了兩種西形式，光滑最小化函數(shù)( s m o o t h e dm i n i m u mf u n c t i i o n ) 和 光滑f b 函數(shù)( s m o o t h e df i s c h e r - b u r m e i s t e rf u n c t i o n ) ，并將牛頓型方法應用于非 線性系統(tǒng)，數(shù)值結果顯示這種方法優(yōu)于內點法2 0 0 6 年，j p o v h 等提出了線 性半定規(guī)劃的邊界點算法( b o u n d a r yp o i n tm e t h o d ) ，實際上是將增廣l a g r a n g i a n 罰函數(shù)方法應用于半定規(guī)劃問題，從半定規(guī)劃的最優(yōu)性條件( k k t 系統(tǒng)) 出發(fā)，但 其不同子原始對偶內點算法，在每次的循環(huán)過程中，始終保證每次迭代的原始變量 兒及對偶變量五處于半正定矩陣錐的邊界上，且恒滿足k k t 系統(tǒng)互補松弛條 件當關于原始與對偶線性方程在誤差允許范圍內滿足可行性，該算法最終保證原 始變量虬和對偶變量磊趨于原問題和對偶問題的最優(yōu)解x ，z 半定規(guī)劃的日漸成熟與發(fā)展，為分析和解決工程及其他規(guī)劃問題提供了強有力 工具，比如非凸二次約束的二次規(guī)劃問題、整數(shù)規(guī)劃問題對于非凸二次約束的二 次規(guī)劃問題： i n f z 丁q o z 營 s t x t a z = bv i i n f q o x x t z s t q t z z t = qv i 通過適當?shù)奶鎿Q( 令z z 7 = y ) ，可以很容易得到如下s d p 松弛問題 西y s t q i y = qv i y 三0 從而可獲得原問題的一個界值估計 我們知道，大部分整數(shù)規(guī)劃都是n p 一完全或者n p 難問題，很難找到多項式 時間算法求解，目前解決整數(shù)規(guī)劃( i p ) 的通用方法主要有：分支定界法，割平面方 法，動態(tài)規(guī)劃方法當然，在利用這些通用算法求解時，并不是僅僅孤立地使用， 為了得到更好的效果，經(jīng)常是將這些方法或者與其他方法結合起來在求解整數(shù)規(guī) 劃過程中經(jīng)常涉及到最優(yōu)解的定界問題，可以通過求解s d p 松弛問題【2 4 】來獲得 3 福建師范大學康志林碩士學位論文 原問題最優(yōu)解的一個界值估計當原始問題不好求解時，經(jīng)常借助對偶問題來分析 原問題。甚至可通過對偶問題獲得原問題的解比如，二次( 一1 , 1 ) 整數(shù)規(guī)劃問題 r a i n 互1 z t 啦+ c t z x e - 1 ，1 n 。 其中q 鏟，c 儼令人驚奇的是，其對偶問題最終可變?yōu)槿缦潞唵蔚木€性半定 規(guī)劃問題： ( a ，1 ) p + 1 st(q+2dtin夕a2rcc2 一e t a ) 三。 、 1 z 7 - 一 1a ， 2 0 世紀9 0 年代考慮的s d p 都是線性半定規(guī)劃問題( l - s d p ) ，即目標函數(shù)是線 性的，隨著研究的深入，人們自然而然地要考慮非線性半定規(guī)劃問題，而線性二次 半定規(guī)劃( l i n e a r - q u a d r a t i cs e m i - d e f i n i t ep r o g r a m m i n g ，簡記為。l - q s d p ) 是二 次規(guī)劃的推廣，同時也是最簡單的一種非線性半定規(guī)劃，而且它在控制論中也有比 較強的應用背景，因此探討二次半定規(guī)劃問題的結構及求解算法就顯得很有必要也 很有意義在此之前，先給出二次半定規(guī)劃一般模型【2 5 】： r a i n x q ( x ) + c x x 6 s z 7 s ta x ：b( q s d p ) x 蘭0 其中，q 是鏟到鏟的半正定自伴隨算子( s e l f - a d j o i n tp o s i t i v es e m i d e f i n i t e o p e r a t o r ) ，即對任意4 ，b 釅，有 q ( a ) b = a q ( b ) ，q ( a ) a 0 進一步地，若算子q ( x ) 關于x 是線性的，則二次半定規(guī)劃( q s d p ) 即為線性二 次半定規(guī)劃( l - q s d p ) 顯然，對( q s d p ) ，若不存在二次項，則( q s d p ) 即為線性 半定規(guī)劃問題( l - s d p ) g u a n 2 5 】考慮了如下二次半定規(guī)劃s x m i s n 。 ；u e c t ( x ) 少丁歲u e c ( x ) 一礦夕t ，e c ( x ) + c x s ta x = b x 三0 其中夕= ( v e c r f l ，v e c r f , ) t 彤礦，只( i = 1 ，s ) 均為n 階實對稱矩陣 g u s r t 將此二次半定規(guī)劃問題的最優(yōu)性條件等價轉化為線性變分不等式，將用于求 4 第1 章引言 解單調線性變分不等式的投影收縮算法( p c 算法) ，應用到該二次半定規(guī)劃問題中 來，但是該算法解決的仍只是一些小規(guī)模問題，當( q s d p ) 的規(guī)模比較大時，p c 算法收效甚微基于此，x u l 2 6 1 在文獻【1 6 】基礎上將求解線性半定規(guī)劃的原始對偶 內點算法推廣至文獻【2 5 】中討論的二次半定規(guī)劃，給出了短步長路徑跟蹤算法，數(shù) 值試驗結果也表明基于n t 方向的內點算法優(yōu)于p c 算法除此之外，k c t o h 等 【2 7 】進一步探討了一般二次半定規(guī)劃的不精確原始對偶內點算法 半定最小二乘問題是一類特殊的二次半定規(guī)劃問題，其標準形式如下： 娜m i n 。 1 1 x c 幢 s t 似= b x 三0 容易發(fā)現(xiàn)，該規(guī)劃是嚴格凸規(guī)劃問題，且目標函數(shù)具有平方和這種特殊形式，從而 給問題的求解帶來了某種方便，對于該問題，除了能夠運用一般求解方法( 原始對 偶內點算法) 外，還可以考慮其他一些更為簡便有效算法2 0 0 2 年，h i g h 鋤【2 8 1 考慮了約柬仿射算子為對角算子( 4 = 出叼) 半定最小二乘問題的求解算法，即校 正交錯投影算法。該算法在原來交錯投影運算的基礎上引入d y k s t r a 校正步例，然 后交錯投影到由約束集構成的閉凸集合上，最終保證算法收斂到全局最優(yōu)點有關 交錯投影算法的描述，可進一步查閱文獻 3 0 】。在半定矩陣錐投影算子b 竺1 3 , 】的基 礎上，2 0 0 5 年，m a l i c k j 1 3 2 1 只對仿射約束求l a g r a n g i a n 對偶，提出了該問胚的 部分對偶方法，并利用對稱錐的m o r e a u 分解定理將對偶問題改寫為目標函數(shù)如下 相對簡化的無約束優(yōu)化問題 7 7 ( ! ，) = - d ( s 7 ) 。( c + a y ) + i l c i | 芻+ y r b = 一；1 1p s 7 ( c + 4 ) j i 齋+ 1 1 c l l ；, 4 - y t b 這種方法可以有效地解決中等規(guī)模的( s d l s ) 問題b o y ds ，l i nx i a o l 刪在【3 2 】 的基礎上進一步考慮了含不等式約束的二次半定規(guī)劃問題，稱之為協(xié)方差矩陣校正 問題( l s c a p ) ： 心m i n 。；l l x c 幅 s t4 x = b 紡x 冬d x 三0 其中留x = ( 局x ，昂x ) t ，d r p 易知( l s c a p ) 也是凸二次半定規(guī)劃問 題，若不考慮約束中不等式，則( l s c a p ) 即為半定最小二乘問題對于此問題，當 5 福建師范大學康志林碩士學位論文 變量個數(shù)小于1 0 0 0 ，即對應于n = 4 5 情況，可以由內點算法【1 6 j 得到有效的解決 b o y ds 從問題本身出發(fā)，經(jīng)過化簡，得到不含矩陣變量的有約束對偶問題其約束 變量個數(shù)為不等式約束的個數(shù)，并給出了( l s c a p ) 的對偶投影次梯度算法，同時 討論了步長選取的條件及算法收斂性問題之后，h o u d u oq i 等f 3 4 l 進一步考慮了 約束仿射算子為對角算子的半定最小二乘問題。通過對偶性理論將規(guī)劃問題轉化為 求解關于半正定錐投影算子的非光滑方程 f ( y ) ：= 4 ( c + a y ) + = b 其中耳定義為c 到半正定矩陣錐毋上的尺度投影同時，作者利用非光滑牛頓 法f 3 5 1 求解該方程，并由半正定錐投影算子的強半光滑性例吲，證明了當初始迭代 點充分靠近最優(yōu)點時，非光滑牛頓法的二次收斂性 2 0 0 7 年，i g o rg r u b i s i c 等f 3 8 j 進一步強化了仿射和半正定約束，考慮低秩 ( 1 0 w - r a n k ) 矩陣校正問題，即在約束中增加一個秩的約束 挪m i n 。釧x 一哪 s t r a n k ( x ) d 咒 = b i ，i = 1 ，n x 三0 其中d 1 ，n ) ，目標函數(shù)中的| | i i 是定義在伊上的哈達瑪半范數(shù)( h a d a m a r d s e m i n o r m ) ，i e ， 勃x e l l 2 = 去w t j ( x o 一) 2 - i 一o ) ，矩 陣的半正定約束雖然是非線性非光滑的，但也是凸的，故該二次半定規(guī)劃為凸( 嚴 格凸) 二次優(yōu)化問題 若取矩陣變量x = d i a g ( x l ，t 2 ，) ，令= v e c ( x ) ，則x 三0 營v e c ( x ) o 故二次半定規(guī)劃就等價于如下二次規(guī)劃問題： 譬m ：i n i 5yt纛tpi：pi，)y：+1v，ec(c，)tyvec(ayb ii m t ，、z z ， s t ) t = ，= 1 ， ， 在討論該規(guī)劃的對偶性及最優(yōu)性條件之前，先給出以下幾個有用的引理； 9 福建師范大學康志林碩士學位論文 引理2 1 1 【6 】設a ，b s ”，若a 蘭0 ，b 三0 ，則a b 0 ，且a b = 0 當且僅當a 口= 0 引理2 1 2 【6 】設b 是億n 階非奇異矩陣，則a 卑當且僅當b r a b 卑j a 卑+ 當且僅當b t a b 肆+ 弓l 理2 1 3 若只= 掣，圣= l ， 則竺掣= 圭只x 最， 證明：由 4 1 】，o ( t 7 ( x 獄a x b ) ) - = ( a x b + b x a ) t ，則 a ( 小ep i x p da ( 扣( x 夏p , x p d ) 荀卜2 靜一 a ( 打( x p x p d ) 一勱f 一 8 ( r ( x p t x p d ) 一互刁又一 = j ( 戶；x 只+ 只x 只) r2 厶、。1 7 l 4i 。、ol ， f = 只x 只 引入拉格朗日乘子a ，z 辯，則二次半定規(guī)劃問題的拉格朗日函數(shù)為t l ( x ，入，z ) = 去x 只x 只+ c x 一氣( a x - h i ) 一x z ， 。 i = ii = l 由引理2 1 3 可求得函數(shù)l 關于變量x 的偏導數(shù)，并令其為0 ，則有： 裝= 妻只x 只+ c 一喜砌t z = 。，z 三。 利用凸規(guī)劃的對偶理論，可得原二次半定規(guī)劃的對偶規(guī)劃： l，孔 m a ，a z x i x - i = i 蹦a + 洶e 九玩 fm s t 只x 只+ c 一九a z = 0 t = 1i = 1 么三0 1 0 - ( 2 3 ) 第2 章二次半定規(guī)劃f u i 題及其內點算法 顯然，原二次半定規(guī)劃( 2 1 ) 的對偶規(guī)劃也是二次半定規(guī)劃，目標函數(shù)是拉格 朗日函數(shù)在可行域上的簡化當然，在一定條件下，可以把對偶規(guī)劃改寫為只含對 偶變量入，z 的規(guī)劃形式。在此，我們考慮一般情況，即只0 0 = l ，f ) 的情 形，而r o ( i = l ，z ) 是顯然的 引理2 1 4 4 1 jp j 若矩陣q ( i = 1 ，z ) 相互正交，即q q = o c i j ) ，則 ( q 1 + q 2 + q f ) = q + q ；+ + q ；， 例對于任意n 階矩陣q ，r ，有( q 固r ) t = q r t ，( q + ) t = ( q t ) 引理2 1 5 若矩陣掣= 只( i = 1 ，c ) ，則只與弓“j ) 正交當且僅當 只。只與弓 另正交 證明：若只與b 正交，即r 弓= 0 ，則 ( eo 只) ? ( p jpp j ) = ( rqp , ) c 5 弓) = 只弓9r b = 0 反之，若只。只與毋9 另正交，則只弓 p , p j = ( 只p 只) ( b b ) = ( r 只) t ( b p j ) = 0 ，故推得只弓= 0 ， 1 l 假定關于x 的矩陣方程( 2 4 ) 是有解的，用釕e c 算子作用，有( 只o p d v e c ( x ) = l i = l t ，e c ( 印，則取其一特殊解：v e c ( x ) = ( 只。只) u e c ( s ) 因此，當二次半定規(guī)劃 t = 1 ( 2 1 ) e e l _ 陣只與b 正交，即只局= 0 時，由引理2 1 4 ，引理2 1 5 ，易發(fā)現(xiàn)其對 偶目標甬數(shù)也具有二次半定規(guī)劃( 2 ，t ) 的表達形式事實上，對偶規(guī)劃( 2 3 ) 的目 qp c ，) 壘一g a m 洶 + z= r x r ，僦 記現(xiàn) 福建師范大學康志林碩士學位論文 標函數(shù)可進一步改寫為： - x 只xr + 人墳 i = li = l fm = 一； e c ( x ) r ( 只 只) v e c ( x ) + 凡甌 ：一；可e c ( s ) r ( 圭只 只) ( 圭只 r ) ( 圭只。r ) t u e c ( s ) + 曼八機 1 虧1 。1 m 。l 2 1 = 一；可e c ( s ) r ( 只。只) e c ( s ) + 妻a i b i = 一；u e c ( s ) r ( 只。只) 口e c ( 印+ 九機 一 m = 一；可e c ( s ) ? ( 辟固磷) c ( s ) + 玟 仃l = 一j u e c ( s ) t ? j e c ( 日s 辟) + 九兢 tn i = li = 1 m = 一；s 辟s 爿+ a 兢 因而，當二次半定規(guī)劃( 2 1 ) 中矩陣只與b 正交，即j f ：弓= 0 時，其對偶規(guī)劃具 有與原規(guī)劃異常對稱的表示式： m 程一抄i = 1 曩s 牟+ i = 1 沁魂 ( 2 5 ) ，o l z 6j s t a ，z 三0 其中s = z + 八4 f c ，曩是矩陣只的m o r r e p e n r o s e 廣義逆 = l 設原始問題的目標函數(shù)為f ( x ) ，對偶問題的目標函數(shù)為叮( a ，z ) = m x i n l ( x ，a ，z ) ， 原問題的可行域為口= f x 鏟i4 l x = 仇0 = l ，m ) ，x 藝o ) 由凸規(guī)劃的 對偶性理論，我們有如下弱對偶定理： 命題2 1 6 設x 為二次半定規(guī)劃原問題的可行解，a ，z 為對偶問題的 - t 4 r 解，則 s u 。pq ( a ，z ) i n y ff ( x ) a z 證明；設y 為原問題的可行解。 x ，a ，z 為對偶問題的可行解f ( x ) = f ；x 只x 只+ c x 為凸函數(shù)，由凸性可知，擬，y 刃，有f ( y ) f ( x ) + i = 1 l v f ( x ) ( y x ) ，其中v f ( x ) = 只x b + c 因為x ，入，z 為對偶問題的可行 ：1 1 2 第2 章二次半定規(guī)劃問題及其內點算法 解，所以v x l ( x ，a ，z ) = v 尸( x ) 一a i a i z ，z 蘭0 i = l f ( y ) 之f ( x ) 十( e 丸a 一z ) ( y x ) 害1仇 = r ( x ) + ea i ( a i y ) + z y 一a i ( a i x ) 一x z = 1t = l m f ( x ) 一a i ( a i x b i ) 一x z = l ( x ，a ，z ) l = 1 故g ( a ，z ) = i n 、，fl ( x ，a ，z ) f ( x ) ，進而q = s u pg ( a ，z ) i n ff ( x ) _ a z “ 命題2 1 7 設一x ，滅，一z 滿足二次半定規(guī)劃( 2 1 ) 的k k t 條件( 2 6 ) ，則叉和 ( 天，z ) 是原問題與對偶問題的最優(yōu)解，且具有零對偶間隙 證明：由已知叉，頁，z 滿足二次半定規(guī)劃( 2 1 ) 的k k t 條件，故又是原始可 行的又l ( x ，- ，一z ) 關于x 是凸函數(shù)，由k k 丁條件的第二式知，l ( x ，天，芴在 叉處的梯度為0 ，即v x l ( - z ，頁，z ) = 0 ，也即l ( x ，頁，一z ) 在叉處取得最小值，因而 有 口( 天，- z ) = l ( 一x ，頁，勱 = 尸( 叉) 故叉與( 天，z ) 具有零對偶間隙再由命題2 1 6 知，又是原始最優(yōu)解，( 天，z ) 是對 偶最優(yōu)解 注2 1 1 命題2 j 7 給出了二次半定規(guī)劃的最優(yōu)性條件，為我們用原始對偶內 點算法解決此二次半定規(guī)劃問題( 2 1 ) 提供了理論依據(jù) 2 2 原始對偶路徑跟蹤算法 眾所周知，在對優(yōu)化問題( 特別是凸規(guī)劃問題) 進行求解時，經(jīng)常從該問題的最 優(yōu)性條件出發(fā)，去求關于最優(yōu)性條件的非線性方