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

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

2、合在每步迭代過程中隨著截斷精度控制準(zhǔn)則自適應(yīng)調(diào)整，以盡可能地減少函數(shù)的梯度及海賽陣的計算量.我們給出保持校正算法的二次收斂性和預(yù)估步的有效性的截斷凝聚精度控制準(zhǔn)則，該精度控制準(zhǔn)則不涉及梯度和海賽陣的計算，只與max-min函數(shù)的組成函數(shù)的函數(shù)值有關(guān).基于該精度控制準(zhǔn)則，我們證明了截斷凝聚同倫算法的收斂性及每步校正的局部二次收斂性，
　　 第三章基于二次凝聚函數(shù)，對min-max-min規(guī)劃構(gòu)造了一種動約束函數(shù)，使得原問題的可行集

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

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