《最優(yōu)化方法雙語》課程教學(xué)大綱

《最優(yōu)化方法（雙語）》課程教學(xué)大綱一、課程基本信息課程代碼：102193課程名稱：最優(yōu)化方法（雙語）英文名稱：Optimizationmethods課程類別：專業(yè)課學(xué)時：48學(xué)分：3適用對象：大二、大三學(xué)生考核方式：考試先修課程：概率論，數(shù)理統(tǒng)計(jì)，線性代數(shù)二、課程簡介本課程介紹與優(yōu)化問題相關(guān)的線性規(guī)劃，非線性規(guī)劃等各種算法，包括：單純形法，最速下降法，牛頓法，擬牛頓法，共輾梯度法，以及線性規(guī)劃的約束條件等內(nèi)容。Thiscoursewillintroducelinearprogrammingmethods,nonlinearprogrammingmethods,including:simplexmethod,steepestdescentmethod,Newton'smethod,quasiNewtonmethod,conjugateGradientmethodetc.,whicharehighlyrelatedwithoptimizationproblemsinpractice.Theoreticalanalysisaboutoptimizationconditionswillalsobeinvestigatedinthiscourse.三、課程性質(zhì)與教學(xué)目的本課程是面向大二應(yīng)用統(tǒng)計(jì)專業(yè)學(xué)生，大三數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)開設(shè)的專業(yè)限修課，可作為其他專業(yè)學(xué)生的選修課。課程目的是介紹與優(yōu)化問題密切相關(guān)的各種優(yōu)化算法，培養(yǎng)和增強(qiáng)學(xué)生解決實(shí)際數(shù)據(jù)分析問題的能力。課程思政總體思路：最優(yōu)化方法如今廣泛應(yīng)用于人工智能，運(yùn)籌，物流，國防等領(lǐng)域。英國1947年最早將最優(yōu)化方法應(yīng)用于戰(zhàn)爭中，掌握了主動權(quán)?，F(xiàn)在世界局勢紛繁復(fù)雜，如果我們能夠利用最新的最優(yōu)化方法，這將有助于我國在人工智能，國防等領(lǐng)域搶占先機(jī)，爭奪話語權(quán)。四、教學(xué)內(nèi)容及要求第一章最優(yōu)化問題分類（一）目的與要求.介紹數(shù)學(xué)專業(yè)英語，不同類型的決策問題，本書的記號，最優(yōu)化的問題分類和模型，基本框架及相關(guān)基礎(chǔ)知識.了解本書所要介紹的內(nèi)容以及數(shù)據(jù)集（二）教學(xué)內(nèi)容第一節(jié)數(shù)學(xué)專業(yè)英語.主要內(nèi)容數(shù)學(xué)專業(yè)英語的表達(dá)方式.基本概念和知識點(diǎn)數(shù)學(xué)專業(yè)英語，最優(yōu)化問題分類.問題與應(yīng)用（能力要求）了解數(shù)學(xué)專業(yè)英語的表達(dá)方式，優(yōu)化問題分類第二節(jié)本書內(nèi)容安排.主要內(nèi)容介紹數(shù)學(xué)專業(yè)英語，最優(yōu)化問題分類.基本概念和知識點(diǎn)不同分支數(shù)學(xué)的英文表達(dá)方式，優(yōu)化問題的分類.問題與應(yīng)用（能力要求）對實(shí)踐問題能夠進(jìn)行建模分類。（三）思考與實(shí)踐思考最優(yōu)化方法所涉及的基礎(chǔ)預(yù)備知識。（四）教學(xué)方法與手段課堂講授第二章凸優(yōu)化（一）目的與要求.介紹凸優(yōu)化的相關(guān)概念，凸集，閉集的定義，以及上圖，方向?qū)?shù)等概念.掌握凸集凸函數(shù)的判別方式，上圖的使用方法以及計(jì)算方向?qū)?shù)的方法（二）教學(xué)內(nèi)容第一節(jié)最優(yōu)化開展簡史.主要內(nèi)容最優(yōu)化的開展歷程.基本概念和知識點(diǎn)80年代以前的開展歷程和80年代以后的開展歷程.問題與應(yīng)用（能力要求）掌握最優(yōu)化的開展歷程第二節(jié)凸集，閉集，閉包.主要內(nèi)容凸集，凸函數(shù)的定義及判別方法，閉包的含義.基本概念和知識點(diǎn)凸集，凸函數(shù)，閉包.問題與應(yīng)用（能力要求）掌握凸集、凸函數(shù)的判別方法第三節(jié)上圖，方向?qū)?shù).主要內(nèi)容上圖的含義和方向?qū)?shù)的定義，計(jì)算方法.基本概念和知識點(diǎn)上圖，方向?qū)?shù).問題與應(yīng)用（能力要求）會構(gòu)建上圖，計(jì)算方向?qū)?shù)。（三）思考與實(shí)踐上圖與凸函數(shù)的關(guān)系，方向?qū)?shù)與導(dǎo)數(shù)的關(guān)系（四）教學(xué)方法與手段課堂講授第三章一維優(yōu)化問題（一）目的與要求掌握可微，凸性，一維優(yōu)化問題的最優(yōu)性條件，牛頓法，搜索方法等優(yōu)化方法（二）教學(xué)內(nèi)容第一節(jié)可微與凸性.主要內(nèi)容凸函數(shù)的一階二階判別條件，仿射包，仿射集的概念。.基本概念和知識點(diǎn)凸函數(shù)的判別條件，仿射包。.問題與應(yīng)用（能力要求）掌握凸函數(shù)一階二階判別條件第二節(jié)最優(yōu)性條件.主要內(nèi)容局部極值點(diǎn)，全局極值點(diǎn)，駐點(diǎn)，關(guān)鍵點(diǎn)，鞍點(diǎn).基本概念和知識點(diǎn)極值點(diǎn)，駐點(diǎn)，鞍點(diǎn).問題與應(yīng)用（能力要求）掌握局部極值點(diǎn)和全局極值點(diǎn)的判別方法，會判定鞍點(diǎn)。第三節(jié)牛頓法.主要內(nèi)容牛頓法的原理和計(jì)算步驟.基本概念和知識點(diǎn)牛頓法的一階迭代公式和二階迭代公式.問題與應(yīng)用（能力要求）掌握牛頓法的計(jì)算步驟，優(yōu)缺點(diǎn)。第四節(jié)搜索方法1-主要內(nèi)容搜索問題模型，單峰函數(shù)，黃金分割法，F(xiàn)ibonacci法，拋物線內(nèi)插法.基本概念和知識點(diǎn)黃金分割法，F(xiàn)ibonacci法.問題與應(yīng)用（能力要求）掌握黃金分割法，F(xiàn)ibonacci法的計(jì)算步驟和異同。（三）思考與實(shí)踐思考黃金分割法，F(xiàn)ibonacci法的先決條件和收斂速率。（四）教學(xué)方法與手段課堂講授第四章線性規(guī)劃（一）目的與要求理解和掌握原問題和對偶問題的關(guān)系，掌握常見的單純性方法:兩階段法,大M法，線性規(guī)劃的最優(yōu)性條件，會進(jìn)行靈敏度分析（二）教學(xué)內(nèi)容第一節(jié)原問題與對偶問題.主要內(nèi)容介紹原問題和對偶問題兩者之間的關(guān)系，原問題和對偶問題的對應(yīng)關(guān)系.基本概念和知識點(diǎn)原問題，對偶問題.問題與應(yīng)用（能力要求）能夠?qū)懗鲈瓎栴}的對偶問題，掌握對偶問題的約束條件與原問題的相應(yīng)約束之間的關(guān)系。第二節(jié)單純形法.主要內(nèi)容介紹松弛變量和人工變量的作用，介紹解決線性規(guī)劃問題的兩階段法,大M法.基本概念和知識點(diǎn)進(jìn)基變量，離基變量，兩階段法，大M法，人工變量，松弛變量.問題與應(yīng)用（能力要求）明白單純形法的求解思路，掌握線性規(guī)劃問題的求解方法：兩階段法，大M法，會通過引入松弛變量和人工變量來轉(zhuǎn)化原問題，并采用相應(yīng)的方法求解。第三節(jié)最優(yōu)性條件.主要內(nèi)容KKT條件，互補(bǔ)松弛條件.基本概念和知識點(diǎn)KKT點(diǎn).問題與應(yīng)用（能力要求）掌握如何運(yùn)用互補(bǔ)松弛條件，會判定駐點(diǎn)是否是KKT點(diǎn)第四節(jié)靈敏度分析.主要內(nèi)容靈敏度分析涉及的五大領(lǐng)域.基本概念和知識點(diǎn)技術(shù)系數(shù).問題與應(yīng)用（能力要求）當(dāng)改變系數(shù)矩陣A,右端向量b,目標(biāo)函數(shù)系數(shù)c,增加額外約束，增加新的變量時，能夠通過原優(yōu)化解來求解新問題的解。（三）思考與實(shí)踐思考進(jìn)基變量和離基變量對應(yīng)的幾何意義，KKT條件，互補(bǔ)松弛條件。（四）教學(xué)方法與手段課堂講授第五章無約束優(yōu)化問題（一）目的與要求介紹無約束優(yōu)化問題的最優(yōu)性條件，最速下降法，牛頓法，阻尼牛頓法，直線搜索，擬牛頓法，共軌梯度法，最小二乘法等方法（二）教學(xué)內(nèi)容第一節(jié)最優(yōu)性條件.主要內(nèi)容極值點(diǎn)，最值點(diǎn)的判別方法.基本概念和知識點(diǎn)方向?qū)?shù)，矩陣的正定、負(fù)定、不定，希爾維斯特準(zhǔn)那么.問題與應(yīng)用（能力要求）掌握無約束優(yōu)化問題的極值求解方法，會通過二階矩陣來判定所求的駐點(diǎn)是否是極值點(diǎn)第二節(jié)最速下降法.主要內(nèi)容介紹最速下降法的計(jì)算法，鋸齒現(xiàn)象.基本概念和知識點(diǎn)最速下降方向，鋸齒現(xiàn)象.問題與應(yīng)用（能力要求）掌握最速下降法的計(jì)算方法，優(yōu)缺點(diǎn)，鋸齒現(xiàn)象的產(chǎn)生原因。第三節(jié)牛頓法.主要內(nèi)容介紹收斂速率的概念，牛頓法和阻尼牛頓法的迭代思想.基本概念和知識點(diǎn)收斂速率，牛頓方向，阻尼牛頓法.問題與應(yīng)用（能力要求）掌握線性收斂，二次收斂，超線性收斂的區(qū)別，掌握牛頓法，阻尼牛頓法的計(jì)算方法，優(yōu)缺點(diǎn)。第四節(jié)直線搜索和擬牛頓法.主要內(nèi)容介紹直線搜索的兩大關(guān)鍵因素，介紹Armijo直線搜索，阻尼牛頓法的迭代思想.基本概念和知識點(diǎn)直線搜索，Armijo直線搜索，阻尼牛頓法，DFP算法，BFGS算法，擬牛頓條件.問題與應(yīng)用（能力要求）掌握Armijo直線搜索的策略，掌握DFP算法，BFGS算法的計(jì)算方法第五節(jié)共聊梯度法.主要內(nèi)容介紹共粗梯度法的原理，F(xiàn)R方法，PR方法的迭代公式.基本概念和知識點(diǎn)共加方向，F(xiàn)R方法，PR方法.問題與應(yīng)用（能力要求）掌握FR方法，PR方法的計(jì)算步驟，了解共軌梯度法的優(yōu)缺點(diǎn)第六節(jié)最小二乘法.主要內(nèi)容介紹最小二乘法的原理和計(jì)算思路，優(yōu)缺點(diǎn).基本概念和知識點(diǎn)最小二乘，線性回歸.問題與應(yīng)用（能力要求）掌握最小二乘法的計(jì)算方法（三）思考與實(shí)踐思考無約束優(yōu)化問題常見迭代方法：最速下降法，牛頓法，共加梯度法的優(yōu)缺點(diǎn)。（四）教學(xué)方法與手段課堂講授第六章約束規(guī)劃（一）目的與要求介紹約束規(guī)劃問題的最優(yōu)性條件，可行方向法，罰函數(shù)法，梯度投影法,Frank-Wolf方法，起作用集方法。（二）教學(xué)內(nèi)容第一節(jié)最優(yōu)性條件.主要內(nèi)容介紹線性約束和非線性約束的KT條件，LICQ.基本概念和知識點(diǎn)一階條件，二階條件，LICQo.問題與應(yīng)用（能力要求）掌握KT點(diǎn)的求法第二節(jié)可行方向法.主要內(nèi)容介紹可行方向，線性，非線性情形的Zoutendijk迭代方法.基本概念和知識點(diǎn)可行方向，Zoutendijk方法.問題與應(yīng)用（能力要求）掌握Zoutendijk方法的計(jì)算步驟第三節(jié)罰函數(shù)法.主要內(nèi)容介紹內(nèi)點(diǎn)法，外點(diǎn)法，乘子法.基本概念和知識點(diǎn)內(nèi)點(diǎn)法，外點(diǎn)法，乘子法.問題與應(yīng)用（能力要求）掌握內(nèi)點(diǎn)法，外點(diǎn)法，乘子法的計(jì)算步驟，明白三種罰函數(shù)的適用范圍第四節(jié)梯度投影法.主要內(nèi)容介紹投影矩陣，梯度投影法的原理和計(jì)算步驟.基本概念和知識點(diǎn)投影矩陣，梯度投影法.問題與應(yīng)用（能力要求）掌握梯度投影法的計(jì)算方法，適用領(lǐng)域第五節(jié)Frank-Wolf方法.主要內(nèi)容介紹Frank-Wolfe方法的計(jì)算步驟，優(yōu)缺點(diǎn)，適用范圍.基本概念和知識點(diǎn)Frank-Wolfe方法.問題與應(yīng)用（能力要求）掌握Frank-Wolfe的計(jì)算方法，迭代步驟（三）思考與實(shí)踐思考約束規(guī)劃問題的各種迭代方法：可行方向法，罰函數(shù)法，梯度投影法,Frank-Wolfe方法的區(qū)別和原理。（四）教學(xué)方法與手段課堂講授五'各教學(xué)環(huán)節(jié)學(xué)時分配

教學(xué)環(huán)節(jié)教學(xué)時課程內(nèi)容講課習(xí)題課討論課實(shí)驗(yàn)其他教學(xué)環(huán)節(jié)小計(jì)第一章2/1周0課堂隨時討論第一早2/1周0課堂隨時討論第三章9/3周0課堂隨時討論第四章9/3周0課堂隨時討論第五章12/4周0課堂隨時討論第六章14/4周0課堂隨時討論合計(jì)48/16周六、推薦教材和教學(xué)參考資源1.陳寶林，最優(yōu)化理論與算法(第二版).清華大學(xué)出版社，2005.2.MokhtarS.Bazar