Robust Solutions to Uncertain Semidefinite Programs.
In this paper we consider semidefinite programs (SDPs) whose data depend on some unknown but bounded perturbation parameters.  We seek "robust" solutions to such programs, that is, solutions which minimize the (worst-case) objective while satisfying the constraints for every possible value of parameters within the given bounds. Assuming the data matrices are rational functions of the perturbation parameters, we show how to formulate sufficient conditions for a robust solution to exist as SDPs.  When the perturbation is "full," our conditions are necessary and sufficient.  In this case, we provide sufficient conditions which guarantee that the robust solution is unique and continuous (Hlder-stable) with respect to the unperturbed problem's data.  The approach can thus be used to regularize ill-conditioned SDPs.  We illustrate our results with examples taken from linear programming, maximum norm minimization, polynomial interpolation, and integer programming.
Introduction
. A semidefinite program (SDP) consists of minimizing a linear
objective under a linear matrix inequality (LMI) constraint; precisely,
subject to F
(1)
- {0} and the symmetric matrices F
are given. SDPs are convex optimization problems and can be solved in polynomial
time with, e.g., primal-dual interior-point methods [24, 35, 26, 19, 2]. SDPs include
linear programs and convex quadratically constrained quadratic programs, and arise
in a wide range of engineering applications; see, e.g., [12, 1, 35, 22].
In the SDP (1), the "data" consist of the objective vector c and the matrices
In practice, these data are subject to uncertainty. An extensive body of
work has concentrated on the sensitivity issue, in which the perturbations are assumed
to be infinitesimal, and regularity of optimal values and solution(s), as functions of
the data matrices, is studied. Recent references on sensitivity analysis include [30,
31, 10] for general nonlinear programs, [33] for semi-infinite programs, and [32] for
semidefinite programs.
When the perturbation a#ecting the data of the problem is not necessarily small,
a sensitivity analysis is not su#cient. For general optimization problems, a whole field
# Received by the editors June 21, 1996; accepted for publication (in revised form) September 22,
1997; published electronically October 30, 1998.
http://www.siam.org/journals/siopt/9-1/30571.html
Ecole Nationale Sup-erieure de Techniques Avanc-ees, 32, Bd. Victor, 75739 Paris, France
(elghaoui@ensta.fr, oustry@ensta.fr, lebret@ensta.fr).
34 L. EL GHAOUI, F. OUSTRY, AND H. LEBRET
of study (stochastic programming) concentrates on the case where the perturbation
is stochastic with known statistics. One object of this field is to study the impact of,
say, a random objective on the distribution of optimal values (this problem is called
the "distribution problem"). References relevant to this approach to the perturbation
problem include [15, 9, 29]. We are not aware of special references for general SDPs
with randomly perturbed data except for the last section of [30], some exercises in
the course notes of [13], and section 2.6 in [23].
The main objective of this paper is to quantify the e#ect of unknown but bounded
deterministic perturbation of problem data on solutions. In our framework, the perturbation
is not necessarily small, and we seek a solution that is "robust," that is,
remains feasible despite the allowable, not necessarily small, perturbation. Our aim
is to obtain (approximate) robust solutions via SDP. Links between regularity of solutions
and robustness are, of course, expected. One of our side objectives is to
clarify these links to some extent. This paper extends results given in [16] for the
least-squares problem.
The approach developed here can be viewed as a special case of stochastic programming
in which the distribution of the perturbation is uniform.
The ideas developed in this paper draw mainly from two sources: control theory,
in which we have found the tools for robustness analysis [36, 17, 12] and some recent
work on sensitivity analysis of optimization problems by Shapiro [31] and Bonnans,
Cominetti, and Shapiro [10].
Shortly after completion of our manuscript, we became aware of the ongoing
work of Ben-Tal and Nemirovski on the same subject. In [7], they apply similar ideas
to a truss topology design problem and derive very e#cient algorithms for solving
the corresponding robustness problem. In [8], the general problem of tractability of
obtaining a robust solution is studied, and "tractable counterparts" of a large class of
uncertain SDPs are given. The case of robust linear programming, under quite general
assumptions on the perturbation bounds, is studied in detail in [6]. Our paper can
be seen as a complement of [8], giving ways to cope with (not necessarily) tractable
robust SDPs by means of upper bounds. (In particular, our paper handles the case
of nonlinear dependence of the data on the uncertainties.) A unified treatment, and
more results, will appear in [4].
The paper is divided as follows. Our problem is defined in section 2. In section
3, we show how to compute upper bounds on our problem via SDP. We give
special attention to the so-called full perturbations case, for which our results are
nonconservative. In section 4, we examine sensitivity of the robust solutions in the
full perturbations case. We provide conditions which guarantee that the robust solution
is unique and a regular function of the data matrices. We then consider several
interesting examples in section 5, such as robust linear programming, robust norm
minimization, and error-in-variables SDPs.
2. Problem definition.
2.1. Robust SDPs. Let F(x, #) be a symmetric matrix-valued function of two
variables x # R m
. In the following, we consider x to be the decision
variable, and we think of # as a perturbation. We assume that # is unknown but
bounded. Precisely, we assume that # is known to belong to a given linear subspace
D of R p-q , and in addition, #, where # 0 is given.
In section 2.2, we will be more precise about the dependence of F on #.
We define the robust feasible set by
for every # D, #,
F(x, #) is well defined and F(x, # 0
# .
(2)
Now let c(#) be a vector-valued rational function of the perturbation #, such that
We consider the following min-max problem:
c(#) T x subject to x # X # .
From now on, we assume that the function c(#) is independent of # (in other
words, the objective vector c is not subject to perturbation). This is done with no
loss of generality: introduce a slack variable # and define
Problem (3) can be formulated as
x subject to -
# is the robust feasible set corresponding to the function -
F.
In the following, we thus consider a problem of the form
subject to x # X #
and refer to it as a robust semidefinite problem (RSDP). In general, although X #
is convex, P # is not a tractable problem-in particular, it is not an SDP. Our aim
is to find a convex, inner approximation of X # that is described by a linear matrix
inequality constraint. This inner approximation is then used to find an upper bound
on the optimal value of P # by solving an SDP. In some cases, we can prove our results
are nonconservative, that is, as in the so-called "full perturbation" case.
We refer to the set X 0 (resp., problem P 0 , i.e., (1)) as the nominal feasible set
nominal SDP). We shall assume that the nominal SDP is feasible, that is,
course, the robust feasible set X # may become empty for some # > 0; we
return to this question later.
2.2. Linear-fractional representation. In this paper, we restrict our attention
to functions F that are given by a "linear-fractional representation" (LFR):
where F (x) is defined in (1), R(-) is an a#ne mapping taking values in R q-n , and
L # R n-p and D # R q-p are given matrices. Together, the mappings F (-), R(-), the
matrices L, D, the subspace D, and the scalar # constitute our perturbation model for
the nominal SDP (1).
The above class of models seems quite specialized. In fact, these models can
be used in a wide variety of situations, for example, in the case where the (matrix)
coe#cients F i in P 0 are rational functions of the perturbation. The representation
lemma, given below, and the examples of section 5 illustrate this point.
A constructive proof of the following result can be found in [37].
Lemma 2.1. For any rational matrix function M : R k
singularities
at the origin, there exist nonnegative integers r 1 , . , r k , and matrices M # R n-c ,
36 L. EL GHAOUI, F. OUSTRY, AND H. LEBRET
, such that M has the
following linear-fractional representation (LFR): For all # where M is defined,
Using the LFR lemma, we may devise LFR models for SDPs, where a perturbation
vector
enters rationally in the coe#cient matrices. The resulting set D of
perturbation matrices # is then a set of diagonal matrices of repeated elements, as
in (6). Componentwise bounds on the vector #, such as |#| i #,
into a norm-bound # on the corresponding matrix #.
2.3. A special case. We distinguish a special case for which exact (nonconser-
vative) results can be obtained via SDP. This is when F(x, #) is block diagonal, each
block being independently perturbed-precisely, when
where each F i (x, # i ) assumes the form shown in section 2.2 for appropriate L i , R i , D i ,
with consists of block-diagonal matrices of the form
# .
We refer to this situation as the block-full perturbation case. When
of the full perturbation case. As will be seen later, all results given for can be
generalized to the case L > 1.
3. Robust solutions for SDPs. Unless otherwise specified, we fix # > 0.
3.1. Full perturbations case. In this section, we consider the full perturbations
case, that is,
. We assume #D# -1 , which is a necessary and
su#cient condition for F(x, #) to be well defined for every x
#.
The following lemma is a simple corollary of a classic result on quadratic inequal-
ities, referred to as the S-procedure [12]. Its proof is detailed in [16].
Lemma 3.1. Let real matrices of appropriate size. We have
det(I -D#= 0 and
for every # 1, if and only if #D# < 1 and there exists a scalar # such that
A direct application of the above lemma shows that, in the full perturbations
case, the RSDP (4) is an SDP.
Theorem 3.1. When the RSDP (4) and a corresponding solution x
can be computed by solving the SDP in variables
subject to # F (x) - #LL T R(x) T
ROBUST SOLUTIONS TO UNCERTAIN SEMIDEFINITE PROGRAMS 37
Special barrier functions adapted to a conic formulation of the problem can be
devised and yield an interior-point algorithm that has the same complexity as the
nominal problem; see [24].
We may define the maximum allowable perturbation level, which is the largest
number # max such that X # for every #, 0 #
Computing # max is a (quasi-convex) generalized eigenvalue minimization
problem [24, 11]:
minimize # subject to # F (x) - #LL T R(x) T
Remark. The above exact results are readily generalized to the block-full perturbation
case (L > 1) as defined in section 2.2.
3.2. Structured case. We now turn to the general case (D is now an arbitrary
linear subspace). In this section, we associate with D the following linear subspace:
-R q-q
-R q-p
S#T , G# T G T for every # D # .
As shown in [16], a general instance of problem (4) is NP-hard. Therefore, we
look for upper bounds on its optimal value. The following lemma is a generalization
of Lemma 3.1 that traces back to [17]. Its proof is detailed in [16].
Lemma 3.2. Let real matrices of appropriate size. Let D be
a subspace of R p-q , and denote by B the set of matrices associated with D as in (11).
We have det(I -D#= 0 and
for every # D, # 1 if there exist a triple (S, T,
and
Using Lemma 3.2, we obtain the following result.
Theorem 3.2. An upper bound on the RSDP (4) and a corresponding solution
x can be computed by solving the SDP in variables x, S, T
subject to (S, T,
Note that when the perturbation is full, the variable G is zero and S, T are of the
form #I p , #I q , resp., for some # 0. We then recover the exact results of section 3.1.
As before, we may define the maximum allowable perturbation level, which is the
largest number # max such that X # for every #, 0 # max . Computing a
lower bound on this number is a (quasi-convex) generalized eigenvalue minimization
problem:
subject to (S, T,
38 L. EL GHAOUI, F. OUSTRY, AND H. LEBRET
4. Uniqueness and regularity of robust solutions. In this section, we derive
uniqueness and regularity results for the RSDP in the case of full perturbations. As
before, we first take . The results of this section
remain valid in the general case L > 1 (several blocks).
We fix #, 0 < # max . For simplicity of notation (and without loss of generality)
we take 1). For well-posedness reasons, we must assume
#D# < 1. We make the further assumption that #) is
a#ne in #). In section 4.5, we show how the case D #= 0 can be treated.
For full perturbations and the RSDP is the SDP
subject to # F (x) - #LL T R(x) T
4.1. Hypotheses. We assume that the SDP (15) (with satisfies the
following hypotheses:
H1. The Slater condition holds, that is, the problem is strictly feasible.
H2. The problem is inf-compact, meaning that any unbounded sequence
feasible points (if any) produces an unbounded sequence of objectives. An
equivalent condition is that the Slater condition holds for the dual problem
[28, p. 317, Thm. 30.4].
H3. (a) The nullspace of the matrix
x
is independent of (#, x) #= (0, 0) and not equal to the whole space.
(b) For every x,
# is full column-rank.
Hypotheses H1 and H2 ensure, in particular, the existence of optimal points for problem
(15) and its dual. Hypotheses H3(a) and (b) are di#cult to check in general, but
sometimes can be easily tested in practical examples, as seen in section 5. We note
that H3(a) implies that R(x) #= 0 for every x.
Hypothesis H1 is equivalent to Robinson's condition [27], which can be expressed
in terms of
# .
Robinson's condition is stated in [27] as the existence of x 0
R such that
where dF is the di#erential of F , and S
n+q is the set of positive semidefinite matrices
of q. The equivalence between H1 and Robinson's assumption is not true,
in general. Here, this equivalence stems from the fact that the problem is convex and
that the cone S
n+q has a nonempty interior.
Remark. Hypothesis H1 holds if and only if it holds for the nominal problem (1)
(recall our assumption # max > 1). Also, hypothesis H2 implies L #= 0 (otherwise, we
can let # without a#ecting the objective value). If H2 holds for the nominal
problem and L #= 0, then H2 holds for the RSDP (15).
4.2. An equivalent nonlinear program. Let x opt , # opt be optimal for (15).
Hypothesis H3(a) ensures that any # that is feasible for (15) is nonzero (otherwise,
R(x) would be zero for some x). We thus have # opt > 0.
We introduce some notation. For x
Using Schur complements and # opt > 0, we obtain that problem (15) can be
rewritten as
minimize d T y subject to G(y) # 0
and that y
Our aim is first to prove that the
so-called quadratic growth condition [10] holds at y opt for problem (16). Then, we
will apply the results of [10] to obtain uniqueness and regularity theorems.
4.3. Checking the quadratic growth condition. Following [10], we say that
the quadratic growth condition (QGC) holds at y opt if there exists a scalar # > 0 such
that, for every feasible y,
Roughly speaking, this condition guarantees that y opt is not on a facet on the boundary
of the feasible set.
Define the set of dual variables associated with y opt by
The following result is a direct consequence of a general result by Bonnans,
Cominetti, and Shapiro [10]. Roughly speaking, this result states that, if an optimization
problem satisfies Robinson's condition and has an optimal point, and if a
certain "curvature" condition is satisfied, then the QGC holds at that point.
Theorem 4.1. With the notation above, if H1 and H2 hold, and if
then problem (16) satisfies the QGC.
The following theorem is proven in appendix A.
Theorem 4.2. If H1-H3 hold, problem (15) satisfies the quadratic growth condition
at every optimal point y opt . Consequently, there exists a unique solution to the
SDP (15).
Remark. Note that the QGC is satisfied independent of the objective vector. This
means that the boundary of the feasible set is strictly convex (it contains no facets).
4.4. Regularity results. In problem (15), the data consist of the matrices L,
We seek to examine the sensitivity of the problem with
respect to small variations in F i , L i , and R i .
In this section, we consider matrices
are functions of class C 1 of a (small) parameter vector u. Define
x
We denote by P(u) the corresponding problem (15), where F (-), R(-), and L are
replaced by F (-, u), R(-, u), and L(u). We assume that F (-,
and L, so that P(0) is (15).
We first note that, in the vicinity of problem P(u) satisfies the hypotheses
H1 and H2 if P(0) does. In this case, for every # > 0 we may define the set S # (u) of
#-suboptimal points of P(u):
where v(u) is the optimal value of P(u).
Recall that, if P 0 satisfies hypotheses H1 and H2, the optimal value v(u) is con-
tinuous, and even directionally di#erentiable, at Thm. 5.1]. With the QGC
in force, and using [31, Thm. 4.1], we can give quite complete regularity results for
the robust solutions.
Theorem 4.3. If hypotheses H1-H3 hold for P(0), then for every
there exists a # > 0 and a neighborhood V of such that for every u # V and
When H1-H3 hold for P(0), the above theorem states that every (su#ciently)
suboptimal solution to P(0) is H-older-stable (with coe#cient 1/2). This is true, in
particular, for any optimal solution of P(u) (that is, for 0). The fact that the
theorem remains true for # > 0 guarantees regularity of numerical solutions to the
RSDP. The main consequence is that even if the nominal SDP is ill conditioned (with
respect to variations in the F i 's), the RSDP becomes well conditioned for every # > 0.
Now assume #= 1. We seek to examine the behavior of problem (10) (with
when the uncertainty level # for 0 < # max varies. This is a special case of
the problem examined above, with
Corollary 4.1. For every #, 0 < # max , the solution to (10) (with
is unique and satisfies the regularity results (written with #) of Theorem 4.3.
Remark. The results of this section are all valid in the block-full perturbation
case (L > 1), as defined in section 2.2. Of course, the conditions given in H3 should
be understood blockwise.
4.5. Case D #= 0. When D #= 0, we can get back to the case
Recall that we have #D# < 1 in order to ensure that F(x, #) is defined everywhere
on D. With this assumption, we can define, for x
Using Schur complements, we have, for every x and # > 0,
Hypothesis H3 holds for -
L, -
R(-) if and only if it holds for L, R(-). We can then follow
the steps detailed previously.
Corollary 4.2. If the SDP (10) (with
then the results of Theorem 4.3 hold.
5. Examples.
5.1. Unstructured perturbations. Assume
This case corresponds to the representation in section 5, with
x
Using Lemma 3.2, we obtain that problem (4) is equivalent to the SDP
subject to # F (x) - #I # 1 x T
#I
T#I #I
It turns out that we may get rid of the variable # and get back to a convex problem
of the same size as that of the unperturbed problem (1). To see this, first note that
every feasible variable # in problem (20) is strictly positive. Use Schur complements
to rewrite the matrix inequality in (20) as
Minimizing (over variable #) the scalar in the left-hand side of the above inequality
shows that the RSDP (1) is equivalent to
subject to F (x) #
Formulation (21) is more advantageous than (20), since (21) involves a (convex) matrix
inequality constraint of the same size as the original problem. As noted before, special
barrier functions can be devised for this problem and yield an interior-point algorithm
that has the same complexity as the original problem; see [24].
We note that, with the above choice for L, R, hypothesis H3 holds, which yields
the following result.
Theorem 5.1. The optimal value of the RSDP (20) can be computed by solving
the convex problem (21). If (21) satisfies hypotheses H1 and H2, then for every # > 0,
the solution is unique and satisfies the regularity conditions of Theorem 4.3.
Remark. A su#cient condition for hypotheses H1 and H2 to hold for (21) is that
they hold for the nominal problem. A more restrictive su#cient condition is that the
nominal feasible set X 0 is nonempty and bounded, and # max .
42 L. EL GHAOUI, F. OUSTRY, AND H. LEBRET
.3
x
Fig. 1. Nominal and robust solutions of an SDP, with a 5 - 5 matrix F (x). Here
5.2. Robust center of a linear matrix inequality. In this section, for # > 0,
we consider the SDP (21) and corresponding feasible (convex) set X # . We assume
that X 0 is nonempty and bounded, and that P 0 is strictly feasible. Then, for every #,
is nonempty and bounded, and we can define a (unique) solution
x(#) to the strictly convex problem (21).
In view of Corollary 4.1, x(#) is a continuous function of # in ]0 # max [. Since (X # )
is a decreasing family of bounded sets, we may define
x(#).
Note that x # is independent on the objective vector c.
Thus, to the matrix inequality F (x) # 0, we may associate the robust center,
defined by (22). The robust center has the property of being the most tolerant (with
respect to unstructured perturbation) among the feasible points.
An example is depicted in Fig. 1. The nominal feasible set X 0 is described by a
linear matrix inequality F (x) # 0, where F is a 5 - 5 matrix. For various values of #,
we seek to minimize x 2 . The dashed lines correspond to the optimal objectives. As #
increases, we observe that the robust feasible sets shrink. A crucial property of these
robust sets is that they do not possess any straight faces, as observed in the figure.
For the robust feasible set is a singleton (in this example, x
the optimal solution is not unique and not continuous with respect
to changes in the coe#cient matrices F i , (although the optimal value is
continuous). Since the sets X # become strictly convex as soon as # > 0, the resulting
robust solutions are continuous.
5.3. Robust linear programs. An interesting special case arises with linear
programming (LP). Consider the LP
subject to a T
Assume that the a i 's and b i 's are subject to unstructured perturbations. The perturbed
value of [a T
We seek a
ROBUST SOLUTIONS TO UNCERTAIN SEMIDEFINITE PROGRAMS 43
robust solution to our problem, which is a special case of the block-full perturbation
case referred to in section 2.2, with F given by (7), and
and D is the set of diagonal, L - L matrices. The robust LP is
subject to a T
The above program is readily written as an SDP by introducing slack variables. In
fact, the robust LP is a second-order cone program (SOCP) for which e#cient special-purpose
interior-point methods are available [24, 20, 23].
We note that hypothesis H3 holds blockwise. This yields the following result.
Theorem 5.2. The optimal value of the robust LP can be computed by solving
the convex problem (23). If the latter satisfies hypotheses H1 and H2, then for every
#, 0 < # max , the solution is unique and satisfies the regularity conditions of
Theorem 4.3.
In [6], robust linear programming is studied in detail. For a wide class of perturbation
models, where the data of every linear constraint vary in an ellipsoid, explicit
robust solutions are constructed using convex SOCPs. Reference [23] also provides
examples of robust linear programs solved via SOCP.
5.4. Robust eigenvalue minimization. Consider the case where the nominal
problem consists of minimizing the largest eigenvalue of a matrix-valued function
When F (-) is subject to unstructured perturbations (as defined in section 5.1), the
robust version of the problem is
subject to #I # F (x),
or equivalently
When written in an SDP form, the above problem satisfies the
hypotheses H1-H3. From Theorem 4.3 we obtain that the solution is unique. If we
consider that the data of the above problem consist of the matrices F i ,
then we know that the corresponding solution is H-older-stable (with coe#cient 1/2).
Since the problem is unconstrained, we can use a result of Shapiro [31, Thm. 3.1], by
which we conclude that the solution is actually Lipschitz stable (inequality (18) holds
with the exponent 1/2 replaced by 1). Finally, using the results from Attouch [3], we
can show that computing the solution for # 0 amounts to selecting the minimum
norm solution among the solutions of the nominal problem.
Theorem 5.3. The optimal value of the min-max problem (24) can be computed
by solving the convex problem (25). For every # > 0, the solution is unique and is
Lipschitz stable with respect to perturbations in F i , the
solution converges to the minimum norm solution of the nominal problem (24).
Remark. In this case, the RSDP is a regularized version of the nominal SDP, which
belongs to the class of Tikhonov regularizations [34]. The regularization parameter
44 L. EL GHAOUI, F. OUSTRY, AND H. LEBRET
is 2# and is chosen according to some a priori information on uncertainty associated
with the nominal problem's data. Taking # close to zero can be used as a selection
procedure for choosing a particular (minimum norm, regular) solution among the (not
necessarily unique and/or regular) solutions of the nominal problem.
Problem (25) is particularly suitable to the recent so-called U-Newton algorithms
for solving problem (24). These methods, described in [21, 25], require that the Hessian
of the "smooth part" (the so-called U-Hessian) of the objective of (24) be positive
definite. For general mappings F (-), this property is not guaranteed. However, when
looking at the robust problem (25), we see that the modified U-Hessian is guaranteed
to be positive definite for every x and # > 0. This indicates that the RSDP approach
may be used to devise robust algorithms for solving SDPs.
5.5. Robust SOCPs. An SOCP is a problem of the form
subject to #C
can be
formulated as SDPs, but special-purpose, more e#cient algorithms can be devised for
them; see [24, 5, 23].
Assuming that C i , d i , e i , f i are subject to linear-or even rational-uncertainty,
we may formulate the corresponding RSDP as an SDP. This SDP can be written as
an SOCP if the uncertainty is unstructured and a#ects each constraint independently.
The subject of robust SOCPs is explored in [5] in detail. Explicit SDPs that
yield robust counterparts to SOCPs nonconservatively are given for a wide class of
uncertainty structures. In some cases, albeit not all, the robust counterpart is itself
an SOCP. In [16, 14], the special case of least-squares problems with uncertainty in
the data is studied at length.
5.6. Robust maximum norm minimization. Several engineering problems
take the form
minimize #H(x)#,
where
are given p-q matrices. A well-known instance of this problem is
the linear least-squares problem, with Another example is a minimal
norm extension problem for a Hankel operator studied in [18], in which H 0 is a given
Hankel matrix and H i , is the n - n Hankel matrix
associated with the polynomial 1/z i . In practice, the matrices H i , are
subject to perturbation, which motivates a study of the robust version of problem (27).
Note that the least-squares case is extensively studied in [16].
Consider the full perturbation case, which occurs when each H i is perturbed independently
in a linear manner. Precisely, consider the matrix-valued function
For a given # > 0, we address the min-max problem
min
x
#H(x, #.
This problem is an RSDP for which we can get exact results using SDP. Indeed, for
every x # R m and # 0, the property
is equivalent to F(x, # 0 for every #, where
where
F (x, #I H(x)
x
I # .
We thus write problem (28) as (4), where the perturbation set D is R p-q .
Applying Theorem 3.2, we obtain that the RSDP above is equivalent to the
As in section 5.1, we may get rid of the variable # and
obtain the equivalent formulation
This RSDP satisfies hypotheses H1-H3, so we conclude that the results of Theorem 4.3
hold. As in robust eigenvalue minimization, we can get improved results using [31,
section 3, Thm. 3.1].
Theorem 5.4. The optimal value of the min-max problem (28) can be computed
by solving the convex problem (29). For every # > 0, the solution is unique and
Lipschitz stable with respect to perturbations in H i , the
solution converges to the minimum norm solution of the nominal problem (27).
Remark. As for the RSDP arising in robust eigenvalue minimization, the robust
minimum norm minimization problem is a regularized version of the nominal problem,
which belongs to the class of Tikhonov regularizations.
We now consider the general case where each matrix H i in (27) is perturbed in
a structured manner. To be specific, we concentrate on the minimal norm extension
problem mentioned above.
In practice, the matrix H 0 is obtained from measurement and is thus subject to
error. We may assume that this matrix is constructed from an n - 1 vector h 0
is unknown but bounded. The perturbed matrix H 0 is of the form
where L, R are given matrices (the exact form of which we do not detail), and
(In the above, each # i corresponds to the uncertainty associated with the ith antidiagonal
of H 0 .) We address the min-max problem
L. EL GHAOUI, F. OUSTRY, AND H. LEBRET
This problem is amenable to the robustness analysis technique. Defining
we obtain the following result.
Theorem 5.5. An upper bound on the objective value of the min-max problem
(30) can be computed by solving the SDP in variables x, S, G:
subject to
5.7. Polynomial interpolation. This example, taken from [16], can be formulated
as an RSDP with rational dependence. For given integers n # 1, k, we seek a
polynomial of degree that interpolates given points
(a
If we assume that (a i , b i ) are known exactly, we obtain a linear equation in the unknown
x, with a Vandermonde structure:
1 a 1 . a n-11 a k . a n-1
which can be solved via standard least-squares techniques.
Now assume that the interpolation points are not known exactly. For instance,
we may assume that the b i 's are known, while the a i 's are parameter dependent:
a
where the # i 's are unknown but bounded: |# i | #,
We seek a robust interpolant, that is, a solution x that minimizes
where
1 a k (#) . a k (#) n-1
# .
The above problem is an RSDP. Indeed, it can be shown that
where
. a n-2
and, for each i,
. a n-2
. a i
. a n-3
. a i
(Note that det(I - D#= 0, since D is strictly upper triangular.) With the above
notation, if we define F(x, #) as in section 5, then problem (31) can be formulated as
the RSDP (4).
With the approach described in this paper, one can compute an upper bound for
the minimizing value of (31), and a corresponding suboptimal x. We do not know if
the problem can be solved exactly in polynomial time, e.g., using SDP. We conjecture
(as the reviewers of this paper did) that the answer is no. To motivate this claim,
note that the solution to the problem of computing (31) for arbitrary a#ne functions
A is already NP-hard [16].
5.8. Error-in-variables RSDPs. In many SDPs that arise in engineering, the
variable x represents physical parameters that can be implemented with finite absolute
precision only. A typical example is integer programming, where integer solutions
to (linear) programs are sought. These problems (which are equivalent to integer
programming) are NP-hard. We now show that we may find upper bounds on these
problems using robustness analysis.
Consider, for instance, the problem of finding a solution x to the feasibility SDP
find an integer vector x such that F (x) # 0.
Now, consider the robust SDP
maximize # subject to
Assume there exists a feasible pair (x feas , #) to the above problem, with # 0. By
construction, x feas satisfies F Furthermore, any vector x chosen such that
is guaranteed to satisfy F (x) # 0. This is true, in particular,
for x int , the integer closest to x feas . Thus, if we know a positive lower bound #,
and corresponding feasible point for problem (33), then we can compute an integer
solution to our original problem.
Finding a lower bound for (33) and an associated feasible point can be done as
follows. For
Let
Rm
# , and
48 L. EL GHAOUI, F. OUSTRY, AND H. LEBRET
Problem (33) can be formulated as
maximize # subject to #I # F
for every # D, # 1/2.
The above is a special instance of the structured problem examined in section 3.2.
Theorem 5.6. A su#cient condition for an integer solution to the feasibility
SDP (32) is that the constraints
are feasible. If x feas is feasible for the above constraints, then any integer vector closest
to x feas (in the maximum norm sense) is feasible for (32).
6. Conclusions. In this paper, we considered semidefinite programs subject to
uncertainty. Assuming the latter is unknown but bounded, we have provided su#cient
conditions that guarantee "robust" solutions to exist via SDPs. Under some conditions
(detailed in section 4), the robust solution is unique, and not surprisingly, stable. The
method can then be used to regularize possibly ill-conditioned problems. For some
perturbation structures (as for unstructured perturbations), the conditions are also
necessary. That is, there is no conservatism induced by the method.
The paper raises several open questions.
In our description, we have considered the problem of making the primal SDP
robust, thereby obtaining upper bounds on an SDP subject to uncertainty. The
dual point of view should be very interesting. One might be interested in applying
the approach to the dual problem instead. Does this lead to lower bounds on the
perturbed problem? Also, in some cases, the RSDP approach leads to a unique (and
stable) primal solution. May we obtain a unique solution to the dual problem by
making the latter robust? (This would lead to analyticity of the primal solution;
see [32].)
As seen in section 5.2 the notion of robust center has, certainly, connections with
the well-known analytic center; is the latter related to some robustness characterization

It seems that the RSDP method could be useful for deriving fast and robust
(stable) algorithms for solving SDPs (see section 5.4), especially in connection with
maximum eigenvalue minimization.
Finally, as said in section 2.2 (Lemma 2.1), an SDP with coe#cient matrices
depending rationally on a perturbation vector can always be represented by an LFR
model. Now, this LFR model is not unique. However, the results given here (for
example, Theorem 3.2) hinge on a particular linear-fractional representation for a
perturbed SDP. Hence we have the question: are our results independent of the chosen
representation? We partially answer this di#cult question in Appendix B.


Appendix

A. Proof of Theorem 4.2. We take the notation of section 4.
diag(Z, -) be dual variables associated with are optimal
(their existence is guaranteed by H1 and H2). Then, Y # Y(y opt ). Let us show that
condition (17) holds for this choice of Y .
Since the problem satisfies H1 and H2, the complementarity conditions hold;
therefore, the (optimal) dual variable - associated with the constraint # opt is
zero. Consequently the variable Z is nonzero (recall c #= 0). Using
TrY
we obtain
From # opt #= 0 (implied by H3(a)), and using hypothesis H3(b), we can show that
are impossible for Z # 0, Z #= 0. This yields TrR(x opt ) T R(x opt )Z > 0.
Now let # R m and # R, and define
We have, for every i,
(R(x)
(R T
By summation, we have
(R(#)
opt
opt
R T
R+# opt
R(x opt ). We obtain finally,
opt
0 with means that every column of Z 1/2 belongs
to the nullspace of R(#) -R(0). Now assume #= 0. By hypothesis H3(a), we obtain
that every column of Z 1/2 also belongs to the nullspace of R(x opt ), which contradicts
50 L. EL GHAOUI, F. OUSTRY, AND H. LEBRET
We conclude that # 2
yy L is positive definite at (y opt , Y ).
Thus, problem (15) satisfies the QCG.


Appendix

B. Invariance with respect to the LFR model. In this section,
we show that the su#cient conditions obtained in this paper are, in some sense,
independent of the LFR model used to describe the perturbation structure.
Consider a function F taking values in the set of symmetric matrices having an
LFR such as that in section 5. This function can be written in a more symmetric
#)
where we have dropped the dependence on x for convenience, and
# .
It is easy to check that, if an invertible matrix Z satisfies the relation Z -
# for
every # D, then
#)
LZ) T .
In other words, the "scaled" triple
DZ)) can be used to represent F
instead of F, -
L, -
D in (35). By spanning valid scaling matrices Z, we span a subset of
all LFR models that describe F.
A valid scaling matrix Z can be constructed as follows. Let (S, T, G) # B, and
define
I
# .
It turns out that such a Z satisfies the relation Z -
# for every # D.
Using the above facts, we can show that if condition (13) is true for the original
LFR model F, L, R, D with appropriate S, T, G, then it is also true for the scaled LFR
obtained using any scaling matrix Z such as that above, for appropriate matrices -
T . That is, the condition is independent of the scaling Z.
In this sense, the conditions we obtained are independent of the LFR used to
represent the perturbation structure.

Acknowledgments

. This paper has benefitted from many stimulating discussions
with several colleagues, including Aharon Ben-Tal, Stephen Boyd, Arkadii Ne-
mirovski, Michael Overton, and particularly, Lieven Vandenberghe (who pointed out
a mistake just before the final version was sent). Last but not least, the authors would
like to thank the editor and reviewers for their very helpful comments and revisions.



--R

Interior point methods in semidefinite programming with applications to combinatorial optimization

Viscosity Solutions of Optimization Problems
in Semidefinite Programming and Applications

Robust Solutions to Uncertain Linear Programs
Robust truss topology design via semidefinite programming
Anal., <Year>1998</Year>, to appear.
Some Numerical Methods in
Sensitivity Analysis of Optimization Problems under Second Order Regular Constraints
Method of centers for minimizing generalized eigenvalues
Linear Matrix Inequalities in System and Control Theory
Introduction to convex optimization with engineering applications

New York
Robust solutions to least-squares problems with uncertain data
Robustness in the presence of mixed parametric uncertainty and unmodeled dynamics
Minimal norm extensions and eigenstructures
Global and Local Convergence of Predictor-Corrector- Interior-Point Algorithm for Semidefinite Programming




Interior Point Polynomial Methods in Convex Program- ming: Theory and Applications

On homogeneous interior-point algorithms for semidefinite pro- gramming
Stability theorems for systems of inequalities
Convex Analysis
Discrete Event Systems
Perturbation theory of nonlinear programs when the set of optimal solutions is not a singleton
Perturbation analysis of optimization problems in Banach spaces
First and second order analysis of nonlinear semidefinite programs.

Solutions of Ill-Posed Problems

The solution of certain matrix inequalities in automatic control theory
Robust and Optimal Control
--TR

--CTR
Frank Lutgens , Jos Sturm , Antoon Kolen, Robust One-Period Option Hedging, Operations Research, v.54 n.6, p.1051-1062, November 2006
Budi Santosa , Theodore B. Trafalis, Robust multiclass kernel-based classifiers, Computational Optimization and Applications, v.38 n.2, p.261-279, November  2007
B. P. Lampe , E. N. Rosenwasser, Polynomial solution to stabilization problem for multivariable sampled-data systems with time delay, Automation and Remote Control, v.67 n.1, p.105-114, January   2006
D. Goldfarb , G. Iyengar, Robust portfolio selection problems, Mathematics of Operations Research, v.28 n.1, p.1-38, February
Mung Chiang, Geometric programming for communication systems, Communications and Information Theory, v.2 n.1/2, p.1-154, July 2005
uncertainty;robustness;regularization;semidefinite programming;convex optimization