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

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

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

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

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

5、者在難度上均有質(zhì)的改變,具有不確定性和動(dòng)態(tài)特性的問題,轉(zhuǎ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)是在搜索過程中允許前進(jìn)到目標(biāo)函數(shù)值變差的點(diǎn)，如在 之間容許目標(biāo)函數(shù)下降才有可能找到全局最優(yōu)解,由此產(chǎn)生新問題，無法保證算法收斂,為了使算法收斂

6、，只能引入不確定性，讓算法在任何一點(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)化方法,本門課程有關(guān)事宜,教材：運(yùn)籌學(xué)（第二