Robust Optimization

by Ben-Tal, Aharon; Laurent, El Ghaoui; Nemirovski, Arkadi

• ISBN13: 9781400831050
• ISBN10: 1400831059
• Copyright: 2009-09-03
• Publisher: Princeton Univ Pr

Summary

Robust optimization is still a relatively new approach to optimization problems affected by uncertainty, but it has already proved so useful in real applications that it is difficult to tackle such problems today without considering this powerful methodology. Written by the principal developers of robust optimization, and describing the main achievements of a decade of research, this is the first book to provide a comprehensive and up-to-date account of the subject.Robust optimization is designed to meet some major challenges associated with uncertainty-affected optimization problems: to operate under lack of full information on the nature of uncertainty; to model the problem in a form that can be solved efficiently; and to provide guarantees about the performance of the solution.The book starts with a relatively simple treatment of uncertain linear programming, proceeding with a deep analysis of the interconnections between the construction of appropriate uncertainty sets and the classical chance constraints (probabilistic) approach. It then develops the robust optimization theory for uncertain conic quadratic and semidefinite optimization problems and dynamic (multistage) problems. The theory is supported by numerous examples and computational illustrations.An essential book for anyone working on optimization and decision making under uncertainty,Robust Optimizationalso makes an ideal graduate textbook on the subject.

Table of Contents

Preface	p. ix
Robust Linear Optimization	p. 1
Uncertain Linear Optimization Problems and their Robust Counterparts	p. 3
Data Uncertainty in Linear Optimization	p. 3
Uncertain Linear Problems and their Robust Counterparts	p. 7
Tractability of Robust Counterparts	p. 16
Non-Affne Perturbations	p. 23
Exercises	p. 25
Notes and Remarks	p. 25
Robust Counterpart Approximations of Scalar Chance Constraints	p. 27
How to Specify an Uncertainty Set	p. 27
Chance Constraints and their Safe Tractable Approximations	p. 28
Safe Tractable Approximations of Scalar Chance Constraints: Basic Examples	p. 31
Extensions	p. 44
Exercises	p. 60
Notes and Remarks	p. 64
Globalized Robust Counterparts of Uncertain LO Problems	p. 67
Globalized Robust Counterpart Motivation and Definition	p. 67
Computational Tractability of GRC	p. 69
Example: Synthesis of Antenna Arrays	p. 70
Exercises	p. 79
Notes and Remarks	p. 79
More on Safe Tractable Approximations of Scalar Chance Constraints	p. 81
Robust Counterpart Representation of a Safe Convex Approximation to a Scalar Chance Constraint	p. 81
Bernstein Approximation of a Chance Constraint	p. 83
From Bernstein Approximation to Conditional Value at Risk and Back	p. 90
Majorization	p. 105
Beyond the Case of Independent Linear Perturbations	p. 109
Exercises	p. 136
Notes and Remarks	p. 145
Robust Conic Optimization	p. 147
Uncertain Conic Optimization: The Concepts	p. 149
Uncertain Conic Optimization: Preliminaries	p. 149
Robust Counterpart of Uncertain Conic Problem: Tractability	p. 151
Safe Tractable Approximations of RCs of Uncertain Conic Inequalities	p. 153
Exercises	p. 156
Notes and Remarks	p. 157
Uncertain Conic Quadratic Problems with Tractable RCs	p. 159
A Generic Solvable Case: Scenario Uncertainty	p. 159
Solvable Case I: Simple Interval Uncertainty	p. 160
Solvable Case II: Unstructured Norm-Bounded Uncertainty	p. 161
Solvable Case III: Convex Quadratic Inequality with Un-structured Norm-Bounded Uncertainty	p. 165
Solvable Case IV: CQI with Simple Ellipsoidal Uncertainty	p. 167
Illustration: Robust Linear Estimation	p. 173
Exercises	p. 178
Notes and Remarks	p. 178
Approximating RCs of Uncertain Conic Quadratic Problems	p. 179
Structured Norm-Bounded Uncertainty	p. 179
The Case of \-Ellipsoidal Uncertainty	p. 195
Exercises	p. 201
Notes and Remarks	p. 201
Uncertain Semidefinite Problems with Tractable RCs	p. 203
Uncertain Semidefinite Problems	p. 203
Tractability of RCs of Uncertain Semidefinite Problems	p. 204
Exercises	p. 222
Notes and Remarks	p. 222
Approximating RCs of Uncertain Semide�nite Problems	p. 225
Tight Tractable Approximations of RCs of Uncertain SDPs with Structured Norm-Bounded Uncertainty	p. 225
Exercises	p. 232
Notes and Remarks	p. 234
Approximating Chance Constrained CQIs and LMIs	p. 235
Chance Constrained LMIs	p. 235
The Approximation Scheme	p. 240
Gaussian Majorization	p. 252
Chance Constrained LMIs: Special Cases	p. 255
Notes and Remarks	p. 276
Globalized Robust Counterparts of Uncertain Conic Problems	p. 279
Globalized Robust Counterparts of Uncertain Conic Problems: De�nition	p. 279
Safe Tractable Approximations of GRCs	p. 281
GRC of Uncertain Constraint: Decomposition	p. 282
Tractability of GRCs	p. 284
Illustration: Robust Analysis of Nonexpansive Dynamical Systems	p. 292
Robust Classification and Estimation	p. 301
Robust Support Vector Machines	p. 301
Robust Classification and Regression	p. 309
Affine Uncertainty Models	p. 325
Random Affine Uncertainty Models	p. 331
Exercises	p. 336
Notes and remarks	p. 337
Robust Multi-Stage Optimization	p. 339
Robust Markov Decision Processes	p. 341
Markov Decision Processes	p. 341
The Robust MDP Problems	p. 345
The Robust Bellman Recursion on Finite Horizon	p. 347
Notes and Remarks	p. 352
Robust Adjustable Multistage Optimization	p. 355
Adjustable Robust Optimization: Motivation	p. 355
Adjustable Robust Counterpart	p. 357
Affinely Adjustable Robust Counterparts	p. 368
Adjustable Robust Optimization and Synthesis of Linear Controllers	p. 392
Exercises	p. 408
Notes and Remarks	p. 411
Selected Applications	p. 415
Selected Applications	p. 417
Robust Linear Regression and Manufacturing of TV Tubes	p. 417
Inventory Management with Flexible Commitment Contracts	p. 421
Controlling a Multi-Echelon Multi-Period Supply Chain	p. 432
Notation and Prerequisites	p. 447
Notation	p. 447
Conic Programming	p. 448
Efficient Solvability of Convex Programming	p. 460
Some Auxiliary Proofs	p. 469
Proofs for Chapter 4	p. 469
S-Lemma	p. 481
Approximate S-Lemma	p. 483
Matrix Cube Theorem	p. 489
Proofs for Chapter 10	p. 506
Solutions to Selected Exercises	p. 511
Chapter 1	p. 511
Chapter 2	p. 511
Chapter 3	p. 513
Chapter 4	p. 513
Chapter 5	p. 516
Chapter 6	p. 519
Chapter 7	p. 520
Chapter 8	p. 521
Chapter 9	p. 523
Chapter 12	p. 525
Chapter 14	p. 527
Table of Contents provided by Publisher. All Rights Reserved.