NANZAN-TR-2010-05

Robust Semidefinite Programming Problems with General
Nonlinear Parameter Dependence:
Approaches Using the DC-Representations
Yasuaki Oishi and Teodoro Alamo

March 2011

Technical Report of the Nanzan Academic Society
Information Sciences and EngineeringRobust Semideﬁnite Programming Problems with General
Nonlinear Parameter Dependence:
Approaches Using the DC-Representations∗
Yasuaki Oishi† and Teodoro Alamo‡Two conservative approaches are proposed to a semideﬁnite programming problem nonlinearly dependent on uncertain parameters. These approaches are applicable to general nonlinear parameter
dependence not necessarily polynomial or rational. They are based on a mild assumption that theparameter dependence is expressed as the diﬀerence of two convex functions. The ﬁrst approach
uses constant bounds on the parameter dependence. Optimization of the bounds is reduced to convex nonsmooth minimization in general. The second approach uses parameter-dependent bounds
for a less conservative result. Optimization of the bounds is immediate when the gravity centeris computable for the parameter set. Numerical examples are presented for illustration of theapproaches.
Keywords:
robust semideﬁnite programming, nonlinear parameter dependence,
representation, convexity, conjugate functions, linear matrix inequalities, conservatism.

DC-

1. Introduction
A robust semideﬁnite programming problem (robust SDP problem) is an important optimization
problem, to which many control problems are reduced (Ben-Tal & Nemirovski, 2001; Scherer, 2006;
Ben-Tal, El Ghaoui, & Nemirovski, 2009). There, a linear objective function is to be optimized undera linear matrix inequality (LMI) constraint dependent on uncertain parameters. When the parameter
dependence is aﬃne, this problem is exactly solvable: the parameter-dependent constraint is replacedby the constraints corresponding to the vertices of the parameter set and the resulting problem issolved with the standard interior-point method. Note however that the problem is NP-hard even inthis simple case (Nemirovskii, 1993). When the parameter dependence is not aﬃne, a conservative
approach is usually taken: the parameter-dependent constraint is replaced by its suﬃcient condition
expressed by a ﬁnite number of parameter-independent LMI constraints. Considerable eﬀorts havebeen paid in the case of polynomial or rational parameter dependence (e.g., Ben-Tal & Nemirovski,
1998; El Ghaoui, Oustry, & Lebret, 1998; Bliman, 2004; Chesi, Garulli, Tesi, & Vicino, 2005; Scherer,
2005; Scherer & Hol, 2006; Peaucelle & Sato, 2009; Oishi, 2009). There, conservatism can be reduced
to any desired degree. On the other hand, the case of general nonlinear parameter dependence has notbeen considered so much except for a few works (Papachristodoulou & Prajna, 2005; Chesi & Hung,2008; Oishi & Fujioka, 2010).
∗†

March 30, 2011
Department of Systems Design and Engineering, Nanzan University, Seireicho 27, Seto 489-0863, Japan; email:oishi@nanzan-u.ac.jp‡
Departamento de Ingenierı́a de Sistemas y Automática, Universidad de Sevilla, Camino de los Descubrimientos s/n.
41092 Sevilla, Spain; email: alamo@cartuja.us.es

In this paper, we consider a robust SDP problem with general nonlinear parameter dependence andshow the usefulness of the, so-called, DC-representations, which will be explained later. Speciﬁcally, we
consider minimization of a linear objective function subject to an LMI constraint aﬃnely dependent on
q continuous nonlinear functions aj (θ), j = 1, 2, . . . , q, where θ is a p-dimensional uncertain parameter.
This constraint has to be satisﬁed for all θ in the set Θ, which is a p-dimensional closed convex polytope(i.e., bounded polyhedron) having a nonempty interior. (See Section 2.1 for the explicit form of the
problem.) One possible approach to this problem is to obtain upper and lower bounds, aj ≤ aj (θ) ≤ aj(θ ∈ Θ), for each j = 1, 2, . . . , q and to replace aj (θ) in the original LMI constraint either by aj or aj .
The resulting 2q LMIs constitute a suﬃcient condition for the original LMI constraint to be satisﬁed.
Hence, we can minimize the objective function subject to these LMIs and regard the obtained solution
as an approximate solution of the original problem. Now, we have two issues in this approach. First,
the upper and lower bounds on aj (θ) can be diﬃcult to ﬁnd. Second, this approach can be considerablyconservative because it uses constant bounds and neglects how aj (θ) depends on θ. (See Section 5 foran example.)In this paper, we would like to address these two issues using the DC-representations. Here,the letters “DC” mean the diﬀerence of two convex functions. We assume that each of the nonlinear functions aj (θ) is expressed as the diﬀerence of two convex functions. Then, we can compute
upper and lower bounds on aj (θ) with this representation. Furthermore, we can obtain parameterdependent bounds incorporating the parameter dependence of aj (θ). The constant bounds as well as
the parameter-dependent bounds form parameterized families and they can be optimized in some speciﬁc sense. Between these two types of bounds, the parameter-dependent bounds look better because
they can incorporate the parameter dependence of aj (θ) and they have computational advantage intheir optimization. The notion of the DC-representation has been utilized in the ﬁeld of optimization(Tuy, 1998; Horst & Thoai, 1999). Its application in control was considered by Tuan, Apkarian, Hosoe,
and Tuy (2000), Tuan, Hosoe, and Tuy (2000), Bravo, Alamo, Fiacchini, and Camacho (2007), andAlamo, Bravo, Redondo, and Camacho (2008).
The organization of the paper is as follows. In Section 2, the problem is presented and the notionof DC-representation is introduced. In Section 3, an approach with the constant bounds is presented.
In Section 4, an approach with the parameter-dependent bounds is presented and its advantage isdiscussed. Section 5 gives numerical examples and Section 6 concludes the paper.
The following notation is used. The symbol Rn stands for the set of n-dimensional real column
vectors. The symbol T expresses the transpose of a vector. The symbol I denotes the identity matrix
of appropriate size. For a symmetric matrix A, the inequality A º O means that A is positive
semideﬁnite. For a closed convex polytope Θ, the symbol ver Θ indicates the set of the vertices of Θ.
The number of the vertices is expressed by | ver Θ|.

2

2. Preparations
2.1. Problem to be considered
The problem to be considered in this paper is the following:P : minimize
subject to

cT x
F0 (x) +p
X

θi Fi (x) +

i=1

q
X

aj (θ)Fp+j (x) º O (∀θ ∈ Θ).

(1)

j=1

Here, x ∈ Rn is a design variable; c ∈ Rn is a given vector; Fi (x), i = 0, 1, . . . , p+q, are aﬃne functionsof x whose values are m × m symmetric matrices; θ = (θ1 θ2 · · · θp )T is an uncertain parametertaking the value in the parameter set Θ; Θ is a closed convex polytope in Rp having a nonempty
interior; aj (θ), j = 1, 2, . . . , q, are continuous nonlinear functions of θ ∈ Θ. This problem is diﬃcult tosolve because the constraint (1) has to be satisﬁed for all θ in Θ. If the nonlinear functions aj (θ) arepolynomial or rational, a suﬃcient condition can be obtained for (1) and can be used for approximate
solution of the problem P (El Ghaoui, et al., 1998; Bliman, 2004; Chesi, et al., 2005; Scherer, 2005;
Scherer & Hol, 2006; Peaucelle & Sato, 2009; Oishi, 2009). Hence, we are interested in the case thataj (θ) are not polynomial or rational though not restricted to the case.
As discussed in the introduction, a conservative approach is possible to the problem P if upperand lower bounds are available on aj (θ), j = 1, 2, . . . , q. To have these bounds, we use the DCrepresentation of aj (θ), which is explained next.

2.2. DC-representation
Let Θ be a closed convex polytope in Rp having a nonempty interior. A continuous function a(θ) on
Θ is said to have a DC-representation if it is expressed as the diﬀerence of two convex functions, thatis,a(θ) = b(θ) − c(θ) (θ ∈ Θ),
where b(θ) and c(θ) are convex functions on Θ.
Example 1. Suppose that a(θ) = sinh θ and Θ = [−1, 1]. Its DC-representation is given by b(θ) =eθ /2 and c(θ) = e−θ /2.
Suppose that a(θ) = sin θ and Θ = [−2, 2]. The second derivative of sin θ is larger than or equal to−1 on Θ, which implies the convexity of sin θ + θ2 /2 on Θ. Hence, b(θ) = sin θ + θ2 /2 and c(θ) = θ2 /2
3give the DC-representation.

Polynomials and rational functions have DC-representations if they are continuous on Θ. Anyfunction continuous on Θ can be approximated to any precision by a function possessing a DCrepresentation. Moreover, the second example above shows that an explicit DC-representation canbe obtained for a given function if a lower bound is known on its second derivative (or the Hessian
matrix in the case of p > 1). Computation of such a bound is discussed by Adjiman and Floudas
3b(θb f (θ))
b + f (θ)
b
λT (θ − θ)

Ã

λ

!

−1

f (θ)

fλ (θ)
θ

Figure 1. The graphs of f (θ) and fλ (θ)(1996). It is hence reasonably mild to assume the nonlinear functions aj (θ) in the problem P to have
known DC-representations. In the following sections, we are to consider the problem P under thisassumption.

3. Approach with constant bounds
We assume in the problem P that the nonlinear function aj (θ) has a known DC-representation
aj (θ) = bj (θ) − cj (θ) (θ ∈ Θ)for each j = 1, 2, . . . , q, where bj (θ) and cj (θ) are convex functions on Θ. We consider in this section
how to obtain upper and lower bounds on aj (θ) using its DC-representation. Once such bounds are
obtained, we can form a suﬃcient condition for the constraint (1) of the problem P and obtain an
approximate solution of P .
For preparation, let us consider in general a convex function f (θ) on Θ. For any λ ∈ Rp , we deﬁne
an aﬃne function in θ by£¤b .
fλ (θ) := λT θ − max λT θb − f (θ)

(2)

£
¤
b + f (θ)
b ,fλ (θ) = min λT (θ − θ)

(3)

b
θ∈Θ

Rewriting it asbθ∈Θ

we can see that the graph of this function forms the hyperplane having the normal vector (λT − 1)Tand supporting the graph of f (θ) from below (Figure 1). It is also seen that fλ (θ) ≤ f (θ) for anyθ ∈ Θ because the square bracket in (3) is equal to f (θ) with θb = θ. The function fλ (θ) is related tothe conjugate function of f (θ), which will be used later in Proposition 8.
The next proposition gives the desired bounds on aj (θ).
Proposition 2. For each j = 1, 2, . . . , q, set the values£¤
aj,λ := min bj,λ (θ) − cj (θ) ,£¤aj,µ := max bj (θ) − cj,µ (θ)θ∈ver Θθ∈ver Θwith λ and µ being any vectors in Rp . Then, they satisfy aj,λ ≤ aj (θ) ≤ aj,µ (θ ∈ Θ).

4(4)

Proof. The relation bj,λ (θ) ≤ bj (θ) implies aj (θ) ≥ bj,λ (θ) − cj (θ) ≥ minθ∈Θ [bj,λ (θ) − cj (θ)] for anyθ ∈ Θ. The function bj,λ (θ) − cj (θ) is concave because bj,λ (θ) is aﬃne and −cj (θ) is concave. Thisfunction hence attains the minimum at a vertex of Θ. This implies one of the desired inequalities,
aj,λ ≤ aj (θ). The remaining inequality aj (θ) ≤ aj,µ follows by similar reasoning.

¤

Computation of the bounds aj,λ and aj,µ is carried out as follows. For given λ and µ, we ﬁrst
obtain explicit forms of bj,λ (θ) and cj,µ (θ) following the deﬁnition (2). This can be performed throughb and µT θb − cj (θ),
b though it requires a numericalmaximization of the concave functions λT θb − bj (θ)
technique1 in general (e.g., Hiriart-Urruty & Lemaréchal, 1993; Bertsekas, 1999). Then, we carry out
minimization and maximization in (4) to obtain the bounds. This step requires only comparison of aﬁnite number of values.
Proposition 2 allows us to construct a suﬃcient condition for the constraint (1) of the problem P .
Let us choose the vectors λ(j) and µ(j) arbitrarily from Rp for each j = 1, 2, . . . , q and consider thefollowing condition on x ∈ Rn :F0 (x) +p
X
i=1

θi Fi (x) +qXαj Fp+j (x) º O

j=1(∀αj ∈ {aj,λ(j) , aj,µ(j) }, j = 1, 2, . . . , q; ∀θ ∈ ver Θ).

(5)Here, all the 2q assignments are considered for αj , j = 1, 2, . . . , q, and all the vertices of Θ areconsidered for θ.
Proposition 3. Let λ(j) and µ(j) be some vectors in Rp for each j = 1, 2, . . . , q. Then, for a givenx ∈ Rn , the condition (1) is satisﬁed if the condition (5) is satisﬁed.
Proof. Proposition 2 assures aj,λ(j) ≤ aj (θ) ≤ aj,µ(j) (θ ∈ Θ) for each j = 1, 2, . . . , q. Since thecondition (5) is convex in θi and αj , it implies the condition (1).

¤

We now have the following approach to the problem P . We replace the constraint (1) with its
suﬃcient condition (5) to have a standard SDP problem solvable with the interior-point method. The
optimal solution of this modiﬁed problem can be used as an approximate solution of P , though it
attains, in general, a larger value than the minimum of P . The condition (5) consists of 2q | ver Θ|
LMIs with | ver Θ| meaning the number of the vertices of Θ. Although this number becomes large fora large q, it may be reasonable for the NP-hard problem P .
The choice of the vectors λ(j) and µ(j) is arbitrary. It would be nice, however, if we can choose
optimal vectors. Speciﬁcally, the desired λ and µ would be such that maximize the lower bound aj,λand minimize the upper bound aj,µ , respectively. The result of Carrizosa (2001) is useful for thispurpose. (A related result can be found in Bravo, et al. (2007).) He showed that these maximization
1

Maximization is not necessary to have bj,λ (θ) if λ is known to be a subgradient of bj (θ) at some point θ0 ∈ Θ.

Indeed, in this case, we have bj,λ (θ) = λT (θ − θ0 ) + bj (θ0 ). The same comment applies to cj,µ (θ), too. This property
will be used in Proposition 8.

5

1.5

4

aµ

aµ
0

rµ (θ)rλ (θ)0a(θ)

rµ (θ)

a(θ)
−1.5
−1

rλ (θ)

aλ
0
θ
(a)

aλ
−4
−2

1

0
θ
(b)

2

Figure 2. The graphs of a(θ) and its bounds. (a) The case of a(θ) = sinh θ and Θ = [−1, 1]. The solidline stands for the original function a(θ); the broken lines stand for the constant bounds aλ and aµ ;the dash-dotted lines stand for the parameter-dependent bounds rλ (θ) and rµ (θ), to be introduced in
Section 4. (b) The case of a(θ) = sin θ and Θ = [−2, 2]. The usage of the lines is the same as in (a).
and minimization can be reduced to minimization of some convex functions. This minimization is
however not easy in general because the minimized functions do not have analytic expressions andmay not be diﬀerentiable at some points. On the other hand, in the special case that Θ is a simplex,
we can obtain the optimal λ and µ by solving linear equations. Indeed, λ is optimal when the valueof λT θ − cj (θ) is identical for all θ ∈ ver Θ. A similar property holds on the optimal µ but withµT θ − bj (θ) this time.
Example 4. We continue Example 1.
In the case that a(θ) = sinh θ and Θ = [−1, 1], the functions b(θ) = eθ /2 and c(θ) = e−θ /2 givethe DC-representation. Let us compute the optimal lower bound aλ . Since the parameter set Θ is a
simplex, the optimal λ can be obtained by solving λ · (−1) − c(−1) = λ · 1 − c(1), i.e., λ = 1/4e − e/4.
bWith this λ, we obtain the explicit expression of bλ (θ) = λθ − max b [λθb − b(θ)].
Diﬀerentiatingθ∈Θ

the function in the square bracket, we see that the maximum is attained at θb = −1, which givesbλ (θ) = λθ + λ + 1/2e. To compute aλ = minθ∈ver Θ [bλ (θ) − c(θ)], we evaluate bλ (θ) − c(θ) at θ = −1

and θ = 1. The two values are equal and give the desired optimal lower bound aλ = 1/2e − e/2. Thisbound is tight because a(θ) takes the same value at θ = −1. By symmetry, the optimal upper boundis aµ = e/2 − 1/2e, which is attained at µ = e/4 − 1/4e. Figure 2 (a) shows the obtained optimal
bounds aλ and aµ together with the original function a(θ). It conﬁrms the inequality aλ ≤ a(θ) ≤ aµ(θ ∈ Θ) and the tightness of the bounds. The ﬁgure also shows the parameter-dependent bounds, tobe discussed in the next section.
In the case that a(θ) = sin θ and Θ = [−2, 2], the functions b(θ) = sin θ + θ2 /2 and c(θ) =θ2 /2 give the DC-representation. The optimal lower bound aλ is computed similarly to the ﬁrst
example. In particular, we obtain the optimal λ as 0 by noticing that Θ is a simplex. Since bλ (θ) =− max b [− sin θb − θb2 /2], we carry out the numerical maximization to have the explicit expressionθ∈Θ

bλ (θ) ≈ −0.400. We then evaluate bλ (θ) − c(θ) at θ = −2 and θ = 2 and obtain the optimal lower
bound aλ ≈ −2.400. This bound is not tight. Computation of the optimal upper bound aµ is similar.
6

The result is aµ ≈ 2.103 for µ ≈ 0.455. This bound is not tight, either. Figure 2 (b) shows the bounds
3

in this case.

Our approach is conservative because the condition (5) is only suﬃcient for the original condition(1). This conservatism can be reduced by division of the parameter set Θ. Namely, we divide theparameter set Θ into a ﬁnite family of closed convex polytopes and consider a condition corresponding
to (5) for each subpolytope. It is also possible to make such division adaptively in order to suppress
the rapid increase of the number of subpolytopes. See Oishi (2009) and Oishi and Fujioka (2010) for
the details.

4. Approach with parameter-dependent bounds
The bounds in the previous section are constant in θ and neglect how the functions aj (θ) depend on θ.
They can give a considerably conservative result when incorporation of this dependence is importantfor solving P . In this section, we introduce parameter-dependent bounds using the DC-representationsof aj (θ). These bounds give another suﬃcient condition for the constraint (1) of the problem P . Using
this condition in the problem P , we have a solvable SDP problem, which gives an approximate solutionof P . We hence have another approach to the problem P .
The considered bounds are the following.
Proposition 5. For each j = 1, 2, . . . , q, deﬁne the functions on Θ as
rj,λ (θ) := bj,λ (θ) − cj (θ),

rj,µ (θ) := bj (θ) − cj,µ (θ)(6)

with λ and µ being any vectors in Rp . Then, rj,λ (θ) is concave and rj,µ (θ) is convex. Moreover, theysatisfyrj,λ (θ) ≤ aj (θ) ≤ rj,µ (θ)(θ ∈ Θ).

Proof. The concavity of rj,λ (θ) follows from the aﬃnity of bj,λ (θ) and the convexity of cj (θ). The
convexity of rj,µ (θ) follows similarly. The desired inequality is a consequence of bj,λ (θ) ≤ bj (θ) andcj,µ (θ) ≤ cj (θ).

¤

With the parameter-dependent bounds rj,λ (θ) and rj,µ (θ), we have the following suﬃcient condition
for (1). Let λ(j) and µ(j) be some vectors in Rp for each j = 1, 2, . . . , q. Then, for a given x ∈ Rn , weconsider the condition
F0 (x) +p
X
i=1

θi Fi (x) +qXρj (θ)Fp+j (x) º O

j=1(∀ρj ∈ {rj,λ(j) , rj,µ(j) }, j = 1, 2, . . . , q; ∀θ ∈ ver Θ).

(7)Here, ρj (θ) is a function chosen from the two candidate functions rj,λ(j) (θ) and rj,µ(j) (θ) for each j.
All the 2q choices are considered for ρj (θ), j = 1, 2, . . . , q, and all the vertices in ver Θ are consideredfor θ.
7

Proposition 6. For a given x ∈ Rn , the condition (1) is satisﬁed if the condition (7) is satisﬁed.
Proof. Let v be any nonzero vector in Rm . The proof is complete if we can show
v T F0 (x)v +pX

θi v T Fi (x)v +

i=1

q
X

aj (θ)v T Fp+j (x)v ≥ 0

(8)

j=1

for any θ ∈ Θ, which is the inequality (1) multiplied by v T and v. Toward this end, multiply v T andv to the assumption (7). Deﬁning©
ªfj (θ) := min rj,λ(j) (θ)v T Fp+j (x)v, rj,µ(j) (θ)v T Fp+j (x)v
for j = 1, 2, . . . , q, we havev T F0 (x)v +pX

θi v T Fi (x)v +

i=1

q
X

fj (θ) ≥ 0(θ ∈ ver Θ).

(9)

j=1

Pick up any j and suppose v T Fp+j (x)v ≥ 0. In this case, the function fj (θ) is equal to rj,λ(j) (θ)v T Fp+j (x)v,
which is concave in θ and less than or equal to aj (θ)v T Fp+j (x)v by Proposition 5. Repeating a similar
discussion in the case of v T Fp+j (x)v < 0, we see that, in any case, fj (θ) is concave and satisﬁes
aj (θ)v T Fp+j (x)v ≥ fj (θ)(θ ∈ Θ)(10)for each j. The concavity of fj (θ) implies that the inequality (9) holds for all θ ∈ Θ and the inequality(10) implies that the desired inequality (8) holds for all θ ∈ Θ. The proof is complete.

¤

In the present approach, the utilized suﬃcient condition (7) consists of 2q | ver Θ| LMIs. This
number is the same as the approach in the previous section. On the other hand, the present approachis less conservative than the previous one when the two approaches use the same λ(j) and µ(j) for
each j. This is shown by the next result.
Proposition 7. Let λ(j) and µ(j) be some vectors in Rp for each j = 1, 2, . . . , q. Then, the condition(7) is satisﬁed if the condition (5) is satisﬁed.
Proof. The claim follows if we haveaj,λ(j) ≤ rj,λ(j) (θ) (θ ∈ Θ),

rj,µ(j) (θ) ≤ aj,µ(j)(θ ∈ Θ)(11)for each j = 1, 2, . . . , q.
Recall that£¤£¤aj,λ(j) = min bj,λ(j) (θ) − cj (θ) = min bj,λ(j) (θ) − cj (θ) ,θ∈ver Θθ∈Θrj,λ(j) (θ) = bj,λ(j) (θ) − cj (θ).
Hence, the ﬁrst inequality in (11) follows immediately. The second inequality is similarly derived. ¤8

We next consider how the vectors λ(j) and µ(j) should be chosen for the parameter-dependent
bounds. One possibility is to use the λ and µ that optimize the constant bounds aj,λ and aj,µ .
Proposition 7 then guarantees a less conservative result for the parameter-dependent bounds. A
problem here is that computation of such λ and µ is not easy except for the special case that Θ is a
simplex. Even if such λ and µ are computed, we still need concave maximization to have the explicit
expressions of bj,λ (θ) and cj,µ (θ). It is also questionable if the optimality in this criterion really means
the goodness of the parameter-dependent bounds.
We here consider another criterion for the choice of λ and µ. It does not guarantee a less conservative result for the present approach in the sense of Proposition 7. It is however reasonable to use andconvenient to compute the corresponding bounds. In particular, we employ the following quantity asZa measure of conservatism:rj,µ (θ) − rj,λ (θ) dθVj (λ, µ) :=

(12)

Θ

and choose λ and µ so as to minimize this measure for each j. The measure Vj (λ, µ) stands for thevolume of the region sandwiched by the parameter-dependent bounds rj,λ (θ) and rj,µ (θ). Since we
use rj,λ (θ) and rj,µ (θ) to approximate aj (θ) in the present approach, it is reasonable to choose λ andµ so as to minimize Vj (λ, µ). Such λ and µ have the following simple characterization.
Proposition 8. For each j = 1, 2, . . . , q, the measure of conservatism, Vj (λ, µ) in (12), is minimized
if and only if λ and µ are subgradients of bj (θ) and cj (θ), respectively, at the gravity center of Θ, that
is,

R
θ dθ
θ := RΘ.
Θ dθcMoreover, for these λ and µ, the following relationships hold:bj,λ (θ) = λT (θ − θc ) + bj (θc ),cj,µ (θ) = µT (θ − θc ) + cj (θc ).

Proof. As noticed in the previous section, the functions bj,λ (θ) and cj,µ (θ), which are used in thedeﬁnitions of rj,λ (θ) and rj,µ (θ), are related to the notion of conjugate functions. Consider in generala convex function f (θ) on Θ. Then, its conjugate f ∗ (λ) is deﬁned as£¤f ∗ (λ) := max λT θ − f (θ)θ∈Θ

for λ ∈ Rp (e.g., Hiriart-Urruty & Lemaréchal, 1993; Bertsekas, Nedić, & Ozdaglar, 2003). The
conjugate function f ∗ (λ) is convex because it is the maximum of the family of aﬃne functions. With
this notion, we can write
rj,µ (θ) = bj (θ) − µT θ + c∗j (µ)

rj,λ (θ) = λT θ − b∗j (λ) − cj (θ),

for any j, λ, and µ. The measure of conservatism can be rewritten asZ£¤
Vj (λ, µ) =bj (θ) − µT θ + c∗j (µ) − λT θ + b∗j (λ) + cj (θ) dθ
Θ

9

Z

Z
bj (θ) + cj (θ) dθ − λ=ΘTθ dθ + b∗j (λ)

Zdθ − µΘΘZTΘθ dθ + c∗j (µ)

ZdθΘfor each j. This is minimized when both −λT θc + b∗j (λ) and −µT θc + c∗j (µ) are minimized. Let us
consider when the ﬁrst function, −λT θc + b∗j (λ), is minimized. Due to the convexity of this function,
it is minimized if and only if 0 is a subgradient of −λT θc + b∗j (λ) or, equivalently, θc is a subgradientof b∗j (λ). This occurs if and only if λ is a subgradient of bj (θc ) by a property of conjugate functions(Corollary X.1.4.4 of Hiriart-Urruty and Lemaréchal (1993)). Similar equivalence holds on the second
function.
Suppose that λ is a subgradient of bj (θ) at θ = θc . Then, the graph of λT (θ − θc ) + bj (θc ) gives a
hyperplane supporting the graph of bj (θ) from below. This means that this function is identical with¤

bj,λ (θ). Similar discussion is possible on cj,µ (θ).
Example 9. This is a continuation of Example 4.

We consider the ﬁrst example: a(θ) = sinh θ and Θ = [−1, 1]. The function b(θ) = eθ /2 is
diﬀerentiable at the gravity center θc = 0 and its gradient is 1/2 there. Hence, by Proposition 8,
λ = 1/2 is optimal and the corresponding bλ (θ) is λ(θ − θc ) + b(θc ) = θ/2 + 1/2. We thus obtain
the optimal lower bound rλ (θ) = θ/2 + 1/2 − e−θ /2. By symmetry, the optimal upper bound isrµ (θ) = eθ /2 + θ/2 − 1/2 for µ = −1/2. The obtained bounds are shown in Figure 2 (a). In alarge subset of Θ, they are closer to the original function a(θ) than the constant bounds aλ and aµ
considered in Example 4. It is seen however that aλ is closer to a(θ) than rλ (θ) around θ = −1 andthat aµ is closer than rµ (θ) around θ = 1. This is not surprising. Indeed, the uniform superiorityof the parameter-dependent bounds is not guaranteed in the sense of Proposition 7 because diﬀerent
values are used for λ and µ between the two types of bounds.
The procedure is the same for the second example: a(θ) = sin θ and Θ = [−2, 2]. The functionb(θ) = sin θ + θ2 /2 has the gradient 1 at the gravity center θc = 0. Hence, λ = 1 is optimal and thecorresponding bλ (θ) is λ(θ − θc ) + b(θc ) = θ. This gives the optimal lower bound rλ (θ) = θ − θ2 /2. On
the other hand, the function c(θ) = θ2 /2 has the gradient 0 at θc = 0. Hence, µ = 0 is optimal and thecorresponding cµ (θ) is µ(θ −θc )+c(θc ) = 0. The obtained optimal upper bound is rµ (θ) = sin θ +θ2 /2.
The obtained bounds are found in Figure 2 (b). The same comments apply on the comparison with3

the constant bounds.

When the gravity center θc is computable for Θ, the following approach is possible to the problem
P . For each j = 1, 2, . . . , q, we compute subgradients of bj (θ) and cj (θ) at θ = θc and choose them for
λ(j) and µ(j), respectively. Proposition 8 then guarantees their optimality with respect to Vj (λ, µ) andprovides the explicit expressions of bj,λ(j) (θ) and cj,µ(j) (θ). We obtain the optimal bounds rj,λ(j) (θ)
and rj,µ(j) (θ) with (6) and substitute them into the condition (7). Using this condition in place of (1),
we obtain an approximate problem of P , which is solvable with the interior-point method. If we want
to reduce the conservatism of the present approach, we can divide the parameter set Θ as in Section 3.
Computation of the gravity center θc is immediate when Θ is a simplex or a parallelepiped. In
many control problems, Θ is a hyperrectangle, which is a special parallelepiped. On the other hand,10the exact computation of θc is diﬃcult when Θ is a general polytope (Rademacher, 2007). A solution
would be approximate computation of θc with a randomized technique (e.g., Bertsimas & Vempala,2004).

5. Examples
We applied the proposed two approaches to three example problems. The ﬁrst two problems are on
random matrices and the last problem is on control system design. The proposed approaches worked
well for all the problems. In particular, they gave approximate solutions of the problems, whose
precision became better as the division of the parameter region became ﬁner.
Example 10. Set a(θ) = sinh θ and Θ = [−1, 1]. Let F be a 3 × 3 symmetric matrix whose elements
are randomly generated according to the standard normal distribution. We consider the problem:
minimizezsubject tozI − θ diag(x1 , x2 , x3 ) + a(θ)F º O(∀θ ∈ Θ),(13)

zI + θ diag(x1 , x2 , x3 ) − a(θ)F º O(∀θ ∈ Θ),(14)

with the real scalar design variables z, x1 , x2 , and x3 . Here, diag(x1 , x2 , x3 ) stands for the 3 × 3
diagonal matrix with the diagonal elements x1 , x2 , and x3 . In this problem, uniform approximationof a(θ)F is considered with θ diag(x1 , x2 , x3 ). Hence, it is important to take account of the parameter
dependence of a(θ).
For 100 randomly generated F , we applied our two approaches and obtained the approximate
solutions. Let zcons stand for the minimum given by the approach with the constant bounds; letzdep stand for the minimum given by the approach with the parameter-dependent bounds. These
are upper bounds on the true minimum of the problem. For reference, we also computed its lower
bound zsamp by minimizing z subject to the inequalities (13) and (14) but only for the 101 values of θ
equally spaced in Θ. The normalized approximation error for the approach with the constant bounds,
i.e., (zcons − zsamp )/zsamp , had the mean 0.96 and the standard deviation 1.81. On the other hand,the normalized approximation error for the approach with the parameter-dependent bounds, i.e.,(zdep − zsamp )/zsamp , had the mean 0.22 and the standard deviation 0.30. To summarize, the approachwith the parameter-dependent bounds gave better approximation on average. For some individual
instances of F , however, this approach was inferior to the other. This is not surprising because theoptimality of the parameter-dependent bounds does not imply the minimality of the approximation
error. The mean computational time was 0.15 s in the approach with the constant bounds and 0.22 s
in the approach with the parameter-dependent bounds. Here, the SDP problems were solved with
SeDuMi (Sturm, 1999) through the modeling language YALMIP (Löfberg, 2004) on the computerequipped with Intel Core 2 Duo P8800 (2.66 GHz) and the memory of 4 GB.
We were able to improve the result by dividing the parameter set Θ to the two intervals [−1, 0]
and [0, 1]. Indeed, for the same set of 100 matrices F , the mean of (zcons − zsamp )/zsamp was improved11

from 0.96 to 0.65 and the mean of (zdep − zsamp )/zsamp was improved from 0.22 to 0.031. The mean
computational time was a little longer: 0.24 s in the approach with the constant bounds and 0.34 s in3

the approach with the parameter-dependent bounds.

Example 11. We consider the same problem as the previous example for the same set of F but witha(θ) = sin θ and Θ = [−2, 2]. The result was more or less similar to the previous one. We ﬁrst applied
our approaches without dividing Θ. The mean of the normalized approximation error was 2.66 for theapproach with the constant bounds and 3.33 for the approach with the parameter-dependent bounds.
Although the result of the parameter-dependent approach was worse, the situation changed when Θwas divided into [−2, 0] and [0, 2]. Namely, the mean of the normalized error became 0.71 for theapproach with the constant bounds and 0.35 for the approach with the parameter-dependent bounds.
3
Example 12. We apply our approaches to design of a sampled-data control system with an uncertain
sampling interval. Consider a linear continuous-time plant (d/dt)x(t) = Ax(t) + Bu(t) with
Ã
A=

0

1

0 −0.1

!

Ã
,

B=

0

!
.

0.1

We would like to design a matrix K so that the sampled-data state-feedback control
u(t) = Kx(tk ) (tk ≤ t < tk+1 ; k = 0, 1, 2, . . .)stabilizes the plant, where t0 , t1 , t2 , . . . are sampling instants that satisfy 0 = t0 < t1 < t2 < · · · andlimk→∞ tk = ∞. We assume here that the sampling interval tk+1 −tk is uncertain and can vary with k,motivated by the need in the networked and embedded control. In particular, we consider the (rather
extreme) situation that tk+1 − tk can take any value in (0, 200] and look for a stabilizing K even inthis situation.
This type of control problems has been considered by several authors (e.g., Fridman, Seuret, &Richard, 2004; Hetel, Daafouz, & Iung, 2006; Mirkin, 2007; Naghshtabrizi, Hespanha, & Teel, 2008).
We here follow the approach of Oishi and Fujioka (2010) and reduce the problem to a robust SDP
problem:minimizezsubject to

Q − I º O,
(the formula (15) at the bottom of this page)

with Θ := [0, 200] andÃ−E(θ)(AQ + BL) − (AQ + BL)T E(θ)T + zI√
θ(AQ + BL)T E(θ)T

12

√

!
θE(θ)(AQ + BL)
QºO(θ ∈ Θ)(15)

1
E(θ) :=
θÃZ θ
eAt dt =
0

1 −10
0

1

!Ã
1
0

0
e−0.1θ −1
−0.1θ

!Ã
!
1 10
0

1

.

We deﬁne E(θ) = I at θ = 0. In this problem, the design variables are a scalar z, a 2 × 2 symmetricmatrix Q, and a 1 × 2 matrix L. If a feasible solution (z, Q, L) such that z < 0 is found for thisproblem, a stabilizing state-feedback gain K is obtained by LQ−1 .
√Let us set a1 (θ) = θ and a2 (θ) = (e−0.1θ − 1)/(−0.1θ). We deﬁne a2 (θ) = 1 at θ = 0. We ﬁrst
notice that the constraint of the problem includes the product a1 (θ)a2 (θ). To remove this product,
we apply the technique of Oishi (2009) and Oishi and Isaka (2009). Then, we can obtain a suﬃcientcondition, which is aﬃne in a1 (θ) and a2 (θ). Replacing the constraint by this suﬃcient condition, we
can apply our approaches. We choose b1 (θ) and c2 (θ) to be zero noting the concavity of a1 (θ) and theconvexity of a2 (θ), respectively.
The obtained minimum was 1.75 × 10−5 in the approach with the constant bounds and 3.87 × 10−4in the approach with the parameter-dependent bounds. This means that both approaches failed togive a stabilizing state-feedback gain. The situation changed when Θ was divided into two subintervals[0, 100] and [100, 200]. Indeed, with both approaches, a feasible solution with a negative z was found,which gave a stabilizing state-feedback gain. The computational time in this case was 1.65 s in theapproach with the constant bounds and 4.85 s in the approach with the parameter-dependent bounds.
Oishi and Fujioka (2010) gave an approach specialized for analysis and design of this type ofsampled-data control systems. The performance of our present approaches were comparable to thisspecialized approach. Indeed, the specialized approach failed to give a state-feedback gain when Θ
was not divided. It failed again with the division consisting of [0, 100] and [100, 200]. After some trials
and errors, it succeeded with the division consisting of [0, 25] and [25, 200]. The computational timein the last case was 0.39 s, which was short due to specialization.

3

6. Conclusion
Two conservative approaches are proposed for robust SDP problems with general nonlinear parameter
dependence. The ﬁrst approach is based on the computation of constant bounds for each nonlinear
function. It is conceptually simple but has a computational issue in the optimization of the bounds.
The second approach is based on the computation of parameter-dependent bounds. It has a potential
to give a less conservative result by exploiting the parameter dependence of the problem. It also
has a computational advantage when the gravity center is computable for the parameter set. Bothapproaches rely on the assumption that the nonlinear parameter dependence is expressed as thediﬀerence of two convex functions. Since this assumption is mild enough, the proposed approaches
can be applied to a large class of problems.
Some extensions are possible with the present approaches. We saw in Example 12 that, even if theoriginal constraint includes the product a1 (θ)a2 (θ), we can apply our approaches with the help of theexisting result. This technique can be generalized to the case that the constraint includes polynomial13

or rational functions of aj (θ) (Peaucelle & Sato, 2009; Oishi, 2009; Oishi & Isaka, 2009). On the other
hand, by mimicing the approach of Chesi and Hung (2008), it is possible to expand aj (θ) to the ﬁnite
Taylor series and compute the proposed bounds for the remainder term. This technique can reduce
conservatism when the remainder term is smaller than the original function aj (θ).

Acknowledgments
The authors are thankful to Fabrizio Dabbene, Yoshio Ebihara, Dimitri Peaucelle, and Roberto Tempo
for their valuable comments. This work is supported in part by the Grant-in-Aid for Scientiﬁc Researchof the Japan Society for the Promotion of Science and the Nanzan University Pache Research Subsidy
I-A-2 for the academic year 2010. This work is performed during the sabbatical stay of the ﬁrst author
at the MAC group, LAAS-CNRS, Toulouse, France.

References
Adjiman, C. S., & Floudas, C. A. (1996). Rigorous convex underestimators for general twice-diﬀerentiableproblems. Journal of Global Optimization, 9 (1), 23–40.
Alamo, T., Bravo, J. M., Redondo, M. J., & Camacho, E. F. (2008). A set-membership state estimation
algorithm based on DC programming. Automatica, 44 (1), 216–224.
Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust Optimization. Princeton, USA: Princeton University Press.
Ben-Tal, A., & Nemirovski, A. (1998). Robust convex optimization. Mathematics of Operations Research, 23(4), 769–805.
Ben-Tal, A., & Nemirovski, A. (2001). Lectures on Modern Convex Optimization: Analysis, Algorithms, andEngineering Applications. Philadelphia, USA: SIAM.
Bertsekas, D. P. (1999). Nonlinear Programming, 2nd ed. Belmont, USA: Athena Scientiﬁc.
Bertsekas, D. P., Nedić, A., & Ozdaglar, A. E. (2003). Convex Analysis and Optimization. Belmont, USA:
Athena Scientiﬁc.
Bertsimas, D., & Vempala, S. (2004). Solving convex programs by random walks. Journal of the ACM, 51 (4),
540–556.
Bliman, P.-A. (2004). On robust semideﬁnite programming. In Proceedings of the 16th International Symposiumon Mathematical Theory of Networks and Systems (MTNS 2004), Leuven, Belgium.
Bravo, J. M., Alamo, T., Fiacchini, M., & Camacho, E. F. (2007). A convex approximation of the feasible
solution set for nonlinear bounded-error identiﬁcation problems. In Proceedings of the 46th IEEE Conferenceon Decision and Control, New Orleans, USA (pp. 5743–5748).
Carrizosa, E. (2001). An optimal bound for d.c. programs with convex constraints. Mathematical Methods ofOperations Research, 54 (1), 47–51.

14

Chesi, G., Garulli, A., Tesi, A., & Vicino, A. (2005). Polynomially parameter-dependent Lyapunov functions
for robust stability of polytopic systems: an LMI approach. IEEE Transactions on Automatic Control, 50(3), 365–370.
Chesi, G., & Hung, Y. S. (2008). Analysis and synthesis of nonlinear systems with uncertain initial conditions.
IEEE Transactions on Automatic Control, 53 (5), 1262–1267.
El Ghaoui, L., Oustry, F., & Lebret, H. (1998). Robust solutions to uncertain semideﬁnite programs. SIAM
Journal on Optimization, 9 (1), 33–52.
Fridman, E., Seuret, A., & Richard, J.-P. (2004). Robust sampled-data stabilization of linear systems: an input
delay approach. Automatica, 40 (8), 1441–1446.
Hetel, L., Daafouz, J., & Iung, C. (2006). Stabilization of arbitrary switched linear systems with unknown
time-varying delays. IEEE Transactions on Automatic Control, 51 (10), 1668–1674.
Hiriart-Urruty, J.-B., & Lemaréchal, C. (1993). Convex Analysis and Minimization Algorithms. Berlin, Germany:
Springer.
Horst, R., & Thoai, N. V. (1999). DC programming: overview. Journal of Optimization Theory and Applications,
103 (1), 1–43.
Löfberg, J. (2004), YALMIP: a toolbox for modeling and optimization in MATLAB. In Proceedings of the
CACSD Conference, Taipei, Taiwan. Available from http://users.isy.liu.se/johanl/yalmip/
Mirkin, L. (2007). Some remarks on the use of time-varying delay to model sample-and-hold circuits. IEEE
Transactions on Automatic Control, 52 (6), 1109–1112.
Naghshtabrizi, P., Hespanha, J. P., & Teel, A. R. (2008). Exponential stability of impulsive systems withapplication to uncertain sampled-data systems. Systems & Control Letters, 57 (5), 378–385.
Nemirovskii, A. (1993). Several NP-hard problems arising in robust stability analysis. Mathematics of Control,
Signals, and Systems, 6 (2), 99–105.
Oishi, Y. (2009). An asymptotically exact approach to robust semideﬁnite programming problems with function
variables. IEEE Transactions on Automatic Control, 54 (5), 1000–1006.
Oishi, Y., & Fujioka, H. (2010). Stability and stabilization of aperiodic sampled-data control systems using
robust linear matrix inequalities. Automatica, 46 (8), 1327–1333.
Oishi, Y., & Isaka, Y. (2009). Exploiting sparsity in the matrix-dilation approach to robust semideﬁnite programming. Journal of the Operations Research Society of Japan, 52 (3), 321–338.
Papachristodoulou, A., & Prajna, S. (2005). Analysis of non-polynomial systems using the sum of squares
decomposition. In D. Henrion & A. Garulli (Eds.), Positive Polynomials in Control (pp. 23–43). Berlin,
Germany: Springer.
Peaucelle, D., & Sato, M. (2009). LMI tests for positive deﬁnite polynomials: slack variable approach. IEEE
Transactions on Automatic Control, 54 (4), 886–891.

15

Rademacher, L. (2007). Approximating the centroid is hard. In Proceedings of the 24th Annual Symposium on
Computational Geometry, Gyeongju, South Korea.
Scherer, C. W. (2005). Relaxations for robust linear matrix inequality problems with veriﬁcations for exactness.
SIAM Journal on Matrix Analysis and Applications, 27 (2), 365–395.
Scherer, C. W. (2006). LMI relaxations in robust control. European Journal of Control, 12 (1), 3–29.
Scherer, C. W., & Hol, C. W. J. (2006). Matrix sum-of-squares relaxations for robust semi-deﬁnite programs.
Mathematical Programming, 107 (1–2), 189–211.
Sturm, J. F. (1999). Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optimization Methods and Software, 11–12, 625–653. Available from http://sedumi.ie.lehigh.edu/
Tuan, H. D., Apkarian, P., Hosoe, S., & Tuy, H. (2000). D.C. optimization approach to robust control: feasibility
problems. International Journal of Control, 73 (2), 89–104.
Tuan, H. D., Hosoe, S., & Tuy, H. (2000). DC optimization approach to robust controls: the optimal scaling
value problem. IEEE Transactions on Automatic Control, 45 (10), 1903–1909.
Tuy, H. (1998). Convex Analysis and Global Optimization. Dordrecht, The Netherlands: Kluwer Academic
Publishers.

16