最優(yōu)化方法第一次-PPT幻燈片

前言9/22/20231一、最優(yōu)化方法簡介

最優(yōu)化方法是一門古老而又年青的學科。這門學科的源頭可以追溯到17世紀法國數(shù)學家拉格朗日關于求解多元函數(shù)極值的Lagrange乘數(shù)法。19世紀柯西引入了最速下降法求解非線性規(guī)劃問題。9/22/20232直到20世紀四、五十年代，最優(yōu)化理論的研究才出現(xiàn)重大進展。1947年丹奇格提出了求解線性規(guī)劃的單純形法；1951年庫恩和塔克給出了非線性規(guī)劃的最優(yōu)性條件即Kuhn-Tucker條件。20世紀六十年代，隨著計算機技術的發(fā)展，各種最優(yōu)化算法應運而生,9/22/20233的決策序列，則歸結為“動態(tài)規(guī)劃”；如果可行集是無窮維空間中的連續(xù)子集，則歸結為“最優(yōu)控制”。線性規(guī)劃與非線性規(guī)劃是最優(yōu)化方法中最基本、最重要的兩類問題。一般來說，各優(yōu)化分支有其相應的應用領域。線性規(guī)劃、網(wǎng)絡規(guī)劃、動態(tài)規(guī)劃通常用于管理與決策科學；9/22/20236最優(yōu)控制常用于控制工程；非線性規(guī)劃則更多地用于工程優(yōu)化設計。前面提到的算法是最優(yōu)化的基本方法，它們簡單易行，對于性態(tài)優(yōu)良的一般函數(shù)，優(yōu)化效果較好。但這些經(jīng)典的方法是以傳統(tǒng)微積分為基礎的,不可避免地帶有某種局限局限性，主要表現(xiàn)為：①大多數(shù)傳統(tǒng)優(yōu)化方法僅9/22/20237能計算目標函數(shù)的局部最優(yōu)點，不能保證找到全局最優(yōu)解。對于多峰值函數(shù)，這些方法往往由于過分追求“下降”而陷于局部最優(yōu)解；②許多傳統(tǒng)優(yōu)化方法對目標函數(shù)的光滑性、凹凸性等有較高的要求，對于離散型函數(shù)、隨機型函數(shù)基本上無能為力。20世紀六、七十年代以來，人們9/22/20238將人工智能技術和生物進化機理引入最優(yōu)化方法，形成了一批完全不同于傳統(tǒng)優(yōu)化方法、令人耳目一新的現(xiàn)代優(yōu)化方法。例如模擬退火、神經(jīng)網(wǎng)絡、遺傳算法、粒子群算法、蟻群算法、免疫算法、協(xié)同進化算法等，已被廣泛應用于函數(shù)優(yōu)化、組合優(yōu)化、自動控制、圖像與信號處理等領域。9/22/20239二、最優(yōu)化方法課程主要內(nèi)容

本門課程的主要內(nèi)容為常用經(jīng)典優(yōu)化方法、現(xiàn)代優(yōu)化方法簡介和運籌優(yōu)化軟件Lingo簡介。經(jīng)典優(yōu)化方法包括：1.常用的一維搜索方法——黃金分割法和非精確搜索法；2.最速下降法、共軛梯度法；9/22/2023103.牛頓法；4.變尺度法——DFP和BFGS；5.約束優(yōu)化方法——梯度法、罰函數(shù)法、乘子法。現(xiàn)代優(yōu)化算法僅簡要介紹模擬退火算法。Lingo軟件只介紹基本功能與基本操作。9/22/202311三、授課方式與課程要求

1.授課方式——自學+提問+講解首先由學生按教師要求對下次授課內(nèi)容進行自學，然后教師在課堂上逐一提問，最后由教師對本次授課內(nèi)容進行講解、總結，布置作業(yè)。學生成績根據(jù)平時回答問題、作業(yè)和編程及書面考試情況綜合評判。9/22/2023122.課程要求希望掌握優(yōu)化計算數(shù)學工具的工程技術人員可以分為下列三個層次：①不愿意花精力了解優(yōu)化計算的數(shù)學原理，只要能熟練使用一些現(xiàn)成的優(yōu)化數(shù)學軟件，如Lingo、Matlab優(yōu)化工具箱等；②希望大致明白優(yōu)化計算的數(shù)學9/22/202313原理，了解各種算法的優(yōu)缺點及適用范圍，對計算結果有一定的分析判斷能力，讓自己成為一個有數(shù)學素養(yǎng)的優(yōu)化工具使用者。但也不打算自己編制算法程序；③希望透徹地了解優(yōu)化計算的數(shù)學原理，詳細掌握算法的計算步驟，由自己編制質量較高的優(yōu)化程序。9/22/202314本課程對學生的具體要求為：①理解最優(yōu)化的基本概念、算法原理和算法結構；②熟悉幾種常用的經(jīng)典優(yōu)化算法，知曉其優(yōu)缺點及適用范圍；③了解幾種現(xiàn)代智能優(yōu)化算法的基本原理和應用領域；④掌握Lingo的基本功能。9/22/2023153.編程要求基于下列理由，本門課要求學生對2~3個基本優(yōu)化算法(如一維搜索、梯度法、變尺度法、模擬退火)編制出通用程序，編程工具建議采用C++、Matlab或Maple。①最優(yōu)化方法是一門實踐性特別強的課程，算法眾多。如果對于一個9/22/202316算法僅了解其數(shù)學原理，不將算法編制成高質量的程序，那么就不能保證你已對此算法有全面、正確的理解，對此算法的優(yōu)缺點、適用范圍就缺乏深刻的體會，更無法體驗到最優(yōu)化方法的精髓；②在一些大型計算中，可能要求優(yōu)化計算是“實時計算”，即優(yōu)化計算9/22/202317從前一計算環(huán)節(jié)獲取參數(shù)，計算結果后立即傳送給后一環(huán)節(jié)，所有這些計算都是在內(nèi)存中進行的。顯然，現(xiàn)成的工具軟件對此無能為力；③Lingo,Matlab優(yōu)化工具箱等優(yōu)化軟件功能的確強大，但它們也不是萬能的。首先，對于某些優(yōu)化問題，這些工具軟件可能都求不出最優(yōu)解；9/22/202318其次不能保證對任何優(yōu)化問題都有現(xiàn)成的工具軟件，實際上，許多現(xiàn)代優(yōu)化方法都不可能編制成通用軟件；④熟練使用相關科技軟件、具有一定的編程水平是工科研究生所必須具有的素養(yǎng)，而編程經(jīng)驗和水平不是憑一朝一夕就可以提高的，要靠大量的編程實踐和不斷地日積月累。9/22/2023194.參考書目①粟塔山，最優(yōu)化計算原理與算法程序設計，國防科技大學出版社；②謝金星，優(yōu)化建模與Lingo軟件，清華大學出版社。信箱：austmathmodeling@163.comMM：matlabmaple9/22/202320第1次自學內(nèi)容

1.梯度的定義、幾何意義；等高線的概念，等高線與梯度的關系；梯度為零的點與極值點的關系。2.Hesse矩陣的概念；Hesse矩陣的正定性與函數(shù)曲面凹凸性的關系。3.設A為n階對稱矩陣，b,X為n元列向量，c為標量，對二次函數(shù)9/22/202321求和。

4.寫出二元函數(shù)的二階Taylor展式的矩陣形式。5.凸集的概念。6.凸函數(shù)及其兩個充要條件；凸函數(shù)的極值點有什么特點？9/22/202322第一部分經(jīng)典優(yōu)化方法9/22/202323Ch1最優(yōu)化的基本概念9/22/202324一、預備知識

1.梯度定義1.1對n元可微函數(shù)向量9/22/202325稱為f在X處的梯度，記為

或，稱為Hamilton算子或梯度算子。從幾何上講，的方向是f在X處上升最快的方向，的模是f在X處上升最快的速率。若，則函數(shù)曲面在X處的切平面是水平的。9/22/2023262.

二階導數(shù)矩陣定義1.2設n元函數(shù)

具有二階連續(xù)偏導數(shù)，則f的所有二階偏導數(shù)構成的矩陣9/22/202327稱為f在X處的二階導數(shù)矩陣或Hessain矩陣，記為。

顯然，是一個對稱矩陣。在幾何上，反映了函數(shù)曲面的彎曲方向。若正定，則函數(shù)曲面向上彎曲(凹)；若負定，則函數(shù)曲面向下彎曲(凸)。9/22/202328例1.1設A為n階對稱矩陣，b,X為n元列向量，c為標量，對二次函數(shù)求和。

解以二元函數(shù)為例計算。9/22/2023299/22/2023309/22/2023319/22/202332即對可將算子理解為對向量函數(shù)的一階、二階導數(shù)，易得9/22/2023333.

n元函數(shù)的二階Taylor展式一元函數(shù)的Taylor展式：其中9/22/202334二元函數(shù)的Taylor展式：9/22/202335其中9/22/202336二元函數(shù)的二階Taylor展式：9/22/202337

若引入矩陣記號

9/22/202338則n元函數(shù)的二階Taylor展式與二元函數(shù)的二階Taylor展式形式類似。9/22/2023394.

凸集與凸函數(shù)定義1.3設，若S中任兩點的連線都屬于S，即對任意，均有，則稱S為一個凸集。定義1.4設為定義在凸集S上的函數(shù)，若對任意，均有9/22/202340則稱為S上的凸函數(shù)。若上式改為嚴格不等式，則稱為S上的嚴格凸函數(shù)。9/22/202341定理1.1(一階判別條件