Robust Optimization

By Aharon Ben-Tal Laurent El Ghaoui Arkadi Nemirovski

Princeton University Press

Copyright © 2009 Princeton University Press
All right reserved.
ISBN: 9780-691-14368-2

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

Uncertain Linear Optimization Problems and their Robust Counterparts

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 active agent A, which is extracted from raw materials purchased on the market. There are two kinds of raw materials, RawI and RawII, which can be used as sources of the active agent. The related production, cost, and resource data are given in table 1.1. The goal is to find the production plan that maximizes the profit of the company.

The problem can be immediately posed as the following linear programming program:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The problem has four variables – the amounts RawI, RawII (in kg) of raw materials to be purchased and the amounts DrugI, DrugII (in 1000 of packs) of drugs to be produced.

The optimal solution of our LO problem is

Opt = -8819.658; RawI = 0, RawII = 438.789, DrugI = 17.552, DrugII = 0.

Note that both the budget and the balance constraints are active (that is, the production process utilizes the entire 100,000 budget and the full amount of active agent contained in the raw materials). The solution promises the company a modest, but quite respectable profit of 8.8%.

1.1.2 Data Uncertainty and its Consequences

Clearly, even in our simple problem some of the data cannot be “absolutely reliable”; e.g., one can hardly believe that the contents of the active agent in the raw materials are exactly 0.01 g/kg for RawI and 0.02 g/kg for RawII. In reality, these contents vary around the indicated values. A natural assumption here is that the actual contents of active agent aI in RawI and aII in RawII are realizations of random variables somehow distributed around the “nominal contents” anI = 0.01 and anII = 0.02. To be more specific, assume that aI drifts in a 0.5% margin of anI, thus taking values in the segment [0.00995, 0.01005]. Similarly, assume that aII drifts in a 2% margin of anII, thus taking values in the segment [0.0196, 0.0204]. Moreover, assume that aI, aII take the two extreme values in the respective segments with probabilities 0.5 each. How do these perturbations of the contents of the active agent affect the production process? The optimal solution prescribes to purchase 438.8 kg of RawII and to produce 17.552K packs of DrugI (K stands for “thousand”). With the above random fluctuations in the content of the active agent in RawII, this production plan will be infeasible with probability 0.5, i.e., the actual content of the active agent in raw materials will be less than the one required to produce the planned amount of DrugI. This difficulty can be resolved in the simplest way: when the actual content of the active agent in raw materials is insufficient, the output of the drug is reduced accordingly. With this policy, the actual production of DrugI becomes a random variable that takes with equal probabilities the nominal value of 17.552K packs and the (2% less) value of 17.201K packs. These 2% fluctuations in the production affect the profit as well; it becomes a random variable taking, with probabilities 0.5, the nominal value 8,820 and the 21% (!) less value 6,929. The expected profit is 7,843, which is 11% less than the nominal profit 8,820 promised by the optimal solution of the nominal problem.

We see that in our simple example a pretty small (and unavoidable in reality) perturbation of the data may make the nominal optimal solution infeasible. Moreover, a straightforward adjustment of the nominally optimal solution to the actual data may heavily affect the quality of the solution.

Similar phenomenon can be met in many practical linear programs where at least part of the data are not known exactly and can vary around their nominal values. The consequences of data uncertainty can be much more severe than in our toy example. The analysis of linear optimization problems from the NETLIB collection reported in [7] reveals that for 13 of 94 NETLIB problems, random 0.01% perturbations of the uncertain data can make the nominal optimal solution severely infeasible: with a non-negligible probability, it violates some of the constraints by 50% and more. It should be added that in the general case (in contrast to our toy example) there is no evident way to adjust the optimal solution to the actual values of the data by a small modification, and there are cases when such an adjustment is in fact impossible; in order to become feasible for the perturbed data, the nominal optimal solution should be “completely reshaped.”

The conclusion is as follows:

In applications of LO, there exists a real need of a technique capable of detecting cases when data uncertainty can heavily affect the quality of the nominal solution, and in these cases to generate a “reliable” solution, one that is immunized against uncertainty.

We are about to introduce the Robust Counterpart approach to uncertain LO problems aimed at coping with data uncertainty.

1.2 UNCERTAIN LINEAR PROBLEMS AND THEIR ROBUST COUNTERPARTS

Definition 1.2.1. An uncertain Linear Optimization problem is a collection

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ([LOU.sub.u])

of LO problems (instances) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of common structure (i.e., with common numbers m of constraints and n of variables) with the data varying in a given uncertainty set U [subset] [R.sup.(m+1)x(n+1)].

We always assume that the uncertainty set is parameterized, in an affine fashion, by perturbation vector [zeta] varying in a given perturbation set Z:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2.1)

For example, the story told in section 1.1.2 makes (Drug) an uncertain LO problem as follows:

Decision vector: x = [RawI; RawII; DrugI; DrugII];

Nominal data: [D.sub.0] = [ILLUSTRATION OMITTED]

Two basic shifts:

[ILLUSTRATION OMITTED]

Perturbation set:

Z = {[zeta] [member of] [R.sup.2]: -1 [less than or equal to] [[zeta].sub.1], [[zeta].sub.2] [less than or equal to] 1}.

This description says, in particular, that the only uncertain data in (Drug) are the coefficients anI, anII of the variables RawI, RawII in the balance inequality, (which is the first constraint in (Drug)), and that these coefficients vary in the respective segments [0.01 * (1-0.005), 0.01 * (1+0.005)], [0.02 * (1-0.02), 0.02(1+0.02)] around the nominal values 0.01, 0.02 of the coefficients, which is exactly what was stated in section 1.1.2.

Remark 1.2.2. If the perturbation set Z in (1.2.1) itself is represented as the image of another set [??] under affine mapping [xi] -> [zeta] = p + P]xi], then we can pass from perturbations [zeta] to perturbations [xi]:

[ILLUSTRATION OMITTED]

It follows that when speaking about perturbation sets with simple geometry (parallelotopes, ellipsoids, etc.), we can normalize these sets to be “standard.” For example, a parallelotope is by definition an affine image of a unit box {[xi] [member of] [R.sup.k]: -1 [less than or equal to] [[xi].sub.j] [less than or equal to] 1, j = 1, …, k}, which gives us the possibility to work with the unit box instead of a general parallelotope. Similarly, an ellipsoid is by definition the image of a unit Euclidean ball [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] under affine mapping, so that we can work with the standard ball instead of the ellipsoid, etc. We will use this normalization whenever possible.

Note that a family of optimization problems like ([LO.sub.U), in contrast to a single optimization problem, is not associated by itself with the concepts of feasible/optimal solution and optimal value. How to define these concepts depends of course on the underlying “decision environment.” Here we focus on an environment with the following characteristics:

A.1. All decision variables in ([LO.sub.U) represent “here and now” decisions; they should be assigned specific numerical values as a result of solving the problem before the actual data “reveals itself.”

A.2. The decision maker is fully responsible for consequences of the decisions to be made when, and only when, the actual data is within the prespecified uncertainty set U given by (1.2.1).

A.3. The constraints in ([LO.sub.U) are “hard” – we cannot tolerate violations of constraints, even small ones, when the data is in U.

The above assumptions determine, in a more or less unique fashion, what are the meaningful feasible solutions to the uncertain problem ([LO.sub.U). By A.1, these should be fixed vectors; by A.2 and A.3, they should be robust feasible, that is, they should satisfy all the constraints, whatever the realization of the data from the uncertainty set. We have arrived at the following definition.

Definition 1.2.3. A vector x [member of] [R.sup.n] is a robust feasible solution to ([LO.sub.U), if it satisfies all realizations of the constraints from the uncertainty set, that is,

Ax [less than or equal to] b [for all](c, d, A, b) [member of] U. (1.2.2)

As for the objective value to be associated with a meaningful (i.e., robust feasible) solution, assumptions A.1 – A.3 do not prescribe it in a unique fashion. However, “the spirit” of these worst-case-oriented assumptions leads naturally to the following definition:

Definition 1.2.4. Given a candidate solution x, the robust value [??](x) of the objective in ([LO.sub.U) at x is the largest value of the “true” objective [c.sup.T] x + d over all realizations of the data from the uncertainty set:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1.2.3)

After we agree what are meaningful candidate solutions to the uncertain problem ([LO.sub.U) and how to quantify their quality, we can seek the best robust value of the objective among all robust feasible solutions to the problem. This brings us to the central concept of this book, Robust Counterpart of an uncertain optimization problem, which is defined as follows:

Definition 1.2.5. The Robust Counterpart of the uncertain LO problem ([LO.sub.U) is the optimization problem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1.2.4)

of minimizing the robust value of the objective over all robust feasible solutions to the uncertain problem.

An optimal solution to the Robust Counterpart is called a robust optimal solution to ([LO.sub.U), and the optimal value of the Robust Counterpart is called the robust optimal value of ([LO.sub.U).

In a nutshell, the robust optimal solution is simply “the best uncertainty-immunized” solution we can associate with our uncertain problem.

Example 1.1.1 continued. Let us find the robust optimal solution to the uncertain problem (Drug). There is exactly one uncertainty-affected “block” in the data, namely, the coefficients of RawI, RawII in the balance constraint. A candidate solution is thus robust feasible if and only if it satisfies all constraints of (Drug), except for the balance constraint, and it satisfies the “worst” realization of the balance constraint. Since RawI, RawII are nonnegative, the worst realization of the balance constraint is the one where the uncertain coefficients anI, anII are set to their minimal values in the uncertainty set (these values are 0.00995 and 0.0196, respectively). Since the objective is not affected by the uncertainty, the robust objective values are the same as the original ones. Thus, the RC (Robust Counterpart) of our uncertain problem is the LO problem

[ILLUSTRATION OMITTED]

Solving this problem, we get

RobOpt = -8294.567; RawI = 877.732, RawII = 0, DrugI = 17.467, DrugII = 0.

The “price” of robustness is the reduction in the promised profit from its nominal optimal value 8819.658 to its robust optimal value 8294.567, that is, by 5.954%. This is much less than the 21% reduction of the actual profit to 6,929 which we may suffer when sticking to the nominal optimal solution when the “true” data are “against” it. Note also that the structure of the robust optimal solution is quite different from the one of the nominal optimal solution: with the robust solution, we shall buy only raw materials RawI, while with the nominal one, only raw materials RawII. The explanation is clear: with the nominal data, RawII as compared to RawI results in a bit smaller per unit price of the active agent (9,995 $/g vs. 10,000 $/g). This is why it does not make sense to use RawI with the nominal data. The robust optimal solution takes into account that the uncertainty in anI (i.e., the variability of contents of active agent in RawI) is 4 times smaller than that of anII (0.5% vs. 2%), which ultimately makes it better to use RawI.

(Continues…)

Excerpted from Robust Optimizationby Aharon Ben-Tal Laurent El Ghaoui Arkadi Nemirovski Copyright © 2009 by Princeton University Press. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.