最優(yōu)化是運籌學的一個重要分支，在很多領(lǐng)域具有廣泛的應(yīng)用. 《最優(yōu)化計算方法》系統(tǒng)地介紹了線性規(guī)劃、無約束優(yōu)化及約束優(yōu)化的基礎(chǔ)理論和求解方法，主要內(nèi)容包括：線性規(guī)劃的對偶理論與最優(yōu)性條件、無約束優(yōu)化的最優(yōu)性條件、約束優(yōu)化的最優(yōu)性條件與鞍點定理；求解線性規(guī)劃的單純形算法、內(nèi)點算法、非內(nèi)部連續(xù)化算法；求解無約束優(yōu)化的最速下降法、牛頓法、共軛梯度法、擬牛頓法、非單調(diào)線搜索法、信賴域法；求解約束優(yōu)化的序列無約束優(yōu)化法、可行方向法、序列二次規(guī)劃法等，也簡單介紹了多目標規(guī)劃的基本理論與求解方法。
更多科學出版社服務(wù)，請掃碼獲取。
目 錄
前 言
第1章 引論 1
1.1 最優(yōu)化問題概述 1
1.2 預(yù)備知識 3
1.2.1 向量范數(shù)與矩陣范數(shù) 3
1.2.2 函數(shù)的可徽性 6
1.3 凸集、凸函數(shù)、凸規(guī)劃 8
1.3.1 凸集 8
1.3.2 凸函數(shù) 12
1.3.3 凸規(guī)劃 17
1.4 線搜索選代算法概述及收斂性準則 18
1.4.1 線搜索迭代算法的一般框架 18
1.4.2 選代方向 19
1.4.3 選代步長 20
1.4.4 算法收斂性 24
習題1 25
第2章 線性規(guī)劃 28
2.1 線性規(guī)劃問題及其基本概念 28
2.2 線性規(guī)劃的基本理論 30
2.2.1 解的兒何特性 30
2.2.2 對偶理論與最優(yōu)性條件 33
2.3 線性規(guī)劃的單純形算法 39
2.3.1 算法介紹 39
2.3.2 單純形表 45
2.3.3 初始基可行解的求法 48
2.4 線性規(guī)劃的對偶單純形算法 55
2.5 線性規(guī)劃的原對偶可行路徑跟蹤內(nèi)點算法 57
2.5.1 算法描述 57
2.5.2 算法的多項式復(fù)雜性 61
2.6 線性規(guī)劃的非內(nèi)部連續(xù)化算法 63
2.6.1 算法描述 63
2.6.2 算法的收敢性 66
習題2 72
第3章 無約束優(yōu)化方法 78
3.1 算法理論基礎(chǔ) 78
3.1.1 最優(yōu)性條件 78
3.1.2 線搜索迭代下降算法及其收斂性 80
3.2 最速下降法 84
3.3 牛頓法 87
3.3.1 經(jīng)典牛頓法 87
3.3.2 帶錢搜索的牛頓法 89
3.4 共輒梯度法 90
3.4.1 二次函數(shù)極小化的共輒方向法 90
3.4.2 三次函數(shù)極小化的共輒梯度法 93
3.4.3 一般函數(shù)極小化的共輒梯度法 94
3.5 擬牛頓法 97
3.5.1 擬牛頓條件 97
3.5.2 DFP算法 99
3.5.3 BFGS算法 102
3.6 非單調(diào)線搜索算法 103
3.7 信賴域方法 108
3.8 最小二乘法 112
3.8.1 線性最小二乘問題 112
3.8.2 非線性最小二乘問題 113
習題3 114
第4章 約束優(yōu)化方法 117
4.1 約束優(yōu)化問題的最優(yōu)性條件 117
4.1.1 一階最優(yōu)性條件 117
4.1.2 工階最優(yōu)性條件 125
4.1.3 凸規(guī)劃問題的最優(yōu)性條件 127
4.2 對偶與鞍點問題 129
4.3 二次規(guī)劃 132
4.3.1 基本概念與基本性質(zhì) 132
4.3.2 等式約束的三次規(guī)劃 135
4.3.3 一般的束二次規(guī)劃的有效集方法 144
4.4 序列無約束方法 147
4.4.1 外罰函數(shù)法 148
4.4.2 內(nèi)罰函數(shù)法 155
4.4.3 乘子法 160
4.5 可行方向法 171
4.5.1 Zoutendijk可行方向法 172
4.5.2 Roaen梯度投影法 178
4.5.3 既約梯度法 183
4.6 序列二次規(guī)劃法 186
習題4 195
第5章 多目標規(guī)劃簡介 202
5.1 多目標規(guī)劃的模型及其分類 203
5.1.1 多目標規(guī)劃問題的例子 203
5.1.2 多目標規(guī)劃問題的數(shù)學模型及其分類 204
5.2 多目標規(guī)劃解的概念及其性質(zhì) 207
5.2.1 解的概念 207
5.2.2 解的性質(zhì) 209
5.3 多目標規(guī)劃問題的解法 212
5.3.1 評價函數(shù)法 212
5.3.2 權(quán)系數(shù)的確定 217
5.3.3 分層求解法 219
習題5 222
參考文獻 225
《最優(yōu)化計算方法》：
第1章 引論
本章首先介紹最優(yōu)化問題的數(shù)學模型?基本概念及其分類， 然后介紹凸集和凸函數(shù)的概念及相關(guān)性質(zhì)， 最后介紹線搜索迭代算法的一般框架?線搜索準則及其算法收斂性判別.
1.1 最優(yōu)化問題概述
在現(xiàn)實社會中， 人們經(jīng)常遇到這樣一類問題： 判別在一個問題的眾多解決方案中什么樣的方案最佳， 以及如何找出最佳方案. 例如， 在資源分配中， 如何分配有限資源， 使得分配方案既能滿足各方面的需求， 又能獲得好的經(jīng)濟效益； 在工程設(shè)計中， 如何選擇設(shè)計參數(shù)， 使得設(shè)計方案既能滿足設(shè)計要求， 又能降低成本等. 這類問題就是在一定的限制條件下使得所關(guān)心的指標達到最優(yōu). 最優(yōu)化就是為解決這類問題提供理論基礎(chǔ)和求解方法的一門數(shù)學學科.
最優(yōu)化問題的基本數(shù)學模型為
min f（x）
s.t. ci（x） > 0； 8i 2 I ：= f1； 2； ￠ ￠ ￠ ； pg；
ci（x） = 0； 8i 2 E ：= fp + 1； p + 2； ￠ ￠ ￠ ；mg； （1.1.1）
其中， min 是 minimize 的縮寫， s.t. 是 subject to 的縮寫， x 2 Rn 稱為決策向量，函數(shù) f ： Rn ! R 稱為目標函數(shù)， 函數(shù) ci（￠） （i 2 I） 稱為不等式約束函數(shù)， 函數(shù)ci（￠） （i 2 E） 稱為等式約束函數(shù)， 不等式 ci（x） > 0 （i 2 I） 稱為不等式約束， 方程ci（x） = 0 （i 2 E） 稱為等式約束， I 稱為不等式約束的指標集， E 稱為等式約束的指標集. 記
F ：=8<：
x 2 Rnˉˉˉˉˉˉ
ci（x） > 0； 8i 2 I = f1； 2； ￠ ￠ ￠ ； pg ；
ci（x） = 0； 8i 2 E = fp + 1； p + 2； ￠ ￠ ￠ ；mg9=；： （1.1.2）
那么， 稱集合 F 為最優(yōu)化問題 （1.1.1） 的可行域， F 中的每個點 x 稱為最優(yōu)化問題（1.1.1） 的一個可行點. 若 F = ?， 則稱問題 （1.1.1） 是不可行的； 否則稱問題 （1.1.1）是可行的. 因此， 最優(yōu)化問題 （1.1.1） 就是在可行域 F 中尋找一點 x 使得它對應(yīng)的目標函數(shù)值 f（x） 不大于 F 中其他任何點所對應(yīng)的目標函數(shù)值.
定義 1.1.1 假設(shè)可行域 F 由 （1.1.2） 式給出.
�。╥） 若 x¤ 2 F， 且對所有的 x 2 F 恒有 f（x¤） 6 f（x）， 則稱 x¤ 為最優(yōu)化問題（1.1.1） 的一個全局最優(yōu)解.
�。╥i） 若 x¤ 2 F， 且對所有的 x 2 F n fx¤g 恒有 f（x¤） < f（x）， 則稱 x¤ 為最優(yōu)化問題 （1.1.1） 的嚴格全局最優(yōu)解.
（iii） 若 x¤ 2 F， 且存在 x¤ 的某個鄰域
N"（x¤） ：= fx 2 Rn j kx . x¤k < "g； "為正實數(shù)且k ￠ k表示某種范數(shù)；
使得對所有的 x 2 F \N"（x¤） 恒有 f（x¤） 6 f（x）， 那么稱 x¤ 為最優(yōu)化問題 （1.1.1）的一個局部最優(yōu)解.
�。╥v） 若 x¤ 2F， 且存在 x¤ 的某個鄰域 N"（x¤）， 使得對所有的 x 2 F \ N"（x¤）n fx¤g 恒有 f（x¤） < f（x）， 那么稱 x¤ 為最優(yōu)化問題 （1.1.1） 的一個嚴格局部最優(yōu)解.
顯然， 全局最優(yōu)解一定是局部最優(yōu)解； 而局部最優(yōu)解不一定是全局最優(yōu)解. 求解最優(yōu)化問題 （1.1.1） 就是在可行域 F 上尋找問題 （1.1.1） 的全局最優(yōu)解. 但是， 在一般情況下， 不容易求得全局最優(yōu)解， 往往只能求出局部最優(yōu)解. 以下若不做特別聲明， 全局最優(yōu)解簡稱最優(yōu)解.
定義 1.1.2 對于最優(yōu)化問題 （1.1.1）， 稱其最優(yōu)解 x¤ 對應(yīng)的目標函數(shù)值 f（x¤）為此優(yōu)化問題的最優(yōu)值.
對于最優(yōu)化問題 （1.1.1）， 最優(yōu)解不一定存在， 即使存在也不一定唯一； 但是， 若最優(yōu)解存在， 則最優(yōu)值必唯一. 以下用 S 表示最優(yōu)化問題 （1.1.1） 的最優(yōu)解集. 如果S = ?， 那么最優(yōu)化問題 （1.1.1） 無最優(yōu)解； 否則最優(yōu)化問題 （1.1.1） 有最優(yōu)解. 顯然，若最優(yōu)化問題 （1.1.1） 不可行； 或者該問題可行但它的目標函數(shù)值在可行域上無下界， 則最優(yōu)化問題 （1.1.1） 都無最優(yōu)解. 另外需要提到的一點是： 在實際中， 若需要極大化目標函數(shù)， 那么通過將目標函數(shù)前加負號可轉(zhuǎn)化為極小化問題求解. 因此，不失一般性， 本書中只考慮極小化問題.
最優(yōu)化問題 （1.1.1） 也常被寫成
min8<：
f（x)ˉˉˉˉˉˉ
ci（x） > 0； 8i 2 I ：= f1； 2； ￠ ￠ ￠ ； pg；
ci（x） = 0； 8i 2 E ：= fp + 1； p + 2； ￠ ￠ ￠ ；mg
9=；
或者 minff（x） j x 2 Fg； 或者 minx2F f（x）； 或者 x¤ = arg minx2F f（x） 等， 其中arg min 為 the argument of the minimum 的縮寫.
最優(yōu)化問題形形色色， 對應(yīng)的最優(yōu)化模型多種多樣， 不同的優(yōu)化模型， 其求解方法有很大的差異. 因此， 為了有效地求解最優(yōu)化問題， 人們首先應(yīng)能區(qū)分優(yōu)化問題的類型. 下面從不同的角度對優(yōu)化問題進行分類.
�。�1） 根據(jù)有無約束條件分為無約束優(yōu)化和約束優(yōu)化 若 F = Rn， 則稱問題 （1.1.1） 為無約束優(yōu)化問題； 若 F μ Rn 且 F 6= Rn， 則稱問題 （1.1.1） 為約束優(yōu)化問題.
（2） 根據(jù)所涉及的函數(shù)是否線性分為線性規(guī)劃和非線性規(guī)劃 若目標函數(shù)和約束函數(shù)都是線性的， 則稱問題 （1.1.1） 為線性規(guī)劃問題； 若目標函數(shù)和約束函數(shù)中至少有一個是非線性的， 則稱問題 （1.1.1） 為非線性規(guī)劃問題. 若目標函數(shù)是二次函數(shù)且所有約束函數(shù)都是線性函數(shù)， 則稱問題 （1.1.1） 為二次規(guī)劃問題. 二次規(guī)劃是一 類簡單?特殊的非線性規(guī)劃問題.
�。�3） 根據(jù)目標函數(shù)分為單目標規(guī)劃和多目標規(guī)劃 若目標函數(shù) f 是一個實值函數(shù)， 則稱問題 （1.1.1） 為單目標規(guī)劃問題； 若目標函數(shù) f 是一個向量值函數(shù)， 則稱問題 （1.1.1） 為多目標規(guī)劃問題.
�。�4） 根據(jù)涉及函數(shù)的可微性質(zhì)分為光滑優(yōu)化和非光滑優(yōu)化 若目標函數(shù)和約束函數(shù)都是連續(xù)可微的， 則稱問題 （1.1.1） 為光滑優(yōu)化問題； 否則稱為非光滑優(yōu)化問題.
�。�5） 根據(jù)涉及函數(shù)的凸性分為凸規(guī)劃和非凸規(guī)劃 若可行域 F 是凸集且目標函數(shù) f 是凸函數(shù)， 則稱問題 （1.1.1） 為凸規(guī)劃問題； 否則稱為非凸規(guī)劃問題. 1.3節(jié)將詳細介紹凸規(guī)劃.
�。�6） 根據(jù)可行點的個數(shù)情況分為連續(xù)優(yōu)化和離散優(yōu)化 若可行域 F 中含有無窮多個點且可行域中的點連續(xù)變化， 則稱問題 （1.1.1） 為連續(xù)優(yōu)化問題. 若可行域F 中含有有限個點或可數(shù)個點， 則稱問題 （1.1.1） 為離散優(yōu)化問題. 若所有決策變量取整數(shù)， 則稱問題 （1.1.1） 為整數(shù)規(guī)劃問題； 若部分決策變量取整數(shù)且其他決策變量連續(xù)變化， 則稱問題 （1.1.1） 為混合整數(shù)規(guī)劃問題. 在整數(shù)規(guī)劃中， 如果決策變量只能取 0 和 1， 那么對應(yīng)的優(yōu)化問題稱為 0-1 整數(shù)規(guī)劃問題.需要指出兩點：第一， 部分不同優(yōu)化問題在某些情況下可以相互轉(zhuǎn)化； 第二， 這里只是給出一些基本的分類， 最優(yōu)化問題還有其他的一些分類.本書主要討論光滑的單目標無約束優(yōu)化和約束優(yōu)化問題的理論與求解算法， 對多目標規(guī)劃只做簡單的介紹.
1.2 預(yù) 備 知 識
本節(jié)介紹在最優(yōu)化理論與方法中經(jīng)常使用的數(shù)學基礎(chǔ)知識， 包括向量范數(shù)?矩陣范數(shù)?函數(shù)的梯度與 Hesse 陣?Taylor 展開式等.
1.2.1 向量范數(shù)與矩陣范數(shù)
本小節(jié)介紹向量范數(shù)與矩陣范數(shù)的定義以及幾個重要不等式.
在本書中， 約定向量取列向量形式， 即 x 2 Rn 是指 x 具有如下形式：
其中， x1； x2； ￠ ￠ ￠ ； xn 分別是向量 x 的分量， 記號 \：=" 表示 \定義". 此外， 對任意的 x； y 2 Rn， 常用的內(nèi)積 hx； yi 定義為
定義 1.2.1 稱映射 k ￠ kRn !R 為 Rn 上的范數(shù)， 當且僅當它具有下列性質(zhì)：
�。╥） 對任意的 x 2 Rn， 有 kxk > 0， 且 kxk = 0 當且僅當 x = 0；
�。╥i） 對任意的 x 2 Rn 和任意的 . 2 R， 有 k.xk = j.jkxk；
�。╥ii） 對任意的 x； y 2 Rn， 有 kx + yk 6 kxk + kyk.
對任意的 x 2 Rn， 常用的向量范數(shù)如下.
（1） l1-范數(shù)： kxk1 =
注 在本書中， 向量范數(shù) k ￠ k2 廣為使用， 為了簡便， 簡寫為 k ￠ k.
由上述各種范數(shù)的定義，容易驗證： 對任意的 x 2 Rn， 有向量范數(shù)等價性的定義如下.
命題 1.2.1 假設(shè) k ￠ k. 和 k ￠ kˉ 是定義在 Rn 上的任意兩種范數(shù). 那么總存在兩個正數(shù) .1 和 .2， 使得對任意的 x 2 Rn， 有 .1kxk. 6 kxkˉ 6 .2kxk
因此，以上定義在 Rn 上的向量范數(shù)是等價的. 在最優(yōu)化方法中， 常需要考察某個點列 fxkg 趨向于 x¤ 的速率， 利用命題 1.2.1， 只需要按某種范數(shù) k ￠ k 考察kxk . x¤k 趨向于 0 的速率即可.
另外，假設(shè) A 2 Rn￡n 是對稱正定矩陣. 那么向量的橢球范數(shù) k￠kA 定義如下： kxkA ：= pxTAx； 8x 2 Rn：
1.2 預(yù) 備 知 識
類似于向量范數(shù)， 可以定義矩陣范數(shù).
定義 1.2.2 稱映射 k ￠ k ： Rn￡n ! R 為 Rn￡n 上的范數(shù)， 當且僅當它具有下列性質(zhì)：
�。╥） 對任意的 A 2 Rn￡n， 有 kAk > 0， 且 kAk = 0 當且僅當 A = 0；
�。╥i） 對任意的 A 2 Rn￡n 和任意的 . 2 R， 有 k.Ak = j.jkAk；
�。╥ii） 對任意的 A；B 2 Rn￡n， 有 kA + Bk 6 kAk + kBk.
對任意的 A = （aij）n￡n 2 Rn￡n， 最常用的矩陣范數(shù)是 Frobenius 范數(shù)， 其定義為
其中， Tr（ATA） 表示矩陣 ATA 的跡， 即 ATA 的所有主對角線元素之和， 也等于ATA 的所有特征值之和. 另一個常用的矩陣范數(shù)是由向量所誘導的矩陣范數(shù)， 也稱為算子范數(shù)， 其定義為
其中， k ￠ k 是某種向量范數(shù). 特別地， 對任意的 A 2 Rn￡n， 有
（1） 由向量 l1- 范數(shù)誘導的矩陣范數(shù) （列范數(shù)） 為 kAk1 = max . n Xi=1jaij jˉj 2 f1； 2； ￠ ￠ ￠ ； nga；
�。�2） 由向量 l1- 范數(shù)誘導的矩陣范數(shù) （行范數(shù)） 為 kAk1 = max . n Xj=1jaij jˉˉi 2 f1； 2； ￠ ￠ ￠ ； nga；
（3） 由向量 l2- 范數(shù)誘導的矩陣范數(shù) （譜范數(shù)） 為 kAk2 = p.max（ATA）， 其中.max（ATA） 表示矩陣 ATA 的最大特征值.
假設(shè) k ￠ k 表示上述定義四種矩陣范數(shù)中的任意一種范數(shù)， 那么它滿足相容性件， 即對任意的 A；B 2 Rn￡n， 有 kABk 6 kAkkBk； 并且它與相應(yīng)的向量范數(shù)是 相容的， 即對任意的 A 2 Rn￡n 和 x 2 Rn 有 kAxk 6 kAkkxk.
下面介紹五個常用的不等式.
……
書單推薦
