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.

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 .. 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.

3 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 .. 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.

4 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.

5 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.

6 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 .. 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.

7 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.

8 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.

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

10 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. Bertsekas, 1996, ISBN 1-886529-04-3, 410 pages 12. Stochastic Optimal Control: The Discrete-Time Case, by Dimitri P. Bertsekas and Steven E.