Convex Optimization (Stanford CVX101)

【实例简介】
Convex Optimization (Stanford CVX101)
Convex Optimization Stephen boyd Department of Elcctrical Enginccring Stanford umiversity Lieven Vandenberghe Electrical Engineering Department University of California. Los Angeles 圖 CAMBRIDGE 圆 UNIVERSITY PRESS CAMBRIDGE UNIVERSITY PRESS Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, Sao Paolo, Delhi Cambridge University Press The Edinburgh Building, Cambridge, CB2 &RU, UK Published in the United States of America by Cambridge University Press, New York http://www.cambridge.org Informationonthistitlewww.cambridge.org/9780521833783 Cambridge University Press 2004 This publication is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements duction of an the written permission of Cambridge University Press First published 2004 Seventh printing with corrections 2009 Printed in the United Kingdom at the University Press, Cambridge A catalogue record for this publication is available from the British Library Library of Congress Cataloguing-in-Publication data boyd, stephen p Convex Optimization/ Stephen Boyd Lieven Vandenberghe Includes bibliographical references and index ISBN0521833787 1. Mathematical optimization. 2. Convex functions. I. Vandenberghe, Lieven. II. Title QA402.5.B692004 2003063284 ISBN 978-0-521-83378-3 hardback Cambridge Lniversity Press has no responsiblity for the persistency or accuracy of URls for cxtcrnal or third-party internet websites referred to in this publication, and docs not guarantee that any content on such websites is, or will remain, accurate or appropriate Anna, Nicholas and nora Daniel and Margriet Contents Prefa 1 Introduction 1.1 Mathematical optimizati 1.2 Least-squares and linear programming 4 1.3C 1. 4 Nonlinear optimization 1.5 Outline 1. 6 Notation Bibliography Theory 19 2 Convex sets 21 2.1 Affine and convex sets 21 2.2 Some important examples 2 2.3 Operations that preserve convexity 35 2.4 Generalized inequalities 2.5 Separating and supporting hyperplanes 2.6 Dual cones and generalized inequalities .51 Bibliograph 59 Exercises 60 3 Convex functions 67 3.1 Basic properties and examples 67 3.2 Operations that preserve convexity 3.3 The conjugate function 90 3.4 Quasiconvex functions 3.5 Log-concave and log-convex functions 104 3.6 Convexity with respect to generalized inequalities 108 Bibliograph excises 113 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 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 lag dual proble 223 5. 3 Geometric interpretation ....232 5. 4 Saddle-point interpretation 237 5.5 optimality conditions .241 5.6 Perturbation and sensitivity ana lysis 249 5.7 Examples ..253 5. 8 T heorems of alternatives 258 5.9 Generalized inequalities 264 Bibliograph 272 Exercises 273 I Applications 289 6 Approximation and fitting 291 6.1 Norm approximation 291 6.2 Least-norm problems 302 6. 3 Regularized approximation 05 6.4 Robust approximation 318 6.5 Function fitting and interpolation 324 Bibliography 343 Eⅹ ercis 44 7 Statistical estimation 351 7.1 Parametric distribution estimation 35 7.2No tric distribution estimati 359 7.3 Optimal detector design and hypothesis testing 364 7. 4 Chebyshev and Chernoff be 374 7.5 Experiment design 384 Bibliograph apl 392 Exerci 393 Contents 8 Geometric problem 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 Exercises 447 I Algorithms 455 9 Unconstrained minimization 457 9.1 Unconstrained minimization problems 45′ 9.2D 463 9.3 Gradient descent method 466 9.4 Steepest descent method ...475 9.5 Newtons method 484 9. 6 Self-concord 9.7 Implementation lography 10 Equality constrained 521 10.1 Equality constrained minim proble 521 10.2 Newton's method with equality constraints 525 10.3 Infeasible start Newton method 531 10.4 Implementation 542 Bibliography E× excises 557 11 Interior-point methods 561 11.1 Ineq uality 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 11.5 Complexity analysis via self-concordance .585 11.6 Problems with generalized inequalities 596 11.7 Primal-dual interior-point methods 11. 8 Implementation 615 Bibliography 621 Ex xercises 623 X Content: Appendices 631 a Mathematical background 633 A 1 Norms 633 A 2 Anal 637 A 3 Functions ..639 A 4 Derivatives 640 A.5 Line abra 645 Bibliography 652 B Problems involving two quadratic functions 653 B.1 Single constraint quadratic optimization 653 B. 2 The s-pr rocedure 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 C2 Solving linear equations with factored matrices 664 C3 LU, Cholesky, and LDL factorization 668 C 4 Block elimination and Schur complements 672 C 5 Solving underdetermined linear equations 681 Bibliography 684 References 685 Notation 697 ngex 701 【实例截图】
【核心代码】