最優(yōu)化方法

《最優(yōu)化方法》介紹最優(yōu)化模型的理論與計(jì)算方法，其中理論包括對(duì)偶理論、非線性規(guī)劃的最優(yōu)性理論、非線性半定規(guī)劃的最優(yōu)性理論、非線性二階錐優(yōu)化的最優(yōu)性理論；計(jì)算方法包括無(wú)約束優(yōu)化的線搜索方法、線性規(guī)劃的單純形方法和內(nèi)點(diǎn)方法、非線性規(guī)劃的序列二次規(guī)劃方法、非線性規(guī)劃的增廣Lagrange方法、非線性半定規(guī)劃的增廣Lagrange方法、非線性二階錐優(yōu)化的增廣Lagrange方法以及整數(shù)規(guī)劃的Lagrange松弛方法?！蹲顑?yōu)化方法》注重知識(shí)的準(zhǔn)確性、系統(tǒng)性和算法論述的完整性，是學(xué)習(xí)最優(yōu)化方法的一本入門書。

《最優(yōu)化方法》可用作高等院校數(shù)學(xué)系高年級(jí)本科生和管理專業(yè)研究生的教材，也可作為相關(guān)工程技術(shù)人員的參考用書。

前言

第1章 變分分析的相關(guān)素材

1.1 凸分析素材

1.1.1 凸集合

1.1.2 凸函數(shù)的閉包

1.1.3 共軛函數(shù)

1.1.4 次可微性

1.2 集值映射的極限

1.3 方向?qū)?shù)

1.4 集合的切錐與二階切集

1.4.1 集合的切錐

1.4.2 二階切集

1.4.3 函數(shù)水平集的切錐與二階切集

1.4.4 負(fù)卦限錐的切錐與二階切集

1.5 有限維系統(tǒng)的穩(wěn)定性

1.5.1線性系統(tǒng)

1.5.2 集合約束的線性系統(tǒng)

1.5.3 集合約束的非線性系統(tǒng)

第2章 無(wú)約束優(yōu)化

2.1 引言

2.2 線搜索方法

2.2.1 線搜索原則

2.2.2 下降方法的收斂性

2.3 最速下降方法

2.3.1 最速下降方法的全局收斂性

2.3.2 最速下降方法的收斂速度

2.4 Newton法

2.4.1 經(jīng)典Newton法

2.4.2 帶線搜索的：Newton法

2.4.3 自協(xié)調(diào)函數(shù)的Newton法

2.5 擬Newton法

2.5.1 擬Newton方程和著名的擬Newton公式

2.5.2 擬Newton法求解凸二次規(guī)劃

2.5.3 Dixon定理

2.5.4 DFP方法的收斂性

2.5.5 BFGS方法的收斂性

2.5.6 限制Broyden類方法的收斂性

2.6 共軛梯度方法

2.6.1 共軛方向

2.6.2 共軛梯度方法求解二次規(guī)劃

2.6.3 求解無(wú)約束優(yōu)化問(wèn)題的FR方法

2.7 信賴域方法

2.7.1 信賴域基本算法

2.7.2 Cauchy點(diǎn)與模型下降

2.7.3 信賴域算法的收斂性

第3章 線性規(guī)劃

3.1 線性規(guī)劃問(wèn)題及其性質(zhì)

3.2 單純形法

3.3 Bland原則

3.4 線性規(guī)劃的對(duì)偶定理

3.5 對(duì)偶單純形方法

3.6 線性規(guī)劃的Karmakar內(nèi)點(diǎn)法

3.6.1 解析中心與勢(shì)函數(shù)

3.6.2 線性規(guī)劃的勢(shì)函數(shù)

3.6.3 線性規(guī)劃的中心路徑

3.6.4 線性規(guī)劃的Karmarkar算法

第4章 對(duì)偶理論

4.1 共軛對(duì)偶性

4.2 Lagrange對(duì)偶性

4.3 對(duì)偶理論的應(yīng)用

第5章 最優(yōu)性條件

5.1 一階最優(yōu)性條件

5.2 廣義Lagrange乘子

5.3 二階最優(yōu)性條件

第6章 增廣Lagrange函數(shù)方法

6.1 懲罰與障礙函數(shù)方法

6.1.1 懲罰函數(shù)方法

6.1.2 經(jīng)典障礙函數(shù)方法

6.2 增廣Lagrange函數(shù)方法

6.2.1 增廣Lagrange函數(shù)

6.2.2 Bertsekas的經(jīng)典結(jié)果

6.2.3 對(duì)偶收斂率

第7章 序列二次規(guī)劃（SQP）方法

7.1 等式約束優(yōu)化問(wèn)題的局部方法

7.1.1 Newton法

7.1.2 KKT系統(tǒng)

7.1.3 既約Hesse陣方法

7.2 一般約束優(yōu)化問(wèn)題的局部方法

7.2.1 序列二次規(guī)劃方法

7.2.2 原始.對(duì)偶二次收斂性

7.2.3 原始超線性收斂性

7.3 線搜索全局方法

7.3.1 不可微懲罰函數(shù)

7.3.2 線搜索SQP方法

7.3.3 Maratos效應(yīng)

參考文獻(xiàn)

最優(yōu)化方法（也稱做運(yùn)籌學(xué)方法）是近幾十年形成的，它主要運(yùn)用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)。

最優(yōu)化方法的主要研究對(duì)象是各種有組織系統(tǒng)的管理問(wèn)題及其生產(chǎn)經(jīng)營(yíng)活動(dòng)。最優(yōu)化方法的目的在于針對(duì)所研究的系統(tǒng)，求得一個(gè)合理運(yùn)用人力、物力和財(cái)力的最佳方案，發(fā)揮和提高系統(tǒng)的效能及效益，最終達(dá)到系統(tǒng)的最優(yōu)目標(biāo)。 實(shí)踐表明，隨著科學(xué)技術(shù)的日益進(jìn)步和生產(chǎn)經(jīng)營(yíng)的日益發(fā)展，最優(yōu)化方法已成為現(xiàn)代管理科學(xué)的重要理論基礎(chǔ)和不可缺少的方法，被人們廣泛地應(yīng)用到公共管理、經(jīng)濟(jì)管理、工程建設(shè)、國(guó)防等各個(gè)領(lǐng)域，發(fā)揮著越來(lái)越重要的作用。本章將介紹最優(yōu)化方法的研究對(duì)象、特點(diǎn)，以及最優(yōu)化方法模型的建立和模型的分析、求解、應(yīng)用。主要是線性規(guī)劃問(wèn)題的模型、求解（線性規(guī)劃問(wèn)題的單純形解法）及其應(yīng)用――運(yùn)輸問(wèn)題；以及動(dòng)態(tài)規(guī)劃的模型、求解、應(yīng)用――資源分配問(wèn)題。

最優(yōu)化方法

1、微分學(xué)中求極值

2、無(wú)約束最優(yōu)化問(wèn)題

3、常用微分公式

4、凸集與凸函數(shù)

5、等式約束最優(yōu)化問(wèn)題

6、不等式約束最優(yōu)化問(wèn)題

7、變分學(xué)中求極值

最優(yōu)化方法數(shù)學(xué)意義

為了達(dá)到最優(yōu)化目的所提出的各種求解方法。從數(shù)學(xué)意義上說(shuō)，最優(yōu)化方法是一種求極值的方法，即在一組約束為等式或不等式的條件下，使系統(tǒng)的目標(biāo)函數(shù)達(dá)到極值，即最大值或最小值。從經(jīng)濟(jì)意義上說(shuō)，是在一定的人力、物力和財(cái)力資源條件下，使經(jīng)濟(jì)效果達(dá)到最大（如產(chǎn)值、利潤(rùn)），或者在完成規(guī)定的生產(chǎn)或經(jīng)濟(jì)任務(wù)下，使投入的人力、物力和財(cái)力等資源為最少。

最優(yōu)化方法發(fā)展簡(jiǎn)史

公元前 500年古希臘在討論建筑美學(xué)中就已發(fā)現(xiàn)了長(zhǎng)方形長(zhǎng)與寬的最佳比例為0.618,稱為黃金分割比。其倒數(shù)至今在優(yōu)選法中仍得到廣泛應(yīng)用。在微積分出現(xiàn)以前，已有許多學(xué)者開(kāi)始研究用數(shù)學(xué)方法解決最優(yōu)化問(wèn)題。例如阿基米德證明：給定周長(zhǎng)，圓所包圍的面積為最大。這就是歐洲古代城堡幾乎都建成圓形的原因。但是最優(yōu)化方法真正形成為科學(xué)方法則在17世紀(jì)以后。17世紀(jì)，I.牛頓和G.W.萊布尼茨在他們所創(chuàng)建的微積分中，提出求解具有多個(gè)自變量的實(shí)值函數(shù)的最大值和最小值的方法。以后又進(jìn)一步討論具有未知函數(shù)的函數(shù)極值，從而形成變分法。這一時(shí)期的最優(yōu)化方法可以稱為古典最優(yōu)化方法。第二次世界大戰(zhàn)前后，由于軍事上的需要和科學(xué)技術(shù)和生產(chǎn)的迅速發(fā)展，許多實(shí)際的最優(yōu)化問(wèn)題已經(jīng)無(wú)法用古典方法來(lái)解決，這就促進(jìn)了近代最優(yōu)化方法的產(chǎn)生。

近代最優(yōu)化方法的形成和發(fā)展過(guò)程中最重要的事件有： 以蘇聯(lián)Л.В.康托羅維奇和美國(guó)G.B.丹齊克為代表的線性規(guī)劃；以美國(guó)庫(kù)恩和塔克爾為代表的非線性規(guī)劃；以美國(guó)R.貝爾曼為代表的動(dòng)態(tài)規(guī)劃；以蘇聯(lián)Л.С.龐特里亞金為代表的極大值原理等。這些方法后來(lái)都形成體系，成為近代很活躍的學(xué)科，對(duì)促進(jìn)運(yùn)籌學(xué)、管理科學(xué)、控制論和系統(tǒng)工程等學(xué)科的發(fā)展起了重要作用。

最優(yōu)化方法工作步驟

用最優(yōu)化方法解決實(shí)際問(wèn)題，一般可經(jīng)過(guò)下列步驟：①提出最優(yōu)化問(wèn)題，收集有關(guān)數(shù)據(jù)和資料；②建立最優(yōu)化問(wèn)題的數(shù)學(xué)模型,確定變量,列出目標(biāo)函數(shù)和約束條件；③分析模型，選擇合適的最優(yōu)化方法；④求解，一般通過(guò)編制程序，用計(jì)算機(jī)求最優(yōu)解；⑤最優(yōu)解的檢驗(yàn)和實(shí)施。上述 5個(gè)步驟中的工作相互支持和相互制約，在實(shí)踐中常常是反復(fù)交叉進(jìn)行。

最優(yōu)化方法模型的基本要素

最優(yōu)化模型一般包括變量、約束條件和目標(biāo)函數(shù)三要素:①變量:指最優(yōu)化問(wèn)題中待確定的某些量。變量可用x=(x1，x2,…,xn)T表示。②約束條件:指在求最優(yōu)解時(shí)對(duì)變量的某些限制,包括技術(shù)上的約束、資源上的約束和時(shí)間上的約束等。列出的約束條件越接近實(shí)際系統(tǒng)，則所求得的系統(tǒng)最優(yōu)解也就越接近實(shí)際最優(yōu)解。約束條件可用 gi(x)≤0表示i=1,2，…，m，m 表示約束條件數(shù)；或x∈R(R表示可行集合)。③目標(biāo)函數(shù)：最優(yōu)化有一定的評(píng)價(jià)標(biāo)準(zhǔn)。目標(biāo)函數(shù)就是這種標(biāo)準(zhǔn)的數(shù)學(xué)描述，一般可用f(x)來(lái)表示，即f(x)=f(x1，x2,…,xn)。要求目標(biāo)函數(shù)為最大時(shí)可寫成；要求最小時(shí)則可寫成。目標(biāo)函數(shù)可以是系統(tǒng)功能的函數(shù)或費(fèi)用的函數(shù)。它必須在滿足規(guī)定的約束條件下達(dá)到最大或最小。 　問(wèn)題的分類 　最優(yōu)化問(wèn)題根據(jù)其中的變量、約束、目標(biāo)、問(wèn)題性質(zhì)、時(shí)間因素和函數(shù)關(guān)系等不同情況，可分成多種類型（見(jiàn)表）。最優(yōu)化方法

最優(yōu)化方法

不同類型的最優(yōu)化問(wèn)題可以有不同的最優(yōu)化方法，即使同一類型的問(wèn)題也可有多種最優(yōu)化方法。反之,某些最優(yōu)化方法可適用于不同類型的模型。最優(yōu)化問(wèn)題的求解方法一般可以分成解析法、直接法、數(shù)值計(jì)算法和其他方法。①解析法：這種方法只適用于目標(biāo)函數(shù)和約束條件有明顯的解析表達(dá)式的情況。求解方法是：先求出最優(yōu)的必要條件，得到一組方程或不等式，再求解這組方程或不等式，一般是用求導(dǎo)數(shù)的方法或變分法求出必要條件，通過(guò)必要條件將問(wèn)題簡(jiǎn)化，因此也稱間接法。②直接法：當(dāng)目標(biāo)函數(shù)較為復(fù)雜或者不能用變量顯函數(shù)描述時(shí)，無(wú)法用解析法求必要條件。此時(shí)可采用直接搜索的方法經(jīng)過(guò)若干次迭代搜索到最優(yōu)點(diǎn)。這種方法常常根據(jù)經(jīng)驗(yàn)或通過(guò)試驗(yàn)得到所需結(jié)果。對(duì)于一維搜索(單變量極值問(wèn)題)，主要用消去法或多項(xiàng)式插值法；對(duì)于多維搜索問(wèn)題(多變量極值問(wèn)題)主要應(yīng)用爬山法。③數(shù)值計(jì)算法：這種方法也是一種直接法。它以梯度法為基礎(chǔ)，所以是一種解析與數(shù)值計(jì)算相結(jié)合的方法。④其他方法：如網(wǎng)絡(luò)最優(yōu)化方法等(見(jiàn)網(wǎng)絡(luò)理論)。

解析性質(zhì)

根據(jù)函數(shù)的解析性質(zhì)，還可以對(duì)各種方法作進(jìn)一步分類。例如，如果目標(biāo)函數(shù)和約束條件都是線性的，就形成線性規(guī)劃。線性規(guī)劃有專門的解法，諸如單純形法、解乘數(shù)法、橢球法和卡馬卡法等。當(dāng)目標(biāo)或約束中有一非線性函數(shù)時(shí),就形成非線性規(guī)劃。當(dāng)目標(biāo)是二次的,而約束是線性時(shí)，則稱為二次規(guī)劃。二次規(guī)劃的理論和方法都較成熟。如果目標(biāo)函數(shù)具有一些函數(shù)的平方和的形式，則有專門求解平方和問(wèn)題的優(yōu)化方法。目標(biāo)函數(shù)具有多項(xiàng)式形式時(shí)，可形成一類幾何規(guī)劃。

最優(yōu)解的概念

最優(yōu)化問(wèn)題的解一般稱為最優(yōu)解。如果只考察約束集合中某一局部范圍內(nèi)的優(yōu)劣情況，則解稱為局部最優(yōu)解。如果是考察整個(gè)約束集合中的情況，則解稱為總體最優(yōu)解。對(duì)于不同優(yōu)化問(wèn)題，最優(yōu)解有不同的含意，因而還有專用的名稱。例如，在對(duì)策論和數(shù)理經(jīng)濟(jì)模型中稱為平衡解；在控制問(wèn)題中稱為最優(yōu)控制或極值控制；在多目標(biāo)決策問(wèn)題中稱為非劣解（又稱帕雷托最優(yōu)解或有效解）。在解決實(shí)際問(wèn)題時(shí)情況錯(cuò)綜復(fù)雜，有時(shí)這種理想的最優(yōu)解不易求得，或者需要付出較大的代價(jià)，因而對(duì)解只要求能滿足一定限度范圍內(nèi)的條件,不一定過(guò)分強(qiáng)調(diào)最優(yōu)。50年代初,在運(yùn)籌學(xué)發(fā)展的早期就有人提出次優(yōu)化的概念及其相應(yīng)的次優(yōu)解。提出這些概念的背景是：最優(yōu)化模型的建立本身就只是一種近似，因?yàn)閷?shí)際問(wèn)題中存在的某些因素，尤其是一些非定量因素很難在一個(gè)模型中全部加以考慮。另一方面，還缺乏一些求解較為復(fù)雜模型的有效方法。1961年H.A.西蒙進(jìn)一步提出滿意解的概念，即只要決策者對(duì)解滿意即可。

最優(yōu)化方法最優(yōu)化方法的應(yīng)用

最優(yōu)化一般可以分為最優(yōu)設(shè)計(jì)、最優(yōu)計(jì)劃、最優(yōu)管理和最優(yōu)控制等四個(gè)方面。①最優(yōu)設(shè)計(jì):世界各國(guó)工程技術(shù)界,尤其是飛機(jī)、造船、機(jī)械、建筑等部門都已廣泛應(yīng)用最優(yōu)化方法于設(shè)計(jì)中，從各種設(shè)計(jì)參數(shù)的優(yōu)選到最佳結(jié)構(gòu)形狀的選取等，結(jié)合有限元方法已使許多設(shè)計(jì)優(yōu)化問(wèn)題得到解決。一個(gè)新的發(fā)展動(dòng)向是最優(yōu)設(shè)計(jì)和計(jì)算機(jī)輔助設(shè)計(jì)相結(jié)合。電子線路的最優(yōu)設(shè)計(jì)是另一個(gè)應(yīng)用最優(yōu)化方法的重要領(lǐng)域。配方配比的優(yōu)選方面在化工、橡膠、塑料等工業(yè)部門都得到成功的應(yīng)用,并向計(jì)算機(jī)輔助搜索最佳配方、配比方向發(fā)展(見(jiàn)優(yōu)選法)。②最優(yōu)計(jì)劃:現(xiàn)代國(guó)民經(jīng)濟(jì)或部門經(jīng)濟(jì)的計(jì)劃，直至企業(yè)的發(fā)展規(guī)劃和年度生產(chǎn)計(jì)劃，尤其是農(nóng)業(yè)規(guī)劃、種植計(jì)劃、能源規(guī)劃和其他資源、環(huán)境和生態(tài)規(guī)劃的制訂,都已開(kāi)始應(yīng)用最優(yōu)化方法。一個(gè)重要的發(fā)展趨勢(shì)是幫助領(lǐng)導(dǎo)部門進(jìn)行各種優(yōu)化決策。③最優(yōu)管理：一般在日常生產(chǎn)計(jì)劃的制訂、調(diào)度和運(yùn)行中都可應(yīng)用最優(yōu)化方法。隨著管理信息系統(tǒng)和決策支持系統(tǒng)的建立和使用，使最優(yōu)管理得到迅速的發(fā)展。④最優(yōu)控制：主要用于對(duì)各種控制系統(tǒng)的優(yōu)化。例如，導(dǎo)彈系統(tǒng)的最優(yōu)控制，能保證用最少燃料完成飛行任務(wù),用最短時(shí)間達(dá)到目標(biāo);再如飛機(jī)、船舶、電力系統(tǒng)等的最優(yōu)控制，化工、冶金等工廠的最佳工況的控制。計(jì)算機(jī)接口裝置不斷完善和優(yōu)化方法的進(jìn)一步發(fā)展，還為計(jì)算機(jī)在線生產(chǎn)控制創(chuàng)造了有利條件。最優(yōu)控制的對(duì)象也將從對(duì)機(jī)械、電氣、化工等硬系統(tǒng)的控制轉(zhuǎn)向?qū)ι鷳B(tài)、環(huán)境以至社會(huì)經(jīng)濟(jì)系統(tǒng)的控制。

圖書信息

書 名: 最優(yōu)化方法

作　者：張立衛(wèi)

出版社：科學(xué)出版社

出版時(shí)間： 2010年6月1日

ISBN: 9787030276490

開(kāi)本： 16開(kāi)

定價(jià): 27.00元

本書深入淺出地闡述了最優(yōu)化方法和最優(yōu)控制系統(tǒng)的基礎(chǔ)理論、基本方法，并配有豐富的例題和習(xí)題，幫助讀者理解書申所闡述的內(nèi)容。

本書的內(nèi)容分為兩大部分，第一部分包括第1章、第2章和第3章，闡述了最優(yōu)化方法的一般概念和靜態(tài)最優(yōu)化方法（線性規(guī)劃和非線性規(guī)劃）的一些基本理論和計(jì)算方法；第二部分包括第4章至第7章，闡述了動(dòng)態(tài)最優(yōu)化方法的基本內(nèi)容，包括變分極值問(wèn)題、最小值原理、線性二次型最優(yōu)控制系統(tǒng)和動(dòng)態(tài)規(guī)劃的各種基本算法。

本書各章節(jié)注重基本原理和基本概念的闡述，容易理解。

本書主要闡述最優(yōu)化方法的原理和算法及其在通信工程中的應(yīng)用。全書共分八章，內(nèi)容分別為最優(yōu)化問(wèn)題的數(shù)學(xué)模型和最優(yōu)解的數(shù)學(xué)基礎(chǔ)、無(wú)約束優(yōu)化問(wèn)題的求解方法、求解線性規(guī)劃的單純形算法和卡瑪卡算法、非線性規(guī)劃的求解策略和主要算法、多目標(biāo)規(guī)劃和動(dòng)態(tài)規(guī)劃的求解原理和方法，最后一章綜合了各種算法，較為詳細(xì)地分析和介紹最優(yōu)化方法在通信工程中的七類典型應(yīng)用實(shí)例。

第1章　最優(yōu)化方法的一般概念

1.1　目標(biāo)函數(shù)、約束條件和求解方法

1.2　靜態(tài)最優(yōu)化問(wèn)題與動(dòng)態(tài)最優(yōu)化問(wèn)題

1.3　線性規(guī)劃和非線性規(guī)劃問(wèn)題

1.4　最優(yōu)化方法在控制領(lǐng)域中的應(yīng)用

習(xí)題

第2章　非線性規(guī)劃

2.1　一元函數(shù)的極小化

2.2　多元函數(shù)無(wú)約束的極小化

2.3　求解多元函數(shù)無(wú)約束極值的直接法

2.4　多元函數(shù)帶約束極小化

2.5　非線性規(guī)劃應(yīng)用舉例

習(xí)題

第3章　線性規(guī)劃

3.1　線性規(guī)劃的數(shù)學(xué)模型

3.2　圖解法

3.3　線性規(guī)劃的數(shù)學(xué)基礎(chǔ)

3.4　線性規(guī)劃的單純形法

3.5　線性規(guī)劃的對(duì)偶問(wèn)題

3.6　對(duì)偶單純形法

3.7　線性規(guī)劃應(yīng)用舉例

習(xí)題

第4章　最優(yōu)控制與變分法

4.1　最優(yōu)控制問(wèn)題的數(shù)學(xué)描述

4.2　無(wú)約束條件的動(dòng)態(tài)最優(yōu)化問(wèn)題

4.3　帶等式約束的動(dòng)態(tài)最優(yōu)化問(wèn)題

4.4　用哈密頓函數(shù)求解最優(yōu)控制問(wèn)題

習(xí)題

第5章　最小值原理

5.1　最小值原理

5.2　快速最優(yōu)控制

5.3　奇異最優(yōu)控制

5.4　一些典型性能指標(biāo)下的最優(yōu)控制

習(xí)題

第6章　線性二次型最優(yōu)控制系統(tǒng)

6.1　線性二次型最優(yōu)控制系統(tǒng)

6.2　狀態(tài)調(diào)節(jié)問(wèn)題

6.3　tf—8時(shí)的狀態(tài)調(diào)節(jié)問(wèn)題

6.4　能夠保證衰減速度的最優(yōu)控制

6.5　在階躍干擾作用下的狀態(tài)調(diào)節(jié)器

6.6　輸出調(diào)節(jié)問(wèn)題

6.7　最優(yōu)跟蹤問(wèn)題

習(xí)題

第7章　動(dòng)態(tài)規(guī)劃

7.1　多級(jí)決策過(guò)程

7.2　最優(yōu)性原理

7.3　離散系統(tǒng)的線性調(diào)節(jié)問(wèn)題

7.4　動(dòng)態(tài)規(guī)劃的連續(xù)形式

7.5　用動(dòng)態(tài)規(guī)劃求解連續(xù)線性二次型最優(yōu)調(diào)節(jié)問(wèn)題

7.6　動(dòng)態(tài)規(guī)劃的應(yīng)用示例

習(xí)題

參考文獻(xiàn)2100433B