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

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

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

學

主

要

內(nèi)

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

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

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

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

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

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

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

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

94線性搜索與信賴域方法習題，最速下降法講課、習題、實驗演示

104Newton法、共軛梯度法講課

114擬Newton條件、擬Newton法，習題講課，實驗演示

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

134最小二乘問題的信賴域方法，對Gauss-Newton矩陣的擬Newton修正，習題講課，實驗演示

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

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

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

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

184模式定理，復習講課，實驗演示

第一章

基本概念

一、學習目的通過本章的學習，

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

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

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

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

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

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

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

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

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

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

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

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

§2.3

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

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

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

線性搜索掌握線性搜索的迭代格式，理解相關(guān)基本概念，掌握確定搜索區(qū)間的進退法?！?.2

0.618法和Fibonacci法理解0.618法和Fibonacci法的基本思想，熟練掌握它們的算法步驟，了解二分法的基本思想?！?.3

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

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

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

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

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

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

0.618法和逐次插值法；3.

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

第四章

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

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

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

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

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

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

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

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

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

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

第五章

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

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

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

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

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

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

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

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

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

第六章

二次規(guī)劃

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

二次規(guī)劃了解二次規(guī)劃的實際應(yīng)用背景，掌握二次規(guī)劃的模型和相關(guān)概念。§6.2

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

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

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

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

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

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

第七章

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

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

二、課程內(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)點障礙罰函數(shù)法了解內(nèi)點障礙函數(shù)原理和適用范圍，掌握內(nèi)點罰函數(shù)法解約束優(yōu)化問題的算法，并會用該方法求解實際約束優(yōu)化問題。§7.4

序