最優(yōu)化是運(yùn)籌學(xué)的一個(gè)重要分支，在很多領(lǐng)域具有廣泛的應(yīng)用. 《最優(yōu)化計(jì)算方法》系統(tǒng)地介紹了線性規(guī)劃、無約束優(yōu)化及約束優(yōu)化的基礎(chǔ)理論和求解方法，主要內(nèi)容包括：線性規(guī)劃的對偶理論與最優(yōu)性條件、無約束優(yōu)化的最優(yōu)性條件、約束優(yōu)化的最優(yōu)性條件與鞍點(diǎn)定理；求解線性規(guī)劃的單純形算法、內(nèi)點(diǎn)算法、非內(nèi)部連續(xù)化算法；求解無約束優(yōu)化的最速下降法、牛頓法、共軛梯度法、擬牛頓法、非單調(diào)線搜索法、信賴域法；求解約束優(yōu)化的序列無約束優(yōu)化法、可行方向法、序列二次規(guī)劃法等，也簡單介紹了多目標(biāo)規(guī)劃的基本理論與求解方法。
更多科學(xué)出版社服務(wù)，請掃碼獲取。
目 錄
前 言
第1章 引論 1
1.1 最優(yōu)化問題概述 1
1.2 預(yù)備知識(shí) 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 線搜索選代算法概述及收斂性準(zhǔn)則 18
1.4.1 線搜索迭代算法的一般框架 18
1.4.2 選代方向 19
1.4.3 選代步長 20
1.4.4 算法收斂性 24
習(xí)題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)點(diǎn)算法 57
2.5.1 算法描述 57
2.5.2 算法的多項(xiàng)式復(fù)雜性 61
2.6 線性規(guī)劃的非內(nèi)部連續(xù)化算法 63
2.6.1 算法描述 63
2.6.2 算法的收敢性 66
習(xí)題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
習(xí)題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 對偶與鞍點(diǎn)問題 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
習(xí)題4 195
第5章 多目標(biāo)規(guī)劃簡介 202
5.1 多目標(biāo)規(guī)劃的模型及其分類 203
5.1.1 多目標(biāo)規(guī)劃問題的例子 203
5.1.2 多目標(biāo)規(guī)劃問題的數(shù)學(xué)模型及其分類 204
5.2 多目標(biāo)規(guī)劃解的概念及其性質(zhì) 207
5.2.1 解的概念 207
5.2.2 解的性質(zhì) 209
5.3 多目標(biāo)規(guī)劃問題的解法 212
5.3.1 評價(jià)函數(shù)法 212
5.3.2 權(quán)系數(shù)的確定 217
5.3.3 分層求解法 219
習(xí)題5 222
參考文獻(xiàn) 225
《最優(yōu)化計(jì)算方法》：
第1章 引論
本章首先介紹最優(yōu)化問題的數(shù)學(xué)模型?基本概念及其分類， 然后介紹凸集和凸函數(shù)的概念及相關(guān)性質(zhì)， 最后介紹線搜索迭代算法的一般框架?線搜索準(zhǔn)則及其算法收斂性判別.
1.1 最優(yōu)化問題概述
在現(xiàn)實(shí)社會(huì)中， 人們經(jīng)常遇到這樣一類問題： 判別在一個(gè)問題的眾多解決方案中什么樣的方案最佳， 以及如何找出最佳方案. 例如， 在資源分配中， 如何分配有限資源， 使得分配方案既能滿足各方面的需求， 又能獲得好的經(jīng)濟(jì)效益； 在工程設(shè)計(jì)中， 如何選擇設(shè)計(jì)參數(shù)， 使得設(shè)計(jì)方案既能滿足設(shè)計(jì)要求， 又能降低成本等. 這類問題就是在一定的限制條件下使得所關(guān)心的指標(biāo)達(dá)到最優(yōu). 最優(yōu)化就是為解決這類問題提供理論基礎(chǔ)和求解方法的一門數(shù)學(xué)學(xué)科.
最優(yōu)化問題的基本數(shù)學(xué)模型為
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 稱為目標(biāo)函數(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 稱為不等式約束的指標(biāo)集， E 稱為等式約束的指標(biāo)集. 記
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 中的每個(gè)點(diǎn) x 稱為最優(yōu)化問題（1.1.1） 的一個(gè)可行點(diǎn). 若 F = ?， 則稱問題 （1.1.1） 是不可行的； 否則稱問題 （1.1.1）是可行的. 因此， 最優(yōu)化問題 （1.1.1） 就是在可行域 F 中尋找一點(diǎn) x 使得它對應(yīng)的目標(biāo)函數(shù)值 f（x） 不大于 F 中其他任何點(diǎn)所對應(yīng)的目標(biāo)函數(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） 的一個(gè)全局最優(yōu)解.
�。╥i） 若 x¤ 2 F， 且對所有的 x 2 F n fx¤g 恒有 f（x¤） < f（x）， 則稱 x¤ 為最優(yōu)化問題 （1.1.1） 的嚴(yán)格全局最優(yōu)解.
（iii） 若 x¤ 2 F， 且存在 x¤ 的某個(gè)鄰域
N"（x¤） ：= fx 2 Rn j kx . x¤k < "g； "為正實(shí)數(shù)且k ￠ k表示某種范數(shù)；
使得對所有的 x 2 F \N"（x¤） 恒有 f（x¤） 6 f（x）， 那么稱 x¤ 為最優(yōu)化問題 （1.1.1）的一個(gè)局部最優(yōu)解.
�。╥v） 若 x¤ 2F， 且存在 x¤ 的某個(gè)鄰域 N"（x¤）， 使得對所有的 x 2 F \ N"（x¤）n fx¤g 恒有 f（x¤） < f（x）， 那么稱 x¤ 為最優(yōu)化問題 （1.1.1） 的一個(gè)嚴(yán)格局部最優(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)的目標(biāo)函數(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） 不可行； 或者該問題可行但它的目標(biāo)函數(shù)值在可行域上無下界， 則最優(yōu)化問題 （1.1.1） 都無最優(yōu)解. 另外需要提到的一點(diǎn)是： 在實(shí)際中， 若需要極大化目標(biāo)函數(shù)， 那么通過將目標(biāo)函數(shù)前加負(fù)號(hào)可轉(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)化問題進(jìn)行分類.
�。�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ī)劃 若目標(biāo)函數(shù)和約束函數(shù)都是線性的， 則稱問題 （1.1.1） 為線性規(guī)劃問題； 若目標(biāo)函數(shù)和約束函數(shù)中至少有一個(gè)是非線性的， 則稱問題 （1.1.1） 為非線性規(guī)劃問題. 若目標(biāo)函數(shù)是二次函數(shù)且所有約束函數(shù)都是線性函數(shù)， 則稱問題 （1.1.1） 為二次規(guī)劃問題. 二次規(guī)劃是一 類簡單?特殊的非線性規(guī)劃問題.
�。�3） 根據(jù)目標(biāo)函數(shù)分為單目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃 若目標(biāo)函數(shù) f 是一個(gè)實(shí)值函數(shù)， 則稱問題 （1.1.1） 為單目標(biāo)規(guī)劃問題； 若目標(biāo)函數(shù) f 是一個(gè)向量值函數(shù)， 則稱問題 （1.1.1） 為多目標(biāo)規(guī)劃問題.
�。�4） 根據(jù)涉及函數(shù)的可微性質(zhì)分為光滑優(yōu)化和非光滑優(yōu)化 若目標(biāo)函數(shù)和約束函數(shù)都是連續(xù)可微的， 則稱問題 （1.1.1） 為光滑優(yōu)化問題； 否則稱為非光滑優(yōu)化問題.
�。�5） 根據(jù)涉及函數(shù)的凸性分為凸規(guī)劃和非凸規(guī)劃 若可行域 F 是凸集且目標(biāo)函數(shù) f 是凸函數(shù)， 則稱問題 （1.1.1） 為凸規(guī)劃問題； 否則稱為非凸規(guī)劃問題. 1.3節(jié)將詳細(xì)介紹凸規(guī)劃.
�。�6） 根據(jù)可行點(diǎn)的個(gè)數(shù)情況分為連續(xù)優(yōu)化和離散優(yōu)化 若可行域 F 中含有無窮多個(gè)點(diǎn)且可行域中的點(diǎn)連續(xù)變化， 則稱問題 （1.1.1） 為連續(xù)優(yōu)化問題. 若可行域F 中含有有限個(gè)點(diǎn)或可數(shù)個(gè)點(diǎn)， 則稱問題 （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ī)劃問題.需要指出兩點(diǎn)：第一， 部分不同優(yōu)化問題在某些情況下可以相互轉(zhuǎn)化； 第二， 這里只是給出一些基本的分類， 最優(yōu)化問題還有其他的一些分類.本書主要討論光滑的單目標(biāo)無約束優(yōu)化和約束優(yōu)化問題的理論與求解算法， 對多目標(biāo)規(guī)劃只做簡單的介紹.
1.2 預(yù) 備 知 識(shí)
本節(jié)介紹在最優(yōu)化理論與方法中經(jīng)常使用的數(shù)學(xué)基礎(chǔ)知識(shí)， 包括向量范數(shù)?矩陣范數(shù)?函數(shù)的梯度與 Hesse 陣?Taylor 展開式等.
1.2.1 向量范數(shù)與矩陣范數(shù)
本小節(jié)介紹向量范數(shù)與矩陣范數(shù)的定義以及幾個(gè)重要不等式.
在本書中， 約定向量取列向量形式， 即 x 2 Rn 是指 x 具有如下形式：
其中， x1； x2； ￠ ￠ ￠ ； xn 分別是向量 x 的分量， 記號(hào) \：=" 表示 \定義". 此外， 對任意的 x； y 2 Rn， 常用的內(nèi)積 hx； yi 定義為
定義 1.2.1 稱映射 k ￠ kRn !R 為 Rn 上的范數(shù)， 當(dāng)且僅當(dāng)它具有下列性質(zhì)：
�。╥） 對任意的 x 2 Rn， 有 kxk > 0， 且 kxk = 0 當(dāng)且僅當(dāng) 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ù)的定義，容易驗(yàn)證： 對任意的 x 2 Rn， 有向量范數(shù)等價(jià)性的定義如下.
命題 1.2.1 假設(shè) k ￠ k. 和 k ￠ kˉ 是定義在 Rn 上的任意兩種范數(shù). 那么總存在兩個(gè)正數(shù) .1 和 .2， 使得對任意的 x 2 Rn， 有 .1kxk. 6 kxkˉ 6 .2kxk
因此，以上定義在 Rn 上的向量范數(shù)是等價(jià)的. 在最優(yōu)化方法中， 常需要考察某個(gè)點(diǎn)列 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ù)， 可以定義矩陣范數(shù).
定義 1.2.2 稱映射 k ￠ k ： Rn￡n ! R 為 Rn￡n 上的范數(shù)， 當(dāng)且僅當(dāng)它具有下列性質(zhì)：
�。╥） 對任意的 A 2 Rn￡n， 有 kAk > 0， 且 kAk = 0 當(dāng)且僅當(dāng) 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 的所有特征值之和. 另一個(gè)常用的矩陣范數(shù)是由向量所誘導(dǎo)的矩陣范數(shù)， 也稱為算子范數(shù)， 其定義為
其中， k ￠ k 是某種向量范數(shù). 特別地， 對任意的 A 2 Rn￡n， 有
�。�1） 由向量 l1- 范數(shù)誘導(dǎo)的矩陣范數(shù) （列范數(shù)） 為 kAk1 = max . n Xi=1jaij jˉj 2 f1； 2； ￠ ￠ ￠ ； nga；
�。�2） 由向量 l1- 范數(shù)誘導(dǎo)的矩陣范數(shù) （行范數(shù)） 為 kAk1 = max . n Xj=1jaij jˉˉi 2 f1； 2； ￠ ￠ ￠ ； nga；
（3） 由向量 l2- 范數(shù)誘導(dǎo)的矩陣范數(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.
下面介紹五個(gè)常用的不等式.
……
書單推薦
