Digital Object Identifier (DOI) 10.1007/s10107-003-0499-yMath. Program., Ser. A 102: 25–46 (2005)Giuseppe Calafiore · M.C. CampiUncertain convex programs: randomized solutions andconfidence levelsReceived: September 12, 2002 / Accepted: November 28, 2003Published online: February 6, 2004 – © Springer-Verlag 2004Abstract. Many engineering problems can be cast as optimization problems subject to convex constraintsthat are parameterized by an uncertainty or ‘instance’parameter. Two main approaches are generally availableto tackle constrained optimization problems in presence of uncertainty: robust optimization and chance-con-strained optimization. Robust optimization is a deterministic paradigm where one seeks a solution whichsimultaneously satisfies all possible constraint instances. In chance-constrained optimization a probabilitydistribution is instead assumed on the uncertain parameters, and the constraints are enforced up to a pre-speci-fied level of probability. Unfortunately however, both approaches lead to computationally intractable problemformulations.In this paper, we consider an alternative ‘randomized’or ‘scenario’approach for dealing with uncertaintyin optimization, based on constraint sampling. In particular, we study the constrained optimization problemresulting by taking into account only a finite set of N constraints, chosen at random among the possibleconstraint instances of the uncertain problem. We show that the resulting randomized solution fails to satisfyonly a small portion of the original constraints, provided that a sufficient number of samples is drawn. Ourkey result is to provide an efficient and explicit bound on the measure (probability or volume) of the originalconstraints that are possibly violated by the randomized solution. This volume rapidly decreases to zero as Nis increased.1. IntroductionUncertain convex programming [4, 15] deals with convex optimization problemsin which the constraints are imprecisely known. In formal terms, an uncertain convexprogram (UCP) is a family of convex optimization problems whose constraints areparameterized by an uncertainty (or instance) parameter δ ∈  ⊆ RUCP :minx∈X ⊆RncTx subject to f(x,δ)≤ 0,δ∈ , (1)where x ∈ X is the optimization variable, X is convex and closed, and the functionf(x,δ) : X ×  → R is convex in x for all δ ∈ . The function f(x,δ) is hereG. Calafiore: Dipartimento di Automatica e Informatica, Politecnico di Torino, corso Duca degli Abruzzi, 24,10129 Torino, Italy. Tel.: +39-011-564 7071; Fax: +39-011-564 7099e-mail: [email protected]. Campi: Dipartimento di Automatica per l’Automazione, Universit`a di Brescia, via Branze 38, 25123Brescia, Italy. e-mail: [email protected] work is supported in part by the European Commission under the project HYBRIDGE IST-2001-32460,and by MIUR under the project “New methods for Identification and Adaptive Control for Industrial Systems,”and the FIRB project “Learning, randomization and guaranteed predictive inference for complex uncertainsystems.”26 G. Calafiore, M.C. Campiassumed to be scalar-valued without loss of generality, since multiple scalar-valued con-vex constraints fi(x, δ) ≤ 0, i = 1,... ,nf, may always be converted into a singlescalar-valued convex constraint of the form f(x,δ)= maxi=1,... ,nffi(x, δ) ≤ 0. Also,in the problem family (1) the optimization objective is assumed to be linear and ‘certain’without loss of generality.1.1. Current solution approachesTwo main and distinct philosophies of solution to uncertain programs are currently foundin the literature: a probabilistic approach based on ‘chance constraints’, and a determinis-tic one based on ‘robust optimization’. The chance-constrained approach has the longesthistory, dating back to the work of Charnes and Cooper for linear programs in 1959, [10].The essence of this probabilistic approach is to consider the uncertainty parameter δ as arandom variable and to enforce the constraints up to a desired level of probability. Moreprecisely, if P is the probability on , and ∈ [0, 1] is an acceptable ‘risk’of constraintviolation, the chance (or probability) constrained version of the uncertain program is thefollowing programPCP : minx∈X ⊆RncTx subject to P {f(x,δ) >0}≤ . (2)Unfortunately however, such kind of optimization problems turn out to be extremelydifficult to solve exactly. Moreover, even if f(x,δ)is convex in x for all δ, the feasibleset {x : P {f(x,δ) > 0}≤ } may be nonconvex, and hence PCP is not a convex pro-gram in general. We direct the reader to the monograph by Pr´ekopa [27] for an extensivepresentation of many available results on chance-constrained optimization.An alternative to the chance-constrained approach to the solution of uncertain pro-grams is the so-called ‘min-max’ or ‘worst-case’ approach. While the worst-case para-digm is classical in statistical decision theory, numerically efficient algorithms (mainlyinterior point methods for convex programming) for the solution of worst-case optimi-zation problems in some specific cases appeared only recently in the literature, see [3–5,14, 15]. Perhaps due to the influence of robust control theory on this particular area ofoptimization, the term ‘robust optimization’ was employed in the above references todenote the min-max or worst-case approach.In robust optimization one looks for a solution which is feasible for all possibleinstances of the uncertain parameter δ, and hence for all problem instances belonging tothe family UCP. This amounts to solving the following robust convex programRCP: minx∈RncTx subject to x ∈ X ∩ , (3)where.= δ∈{x : f(x,δ)≤ 0}(4)(throughout, we assume that X ∩  =∅).Notable special cases of the above problem are robust linear programs [5], for whichf(x,δ) is affine in x, and robust semidefinite programs [15], for which the set  isexpressed asUncertain convex programs: randomized solutions 27 = δ∈{x : F(x,δ)  0},where F(x,δ) = F0(δ) +ni=1xiFi(δ), Fi(δ) = FTi(δ), and ‘’ means ‘negativesemidefinite’.Robust convex programs have found applications in many contexts, such as trusstopology design [3], robust antenna array design, portfolio optimization, and robustestimation and filtering, [13, 15]. In the context of systems and control engineering,robust semidefinite programs proved to be useful in