最優(yōu)化：理論、計(jì)算與應(yīng)用

目 錄 
第1章 最優(yōu)化問題概述 1 
1.1 最優(yōu)化問題的數(shù)學(xué)模型與分類 1 
1.2 最優(yōu)化問題 2 
1.2.1 無約束最優(yōu)化問題 2 
1.2.2 線性規(guī)劃問題 3 
1.2.3 二次規(guī)劃問題 4 
1.2.4 約束優(yōu)化問題 6 
1.3 無約束問題的最優(yōu)性條件 7 
1.3.1 無約束問題的最優(yōu)解 7 
1.3.2 最優(yōu)性條件 9 
1.4 約束問題的最優(yōu)性條件 13 
1.4.1 約束問題的全局解與局部解 13 
1.4.2 約束問題最優(yōu)解的最優(yōu)性條件 14 
1.5 凸集與凸函數(shù) 21 
1.5.1 凸集 22 
1.5.2 凸函數(shù) 25 
1.6 約束問題最優(yōu)性條件的證明 28 
1.6.1 一階必要條件的證明 28 
1.6.2 二階充分條件的證明 33 
1.7 MATLAB優(yōu)化工具箱 35 
1.7.1 MATLAB概述 35 
1.7.2 MATLAB優(yōu)化工具箱概述 35 
1.7.3 MATLAB優(yōu)化工具箱中的函數(shù) 36 
習(xí)題1 37 
第2章 一維搜索與信賴域方法 42 
2.1 求解無約束問題的結(jié)構(gòu) 42 
2.1.1 一維搜索策略的下降算法 42 
2.1.2 信賴域方法 42 
2.2 一維搜索 43
2.2.1 精確一維搜索算法 43 
2.2.2 非精確一維搜索算法 46 
2.2.3 正定二次函數(shù)的一維搜索方法 48 
2.3 下降算法的收斂性 49 
2.3.1 算法的收斂性 49 
2.3.2 算法的收斂速率 52 
2.3.3 算法的二次終止性 52 
2.4 信賴域方法 53 
2.4.1 信賴域方法的基本結(jié)構(gòu) 53 
2.4.2 求解信賴域子問題的dogleg方法 54 
2.4.3 信賴域方法的全局收斂性 55 
2.5 自編的MATLAB程序 57 
2.5.1 一維搜索程序 57 
2.5.2 求解信賴域子問題折線方法 61 
2.6 MATLAB優(yōu)化工具箱中的函數(shù) 63 
2.7 一維優(yōu)化問題的應(yīng)用 64 
2.7.1 路燈照明問題 65 
2.7.2 極大似然估計(jì) 66 
習(xí)題2 67 
第3章 無約束最優(yōu)化方法 68 
3.1 算法 68 
3.1.1 最速下降法的收斂性質(zhì) 68 
3.1.2 算法的收斂性質(zhì) 70 
3.2 共軛梯度法 74 
3.2.1 線性共軛梯度法 74 
3.2.2 非線性共軛梯度法 79 
3.2.3 共軛梯度法的收斂性質(zhì) 82 
3.3 Newton法 85 
3.3.1 精確Newton法 85 
3.3.2 Newton法的收斂性質(zhì) 87 
3.3.3 非精確Newton法 88 
3.3.4 帶有一維搜索的Newton法 89 
3.3.5 信賴域Newton法 91 
3.4 擬Newton法 94
3.4.1 秩1修正公式 95 
3.4.2 秩1修正公式的性質(zhì) 98 
3.4.3 秩2修正公式 100 
3.4.4 秩2修正公式的性質(zhì) 105 
3.4.5 信賴域算法 110 
3.5 自編的MATLAB程序 111 
3.5.1 最速下降法 111 
3.5.2 共軛梯度法 112 
3.5.3 Newton法 113 
3.5.4 擬Newton法 114 
3.5.5 信賴域方法 115 
3.6 MATLAB優(yōu)化工具箱中的函數(shù) 118 
3.6.1 多變量極小化函數(shù) 118 
3.6.2 設(shè)置優(yōu)化參數(shù) 121 
3.7 無約束最優(yōu)化問題的應(yīng)用 125 
3.7.1 選址問題 125 
3.7.2 曲線擬合問題 126 
3.7.3 藥物濃度的測定 126 
習(xí)題3 129 
第4章 非線性方程與最小二乘問題 133 
4.1 求解非線性方程組 133 
4.1.1 非線性方程求根 133 
4.1.2 非線性方程組求解 136 
4.2 超定方程組求解與最小二乘問題 143 
4.2.1 線性最小二乘問題 144 
4.2.2 Gauss-Newton法 146 
4.2.3 Levenberg-Marquardt方法 149 
4.2.4 擬Newton法 152 
4.3 自編MATLAB程序 153 
4.3.1 求解非線性方程的方法 153 
4.3.2 求解非線性方程組的方法 156 
4.3.3 求解非線性最小二乘問題的算法 161 
4.4 MATLAB優(yōu)化工具箱中的函數(shù) 167 
4.4.1 求解非線性方程 (組) 167
4.4.2 求解線性最小二乘問題 170 
4.4.3 求解非線性最小二乘問題 174 
4.5 非線性方程(組)的應(yīng)用 177 
4.5.1 求極值問題 177 
4.5.2 GPS定位問題 179 
4.6 最小二乘問題的應(yīng)用 182 
4.6.1 曲線擬合問題 182 
4.6.2 GPS定位問題(續(xù)) 182 
習(xí)題4 184 
第5章 線性規(guī)劃 187 
5.1 線性規(guī)劃的數(shù)學(xué)模型 187 
5.1.1 線性規(guī)劃的實(shí)例 187 
5.1.2 線性規(guī)劃的標(biāo)準(zhǔn)形式 190 
5.1.3 線性規(guī)劃的圖解法 191 
5.2 求解線性規(guī)劃問題的單純形法 194 
5.2.1 基本單純形法 194 
5.2.2 單純形表 197 
5.2.3 兩階段方法 199 
5.2.4 改進(jìn)單純形法 203 
5.3 線性規(guī)劃的對偶問題 205 
5.3.1 對偶線性規(guī)劃 205 
5.3.2 線性規(guī)劃的對偶理論 208 
5.3.3 對偶單純形法 211 
5.4 內(nèi)點(diǎn)算法概述 215 
5.4.1 算法復(fù)雜性的基本概念 215 
5.4.2 單純形法的復(fù)雜性 215 
5.4.3 內(nèi)點(diǎn)算法簡介 216 
5.5 自編MATLAB程序 217 
5.5.1 從基本可行解開始的單純形法 217 
5.5.2 兩階段方法 218 
5.5.3 從正則解開始的對偶單純形法 220 
5.6 MATLAB優(yōu)化工具箱中的函數(shù) 222 
5.6.1 linprog函數(shù) 222 
5.6.2 Lagrange乘子的意義 224 
5.6.3 intlinprog函數(shù) 227 
5.7 線性規(guī)劃問題的應(yīng)用 230 
5.7.1 城市規(guī)劃 230 
5.7.2 投資 233 
5.7.3 生產(chǎn)計(jì)劃與庫存控制 236 
5.7.4 人力規(guī)劃 244 
5.7.5 最小覆蓋 246 
5.8 用線性規(guī)劃求解圖論中的問題 248 
5.8.1 運(yùn)輸問題 248 
5.8.2 最優(yōu)指派問題 250 
5.8.3 最短路問題 253 
5.8.4 最大流問題及應(yīng)用 258 
習(xí)題5 264 
第6章 約束最優(yōu)化方法 273 
6.1 二次規(guī)劃問題 273 
6.1.1 二次規(guī)劃的基本性質(zhì) 273 
6.1.2 等式二次規(guī)劃問題 274 
6.1.3 求解凸二次規(guī)劃的有效集法 280 
6.2 罰函數(shù)方法 286 
6.2.1 二次罰函數(shù)方法 286 
6.2.2 l1 模罰函數(shù)方法 294 
6.2.3 乘子罰函數(shù)法 297 
6.2.4 一般等式約束問題的乘子罰函數(shù)法 302 
6.2.5 一般約束問題的乘子罰函數(shù)法 304 
6.3 序列二次規(guī)劃方法 308 
6.3.1 Lagrange-Newton法 308 
6.3.2 一般約束問題的序列二次規(guī)劃方法 310 
6.4 序列二次規(guī)劃的信賴域方法 316 
6.4.1 求解等式約束問題的信賴域算法 316 
6.4.2 求解一般約束問題的信賴域算法 320 
6.5 MATLAB優(yōu)化工具箱中的函數(shù) 323 
6.5.1 求解二次規(guī)劃問題 323 
6.5.2 求解一般約束問題 327 
6.6 約束最優(yōu)化問題的應(yīng)用 331
6.6.1 投資組合問題 331 
6.6.2 選址問題 332 
習(xí)題6 334 
習(xí)題參考答案 339 
參考文獻(xiàn) 347 
索引 348 
MATLAB函數(shù)索引 352 
MATLAB自編函數(shù)索引 353