实例介绍
【实例简介】
经典书籍不用多介绍，优化大师BertSekas经典力作，凸优化理论，包含最新版的第6章算法部分
Athena scientific Post Office Box 805 Nashua. NH 03061-0805 U.s.A Email: infoathenasc com Www:httP://www.athenasc.com C 2009 Dimitri P Bertsekas All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means(including photocopying, recording or information storage and retrieval) without permission in writing from the publisher. Publisher's Cataloging-in-Publication Data Bertsckas. Dimitri p Convex Optimization Thcory Includes bibliographical refercnces and index 1. Nonlinear Programming 2. Mathematical Optimization. I. Title T578B4752009 519.703 Library of congress control Number: 2002092168 ISBN-10:1-886529-31-0,ISBN-13:978-1-886529-31-1 Contents 1. Basic Concepts of Convex Analysis 1.1. Convex Scts and Functions p 1.1.1. Convex functions p.5 1.1.2. Closedness and Semicontinuity p 1.1.3. Operations with Convex Functions p.11 1. 4. Characterizations of Differentiable Convex Functions . p. 13 1.2. Convex and Affine hulls ·p.19 1.3. Relative Interior and Closure p.23 1.3.1. Calculus of relative Interiors and closures p.28 1.3.2. Continuity of Convex Functions p.35 1.3.3, Closures of functions p.37 1.4. Recession cones p.43 1.4.1 Directions of recession of a convex function p.50 1.4.2. Nonemptiness of Intersections of Closed Sets .p.57 1.4.3. Closedness Under Linear Transformations p.64 1.5. Hyperplanes p.67 1.5.1. Ilyperplane Separation p.68 1.5.2. Proper Hyperplane Separation p.73 1.5.3. Nonvertical Hyperplane Separation p.80 1.6. Conjugate Functions p.82 1.7. Summary p.89 2. Basic Concepts of Polyhedral Convexity p.91 2. 1. Extreme points p.92 2.2. Polar cones p 99 2.3. Polyhedral Sets and Functions p.102 2.3. 1. Polyhedral Cones and Farkas' Lemma 102 2.3.2. Structure of Poly hedral Sets p.104 2.3.3. Polyhedral functions p.109 2. 4. Polyhedral Aspects of Optimization p.111 3. Basic Concepts of Convex Optimization p.115 3.1. Constrained Optimization p.1l6 3.2. Existence of Optimal Solutions 18 Contents 3.3. Partial minimization of Convex functions 122 3.4. Saddle point and Minimax Theory p.127 4. Geometric Duality Framework p.131 4.1. Min Common /Max Crossing Duality p.132 4.2. Some Special cases p.137 4.2. 1. Connection to Conjugate Convex Functions p.137 4.2.2. General Optimization Duality p.138 4.2.3. Optimization with Inequality Constraints p.139 4.2. 4. Augmented Lagrangian duality p.140 4.2.5. Minimax Problems p.141 4.3. Strong Duality Theore 146 4.4. Existence of Dual Optimal Solutions p.149 4.5. Duality and polyhedral convexity p.153 4.6. Summary .p.158 5. Duality and Optimization .:p.157 5.1. Nonlinear Farkas'lemma p.160 5.2. Linear Programming Duality .p.164 5.3. Convex Programming Duality p.167 5.3.l. Strong duality Theorem-Inequality Constraints p.168 5.3.2. Optimality Conditions p.169 5.3.3. Partially Polyhedral constraints ..p.171 5.3.4. Duality and Existence of Optimal Primal solutions .. p 176 5.3.5. Fenchel duality p.179 5.3.6. Conic Duality p.181 5.4. Subgradients and Optimality conditions ..p.182 5.4.1. Subgradients of Conjugate Functions p.187 5.4.2. Subdifferential Calculus p.192 5.4.3. Opt. iInality Conditions p.195 5.4.4. Directional Derivatives p.196 5.5. Minimax Theory p.200 5.5. 1. Minimax Duality Theorems p.200 5.5.2. Saddle point theorems p).204 5.6. Theorems of the alternative p.209 5.7. Nonconvex Problems p.216 5.7.1. Duality Gap in Separable Problems p.217 5.7.2. Duality Gap in Minimax Problems p.226 Appendix A: Mathematical Background .p.227 Notes and Sources p.239 ABOUT THE AUTHOR Dimitri Bertsekas studied Mechanical and Electrical Engineering at the National Technical University of Athens. Greece, and obtained his Ph. D. in system science from the Massachusetts Institute of technology He has held faculty positions with the Engineering- Economic Systems De partment, Stanford University, and the Electrical Engineering Department of the University of lllinois, Urbana. Since 1979 he has been teaching at the Electrical Engineering and Computer science Department of the Mas sachusetts Institute of Technology(MIT), where he is currently McAfee Professor of engineering His teaching and research spans several fields, including deterministic optimization, dynainic programming and stochastic control, large-scale and distributed computation, and data communication networks. He has au thored or coauthored numerous research papers and fourteen books, several of which are used as textbooks in mit classes, including "Nonlinear Pro gramming,"“ Dynamic Programming and Optimal Control,”“ Data net works "introduction to Probability, as well as the present book He often consults with private industry and has held editorial positions in several journals Professor bertsekas was awarded the Informs 19 97 Prize for re search Excellence in the Interface Between Operations Research and Com puter Science for his book "Neuro-Dynamic Programming(co-authored with John Tsitsiklis), the 2000 Greek National Award for Operations Re search, and the 2001 ACC John R. Ragazzini Education Award. In 2001 he was elected to the United States National academy of Engineering ATHENA SCIENTIFIC OPTIMIZATION AND COMPUTATION SERIES 1. Convex Optimization Theory, by Dimitri P. Bertsekas, 2009 ISBN978-1-88652931-1,256 pages 2. Introduction to Probability, 2nd Edition, by Dimitri P. Bertsekas and John N. Tsitsiklis, 2008, ISBN 978-1-886529-23-6, 544 pages 3. Dynamic Programming and Optimal Control, Two-Volume Set by Dimitri P. Bertsekas, 2007, ISBN 1-886529-08-6, 1020 pages 4. Convex Analysis and Optimization, by Dimitri P. Bertsekas, with Angelia Nedic and Asuman E. Ozdaglar, 2003, ISBN 1-886529- 45-0,560 pages 1999, ISBN 1-886529-00-0, 791 page, by Dimitri P. Bertsekas 5. Nonlinear Programming, 2nd Edition 6.Network Optimization: Continuous and Discrete Models, by Dim itri P. Bertsekas, 1998, ISBN 1-886529-02-7, 608 pages 7. Network Flows and Monotropic Optimization, by R. Tyrrell rock afellar, 1998, ISBN 1-886529-06-x, 634 pages 8. Introduction to Linear Optimization, by Dimitris Bertsimas and John N. Tsitsiklis, 1997, ISBN 1-886529-19-1, 608 pages 9. Parallel and Distributed Computation: Numerical Methods, by Dimitri P. Bertsekas and John N. Tsitsiklis. 1997. ISBN 1-886529 01-9,718 pages 10. Neuro-Dynamic Programming, by Dimitri P. Bertsekas and John N. Tsitsiklis, 1996, ISBN 1-886529-10-8, 512 pages 11. Constrained Optimization and Lagrange Multiplier Methods, b Dimitri P Bertsekas, 1996, ISBN 1-886529-04-3, 410 pages 12. Stochastic Optimal Control: The Discrete-Time Case, by dimitri P, Bertsekas and Steven E. Shreve, 1996. IsbN 1-886529-03-5 330 pages Preface This book aims at an accessible, concise, and intuitive exposition of two related subjects that find broad practical application a)Convex analysis, particularly as it relates to optimization (b) Duality theory for optimization and minimax problems, mainly within a convexity framework The focus on optimisation is to derive conditions for existence of primal and dual optimal solutions for constrained problems such as minimize f(a) subject to 2∈X,91(2) Other types of optimization problems, such as those arising in Fenchel duality, are also part of our scope. The focus on minimax is to derive conditions guaranteeing the equality inf sup o(a, x)=sup inf (a, z) c∈Xz∈z z∈zm∈X and the attainment of the“ inf and the“sup.” The treatment of convexity theory is fairly detailed. It touches upon nearly all major aspects of the subject and it is sufficient for the devel- opment of the core analytical issues of convex optimization. The mathe matical prerequisites are a first course in linear algebra and a first course in real analysis, A summary of the relevant material is provided in an appendix. Prior knowledge of linear and nonlinear optimization theory is not assumed, although it will undoubtedly be helpful in providing context and perspective. Other than this modest background, the development is self-contained, with rigorous proofs provided throughout We have aimed at a unified development of the strongest possible forms of duality with the most economic use of convexity theory. To this end, our analysis often departs from the lines of rockafellar's classic 1970 book and other books that followed the Fenchel/ Rockafellar formalism. For example, we treat differently closed set intersection theory and preserva tion of closure under linear transformations(Sections 1.4.2 and 1.4.3);we Vl1 Preface develop subdifferential calculus by using constrained optimization duality (Section 5. 4. 2); and we do not rely on concepts such as infimal convolu tion, image, polar sets and functions, bifunctions, and conjugate saddle functions. Perhaps our greatest departure is in duality theory itself: sim- ilar to Fenchel/Rockafellar, our development rests on Legendre/Fenchel conjugacy ideas, but is far more geometrical and visually intuitive Our duality framework is based on two simple geometrical problems the min common point problem and the ma crossing point problem. The salient feature of the min common/max crossing(MC/ MC) framework is its highly visual geometry, through which all the core issues of duality theory become apparent and can be analyzed in a unified way. Our approach is to obtain a handful of broadly applicable theorems within the Mc/MC frame work, and then specialize them to particular types of problems(constrained optimization, Fenchel duality, minimax problems, etc). We address all du- ality questions(existence of duality gap, existence of dual optimal solutions structure of the dual optimal solution set ), and other issues(subdifferential theory, theorems of the alternative, duality gap estimates) in this way Fundamentally, the MC/MC framework is closely connected to the conjugacy framework, and owes its power and generality to this connec tion. However, the two frameworks offer complementary starting points for analysis and provide alternative views of the geometric foundation of duality: conjugacy emphasizes functional/algebraic descriptions, while MC/MC emphasizes set/epigraph descriptions. The MC/MC framework is simpler, and seems better suited for visualizing and investigating questions of strong duality and existence of dual optimal solutions. The conjugacy franework, with its emphasis on functional descriptions, is more suitable when mathematical operations on convex functions are involved, and the calculus of conjugate functions can be brought to bear for analysis or com putation The book evolved from the earlier book of the author BNO03Onl the subject,(coauthored with A Nedic and A Ozdaglar), but has different character and objectives. The 2003 book was quite extensive was struc tured (at least in part)as a research monograph, and ained to bridge the gap between convex and nonconvex optimization using concepts of non smooth analysis. By contrast the present book is organized differently has the character of a textbook, and concentrates exclusively on convex optimization. Despite the differences, the two books have similar style and level of mathematical sophistication, and share some material The chapter-by-chapter description of the book follows Chapter 1: This chapter develops all of the convex analysis tools that are needed for the development of duality theory in subsequent chapters It covers basic algebraic concepts such as convex hulls and hyperplanes and topological concepts such as relative interior, closure, preservation of closedness ridler linea r traristorinations, and hyperplane scparation. In Preface addition, it develops subjects of special interest in duality and optimization such as recession cones and conjugate functions Chapter 2: This chapter covers polyhedral convexity concepts: cxtrcmc points, the Farkas and Minkowski-Weyl theorems, and sonc of thcir ap- plications in lincar programming It is not needed for the developments of subsequent chapters, and may be skipped at first reading Chapter 3: This chapter focuses on basic optimization concepts: types of minima, existence of solutions, and a few topics of special interest for duality theory, such as partial minimization and minimax theory Chapter 4: This chapter introduces the MC/MC duality framework. It discusses its connection with conjugacy theory, and it charts its applica- tions to constrained optimization and minimax problems. It then develops broadly applicable theorems relating to strong duality and existence of dual optimal solutions Chapter 5: This chapter specializes the duality theorems of Chapter 4 to important contexts relating to linear programming, convex programming, and minimax thcory. It also uses these thcorems as an aid for the devel- opment of additional convex analysis tools, such as a powerful nonlinear version of Farkas' Lerma, subdifferential theory, and theorems of the al ternative. a final section is devoted to nonconvex problcms and estimates of the duality gap, with spccial focus on scparable problems In aiming for brevity. I have omitted a number of topics that an instructor may wish for. One such omission is applications to specially structured problems; the book by Boyd and Vanderbergue [Bovo4], as well as my book on parallel and distributed computation with John Tsitsiklis BeT89 cover this material extensively(both books are available on line) Another important omission is computational methods. However, I have written a long supplementary sixth chapter (over 100 pages), which covers the most popular convex optimization algorithms(and some new ones), and can be downloaded from the book's web page http://www.athenasc.com/convexduality.html This chapter, together with a more comprehensive treatment of convex analysis, optimization, duality, and algorithms will be part of a more ex tensive textbook that i am currently writing. Until that time, the chapter will serve instructors who wish to cover convex optimization algorithms in addition to duality (as i do in my M I.T. course). This is a"living "chapter that will be periodically updated. Its current contents are as follows: Chapter 6 on Algorithms: 6.1. Problem Structures and Computational Approaches; 6.2. Algorithmic Descent; 6.3. Subgradient Methods; 6.4. Poly hedral approximation methods; 6.5. Proximal and bundle methods; 6.6 Dual Proximal point algorithms; 6.7. Interior Point Methods; 6.8. Approx- 【实例截图】
【核心代码】
经典书籍不用多介绍，优化大师BertSekas经典力作，凸优化理论，包含最新版的第6章算法部分
Athena scientific Post Office Box 805 Nashua. NH 03061-0805 U.s.A Email: infoathenasc com Www:httP://www.athenasc.com C 2009 Dimitri P Bertsekas All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means(including photocopying, recording or information storage and retrieval) without permission in writing from the publisher. Publisher's Cataloging-in-Publication Data Bertsckas. Dimitri p Convex Optimization Thcory Includes bibliographical refercnces and index 1. Nonlinear Programming 2. Mathematical Optimization. I. Title T578B4752009 519.703 Library of congress control Number: 2002092168 ISBN-10:1-886529-31-0,ISBN-13:978-1-886529-31-1 Contents 1. Basic Concepts of Convex Analysis 1.1. Convex Scts and Functions p 1.1.1. Convex functions p.5 1.1.2. Closedness and Semicontinuity p 1.1.3. Operations with Convex Functions p.11 1. 4. Characterizations of Differentiable Convex Functions . p. 13 1.2. Convex and Affine hulls ·p.19 1.3. Relative Interior and Closure p.23 1.3.1. Calculus of relative Interiors and closures p.28 1.3.2. Continuity of Convex Functions p.35 1.3.3, Closures of functions p.37 1.4. Recession cones p.43 1.4.1 Directions of recession of a convex function p.50 1.4.2. Nonemptiness of Intersections of Closed Sets .p.57 1.4.3. Closedness Under Linear Transformations p.64 1.5. Hyperplanes p.67 1.5.1. Ilyperplane Separation p.68 1.5.2. Proper Hyperplane Separation p.73 1.5.3. Nonvertical Hyperplane Separation p.80 1.6. Conjugate Functions p.82 1.7. Summary p.89 2. Basic Concepts of Polyhedral Convexity p.91 2. 1. Extreme points p.92 2.2. Polar cones p 99 2.3. Polyhedral Sets and Functions p.102 2.3. 1. Polyhedral Cones and Farkas' Lemma 102 2.3.2. Structure of Poly hedral Sets p.104 2.3.3. Polyhedral functions p.109 2. 4. Polyhedral Aspects of Optimization p.111 3. Basic Concepts of Convex Optimization p.115 3.1. Constrained Optimization p.1l6 3.2. Existence of Optimal Solutions 18 Contents 3.3. Partial minimization of Convex functions 122 3.4. Saddle point and Minimax Theory p.127 4. Geometric Duality Framework p.131 4.1. Min Common /Max Crossing Duality p.132 4.2. Some Special cases p.137 4.2. 1. Connection to Conjugate Convex Functions p.137 4.2.2. General Optimization Duality p.138 4.2.3. Optimization with Inequality Constraints p.139 4.2. 4. Augmented Lagrangian duality p.140 4.2.5. Minimax Problems p.141 4.3. Strong Duality Theore 146 4.4. Existence of Dual Optimal Solutions p.149 4.5. Duality and polyhedral convexity p.153 4.6. Summary .p.158 5. Duality and Optimization .:p.157 5.1. Nonlinear Farkas'lemma p.160 5.2. Linear Programming Duality .p.164 5.3. Convex Programming Duality p.167 5.3.l. Strong duality Theorem-Inequality Constraints p.168 5.3.2. Optimality Conditions p.169 5.3.3. Partially Polyhedral constraints ..p.171 5.3.4. Duality and Existence of Optimal Primal solutions .. p 176 5.3.5. Fenchel duality p.179 5.3.6. Conic Duality p.181 5.4. Subgradients and Optimality conditions ..p.182 5.4.1. Subgradients of Conjugate Functions p.187 5.4.2. Subdifferential Calculus p.192 5.4.3. Opt. iInality Conditions p.195 5.4.4. Directional Derivatives p.196 5.5. Minimax Theory p.200 5.5. 1. Minimax Duality Theorems p.200 5.5.2. Saddle point theorems p).204 5.6. Theorems of the alternative p.209 5.7. Nonconvex Problems p.216 5.7.1. Duality Gap in Separable Problems p.217 5.7.2. Duality Gap in Minimax Problems p.226 Appendix A: Mathematical Background .p.227 Notes and Sources p.239 ABOUT THE AUTHOR Dimitri Bertsekas studied Mechanical and Electrical Engineering at the National Technical University of Athens. Greece, and obtained his Ph. D. in system science from the Massachusetts Institute of technology He has held faculty positions with the Engineering- Economic Systems De partment, Stanford University, and the Electrical Engineering Department of the University of lllinois, Urbana. Since 1979 he has been teaching at the Electrical Engineering and Computer science Department of the Mas sachusetts Institute of Technology(MIT), where he is currently McAfee Professor of engineering His teaching and research spans several fields, including deterministic optimization, dynainic programming and stochastic control, large-scale and distributed computation, and data communication networks. He has au thored or coauthored numerous research papers and fourteen books, several of which are used as textbooks in mit classes, including "Nonlinear Pro gramming,"“ Dynamic Programming and Optimal Control,”“ Data net works "introduction to Probability, as well as the present book He often consults with private industry and has held editorial positions in several journals Professor bertsekas was awarded the Informs 19 97 Prize for re search Excellence in the Interface Between Operations Research and Com puter Science for his book "Neuro-Dynamic Programming(co-authored with John Tsitsiklis), the 2000 Greek National Award for Operations Re search, and the 2001 ACC John R. Ragazzini Education Award. In 2001 he was elected to the United States National academy of Engineering ATHENA SCIENTIFIC OPTIMIZATION AND COMPUTATION SERIES 1. Convex Optimization Theory, by Dimitri P. Bertsekas, 2009 ISBN978-1-88652931-1,256 pages 2. Introduction to Probability, 2nd Edition, by Dimitri P. Bertsekas and John N. Tsitsiklis, 2008, ISBN 978-1-886529-23-6, 544 pages 3. Dynamic Programming and Optimal Control, Two-Volume Set by Dimitri P. Bertsekas, 2007, ISBN 1-886529-08-6, 1020 pages 4. Convex Analysis and Optimization, by Dimitri P. Bertsekas, with Angelia Nedic and Asuman E. Ozdaglar, 2003, ISBN 1-886529- 45-0,560 pages 1999, ISBN 1-886529-00-0, 791 page, by Dimitri P. Bertsekas 5. Nonlinear Programming, 2nd Edition 6.Network Optimization: Continuous and Discrete Models, by Dim itri P. Bertsekas, 1998, ISBN 1-886529-02-7, 608 pages 7. Network Flows and Monotropic Optimization, by R. Tyrrell rock afellar, 1998, ISBN 1-886529-06-x, 634 pages 8. Introduction to Linear Optimization, by Dimitris Bertsimas and John N. Tsitsiklis, 1997, ISBN 1-886529-19-1, 608 pages 9. Parallel and Distributed Computation: Numerical Methods, by Dimitri P. Bertsekas and John N. Tsitsiklis. 1997. ISBN 1-886529 01-9,718 pages 10. Neuro-Dynamic Programming, by Dimitri P. Bertsekas and John N. Tsitsiklis, 1996, ISBN 1-886529-10-8, 512 pages 11. Constrained Optimization and Lagrange Multiplier Methods, b Dimitri P Bertsekas, 1996, ISBN 1-886529-04-3, 410 pages 12. Stochastic Optimal Control: The Discrete-Time Case, by dimitri P, Bertsekas and Steven E. Shreve, 1996. IsbN 1-886529-03-5 330 pages Preface This book aims at an accessible, concise, and intuitive exposition of two related subjects that find broad practical application a)Convex analysis, particularly as it relates to optimization (b) Duality theory for optimization and minimax problems, mainly within a convexity framework The focus on optimisation is to derive conditions for existence of primal and dual optimal solutions for constrained problems such as minimize f(a) subject to 2∈X,91(2) Other types of optimization problems, such as those arising in Fenchel duality, are also part of our scope. The focus on minimax is to derive conditions guaranteeing the equality inf sup o(a, x)=sup inf (a, z) c∈Xz∈z z∈zm∈X and the attainment of the“ inf and the“sup.” The treatment of convexity theory is fairly detailed. It touches upon nearly all major aspects of the subject and it is sufficient for the devel- opment of the core analytical issues of convex optimization. The mathe matical prerequisites are a first course in linear algebra and a first course in real analysis, A summary of the relevant material is provided in an appendix. Prior knowledge of linear and nonlinear optimization theory is not assumed, although it will undoubtedly be helpful in providing context and perspective. Other than this modest background, the development is self-contained, with rigorous proofs provided throughout We have aimed at a unified development of the strongest possible forms of duality with the most economic use of convexity theory. To this end, our analysis often departs from the lines of rockafellar's classic 1970 book and other books that followed the Fenchel/ Rockafellar formalism. For example, we treat differently closed set intersection theory and preserva tion of closure under linear transformations(Sections 1.4.2 and 1.4.3);we Vl1 Preface develop subdifferential calculus by using constrained optimization duality (Section 5. 4. 2); and we do not rely on concepts such as infimal convolu tion, image, polar sets and functions, bifunctions, and conjugate saddle functions. Perhaps our greatest departure is in duality theory itself: sim- ilar to Fenchel/Rockafellar, our development rests on Legendre/Fenchel conjugacy ideas, but is far more geometrical and visually intuitive Our duality framework is based on two simple geometrical problems the min common point problem and the ma crossing point problem. The salient feature of the min common/max crossing(MC/ MC) framework is its highly visual geometry, through which all the core issues of duality theory become apparent and can be analyzed in a unified way. Our approach is to obtain a handful of broadly applicable theorems within the Mc/MC frame work, and then specialize them to particular types of problems(constrained optimization, Fenchel duality, minimax problems, etc). We address all du- ality questions(existence of duality gap, existence of dual optimal solutions structure of the dual optimal solution set ), and other issues(subdifferential theory, theorems of the alternative, duality gap estimates) in this way Fundamentally, the MC/MC framework is closely connected to the conjugacy framework, and owes its power and generality to this connec tion. However, the two frameworks offer complementary starting points for analysis and provide alternative views of the geometric foundation of duality: conjugacy emphasizes functional/algebraic descriptions, while MC/MC emphasizes set/epigraph descriptions. The MC/MC framework is simpler, and seems better suited for visualizing and investigating questions of strong duality and existence of dual optimal solutions. The conjugacy franework, with its emphasis on functional descriptions, is more suitable when mathematical operations on convex functions are involved, and the calculus of conjugate functions can be brought to bear for analysis or com putation The book evolved from the earlier book of the author BNO03Onl the subject,(coauthored with A Nedic and A Ozdaglar), but has different character and objectives. The 2003 book was quite extensive was struc tured (at least in part)as a research monograph, and ained to bridge the gap between convex and nonconvex optimization using concepts of non smooth analysis. By contrast the present book is organized differently has the character of a textbook, and concentrates exclusively on convex optimization. Despite the differences, the two books have similar style and level of mathematical sophistication, and share some material The chapter-by-chapter description of the book follows Chapter 1: This chapter develops all of the convex analysis tools that are needed for the development of duality theory in subsequent chapters It covers basic algebraic concepts such as convex hulls and hyperplanes and topological concepts such as relative interior, closure, preservation of closedness ridler linea r traristorinations, and hyperplane scparation. In Preface addition, it develops subjects of special interest in duality and optimization such as recession cones and conjugate functions Chapter 2: This chapter covers polyhedral convexity concepts: cxtrcmc points, the Farkas and Minkowski-Weyl theorems, and sonc of thcir ap- plications in lincar programming It is not needed for the developments of subsequent chapters, and may be skipped at first reading Chapter 3: This chapter focuses on basic optimization concepts: types of minima, existence of solutions, and a few topics of special interest for duality theory, such as partial minimization and minimax theory Chapter 4: This chapter introduces the MC/MC duality framework. It discusses its connection with conjugacy theory, and it charts its applica- tions to constrained optimization and minimax problems. It then develops broadly applicable theorems relating to strong duality and existence of dual optimal solutions Chapter 5: This chapter specializes the duality theorems of Chapter 4 to important contexts relating to linear programming, convex programming, and minimax thcory. It also uses these thcorems as an aid for the devel- opment of additional convex analysis tools, such as a powerful nonlinear version of Farkas' Lerma, subdifferential theory, and theorems of the al ternative. a final section is devoted to nonconvex problcms and estimates of the duality gap, with spccial focus on scparable problems In aiming for brevity. I have omitted a number of topics that an instructor may wish for. One such omission is applications to specially structured problems; the book by Boyd and Vanderbergue [Bovo4], as well as my book on parallel and distributed computation with John Tsitsiklis BeT89 cover this material extensively(both books are available on line) Another important omission is computational methods. However, I have written a long supplementary sixth chapter (over 100 pages), which covers the most popular convex optimization algorithms(and some new ones), and can be downloaded from the book's web page http://www.athenasc.com/convexduality.html This chapter, together with a more comprehensive treatment of convex analysis, optimization, duality, and algorithms will be part of a more ex tensive textbook that i am currently writing. Until that time, the chapter will serve instructors who wish to cover convex optimization algorithms in addition to duality (as i do in my M I.T. course). This is a"living "chapter that will be periodically updated. Its current contents are as follows: Chapter 6 on Algorithms: 6.1. Problem Structures and Computational Approaches; 6.2. Algorithmic Descent; 6.3. Subgradient Methods; 6.4. Poly hedral approximation methods; 6.5. Proximal and bundle methods; 6.6 Dual Proximal point algorithms; 6.7. Interior Point Methods; 6.8. Approx- 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论