实例介绍
【实例截图】
【核心代码】
Contents Preface xi 1 Introduction 1 1.1 Mathematical optimization . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Least-squares and linear programming . . . . . . . . . . . . . . . . . . 4 1.3 Convex optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Nonlinear optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 I Theory 19 2 Convex sets 21 2.1 Affine and convex sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Some important examples . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 Operations that preserve convexity . . . . . . . . . . . . . . . . . . . . 35 2.4 Generalized inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.5 Separating and supporting hyperplanes . . . . . . . . . . . . . . . . . . 46 2.6 Dual cones and generalized inequalities . . . . . . . . . . . . . . . . . . 51 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3 Convex functions 67 3.1 Basic properties and examples . . . . . . . . . . . . . . . . . . . . . . 67 3.2 Operations that preserve convexity . . . . . . . . . . . . . . . . . . . . 79 3.3 The conjugate function . . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.4 Quasiconvex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 3.5 Log-concave and log-convex functions . . . . . . . . . . . . . . . . . . 104 3.6 Convexity with respect to generalized inequalities . . . . . . . . . . . . 108 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 viii Contents 4 Convex optimization problems 127 4.1 Optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.2 Convex optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 4.3 Linear optimization problems . . . . . . . . . . . . . . . . . . . . . . . 146 4.4 Quadratic optimization problems . . . . . . . . . . . . . . . . . . . . . 152 4.5 Geometric programming . . . . . . . . . . . . . . . . . . . . . . . . . . 160 4.6 Generalized inequality constraints . . . . . . . . . . . . . . . . . . . . . 167 4.7 Vector optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 5 Duality 215 5.1 The Lagrange dual function . . . . . . . . . . . . . . . . . . . . . . . . 215 5.2 The Lagrange dual problem . . . . . . . . . . . . . . . . . . . . . . . . 223 5.3 Geometric interpretation . . . . . . . . . . . . . . . . . . . . . . . . . 232 5.4 Saddle-point interpretation . . . . . . . . . . . . . . . . . . . . . . . . 237 5.5 Optimality conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 5.6 Perturbation and sensitivity analysis . . . . . . . . . . . . . . . . . . . 249 5.7 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 5.8 Theorems of alternatives . . . . . . . . . . . . . . . . . . . . . . . . . 258 5.9 Generalized inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . 264 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 II Applications 289 6 Approximation and fitting 291 6.1 Norm approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 6.2 Least-norm problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 6.3 Regularized approximation . . . . . . . . . . . . . . . . . . . . . . . . 305 6.4 Robust approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 6.5 Function fitting and interpolation . . . . . . . . . . . . . . . . . . . . . 324 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 7 Statistical estimation 351 7.1 Parametric distribution estimation . . . . . . . . . . . . . . . . . . . . 351 7.2 Nonparametric distribution estimation . . . . . . . . . . . . . . . . . . 359 7.3 Optimal detector design and hypothesis testing . . . . . . . . . . . . . 364 7.4 Chebyshev and Chernoff bounds . . . . . . . . . . . . . . . . . . . . . 374 7.5 Experiment design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393 Contents ix 8 Geometric problems 397 8.1 Projection on a set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 8.2 Distance between sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 8.3 Euclidean distance and angle problems . . . . . . . . . . . . . . . . . . 405 8.4 Extremal volume ellipsoids . . . . . . . . . . . . . . . . . . . . . . . . 410 8.5 Centering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416 8.6 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422 8.7 Placement and location . . . . . . . . . . . . . . . . . . . . . . . . . . 432 8.8 Floor planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 III Algorithms 455 9 Unconstrained minimization 457 9.1 Unconstrained minimization problems . . . . . . . . . . . . . . . . . . 457 9.2 Descent methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 9.3 Gradient descent method . . . . . . . . . . . . . . . . . . . . . . . . . 466 9.4 Steepest descent method . . . . . . . . . . . . . . . . . . . . . . . . . 475 9.5 Newton’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 9.6 Self-concordance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496 9.7 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514 10 Equality constrained minimization 521 10.1 Equality constrained minimization problems . . . . . . . . . . . . . . . 521 10.2 Newton’s method with equality constraints . . . . . . . . . . . . . . . . 525 10.3 Infeasible start Newton method . . . . . . . . . . . . . . . . . . . . . . 531 10.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 11 Interior-point methods 561 11.1 Inequality constrained minimization problems . . . . . . . . . . . . . . 561 11.2 Logarithmic barrier function and central path . . . . . . . . . . . . . . 562 11.3 The barrier method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568 11.4 Feasibility and phase I methods . . . . . . . . . . . . . . . . . . . . . . 579 11.5 Complexity analysis via self-concordance . . . . . . . . . . . . . . . . . 585 11.6 Problems with generalized inequalities . . . . . . . . . . . . . . . . . . 596 11.7 Primal-dual interior-point methods . . . . . . . . . . . . . . . . . . . . 609 11.8 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623 x Contents Appendices 631 A Mathematical background 633 A.1 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 A.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637 A.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639 A.4 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640 A.5 Linear algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652 B Problems involving two quadratic functions 653 B.1 Single constraint quadratic optimization . . . . . . . . . . . . . . . . . 653 B.2 The S-procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655 B.3 The field of values of two symmetric matrices . . . . . . . . . . . . . . 656 B.4 Proofs of the strong duality results . . . . . . . . . . . . . . . . . . . . 657 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659 C Numerical linear algebra background 661 C.1 Matrix structure and algorithm complexity . . . . . . . . . . . . . . . . 661 C.2 Solving linear equations with factored matrices . . . . . . . . . . . . . . 664 C.3 LU, Cholesky, and LDLT factorization . . . . . . . . . . . . . . . . . . 668 C.4 Block elimination and Schur complements . . . . . . . . . . . . . . . . 672 C.5 Solving underdetermined linear equations . . . . . . . . . . . . . . . . . 681 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684 References 685 Notation 697 Index 701
标签: Optimization IO IM
网友评论
小贴士
感谢您为本站写下的评论,您的评论对其它用户来说具有重要的参考价值,所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字,对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙,所以请不要反馈意义不大的重复字符,也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明,或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦,又没人会搭理,于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享,对搜索内容的合法性不具有预见性、识别性、控制性,仅供学习研究,请务必在下载后24小时内给予删除,不得用于其他任何用途,否则后果自负。基于互联网的特殊性,平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查;无论平台是否已进行审查,用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场,基于网友分享,根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定,若资源存在侵权或相关问题请联系本站客服人员,点此联系我们。关于更多版权及免责申明参见 版权及免责申明
支持(0) 盖楼(回复)