robust optimization.pdf-资料库

17bec406-dd68-4ef0-bb83-0a519a3f2081.pdf-第1页.png

第1页 / 共565页

17bec406-dd68-4ef0-bb83-0a519a3f2081.pdf-第2页.png

第2页 / 共565页

17bec406-dd68-4ef0-bb83-0a519a3f2081.pdf-第3页.png

第3页 / 共565页

17bec406-dd68-4ef0-bb83-0a519a3f2081.pdf-第4页.png

第4页 / 共565页

17bec406-dd68-4ef0-bb83-0a519a3f2081.pdf-第5页.png

第5页 / 共565页

17bec406-dd68-4ef0-bb83-0a519a3f2081.pdf-第6页.png

第6页 / 共565页

17bec406-dd68-4ef0-bb83-0a519a3f2081.pdf-第7页.png

第7页 / 共565页

17bec406-dd68-4ef0-bb83-0a519a3f2081.pdf-第8页.png

第8页 / 共565页

Robust Optimization

Princeton Series in Applied Mathematics Series Editors: Ingrid Daubechies (Princeton University); Weinan E (Princeton University); Jan Karel Lenstra (Eindhoven University); Endre Süli (University of Oxford) The Princeton Series in Applied Mathematics publishes high quality advanced texts and monographs in all areas of applied mathematics. Books include those of a theoretical and general nature as well as those dealing with the mathematics of specific applications areas and real-world situations. Chaotic Transitions in Deterministic and Stochastic Dynamical Systems: Applications of Melnikov Processes in Engineering, Physics, and Neuroscience, Emil Simiu Self-Regularity: A New Paradigm for Primal-Dual Interior Point Algorithms, Jiming Peng, Cornelis Roos, and Tamas Terlaky Selfsimilar Processes, Paul Embrechts and Makoto Maejima Analytic Theory of Global Bifurcation: An Introduction, Boris Buffoni and John Toland Entropy, Andreas Greven, Gerhard Keller, and Gerald Warnecke, editors Auxiliary Signal Design for Failure Detection, Stephen L. Campbell and Ramine Nikoukhah Max Plus at Work Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications, Bernd Heidergott, Geert Jan Olsder, and Jacob van der Woude Optimization: Insights and Applications, Jan Brinkhuis and Vladimir Tikhomirov Thermodynamics: A Dynamical Systems Approach, Wassim M. Haddad, VijaySekhar Chellaboina, and Sergey G. Nersesov Impulsive and Hybrid Dynamical Systems Stability, Dissipativity, and Control, Wassim M. Haddad, VijaySekhar Chellaboina, and Sergey G. Nersesov Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms, Francesco Bullo, Jorge Cortés, and Sonia Martínez Genomic Signal Processing, Ilya Shmulevich and Edward Dougherty Positive Definite Matrices, Rajendra Bhatia The Traveling Salesman Problem: A Computational Study, David L. Applegate, Robert E. Bixby, Vasek Chvatal, and William J. Cook Wave Scattering by Time-Dependent Perturbations: An Introduction, G. F. Roach Algebraic Curves over a Finite Field, J.W.P. Hirschfeld, G. Korchmáros, and F. Torres Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms, Francesco Bullo, Jorge Cortés, and Sonia Martínez Robust Optimization, Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski

Robust Optimization Aharon Ben-Tal Laurent El Ghaoui Arkadi Nemirovski Princeton University Press Princeton and Oxford

Copyright © 2009 by Princeton University Press Requests for permission to reproduce material from this work should be sent to Permissions, Princeton University Press Published by Princeton University Press, 41 William Street, Princeton, New Jersey 08540 In the United Kingdom: Princeton University Press, 6 Oxford Street, Woodstock, Oxfordshire OX20 1TW All Rights Reserved Library of Congress Cataloging-in-Publication Data Ben-Tal, A.. Robust optimization / Aharon Ben-Tal, Laurent El Ghaoui, Arkadi Nemirovski. p. cm. ISBN 978-0-691-14368-2 (hardcover : alk. paper) 1. Robust optimization. 2. Linear programming. I. El Ghaoui, Laurent. II. Nemirovskii, Arkadii Semenovich. III. Title. QA402.5.B445 2009 519.6--dc22 2009013229 The publishers would like to acknowledge the authors of this volume for providing the electronic files from which this book was printed Printed on acid-free paper. press.princeton.edu Printed in the United States of America 10 9 8 7 6 5 4 3 2 1

Contents Preface PART I. ROBUST LINEAR OPTIMIZATION Chapter 1. Uncertain Linear Optimization Problems and their Robust Counterparts 1.1 1.2 1.3 1.4 1.5 1.6 Data Uncertainty in Linear Optimization Uncertain Linear Problems and their Robust Counterparts Tractability of Robust Counterparts Non-Aﬃne Perturbations Exercises Notes and Remarks Chapter 2. Robust Counterpart Approximations of Scalar Chance Constraints 2.1 2.2 2.3 How to Specify an Uncertainty Set Chance Constraints and their Safe Tractable Approximations Safe Tractable Approximations of Scalar Chance Constraints: Basic Examples 2.4 2.5 2.6 Extensions Exercises Notes and Remarks Chapter 3. Globalized Robust Counterparts of Uncertain LO Prob- lems 3.1 3.2 3.3 3.4 3.5 Globalized Robust Counterpart — Motivation and Deﬁnition Computational Tractability of GRC Example: Synthesis of Antenna Arrays Exercises Notes and Remarks Chapter 4. More on Safe Tractable Approximations of Scalar Chance Constraints ix 1 3 3 7 16 23 25 25 27 27 28 31 44 60 64 67 67 69 70 79 79 81

vi 4.1 4.2 4.3 4.4 4.5 4.6 4.7 Robust Counterpart Representation of a Safe Convex Approximation to a Scalar Chance Constraint Bernstein Approximation of a Chance Constraint From Bernstein Approximation to Conditional Value at Risk and Back Majorization Beyond the Case of Independent Linear Perturbations Exercises Notes and Remarks PART II. ROBUST CONIC OPTIMIZATION Chapter 5. Uncertain Conic Optimization: The Concepts 5.1 5.2 5.3 5.4 5.5 Uncertain Conic Optimization: Preliminaries Robust Counterpart of Uncertain Conic Problem: Tractability Safe Tractable Approximations of RCs of Uncertain Conic Inequalities Exercises Notes and Remarks Chapter 6. Uncertain Conic Quadratic Problems with Tractable RCs 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 A Generic Solvable Case: Scenario Uncertainty Solvable Case I: Simple Interval Uncertainty Solvable Case II: Unstructured Norm-Bounded Uncertainty Solvable Case III: Convex Quadratic Inequality with Un- structured Norm-Bounded Uncertainty Solvable Case IV: CQI with Simple Ellipsoidal Uncertainty Illustration: Robust Linear Estimation Exercises Notes and Remarks Chapter 7. Approximating RCs of Uncertain Conic Quadratic Problems 7.1 7.2 7.3 7.4 Structured Norm-Bounded Uncertainty The Case of ∩-Ellipsoidal Uncertainty Exercises Notes and Remarks Chapter 8. Uncertain Semideﬁnite Problems with Tractable RCs 8.1 8.2 8.3 Uncertain Semideﬁnite Problems Tractability of RCs of Uncertain Semideﬁnite Problems Exercises CONTENTS 81 83 90 105 109 136 145 147 149 149 151 153 156 157 159 159 160 161 165 167 173 178 178 179 179 195 201 201 203 203 204 222

CONTENTS 8.4 Notes and Remarks Chapter 9. Approximating RCs of Uncertain Semideﬁnite Problems 9.1 Tight Tractable Approximations of RCs of Uncertain SDPs with Structured Norm-Bounded Uncertainty 9.2 9.3 Exercises Notes and Remarks Chapter 10. Approximating Chance Constrained CQIs and LMIs 10.1 10.2 10.3 10.4 10.5 Chance Constrained LMIs The Approximation Scheme Gaussian Majorization Chance Constrained LMIs: Special Cases Notes and Remarks Chapter 11. Globalized Robust Counterparts of Uncertain Conic Problems 11.1 Globalized Robust Counterparts of Uncertain Conic Problems: Deﬁnition 11.2 11.3 11.4 11.5 Safe Tractable Approximations of GRCs GRC of Uncertain Constraint: Decomposition Tractability of GRCs Illustration: Robust Analysis of Nonexpansive Dynamical Systems Chapter 12. Robust Classiﬁcation and Estimation 12.1 12.2 12.3 12.4 12.5 12.6 Robust Support Vector Machines Robust Classiﬁcation and Regression Aﬃne Uncertainty Models Random Aﬃne Uncertainty Models Exercises Notes and remarks PART III. ROBUST MULTI-STAGE OPTIMIZATION Chapter 13. Robust Markov Decision Processes 13.1 Markov Decision Processes 13.2 The Robust MDP Problems The Robust Bellman Recursion on Finite Horizon 13.3 13.4 Notes and Remarks Chapter 14. Robust Adjustable Multistage Optimization vii 222 225 225 232 234 235 235 240 252 255 276 279 279 281 282 284 292 301 301 309 325 331 336 337 339 341 341 345 347 352 355

资料库

robust optimization.pdf

相关推荐

课程资源

热门标签

最新资料