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

《最優(yōu)化方法》教學(xué)大綱《最優(yōu)化方法》是信息與計(jì)算科學(xué)專業(yè)高等教育的重要專業(yè)選修課程。最優(yōu)化方法是近幾十年發(fā)展和形成的一門新興的應(yīng)用學(xué)科，它應(yīng)用數(shù)學(xué)、計(jì)算機(jī)科學(xué)以及其它科學(xué)的新成就研究各種系統(tǒng)和實(shí)際問題的優(yōu)化設(shè)計(jì)，控制和管理的途徑及策略，為決策者和管理者提供科學(xué)決策的理論依據(jù)和實(shí)際操作手段與方法，是集理論性與應(yīng)用性為一體的學(xué)科，它在生產(chǎn)管理和工程技術(shù)等許多領(lǐng)域中有廣泛的應(yīng)用背景與前景。設(shè)置本課程的目的是：通過對(duì)該課程的學(xué)習(xí)，培養(yǎng)學(xué)生運(yùn)用數(shù)學(xué)工具解決實(shí)際問題的能力。掌握最優(yōu)化的基本理論，了解求解各類最優(yōu)化問題的不同算法的優(yōu)缺點(diǎn)，了解常用算法的收斂性理論。培養(yǎng)學(xué)生具有比較熟練的數(shù)值計(jì)算能力和綜合運(yùn)用所學(xué)知識(shí)解決問題的能力，能熟練運(yùn)用所學(xué)算法和Matlab工具箱求解最優(yōu)化問題，為學(xué)生運(yùn)用所學(xué)知識(shí)解決有關(guān)實(shí)際最優(yōu)化問題奠定一定的理論基礎(chǔ)和計(jì)算技能。同時(shí)，通過結(jié)合課程的進(jìn)展，介紹學(xué)科發(fā)展前沿研究動(dòng)態(tài)，開闊學(xué)生眼界，啟迪他們的思維，使學(xué)生了解該學(xué)科國(guó)內(nèi)外有關(guān)最新研究成果。加深他們對(duì)最優(yōu)化理論和算法的理解和認(rèn)識(shí)。使之有利于提高學(xué)生的科學(xué)素質(zhì)和能力。并為從事最優(yōu)化理論與算法研究或最優(yōu)化方法解決實(shí)際問題打下堅(jiān)實(shí)的基礎(chǔ)。學(xué)習(xí)本課程的要求是：牢固地掌握最優(yōu)化的基本理論，常用算法的構(gòu)造途徑，并能在計(jì)算機(jī)上實(shí)現(xiàn)。通過各教學(xué)環(huán)節(jié)，本課程應(yīng)達(dá)到下列要求：理解凸集、凸函數(shù)等基本概念，了解本學(xué)科的研究?jī)?nèi)容、重要進(jìn)展及發(fā)展趨勢(shì)。掌握線性規(guī)劃的基本性質(zhì)、單純形法、對(duì)偶理論等線性規(guī)劃的基本理論和方法。理解有關(guān)算法收斂性的理論。掌握非線性最優(yōu)解所應(yīng)滿足的必要條件和充分條件；掌握常用的一維搜索算法。掌握常用的非線性最優(yōu)化問題的解析解法和直接解法，如最速下降法、共軛梯度法、牛頓法、最小二乘法、掌握可行方向法、罰函數(shù)法。了解進(jìn)化計(jì)算的思想與原理，掌握遺傳算法的方法和步驟，了解遺傳算法的收斂性質(zhì)。先修課程要求：數(shù)學(xué)分析，高等代數(shù)，數(shù)值分析，Matlab對(duì)象編程本課程計(jì)劃72學(xué)時(shí)，3學(xué)分。選用教材：孫文瑜，

徐成賢，朱德通編，最優(yōu)化方法，高等教育出版社，2004年07月。教學(xué)手段：多媒體講授為主，實(shí)驗(yàn)演示、習(xí)題課為輔考核方法：考試教學(xué)進(jìn)程安排表周次學(xué)時(shí)數(shù)教

學(xué)

主

要

內(nèi)

容教學(xué)方法備注14最優(yōu)化問題簡(jiǎn)介，凸集和凸函數(shù)講課

24最優(yōu)化條件，最優(yōu)化方法概述，Matlab最優(yōu)化工具箱簡(jiǎn)介講課，實(shí)驗(yàn)演示

34線性規(guī)劃的基本概念與性質(zhì)講課

44線性規(guī)劃的單純形法講課

54線性規(guī)劃的對(duì)偶與對(duì)偶單純形法講課

64線性規(guī)劃的內(nèi)點(diǎn)算法，例題與習(xí)題講課、習(xí)題、實(shí)驗(yàn)演示

74線性搜索，0．618法和Fibonacci法，逐次插值逼近法，精確線性搜索的收斂性講課

84不精確線性搜索方法，信賴域方法的思想、算法框架和收斂性，解信賴域子問題講課

94線性搜索與信賴域方法習(xí)題，最速下降法講課、習(xí)題、實(shí)驗(yàn)演示

104Newton法、共軛梯度法講課

114擬Newton條件、擬Newton法，習(xí)題講課，實(shí)驗(yàn)演示

124線性最小二乘問題的解法，非線性最小二乘問題的Gauss-Newton法講課

134最小二乘問題的信賴域方法，對(duì)Gauss-Newton矩陣的擬Newton修正，習(xí)題講課，實(shí)驗(yàn)演示

144二次規(guī)劃，等式約束二次規(guī)劃講課

154凸二次規(guī)劃的有效集方法，約束最優(yōu)化問題與最優(yōu)性條件講課

164約束優(yōu)化的罰函數(shù)法，內(nèi)點(diǎn)障礙罰函數(shù)法，講課

174序列二次規(guī)劃法、遺傳算法的概念、流程與實(shí)現(xiàn)，講課

184模式定理，復(fù)習(xí)講課，實(shí)驗(yàn)演示

第一章

基本概念

一、學(xué)習(xí)目的通過本章的學(xué)習(xí)，

了解最優(yōu)化問題的一些來源，理解建立合適的數(shù)學(xué)模型的重要性。理解最優(yōu)化方法的一些常見的名詞術(shù)語，了解優(yōu)化模型的一些常見分類。掌握最優(yōu)解存在的一階條件與二階條件，最優(yōu)化方法的一般結(jié)構(gòu)。初步了解MATLAB的最優(yōu)化工具箱。本章計(jì)劃8學(xué)時(shí)。

二、課程內(nèi)容本章主要介紹同最優(yōu)化方法和技術(shù)有關(guān)的基本概念和基本的理論，共分5節(jié)．§1.1

最優(yōu)化問題簡(jiǎn)介理解最優(yōu)化問題一般形式的數(shù)學(xué)模型，了解這種一般形式的模型同各種具體問題模型之間的關(guān)系和相互轉(zhuǎn)換；了解線性規(guī)劃、二次規(guī)劃、無約束最優(yōu)化、等式約束最優(yōu)化和不等式約束最優(yōu)化問題等幾種主要的最優(yōu)化問題的標(biāo)準(zhǔn)形式，熟練掌握最優(yōu)化問題的一些基本定義,如可行點(diǎn)、可行域、起作用約束、局部最優(yōu)解、整體最優(yōu)解等，以及它們之間的關(guān)系。§1.2

凸集和凸函數(shù)掌握凸集的定義，凸集同最優(yōu)化直接相關(guān)的性質(zhì)和特性，重點(diǎn)為在最優(yōu)化理論中起重要作用的凸集分離定理。熟練掌握一個(gè)函數(shù)是凸函數(shù)的一階充分必要條什，二階充分和必要條件，了解目標(biāo)函數(shù)為凸函數(shù)，可行域?yàn)橥辜耐挂?guī)劃問題，了解凸規(guī)劃問題的任何最優(yōu)解必為全局最優(yōu)解的證明，掌握可行域是凸集的條件和要求。§1.3

最優(yōu)性條件理解可行方向、下降方向的定義，熟練掌握最優(yōu)化問題最優(yōu)解的一階必要條件，又稱KKT條件；掌握在假定所有函數(shù)二階連續(xù)可微的條件下給出一般最優(yōu)化問題最優(yōu)解的二階必要條件和二階充分條件．§1.4

最優(yōu)化方法概述了解一般最優(yōu)化方法的基本特征和要求，掌握一般方法的迭代格式、評(píng)價(jià)一個(gè)點(diǎn)好壞約準(zhǔn)則和方法、終止迭代的準(zhǔn)則，了解衡量一個(gè)方法性能的收斂性和收斂速度?！?.5

Matlab最優(yōu)化工具箱簡(jiǎn)介了解Matlab最優(yōu)化工具箱的基本特點(diǎn)和使用方法。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）重點(diǎn)、難點(diǎn)1.

最優(yōu)化問題一般形式的數(shù)學(xué)模型以及相關(guān)基本概念；2.凸集分離定理，函數(shù)為凸函數(shù)的一階與二階條件;3.最優(yōu)解存在的一階與二階條件;4.最優(yōu)化方法的一般結(jié)構(gòu)。（二）教學(xué)手段課堂講授、課堂演示和習(xí)題課相結(jié)合四、思考與練習(xí)（注：具體形式由教師可自行調(diào)整。）第二章

線性規(guī)劃一、學(xué)習(xí)目的通過本章的學(xué)習(xí)，要求學(xué)生理解線性規(guī)劃模型的特征、基本概念及基本理論，理解單純形方法的基本思想,熟練掌握單純形方法，并能用于解決實(shí)際問題；掌握對(duì)偶理論及對(duì)偶單純形法，并會(huì)進(jìn)行靈敏度分析；理解線性規(guī)劃的內(nèi)點(diǎn)算法。本章計(jì)劃16學(xué)時(shí)。二、課程內(nèi)容本章主要介紹在現(xiàn)實(shí)生活．科學(xué)管理和科學(xué)實(shí)驗(yàn)中最常見、最有用的最優(yōu)化技術(shù)和方法——線性規(guī)劃，分四節(jié)分別介紹線性規(guī)劃的基本性質(zhì)、以及求解線性規(guī)劃的常用方法：?jiǎn)渭冃畏?、?duì)偶單純形法和內(nèi)點(diǎn)算法?！?.1

基本性質(zhì)掌握線性規(guī)劃的標(biāo)準(zhǔn)形式，了解它同各種不同形式的線性規(guī)劃問題之間的關(guān)系的相互轉(zhuǎn)換,

熟練掌握線性規(guī)則問題的基本性質(zhì)，理解線性規(guī)劃的基本解和基本可行解的概念和它們的代數(shù)表示、基本可行解和可行域頂點(diǎn)的等價(jià)性。§2.2

單純形法理解用于判定最優(yōu)解和確定新可行解的基本概念與方法，熟練掌握單純形法的具體步驟以及求解過程中使用的表格形式，了解用單純形法同計(jì)算機(jī)實(shí)現(xiàn)有關(guān)的三個(gè)問題和解決辦法。

§2.3

線性規(guī)劃的對(duì)偶與對(duì)偶單純形法熟練掌握標(biāo)準(zhǔn)型線性規(guī)劃問題的對(duì)偶問題的形式和一般形式線性規(guī)劃問題的對(duì)偶問題的形式，理解原規(guī)劃問題確定對(duì)偶問題的一般對(duì)偶關(guān)系和原則。掌握描述原問題和對(duì)偶問題的最優(yōu)解之間關(guān)系的弱對(duì)偶定理扣強(qiáng)對(duì)偶定理．§2.4

線性規(guī)劃的內(nèi)點(diǎn)算法了解原始對(duì)偶內(nèi)點(diǎn)算法的迭代序列產(chǎn)生的基本原理和過程，熟練掌握線性規(guī)劃的內(nèi)點(diǎn)算法，掌握確定初始可行內(nèi)點(diǎn)的方法和算法的計(jì)算復(fù)雜性。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）重點(diǎn)、難點(diǎn)1.線性規(guī)劃模型的特征、基本概念及基本理論；2.單純形方法的基本思想和方法；3.對(duì)偶理論及對(duì)偶單純形法；4.線性規(guī)劃的內(nèi)點(diǎn)算法（二）教學(xué)手段課堂講授、課堂演示和習(xí)題課相結(jié)合四、思考與練習(xí)P81：1(1),2(2),4（1,2），5（2），8（1，2），11（注：具體形式由教師自行掌握。）第三章

線性搜索與信賴域方法一、學(xué)習(xí)目的通過本章的學(xué)習(xí)，要求學(xué)生理解一維搜索算法的構(gòu)造方法；掌握兩個(gè)常用算法——0.618法和逐次插值法，能應(yīng)用這些算法求解一維搜索問題。了解精確線性搜索的收斂性；掌握常用的非線性搜索方法；理解信賴域方法的構(gòu)造思想，掌握信賴域方法的基本模型和算法的基本形式；了解信賴域方法的總體收斂性和解信賴域子問題。本章計(jì)劃10學(xué)時(shí)。二、課程內(nèi)容§3.1

線性搜索掌握線性搜索的迭代格式，理解相關(guān)基本概念，掌握確定搜索區(qū)間的進(jìn)退法。§3.2

0.618法和Fibonacci法理解0.618法和Fibonacci法的基本思想，熟練掌握它們的算法步驟，了解二分法的基本思想。§3.3

逐次插值逼近法理解三點(diǎn)二次插值、二點(diǎn)二次插值法的思想，熟練掌握它們的算法步驟，了解兩點(diǎn)二次插值的收斂速度，了解兩點(diǎn)三次插值的思想?！?.4

精確線性搜索方法的收斂性掌握精確線性搜索的無約束最優(yōu)化算法的一般形式，掌握精確線性搜索收斂的條件?！?.5

不精確線性搜索方法理解Goldstein準(zhǔn)則，掌握Goldstein不精確線性搜索算法；理解Wolfe準(zhǔn)則，掌握Wolfe不精確線性搜索算法；了解Armijo準(zhǔn)則。理解不精確線性搜索的一般步驟和收斂性能?！?.6

信賴域方法的思想和算法框架理解信賴域方法的思想，掌握信賴域方法的算法§3.7

信賴域方法的收斂性理解信賴域方法模型子問題的Cauchy點(diǎn)、精確解和近似解的關(guān)系，掌握信賴域方法的整體收斂性?！?.8

解信賴域子問題掌握解信賴域子問題的折線法和雙折線法的思想與算法。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）重點(diǎn)、難點(diǎn)1.線性搜索的迭代格式和確定搜索區(qū)間的進(jìn)退法；2.

0.618法和逐次插值法；3.

Goldstein不精確線性搜索法和Wolfe不精確線性搜索算法；4.信賴域方法的基本模型和算法的基本形式；5.信賴域方法的總體收斂性和解信賴域子問題。（二）教學(xué)手段課堂講授、課堂演示和習(xí)題課相結(jié)合四、思考與練習(xí)（注：具體形式由教師自行掌握。）

第四章

無約束最優(yōu)化方法一、學(xué)習(xí)目的

本章是全書最重要主要內(nèi)容之一，通過學(xué)習(xí)，要求學(xué)生理解最速下降法、共軛梯度法、Newton法和擬Newton法的算法構(gòu)造，熟練其掌握算法，并應(yīng)用這些方法求解無約束最優(yōu)化問題。本章計(jì)劃10學(xué)時(shí)。

二、課程內(nèi)容§4.1

最速下降法理解最速下降法的算法構(gòu)造思想和算法，掌握最速下降法的總體收斂性?！?.2Newton法掌握Newton法的算法，理解Newton法的收斂定理，了解精確線性搜索和Wolfe不精確線性搜索條件下帶步長(zhǎng)因子的Newton法的收斂性，并會(huì)用Newton法求解無約束優(yōu)化問題?！?.3

共軛梯度法理解共軛方向的概念，掌握共軛方向法求解無約束優(yōu)化問題的算法，了解在精確線性搜索情況下共軛方向法的收斂性，掌握共軛梯度法搜索方向的確定方法和共軛梯度法求解無約束正定二次函數(shù)優(yōu)化的算法，了解共軛梯度法的性質(zhì)和預(yù)處理共軛梯度法，掌握求解非二次函數(shù)最優(yōu)化問題的共軛梯度法，了解其收斂性?！?.4

擬牛頓法掌握擬牛頓條件和擬牛頓算法，了解擬牛頓法的優(yōu)缺點(diǎn)，DFP校正和BFGS校正。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）重點(diǎn)、難點(diǎn)1.

最速下降法的算法構(gòu)造與算法；2．

共軛方向的概念及其基本性質(zhì)；共軛梯度下降方法的算法；3．

牛頓法的算法構(gòu)造和一些常見的修正算法；4．?dāng)M牛頓條件及擬牛頓算法的一般形式；

DFP校正公式和BFGS校正公式。（二）教學(xué)手段課堂講授、課堂演示和習(xí)題課相結(jié)合四、思考與練習(xí)（注：具體形式由教師自行掌握。）

第五章

線性與非線性最小二乘問題一、學(xué)習(xí)目的本章主要介紹求解線性與非線性最小二乘問題的常用方法。通過本章的學(xué)習(xí)，要求學(xué)生了解最小二乘問題的來源，掌握線性最小二乘問題的解法，掌握求解非線性最小二乘問題的Gauss-Newton法、L—M算法和信賴域方法，了解對(duì)Gauss-Newton矩陣的擬牛頓修正算法。本章計(jì)劃8學(xué)時(shí)。二、課程內(nèi)容§5.1

線性最小二乘問題的解法復(fù)習(xí)線性最小二乘問題的解法，求線性最小二乘問題最優(yōu)解的正交分解算法，理解求線性等式約束線性最小二乘問題的思想，掌握線性等式約束最小二乘問題的正交分解算法和線性等式約束線性最小二乘問題的Lagrange乘子法，了解解線性不等式約束的線性最小二乘問題的解法?！?.2

非線性最小二乘的Gauss—Newton法理解非線性最小二乘的Gauss—Newton法的求解思想，掌握解非線性最小二乘的Gauss—Newton法的算法，了解該算法的收斂性算法的具體的特征，方法適用問題的類型，以及方法的不足，了解阻尼Gauss—Newton算法?！?.3

解非線性最小二乘問題的信賴域方法了解解非線性最小二乘問題的信賴域方法的推導(dǎo)過程，掌握該方法的算法，理解其收斂性和收斂速度?！?.4

對(duì)Gauss—Newton矩陣的擬牛頓修正了解根據(jù)問題結(jié)構(gòu)用擬牛頓法修正解非線性最小二乘問題的修正公式的推導(dǎo)原理和基本過程，掌握利用這些公式求解非線性最小二乘問題的擬牛頓型算法。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）重點(diǎn)、難點(diǎn)1.

線性最小二乘問題最優(yōu)解的正交分解算法；2.

解非線性最小二乘的Gauss—Newton法的算法；3.

解非線性最小二乘問題的信賴域方法。

（二）教學(xué)手段課堂講授和習(xí)題課相結(jié)合四、思考與練習(xí)（注：具體形式由教師自行掌握。）

第六章

二次規(guī)劃

一、學(xué)習(xí)目的本章簡(jiǎn)要介紹二次規(guī)劃的基本理論與算法，通過本章的學(xué)習(xí)，要求學(xué)生了解二次規(guī)劃的實(shí)際應(yīng)用背景，掌握二次規(guī)劃的模型和基本求解方法。本章計(jì)劃6學(xué)時(shí)。二、課程內(nèi)容§6.1

二次規(guī)劃了解二次規(guī)劃的實(shí)際應(yīng)用背景，掌握二次規(guī)劃的模型和相關(guān)概念?！?.2

等式約束二次規(guī)劃問題了解直接消去法的基本原理和公式推導(dǎo)，掌握等式約束二次規(guī)劃問題的KKT條件和KKT方程，熟練掌握解等式約束二次規(guī)劃問題的間接消去法，并應(yīng)用該方法求解實(shí)際問題?！?.3

凸二次規(guī)劃的有效集方法理解不等式約束二次規(guī)劃的有效集方法的原理，熟練掌握該方法的具體算法，并能用該方法求解實(shí)際問題。三、重點(diǎn)、難點(diǎn)提示和教學(xué)手段（一）重點(diǎn)、難點(diǎn)1.

二次規(guī)劃模型與相關(guān)概念；2.

求解等式約束二次規(guī)劃的間接消去法；3.

求解凸二次規(guī)劃的有效集方法。（二）教學(xué)手段課堂講授、課堂演示和習(xí)題課相結(jié)合

四、思考與練習(xí)（注：具體形式由教師自行掌握。）

第七章

約束最優(yōu)化的理論與方法

一、學(xué)習(xí)目的本章主要研究約束優(yōu)化問題的理論與求解方法，約束優(yōu)化問題的理論與最優(yōu)件條件是最優(yōu)化算法的基礎(chǔ)。通過本章的學(xué)習(xí)，要求學(xué)生掌握約束優(yōu)化問題的基本概念和KKT條件，熟練掌握函數(shù)法、序列二次規(guī)劃法解約束優(yōu)化問題的算法。本章計(jì)劃8學(xué)時(shí)。

二、課程內(nèi)容§7.1

約束最優(yōu)化問題與最優(yōu)性條件理解約束最優(yōu)化問題的積極約束條件（非積極約束約束）、可行性方向、非可行性方向和序列可行性方向的概念；熟練掌握約束優(yōu)化問題的一階最優(yōu)性條件（KKT條件），了解約束優(yōu)化問題的二階充分條件和必要條件。

§7.2

二次罰函數(shù)方法熟練掌握次罰函數(shù)方法的原理和算法，并應(yīng)用該方法求解約束優(yōu)化問題，了解其收斂性能?！?.3內(nèi)點(diǎn)障礙罰函數(shù)法了解內(nèi)點(diǎn)障礙函數(shù)原理和適用范圍，掌握內(nèi)點(diǎn)罰函數(shù)法解約束優(yōu)化問題的算法，并會(huì)用該方法求解實(shí)際約束優(yōu)化問題?！?.4

序