电子科技大学：《最优化理论与应用 Optimization Theory and Applications》课程教学资源（课件讲稿，共六章）最优化理论与方法 OPTIMIZATION THEORY AND METHODS

最优化理论与方法 OPTIMIZATION THEORY AND METHODS 张晓伟 数学科学学院 Zhangxiaowei@uestc.edu.cn http://faculty.uestc.edu.cn/zhangxiaowei VERSION:20200816151400

`zn؆{ Optimization Theory and Methods Ü¡• êƉÆÆ Zhangxiaowei@uestc.edu.cn http://faculty.uestc.edu.cn/zhangxiaowei Version: 20200816151400

目 录 前言 II 目录 XIII 算法 XV 勘误 XVI 第一部分算法篇 1 第一章最优化问题与数学基础 2 81.1最优化问题 ...... 2 1.1.1 发展史........ 2 1.1.2一些例子....... 4 1.1.3数学模型.，..... 17 1.1.4 问题分类....... 20 IV

8 ¹ c ó II 8 ¹ XIII Ž { XV t Ø XVI 1Ü© Ž{Ÿ 1 1Ù `z¯K†êÆÄ: 2 ➜ 1.1 `z¯K. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 uФ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 ~f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.3 êÆ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.1.4 ¯K©a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 IV

§1.2数学基础 21 1.2.1 等值线 21 1.2.2 可微与梯度：： 24 1.2.3 方向导数..... 28 1.2.4 Hesse矩阵...... 30 1.2.5 多元函数的Taylor展式 , 35 1.2.6 开集与闭集..... 39 1.2.7 局部极小点.：：.. 42 1.2.8最优性条件..... 43 1.2.9 凸集...... 45 1.2.10凸函数 47 1.2.11凸规划 ,,,,,, 53 第二章 线性规划和单纯形方法 59 §2.1例子与标准形式 59 §2.2二维线性规划的图解法 72 V

➜ 1.2 ê Æ Ä : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.2.1  Š ‚. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.2.2 Œ ‡ † F Ý . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.2.3  •  ê . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.2.4 Hesse Ý . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.2.5 õ ¼ ê Taylor Ð ª . . . . . . . . . . . . . . . . . . . . . . . . 35 1.2.6 m 8 † 4 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 1.2.7 Û Ü 4 : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 1.2.8  ` 5 ^ ‡ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 1.2.9 à 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 1.2.10 à ¼ ê. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 1.2.11 à 5 y. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 1Ù ‚55yÚüX/{ 59 ➜ 2.1 ~f†IO/ª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 ➜ 2.2 ‘‚55yã){ . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 V

82.3基本概念与解的性质 .... 73 2.3.1基本概念 76 2.3.2一个例子 80 2.3.3解的性质 83 82.4单纯形法...... 92 2.4.1准备工作 92 2.4.2单纯形方法....... 119 2.5初始基可行解的确定法 135 2.5.1两阶段方法...... 138 2.5.2大M法....... 150 S2.6单纯形法的改进 .155 2.6.1避免循环 .155 2.6.2修正单纯形法...... .......158 第三章 对偶线性规划 168 83.1对偶问题的提出..... 168 3.1.1经济问题 168 VI

➜ 2.3 Ä  V g † )  5 Ÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 2.3.1 Ä  V g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 2.3.2 ‡ ~ f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2.3.3 )  5 Ÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 ➜ 2.4 üX / { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 2.4.1 O  ó Š . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 2.4.2 üX /{ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 ➜ 2.5 Ð © Ä Œ 1 )  ( ½ { . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 2.5.1 ü  ã{ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 2.5.2 Œ M { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 ➜ 2.6 üX / {  U ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 2.6.1 ;  Ì ‚ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 2.6.2 ? üX / {. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 1nÙ éó‚55y 168 ➜ 3.1 éó¯KJÑ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 3.1.1 ² L ¯ K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 VI

3.1.2对称形式 174 3.1.3非对称形式...... .178 3.1.4 混合形式 183 §3.2对偶定理 ,, 187 83.3对偶单纯形方法 204 3.3.1基本思想 ,,, 204 3.3.2对偶单纯形法..... 213 83.4对偶线性规划的应用 ,,,, 219 3.4.1对偶单纯形法的应用. 219 3.4.2 影子价格...... 229 第四章 无约束最优化计算方法 233 S4.1下降迭代算法 ,, 234 4.1.1基本思想 234 4.1.2一维搜索 .237 4.1.3 收敛速度 , 239 4.1.4 终止准则 242 VII

3.1.2 é ¡ / ª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 3.1.3 š é ¡ / ª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 3.1.4 · Ü / ª . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 ➜ 3.2 é ó ½ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 ➜ 3.3 é óüX /{ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 3.3.1 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 3.3.2 é óüX / {. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 ➜ 3.4 é ó ‚ 5 5 y A^ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 3.4.1 é óüX / { A^ . . . . . . . . . . . . . . . . . . . . . . . . . . 219 3.4.2 K f d ‚ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229 1oÙ Ãå`zOŽ{ 233 ➜ 4.1 eüSŽ{ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 4.1.1 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 4.1.2 ‘|¢ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 4.1.3  ñ „ Ý . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 4.1.4 ªŽ O K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 VII

§4.2精确一维搜索.. 243 4.2.1黄金分割法 243 4.2.1.1单峰函数 ..243 4.2.1.2 基本思想 ..245 4.2.1.3 算法分析 ..250 4.2.2 Fibonacci法.. 251 4.2.2.1 基本思想 251 4.2.2.2 算法过程 253 4.2.2.3 算法分析 255 4.2.3二次插值法.·· 256 4.2.3.1基本思想 256 4.2.3.2三点二次插值法， 258 4.2.4两点三次插值法 261 4.2.4.1基本思想 261 4.2.4.2三次多项式. 262 §4.3非精确一维搜索. 263 4.3.1 Goldstein准则. ..265 VIlI

➜ 4.2 ° ( ‘|¢ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 4.2.1 ‘ 7 ©  { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 4.2.1.1 ü ¸ ¼ ê . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 4.2.1.2 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 4.2.1.3 Ž{© Û . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 4.2.2 Fibonacci { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 4.2.2.1 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 4.2.2.2 Ž { L § . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 4.2.2.3 Ž{© Û . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 4.2.3  g Š { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 4.2.3.1 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 4.2.3.2 n :  g Š {. . . . . . . . . . . . . . . . . . . . . . . . 258 4.2.4 ü : n g Š { . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 4.2.4.1 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 4.2.4.2 n g õ ‘ ª . . . . . . . . . . . . . . . . . . . . . . . . . . 262 ➜ 4.3 š ° ( ‘|¢ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 4.3.1 Goldstein O K. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265 VIII

4.3.2 Volfe准则.. 267 4.3.3 Armijo准则 269 4.3.4收敛性定理. 272 §4.4最速下降法.. 276 4.4.1基本思想. ..276 4.4.2最速下降法 278 4.4.3收敛性.. 278 4.4.4最优步长 282 §4.5牛顿法... 286 4.5.1基本思想 286 4.5.2几何解释 288 4.5.3牛顿法. 290 4.5.4优缺点及其改进 292 4.5.5收敛性 294 §4.6共轭方向法. 。。 299 4.6.1共轭梯度法 ..308 4.6.1.1FR共轭梯度法 ..312 X

4.3.2 Wolfe O K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 4.3.3 Armijo O K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 4.3.4  ñ 5 ½ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 ➜ 4.4  „ e ü {. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 4.4.1 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 4.4.2  „ e ü { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 4.4.3  ñ 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 4.4.4  ` Ú  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282 ➜ 4.5 Ú î { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 4.5.1 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 4.5.2 A Û ) º . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 4.5.3 Ú î {. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 4.5.4 ` " : 9 Ù U ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 4.5.5  ñ 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 ➜ 4.6
Ý  • {. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 4.6.1
Ý F Ý { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 4.6.1.1 FR
Ý F Ý { . . . . . . . . . . . . . . . . . . . . . . . . 312 IX

4.6.2 拟牛顿法 .320 4.6.2.1 一般格式 .320 4.6.2.2 对称秩一公式.... 321 4.6.2.3 对称秩一算法：...... .328 4.6.2.4对称秩二公式：...... 337 4.6.2.5DFP算法........ ......346 4.6.2.6 Broyden和Huang类校正公式 ...............351 84.7信赖域方法...... ..356 4.7.1基本思想 ....357 4.7.2信赖域方法的收敛性 ..... ..... 365 第五章 约束最优化方法 367 85.1最优性条件..... .368 5.1.1可行方向 368 5.1.2一阶必要条件....... ...372 5.1.3二阶充分条件.....，，， ..... 377 X

4.6.2 [Úî{ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 4.6.2.1 „‚ª . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 4.6.2.2 顝úª . . . . . . . . . . . . . . . . . . . . . . . . . 321 4.6.2.3 顝Ž{ . . . . . . . . . . . . . . . . . . . . . . . . . 328 4.6.2.4 顝úª . . . . . . . . . . . . . . . . . . . . . . . . . 337 4.6.2.5 DFPŽ{ . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 4.6.2.6 BroydenÚHuangaúª . . . . . . . . . . . . . . . 351 ➜ 4.7 &6{. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 4.7.1 ÄgŽ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 4.7.2 &6{Âñ5 . . . . . . . . . . . . . . . . . . . . . . . . . . 365 1ÊÙ å`z{ 367 ➜ 5.1 `5^‡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368 5.1.1 Œ1• . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368 5.1.2 7‡^‡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372 5.1.3 ¿©^‡. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 X

§5.2惩罚函数法... 386 5.2.1基本思想 386 5.2.2罚因子与拉格朗日乘子之间的关系 387 §5.3外点罚函数法 389 5.3.1基本思想 ...389 5.3.2一般约束最优化处理. ...391 5.3.3算法.. ..394 5.3.4收敛性定理 397 §5.4内点罚函数法 403 5.4.1基本思想. ..404 5.4.2算法... 408 5.4.3收敛性定理 411 5.4.4小结 414 §5.5乘子法. ...415 §5.6 Rosen梯度投影法. 432 5.6.1基本思想 433 5.6.2下降可行方向的确定 ..435 XI

➜ 5.2 ¨ v ¼ ê {. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386 5.2.1 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386 5.2.2 v Ï f † . ‚ K F ¦ f ƒ m  ' X . . . . . . . . . . . . . . . . . . 387 ➜ 5.3 : v ¼ ê { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 5.3.1 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 5.3.2 „  å  ` z ? n . . . . . . . . . . . . . . . . . . . . . . . . . . 391 5.3.3 Ž { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394 5.3.4  ñ 5 ½ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 ➜ 5.4 S : v ¼ ê { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403 5.4.1 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404 5.4.2 Ž { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 5.4.3  ñ 5 ½ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 5.4.4 ( . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414 ➜ 5.5 ¦ f { . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415 ➜ 5.6 Rosen F Ý Ý K {. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432 5.6.1 Ä  g Ž . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 5.6.2 e ü Œ 1  •  ( ½ . . . . . . . . . . . . . . . . . . . . . . . . . . 435 XI

5.6.3直线搜索及终止准则...... .440 5.6.4算法........ .442 第六章 直接搜索方法 455 6.1步长加速法.. 455 6.1.1基本思想 456 6.1.2探索性移动........ 457 6.1.3 Hooke-Jeeves步长加速法. 459 S6.2 Powell方向加速法 ,, 462 6.2.1基本算法 462 6.2.2 共轭程度的判别 .470 6.2.3 Powelli改进算法.... .475 6.2.4基本算法........ .475 第二部分 应用篇 477 索引 478 习题 484 XII

5.6.3 †‚|¢9ªŽOK . . . . . . . . . . . . . . . . . . . . . . . . . . 440 5.6.4 Ž{ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442 18Ù †|¢{ 455 ➜ 6.1 Ú\„{. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455 6.1.1 ÄgŽ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 6.1.2 &¢5£Ä . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457 6.1.3 Hooke-JeevesÚ\„{ . . . . . . . . . . . . . . . . . . . . . . 459 ➜ 6.2 Powell•\„{ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462 6.2.1 ÄŽ{ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462 6.2.2
ݧÝO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470 6.2.3 PowellU?Ž{ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475 6.2.4 ÄŽ{ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475 1Ü© A^Ÿ 477 ¢ Ú 478 S K 484 XII