Convex Optimization.pdf

所需积分/C币:38 2019-07-21 13:55:06 6.74MB PDF
138
收藏 收藏
举报

This book is about convex optimization, a special class of mathematical optimiza- tion problems, which includes least-squares and linear programming problems. It is well known that least-squares and linear programming problems have a fairly complete theory, arise in a variety of applications, and can be solved numerically very efficiently. The basic point of this book is that the same can be said for the larger class of convex optimization problems.
Convex Optimization Stephen Boyd Department of Elcctrical Enginccring Stanford University Lieven Vandenberghe Electrical Engineering Department University of California. Los Angeles 圖 CAMBRIDGE 圆 UNIVERSITY PRESS CAMBRIDGE UNIVERSITY PRES 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 ge. org Informationonthistitlewww.cambridge.org/9780521833783 ( c Cambridge University This publication is in copyright. Subject to statutory exception nd 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 Seventh printing with corrections 2009 Printed in the Unitcd 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 E 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.6-dc22 2003063284 ISBN 978-0-521-83378-3 hardback Cambridge University 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 Preface 1 Introduction 1.1 Mathematical optimization 1.2 Least-squares and linear programming 1.3 Convex optimization 1.4 Nonlinear optimization 479 1.5 Outline 11 1. 6 Notation 14 Bibliography Theory 19 2 Convex sets 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.5 Separating and supporting hyperplanes 2.6 Dual cones and generalized inequalities 51 Bibliography 59 excises 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 3.5 Log-concave and log-convex functions 104 3.6 Convexity with respect to generalized inequalities 108 Bibliography 112 Exercises· 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 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 I 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 6.5 Function fitting and interpolation 324 Bibliography ..343 E 44 7 Statistical estimation 351 7.1 Parametric distribution estimation 7. 2 Nor tric distribution es 359 7.3 Optimal detector design and hypothesis testing 364 7.4 Chebyshev and Chernoff bounds 374 7.5 Experiment design 384 Bibliograph 392 Ex xercises 393 Contents 8 Geometric problems 397 8.1 Projection on a set 39 8.2 Distance between sets ..402 8.3 Euclidean distance and angle problems 405 8.4 Extremal volume ellipsoids 8.5 Centering 416 8.6 Classification 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.2 Descent methods 463 9.3 Gradient descent methe 466 9.4 Steepest descent method ...475 9.5 Newton's method 484 9.6 Self-concordance 496 9.7 Implementation 508 Bibliography Exercises 10 Equality constrained minimization 521 10.1 Equality constrained minimization problems .521 10.2 Newton's method with equality constraints 10.3 Infeasible start Newton method .531 10.4 Implementation Bibliography 556 Exercises 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 579 11.5 Com plexity analysis via self-concordance 11.6 Problems with generalized inequalities ..596 11.7 Primal-dual interior-point methods 11.8 Implementation 615 Bibliography 621 excises 623 Contents Appendices 631 A Mathematical background 633 A 1 Norm 633 A2 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 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

...展开详情
试读 127P Convex Optimization.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
Convex Optimization.pdf 38积分/C币 立即下载
1/127
Convex Optimization.pdf第1页
Convex Optimization.pdf第2页
Convex Optimization.pdf第3页
Convex Optimization.pdf第4页
Convex Optimization.pdf第5页
Convex Optimization.pdf第6页
Convex Optimization.pdf第7页
Convex Optimization.pdf第8页
Convex Optimization.pdf第9页
Convex Optimization.pdf第10页
Convex Optimization.pdf第11页
Convex Optimization.pdf第12页
Convex Optimization.pdf第13页
Convex Optimization.pdf第14页
Convex Optimization.pdf第15页
Convex Optimization.pdf第16页
Convex Optimization.pdf第17页
Convex Optimization.pdf第18页
Convex Optimization.pdf第19页
Convex Optimization.pdf第20页

试读结束, 可继续阅读

38积分/C币 立即下载 >