convex optimization---Stephen Boyd，Lieven Vandenberghe

【实例简介】
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 . . . . . . . .
Convex Optimization Stephen boyd Dcpartment 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 8RU, 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 no reproduction of any part may take place without the written permission of Cambridge University Press First published 2004 Sixth printing with corrections 2008 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 519.6dc22 2003063284 ISBN 978-0-521-83378-3 hardback Cambridge Lniversity Press has no responsiblity for the persistency or accuracy of URls for external 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 14 Bibliography Theory 19 2 Convex set 21 2.1 Affine and convex sets 21 2.2 Some important examples 2.3 Operations that preserve convexity 35 2. 4 Generalized inequalities 2.5S 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 95 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 inequa lity constraints 167 4.7 Vector optimization 174 Bibliography 188 Exercises ...189 5 Dualit 215 5.1 The Lagrange dual function 215 5.2 The lagrange dual probler 223 5.3 Geometric interpretation 232 5. 4 Saddle-point interpretation 237 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 Xercises 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 6.5 Function fitting and interpolation 324 Bibliography 343 E× excises 44 7 Statistical estimation 351 7.1 Parametric distribution estimation 35 7.2 Nonparametric distribution estimation 359 7.3 Optimal detector design and hypothesis testing 364 7. 4 Chebyshev and Chernoff be 374 7.5 Experiment design ..384 Bibliograph 392 Exerci 393 Content: 8 Geometric problem 397 8.1P 397 8.2 Distance between sets 402 8.3 Euclidean distance and angle problems 405 8.4 Extremal volume ellipsoids 8.5C g 416 8.6 Classificatio 422 8.7 Placement and location 432 8.8 Floor planning 438 Bibliography 446 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 Newton's method 484 9.6 Self-concord 9.7 Implementation lography 10 Equality constrained 521 10. 1 Equality constrained minimization problem .521 10.2 Newton's method with equality constraints 525 10.3 Infeasible start Newton method 531 10.4 Implementation 542 Bibliograph 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 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 Contents Appendices 631 a Mathematical background 633 A 1 Norms 633 A 2 Anal 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 C2 Solving linear equations with factored matrices .664 C 3 LU, Cholesky, and LDL factorization 668 C 4 Block elimination and Schur complements ..672 C5 Solving underdetermined linear equations 681 Bibliography ..684 References 685 Notation 697 Index 701 【实例截图】
【核心代码】