min-max-min規(guī)劃的凝聚同倫方法及其在數(shù)據(jù)挖掘中的應(yīng)用.pdf

1、min-max-min規(guī)劃是一類重要的非光滑非凸優(yōu)化問(wèn)題，在工程優(yōu)化設(shè)計(jì)、電子線路設(shè)計(jì)、數(shù)據(jù)挖掘等領(lǐng)域有著重要應(yīng)用，本文的工作在已有的凝聚同倫算法的基礎(chǔ)上進(jìn)行。
　　 第一章主要介紹min-max-min規(guī)劃模型及其應(yīng)用背景，并回顧一些相關(guān)理論與算法。
　　 第二章提出了數(shù)值跟蹤凝聚同倫的一個(gè)基于截?cái)嗖呗缘母咝仕惴?在算法的每步迭代，只用到max-min函數(shù)的組成函數(shù)中的一小部分的凝聚函數(shù)，這一部分組成函數(shù)對(duì)應(yīng)的下標(biāo)集

2、合在每步迭代過(guò)程中隨著截?cái)嗑瓤刂茰?zhǔn)則自適應(yīng)調(diào)整，以盡可能地減少函數(shù)的梯度及海賽陣的計(jì)算量.我們給出保持校正算法的二次收斂性和預(yù)估步的有效性的截?cái)嗄劬瓤刂茰?zhǔn)則，該精度控制準(zhǔn)則不涉及梯度和海賽陣的計(jì)算，只與max-min函數(shù)的組成函數(shù)的函數(shù)值有關(guān).基于該精度控制準(zhǔn)則，我們證明了截?cái)嗄弁瑐愃惴ǖ氖諗啃约懊坎叫Ｕ木植慷问諗啃裕?br>　　 第三章基于二次凝聚函數(shù)，對(duì)min-max-min規(guī)劃構(gòu)造了一種動(dòng)約束函數(shù)，使得原問(wèn)題的可行集

3、可以由一個(gè)凸球約束連續(xù)形變過(guò)去，進(jìn)而給出了一類新的凝聚形變同倫方法。新算法不要求可行集滿足弱法錐條件，并且不要求初始點(diǎn)是內(nèi)點(diǎn)。
　　 第四章基于離散化相容逼近的策略，將半無(wú)限min-max-min問(wèn)題轉(zhuǎn)化為有限min-max-nun規(guī)劃問(wèn)題，再用截?cái)嗄弁瑐惙椒ㄇ蠼?，可以證明：當(dāng)離散點(diǎn)充分稠密時(shí)，離散化子問(wèn)題的穩(wěn)定點(diǎn)是原問(wèn)題的ε-次穩(wěn)定點(diǎn)。
　　 第五章將半無(wú)限min-max-min問(wèn)題寫成一個(gè)雙層規(guī)劃問(wèn)題。在底層問(wèn)題嚴(yán)

4、格凸的假設(shè)下，建立了原問(wèn)題的一階最優(yōu)性條件，并構(gòu)造凝聚同倫方法求解該問(wèn)題。在一定條件下，可以證明通向原問(wèn)題的廣義KKT點(diǎn)的光滑同倫路徑的存在性和收斂性。
　　 第六章考慮了截?cái)嗄弁瑐愃惴ㄔ跀?shù)據(jù)挖掘的支持向量機(jī)模型求解中的一些應(yīng)用，首先考慮了半監(jiān)督分類問(wèn)題。將已有的求解半監(jiān)督分類問(wèn)題的一個(gè)支持向量機(jī)模型加以變形，得到一個(gè)由max型以及max-min型的非光滑函數(shù)組合得到的無(wú)約束非光滑非凸優(yōu)化問(wèn)題，并構(gòu)造了截?cái)嗄弁瑐愃惴ㄇ蠼庠撃?/p>