Robust Optimization

Preface ixPART I. ROBUST LINEAR OPTIMIZATION 1Chapter 1. Uncertain Linear Optimization Problems and their Robust Counterparts 31.1 Data Uncertainty in Linear Optimization 31.2 Uncertain Linear Problems and their Robust Counterparts 71.3 Tractability of Robust Counterparts 161.4 Non-Affne Perturbations 231.5 Exercises 251.6 Notes and Remarks 25Chapter 2. Robust Counterpart Approximations of Scalar Chance Constraints 272.1 How to Specify an Uncertainty Set 272.2 Chance Constraints and their Safe Tractable Approximations 282.3 Safe Tractable Approximations of Scalar Chance Constraints: Basic Examples 312.4 Extensions 442.5 Exercises 602.6 Notes and Remarks 64Chapter 3. Globalized Robust Counterparts of Uncertain LO Problems 673.1 Globalized Robust Counterpart | Motivation and Definition 673.2 Computational Tractability of GRC 693.3 Example: Synthesis of Antenna Arrays 703.4 Exercises 793.5 Notes and Remarks 79Chapter 4. More on Safe Tractable Approximations of Scalar Chance Constraints 814.1 Robust Counterpart Representation of a Safe Convex Approximation to a Scalar Chance Constraint 814.2 Bernstein Approximation of a Chance Constraint 834.3 From Bernstein Approximation to Conditional Value at Risk and Back 904.4 Majorization 1054.5 Beyond the Case of Independent Linear Perturbations 1094.6 Exercises 1364.7 Notes and Remarks 145PART II. ROBUST CONIC OPTIMIZATION 147Chapter 5. Uncertain Conic Optimization: The Concepts 1495.1 Uncertain Conic Optimization: Preliminaries 1495.2 Robust Counterpart of Uncertain Conic Problem: Tractability 1515.3 Safe Tractable Approximations of RCs of Uncertain Conic Inequalities 1535.4 Exercises 1565.5 Notes and Remarks 157Chapter 6. Uncertain Conic Quadratic Problems with Tractable RCs 1596.1 A Generic Solvable Case: Scenario Uncertainty 1596.2 Solvable Case I: Simple Interval Uncertainty 1606.3 Solvable Case II: Unstructured Norm-Bounded Uncertainty 1616.4 Solvable Case III: Convex Quadratic Inequality with Un-structured Norm-Bounded Uncertainty 1656.5 Solvable Case IV: CQI with Simple Ellipsoidal Uncertainty 1676.6 Illustration: Robust Linear Estimation 1736.7 Exercises 1786.8 Notes and Remarks 178Chapter 7. Approximating RCs of Uncertain Conic Quadratic Problems 1797.1 Structured Norm-Bounded Uncertainty 1797.2 The Case of -Ellipsoidal Uncertainty 1957.3 Exercises 2017.4 Notes and Remarks 201Chapter 8. Uncertain Semidefinite Problems with Tractable RCs 2038.1 Uncertain Semidefinite Problems 2038.2 Tractability of RCs of Uncertain Semidefinite Problems 2048.3 Exercises 2228.4 Notes and Remarks 222Chapter 9. Approximating RCs of Uncertain Semide-niteProblems 2259.1 Tight Tractable Approximations of RCs of Uncertain SDPswith Structured Norm-Bounded Uncertainty 2259.2 Exercises 2329.3 Notes and Remarks 234Chapter 10. Approximating Chance Constrained CQIs and LMIs 23510.1 Chance Constrained LMIs 23510.2 The Approximation Scheme 24010.3 Gaussian Majorization 25210.4 Chance Constrained LMIs: Special Cases 25510.5 Notes and Remarks 276Chapter 11. Globalized Robust Counterparts of Uncertain Conic Problems 27911.1 Globalized Robust Counterparts of Uncertain Conic Problems: De-nition 27911.2 Safe Tractable Approximations of GRCs 28111.3 GRC of Uncertain Constraint: Decomposition 28211.4 Tractability of GRCs 28411.5 Illustration: Robust Analysis of Nonexpansive Dynamical Systems 292Chapter 12. Robust Classification and Estimation 30112.1 Robust Support Vector Machines 30112.2 Robust Classification and Regression 30912.3 Affine Uncertainty Models 32512.4 Random Affine Uncertainty Models 33112.5 Exercises 33612.6 Notes and remarks 337PART III. ROBUST MULTI-STAGE OPTIMIZATION 339Chapter 13. Robust Markov Decision Processes 34113.1 Markov Decision Processes 34113.2 The Robust MDP Problems 34513.3 The Robust Bellman Recursion on Finite Horizon 34713.4 Notes and Remarks 352Chapter 14. Robust Adjustable Multistage Optimization 35514.1 Adjustable Robust Optimization: Motivation 35514.2 Adjustable Robust Counterpart 35714.3 Affinely Adjustable Robust Counterparts 36814.4 Adjustable Robust Optimization and Synthesis of Linear Controllers 39214.5 Exercises 40814.6 Notes and Remarks 411PART IV. SELECTED APPLICATIONS 415Chapter 15. Selected Applications 41715.1 Robust Linear Regression and Manufacturing of TV Tubes 41715.2 Inventory Management with Flexible Commitment Contracts 42115.3 Controlling a Multi-Echelon Multi-Period Supply Chain 432Appendix A. Notation and Prerequisites 447A.1 Notation 447A.2 Conic Programming 448A.3 Efficient Solvability of Convex Programming 460Appendix B. Some Auxiliary Proofs 469B.1 Proofs for Chapter 4 469B.2 S-Lemma 481B.3 Approximate S-Lemma 483B.4 Matrix Cube Theorem 489B.5 Proofs for Chapter 10 506Appendix C. Solutions to Selected Exercises 511C.1 Chapter 1 511C.2 Chapter 2 511C.3 Chapter 3 513C.4 Chapter 4 513C.5 Chapter 5 516C.6 Chapter 6 519C.7 Chapter 7 520C.8 Chapter 8 521C.9 Chapter 9 523C.10 Chapter 12 525C.11 Chapter 14 527Bibliography 531Index 539