最優(yōu)化算法理論與應(yīng)用

課程名：最優(yōu)化算法理論與應(yīng)用單位：清華大學(xué)自動(dòng)化系電子信箱：swang@教師：王書(shū)寧電話：62783371講課時(shí)間：2008年3月12日起每周三下午2點(diǎn)開(kāi)始講課地點(diǎn)：自動(dòng)化所自動(dòng)化大廈優(yōu)化方法基本分類本門(mén)課程有關(guān)事宜優(yōu)化問(wèn)題基本分類優(yōu)化問(wèn)題基本分類例、和優(yōu)化聯(lián)系非常密切的一類問(wèn)題（回歸、辨識(shí)、估計(jì)、訓(xùn)練、學(xué)習(xí)、擬合、逼近…）已知某個(gè)標(biāo)量和某個(gè)向量之間若干一一對(duì)應(yīng)的樣本數(shù)據(jù)要確定一個(gè)函數(shù)，使在包含所有樣本數(shù)據(jù)的某個(gè)集合里能夠用描述和之間的對(duì)應(yīng)關(guān)系，即使誤差對(duì)任意的都盡量小基本方法：選擇含有待定參數(shù)的函數(shù)，通過(guò)極小化某種樣本誤差確定待定參數(shù)得到所需函數(shù)常用范數(shù)的樣本誤差于是，最終要解決的是下述優(yōu)化問(wèn)題這是連續(xù)變量無(wú)約束優(yōu)化問(wèn)題對(duì)于采用范數(shù)形成的優(yōu)化問(wèn)題為克服目標(biāo)函數(shù)不可導(dǎo)的困難，可以等價(jià)轉(zhuǎn)換成下面的連續(xù)變量約束優(yōu)化問(wèn)題特別是，當(dāng)是的線性函數(shù)時(shí)，即上面的優(yōu)化問(wèn)題是線性規(guī)劃問(wèn)題可以選擇足夠多的基函數(shù)使優(yōu)化問(wèn)題的樣本誤差任意小，這樣得到的模型在樣本集以外通常會(huì)產(chǎn)生很大的預(yù)報(bào)誤差，這就是所謂過(guò)度擬合或過(guò)度訓(xùn)練問(wèn)題。解決該問(wèn)題的根本途經(jīng)是同時(shí)極小化基函數(shù)的個(gè)數(shù)，理論上要解決連續(xù)和離散變量混合的優(yōu)化問(wèn)題其中是設(shè)定的正的權(quán)值前面的例子包含了優(yōu)化問(wèn)題最基本的類型線性與非線性無(wú)約束與有約束連續(xù)變量與離散變量后者相對(duì)于前者在難度上均有質(zhì)的改變具有不確定性和動(dòng)態(tài)特性的問(wèn)題轉(zhuǎn)換成上述問(wèn)題優(yōu)化方法基本分類例基本方法：從之間的任一點(diǎn)出發(fā)，朝著能夠改進(jìn)目標(biāo)函數(shù)的方向搜索前進(jìn)，直至目標(biāo)函數(shù)不能改進(jìn)肯定能夠收斂到一個(gè)局部最優(yōu)解，不能保證全局最優(yōu)跳出局部陷阱的唯一途經(jīng)是在搜索過(guò)程中允許前進(jìn)到目標(biāo)函數(shù)值變差的點(diǎn)，如在之間容許目標(biāo)函數(shù)下降才有可能找到全局最優(yōu)解由此產(chǎn)生新問(wèn)題，無(wú)法保證算法收斂為了使算法收斂，只能引入不確定性，讓算法在任何一點(diǎn)以一定的概率前進(jìn)到鄰近的某點(diǎn)，移動(dòng)概率和相應(yīng)點(diǎn)的目標(biāo)函數(shù)值正相關(guān)，所以由此產(chǎn)生的算法是結(jié)果不確定的算法前面的例子包含了優(yōu)化方法最基本的類型確定型搜索與不確定型搜索前者是經(jīng)典的優(yōu)化教材介紹的主要內(nèi)容，后者包括模擬退火、禁忌搜索、遺傳算法、免疫算法、螞蟻算法等方法，一般統(tǒng)稱為智能算法本課程主要討論基于確定性搜索的優(yōu)化方法后期簡(jiǎn)單介紹基于不確定性搜索的優(yōu)化方法本門(mén)課程有關(guān)事宜教材：運(yùn)籌學(xué)（第二版），刁在筠等編，高教出版社

自第2章到第6章按教材順序講課，內(nèi)容有增減

在第6章后增加一些不確定型搜索方法的內(nèi)容