（應用數學專業(yè)論文）求解約束優(yōu)化問題的序列二次規(guī)劃方法研究.pdf

求解約束優(yōu)化問題的序列二次規(guī)劃方法研究 摘要 本文研究非線性約束優(yōu)化問題的求解 我們提出幾種序列二次規(guī)劃 s q p 算 法 建立相應算法的收斂性 并對所給算法進行數值實驗 第2 章結合積極集估計技術 提出一個求解非線性約束優(yōu)化問題的積極集 s q p 算法 且該算法所產生的點列均為可行點列 該算法的主要優(yōu)點在于 算法 的主搜索方向由一個低維的凸二次規(guī)劃確定 為克服m a r a t o s 效應 我們通過求 解一個低維的最小二乘問題得到高階修正方向 在適當的條件下 我們證明算法 具有全局收斂性和超線性收斂性 第3 章提出一個求解極大極小問題修正的s q p 算法 該算法的主搜索方向 通過求解一個二次規(guī)劃得到 為克服m a r a t o s 效應 不同于以往的方法 我們通 過求解一個線性方程組得到高階修正方向 無需求解二次規(guī)劃子問題 在較弱的 條件下 我們證明該算法是全局收斂和一步超線性收斂的 第4 章提出一個求解非線性約束優(yōu)化問題的可行點s q p 算法 在該算法的每 一個迭代步 分別通過求解一個低維的二次規(guī)劃子問題和一個低維的線性方程組 得到一個下降方向和一個可行方向 在此基礎上 我們構造一個可行下降方向 為避免m a r a t 0 8 效應 我們通過解一個低維的線性方程組得到高階修正方向 在 適當的條件下 該算法被證明是全局收斂和超線性收斂的 與已有算法相比 本章 提出的算法的優(yōu)點是 算法中線性方程組不涉及乘子估計 所求解的兩個線性方 程組的系數矩陣相同且比已有算法中系數矩陣的結構簡單 因而可減少計算量 第5 章提出一個求解非線性不等式約束優(yōu)化問題的非內點型可行點q p f r e e 算法 這個算法不要求迭代點必須是可行域的內點 在算法的每一個迭代步 為 得到搜索方向 只需求解四個系戮擔回的線性方程組 在適當的條件下 我們建 立該算法的全局收斂性和超線性收斂 e 理 第6 章提出一個內點型可行點q p f r e e 算法 在該算法的每一個迭代步 為 得到搜索方向 只需求解三個系數矩陣相同的線性方程組 而且在無嚴格互補條 件下得到系數矩陣的一致非奇異性和近似乘子序列的有界性 且其全局收斂性分 析不受穩(wěn)定點數目有限的限制 關鍵詞 非線性約束優(yōu)化 極大極小問題 s q p 算法 q p f r e e 算法 全局收斂 性 超線性收斂性 博士學位論文 a b s tr a c t t h ep u r p o s eo ft h et h e s i si st os t u d yt h en u m e r i c a lm e t h o df b rs o l v i n gn o n l i n e a rc o n s t r a i n e do p 七i m i z a t i o n w bp r o p o s es e v e r a ls e q u e n t i a lq u a d r a t i cp r o g r a m m i n g s q p a l g o r i t h i i l s a n de s t a b l i s ht h e i rg l o b a lc o n v e r g e n c ea n ds u p e r l i n e a r c o n v e r g e n c e w bd on u m e r i c a le x p e r i m e n 七st o 七e s tt h ep r o p o s e da l g o r i t h m s i nc h a p t e r2 b yt h eu s eo fa na c t i v es e te s t 婦a t et e c h n i q u e w ep r o p o s ea n a c t i v es e ts q pm e t h o df o rn o i l l i n e a rc o i l s t r a i n e do p t i m i z a t i o n t h em e t h o dg e n e r a t e sas e q u e n e eo ff e a s i b l ep o i n t s m a j o ra d v a n t a g eo ft h ep r o p o s e dm e t h o dl i e s i nt h a tt h em a i ns e a r c hd i r e c t i o ni sd e t e r m i n e db yal o w e rd i m e n s i o nq u a d r a t i c p r o g r a m s t bo v 盯c o m em a r a t o se 丘 e c t w ec a l c u l a t eah i g h e r o r d e rc o r r e c t i o nd i r e c t i o nb ys o l v i n gar e d u c e d1 e a s ts q u a r e 8p r o b l e m u n d e r 印p r o p r i a t ec o n d i t i o 璐 w es h o wt h a tt h ep r o p o s e dm e t h o di sg l o b a l l ya n ds u p e r l i n e a r l yc o n v e r g e n t i nc h a p t e r3 w ep r e s e n tam o d i f i e ds q pm e t h o df o rt h em i n i m a xp r o b l e m i nt h ea l g o r i t h m t h em a i ns e a r c hd i r e c t i o ni so b t a i n e db ys o l v i n gaq u a d r a t i c p r o g r a mw h i c ha l w a y sh a sas o l u t i o n i no r d e rt oa v o i dm a r a t o se 乳c t d i r e n t f r o mt h ep r e v i o u st e c h n i q u ew h e r eaq u a d r a t i cp r o g r a m si s8 0 l v e d es o l v ea s y s t e mo fl i n e a re q u a t i o n st oo b t 如ah i 曲e r o r d e rc o r r e c t i o n d i r e c t i o n u n d e r s o m em i l dc o n d i t i o 璐 w eo b t a i nt h e9 1 0 b a la n ds u p e r l i n e 盯c o n v e r g e n c e i nc h a p t e r4 w eh a v ep r o p o s e daf e a s i b l ep o i n ts q pa k o r i t h mf o rn o n l i n e a r i n e q u a l i t yc o i l s t r a i n e do p t i m i z a t i o np r o b l e m s a te a c hi t e r a t i o n w ed e t e r m i n e da d e s c e n ta n df e a u s i b l ed i r e c t i o nb ys o l v i n gar e d u c e dq u a d r a t i cp r o g r a m m i n gs u b p r o b l e ma n dar e d u c e ds y s t e mo fh n e a re q u a t i o n s r e s p e c t i v e l y w et h e nd e v i c ea f e a s i b l ed e f 弓c e n td i r e c t i o nt h r o u g has u i t a b l ec o m b i n a t i o no ft h ed e s c e n td i r e c t i o n a n dt h ef e a s i b l ed i r e c t i o n t do v e r c o m em a u r a t o se 能c t ah i 曲e r o r d e rc o r r e c t i o n d i r e c t i 伽i so b t a i n e db ys o l v i n ga n o t h e rr e d u c e ds y s t e mo fl i n e a re q u a t i o n s t h e a l g o r i t h mi sp r c i v e dt ob eg l o b a l l ya n ds u p e r l i n e a r l yc o n v e r g e n tu n d e rs o m em i l d c o n d i t i o n s ag o o df e a t u r eo ft h ep r o p o s e da l g o r i t h mi st h a tt h ec o e 最c i e n tm a t r i x f o rt h es v s t e mo f 1 i n e a re q u a t i o n sd on o ti n v o l v em u l t i p l i e re s t i m a t e f u r t h e r m o r e t h es t r u c t u r eo fc o e f i i c i e n tm a t r b i ss i m p l e rt h a nt h eo n ei nt h ep r e v i o u s a l g o r i t h m s i nc h a p t e r5 w ep r o p o s ean o n i n t e r i o rt y p ef e a s i b l ep o i n tq p f r e ea l g o r i t h m f o rn 1 1 l i l l e a ri n e q u a l i t yc o n s t r a i n e do p t i m i z a t i o np r o b l e m s t h eg e n e r a t e di t e r a t e sa r ef e a s i b l eb u tn o tn e c e s s a r yi n t e r i o rp o i n 七so ft h ef e a s i b l er e g i o n l te a c h i t e r a c i o n as e a r c hd i r e c t i o ni so b t a i n e db ys o l v i n gf b u rs y s t e m so fl i n e a re q u a 廣 i i i 求解約束優(yōu)化問題的序列二次規(guī)劃方法研究 t i o i l sw i t ht h es a m ec o e m c i e n tm a t r i x t h ea l g o r i t h mi sp r o v e dt ob eg l o b a l l ya n d s u p e r l i n e a r l yc o n v e r g e n tu n d e rs o m em i l dc o n d i t i o n s i nc h a p t e r6 w ep r o p o s ea ni n t e r i o rp o i n tt y p ef e a s i b l eq p f r e ea l g o r i t h m f o rn o n l i n e a ri n e q u a l i t yc o n s t r a i n e do p t i m i z a t i o np r o b l e m s a te a c hi t e r a t i o n b y s o l v i i l gt l l i e es y s t e m so fl i n e a re q u a t i o 璐w i t ht h es a m ec o e m c i e n tm a t r i x as e a r c h d i r e c t i o ni sg e n e r a t e d t h ea l g o r i t h mi s p r o v e dt ob e9 1 0 b a l l ya n ds u p e r l i n e a r l y c o n v e r g e n tu n d e rs o m em i l dc o n d i t i o n s a d v a m a g e so ft h ea 培o r i t h mi n c l u d e t h eu n i f o r m l yn o 璐i n g u l a r i t yo ft h ec o e 伍c i e n tm a t r i c e sa n dt h eb o u n d e d n e s so f t h ea p p r o x i m a t el a 黟a n g em u l t i p l i e r sw i t h o u tt h es t r i c t l yc o m p l e m e n t a r i t ya r e o b t a i n e d m o r e o v e r t h eg l o b a lc o n v e r g e n c ei sa c h i e v e de v e ni ft h en u m b e ro ft h e s t a t i o n a r yp o i i l t si si n f i i l i t e k e y 廠o r d s n o n l i e a rc o n s t r 出n e do p t i m i z a t i o n m i n i m a cp r o b l e m s s q pa l g o r i t h m q p f r e ea l g o r i t h m g l o b a lc o n v e r g e n c e s u p e r l i n e a r c o i l v e r g e n c e i v 湖南大學 學位論文原創(chuàng)性聲明 本人鄭重聲明 所呈交的論文是本人在導師的指導下獨立進行研究 所取得的研究成果 除了文中特別加以標注引用的內容外 本論文不包 含任何其他個人或集體已經發(fā)表或撰寫的成果作品 對本文的研究做出 重要貢獻的個人和集體 均已在文中以明確方式標明 本人完全意識到 本聲明的法律后果由本人承擔 作者簽名 t f 4 l 形k日期 塒年 月夠日 學位論文版權使用授權書 本學位論文作者完全了解學校有關保留 使用學位論文的規(guī)定 同 意學校保留并向國家有關部門或機構送交論文的復印件和電子版 允許 論文被查閱和借閱 本人授權湖南大學可以將本學位論文的全部或部分 內容編入有關數據庫進行檢索 可以采用影印 縮印或掃描等復制手段 保存和匯編本學位論文 本學位論文屬于 1 保密口 在 年解密后適用本授權書 2 不保密口 請在以上相應方框內打 作者簽名 導師簽名 日期 多1 略年于月z l 日 日期 塒8 年手月哆日 博上學位論文 第1 章緒論 1 1 課題的發(fā)展概況與研究意義 本文中我們主要考慮求解如下非線性不等式約束優(yōu)化問題 p 竺2 o s 歹 j 仍 z o f l e t c h e r 1 5 將計算搜索方向的二次規(guī)劃子問題 1 2 轉化為一個無約束優(yōu)化問 題 通過求解這個約束優(yōu)化問題的極小點得到搜索方向 t o n e 1 6 也給出了兩種 修正的二次子規(guī)劃 并證明它們的解不為o 時足效益函數一f 1 精確罰函數的下降 方向 s c h i t t k o w s k i 1 7 則將 1 2 化為一個具有線性約束的最小二乘問題求解 一2 博上學位論文 作為對t o n e 的方法的改進 s p e l l u c c i 1 8 給出了一種克服二次規(guī)劃子問題不相 容的新方法 h a n 和b u r k e f 2 0 也給出了一個修正的二次子規(guī)劃 該子問題總是 相容的 受h a n 和b u r k e 方法的啟發(fā) z h o u 2 1 給出了一種克服二次規(guī)劃子問 題不相容的方法 該方法先解一個具有有界約束的線性規(guī)劃 后解一個修正二次 規(guī)劃得到修正方向 高 賀和賴 6 1 通過引進一個新的罰函數 結合積極集估計 技術 給出了一個具有可解子問題的s q p 算法 f k c h i n e i 2 6 利用l u c i d i 2 5 給 出的精確罰函數作為效益函數 給出了一個克服二次規(guī)劃子問題不相容的方法 如果子問題 1 2 相容且其解可接受 則將其解作為搜索方向 否則 利用效益函 數梯度的一個合理近似得到搜索方向 最近 m o z h a n g 和w 西 2 4 給出了一個 新的二次子規(guī)劃 該子問題也總足相容的 正如m a r a t o s 2 7 指出 傳統(tǒng)的不可行點s q p 算法可能存在m a r a t o s 效應 即當迭代點充分靠近最優(yōu)解時 不一定能保證步長恒為1 或趨于1 從而影響該 算法的超線性收斂性 為克服這個缺陷 學者們給出了幾種克服m a r a t o s 效應的 方法 第一種足用光滑精確罰函數代替z l 精確罰函數作為效益函數 具體見文 獻 2 8 一 3 2 第二種方法足二階修正步方法 具體見文獻 3 3 3 8 第三種方法是 w a t c h d o g 技術和非單調線搜索技巧 具體見文獻 3 9 一 4 7 在傳統(tǒng)的不可行點s q p 算法的收斂性分析中 在解處線性無關約束規(guī)格成立 對分析不可行點s q p 算法的二次收斂性是必要的 為減弱這個條件 w r i 曲t 4 8 通過對 1 2 修改 在m a n g a s a r i a n n o m o v i t z 約束規(guī)格下 給出了一個二次收斂 的s q p 算法 該算法稱作穩(wěn)定s q p 算法 后來 h a g e r 5 0 證明了w r i 曲t 的 算法在無嚴格互補條件下也足二次收斂的 只不過要求在解處強二階充分條件成 立 l i 5 1 通過求解線性方程組也給出了一個穩(wěn)定s q p 算法 并在較弱的條件下 證明了該算法的超線性收斂性 由于傳統(tǒng)的不可行點s q p 算法大多涉及罰參數的調整 為克服這個缺陷 f l e t c h e r l e y 虢r t o i n t w 畫c e r 和b i e g l e r 等人給出了 類新的序列二次規(guī)劃算 法 s q p f i l t e r 算法 而且在一定條件下 給出了該算法的全局收斂性和超線性 收斂性 具體見文獻 5 2 一 5 6 此外 有學者結合信賴域法 內點法和大規(guī)模優(yōu)化的特點 給出了幾類新的 s q p 算法 大規(guī)模s q p 算法可參見文獻 6 9 7 2 信賴域s q p 算法可參見文獻 7 3 一 7 6 內點型s q p 算法可參見文獻 7 7 一 7 9 1 1 2 可行點序列二次規(guī)劃算法 由于大多數求解約束優(yōu)化問題的s q p 算法從任意的初始點出發(fā) 使用精確 罰函數作為效益函數 這使得迭代點可能不足問題 1 1 的可行點 而對許多實際 問題而言 算法產生可行迭代點足非常重要的 例如對某些工程實際問題以及某 一3 一 求解約束優(yōu)化問題的序列二次規(guī)劃方法研究 些實際問題 其目標函數在可行域外往往沒有定義 此時要求迭代點必須可行 為此 p a n i e r 和t i t s 8 8 結合可行方向法和s q p 算法 提出了一類可行點序列 二次規(guī)劃 f s q p 算法 在該算法中 由于任意的迭代點擴均屬于 1 1 的可行 域 故二次規(guī)劃 1 2 總足相容的 即問題 1 1 的可行域總是非空的 而且目標 函數可以直接作為線搜索中的效益函數 但足該算法每個迭代步需求解三個不同 的二次規(guī)劃子問題 有時還要求出一個一階可行下降方向 而且該算法的收斂速度 僅足二步超線性收斂 為克服上述s q p 算法的不足 許多學者對其進行了改進 p a n i e r 和t i t s 1 0 1 對上述算法進行了改進 給出了一個組合可行與下降的超線 性收斂的s q p 算法 該算法的主搜索方向由其對應二次規(guī)劃子問題的解和另一二 次規(guī)劃的解的凸組合得到 為避免m a r a t o s 效應 需求解第三個二次規(guī)劃子問題 得到一個二階校正方向 高 吳 6 2 1 也對上述算法進行了修正 每步迭代只需計 算一個二次子規(guī)劃和一個逆矩陣 而且在較弱的條件下證明了算法的全局收斂和 一步超線性收斂性 j i a n 5 7 5 8 結合廣義投影梯度也對上述算法進行了修正 給 出一個超線性收斂和二次收斂的可行點s q p 算法 為減少上述算法每步迭代的 計算量 最近 z h u 1 0 2 給出了一個簡化可行點s q p 算法 其主搜索方向由其 對應二次規(guī)劃子問題的解和一線性方程組的解的凸組合得到 為避免m a r a t o s 效 應 一個二階校正方向通過解另一線性方程組得到 另外 文獻 8 3 8 4 8 5 中提出了另一類f s q p 算法 在算法的當前迭代點擴 處 通過求解如下二次規(guī)劃子問題得到主搜索方向t 勰z 礦風d s t v 廠 礦 t d 名 1 5 仇 z 七 v 吼 z 七 t d d z i 其中上k 足一對稱正定矩陣 吼是一正參數 從 1 5 中可以看出 如果吼 0 且上述二次規(guī)期的解d 吼 o 則d 口 是問題 1 1 在艫處的可行下降方向 文 獻 8 3 中 b i r g e q i w e i 討論了問題 1 1 的f j 點的求解 他們給參數盯一個 正的初始值 當單位步長不被接受時 適當增加參數盯的值 正如作者們指出 這種參數調整方法破壞了算法的超線性收斂性 文獻 8 4 中 l a w r e n c e 和t i t s 也給出了一個類似算法 需通過求解一個等式約束二次規(guī)劃來修正參數礦 使得 盯 d i l 如 為克服m a r a t o s 效應 需求解另一個等式二次規(guī)劃來修正搜索方向 如 k o s t r e v a 和c h e n 8 5 也通過求解二次規(guī)劃 1 5 提出了一個f s q p 算法 其 中要求盯 o i l 以l 但未具體給出參數盯的修正方式 1 1 3 q p f r e e 算法 由上述討論可知 s q p 類算法每次迭代需求解至少一個含不等式約束的二次 規(guī)劃 而相對而言 解線性方程組比求解含不等式約束的二次規(guī)劃要簡單得多 一4 一 博士學位論文 因此 在研究s q p 類算法的同時 有學者平行地提出了另一類算法 q p f r e e 算 法 或稱序列線性方程組算法 1 0 3 1 0 9 該類算法的產生基于以下事實 給定 一個合適的指標集7 考慮如下關于 d a 的線性方程組 其中 v z 日d a o 卵 z 嘩d o 9 了 z 彩 z 歹 7 v 緲 z j 7 在可行點z 處 如果d 0 a 0 則 v z a 0 毋 z o o 歹 1 6 1 7 若令a f 0 歹 八 則 1 7 表明z 為問題 1 1 的k k t 點 此類算法的思想最早見于文獻 6 3 6 4 而由p a i l i e r t i t s 和h e r s k o v i t s 1 0 3 于 1 9 8 8 年正式提出 該算法每步迭代需求解兩個不同的線性方程組和一個線性最小 二乘問題 而且為保證系數矩陣序列的一致非奇異性和近似乘子序列的有界性 必須假定在所有可行點處嚴格互補條件成立 g a o h e 和w u 1 0 4 給出了一個序 列線性方程組算法 該算法在沒有假定聚點孤立的條件下足全局收斂的 但是在 收斂性分析中必須要求乘子序列有界 q i q i 1 0 5 基于互補函數和k k t 條件 提 出了一個求解問題 p 的可行點q p f r e e 算法 他們在無嚴格互補條件下證明了 迭代矩陣的一致非奇異性和近似乘子序列的有界性 a n g l i 和q i 1 0 6 通過引進 一個工作集的概念 提出了一個新的求解問題 p 的可行點q p f r e e 算法 這個新 算法僅考慮工作集內的約束 這使得計算量大大減少 在這個算法的每一個迭代 步 為得到搜索方向 僅要求解四個系數相同的線性方程組 在合適的條件下 這 個算法具有全局收斂性和局部一步超線性收斂速度 甚至具有二次收斂速度 數 值實驗表明這個算法特別適合求解大規(guī)模不等式約束優(yōu)化問題 最近 z h u 1 0 9 給出了一個新的內點型可行點q p f r e e 算法 在此算法的每一個迭代步 為得到 搜索方向 只需解三個相同系數矩陣的線性方程組 但足系數矩陣序列需在嚴格 互補條件下保持一致非奇異性 而且為得到全局收斂性 穩(wěn)定點數目有限這個條 件足必要的 以上均為可行點q p f r e e 算法 有關不可行點q p f r e e 算法的研究 參見文獻 1 9 5 9 6 0 1 0 7 最近 也有學者研究了求解目標函數足s c l 函數 即 一階導數半光滑 的約束優(yōu)化問題的可行點q p f r e e 算法 可參見文獻 6 6 6 7 一b 一 求解約束優(yōu)化問題的序列二次規(guī)劃方法研究 1 2 本文主要工作及創(chuàng)新點 第2 章在文獻 8 3 8 4 8 5 的基礎上 結合積極集估計技術 提出一個積極集可 行點s q p 算法 該算法的主要優(yōu)點在于 算法的主搜索方向由一個低維的凸 二次規(guī)劃 2 3 確定 而且不需求解任何子問題來修正 2 3 中參數吼 只需 取吼 i i 擴 1 n 其中擴 1 為前一個迭代點處的主搜索方向 為克服m a r a t 0 8 效應 通過求解一個最小二乘問題得到高階修正方向 在適當的條件下 我們 證明算法具有全局收斂性和超線性收斂性 第3 章提出一個求解極大極小問題的修正s q p 算法 該算法的主搜索方向通 過求解一個二次規(guī)劃得到 為克服m a r a t o s 效應 不同于文獻 9 5 9 8 我們 通過求解一個線性方程組得到高階修正方向 而 9 5 和 9 8 中需通過求解一 個二次規(guī)劃子問題得到高階修正方向 在較弱的條件下 我們證明該算法是全 局收斂和一步超線性收斂的 第4 章提出一個求解非線性約束優(yōu)化問題的可行點s q p 算法 在該算法的每 一個迭代步 分別通過求解二次規(guī)劃子問題和線性方程組得到一個下降方向 和一個可行方向 在此基礎上 我們構造一個可行下降方向 為避免m a l r a t o s 效應 我們通過解一線性方程組得到高階修正方向 在適當的條件下 該算法 被證明足全局收斂和超線性收斂的 與已有算法相比 本章提出算法的優(yōu)點 足 算法中線性方程組不涉及乘子估計 所求解的兩個線性方程組的系數矩陣 相同且比文獻 1 0 2 中系數矩陣的結構簡單 因而可減少計算量 第5 章以文獻 1 0 6 中算法為基礎 提出一個求解非線性不等式約束優(yōu)化問題 的非內點型可行點q p f r e e 算法 這個算法不要求迭代點必須足可行域的內 點 在算法的每一個迭代步 為得到搜索方向 只需求解四個系數相同的線性 方程組 在適當的條件下 我們建立該算法的全局收斂性和超線性收斂定理 第6 章以文獻 1 0 5 中算法為基礎 提出一個改進的內點型可行點q p f r e e 算 法 在該算法的每一個迭代步 為得到搜索方向 只需解三個系數矩陣相同的 線性方程組 而且在無嚴格互補條件下得到系數矩陣序列的一致非奇異性和 近似乘子序列的有界性 且其全局收斂性分析不受穩(wěn)定點數目有限的限制 6 博上學位論文 1 3 本文所用的記號 實向量 目標函數 問題的維數 即z 的分量數目 全體實數組成的集合 全體n 維實向量組成的集合 n 階單位矩陣 非奇異方陣a 的逆 矩陣a 的轉置 矩陣a 的行列式 集合f 包含的元素的個數 z 的梯度 z 的海色矩陣 向量的歐氏范數 一 一 二二 腳 兒 z刷以孢舭k臚肛叫啡蹦吧 求解約束優(yōu)化同題的序列二次規(guī)劃方法研究 第2 章求解約束優(yōu)化問題的一個積極集可行點 s q p 算法 2 1 引言 本章考慮求解如下不等式約束優(yōu)化問題 m i n m 2 1 1 p s t 劬 z 0 歹 7 其中m 是正整數 函數 仍0 j 艫一只連續(xù)可微 最近 文獻 8 3 8 4 8 5 中提出了一類求解問題 2 1 的f s q p 算法 在算法 的每一個迭代點礦處 通過求解如下二次規(guī)劃子問題得到主搜索方向 班i 嬰z 礦風d 2 d s t v 擴 t d z 吼 z 七 v 紡 z 知 t d 盯k 名 i j 2 2 其中f k 是一對稱正定矩陣 吼是一正參數 從 2 2 中可以看出 如果以 0 且 上述二次規(guī)劃的解如 o 則d 是問題 2 1 在z 七處的可行下降方向 文獻 8 3 中 b i r g e q i w e i 討論了問題 2 1 的f 點的求解 他們給參數吼一個正的初始 值 當單位步長不被接受時 適當增加參數吼的值 但這種參數修正方法破壞了 算法的超線性收斂性 文獻 8 4 中 l a w t e n c e 和t i t s 也給出了一個類似算法 通 過求解一個等式約束二次規(guī)劃來修正參數吼 使得吼 o i l d 吼 另外 為克服 m a r a t o s 效應 需求解另一個等式二次規(guī)劃來修正搜索方向d 附k o s t r e v a 和c h e n 8 5 也通過求解二次規(guī)劃 2 2 提出了一個f s q p 算法 其中要求吼 d i i d 吼忱 但未具體給出參數吼的修正方式 本章中 我們在文獻 8 3 8 4 8 5 l 的基礎上 結合近似積極集技術 提出了一個 積極集可行點s q p 算法 該算法的主搜索方向由求解一個低維的二次規(guī)劃 2 3 得到 而且不需求解任何子問題來修正 2 3 中參數吼 只需取吼 l 渺 1 盯為 克服m a r a t o s 效應 通過求解一個線性方程組得到一個高階修正方向 在適當的 條件下 我們證明該算法具有全局收斂性和超線性收斂性 2 2 算法描述 首先我們定義問題 p 的可行域x 為 x z r 吼 z o i 一8 一 博士學位論文 而且對每一個可行點z x 定義積極集為 j z i j 9 t z o 本章中我們總假定可行集x 非空且如下假設成立 h 1 對每一個可行點z x 向量組 v 肌 z i z 足線性無關的 對z x 我們使用如下近似積極集 可參見文獻 8 6 1 0 6 a z i 9 i z p z a z o 其中 是一非負參數 p z 入 z 礦虱 天丌 坼州z 肛 m 淵要糾以加 9 1 z 9 2 z 夕m z 入 z 一 v 9 z r v 9 z d i 0 9 吼 z 2 一1 v 9 z r v z v 9 z v 吼 z i j 易知 z 足問題 p 的k k t 點當且僅當圣 礦 o 或p z a o e a c c h i n e i 等人在文獻 8 6 中證明了如果二階充分條件和m a n g a s s 撕a n f r o m o v o t z 約束規(guī)格成立 那么對任意 0 當z 充分接近礦 a z 5 z 下面我們給出求解問題 p 的一個積極集可行點s q p 算法步驟 有關參數r 乃 0 0 丁 2 3 o o p o 1 7 o 1 q o 有關數據給定初始點z 1 x 一個對稱正定矩陣日l 盯l 0 和 o o 令七 1 步1 令e e 步2 令a 七 a 礦 如果v 9 j 4 z 非滿秩 則令e 仃e 進入步2 這 里v g a 1 z 2 v 吼 z 七 i a 七 步3 令e 蠡 小 a e 步4 計算主搜索方向 對當前迭代點擴 求解 m i n r z 玩d q 尸 s t v z 知 r d r z 2 3 吼 z 是 v 吼 z 七 t d n 盯 z i a 七 得 z k 擴 令 札3 u 蓋 是其相應的l a g r a n g e 乘子 如果擴 o 那么擴足問題 p 的k k t 點 停 否則進入步5 一9 一 求解約束優(yōu)化聞題的序列二次規(guī)翔方法研究 步5 計算高階修正方向 通過求解下面的最小二乘問題得高階修正方向矛 己s m i n 到訓 s t 吼 z d v 吼 z 知 t d 一 1 一p k i l d 毛1 1 7 m n 仃z i i d 2 i l i a 矗 2 4 例1 2 一 跫祭n 吼訊 嗍1 2 l 驢i i 令沙 0 步6 線搜索 求序列 1 p p 2 中滿足如下不等式組的第一個數作為k z 七 a d 七十a 2 矛 z 七 a a v z 南 丁d k 吼 z 入d 知 入2 孑 o j 步7 令一 l 擴 k 擴 a 矛 吼 l i i 驢曠 步8 計算一個新的對稱正定矩陣風 l 令忌 七十1 返回步1 為討論方便 對任意的七 我們令 o i 小 下面我們證明該算法是適定的 2 5 2 6 引理2 2 1 對礦 x 如果條件肌成立 則該算法在步2 中的循環(huán)經有限步終 止 該引理的證明類似于文獻 8 7 中引理1 1 和引理2 8 的證明 引理2 2 2 如果風是一對稱正定矩陣 且參數r 巧u 都是正數以及盯 o 則似咧總存在唯一最優(yōu)解 該引理的證明見文獻 8 4 中引理1 的證明 引理2 2 3 若日島是一對稱正定矩陣 則仁別總存在唯一最優(yōu)解 利用王如對稱正定性和夕a t 擴 的滿秩性易得該引理的證明 引理2 2 4 設引理2 2 2 中的條件成立 如果 魂 艫 是償 矽的最優(yōu)解 則 一 jr d 七 丁仇d so 和z 七 o 一砂魂 o 甘d o 錯z 七是問題口 的爿k r 點 一別 o 使得任意a f o 習 妣 0 其次 由 2 6 和引理2 2 4 可知 當i a 七時 磚全吼 z 七 a d 七 入2 矛 吼 z 豇 入v 吼 z 知 t d 南 d a 1 一入 吼 z 七 入z o 入 故存在天 o 使得任意入 o 天 磚 o 當i 隹a 詹時 仇 z 知 一 p z 詹 a z 詹 o 使得任意a o 天 醇 o 令爻 m i l l 天 忑 天 i j 因此結論成立 2 3 全局收斂性分析 本節(jié)我們將分析2 2 節(jié)中算法的全局收斂性 首先做如下假設 h 2 該算法所產生的序列 z 七 是有界的 h 3 對任意忌和所有d j p 存在兩個正數o 6 o 滿足 o 1 2 d 丁風d 6 刮2 我們不妨設礦是序列 z 的一個聚點 注意到a 和以是有限集合 的子集 故存在一子集 使得 i 粵z 詹 z a 蘭a 以蘭zv 忌 k 2 7 知 k o7 其中 以 i a 9 t z 七 v 9 t z 七 丁擴 n 盯七 引理2 3 1 如果假設艘 冊成立 則序列 擴 后 k i 魂 后 k 和 矛 k 都是有界的 l l 求解約束優(yōu)化問題的序列二次規(guī)劃方法研究 證明 首先 由v 擴 v 礦 尼 k 知 存在常數c o o 使得0v i c d v 七 k 而且 結合引理2 2 4 2 3 和假設h 3 可得 o r 沙 t 玩擴 v 擴 t 擴 剖剝2 一i v 廠 z l ll l d 七i l 2i i d 七1 1 2 一c 0 i i d 七 g l l d 七1 1 2 七 k 這表明 驢 七 k 是有界的 其次 旅 七 的有界性可從 驢 后 k 的有界性和下面的不等式推 得 o 2 鐫 v z 七 丁d 奄 一 j i v z 膏 i i i l d i i 一摯i i d i i 后 k 2 8 最后 矛 七 k 的有界性可從 驢 七 k 的有界性得到 下面我們給出 n q p 的k k t 條件如下 凰鏟 u 6 v m 七 三蝣v 緲 擴 o u 墨 磚 j a 2 9 r r 亂5 暑嘭吩鞏 諺 o 歹 a u 3 o 2 1 0 j a o u 3 上 r 魂一v z 七 丁擴 2o 2 1 1 o u 上 吩盯k 一緲 z 奄 一v 緲 z 丁擴 o 歹 a 2 1 2 其中記號z 上可表示z t 秒 0 引理2 3 2 俐乘子序列 讓g 篷 是有界的 以砂設條件肌 如冊成立 且令乘子向量仳 仳魯 o 八a u o 八t 如果l i m 礦 礦以及l(fā) i m 毋 0 則 u 知 南 k 是有界的 k k南 k 證明 i 根據 2 3 的k k t 條件可得 r r 亂3 諺吩吼 r u j a 即 o 仳3 1 i i 假設 i i 的結論不成立 則存在一個子集k k 使得l i 鏟l l l iu 5 i o o 七 k 7 因此 用 i u 釧去除 2 9 兩邊可得 南風d 2 赫v m 七 暑志v 仍 z o 2 1 3 注意到 禹 七 k 是一模長為1 的序列 故我們不妨設 禹一馮 七 k j 正os 弓 j j o 2 1 4 一1 2 博上學位論文 因此 對 2 1 3 兩邊取極限 后 k 七一 考慮到假設h 3 和給定的條件可 得 弓v 緲 o 2 1 5 j j 另一方面 根據給定的條件可得 j z 因此根據 2 1 4 2 1 5 和h 1 可得一矛盾 故 u 詹 七 k 足有界的 考慮到序列 u 3 后 k 讓2 后 k 和 吼 的有界性 我們不妨設 u 奄 磚 j 一u 嵋 歹 u u 吼一盯 七 k 2 1 6 引理2 3 3 設 礦 是該算法所產生的序列 如果l 啦擴 z 且l i m 擴 0 則 知 k k 口是r 題 p 的k k t 點 證明 由l 迪擴 z 和l i m 擴 0 可知 l i mz 七 o 因此 對 2 9 一 2 1 2 兩 七 k 七 k 七 k 邊取極限 七 k 七一 可得 u v 他 暑讓 v 緲 z o q 乃 z o u o 彩 z o 歹 a 2 1 7 r 7 u 以 巧嘭 u o j j 由 2 1 7 的第三式易知 讓 u 0 而且結合假設h 1 可得 喵 0 這 就表明 z 蘭 是問題 p 的k k t 點 基于引理2 3 1 引理2 3 2 和引理2 3 3 我們給出如下全局收斂性定理 定理2 3 1 如果假設何j 艘 冊成立 那么該算法或有限步終止問題俐的麒t 點或產生一無限序列 z 其每一個聚點z 都是問題俐的刪t 點 而且 鬟 七 k 收斂到對應于z 的肼t 乘子且l 蛔砧 o o 七 k 證明 該定理的第一個結論足顯然的 因此我們不妨設 為該算法所產生的無 限序列且 2 1 6 成立 下面分仃 o 和以 o 兩種情況給與證明 1 當以 0 時 由步7 知 存在一無限子集風 k 使得 1 i m 驢 l o 再次由步7 知 z 奄一z 七一1i i 七i ld 1 i 2l i 孑一1l l 2 擴0d 七一1l l o 鳧 k 1 因此 根據 1 i 騁擴 z 可得l i mz n l z 進一步由引理2 3 3 知礦是問題 七 k l奄 k l p 的k k t 點 2 當盯 o 時 顯然 只需證明般沙 o 即可 為此 我們假設躲擴 o 則存在一無限子集k 7 k 和一常數 0 使得對任意后 k 有i l 擴 下面的證明分兩步進行 一1 3 求解約束優(yōu)化問題的序列二次規(guī)劃方法研究 a 首先證明存在天 o 使得對任意克 k 有a 七 天 z a d 七十a 2 d 南 一 z 七 一口a v z 七 丁驢 v z 七 t a d 七 a 2 d 七 一q a v z t d d a 入 1 一q v z 七 d d 入 a 1 一a 7 訊 d a 一 入 1 一n d 島 風d 七 d 入 一i o a 1 一q i i d 1 1 2 d a 一 口a 1 q 2 d a 上面的最后一個不等式表明對七 k 7 充分大和入 0 充分小 有 2 5 成立 下面分析 2 6 如果歹ga 即 緲 擴 一印 擴 a 七 o 充分小 有緲 礦 入擴 a 2 擴 0 成立 如果j a 則由泰勒展式和 2 3 可得 緲 擴 a 擴 a 2 擴 劬 z 缸 a v 乃 擴 t 艫 d a 仍 z 七 a 巧吼 一彩 礦 十d 入 1 一入 仍 z 七 入r j 仃 么 d 曲 入r j 仃七旅 d a 從而由 2 3 和假設h 3 可得 仍 z 七十a d 七十a 2 d 知 a 乃口 一寺 d 七 t 風d 七 d 入 s一入q 仃 砉nl d 七i 1 2 d 入 s一入q 盯 去o 2 o 入 因此上面的不等式表明對后 k 7 充分大和a o 充分小 有 2 6 成立 綜合上面的分析可知 存在天 o 使得對老 k 有k 頁 b 其次利用a 入 o 得出一個矛盾 由 2 5 2 3 和假設h 3 可知 z 七 1 廠 z 知 a a 七v z 2 丁d 七 z 奄 口a 知r z 格 z 一 q a d 丁風d 七 z 南 一 q a 七ol id 七1 1 2 v 七 因此序列 是單調下降的 考慮到 姊 礦 廠 礦 故 i i m 廠 一 z k t 托 o 又 1 詹 一去8 a 頁 2 v 七 k 對上面不等式兩邊取極限 七 k 且七一 可得一 口q 頁 2 o 這是一個矛 盾 因此 擴 o 故由引理2 3 3 知 礦足問題 p 的k k t 點 而且 籌 后 k 收斂到對應于z 的k k t 乘子且2 臻讓5 o 一1 4 博士學位論文 2 4收斂速度分析 本節(jié)我們將分析2 2 節(jié)中算法的收斂速度 為此 我們做如下假設 h 4 i 函數 z 緲 z 歹 二次連續(xù)可微 i i 在序列 礦 的聚點z 處二階充分條件成立 即 礦v l z u d o v d q 型 d 兄 l d o v 9 z z 丁d o 2 1 8 其中 l z t z z 緲 z 2 1 9 j i i i 在z 處嚴格互補條件成立 即 一9 z 0 引理2 4 1 以 j 如果假設肌 上陀成立 則t l i m 驢 o l i m 擴 o 1 i m 訊 o 七 o o