約束序列極大極小問題的部分凝聚動約束組合同倫方法

1、PAGE PAGE 10約束序列極大極小問題的部分凝聚動約束組合同倫方法* 劉慶懷*基金項目：國家自然科學(xué)基金資助項目（10771020）；吉林省教育廳“十一五”科學(xué)技術(shù)研究資助項目 *通訊作者：劉慶懷（1961） 男 教授 博士 吉林長春人 主要從事最優(yōu)化理論與算法研究，Email：L. 王秀玉1 譚佳偉1(1 長春工業(yè)大學(xué)基礎(chǔ)科學(xué)學(xué)院,長春 130012).摘要:為解決約束序列極大極小問題(CSMMP)，首先構(gòu)造凝聚動約束函數(shù)族并給出其相關(guān)性質(zhì),然后構(gòu)造組合同倫方程,給出同倫路徑收斂性證明,所用初始點既可以是內(nèi)點 也可以是外點,最后,給出數(shù)值算例,并用matlab7.0編程進(jìn)行計算,數(shù)值結(jié)

2、果表明:此算法是可行和有效的.關(guān)鍵詞: 序列極大極小問題,同倫方法,凝聚函數(shù),動約束 1991 MR subject classification:90C47,65K05,65H10,90C51中圖分類號:O221.21 預(yù)備知識約束序列極大極小優(yōu)化問題是一類重要的優(yōu)化問題。它在工程設(shè)計、電子線路設(shè)計、熱交換設(shè)計、化學(xué)反應(yīng)設(shè)計等諸多領(lǐng)域有廣泛的應(yīng)用（1 8）.此外，多目標(biāo)規(guī)劃、隨機(jī)規(guī)劃的一些特殊情形可轉(zhuǎn)化為約束序列極大極小優(yōu)化問題9.約束序列極大極小優(yōu)化問題相應(yīng)算法的主要困難是問題本身的非光滑性及非凸性，至今尚缺少有效的算法，處理這類問題有割平面法、捆集信賴域法及采用分解的策略等.文10以引入

3、若干額外變量為代價討論了此類問題轉(zhuǎn)化為一種光滑約束規(guī)劃問題.文11利用凝聚同倫方法討論了可行域的邊界滿足弱法錐條件下約束序列極大極小優(yōu)化問題.但當(dāng)可行域不滿足弱法錐條件時, 使用凝聚同倫方法解決約束序列極大極小優(yōu)化問題的算法尚未見到,本文在這方面做一些嘗試性工作,并得到了較好的結(jié)果. 本文考慮如下的序列極大極小問題(CSMMP):記 ,.引理1 .(證明參考11)假設(shè)1 和均為至少三次連續(xù)可微的函數(shù);對任意是正獨立的;其中,有界連通, 非空.定理 111 若 and 均為充分光滑的函數(shù)且假設(shè)2,3的條件成立.如為 CSMMP問題的局部極小點,則存在 使得其中 .上述方程的解成為序列極大極小問題

4、(CSMMP)的點.為解決CSMMP問題我們構(gòu)造如下動約束函數(shù)族:,其中, 為一族充分光滑的函數(shù).記 .2 主要結(jié)論引理2 若假設(shè)1和 3的條件成立, 則 有:,其中,且有: ,證明: 略.引理3 若假設(shè)1,2,3的條件成立,則存在 ,對,是正獨立的.證明:(反證)假如上述結(jié)論不成立,則存在,且 不全為零,滿足:且 因為, 必存在收斂子列,仍記為,及, , 則 矛盾(因假設(shè)3,及, 固有對任意,是正獨立的.選取即可. 在計算過程中保證所選取的滿足:假設(shè) 4 滿足法錐條件12:,其中是空集.因,只要取得足夠小就能保證非空,對,記,構(gòu)造同倫方程如下: (1)其中,當(dāng), 式(1)變?yōu)?顯然有唯一解.

5、由引理2得: 當(dāng), 式(1)變?yōu)?,where, .且顯然成立.記引理 4 若假設(shè)1,2,3的條件成立,則對于幾乎所有的 ,0是映射 的正則值,同倫方程 (1) 產(chǎn)生一條起始于點的光滑曲線,記為證明:用 表示的矩陣 (看作變量)=,對幾乎所有的 ,有 , 為單位矩陣, 對任意的,因 ,則 行滿秩.由參數(shù)化定理,得0是映射 的正則值,再由逆映象定理及,含有一條起始于點的光滑曲線 .引理5 若假設(shè)1,2,3的條件成立,則對任意給定的 , 0是映射 的正則值,則有 是中的有界曲線.證明: 由同倫方程(1)易知 .若 是無界曲線,那么必存在點列,使得,由同倫方程(1)的第二個方程得: :, (2)由(

6、2)得, 及 , 有界,即有界,必存在收斂子列,仍記為,設(shè),其中,由 (2) 得到:, ,i.e.,.由同倫方程(1)的第一個方程得: : (3)(3)式重寫為: (1) 若 (3)式兩邊取極限得: ,由引理3, 存在,記 (3)式為: ,此與假設(shè)4矛盾.(2) 若當(dāng)時, 式左邊的第二項趨于無限,而其他各項均趨于有限,又產(chǎn)生了矛盾.綜上所述, 有界. 定理2 若假設(shè)1,2,3的條件成立,同倫映射由(1)式給出,則對幾乎所有的 ,同倫方程(1)的零點集包含一條起始于的光滑曲線.當(dāng)時, 的極限點存在,記為, 為序列極大極小問題的K-K-T 點. 證明: 由引理4 和5得的存在性及連續(xù)性.又由一維光

7、滑流形的分類定理知:或微分同胚于單位圓周,或微分同胚于單位區(qū)間.注意到:是非奇異矩陣,不能微分同胚于單位圓周,只能微分同胚于單位區(qū)間.設(shè)為的極限點.則只有下列五種情況可能出現(xiàn):(1) 存在一個;(4) ;.證明:由引理5知:情形(1)不可能出現(xiàn);又由同倫方程在有唯一解知,情形 (3)不可能出現(xiàn);由(2)式,若有某及,必有,這是不可能的, 情形 (2)也不可能出現(xiàn); 由(2)式,如果,則有某,(4)也不可能出現(xiàn);因而,只有情形(5)是唯一可以成立的結(jié)論.其余顯然可證.從定理2可以得到,對幾乎所有的,同倫方程(1)生成一條光滑曲線 ,稱之為同倫路徑.設(shè)s 表示的弧長,參數(shù)化這條解曲線,即存在連續(xù)可

8、微函數(shù)使得: (4)關(guān)于微分(4)式的第一個等式,得到如下結(jié)論:定理3 同倫方程所確定的解曲線滿足如下微分方程的初值問題:并且,若有使得,則是序列極大極小問題的點. 3 數(shù)值算例例1 其中 , ;, ;, ;, ;,.,滿足法錐條件(法錐條件見12). 用7.0編程計算結(jié)果如下：表1 例1計算結(jié)果1/72.611.11110.00061.61720.06930.01940.02420.06870.0094其中 ,.參考文獻(xiàn)1 Limin，H. E. and Polak, E., Effective diagonalization strategies for the solution of a

9、 class of optimal design problems, 35 (1990) 258-267.2 Bandler，J. W., Liu, P. C. and Tromp, H., A nonlinear programming approach to optimal design centering, tolerancing, tuning, CAS-23, 1976, 155-165. 3 Liu, P. C., Chung, V. M. and Li, K. C., Circuit design with post-fabrication tuning, in Proc. Wa

10、shington, DC. IEEE, NY, 1992,344-3474 Muller, G., On computer-aided tuning of microwave filters, In IEEE Proc. international Symposium on Cirtuits and Systems, Munich, IEEE Computer Society Press Los Alamitos, CA, 1976, 722-725.5 Polak, E., Sangiovanni, A. and Vincentelli, A. S., Theoretical and com

11、putational aspects of the optimal design centering, tolerancing and tuning prblom, CAS-26, 1976, 795-813.6 Gilbert,E. G. and Johnson, D. W., Distance functions and their application to robot path pianning in the presence of obstacles, RA-1, 1985,21-30.7 Halemane, K. P. and Grossman, I. E., Optimal p

12、rocess design under uncertainty, 29 (1983),425-433.8 Ostrivsky, G. M., Volin, Y. M., Barit, E. I. and Senyavin, M. M., Flexibility analysis and optimization of chemical plants with uncertain parameters,18 (1991),755-7679 Scholtes, S., Combinatorial structures in nonlinear programming, Judge Institut

13、e of management, Department of Engineerng, University of Cambridge CB21AG, 2002.10 Kirjner-Neto, C. and Polak, E., On the conversion of optimization problems with max-min constraints to standard optimization problems. 8 (1998), 887-915.11 LIU Guo-xin. Aggregaye Homotopy Methods for Solving Sequential Max-Min Problems,Complementarity Problems and Variational lnequalities D：Ph D ThesisChangchun Jilin University, 2003. in Chinese12 Xu Qing，Yu Bo，Homotopy Methods for Non-convex Programming in Un