Semidefinite programming reformulation for a class of robust optimization problems and its application to robust Nash equilibrium problems

Semidefinite programming reformulation for a class of robust optimization problems

and its application to robust Nash equilibrium problems

Guidance

Assistant Professor Shunsuke HAYASHI Professor Masao FUKUSHIMA

Ryoichi NISHIMURA

Department of Applied Mathematics and Physics Graduate School of Informatics

Kyoto University

KYOTO UNIVER SIT

Y

F OU

ND E D 1897 KYOTO JAPAN

February 2009

Abstract

In a real situation, optimization problems often involve uncertain parameters. Robust optimization is one of distribution-free methodologies based on worst-case analyses for handling such problems.

In the model, we first assume that the uncertain parameters belong to some uncertainty sets. Then we deal with the robust counterpart associated with the uncertain optimization problem. The robust optimization problem is in its original form a semi-infinite program. Under some assumptions, it can be reformulated as an efficiently solvable problem, such as a semidefinite program (SDP) or a second-order cone program (SOCP). During the last decade, not only has robust optimization made significant progress in theory, but it has been applied to a large number of problems in various fields.

Game theory is one of such fields. For non-cooperative games with uncertain parameters, several researchers have proposed a model in which each player makes a decision according to the robust optimization policy. The resulting equilibrium is called a robust Nash equilibrium, and the problem of finding such an equilibrium is called the robust Nash equilibrium problem. It is known that the robust Nash equilibrium problem can be reformulated as a second-order cone complementarity problem under certain assumptions.

In this paper, we focus on a class of uncertain linear programs. We reformulate the robust counterpart as an SDP and show that those problems are equivalent under the spherical uncertainty assumption. In the reformulation, the strong duality for nonconvex quadratic programs plays a significant role. Also, by using the same technique, we reformulate the robust counterpart of an uncertain SOCP as an SDP under some assumptions. Furthermore, we apply this idea to the robust Nash equilibrium problem.

Under mild assumptions, we show that each player’s optimization problem can be rewritten as an SDP and the robust Nash equilibrium problem reduces to a semidefinite complementarity problem (SDCP).

We finally give some numerical results to show that those SDP and SDCP are efficiently solvable.

Contents

1 Introduction 1

2 Strong duality in nonconvex quadratic optimization with two quadratic constraints 3 3 SDP reformulation for a class of robust linear programming problems 5 4 Robust second-order cone programming problems with ellipsoidal uncertainty 12 5 SDCP reformulation of robust Nash equilibrium problems 16 5.1 Robust Nash equilibrium and its existence . . . . 16 5.2 SDCP reformulation of robust Nash equilibrium problems . . . . 18

6 Numerical experiments 22

6.1 Robust second-order cone programming problems . . . . 22 6.2 Robust Nash equilibrium problems . . . . 27

7 Concluding remarks 29

1 Introduction

In constructing a mathematical model from a real-world problem, we cannot always determine the objective function or the constraint functions precisely. For example, when parameters in the functions are obtained in a statistical or simulative manner, they usually involve uncertainty (e.g. statistical error, etc.) to some extent. To deal with such situations, we need to incorporate the uncertain data in a mathematical model.

Generally, the mathematical programming problem with uncertain data is expressed as follows:

minimize

x f 0 ( x , u )

subject to f i (x , u) ∈ K i , (i = 1, . . . , m) (1.1) where x ∈ R ⁿ is the decision variable, u ∈ R ^d is the uncertain data, f 0 : R ⁿ × R ^d → R and f i : R ⁿ × R ^d → R ^k

(i = 1, . . . , m) are given functions, and K i ⊆ R ^k

(i = 1, . . . , m) are given nonempty sets. Since problem (1.1) cannot be defined uniquely due to u, it is difficult to handle in a straightforward manner.

Robust optimization [13] is one of distribution-free methodologies for handling the mathematical programming problem with uncertain data. In robust optimization, the uncertain data are assumed to belong to some set U ⊆ R ^d , and then, the objective function is minimized (or maximized) with taking the worst possible case into consideration. That is, the following robust counterpart is solved instead of the original problem (1.1):

minimize

x sup _{u∈ U} f 0 ( x , u )

subject to f i (x , u) ∈ K i , (i = 1, . . . , m), ∀u ∈ U . (1.2) Recently, robust optimization has been studied by many researchers. Ben-Tal and Nemirovski [9, 10, 12], Ben-Tal, Nemirovski and Roos [14], and El Ghaoui, Oustry and Lebret [21] showed that certain classes of robust optimization problems can be reformulated as efficiently solvable problems such as a semidefinite program (SDP) [36] or a second-order cone program (SOCP) [3] under the assumptions that uncertainty set is ellipsoidal and functions f i ( i = 0 , 1 , . . . , m ) in the problem (1.2) are expressed as

f i ( x , u ) = g i ( x ) + F i ( x ) u

with g i : R ⁿ → R ^k

and F i : R ⁿ → R ^k

^×d . El Ghaoui and Lebret [19] showed that the robust least-squares problem can be reformulated as an SOCP. Bertsimas and Sim [16] gave another robust formulation and some properties of the solution. Also, the robust optimization techniques have been applied to many practical problems such as portfolio selection [7, 20, 23, 29, 30, 39], classification problem [38], structural design [8] and inventory management problem [1, 17].

On the other hand, in game theory, there have been a large number of studies on games with un-

certain data. Among them, the new concept of robust Nash equilibrium attracts attention recently.

Hayashi, Yamashita and Fukushima [26], and Aghassi and Bertsimas [2] ^*1 have proposed the model in which each player makes a decision according to the idea of robust optimization. Aghassi et al. [2]

considered the robust Nash equilibrium for N -person games in which each player solves a linear pro- gramming (LP) problem. Moreover, they proposed a method for solving the robust Nash equilibrium problem with convex polyhedral uncertainty sets. Hayashi et al. [26] defined the concept of robust Nash equilibria for bimatrix games. Under the assumption that uncertainty sets are expressed by means of the Euclidean or the Frobenius norm, they showed that each player’s problem reduces to an SOCP and the robust Nash equilibrium problem can be reformulated as a second-order cone comple- mentarity problem (SOCCP) [22, 25]. In addition, Hayashi et al. [26] studied robust Nash equilibrium problems in which the uncertainty is contained in both opponents’ strategies and each player’s cost parameters, whereas Aghassi et al. [2] studied only the latter case. More recently, Nishimura, Hayashi and Fukushima [33] extended the definition of robust Nash equilibria in [2] and [26] to the N -person non-cooperative games with nonlinear cost functions. In particular, they showed existence of robust Nash equilibria under the milder assumptions and gave some sufficient conditions for uniqueness of the robust Nash equilibrium. In addition, they reformulated certain classes of robust Nash equilibrium problems to SOCCPs. However, Hayashi et al. [26] and Nishimura et al. [33] have only dealt with the case where the uncertainty is contained in either opponents’ strategies or each player’s cost parameters, in reformulating the robust Nash equilibrium problem as an SOCCP.

In this paper, we first focus on a special class of linear programs (LPs) with uncertain data. To such a problem, we apply the strong duality in nonconvex quadratic optimization problems with two quadratic constrains studied by Beck and Eldar [5], and reformulate its robust counterpart as an SDP.

Especially, when the uncertainty sets are spherical, we further show that those two problems are equiv- alent. Also, by using the same technique, we reformulate the robust counterpart of SOCP with un- certain data as an SDP. In this reformulation, we emphasize that the uncertainty set is different from what was considered by Ben-Tal et al. [14]. We apply these ideas to game theory, too. Particularly, we show that the robust Nash equilibrium problem in which uncertainty is contained in both opponents’

strategies and each player’s cost parameters can be reduced to a semidefinite complementarity prob- lem (SDCP) [18, 37]. Finally, we give some numerical results to see that those SDP and SDCP are efficiently solvable.

This paper is organized as follows. In Section 2, we review the strong duality in nonconvex quadratic optimization problems with two quadratic constraints, which plays a key role in the SDP reformulation of the robust counterpart. In Section 3, we reformulate the robust counterpart of some LP with uncertain data as an SDP. In Section 4, we reformulate the robust counterpart of SOCP with uncertain data as an SDP. In Section 5, we first formulate the robust Nash equilibrium problem, and show that it reduces to an SDCP under appropriate assumptions. In Section 6, we give some numerical

*1

In [2] a robust Nash equilibrium is called a robust-optimization equilibrium.

results to show the validity of our reformulation and the behavior of obtained solutions.

Throughout the paper, we use the following notations. For a set X , P( X) denotes the set consisting of all subsets of X . R ⁿ ₊ denotes the nonnegative orthant in R ⁿ , that is, R ⁿ ₊ := {x ∈ R ⁿ | x i ≥ 0 ( i = 1 , . . . , n )} . S ⁿ denotes the set of n × n real symmetric matrices. S ₊ ⁿ denotes the cone of positive semidefinite matrices in S ⁿ . For a vector x ∈ R ⁿ , ∥ x ∥ denotes the Euclidean norm defined by ∥ x ∥ : = √

x ^⊤ x . For a matrix M = ( M i j ) ∈ R ^{m × n} , ∥ M ∥ F is the Frobenius norm defined by

∥M∥ F := ( ∑ _m

i = 1

∑ _n

j = 1 (M i j ) ² ) ^{1 / 2} , ∥M∥ 2 is the ` 2 -norm defined by ∥M∥ 2 := max _x̸=0 ∥M x∥/∥x ∥, and ker M denotes the kernel of matrix M, i.e., ker M := { x ∈ R ⁿ | M x = 0}. B(x , r ) denotes the closed sphere with center x and radius r , i.e., B ( x , r ) : = { y ∈ R ⁿ | ∥ y − x ∥ ≤ r } . For a problem (P), val ( P ) denotes the optimal value.

2 Strong duality in nonconvex quadratic optimization with two quadratic constraints

In this section, we study the duality theory in nonconvex quadratic programming problems with two quadratic constrains. This concept plays a significant role in reformulating the robust optimization problem as an SDP. Especially, we give sufficient conditions, shown by Beck and Eldar [5], under which there exists no duality gap.

We consider the following optimization problem:

( QP ) minimize f 0 ( x )

subject to f 1 (x) ≥ 0, f 2 (x ) ≥ 0, (2.1) where f j ( j = 0, 1, 2) are defined by f j (x) := x ^⊤ A j x + 2b j ⊤ x + c j with symmetric matrices A j ∈ R ^n×n , b j ∈ R ⁿ , and c j ∈ R .

We first consider the Lagrangian dual problem to QP (2.1). The Lagrangian function L for QP (2.1) is defined by

L ( x , α, β) = {

x ^⊤ A 0 x + 2b ^⊤ ₀ x + c 0 − α( x ^⊤ A 1 x + 2b ₁ ^⊤ x + c 1 ) − β( x ^⊤ A 2 x + 2b ^⊤ ₂ x + c 2 ), α, β ≥ 0

−∞, otherwise

with Lagrange multipliers α and β . By introducing an auxiliary variable λ ∈ R ∪ {−∞} , we have

α,β≥0 sup inf

x∈ R

L ( x , α, β)

= sup

α,β≥ 0 ,λ

{ λ | L(x, α, β) ≥ λ, ∀x ∈ R ⁿ }

= sup

α,β≥ 0 ,λ

{ λ

[ x

1 ] _⊤ ([

A 0 b 0

b ₀ ^⊤ c 0 − λ ]

− α

[ A 1 b 1

b ^⊤ ₁ c 1

]

− β

[ A 2 b 2

b ^⊤ ₂ c 2

]) [ x 1 ]

≥ 0 , ∀ x ∈ R ⁿ }

= sup

α,β≥ 0 ,λ

{ λ

[

A 0 b 0

b ^⊤ ₀ c 0 − λ ]

− α

[ A 1 b 1

b ^⊤ ₁ c 1

]

− β

[ A 2 b 2

b ^⊤ ₂ c 2

]

≽ 0 }

.

Hence, the Lagrangian dual problem to (QP) is written as

(D)

maximize

α,β,λ λ

subject to

[ A 0 b 0

b ^⊤ ₀ c 0 − λ ]

≽ α

[ A 1 b 1

b ^⊤ ₁ c 1

] + β

[ A 2 b 2

b ^⊤ ₂ c 2

] α ≥ 0, β ≥ 0, λ ∈ R.

(2.2)

Since (D) is an SDP, its dual problem is

(SDR)

minimize tr( M 0 X) subject to tr ( M 1 X ) ≥ 0

tr( M 2 X) ≥ 0 X n + 1 , n + 1 = 1 , X ≽ 0 ,

(2.3)

where

M j =

[ A j b j

b ^⊤ _j c j

]

( j = 0 , 1 , 2 ).

Now let χ( x ) be a rank-one semidefinite symmetric matrix defined by χ( x ) : = ( _x

1

)( _x

1

) _⊤

. Then we have f j ( x ) = ( _x

1

) _⊤ M j

( _x

1

) = tr ( M j χ( x )) for j = 0 , 1 , 2. Thus problem (2.1) is rewritten as minimize tr ( M 0 χ( x ))

subject to tr( M 1 χ(x )) ≥ 0 tr ( M 2 χ( x )) ≥ 0 .

(2.4) Actually, problem (2.3) can be seen as a relaxation of problem (2.4) since the rank-one condition on χ(x ) is removed. In other words, problem (2.3) is the so-called semidefinite relaxation [11] of (2.4) ． From the above argument, we have val ( QP ) ≤ val ( SDR ) . Hence, by using the weak duality theorem, we have

val (QP) ≤ val (SDR) ≤ val (D).

Finally, we study the strong duality. Beck and Eldar [5] considered a nonconvex quadratic opti- mization problem in the complex space and its dual problem, and showed that they have zero duality gap under strict feasibility and boundedness assumptions. Furthermore, they extended the idea to the nonconvex quadratic optimization problem in the real space, and provided sufficient conditions for zero duality gap among (QP), (D) and (SDR).

Theorem 2.1. [5, Theorem 3.5] Suppose that both (QP) and (D) are strictly feasible and that

∃ ˆ α, β ˆ ∈ R such that α ˆ A 1 + ˆ β A 2 ≻ 0 . Let ( λ, ¯ α, ¯ β) ¯ be an optimal solution of the dual problem (D). If

dim ( ker ( A 0 − ¯ α A 1 − ¯ β A 2 )) ̸= 1 ,

then val ( QP ) = val ( D ) = val ( SDR ) .

3 SDP reformulation for a class of robust linear programming problems

In this section, we focus on the following uncertain LP:

minimize

x ( γ ˆ ⁰ ) ^⊤ ( A ˆ ⁰ x + ˆ b ⁰ )

subject to ( γ ˆ ⁱ ) ^⊤ ( A ˆ ⁱ x + ˆ b ⁱ ) ≤ 0 ( i = 1 , . . . , K ) x ∈ ,

(3.1)

where  is a given closed convex set with no uncertainty. Let U i and V i be the uncertainty sets for ˆ

γ ⁱ ∈ R ^m

and ( A ˆ ⁱ , b ˆ ⁱ ) ∈ R ^m

^{×( n + 1 )} , respectively. Then, the robust counterpart (RC) for (3.1) can be written as

minimize

x sup

( A ˆ

, b ˆ

)∈ U

, γ ˆ

∈ V

( γ ˆ ⁰ ) ^⊤ ( A ˆ ⁰ x + ˆ b ⁰ )

subject to ( γ ˆ ⁱ ) ^⊤ ( A ˆ ⁱ x + ˆ b ⁱ ) ≤ 0 ∀( A ˆ ⁱ , b ˆ ⁱ ) ∈ U i , ∀ ˆ γ ⁱ ∈ V i (i = 1, . . . , K ) x ∈ .

(3.2)

The main purpose of this section is to show that RC (3.2) can be reformulated as an SDP [36], which can be solved by existing algorithms such as the primal-dual interior-point method. One may think that the structures of LP (3.1) and its RC (3.2) are much more special than the existing robust optimization models for LP [10]. However, we note that the robust optimization technique in this section plays an important role in considering the robust SOCPs and the robust Nash equilibrium problems in the subsequent sections. We also note that the uncertain LP (3.1) is equivalent to the LP considered by Ben-Tal et. al [10, 11], when V i is a finite set given by V i : = { e ₁ ^(m

⁾ , . . . , e ^(m _m

⁾ } where e ^(m _k

⁾ is a unit vector with 1 at k-th element and 0 elsewhere.

We first make the following assumptions in the uncertainty sets U i and V i : Assumption 1. For i = 0, 1, . . . , K , the uncertainty sets U i and V i are expressed as

U i :=

 

 ( A ˆ ⁱ , b ˆ ⁱ ) ( A ˆ ⁱ , b ˆ ⁱ ) = (A ^{i 0} , b ⁱ⁰ ) +

s

∑

j =1

u ⁱ _j ( A ^{i j} , b ^{i j} ), (u ⁱ ) ^⊤ u ⁱ ≤ 1

 

 ,

V i : =

 

 γ ˆ γ ˆ = γ ⁱ⁰ +

t

∑

j = 1

v ⁱ _j γ ^{i j} , (v ⁱ ) ^⊤ v ⁱ ≤ 1

 

 ,

respectively, where A ^{i j} ∈ R ^m

^{× n} , b ^{i j} ∈ R ^m

( j = 0, 1, . . . , s i ) and γ ^{i j} ∈ R ^m

( j = 1, . . . , t i ) are given matrices and vectors.

Moreover, we introduce the following proposition, which plays a crucial role in reformulating RC

(3.2) to an SDP.

Proposition 3.1. Consider the following optimization problem:

maximize

u∈ R

_{, v∈} R

ξ(v) ^⊤ M ( u )η

subject to u ^⊤ u ≤ 1 , v ^⊤ v ≤ 1 , (3.3)

where η ∈ R ⁿ is a given constant, and M : R ^s → R ^{m × n} and ξ : R ^t → R ^m are defined by M ( u ) = M ⁰ +

∑ s j = 1

u j M ^j , ξ(v) = ξ ⁰ +

∑ t j = 1

v j ξ ^j (3.4)

with given constants M ^j ∈ R ^m×n ( j = 0 , 1 , . . . , s ) and ξ ^j ∈ R ^m ( j = 0 , 1 , . . . , t ) . Then, the following two statements hold:

(a) The Lagrangian dual problem of (3.3) is written as minimize

α,β,λ − λ

subject to

[ P 0 q q ^⊤ r − λ

]

≽ α

[ P ₁ 0

0 1

] + β

[ P ₂ 0

0 1

] , α ≥ 0 , β ≥ 0 , λ ∈ R

(3.5)

with

P 0 = − 1 2

[ 0 (4 ^⊤ 8) ^⊤

4 ^⊤ 8 0

]

, q = − 1 2

[ 8 ^⊤ ξ ⁰ 4 ^⊤ M ⁰ η

] , r = −(ξ ⁰ ) ^⊤ M ⁰ η P 1 =

[ − I s 0

0 0

]

, P 2 =

[ 0 0 0 − I t

] , 4 = [

ξ ¹ · · · ξ ^t ]

, 8 = [

M ¹ η · · · M ^t η ] .

(3.6)

Moreover, it always holds that val(3.3) ≤ val(3.5).

(b) If

dim(ker( P 0 − α ^∗ P 1 − β ^∗ P 2 )) ̸= 1 (3.7) for the optimum (α ^∗ , β ^∗ , λ ^∗ ) of the dual problem (3.5), then it holds that val ( 3 . 3 ) = val ( 3 . 5 ) . Proof. From the definition of M(u) and ξ(v), the objective function of problem (3.3) can be rewritten as

ξ(v) ^⊤ M(u)η = (ξ ⁰ + 4v) ^⊤ ( M ⁰ η + 8u)

= v ^⊤ 4 ^⊤ 8 u + (ξ ⁰ ) ^⊤ 8 u + ( M ⁰ η) ^⊤ 4v + (ξ ⁰ ) ^⊤ M ⁰ η

= − y ^⊤ P 0 y − 2q ^⊤ y − r, where y : = ( _u

v

) . Hence, problem (3.3) is equivalent to the following optimization problem:

maximize

y ∈ R

− y ^⊤ P 0 y − 2q ^⊤ y − r

subject to y ^⊤ P ₁ y + 1 ≥ 0 , y ^⊤ P ₂ y + 1 ≥ 0 . (3.8)

Now, notice that problem (3.8) is a nonconvex quadratic optimization problem with two quadratic constrains since P 0 is indefinite in general. Hence, from the results stated in Section 2, problem (3.5) serves as the Lagrangian dual problem of (3.3).

Next we show (b). From Theorem 2.1, it suffices to show that the following three statements hold:

(i) Both problems (3.3) and (3.5) are strictly feasible.

(ii) There exist α ˆ ∈ R and β ˆ ∈ R such that α ˆ P ₁ + ˆ β P ₂ ≻ O.

(iii) dim(ker(P 0 − α ^∗ P 1 − β ^∗ P 2 )) ̸= 1 for the optimum (α ^∗ , β ^∗ , λ ^∗ ) of problem (3.5).

Problem (3.3) is obviously strictly feasible since ( u , v) = ( 0 , 0 ) is an interior point of the feasible region. Also, problem (3.5) is strictly feasible since the inequalities in the constrains hold strictly when we choose sufficiently large α, β , and sufficiently small λ . Thus, we have (i). We can readily see (ii) since α ˆ P ₁ + ˆ β P ₂ ≻ 0 for any α, ˆ β ˆ such that α, ˆ β < ˆ 0. We also have (iii) from the assumption of the theorem. Hence, the optimal values of (3.3) and (3.5) are equal.

Next, by using the above proposition, we reformulate RC (3.2) as an SDP. Note that RC (3.2) is rewritten as the following optimization problem:

minimize

x f 0 (x ) := max

( A ˆ

, b ˆ

)∈ U

, γ ˆ

∈ V

( γ ˆ ⁰ ) ^⊤ ( A ˆ ⁰ x + ˆ b ⁰ )

subject to f i ( x ) : = max { ( γ ˆ ⁱ ) ^⊤ ( A ˆ ⁱ x + ˆ b ⁱ ) | ( A ˆ ⁱ , b ˆ ⁱ ) ∈ U i , γ ˆ ⁱ ∈ V i } ≤ 0 (i = 1, . . . , K ),

x ∈ .

(3.9)

Now for any fixed x ∈ R ⁿ , we evaluate max { ( γ ˆ ⁱ ) ^⊤ ( A ˆ ⁱ x + ˆ b ⁱ ) | ( A ˆ ⁱ , b ˆ ⁱ ) ∈ U i , γ ˆ ⁱ ∈ V i } for i = 0 , 1 , . . . , K . By letting η : = ( _x

1

) , M ^j = ( A ^{i j} , b ⁱ ) , and ξ ^j : = γ ^{i j} in Proposition 3.1, we have the following inequality for each i = 0, 1, . . . , K :

max { ( γ ˆ ⁱ ) ^⊤ ( A ˆ ⁱ x + ˆ b ⁱ ) | ( A ˆ ⁱ , b ˆ ⁱ ) ∈ U i , γ ˆ ⁱ ∈ V i }

≤ min

 

 −λ i

[ P ₀ ⁱ ( x ) q ⁱ ( x ) q ⁱ ( x ) ^⊤ r ⁱ ( x ) − λ i

]

≽ α i

[ P ₁ ⁱ 0

0 1

] + β i

[ P ₂ ⁱ 0

0 1

] α i ≥ 0 , β i ≥ 0 , λ i ∈ R

 

 , (3.10) where P ₀ ⁱ (x ), q ⁱ (x) and r ⁱ (x ) are defined by

P ₀ ⁱ ( x ) = − 1 2

[ 0 (0 _i ^⊤ 8 i ( x )) ^⊤ 0 _i ^⊤ 8 i ( x ) 0

]

, q ⁱ ( x ) = − 1 2

[ 8 i ( x ) ^⊤ γ ⁱ 0 _i ^⊤ ( A ⁱ⁰ x + b ^{i 0} )

] , r ⁱ (x ) = −(γ ⁱ ) ^⊤ (A ⁱ⁰ x + b ^{i 0} ), P ₁ ⁱ =

[ −I s

0

0 0

]

, P ₂ ⁱ =

[ 0 0 0 − I t

] , 0 i = [

γ ^{i 1} · · · γ ^{i t} ]

, 8 i ( x ) = [

A ⁱ¹ x + b ^{i 1} · · · A ^{i s}

x + b ^{i s}

] .

(3.11)

Moreover, we consider the following problem in which max { ( γ ˆ ⁱ ) ^⊤ ( A ˆ ⁱ x + ˆ b ⁱ ) | ( A ˆ ⁱ , b ˆ ⁱ ) ∈ U i , γ ˆ ⁱ ∈ V i }

in (3.9) is replaced by the right-hand side of (3.10):

minimize

x g 0 (x ) := min

 

 −λ 0

[ P ₀ ⁰ ( x ) q ⁰ ( x ) q ⁰ ( x ) ^⊤ r ⁰ ( x ) − λ 0

]

≽ α 0

[ P ₁ ⁰ 0

0 1

] + β i

[ P ₂ ⁰ 0

0 1

] α 0 ≥ 0 , β 0 ≥ 0 , λ 0 ∈ R

 

 subject to g i (x ) := min

 

 −λ i

[ P ₀ ⁱ ( x ) q ⁱ ( x ) q ⁱ ( x ) ^⊤ r ⁱ ( x ) − λ i

]

≽ α i

[ P ₁ ⁱ 0

0 1

] + β i

[ P ₂ ⁱ 0

0 1

] α i ≥ 0, β i ≥ 0, λ i ∈ R

 

 ≤ 0 (i = 1, . . . , K ),

x ∈ ,

(3.12) which is equivalent to the following SDP:

minimize

x ,α,β,λ − λ 0

subject to

[ P ₀ ⁱ ( x ) q ⁱ ( x ) q ⁱ ( x ) ^⊤ r ⁱ ( x ) − λ i

]

≽ α i

[ P ₁ ⁱ 0

0 1

] + β i

[ P ₂ ⁱ 0

0 1

]

( i = 0 , 1 , . . . , K ), α = (α 0 , α 1 , . . . , α K ) ∈ R ₊ ^{K + 1} , β = (β 0 , β 1 , . . . , β K ) ∈ R ₊ ^{K + 1} , λ = (λ 0 , λ 1 , . . . , λ K ) ∈ R × R ₊ ^K ,

x ∈ .

(3.13)

Here, notice that, if the matrix inequalities in (3.13) hold with some λ i ≥ 0 ( i = 1 , . . . , K ) , then they also hold for λ i = 0. Hence, we can set λ i = 0 ( i = 1 , . . . , K ) without changing the optimal value of (3.13). That is, SDP (3.13) is equivalent to the following SDP:

minimize

x ,α,β,λ

− λ 0

subject to

[ P ₀ ⁰ ( x ) q ⁰ ( x ) q ⁰ ( x ) ^⊤ r ⁰ ( x ) − λ 0

]

≽ α 0

[ P ₁ ⁰ 0

0 1

] + β 0

[ P ₂ ⁰ 0

0 1

] , [ P ₀ ⁱ ( x ) q ⁱ ( x )

q ⁱ (x ) ^⊤ r ⁱ (x ) ]

≽ α i

[ P ₁ ⁱ 0

0 1

] + β i

[ P ₂ ⁱ 0

0 1

]

( i = 1 , . . . , K ), α = (α 0 , α 1 , . . . , α K ) ∈ R ₊ ^{K + 1} , β = (β 0 , β 1 , . . . , β K ) ∈ R ₊ ^{K + 1} , λ 0 ∈ R, x ∈ .

(3.14)

Consequently, we have val (3.9) ≤ val (3.12) = val (3.13) = val (3.14) where the inequality is due to f i ( x ) ≤ g i ( x ) for any x ∈ R ⁿ and i = 0 , 1 , . . . , K . Moreover, we can show val (3.9) = val (3.12), under the following assumption.

Assumption 2. Let z ^∗ : = ( x ^∗ , α ^∗ , β ^∗ , λ ^∗ ₀ ) be an optimum of SDP (3.14). Then, there exists ε > 0 such that

dim ( ker ( P ₀ ⁱ ( x ) − α i P ₁ ⁱ − β i P ₂ ⁱ )) ̸= 1 ( i = 0 , 1 , . . . , K )

for all (x, α, β, λ ^∗ ₀ ) ∈ B(z ^∗ , ε).

Theorem 3.2. Suppose that Assumption 1 holds, and ( x ^∗ , α ^∗ , β ^∗ , λ ^∗ ₀ ) be the optimum of SDP (3.14), then x ^∗ is feasible in RC (3.2) and val (3.14) is an upper bound of val (3.2). Moreover, x ^∗ solves RC (3.2) if Assumption 2 further holds.

Proof. Since the first part is trivial from f i (x ) ≤ g i (x ) for any x ∈ R ⁿ and i = 0, 1, . . . , K , we only show the last part.

Define X , Y ⊆ R ⁿ and θ, ω : R ⁿ → (−∞, ∞ ] by

X = { x ∈ R ⁿ | f i ( x ) ≤ 0 ( i = 1 , . . . , K )} ∩ , Y = {x ∈ R ⁿ | g i (x ) ≤ 0 (i = 1, . . . , K )} ∩ , θ( x ) = f ₀ ( x ) + δ X ( x ),

ω( x ) = g 0 ( x ) + δ Y ( x ),

where δ X and δ Y denote the indicator functions [34] of X and Y , respectively. Then, we can see that RC(3.2) and SDP(3.14) are equivalent to the unconstrained minimization problems with objective functions θ and ω, respectively. In addition, since functions f i , g i (i = 0, 1, . . . , K ) are proper and convex [15, Proposition 1.2.4(c)], θ and ω are proper and convex, too.

Let ( x ^∗ , α ^∗ , β ^∗ , λ ^∗ ₀ ) be an arbitrary solution to SDP (3.14). Then, it is obvious that x ^∗ minimizes ω . Moreover, from Proposition 3.1(b) and Assumption 2, there exists a closed neighborhood B ( x ^∗ , ε) of x ^∗ such that θ(x ) = ω(x ) for all x ∈ B(x ^∗ , ε). Hence, we have

θ(x ^∗ ) = ω(x ^∗ ) ≤ ω(x ) = θ(x ), ∀x ∈ B(x ^∗ , ε). (3.15) Now, for contradiction, assume that x ^∗ is not a solution to RC(3.2). Then, there must exist x ¯ ∈ R ⁿ such that θ( x ¯ ) < θ( x ^∗ ) . Moreover, we have x ¯ ̸∈ B ( x ^∗ , ε) from (3.15). Set α : = ε/∥ ¯ x − x ^∗ ∥ and

˜

x : = ( 1 − α) x ^∗ + α x ¯ . Then, α ∈ ( 0 , 1 ) since x ¯ ̸∈ B ( x ^∗ , ε) , i.e., ∥ ¯ x − x ^∗ ∥ > ε . Thus, we have θ( x ˜ ) = θ(( 1 − α) x ^∗ + α x ¯ )

≤ ( 1 − α)θ( x ^∗ ) + αθ( x ¯ )

< ( 1 − α)θ( x ^∗ ) + αθ( x ^∗ ) = θ( x ^∗ ),

where the first inequality follows from the convexity of θ , and the last inequality follows from θ( x ¯ ) <

θ(x ^∗ ) and α > 0. However, since ∥ ˜ x − x ^∗ ∥ = α∥ ¯ x − x ^∗ ∥ = ε, we have x ˜ ∈ B(x ^∗ , ε), which implies θ( x ^∗ ) ≤ θ( x ˜ ) from (3.15). Hence, x ^∗ is an optimum of RC (3.2).

In order to see whether Assumption 2 holds or not, we generally have to check every function value in the neighborhood of the optimum. However, in some situations, it can be guaranteed more easily.

For example, suppose that at the optimum z ^∗ = ( x ^∗ , α ^∗ , β ^∗ , λ ^∗ ₀ ) ,

dim ( ker ( P ₀ ⁱ ( x ^∗ ) − α i ^∗ P ₁ ⁱ − β i ^∗ P ₂ ⁱ )) = 0 ( i = 0 , 1 , . . . , K ),

equivalently P ₀ ⁱ ( x ^∗ ) − α _i ^∗ P ₁ ⁱ − β _i ^∗ P ₂ ⁱ ≻ 0 ^*2 . Then, by the continuity of P ₀ ⁱ ( x ) − α i P ₁ ⁱ − β i P ₂ ⁱ , it also follows P ₀ ⁱ (x ) − α i P ₁ ⁱ − β i P ₂ ⁱ ≻ 0 for any z sufficiently close to z ^∗ .

Moreover, when the uncertainty sets U i and V i are spherical, Assumption 2 also holds automati- cally. We will show this fact in the remainder of this section.

Assumption 3. Suppose that Assumption 1 holds. Moreover, for each i = 0 , 1 , . . . , K , matrices ( A ^{i j} , b ^{i j} ) ( j = 1 , . . . , m i ( n + 1 )) and vectors γ ^{i j} ( j = 1 , . . . , t i ) ( t i ≥ 2 ) satisfy the following.

• For ( k , l ) ∈ { 1 , . . . , m _i } × { 1 , . . . , n + 1 } ,

( A ^{i j} , b ^{i j} ) = ρ i e ^(m _k

⁾ ( e _l ⁽ⁿ⁺¹⁾ ) ^⊤ with j : = m i l + k ,

where ρ i is a given nonnegative constant, and e ⁽ r ^{p )} is a unit vector with 1 at r -th element and 0 elsewhere.

• For any ( k , l ) ∈ { 1 , . . . , t i } × { 1 , . . . , t i } ,

(γ ^{i k} ) ^⊤ γ ^il = σ _i ² δ kl ,

where σ i is a given nonnegative constant, and δ kl denotes Kronecker’s delta, i.e., δ kl = 0 for k ̸= l and δ kl = 1 for k = l.

Assumption 3 claims that U i is an m i (n + 1)-dimensional sphere with radius ρ i in the m i (n + 1)- dimensional space and V i is a t i -dimensional sphere with radius σ i in the m i -dimensional space, i.e.,

U i = { ( A ˆ ⁱ , b ˆ ⁱ ) | ( A ˆ ⁱ , b ˆ ⁱ ) = ( A ^{i 0} , b ^{i 0} ) + (δ A ⁱ , δ b ⁱ ), ∥(δ A ⁱ , δ b ⁱ )∥ F ≤ ρ i } ⊂ R ^m

^{( n + 1 )} , V i = { ˆ γ ⁱ | ˆ γ ⁱ = γ ^{i 0} + δγ ⁱ , ∥δγ ⁱ ∥ ≤ σ i , δγ ⁱ ∈ span { γ ^{i j} } ^t _j

₌₁ } ⊂ R ^m

.

The following proposition provides sufficient conditions under which condition (3.7) in Proposition 3.1 holds. It also plays an important role in showing that Assumption 3 implies Assumption 2.

Proposition 3.3. Consider the optimization problem (3.3) with a given constant η ∈ R ⁿ and functions M : R ^s → R ^{m × n} and ξ : R ^t → R ^m defined by (3.4). Moreover, suppose that there exist nonnegative constants ρ and σ such that the following statements hold.

• t , n ≥ 2.

• s = m ( m + 1 ) . Moreover, M ^j ( j = 1 , . . . , s ) are given by

M ^j = ρ e ^(m) _k ( e _l ⁽ⁿ⁾ ) ^⊤ with j : = ml + k , for each k = 1, . . . , m and l = 1, . . . , n.

• For any ( k , l ) ∈ { 1 , . . . , t } × { 1 , . . . , t } , (ξ ^k ) ^⊤ ξ ^l = σ ² δ kl .

*2

By the constraints of SDP (3.14), P

( x

) − α

P

− β

P

≽ 0 always holds at the optimum ( x

, α

, β

, λ

, ) .

Then, for P ₀ , P ₁ and P ₂ defined by (3.6), it holds that

dim ( ker ( P 0 − α P 1 − β P 2 )) ̸= 1 for any (α, β) ∈ R × R , and hence val (3.3) = val (3.5).

Proof. Let P (α, β) : = P 0 − α P 1 − β P 2 . Then, since P (α, β) is symmetric, it suffices to show that the multiplicity of zero eigenvalues of P (α, β) can never be 1.

We first define matrices 4 and 8 by (3.6). By Assumption 3, we have the following equalities:

4 ^⊤ 4 = [

ξ ¹ · · · ξ ^t ] _⊤ [

ξ ¹ · · · ξ ^t ]

= σ ² I , 8 = [

M ¹ η · · · M ^t η ]

= ρ [

e ₁ ^(m) ( e ⁽ⁿ⁾ ₁ ) ^⊤ η e ^(m) ₂ ( e ⁽ⁿ⁾ ₁ ) ^⊤ η · · · e ^(m) _m ( e ⁽ⁿ⁾ _n ) ^⊤ η ]

= ρ [[

η 1 e ₁ ^(m) η 1 e ^(m) ₂ · · · η 1 e _m ^(m)

] · · · [

η n e ^(m) ₁ η n e ^(m) ₂ · · · η n e ^(m) _m ]]

= ρ [

η 1 I m · · · η n I m

] .

Therefore,

4 ^⊤ 88 ^⊤ 4 = 4 ^⊤ (ρ ² ∥η∥ ² I m )4

= ρ ² σ ² ∥η∥ ² I t .

Now we consider the eigenvalue equation det ( P (α, β) − ζ I ) = 0. If ζ ̸= α , then we have det ( P (α, β) − ζ I ) = det

([ (α − ζ) I _mn − ¹ ₂ (4 ^⊤ 8) ^⊤

− ¹ ₂ 4 ^⊤ 8 (β − ζ) I _t ])

= det [(α − ζ)I mn ] · det [

(β − ζ ) I t − 1

4 (α − ζ ) 4 ^⊤ 88 ^⊤ 4 ]

= (α − ζ) ^{mn − t} det [(

(α − ζ)(β − ζ) − 1

4 ρσ ∥η∥ ² )

I _t ]

= (α − ζ) ^{mn − t} (

(α − ζ)(β − ζ ) − 1

4 ρσ ∥η∥ ² ) t

, (3.16)

where the second equality follows from the Schur complement [24, Theorem 13.3.8]. Moreover, since det(P(α, β) − ζ I ) is continuous at any (α, β, ζ), equality (3.16) is valid at ζ = α ^*3 . Since we have mn − t ≥ 2 from t , n ≥ 2 and t ≤ m, (3.16) indicates that the multiplicity of all eigenvalues of P (α, β) is greater than 2. Hence, even if P (α, β) has zero eigenvalue, the multiplicity cannot be 1.

By the above proposition, we obtain the following theorem.

Theorem 3.4. Suppose Assumption 3 holds. Then, x ^∗ solves RC (3.2) if and only if there exists (α ^∗ , β ^∗ , λ ^∗ ₀ ) such that ( x ^∗ , α ^∗ , β ^∗ , λ ^∗ ₀ ) is an optimal solution of SDP (3.14).

*3

From the continuity, we have lim

det ( P (α, β) − ˜ ζ I ) = det ( P (α, β) − α I )

Proof. In a way similar to the proof of Theorem 3.2, we evaluate max { ( γ ˆ ⁱ ) ^⊤ ( A ˆ ⁱ x + ˆ b ⁱ ) | ( A ˆ ⁱ , b ˆ ⁱ ) ∈ U i , γ ˆ ⁱ ∈ V i } for each i = 0, 1, . . . , K , in (3.9). In Proposition 3.3, let η := ( _x

1

) and M ^j := (A ^{i j} , b ^{i j} ), and ξ ^j := γ ^{i j} . Then, for all x ∈ R ⁿ and α, β ∈ R, we can see that

dim ( ker ( P ₀ ⁱ ( x ) − α i P ₁ ⁱ − β i P ₂ ⁱ )) ̸= 1 , ( i = 0 , 1 , . . . , K ).

From Proposition 3.1, we have f i (x ) = g i (x ) for all x ∈ R ⁿ . Hence, problems (3.9) is identical to (3.12). This completes the proof.

In Theorem 3.2, the optimality of SDP (3.14) is nothing more than a sufficient condition for the optimality of RC (3.2) under appropriate assumptions. However, Theorem 3.4 shows not only the sufficiency but also the necessity. This is due to the fact that Assumption 3 guarantees f i ( x ) = g i ( x ) for all x ∈ R ⁿ , though Assumption 2 guarantees it only in a neighborhood of the SDP solution.

4 Robust second-order cone programming problems with ellipsoidal uncertainty

The second-order cone programming problem (SOCP) is expressed as follows:

minimize

x f ^⊤ x

subject to M ⁱ x + q ⁱ ∈ K ⁿ

( i = 1 , . . . , K ), x ∈ ,

(4.1)

where K ⁿ

denotes the n i -dimensional second-order cone defined by K ⁿ

:= {(x 0 , x ¯ ^⊤ ) ^⊤ ∈ R×R ⁿ

^{− 1} | x 0 ≤ ∥ ¯ x∥} and  is a given closed convex set. SOCP is applicable to many practical problems such as the antenna array weight design problems and the truss design problems [3, 31]. We note that the second-order cone constraints M ⁱ x + q ⁱ ∈ K ⁿ

( i = 1 , . . . , K ) in (4.1) are rewritten as

∥ A ⁱ x + b ⁱ ∥ ≤ ( c ⁱ ) ^⊤ x + d ⁱ with M ⁱ = ( _{( c}

₎

A

) and q ⁱ = ( _d

b

) . In this section, we consider the following uncertain SOCP:

minimize

x f ^⊤ x

subject to ∥ ˆ A ⁱ x + ˆ b ⁱ ∥ ≤ ( c ˆ ⁱ ) ^⊤ x + ˆ d ⁱ ( i = 1 , . . . , K ), x ∈ ,

(4.2)

where A ˆ ⁱ ∈ R ^m

^{× n} , b ˆ ⁱ ∈ R ^m

, c ˆ ⁱ ∈ R ⁿ and d ˆ ⁱ ∈ R are uncertain data with uncertainty set U i . Then, the robust counterpart (RC) for (4.2) can be written as

minimize

x f ^⊤ x

subject to ∥ ˆ A ⁱ x + ˆ b ⁱ ∥ ≤ ( c ˆ ⁱ ) ^⊤ x + ˆ d ⁱ , ∀( A ˆ ⁱ , b ˆ ⁱ , c ˆ ⁱ , d ˆ ⁱ ) ∈ U i , ( i = 1 , . . . , K ),

x ∈ .

(4.3)

Throughout this section, we assume m _i ≥ 2 for all i = 1 , . . . , K ^*4 ．

Ben-Tal and Nemirovski [9] showed that RC (4.3) can be reformulated as an SDP in the case where the uncertainty sets for ( A ˆ ⁱ , b ˆ ⁱ ) and ( c ˆ ⁱ , d ˆ ⁱ ) are independent and can be represented with two ellipsoids as

U L

= { ( A ˆ ⁱ , b ˆ ⁱ ) | ( A ˆ ⁱ , b ˆ ⁱ ) = ( A ^{i 0} , b ^{i 0} ) +

∑ l j = 1

u ⁱ _j ( A ^{i j} , b ^{i j} ), ( u ⁱ ) ^⊤ u ⁱ ≤ 1 }, U R

= { ( c ˆ ⁱ , d ˆ ⁱ ) | ( c ˆ ⁱ , d ˆ ⁱ ) = ( c ⁱ⁰ , d ⁱ⁰ ) +

∑ r j = 1

v ⁱ _j ( c ^{i j} , d ^{i j} ), (v ⁱ ) ^⊤ v ⁱ ≤ 1 },

with given constants A ^{i j} , b ^{i j} , c ^{i j} and d ^{i j} . However, according to Ben-Tal and Nemirovski [13], it was an open problem until quite recently whether or not RC (4.3) can be reformulated as an SDP under the following assumption (one ellipsoid case).

Assumption 4. The uncertainty sets U i (i = 1, . . . , K ) in RC (4.3) are given by U i =

 



[ A ˆ ⁱ b ˆ ⁱ ( c ˆ ⁱ ) ^⊤ d ˆ ⁱ

] [ A ˆ ⁱ b ˆ ⁱ ( c ˆ ⁱ ) ^⊤ d ˆ ⁱ ]

=

[ A ^{i 0} b ⁱ⁰ ( c ^{i 0} ) ^⊤ d ^{i 0} ]

+

s

∑

j =1

u ⁱ _j

[ A ^{i j} b ^{i j} (c ^{i j} ) ^⊤ d ^{i j} ]

, (u ⁱ ) ^⊤ u ⁱ ≤ 1

 

 , where A ^{i j} , b ^{i j} , c ^{i j} and d ^{i j} ( i = 1 , . . . , K , j = 0 , 1 , . . . , s i ) are given constants.

In this section, we show that the robust counterpart can be reformulated as an explicit SDP under this assumption, using the results in the previous section ^*5 .

We first rewrite RC (4.2) in the form RC (3.1). To this end, we introduce the following result in semi-infinite programming [32, Section 4].

Proposition 4.1. Let A ∈ R ^m×n , b ∈ R ^m , c ∈ R ⁿ and d ∈ R be given. Then x ∈ R ⁿ satisfies the inequality ∥ Ax + b ∥ ≤ c ^⊤ x + d if and only if x satisfies γ ˜ ^⊤ ( Ax + b ) ≤ c ^⊤ x + d for all γ ˜ ∈ R ^m such that ∥ ˜ γ ∥ ≤ 1.

*4

If m

= 1 for some i, then the constraint can be rewritten as two linear inequalities −(ˆ c

)

x + ˆ d

≤ ˆ A

x + ˆ b

≤ (ˆ c

)

x + ˆ d

. So existing frameworks can be applied. (See Ben-Tal and Nemirovski [10]).

*5

Fairly recently, it has been shown that another SDP reformulation is possible by Hildebrand’s Lorentz-positivity re-

sults [27, 28]. However, our approach has an advantage in terms of computational complexity. We state the details at the

end of this section.

By this proposition, RC (4.3) can be rewritten as follows:

minimize

x f ^⊤ x

subject to ( γ ˆ ⁱ ) ^⊤

([ A ˆ ⁱ

−( c ˆ ⁱ ) ^⊤ ]

x + [ b ˆ ⁱ

− ˆ d ⁱ ])

≤ 0,

∀( A ˆ ⁱ , b ˆ ⁱ , c ˆ ⁱ , d ˆ ⁱ ) ∈ U i , ∀ ˆ γ ⁱ ∈ V i := {

(( γ ˜ ⁱ ) ^⊤ , 1) ^⊤ ∥ ˜ γ ⁱ ∥ ≤ 1 } ( i = 1 , . . . , K ),

x ∈ .

(4.4)

Clearly, problem (4.4) belongs to the class of problems of the form RC (3.2). In addition, when As- sumption 4 holds, Assumption 1 also holds by setting V i : = { ˆ γ ⁱ | ˆ γ ⁱ = γ ^{i 0} + ∑ m

j = 1 v ⁱ _j γ ^{i j} , (v ⁱ ) ^⊤ v ⁱ ≤ 1} with γ ^{i 0} = e _m ^{( m}

^{+ 1 )}

i

+1 , γ ^{i j} = e ⁽ _j ^m

⁾ ( j = 1, . . . , m i ). Thus, we have the following theorem, whose proof is omitted since it readily follows from Theorem 3.2.

Theorem 4.2. Suppose that Assumption 4 holds. Let (x ^∗ , α ^∗ , β ^∗ ) be an optimal solution of the fol- lowing SDP:

minimize

x ,α,β f ^⊤ x

subject to

[ P ₀ ⁱ (x) q ⁱ (x) q ⁱ (x) ^⊤ r ⁱ (x) ]

≽ α i

[ P ₁ ⁱ 0

0 1

] + β i

[ P ₂ ⁱ 0

0 1

]

( i = 1 , . . . , K ), α = (α 1 , . . . , α K ) ∈ R ₊ ^K , β = (β 1 , . . . , β K ) ∈ R ₊ ^K ,

x ∈ ,

(4.5)

where

P ₀ ⁱ ( x ) = − 1 2

[ 0 9 i ( x ) ^⊤ 9 i ( x ) 0

]

, q ⁱ ( x ) = − 1 2

[ −ψ i (x ) A ^{i 0} x + b ⁱ⁰

] , r ⁱ ( x ) = ( c ^{i 0} ) ^⊤ x + d ^{i 0} , P ₁ ⁱ =

[ − I s

0

0 0

]

, P ₂ ⁱ =

[ 0 0 0 − I m

− 1

] , ψ i ( x ) = [

( c ⁱ¹ ) ^⊤ x + d ⁱ¹ · · · ( c ^{i s}

) ^⊤ x + d ^{i s}

] _⊤ , 9 i (x ) = [

A ^{i 1} x + b ^{i 1} · · · A ^{i s}

x + b ^{i s}

] .

(4.6)

Then, x ^∗ solves RC (4.3) if

dim(ker( P ₀ ⁱ (x ) − α i P ₁ ⁱ − β i P ₂ ⁱ )) ̸= 1 (i = 0, 1, . . . , K ) (4.7) in an neighborhood of (x ^∗ , α ^∗ , β ^∗ ).

We can easily see that condition (4.7) is guaranteed to hold if

P ₀ ⁱ ( x ^∗ ) − α i ^∗ P ₁ ⁱ − β i ^∗ P ₂ ⁱ ≻ 0 , (4.8)

by using similar arguments to those just after Theorem 3.2. Also when the uncertainty sets are spheri-

cal, condition (4.7) is satisfied and hence the following theorem holds.