Robust Optimization

Preface ix

PART I. ROBUST LINEAR OPTIMIZATION 1

Chapter 1. Uncertain Linear Optimization Problems and their Robust Counterparts 3

1.1 Data Uncertainty in Linear Optimization 3

1.2 Uncertain Linear Problems and their Robust Counterparts 7

1.3 Tractability of Robust Counterparts 16

1.4 Non-Affne Perturbations 23

1.5 Exercises 25

1.6 Notes and Remarks 25

Chapter 2. Robust Counterpart Approximations of Scalar Chance Constraints 27

2.1 How to Specify an Uncertainty Set 27

2.2 Chance Constraints and their Safe Tractable Approximations 28

2.3 Safe Tractable Approximations of Scalar Chance Constraints: Basic Examples 31

2.4 Extensions 44

2.5 Exercises 60

2.6 Notes and Remarks 64

Chapter 3. Globalized Robust Counterparts of Uncertain LO Problems 67

3.1 Globalized Robust Counterpart Motivation and Definition 67

3.2 Computational Tractability of GRC 69

3.3 Example: Synthesis of Antenna Arrays 70

3.4 Exercises 79

3.5 Notes and Remarks 79

Chapter 4. More on Safe Tractable Approximations of Scalar Chance Constraints 81

4.1 Robust Counterpart Representation of a Safe Convex Approximation to a Scalar Chance Constraint 81

4.2 Bernstein Approximation of a Chance Constraint 83

4.3 From Bernstein Approximation to Conditional Value at Risk and Back 90

4.4 Majorization 105

4.5 Beyond the Case of Independent Linear Perturbations 109

4.6 Exercises 136

4.7 Notes and Remarks 145

PART II. ROBUST CONIC OPTIMIZATION 147

Chapter 5. Uncertain Conic Optimization: The Concepts 149

5.1 Uncertain Conic Optimization: Preliminaries 149

5.2 Robust Counterpart of Uncertain Conic Problem: Tractability 151

5.3 Safe Tractable Approximations of RCs of Uncertain Conic Inequalities 153

5.4 Exercises 156

5.5 Notes and Remarks 157

Chapter 6. Uncertain Conic Quadratic Problems with Tractable RCs 159

6.1 A Generic Solvable Case: Scenario Uncertainty 159

6.2 Solvable Case I: Simple Interval Uncertainty 160

6.3 Solvable Case II: Unstructured Norm-Bounded Uncertainty 161

6.4 Solvable Case III: Convex Quadratic Inequality with Un-structured Norm-Bounded Uncertainty 165

6.5 Solvable Case IV: CQI with Simple Ellipsoidal Uncertainty 167

6.6 Illustration: Robust Linear Estimation 173

6.7 Exercises 178

6.8 Notes and Remarks 178

Chapter 7. Approximating RCs of Uncertain Conic Quadratic Problems 179

7.1 Structured Norm-Bounded Uncertainty 179

7.2 The Case of \-Ellipsoidal Uncertainty 195

7.3 Exercises 201

7.4 Notes and Remarks 201

Chapter 8. Uncertain Semidefinite Problems with Tractable RCs 203

8.1 Uncertain Semidefinite Problems 203

8.2 Tractability of RCs of Uncertain Semidefinite Problems 204

8.3 Exercises 222

8.4 Notes and Remarks 222

Chapter 9. Approximating RCs of Uncertain Semide¯nite

Problems 225

9.1 Tight Tractable Approximations of RCs of Uncertain SDPs

with Structured Norm-Bounded Uncertainty 225

9.2 Exercises 232

9.3 Notes and Remarks 234

Chapter 10. Approximating Chance Constrained CQIs and LMIs 235

10.1 Chance Constrained LMIs 235

10.2 The Approximation Scheme 240

10.3 Gaussian Majorization 252

10.4 Chance Constrained LMIs: Special Cases 255

10.5 Notes and Remarks 276

Chapter 11. Globalized Robust Counterparts of Uncertain Conic Problems 279

11.1 Globalized Robust Counterparts of Uncertain Conic Problems: De¯nition 279

11.2 Safe Tractable Approximations of GRCs 281

11.3 GRC of Uncertain Constraint: Decomposition 282

11.4 Tractability of GRCs 284

11.5 Illustration: Robust Analysis of Nonexpansive Dynamical Systems 292

Chapter 12. Robust Classification and Estimation 301

12.1 Robust Support Vector Machines 301

12.2 Robust Classification and Regression 309

12.3 Affine Uncertainty Models 325

12.4 Random Affine Uncertainty Models 331

12.5 Exercises 336

12.6 Notes and remarks 337

PART III. ROBUST MULTI-STAGE OPTIMIZATION 339

Chapter 13. Robust Markov Decision Processes 341

13.1 Markov Decision Processes 341

13.2 The Robust MDP Problems 345

13.3 The Robust Bellman Recursion on Finite Horizon 347

13.4 Notes and Remarks 352

Chapter 14. Robust Adjustable Multistage Optimization 355

14.1 Adjustable Robust Optimization: Motivation 355

14.2 Adjustable Robust Counterpart 357

14.3 Affinely Adjustable Robust Counterparts 368

14.4 Adjustable Robust Optimization and Synthesis of Linear Controllers 392

14.5 Exercises 408

14.6 Notes and Remarks 411

PART IV. SELECTED APPLICATIONS 415

Chapter 15. Selected Applications 417

15.1 Robust Linear Regression and Manufacturing of TV Tubes 417

15.2 Inventory Management with Flexible Commitment Contracts 421

15.3 Controlling a Multi-Echelon Multi-Period Supply Chain 432

Appendix A. Notation and Prerequisites 447

A.1 Notation 447

A.2 Conic Programming 448

A.3 Efficient Solvability of Convex Programming 460

Appendix B. Some Auxiliary Proofs 469

B.1 Proofs for Chapter 4 469

B.2 S-Lemma 481

B.3 Approximate S-Lemma 483

B.4 Matrix Cube Theorem 489

B.5 Proofs for Chapter 10 506

Appendix C. Solutions to Selected Exercises 511

C.1 Chapter 1 511

C.2 Chapter 2 511

C.3 Chapter 3 513

C.4 Chapter 4 513

C.5 Chapter 5 516

C.6 Chapter 6 519

C.7 Chapter 7 520

C.8 Chapter 8 521

C.9 Chapter 9 523

C.10 Chapter 12 525

C.11 Chapter 14 527

Bibliography 531

Index 539