最優化是運籌學的一個重要分支，在很多領域具有廣泛的應用. 《最優化計算方法》系統地介紹了線性規劃、無約束優化及約束優化的基礎理論和求解方法，主要內容包括：線性規劃的對偶理論與最優性條件、無約束優化的最優性條件、約束優化的最優性條件與鞍點定理；求解線性規劃的單純形算法、內點算法、非內部連續化算法；求解無約束優化的最速下降法、牛頓法、共軛梯度法、擬牛頓法、非單調線搜索法、信賴域法；求解約束優化的序列無約束優化法、可行方向法、序列二次規劃法等，也簡單介紹了多目標規劃的基本理論與求解方法。
前言
第1章 引論
1.1 最優化問題概述
1.2 預備知識
1.2.1 向量范數與矩陣范數
1.2.2 函數的可微性
1.3 凸集、凸函數、凸規劃.
1.3.1 凸集
1.3.2 凸函數
1.3.3 凸規劃
1.4 線搜索迭代算法概述及收斂性準則
1.4.1 線搜索迭代算法的一般框架
1.4.2 迭代方向
1.4.3 迭代步長
1.4.4 算法收斂性
習題
第2章 線性規劃
2.1 線性規劃問題及其基本概念
2.2 線性規劃的基本理論
2.2.1 解的幾何特性
2.2.2 對偶理論與最優性條件
2.3 線性規劃的單純形算法
2.3.1 算法介紹
2.3.2 單純形表
2.3.3 初始基可行解的求法
2.4 線性規劃的對偶單純形算法
2.5 線性規劃的原對偶可行路徑跟蹤內點算法
2.5.1 算法描述
2.5.2 算法的多項式復雜性
2.6 線性規劃的非內部連續化算法
2.6.1 算法描述
2.6.2 算法的收斂性 66 習題
第3章 無約束優化方法
3.1 算法理論基礎
3.1.1 最優性條件
3.1.2 線搜索迭代下降算法及其收斂性
3.2 最速下降法
3.3 牛頓法
3.3.1 經典牛頓法
3.3.2 帶線搜索的牛頓法
3.4 共軛梯度法
3.4.1 二次函數極小化的共軛方向法
3.4.2 二次函數極小化的共軛梯度法
3.4.3 一般函數極小化的共軛梯度法
3.5 擬牛頓法
3.5.1 擬牛頓條件
3.5.2 DFP 算法
3.5.3 BFGS 算法
3.6 非單調線搜索算法
3.7 信賴域方法
3.8 最小二乘法
3.8.1 線性最小二乘問題
3.8.2 非線性最小二乘問題
習題 3.
第4章 約束優化方法
4.1 約束優化問題的最優性條件
4.1.1 一階最優性條件
4.1.2 二階最優性條件
4.1.3 凸規劃問題的最優性條件
4.2 對偶與鞍點問題
4.3 二次規劃
4.3.1 基本概念與基本性質
4.3.2 等式約束的二次規劃
4.3.3 一般約束二次規劃的有效集方法
4.4 序列無約束方法
4.4.1 外罰函數法
4.4.2 內罰函數法
4.4.3 乘子法
4.5 可行方向法
4.5.1 Zoutendijk 可行方向法
4.5.2 Rosen 梯度投影法
4.5.3 既約梯度法
4.6 序列二次規劃法
習題 4.
第5章 多目標規劃簡介
5.1 多目標規劃的模型及其分類
5.1.1 多目標規劃問題的例子
5.1.2 多目標規劃問題的數學模型及其分類
5.2 多目標規劃解的概念及其性質
5.2.1 解的概念
5.2.2 解的性質
5.3 多目標規劃問題的解法
5.3.1 評價函數法
5.3.2 權系數的確定
5.3.3 分層求解法
習題 5.
參考文獻.
《最優化計算方法》：
第1章 引論
本章首先介紹最優化問題的數學模型?基本概念及其分類， 然后介紹凸集和凸函數的概念及相關性質， 最后介紹線搜索迭代算法的一般框架?線搜索準則及其算法收斂性判別.
1.1 最優化問題概述
在現實社會中， 人們經常遇到這樣一類問題： 判別在一個問題的眾多解決方案中什么樣的方案最佳， 以及如何找出最佳方案. 例如， 在資源分配中， 如何分配有限資源， 使得分配方案既能滿足各方面的需求， 又能獲得好的經濟效益； 在工程設計中， 如何選擇設計參數， 使得設計方案既能滿足設計要求， 又能降低成本等. 這類問題就是在一定的限制條件下使得所關心的指標達到最優. 最優化就是為解決這類問題提供理論基礎和求解方法的一門數學學科.
最優化問題的基本數學模型為
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 稱為決策向量，函數 f ： Rn ! R 稱為目標函數， 函數 ci（￠） （i 2 I） 稱為不等式約束函數， 函數ci（￠） （i 2 E） 稱為等式約束函數， 不等式 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 為最優化問題 （1.1.1） 的可行域， F 中的每個點 x 稱為最優化問題（1.1.1） 的一個可行點. 若 F = ?， 則稱問題 （1.1.1） 是不可行的； 否則稱問題 （1.1.1）是可行的. 因此， 最優化問題 （1.1.1） 就是在可行域 F 中尋找一點 x 使得它對應的目標函數值 f（x） 不大于 F 中其他任何點所對應的目標函數值.
定義 1.1.1 假設可行域 F 由 （1.1.2） 式給出.
（i） 若 x¤ 2 F， 且對所有的 x 2 F 恒有 f（x¤） 6 f（x）， 則稱 x¤ 為最優化問題（1.1.1） 的一個全局最優解.
（ii） 若 x¤ 2 F， 且對所有的 x 2 F n fx¤g 恒有 f（x¤） < f（x）， 則稱 x¤ 為最優化問題 （1.1.1） 的嚴格全局最優解.
（iii） 若 x¤ 2 F， 且存在 x¤ 的某個鄰域
N"（x¤） ：= fx 2 Rn j kx . x¤k < "g； "為正實數且k ￠ k表示某種范數；
使得對所有的 x 2 F \N"（x¤） 恒有 f（x¤） 6 f（x）， 那么稱 x¤ 為最優化問題 （1.1.1）的一個局部最優解.
（iv） 若 x¤ 2F， 且存在 x¤ 的某個鄰域 N"（x¤）， 使得對所有的 x 2 F \ N"（x¤）n fx¤g 恒有 f（x¤） < f（x）， 那么稱 x¤ 為最優化問題 （1.1.1） 的一個嚴格局部最優解.
顯然， 全局最優解一定是局部最優解； 而局部最優解不一定是全局最優解. 求解最優化問題 （1.1.1） 就是在可行域 F 上尋找問題 （1.1.1） 的全局最優解. 但是， 在一般情況下， 不容易求得全局最優解， 往往只能求出局部最優解. 以下若不做特別聲明， 全局最優解簡稱最優解.
定義 1.1.2 對于最優化問題 （1.1.1）， 稱其最優解 x¤ 對應的目標函數值 f（x¤）為此優化問題的最優值.
對于最優化問題 （1.1.1）， 最優解不一定存在， 即使存在也不一定唯一； 但是， 若最優解存在， 則最優值必唯一. 以下用 S 表示最優化問題 （1.1.1） 的最優解集. 如果S = ?， 那么最優化問題 （1.1.1） 無最優解； 否則最優化問題 （1.1.1） 有最優解. 顯然，若最優化問題 （1.1.1） 不可行； 或者該問題可行但它的目標函數值在可行域上無下界， 則最優化問題 （1.1.1） 都無最優解. 另外需要提到的一點是： 在實際中， 若需要極大化目標函數， 那么通過將目標函數前加負號可轉化為極小化問題求解. 因此，不失一般性， 本書中只考慮極小化問題.
最優化問題 （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 的縮寫.
最優化問題形形色色， 對應的最優化模型多種多樣， 不同的優化模型， 其求解方法有很大的差異. 因此， 為了有效地求解最優化問題， 人們首先應能區分優化問題的類型. 下面從不同的角度對優化問題進行分類.
（1） 根據有無約束條件分為無約束優化和約束優化 若 F = Rn， 則稱問題 （1.1.1） 為無約束優化問題； 若 F μ Rn 且 F 6= Rn， 則稱問題 （1.1.1） 為約束優化問題.
（2） 根據所涉及的函數是否線性分為線性規劃和非線性規劃 若目標函數和約束函數都是線性的， 則稱問題 （1.1.1） 為線性規劃問題； 若目標函數和約束函數中至少有一個是非線性的， 則稱問題 （1.1.1） 為非線性規劃問題. 若目標函數是二次函數且所有約束函數都是線性函數， 則稱問題 （1.1.1） 為二次規劃問題. 二次規劃是一 類簡單?特殊的非線性規劃問題.
（3） 根據目標函數分為單目標規劃和多目標規劃 若目標函數 f 是一個實值函數， 則稱問題 （1.1.1） 為單目標規劃問題； 若目標函數 f 是一個向量值函數， 則稱問題 （1.1.1） 為多目標規劃問題.
（4） 根據涉及函數的可微性質分為光滑優化和非光滑優化 若目標函數和約束函數都是連續可微的， 則稱問題 （1.1.1） 為光滑優化問題； 否則稱為非光滑優化問題.
（5） 根據涉及函數的凸性分為凸規劃和非凸規劃 若可行域 F 是凸集且目標函數 f 是凸函數， 則稱問題 （1.1.1） 為凸規劃問題； 否則稱為非凸規劃問題. 1.3節將詳細介紹凸規劃.
（6） 根據可行點的個數情況分為連續優化和離散優化 若可行域 F 中含有無窮多個點且可行域中的點連續變化， 則稱問題 （1.1.1） 為連續優化問題. 若可行域F 中含有有限個點或可數個點， 則稱問題 （1.1.1） 為離散優化問題. 若所有決策變量取整數， 則稱問題 （1.1.1） 為整數規劃問題； 若部分決策變量取整數且其他決策變量連續變化， 則稱問題 （1.1.1） 為混合整數規劃問題. 在整數規劃中， 如果決策變量只能取 0 和 1， 那么對應的優化問題稱為 0-1 整數規劃問題.需要指出兩點：第一， 部分不同優化問題在某些情況下可以相互轉化； 第二， 這里只是給出一些基本的分類， 最優化問題還有其他的一些分類.本書主要討論光滑的單目標無約束優化和約束優化問題的理論與求解算法， 對多目標規劃只做簡單的介紹.
1.2 預 備 知 識
本節介紹在最優化理論與方法中經常使用的數學基礎知識， 包括向量范數?矩陣范數?函數的梯度與 Hesse 陣?Taylor 展開式等.
1.2.1 向量范數與矩陣范數
本小節介紹向量范數與矩陣范數的定義以及幾個重要不等式.
在本書中， 約定向量取列向量形式， 即 x 2 Rn 是指 x 具有如下形式：
其中， x1； x2； ￠ ￠ ￠ ； xn 分別是向量 x 的分量， 記號 \：=" 表示 \定義". 此外， 對任意的 x； y 2 Rn， 常用的內積 hx； yi 定義為
定義 1.2.1 稱映射 k ￠ kRn !R 為 Rn 上的范數， 當且僅當它具有下列性質：
（i） 對任意的 x 2 Rn， 有 kxk > 0， 且 kxk = 0 當且僅當 x = 0；
（ii） 對任意的 x 2 Rn 和任意的 . 2 R， 有 k.xk = j.jkxk；
（iii） 對任意的 x； y 2 Rn， 有 kx + yk 6 kxk + kyk.
對任意的 x 2 Rn， 常用的向量范數如下.
（1） l1-范數： kxk1 =
注 在本書中， 向量范數 k ￠ k2 廣為使用， 為了簡便， 簡寫為 k ￠ k.
由上述各種范數的定義，容易驗證： 對任意的 x 2 Rn， 有向量范數等價性的定義如下.
命題 1.2.1 假設 k ￠ k. 和 k ￠ kˉ 是定義在 Rn 上的任意兩種范數. 那么總存在兩個正數 .1 和 .2， 使得對任意的 x 2 Rn， 有 .1kxk. 6 kxkˉ 6 .2kxk
因此，以上定義在 Rn 上的向量范數是等價的. 在最優化方法中， 常需要考察某個點列 fxkg 趨向于 x¤ 的速率， 利用命題 1.2.1， 只需要按某種范數 k ￠ k 考察kxk . x¤k 趨向于 0 的速率即可.
另外，假設 A 2 Rn￡n 是對稱正定矩陣. 那么向量的橢球范數 k￠kA 定義如下： kxkA ：= pxTAx； 8x 2 Rn：
1.2 預 備 知 識
類似于向量范數， 可以定義矩陣范數.
定義 1.2.2 稱映射 k ￠ k ： Rn￡n ! R 為 Rn￡n 上的范數， 當且僅當它具有下列性質：
（i） 對任意的 A 2 Rn￡n， 有 kAk > 0， 且 kAk = 0 當且僅當 A = 0；
（ii） 對任意的 A 2 Rn￡n 和任意的 . 2 R， 有 k.Ak = j.jkAk；
（iii） 對任意的 A；B 2 Rn￡n， 有 kA + Bk 6 kAk + kBk.
對任意的 A = （aij）n￡n 2 Rn￡n， 最常用的矩陣范數是 Frobenius 范數， 其定義為
其中， Tr（ATA） 表示矩陣 ATA 的跡， 即 ATA 的所有主對角線元素之和， 也等于ATA 的所有特征值之和. 另一個常用的矩陣范數是由向量所誘導的矩陣范數， 也稱為算子范數， 其定義為
其中， k ￠ k 是某種向量范數. 特別地， 對任意的 A 2 Rn￡n， 有
（1） 由向量 l1- 范數誘導的矩陣范數 （列范數） 為 kAk1 = max . n Xi=1jaij jˉj 2 f1； 2； ￠ ￠ ￠ ； nga；
（2） 由向量 l1- 范數誘導的矩陣范數 （行范數） 為 kAk1 = max . n Xj=1jaij jˉˉi 2 f1； 2； ￠ ￠ ￠ ； nga；
（3） 由向量 l2- 范數誘導的矩陣范數 （譜范數） 為 kAk2 = p.max（ATA）， 其中.max（ATA） 表示矩陣 ATA 的最大特征值.
假設 k ￠ k 表示上述定義四種矩陣范數中的任意一種范數， 那么它滿足相容性件， 即對任意的 A；B 2 Rn￡n， 有 kABk 6 kAkkBk； 并且它與相應的向量范數是 相容的， 即對任意的 A 2 Rn￡n 和 x 2 Rn 有 kAxk 6 kAkkxk.
下面介紹五個常用的不等式.
……
新書資訊