Convex Theory Preface - MIT

1 Convex Optimization Theory Dimitri P. Bertsekas Massachusetts Institute of Technology WWW site for book information and orders Athena Scientific, Belmont, Massachusetts Athena Scientific Post O ce Box 805. Nashua, NH 03061-0805. Email: WWW: 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 Bertsekas, Dimitri P. Convex Optimization Theory Includes bibliographical references and index 1. Nonlinear Programming 2. Mathematical Optimization. I. Title. 2009 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 .. p. 1. Convex Sets and Functions.

2 P. 2. Convex Functions .. p. 5. Closedness and Semicontinuity .. p. 9. Operations with Convex Functions .. p. 11. Characterizations of Di erentiable Convex Functions .. p. 13. Convex and A ne Hulls .. p. 19. Relative Interior and Closure .. p. 23. Calculus of Relative Interiors and Closures .. p. 28. Continuity of Convex Functions .. p. 35. Closures of Functions .. p. 37. Recession Cones .. p. 43. Directions of Recession of a Convex Function .. p. 50. Nonemptiness of Intersections of Closed Sets .. p. 57. Closedness Under Linear Transformations .. p. 64. Hyperplanes .. p. 67. Hyperplane Separation .. p. 68. Proper Hyperplane Separation .. p. 73. Nonvertical Hyperplane Separation .. p. 80. Conjugate Functions .. p. 82. Summary .. p. 89. 2. Basic Concepts of Polyhedral Convexity .. p. 91. Extreme Points .. p. 92. Polar Cones .. p. 99. Polyhedral Sets and Functions.

3 P. 102. Polyhedral Cones and Farkas' Lemma .. p. 102. Structure of Polyhedral Sets .. p. 104. Polyhedral Functions .. p. 109. Polyhedral Aspects of Optimization .. p. 111. 3. Basic Concepts of Convex Optimization .. p. 115. Constrained Optimization .. p. 116. Existence of Optimal Solutions .. p. 118. iii iv Contents Partial Minimization of Convex Functions .. p. 122. Saddle Point and Minimax Theory .. p. 127. 4. Geometric Duality Framework .. p. 131. Min Common/Max Crossing Duality .. p. 132. Some Special Cases .. p. 137. Connection to Conjugate Convex Functions .. p. 137. General Optimization Duality .. p. 138. Optimization with Inequality Constraints .. p. 139. Augmented Lagrangian Duality .. p. 140. Minimax Problems .. p. 141. Strong Duality Theorem .. p. 146. Existence of Dual Optimal Solutions .. p. 149. Duality and Polyhedral Convexity .. p. 153. Summary.

4 P. 158. 5. Duality and Optimization .. p. 157. Nonlinear Farkas' Lemma .. p. 160. Linear Programming Duality .. p. 164. Convex Programming Duality .. p. 167. Strong Duality Theorem Inequality Constraints .. p. 168. Optimality Conditions .. p. 169. Partially Polyhedral Constraints .. p. 171. Duality and Existence of Optimal Primal Solutions .. p. 176. Fenchel Duality .. p. 179. Conic Duality .. p. 181. Subgradients and Optimality Conditions .. p. 182. Subgradients of Conjugate Functions .. p. 187. Subdi erential Calculus .. p. 192. Optimality Conditions .. p. 195. Directional Derivatives .. p. 196. Minimax Theory .. p. 200. Minimax Duality Theorems .. p. 200. Saddle Point Theorems .. p. 204. Theorems of the Alternative .. p. 209. Nonconvex Problems .. p. 216. Duality Gap in Separable Problems .. p. 217. Duality Gap in Minimax Problems .. p. 226. Appendix A: Mathematical Background.

5 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 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 Illinois, Urbana. Since 1979 he has been teaching at the Electrical Engineering and Computer Science Department of the Mas- sachusetts Institute of Technology ( ), where he is currently McAfee Professor of Engineering. His teaching and research spans several fields, including deterministic optimization, dynamic 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.

6 He often consults with private industry and has held editorial positions in several journals. Professor Bertsekas was awarded the INFORMS 1997 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. v ATHENA SCIENTIFIC. OPTIMIZATION AND COMPUTATION SERIES. 1. Convex Optimization Theory , by Dimitri P. Bertsekas, 2009, ISBN 978-1-886529-31-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.

7 Convex Analysis and Optimization, by Dimitri P. Bertsekas, with Angelia Nedic and Asuman E. Ozdaglar, 2003, ISBN 1-886529- 45-0, 560 pages 5. Nonlinear Programming, 2nd Edition, by Dimitri P. Bertsekas, 1999, ISBN 1-886529-00-0, 791 pages 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, by Dimitri P.

8 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 vi 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 optimization is to derive conditions for existence of primal and dual optimal solutions for constrained problems such as minimize f (x). subject to x X, gj (x) 0, j = 1, .. , r. 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 (x, z) = sup inf (x, z), x X z Z z Z x X.

9 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 su cient 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.

10 Book and other books that followed the Fenchel/Rockafellar formalism. For example, we treat di erently closed set intersection Theory and preserva- tion of closure under linear transformations (Sections and ); we develop subdi erential calculus by using constrained optimization duality (Section ); 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. vii viii Preface Our duality framework is based on two simple geometrical problems: the min common point problem and the max 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.