MATLAB 最優化計算

目　錄 

CONTENTS 

第 1章方程求解與最優化技術 ································ 1 

1.1方程與方程求解 ····································· 1 

1.2最優化問題的起源與發展 ······························ 3 

1.3本書框架 ··········································· 4本章習題 ················································ 5第 2章代數方程的求解······································ 6 

2.1多項式方程的求解···································· 7 

2.1.1一次方程與二次方程 ···························· 8 

2.1.2三次方程的解析解 ······························ 9 

2.1.3四次方程的解析解 ······························ 10 

2.1.4高次代數方程與 Abel–Ru.ini定理·················· 12 

2.2非線性方程的圖解法 ·································· 12 

2.2.1光滑隱函數曲線的繪制 ·························· 12 

2.2.2一元方程的圖解法 ······························ 14 

2.2.3二元方程的圖解法 ······························ 15 

2.2.4方程的孤立解·································· 17 

2.3代數方程的數值求解 ·································· 18 

2.3.1 Newton–Raphson迭代方法 ······················· 18 

2.3.2方程求解的二分法 ······························ 23 

2.3.3 MATLAB的直接求解函數························ 24 

2.3.4求解精度的設置································ 26 

2.3.5方程的結構體描述 ······························ 28 

2.3.6方程的復域求解································ 29 

2.3.7基於問題的方程描述與求解······················· 30 

2.4聯立方程組的精確求解 ································ 31 

2.4.1低階多項式方程的解析求解······················· 32 

2.4.2多項式型方程的準解析解 ························ 35 

2.4.3高次多項式矩陣方程的準解析解 ··················· 36 

. iv . MATLAB最優化計算

2.4.4準解析解的提取································ 39 

2.4.5非線性代數方程的準解析解······················· 40 

2.5多解矩陣方程的求解 ·································· 40 

2.5.1方程求解思路與一般求解函數····················· 41 

2.5.2偽多項式方程的求解 ···························· 45 

2.5.3高精度求解函數································ 47 

2.6欠定方程的求解 ····································· 48本章習題 ················································

第 3章無約束最優化 ······································· 53 

3.1無約束最優化問題簡介 ································ 54 

3.1.1無約束最優化問題的數學模型····················· 54 

3.1.2無約束最優化問題的解析解方法 ··················· 54 

3.1.3無約束最優化問題的圖解法······················· 55 

3.1.4局部最優解與全局最優解 ························ 56 

3.1.5數值求解算法的 MATLAB實現···················· 57 

3.2無約束最優化問題的 MATLAB直接求解 ·················· 

3.2.1直接求解方法·································· 60 

3.2.2最優化控制選項································ 62 

3.2.3最優搜索中間過程的圖形顯示····················· 65 

3.2.4附加參數的傳遞································ 68 

3.2.5最優化問題的結構體描述 ························ 

3.2.6梯度信息與求解精度 ···························· 71 

3.2.7基於問題的描述方法 ···························· 76 

3.2.8離散點最優化問題的求解 ························ 78 

3.2.9最優化問題的並行求解 ·························· 79 

3.3全局最優解的嘗試···································· 

3.3.1全局最優問題演示 ······························ 80 

3.3.2全局最優思路與實現 ···························· 82 

3.4帶有決策變量邊界的最優化問題························· 84 

3.4.1單變量最優化問題 ······························ 84 

3.4.2多變量最優化問題 ······························ 86 

3.4.3基於問題的描述與求解 ·························· 88 

3.4.4邊界問題全局最優解的嘗試······················· 88 

3.5最優化問題應用舉例 ·································· 89 

3.5.1線性回歸問題的求解 ···························· 89 

3.5.2曲線的最小二乘擬合 ···························· 

3.5.3邊值微分方程的打靶求解 ························ 93 

目　錄 . v . 

3.5.4方程求解問題轉換為最優化問題 ··················· 96本章習題 ················································ 98第 4章凸優化 ············································· 103 

4.1線性規劃問題簡介···································· 105 

4.1.1線性規劃問題的數學模型 ························ 106 

4.1.2二元線性規劃的圖解法 ·························· 106 

4.1.3單純形法簡介·································· 108 

4.2線性規劃問題的直接求解 ······························ 111 

4.2.1線性規劃問題的求解函數 ························ 111 

4.2.2多決策變量向量的線性規劃問題 ··················· 117 

4.2.3雙下標的線性規劃問題 ·························· 118 

4.2.4線性規劃的應用舉例——運輸問題 ················· 119 

4.3基於問題的線性規劃描述與求解························· 122 

4.3.1線性規劃的 MPS文件描述························ 122 

4.3.2基於問題的線性規劃描述 ························ 124 

4.3.3線性規劃問題的轉換 ···························· 128 

4.4二次型規劃問題的求解 ································ 130 

4.4.1二次型規劃的數學模型 ·························· 130 

4.4.2二次型規劃的直接求解 ·························· 131 

4.4.3基於問題的二次型規劃描述······················· 132 

4.4.4雙下標二次型規劃 ······························ 136 

4.4.5帶有二次型約束的最優化問題····················· 137 

4.5線性矩陣不等式問題 ·································· 138 

4.5.1線性矩陣不等式的一般描述······················· 138 

4.5.2 Lyapunov不等式 ······························· 139 

4.5.3線性矩陣不等式問題分類 ························ 141 

4.5.4線性矩陣不等式問題的 MATLAB求解 ·············· 142 

4.5.5基於 YALMIP工具箱的最優化求解方法 ············· 144 

4.5.6非凸最優化問題求解的嘗試······················· 146 

4.5.7帶有二次型約束條件問題的求解 ··················· 147 

4.6其他常用的凸優化問題 ································ 149 

4.6.1凸優化工具箱簡介 ······························ 149 

4.6.2錐規劃問題 ··································· 152 

4.6.3幾何規劃問題·································· 154 

4.6.4半定規劃 ····································· 156本章習題 ················································ 156 

. vi . MATLAB最優化計算

第 5章非線性規劃 ········································· 163 

5.1非線性規劃簡介 ····································· 164 

5.1.1一般非線性規劃問題的數學模型 ··················· 164 

5.1.2可行解區域與圖解法 ···························· 165 

5.1.3數值求解方法舉例 ······························ 167 

5.2非線性規劃問題的直接求解 ···························· 169 

5.2.1 MATLAB的直接求解函數························ 169 

5.2.2基於問題的描述方法 ···························· 174 

5.2.3搜索過程提前結束的處理 ························ 175 

5.2.4梯度信息的利用································ 176 

5.2.5多決策變量問題的求解 ·························· 177 

5.2.6復雜非線性規劃問題 ···························· 179 

5.3非線性規劃的全局最優解探討 ·························· 181 

5.3.1全局最優解的嘗試 ······························ 182 

5.3.2非凸二次型規劃問題的全局尋優 ··················· 184 

5.3.3凹費用運輸問題的全局尋優······················· 187 

5.3.4全局最優化求解程序的測試······················· 188 

5.3.5最優化模型的可視化編輯 ························ 190 

5.3.6分段目標函數的處理 ···························· 191 

5.4雙層規劃問題 ······································· 193 

5.4.1雙層線性規劃問題的求解 ························ 193 

5.4.2雙層二次型規劃問題 ···························· 194 

5.4.3基於 YALMIP工具箱的雙層規劃問題直接求解········ 195 

5.5非線性規劃應用舉例 ·································· 197 

5.5.1圓內最大面積的多邊形 ·························· 197 

5.5.2半無限規劃問題································ 200 

5.5.3混合池最優化問題 ······························ 205 

5.5.4熱交換網絡的優化計算 ·························· 208 

5.5.5基於最優化技術的非線性方程求解 ················· 211本章習題 ················································ 213

第 6章混合整數規劃 ······································· 221 

6.1整數規劃簡介 ······································· 222 

6.1.1整數規劃與混合整數規劃 ························ 222 

6.1.2整數規劃問題的計算復雜度······················· 222 

目　錄 . vii . 

6.2窮舉方法 ··········································· 223 

6.2.1整數規劃的窮舉方法 ···························· 224 

6.2.2離散規劃問題·································· 227 

6.2.3 0.1規劃的窮舉方法 ···························· 228 

6.2.4混合整數規劃的嘗試 ···························· 230 

6.3混合整數規劃問題的求解 ······························ 232 

6.3.1混合整數線性規劃 ······························ 232 

6.3.2整數規劃問題的 LMI求解方法 ···················· 235 

6.3.3混合整數非線性規劃 ···························· 235 

6.3.4一類離散規劃問題的求解 ························ 238 

6.3.5一般離散規劃問題的求解 ························ 239 

6.4 0.1混合整數規劃的求解 ······························ 241 

6.4.1 0.1線性規劃問題的求解························· 241 

6.4.2 0.1非線性規劃問題的求解 ······················· 246 

6.5混合整數規劃應用···································· 248 

6.5.1最優用料問題·································· 248 

6.5.2指派問題 ····································· 249 

6.5.3旅行商問題 ··································· 251 

6.5.4背包問題 ····································· 255 

6.5.5數獨的填寫 ··································· 256本章習題 ················································ 260第 7章多目標規劃 ········································· 265 

7.1多目標規劃簡介 ····································· 266 

7.1.1多目標規劃的背景介紹 ·························· 266 

7.1.2多目標規劃的數學模型 ·························· 267 

7.1.3多目標規劃問題的圖解舉例······················· 268 

7.2多目標規劃轉換成單目標規劃問題 ······················· 270 

7.2.1無約束多目標函數的最小二乘求解 ················· 270 

7.2.2線性加權變換及求解 ···························· 272 

7.2.3線性規劃問題的最佳妥協解······················· 273 

7.2.4線性規劃問題的最小二乘解······················· 275 

7.2.5基於問題的描述與求解 ·························· 276 

7.3 Pareto最優解 ······································· 276 

7.3.1多目標規劃解的不唯一性 ························ 276 

7.3.2解的占優性與 Pareto解集 ························ 277 

7.3.3 Pareto解集的計算 ······························ 278 

. viii . MATLAB最優化計算

7.4極小極大問題求解···································· 281本章習題 ················································ 287第 8章動態規劃與最優路徑 ·································· 289 

8.1動態規劃簡介 ······································· 290 

8.1.1動態規劃的基本概念與數學模型 ··················· 290 

8.1.2線性規劃問題的動態規劃求解演示 ················· 291 

8.2有向圖的路徑尋優···································· 292 

8.2.1有向圖應用舉例································ 292 

8.2.2有向圖最短路徑問題的手工求解 ··················· 293 

8.2.3逆序遞推問題的動態規劃表示····················· 294 

8.2.4圖的矩陣表示方法 ······························ 295 

8.2.5有向圖搜索及圖示 ······························ 295 

8.2.6新版本 MATLAB的圖表示 ······················· 299 

8.2.7 Dijkstra最短路徑算法及實現 ····················· 301 

8.3無向圖的路徑最優搜索 ································ 303 

8.3.1無向圖的矩陣描述 ······························ 303 8.3.2絕對坐標節點的最優路徑規劃算法與應用············ 304本章習題 ················································ 305

第 9章智能優化方法 ······································· 308 

9.1智能優化算法簡介···································· 309 

9.1.1遺傳算法簡介·································· 309 

9.1.2粒子群優化算法································ 310 

9.2 MATLAB全局優化工具箱 ····························· 310 

9.3最優化問題求解舉例與對比研究························· 313 

9.3.1無約束最優化問題 ······························ 313 

9.3.2有約束最優化問題 ······························ 316 

9.3.3混合整數規劃問題求解 ·························· 322 

9.3.4基於遺傳算法的離散規劃問題····················· 324本章習題 ················································ 326參考文獻··················································· 327 MATLAB函數名索引 ········································· 331術語索引··················································· 335