Über die Autorin bzw. den Autor

Aharon Ben-Tal, Laurent El Ghaoui & Arkadi Nemirovski

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Robust Optimization

Princeton University Press

Contents

Preface.............................................................................................ixPART I. ROBUST LINEAR OPTIMIZATION..................................................................1Chapter 1. Uncertain Linear Optimization Problems and their Robust Counterparts.....................3Chapter 2. Robust Counterpart Approximations of Scalar Chance Constraints...........................27Chapter 3. Globalized Robust Counterparts of Uncertain LO Problems..................................67Chapter 4. More on Safe Tractable Approximations of Scalar Chance Constraints.......................81PART II. ROBUST CONIC OPTIMIZATION..................................................................147Chapter 5. Uncertain Conic Optimization: The Concepts...............................................149Chapter 6. Uncertain Conic Quadratic Problems with Tractable RCs....................................159Chapter 7. Approximating RCs of Uncertain Conic Quadratic Problems..................................179Chapter 8. Uncertain Semidefinite Problems with Tractable RCs.......................................203Chapter 9. Approximating RCs of Uncertain Semidefinite Problems.....................................225Chapter 10. Approximating Chance Constrained CQIs and LMIs..........................................235Chapter 11. Globalized Robust Counterparts of Uncertain Conic Problems..............................279Chapter 12. Robust Classification and Estimation....................................................301PART III. ROBUST MULTI-STAGE OPTIMIZATION...........................................................339Chapter 13. Robust Markov Decision Processes........................................................341Chapter 14. Robust Adjustable Multistage Optimization...............................................355PART IV. SELECTED APPLICATIONS......................................................................415Chapter 15. Selected Applications...................................................................417Appendix A. Notation and Prerequisites..............................................................447Appendix B. Some Auxiliary Proofs...................................................................469Appendix C. Solutions to Selected Exercises.........................................................511Bibliography........................................................................................531Index...............................................................................................539

Chapter One

In this chapter, we introduce the concept of the uncertain Linear Optimization problem and its Robust Counterpart, and study the computational issues associated with the emerging optimization problems.

1.1 DATA UNCERTAINTY IN LINEAR OPTIMIZATION

Recall that the Linear Optimization (LO) problem is of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.1.1)

where x [member of] [R.sup.n] is the vector of decision variables, c [member of] [R.sup.n] and d [member of] R form the objective, A is an m x n constraint matrix, and b [member of] [R.sup.m] is the right hand side vector.

Clearly, the constant term d in the objective, while affecting the optimal value, does not affect the optimal solution, this is why it is traditionally skipped. As we shall see, when treating the LO problems with uncertain data there are good reasons not to neglect this constant term.

The structure of problem (1.1.1) is given by the number m of constraints and the number n of variables, while the data of the problem are the collection (c, d, A, b), which we will arrange into an (m + 1) x (n + 1) data matrix

D = [c.sup.T]/A | d/b].

Usually not all constraints of an LO program, as it arises in applications, are of the form [a.sup.T] x [less than or equal to] const; there can be linear "[greater than or equal to]" inequalities and linear equalities as well. Clearly, the constraints of the latter two types can be represented equivalently by linear "[less than or equal to]" inequalities, and we will assume henceforth that these are the only constraints in the problem.

Typically, the data of real world LOs (Linear Optimization problems) is not known exactly. The most common reasons for data uncertainty are as follows:

Some of data entries (future demands, returns, etc.) do not exist when the problem is solved and hence are replaced with their forecasts. These data entries are thus subject to prediction errors;

Some of the data (parameters of technological devices/processes, contents associated with raw materials, etc.) cannot be measured exactly - in reality their values drift around the measured "nominal" values; these data are subject to measurement errors;

Some of the decision variables (intensities with which we intend to use various technological processes, parameters of physical devices we are designing, etc.) cannot be implemented exactly as computed. The resulting implementation errors are equivalent to appropriate artificial data uncertainties.

Indeed, the contribution of a particular decision variable [x.sub.j] to the left hand side of constraint i is the product [a.sub.ij][x.sub.j]. Hence the consequences of an additive implementation error [x.sub.j] -> [x.sub.j] + [member of] are as if there were no implementation error at all, but the left hand side of the constraint got an extra additive term [a.sub.ij] [member of], which, in turn, is equivalent to the perturbation [b.sub.i] -> [b.sub.j] - [a.sub.ij] [member of] in the right hand side of the constraint. The consequences of a more typical multiplicative implementation error [x.sub.j] -> (1 + [member of]) [x.sub.j] are as if there were no implementation error, but each of the data coefficients [a.sub.ij] was subject to perturbation [a.sub.ij] -> (1 + [member of]) [a.sub.ij]. Similarly, the influence of additive and multiplicative implementation error in [x.sub.j] on the value of the objective can be mimicked by appropriate perturbations in d or [c.sub.j].

In the traditional LO methodology, a small data uncertainty (say, 1% or less) is just ignored; the problem is solved as if the given ("nominal") data were exact, and the resulting nominal optimal solution is what is recommended for use, in hope that small data uncertainties will not affect significantly the feasibility and optimality properties of this solution, or that small adjustments of the nominal solution will be sufficient to make it feasible. We are about to demonstrate that these hopes are not necessarily justified, and sometimes even small data uncertainty deserves significant attention.

1.1.1 Introductory Example

Consider the following very simple linear optimization problem:

Example 1.1.1. A company produces two kinds of drugs, DrugI and DrugII, containing a specific...