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

1、課程名：最優(yōu)化算法理論與應用,單位：清華大學自動化系,電子信箱：swang@mail.tsinghua.edu.cn,教師：王書寧,電話：62783371,講課時間：2008年10月15日起每周三下午2點開始,講課地點：自動化所自動化大廈十三層第二會議室,電子信箱： huangxl06@mails.tsinghua.edu.cn,助教：黃曉霖,優(yōu)化方法基本分類,本門課程有關事宜,優(yōu)化問題基本分類,優(yōu)化問題基本分類,例、和優(yōu)化聯(lián)系非常密切

2、的一類問題（回歸、辨識、估計、訓練、學習、擬合、逼近…）,已知某個標量 和某個向量 之間若干一一對應的樣本數(shù)據(jù),要確定一個函數(shù) ，使在包含所有樣本數(shù)據(jù)的某個集合 里能夠用 描述 和 之間的對應關系，即使誤差 對任意的 都盡量小,基本方法：選

3、擇含有待定參數(shù)的函數(shù) ，通過極小 化某種樣本誤差確定待定參數(shù)得到所需函數(shù),常用 范數(shù)的樣本誤差,于是，最終要解決的是下述優(yōu)化問題,這是連續(xù)變量無約束優(yōu)化問題,對于采用 范數(shù)形成的優(yōu)化問題,為克服目標函數(shù)不可導的困難，可以等價轉換成下面的連續(xù)變量約束優(yōu)化問題,特別是，當 是 的線性函數(shù)時，即,上面的優(yōu)化問題

4、是線性規(guī)劃問題,一般選擇足夠多的基函數(shù) 使優(yōu)化問題,的樣本誤差任意小，這樣得到的模型在樣本集以外通常會產(chǎn)生很大的預報誤差，這就是所謂過度擬合或過度訓練問題。解決該問題的根本途經(jīng)是同時極小化基函數(shù)的個數(shù)，理論上要解決連續(xù)和離散變量混合的優(yōu)化問題,其中 是設定的正的權值,前面的例子包含了優(yōu)化問題最基本的類型,線性 與 非線性,無約束 與 有約束,連續(xù)變量 與 離散變量,后者相對于前

5、者在難度上均有質的改變,具有不確定性和動態(tài)特性的問題,轉換成上述問題,優(yōu)化方法基本分類,,,例,基本方法：從 之間的任一點出發(fā)，朝著能夠改進目標函數(shù)的方向搜索前進，直至目標函數(shù)不能改進,肯定能夠收斂到一個局部最優(yōu)解，不能保證全局最優(yōu),,,,,跳出局部陷阱的唯一途經(jīng)是在搜索過程中允許前進到目標函數(shù)值變差的點，如在 之間容許目標函數(shù)下降才有可能找到全局最優(yōu)解,由此產(chǎn)生新問題，無法保證算法收斂,為了使算法收斂

6、，只能引入不確定性，讓算法在任何一點以一定的概率前進到鄰近的某點，移動概率和相應點的目標函數(shù)值正相關，所以,由此產(chǎn)生的算法是結果不確定的算法,,,前面的例子包含了優(yōu)化方法最基本的類型,確定型搜索 與 不確定型搜索,前者是經(jīng)典的優(yōu)化教材介紹的主要內(nèi)容，后者包括模擬退火、禁忌搜索、遺傳算法、免疫算法、螞蟻算法等方法，一般統(tǒng)稱為智能算法,本課程主要討論基于確定性搜索的優(yōu)化方法,本門課程有關事宜,教材：運籌學（第二