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

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

自第2章到第6章按教材順序講課，內容有增減

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