Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets.
Let F be a compact subset of the n-dimensional Euclidean space Rn represented by (finitely or infinitely many) quadratic inequalities. We propose two methods, one based on successive semidefinite programming (SDP) relaxations and the other on successive linear programming (LP) relaxations. Each of our methods generates a sequence of compact convex subsets Ck . .) of Rn such that   (a) the convex hull of $F \subseteq C_{k+1} \subseteq C_k$ (monotonicity),  (b)  $\cap_{k=1}^{\infty} C_k = \text{the convex hull of  F (asymptotic convergence).   Our methods are extensions of the corresponding Lovsz--Schrijver lift-and-project procedures with the use of SDP or LP relaxation applied to general quadratic optimization problems (QOPs) with infinitely many quadratic inequality constraints. Utilizing descriptions of sets based on cones of matrices and their duals, we establish the exact equivalence of the SDP relaxation and the semi-infinite convex QOP relaxation proposed originally by Fujie and Kojima. Using this equivalence, we investigate some fundamental features of the two methods including (a) and (b) above.
Introduction
. Consider a maximization problem with a linear objective function
c T x:
maximize c T x subject to x # F,
where c denotes a constant vector in the n-dimensional Euclidean space R n and
F a subset of R n . We can reduce a more general maximization problem with a
nonlinear objective function f(x) to a maximization problem having a linear objective
function represented by a new variable, x n+1 , if we replace f(x) by x n+1 and then
add the inequality f(x) # x n+1 to the constraint. Thus (1.1) covers such a general
optimization problem. Throughout the paper we assume that F is compact. Then
the problem (1.1) has a global maximizer whenever the feasible region F is nonempty.
For any compact convex set C containing F , the maximization problem
maximize c T x subject to x # C
serves as a convex relaxation problem, which satisfies the properties that
(i) the maximum objective value # of the problem (1.2) gives an upper bound
for the maximum objective value # of the problem (1.1), i.e., # , and
# Received by the editors March 31, 1998; accepted for publication (in revised form) July 19, 1999;
published electronically March 21, 2000.
http://www.siam.org/journals/siopt/10-3/33645.html
Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, 2-12-1
Oh-Okayama, Meguro-ku, Tokyo 152-8552, Japan (kojima@is.titech.ac.jp).
# Department of Combinatorics and Optimization, Faculty of Mathematics, University of Water-
loo, Waterloo, Ontario N2L 3G1, Canada (ltuncel@math.uwaterloo.ca). This work was completed
while this author was visiting Tokyo Institute of Technology, Department of Mathematical and Computing
Sciences, on a sabbatical leave from University of Waterloo. The research of this author was
supported in part by Tokyo Institute of Technology and by a research grant from NSERC of Canada.
(ii) if a maximizer -
lies in F , it is a maximizer of (1.1).
Since the objective function of (1.1) is linear, we know that if we take the convex hull
(defined as the intersection of all the convex sets containing F ) for C in
(1.2), then
(ii) # the set of the maximizers of (1.2) forms a compact convex set whose extreme
points are maximizers of (1.1).
Therefore, if we solve the relaxation problem (1.2) with a convex feasible region C
which closely approximates c.hull(F ), we can expect to get not only a good upper
bound # for the maximum objective value # but also an approximate maximizer of
the problem (1.1). We can further prove that for almost every c # R n (in the sense of
any maximizer x # of (1.2) is an extreme point of c.hull(F ),
which also lies in F ; hence x # is a maximizer of (1.1). This follows from a result due
to Ewald, Larman, and Rogers [5] for consequences of related results; see also [17].
Furthermore, for many representations of various convex sets C, given - x # C, we can
very e#ciently find x # , an extreme point of C, such that c T x # c T - x.
Indeed, the relaxation technique mentioned above has been playing an essential
role in practical computational methods for solving various problems in the fields of
combinatorial optimization and global optimization. It is often used in hybrid schemes
with the branch-and-bound and branch-and-cut techniques in those fields. See, for
instance, [2].
The aim of this paper is to present a basic idea on how we can approximate the
convex hull of F . This is a quite di#cult problem, and also too general. Before making
further discussions, we at least need to provide an appropriate (algebraic) representation
for the compact feasible region F of the problem (1.1) and the compact convex
feasible region C of the relaxation problem (1.2). We employ quadratic inequalities
for this purpose.
denote the set of n - n symmetric matrices and the set of
positive semidefinite matrices, respectively. Given Q
and # R, we write a quadratic function on R n with the quadratic term x T Qx, the
linear and the constant term # as p(-; #, q, Q):
Then the set Q of quadratic functions on R n and the set Q+ of convex quadratic
functions are defined as
and
respectively. We also write p(-) # Q (or Q+ ) instead of p(-; #, q, Q) # Q (or Q+ )
are irrelevant. Throughout the paper, we assume
that the feasible region F of the problem (1.1) is represented by a set of quadratic
inequalities such that
where PF denotes a set of quadratic functions, i.e., PF # Q, and we will derive convex
relaxations, C, represented by convex quadratic inequalities such that
where PC denotes a set of convex quadratic functions, i.e., PC # Q+ . We allow cases
where PF and/or PC involve infinitely many quadratic functions. Thus (1.1) or (1.2)
(or both) can be a semi-infinite quadratic optimization problem (QOP). Here we use
the word "semi-infinite" for optimization problems having a finite number of scalar
variables and possibly an infinite number of inequality constraints.
There are some reasons why we have chosen quadratic inequalities for the representation
of both problems, the maximization problem (1.1) that we want to solve
and its convex relaxation problem (1.2). First, quadratic inequalities form a class
of relatively easily manageable nonlinear inequalities, yet they have enough power
to describe any compact feasible region F in R n . Indeed, if F is closed, then its
complement R n
\F is open so that it can be represented as the union of the open balls
{x
over all x # G for some G # R n
We also know that any single polynomial inequality can be converted into a system
of quadratic inequalities; for example,
can be converted into
Second, we know that we can solve some classes of maximization problems having
linear objective functions and a convex-quadratic-inequality constrained feasible
region C e#ciently. Among others, we can apply interior-point methods [1, 16] to the
problem (1.2) when either PC is finite or PC is infinite, but its feasible region C is
described as the projection of a set characterized by linear matrix inequalities in the
space S n of n - n symmetric matrices onto the n-dimensional Euclidean space R n .
Third, and also most importantly, we can apply the semidefinite programming
(SDP) relaxation, which was originally developed for 0-1 integer programming problems
by Lov-asz and Schrijver [12] and later extended to nonconvex quadratic optimization
problems [6, 18, 19], to the entire class of maximization problems having a linear
objective function and finitely or infinitely many quadratic inequality constraints. See
also [1, 8, 9, 13, 15, 23, 24, 29].
In addition to the reasons above, we should mention that the maximization problem
with a linear objective function and quadratic inequality constraints involves
various optimization problems such as 0-1 integer linear (or quadratic) programming
problems which, in principle, include all combinatorial optimization problems
[1, 9, 18]. Linear complementarity problems [4], bimatrix games, and bilinear matrix
inequalities [14, 20] are also included as special cases.
For some optimization problems, some of the semidefinite programming (SDP)
relaxations we provide may be solved in polynomially many iterations (of an interior-point
method or an ellipsoid algorithm) approximately. Such conclusion requires, in
the case of the ellipsoid method, the existence of a certain polynomial-time separation
oracle for the underlying convex cone constraint (see [9]). In the case of interior-point
algorithms (whose e#ciency in the theory and practice of SDP has been well
established), we need to have an e#ciently computable self-concordant barrier for the
feasible solutions set or at least for the underlying cone constraints (see [16]).
Some of the most exciting activities in combinatorial optimization are currently
centered around the applications of SDP to combinatorial optimization problems (see
[7]). Such activity in theory and practice is fueled by theoretical results establishing
that certain simple SDP relaxations of a combinatorial optimization problem
can be e#ectively utilized in developing polynomial-time approximation algorithms
with worst-case approximation-ratio guarantees much better than those previously
proven using linear programming or other techniques. (See Goemans [7], Goemans
and Williamson [8], Nesterov [15], and Ye [29].) Also outstanding are the results
on the stable set problem establishing the fact that SDP techniques can be used in
optimizing over a relaxation of the stable set polytope which is contained in the polytope
defined by the clique inequalities. (Note that it is NP-hard to optimize over the
latter-mentioned polytope, whereas Gr-otschel, Lov-asz, and Schrijver [9] and Lov-asz,
and Schrijver [12] were able to utilize polynomial-time methods to achieve a better
goal, as far as the proof of approximate optimality of some feasible solutions of the
stable set problem is concerned.)
Given an initial approximation C 0 of F , i.e., a compact convex set C 0 containing
F , both of the methods, proposed in this paper, generate a sequence of compact
convex subsets
(a)
It should be noted that the compactness of each C k and property (b) imply that
(c) if
(detecting infeasibility).
To generate C k+1 at each iteration, the SDP relaxation and the linear programming
relaxation play an essential role, and the entire method may be regarded
as an extension of the Lov-asz-Schrijver lift-and-project procedure for 0-1 integer programming
problems to semi-infinite nonconvex quadratic optimization problems, with
the use of the SDP relaxation in the first method and the LP relaxation in the second
method. The LP relaxation, referred to above, is essentially the same as the
reformulation-linearization technique developed for nonconvex quadratic optimization
problems by Sherali and Alameddine [21]; see also [2, 22]. However, we should
caution the reader that the methods presented here are mostly conceptual in the general
settings, because we need to solve a semi-infinite SDP (or a semi-infinite LP) at
each iteration. For such a task, an e#cient practical algorithm may not be currently
available.
In their paper [6], Fujie and Kojima proposed the semi-infinite convex QOP relaxation
for nonconvex quadratic optimization problems and showed that the semi-infinite
convex QOP relaxation is not stronger than the SDP relaxation in general,
but the two relaxations are essentially equivalent under Slater's constraint qualifica-
tion. We establish the exact equivalence between the two relaxations for semi-infinite
nonconvex quadratic optimization problems without any constraint qualification. Using
this equivalence, we derive some fundamental features of our methods including
(a) and (b) above. One of the common themes in this paper is the usage of cones of
matrices (and duality) in our constructions. This was also one of the themes of [12].
The other themes of this paper are the successive applications of SDP relaxations and
LP relaxations. We call the related procedures the successive SDP relaxation method
and the successive semi-infinite LP relaxation method, respectively.
Section 2 is devoted to preliminaries, where we provide some basic definitions
and properties on quadratic inequality representations for closed subsets of R n , the
homogeneous form of quadratic functions, the SDP relaxation, etc. In section 3, we
present our first method in detail as well as the main results, including the features (a)
and (b). After we present some fundamental characterizations of the SDP relaxation
in section 4, we give proofs of the main results in section 5. In section 6, we apply our
method to 0-1 semi-infinite nonconvex quadratic optimization problems. Incorporating
the basic results on the lift-and-project procedure given by Lov-asz and Schrijver
[12] for 0-1 integer convex optimization problems, we show that our method terminates
in at most (n iterations either to generate the convex hull of the feasible
region or to detect the emptiness of the feasible region, where n denotes the number
of 0-1 variables of the problem. Section 7 contains our second method, which is based
on semi-infinite LP relaxations. We establish the same theoretical properties as we
do for the successive SDP relaxation method. In section 8, we present two numerical
examples showing the worst-case behavior of some of our procedures. In particular,
we know from the second example that the best of our procedures requires infinitely
many iterations to generate the convex hull of F in the worst case.
2. Preliminaries.
2.1. Semi-infinite quadratic inequality representation. In this subsection,
we discuss some representations of a closed subset F of R n in terms of (possibly
infinitely many) quadratic inequalities. If p(-; #, q, Q) # Q, and p(x; #, q, Q) # 0
holds for all x # F , we say that p(x; #, q, Q) # 0 is a quadratic valid inequality for
F and that p(-; #, q, Q) induces a quadratic valid inequality for F . A quadratic valid
inequality p(x; #, q, Q) # 0 for F is
linear
and # R such that # a T x #x # F ,
rank-2 quadratic if
and # R such that a T x # and b T x #x # F ,
spherical if
ellipsoidal if
convex quadratic if Q # S n
respectively. It should be noted that if a quadratic valid inequality p(x; #, q, Q) # 0
for F is rank-2, then the rank of the matrix Q is at most 2 but that the converse is
not necessarily true.
We say that F has a (semi-infinite) quadratic inequality representation P # Q if
holds. To designate the underlying representation P of F , we often write F (P) instead
of F . Whenever F is a closed proper subset of R n , F has infinitely many represen-
tations. We allow the cases where P consists of infinitely many quadratic functions.
Hence can be a semi-infinite system of quadratic inequalities. If
inequality representation of F and if p(-) # c.cone(P), then
is a quadratic valid inequality, where c.cone(P) denotes the closed convex
cone generated by P. Hence if P # P # c.cone(P), then P # is a quadratic inequality
representation of F ; F inequality representation
P of F is finite if it consists of a finite number of quadratic functions, and
infinite otherwise. If F is a compact convex subset of R n , it has a quadratic inequality
representation; in fact, the set of all the linear (rank-2 quadratic or spherical)
valid inequalities for F forms an inequality representation of F . If, in addition, F is
polyhedral, we can take a finite linear inequality representation.
Let C be a compact subset of R n . We use the following symbols:
the set of p(-)'s that induce linear valid inequalities for C,
the set of p(-)'s that induce rank-1 quadratic valid inequalities for C,
the set of p(-)'s that induce rank-2 quadratic valid inequalities for C,
the set of p(-)'s that induce spherical valid inequalities for C,
the set of p(-)'s that induce ellipsoidal valid inequalities for C,
the set of p(-)'s that induce convex quadratic valid inequalities for C,
the set of p(-)'s that induce all quadratic valid inequalities for C.
By definition, we see that
Note that if C is convex, then the equality
holds with each
these, P # (C) is the strongest quadratic inequality representation of C.
2.2. Homogeneous form of quadratic functions-lifting to the space of
symmetric matrices. We introduce a di#erent description of quadratic functions,
which we call the homogeneous form. This form leads us to a lifting of a quadratic
function defined on the Euclidean space to the space of symmetric matrices and to
the SDP relaxation (or to the semi-infinite LP relaxation in section 4.2). For every
quadratic function p(-; #, q, Q) # Q, we connect the variable vector x # R n to the
positive semidefinite matrix
x
and the triplet of the constant # R, q # R n , and Q # S n to the (1
. Then we have the identity
p(x; #, q,
x
Thus, if P # Q is a quadratic inequality representation of F , then
provides an equivalent representation of F ;
Now we have two kinds of description for a quadratic function on R n : the usual
form p(-; #, q, and the homogeneous form introduced above.
The former is used in section 5, where we prove our main results, while the latter is
suitable for the compact description of the SDP relaxation in section 2.3 and the proof
of its equivalence to the semi-infinite convex QOP relaxation in section 4. We will use
both forms in parallel, choosing whichever is convenient to us in a given situation. It
should be noted that the correspondence
is not only one-to-one but also linear. To save notation, we identify the set Q of
quadratic functions with the set S 1+n of (1
any subset of Q with the corresponding subset of S 1+n . Specifically, we write
identify the set of (1
symmetric matrices
with the set Q of quadratic functions from R n to R.
2.3. SDP relaxation. Let P be a semi-infinite quadratic inequality representation
The SDP relaxation -
F (P) of F (P) with the quadratic inequality representation P is
given by
and
and
x
and P . # 1 x T
This implies that x # -
F (P) and F (P) # -
F (P). We also see that -
F (P) is convex.
Hence
F (P). The SDP relaxation was originally proposed for combinatorial
optimization problems and 0-1 integer programming problems [12], and later
extended to quadratic optimization problems. See [1, 6, 8, 9, 15, 19, 18, 23, 24, 29].
3. Main results. Now we are ready to describe our method for approximating
a quadratic-inequality-constrained compact feasible region F of the minimization
problem (1.1). Before running the method, we need to fix a semi-infinite quadratic
inequality representation PF of F , and choose an initial approximation C 0 of the convex
hull of F , i.e., a compact convex set which contains c.hull(F ). Starting from C 0 ,
the method generates a sequence of compact convex sets
we expect to converge to c.hull(F ). At each iteration, we choose a semi-infinite quadratic
inequality representation P k of the kth approximation C k of c.hull(F ). Since
the union (PF # P k ) forms a semi-infinite quadratic inequality representation
of F . We then apply the SDP relaxation to (PF # P k ) to generate the
next iterate C
It should be emphasized that during none of the
iterations do we modify or strengthen the representation PF directly. We only utilize
the semi-infinite quadratic inequality representation of the compact convex set C k
that has been computed in the previous iteration.
Successive SDP Relaxation Method.
Step 0: Let
Step 2: Choose a semi-infinite quadratic inequality representation P k for C k .
Step 3: Let
and
Step 4: Let to Step 1.
We state two convergence theorems below. We choose the spherical inequality
representation at Step 2 of each iteration in the first theorem, while
we choose the rank-2 quadratic inequality representation P 2 (C k ) for C k at Step 2 of
each iteration in the second theorem. Their proofs will be given in section 5.
Theorem 3.1. Assume that PF is a semi-infinite quadratic inequality representation
of a compact subset F of R n , and that C 0 # F is a compact convex subset
of R n . If we choose P of each iteration in the successive SDP
relaxation method, then the monotonicity property (a) and the asymptotic convergence
property (b) stated in the introduction hold.
Theorem 3.2. Under the same assumptions as in Theorem 3.1, if we choose
of each iteration in the successive SDP relaxation method,
then (a) and (b) remain valid.
We know that if P # Q and P # Q are semi-infinite quadratic inequality representations
of C k and if
F (P). Hence, even if we replace
)" in Theorem 3.1 by "P k # P S (C k )" (or "P )" in Theorem
3.2 by "P k # P 2 (C k )"), the properties (a) and (b) remain valid. In particular,
(a) and (b) remain valid when we choose any of P
If we take the linear representation P L (C k ) of C k at every iteration, then we can
prove that
(See Lemma 4.1.) Hence (b) does not follow in general.
In section 8, we will give two numerical examples. The first example shows that
the rank-1 quadratic inequality representation strong enough
to ensure (b). The second example shows that even when we choose the strongest
quadratic inequality representation P # (C k ) of C k for P k at every iteration, not only
does the convergence "C k # c.hull(F )" require infinitely many iterations, but its
speed also becomes extremely slow in the worst case.
4. Fundamental characterization of successive convex relaxation.
4.1. Semi-infinite convex QOP relaxation and its equivalence to SDP
relaxation. The semi-infinite convex QOP relaxation of F (P) with the semi-infinite
quadratic inequality representation P is defined as
We observe that
F (P)
and that the set -
F (P) is a closed convex set. Hence F (P) # c.hull(F
F (P).
The semi-infinite convex QOP relaxation was introduced by Fujie and Kojima
[6]. It was called the relaxation using convex-quadratic valid inequalities for F (P) in
their paper [6]. The following basic properties of the relaxation are essentially due to
them.
Lemma 4.1. Let PF be a semi-infinite quadratic inequality representation of a
closed set F # R n .
Let P be a set of convex quadratic valid inequalities for F , i.e.,
Then
Let P be a set of linear valid inequalities for F , i.e.,
(iii) Let x # c.hull(F ). Suppose that p(x #, q, Q) # 0 for some p(-; #, q, Q) # PF
with a positive definite Q. Then x # -
F (PF ).
Proof. Part (i) follows directly from the definition of the semi-infinite convex
QOP relaxation. Now we show (ii). Let
we see that
Hence it su#ces to show that -
F (PF #P). Let p(-) # c.cone(P F #P)#Q+ .
Then there exist p(-) i # PF positive
m) such that
are linear functions, we see that
F (PF ).
Moreover,
Therefore,
This proves (ii). Finally we will show (iii). Since x # F , there is a p # PF such
that su#ciently small, we obtain that
This implies x # -
F (PF ), and proves (iii).
When P is finite and F (P) satisfies Slater's constraint qualification, Fujie and Kojima
[6] showed that the semi-infinite convex QOP relaxation is essentially equivalent
to the SDP relaxation in the sense that -
F (P) coincides with the closure of -
F (P). The
theorem below shows the exact equivalence between them, without any constraint
qualification, for more general semi-infinite quadratic inequality representation cases.
F (P) is closed, one of the consequences of the next theorem is that -
F (P) is
always closed. Note that we can assume without loss of generality that P is a closed
convex cone, since every closed set F admits such a representation.
Theorem 4.2. Let P be a closed convex cone, giving a semi-infinite quadratic
inequality representation of a closed subset F of R n
its SDP relaxation and its semi-infinite convex QOP relaxation
coincide with each other; -
F (P).
Proof. Using the dual cone
of P, we can express the sets -
F (P) and -
F (P) as follows:
and
# .
For the last identity above, we have used the fact that for any pair of closed convex
cones K 1 and K 2 in R m , we have (K 1 # K 2
First let x # -
F (P). Then there exists an X # S n such that
760 MASAKAZU KOJIMA AND LEVENT TUNC-EL
Consider the identity
-x -X
The first matrix on the right-hand side is in P # and in the second matrix of the
right-hand side, we have X - xx T
since it is the Schur complement of 1 in
the symmetric, positive semidefinite matrix # 1 x T
We have proved x # -
F (P) and
hence -
F (P).
For the converse, let x # -
F (P); that is, there exists some H # S n
such that
The matrix
is positive semidefinite if and only if (H
is. But the latter was
already established. So,
.
Therefore x # -
F (P), and -
F (P) is proved.
4.2. Semi-infinite LP relaxation. In section 7, we will also need an analog of
the above theorem for our successive semi-infinite LP relaxation method. For every
semi-infinite quadratic inequality representation P of a compact subset F of R n , let
us define
and
of Sherali and Alameddine [21]. Here, L denotes the set of linear functions on
The next result can be obtained by following the steps of the proof of Theorem 4.2.
Corollary 4.3. Let P be a closed convex cone, giving a semi-infinite quadratic
inequality representation of a closed subset F of R n
F L (P).
Proof. We observe that
and
Since it is easy to see that #X # S n such that # 1 x T
only if
the proof is complete.
4.3. Invariance under one-to-one a#ne transformation. Let
b be an arbitrary one-to-one a#ne transformation on R n , where A is an n - n non-singular
matrix and b # R n .
Then
of f(F (P)). This means that the semi-infinite SDP and LP relaxations are
invariant under the one-to-one a#ne transformation
We also see that
holds, where U # {L, 1, 2, E, C, #}. Therefore, P L (C),
are invariant under one-to-one a#ne transformations on R n . If in
addition A is a scalar multiple of an orthogonal matrix, then the above identity also
holds for is invariant under such a one-to-one a#ne transformation
on R n .
At each iteration of the successive SDP relaxation method, we observe that
forms a semi-infinite quadratic inequality representation
of f(F ) and P #
inequality representation of f(C k ). Furthermore, if we choose one of the invariant
semi-infinite quadratic inequality representations P L (C k ),
under any one-to-one a#ne transformation for P k , we see
that P U hence the identity above turns out to
be
Here U # {L, 1, 2, E, C, #}. Therefore the successive SDP relaxation method is
invariant under any one-to-one a#ne transformation. The same comment applies to
the successive semi-infinite LP relaxation method, which we will present in section 7.
762 MASAKAZU KOJIMA AND LEVENT TUNC-EL
5. Proofs of Theorems 3.1 and 3.2. We present three lemmas, Lemma 5.1 in
section 5.1, Lemma 5.2 in section 5.2, and Lemma 5.3 in section 5.4. Lemma 5.1 proves
the monotonicity property (a) in Theorems 3.1 and 3.2 simultaneously. Lemma 5.2
is used to prove Theorem 3.1 in section 5.3, and Lemma 5.3 to prove Theorem 3.2 in
section 5.5.
5.1. Monotonicity. We first establish the monotonicity in general.
Lemma 5.1. Let C 0 be a compact convex set containing F . Fix a closed convex
cone S 1+n
# K and
Assume that
# K and
Proof. Since K # S 1+n
contains all symmetric rank-1 matrices of the form
Now, as in the arguments in section 2.3, it follows that c.hull(F
We will show by induction that C k+1 # C k for all
the construction of C 1 and the assumption imposed on C 0 , we first observe that
Now assume that C k # C k-1 for some k # 1. Then P U (C k-1
which implies that PF # P U (C k-1
desired.
5.2. Separating hypersphere. The following lemma easily follows from the
separating hyperplane theorem, and the proof is omitted here.
Lemma 5.2. Let C be a compact convex subset of R n and x # C. Then there
exists a hypersphere S # {x # R n : #x-d#} which strictly separates the point x #
and C such that
where d # R n and # > 0.
5.3. Proof of Theorem 3.1. The monotonicity property (a) follows from Lemma
5.1 by letting K # S 1+n
and U # S. Let C # k=0 C k . We know by (a) that
that all the sets c.hull(F ), C, and C k
are compact sets. To prove (b), we have the following left to show: C # c.hull(F ).
Assume on the contrary that there exists some x # C such that x # c.hull(F ). Then,
by Lemma 5.2, there exists a hypersphere S # {x # R strictly
separates the point x # C from c.hull(F ) such that
there is a quadratic function,
cuts o# x Q). Note that if p 1 (-; #, q, Q) is
such a quadratic function, then so is #p 1 (-; #, q, Q) for any # > 0. Hence we may
assume that the minimum eigenvalue of the matrix Q # S n is at least (-1). Now
consider a quadratic function p 2 (-) defined by
By the definition of # , we see that
This means that the open ball B+ # {x # R with the center d and the
a neighborhood of the compact set C. On
the other hand, the sequence {C k } of compact subsets of R n satisfies
So, we can find a finite positive number # such that the open ball B+ contains C # .
Hence, We also
see that
Thus we have shown that
Therefore, x # C
. This is a contradic-
tion. The theorem is proved.
5.4. A family of inequalities of the convex cone of rank-2 quadratic
valid inequalities for the unit ball. Let B denote the unit ball {x # R
1}. Let Q be an arbitrary n - n symmetric matrix, and let u # R n be an arbitrary
vector on the boundary of B; #u# = 1. We will construct a family of quadratic
valid inequalities, which lie in the convex cone of rank-2 quadratic valid inequalities,
with a parameter # (0, #/8) for the unit ball B satisfying the properties
(i), (ii), and (iii) listed in Lemma 5.3.
We first apply the eigenvalue decomposition to the matrix Q # S n . We may
assume that the first m eigenvalues are nonnegative and the last
are nonpositive for some nonnegative integer m # n. Then we can write the matrix
denote eigenvectors of Q, which are orthogonal to each other, and - j (j = 1, 2, . , m)
and - j (j = m+ 1, . , n) denote the eigenvalues corresponding to them.
For each # (0, #/8), we define
a
a
are nonzero
vectors, and
a
are linear valid inequalities for the unit ball B. For all # (0, #/8), define
In particular, p # (u) # 0 # (0, #/8).
Lemma 5.3.
tends to 0.
(iii) The Hessian matrix of p # (-) coincides with -Q.
Proof. Part (i) was already shown.
(ii) Let j be fixed. It su#ces to show that
converge to zero as # (0, #/8) tends to 0. First, we derive that # j (#) converges to
zero as # (0, #/8) tends to 0. We see from (5.2) that
sin #)
sin #
(b T
sin #
(b T
Since both the numerator and the denominator above converge to zero as # (0, #/8)
tends to 0, we calculate their derivatives at The derivative of the numerator
turns out to be
(b T
which vanishes at On the other hand, the derivative "2 cos #" of the denominator
"2 sin #" in (5.5) does not vanish at converges to 0 as
# (0, #/8) tends to 0. Similarly, we can prove that - # j (#) converges to 0 as # (0, #/8)
tends to 0.
(iii) It follows from the definitions (5.2) and (5.4) that the Hessian matrix of
the quadratic function p # (-)
a
a j (#) T= -
From the lemma above, we see that the cone rich enough to contain
rank-2 quadratic functions with any prescribed Hessian, leading to valid inequalities
that are tight at any given point on the boundary of B.
5.5. Proof of Theorem 3.2. The monotonicity property (a) follows from
Lemma 5.1 by letting K # S 1+n
2. To derive (b), it su#ces to show
that C # k=0 C k # c.hull(F ) as in the proof of Theorem 3.1. Assume on the contrary
that x # c.hull(F ) for some x # C. By Lemma 5.2, there exists a hypersphere
strictly separates the point x # C and c.hull(F )
such that
the successive SDP relaxation method using the
rank-2 quadratic representation for C k at each iteration is invariant under the a#ne
transformation maps d to the origin and the hypersphere
onto the unit hypersphere {x # R
may assume that 1. Thus, we have obtained that
Since u # F , there is a quadratic function p 1 (-; #, q, Q) # PF that cuts o# u;
be the quadratic function introduced
in section 5.4. See (5.2) and (5.4). By Lemma 5.3, we can choose a # (0, #/8)
for which p # (u) # -p 1 (u; #, q, Q)/3 holds. Now we define
766 MASAKAZU KOJIMA AND LEVENT TUNC-EL
By construction, we know that p # k (-) # c.cone(P 2 (C k )). Since both
quadratic functions p # (-) and p # k (-) have the common Hessian matrix -Q,
We will show that
for every su#ciently large k. Then the above two relations imply u # C k+1 for such
a large k. This contradicts the fact
Since the sequence of compact convex subsets
we see that
as k # (j = 2, 3, . , n). By continuity, we see then that for every su#ciently large
Thus we have shown that (5.6) holds for every su#ciently large k. This completes
the proof of Theorem 3.2.
6. Application to 0-1 semi-infinite, nonconvex quadratic optimization
problems. We briefly recall two of the Lov-asz-Schrijver procedures for 0-1 integer
programming problems, and relate them to our successive SDP relaxation method.
Let F be a subset of {0, 1} n whose convex hull is to be approximated. In the Lov-asz-
Schrijver procedures, we assume that a compact convex subset C 0 of R n satisfying
is given in advance. We define
Let K I denote the convex cone spanned by the 0-1 vectors in K
Here the 0th coordinate is special. It is used in homogenizing the sets of interest in
R n . Clearly
The closed convex cone K 0 serves as an initial relaxation of K I . Given the current
relaxation K k of K I , first a convex cone M+ (K k , K k ) in the space of (1
symmetric matrices is defined (the lifting operation). Then a projection of this cone
gives the next relaxation N+ (K k ) of K I .
Now, we define the lifting operation in general. Let K and T be closed convex
cones in R 1+n . A (1 real entries is in
(This condition is equivalent to Y K # T .)
Here, e 0 denotes the unit vector with 0th coordinate 1. Item (ii) above serves
an important role in Lov-asz-Schrijver procedures as well as in some of the SDP
relaxations used by Goemans and Williamson [8], Nesterov [15], and Ye [29]. This
equation is valid simply because for each j for which x j # {0, 1}, the equation x 2
is valid. Indeed, our general framework applies to any compact set in R n , and the
equation Y e not utilized in earlier sections (as it is not valid). In
this section, however, the equation is valid and we utilize it. As will be noted in the
proof of Theorem 6.3, the inclusion of this equation will be guaranteed by our choice
of the initial formulation.
The third condition of Lov-asz-Schrijver procedures is very interesting. They
present a couple of possibilities for the choice of cone T in 0-1 integer programming.
Among them is the cone spanned by all 0-1 vectors with the first component x
This choice, since the cone T # has a very simple set of generators, allows for the
development of polynomial-time algorithms for approximately solving the successive
SDP relaxations as long as the number of iterations of the successive procedure is
O(1). Their result only assumes that a polynomial-time weak separation oracle is
available for K. The key is that since T # has only O(n) extreme rays, it becomes
trivial to check condition (iii) in polynomial time. On the other hand, Lov-asz and
Schrijver [12] note that the choice T # K is also possible and leads to at least as good
relaxations as the former choice for T . (In many cases the successive relaxations for
are significantly tighter than the successive relaxations with the simpler choice
of T .) In the case of the latter choice, the possibility of polynomial-time solvability
of the first few successive relaxations depends on the availability of polynomial-time
algorithms to check Y K # K. Our procedure uses T # K.
Now, we describe the projection step.
We also define the iterated operators N k
use the notation N+ (K), whereas N+ (K, K)
is used in [12].)
Another procedure studied in [12] uses a weaker relaxation by removing the condition
(i) in the lifting procedure. Let M(K,K) and N(K) denote the related sets for
this procedure. We will refer to the first procedure using the lifting M+ (K, K) (and
the projection N+ ) as the N+ procedure. We will call the other (using M(K,K), and
N) the N procedure. Lov-asz and Schrijver prove the following.
Theorem 6.1.
and
768 MASAKAZU KOJIMA AND LEVENT TUNC-EL
Let us see how our successive SDP relaxation method applies to 0-1 nonconvex
quadratic optimization problems. Consider a 0-1 nonconvex quadratic program:
subject to x # F # {x # {0, 1}
We may assume that the set P # contains the quadratic functions x
1, 2, . , n. Then we can replace the 0-1 constraint imposed on the variable x i by the
inequality -x i by adding the quadratic functions -x
1, 2, . , n, to P # , we obtain a quadratic inequality representation PF of the feasible
region F . Let C 0 # [0, 1] n . Note that F #= C 0 #{0, 1} our general setting
here. However, has been assumed for some compact convex subset
C 0 of R n in the Lov-asz-Schrijver procedures discussed above.
Lemma 6.2. Suppose that we take C
and
Proof. Let C #
1 be the semi-infinite convex QOP relaxation of the set F with the
quadratic inequality representation PF #
In view of Theorem 4.2 and Lemma 5.1, we know that
Hence it su#ces to show that
If F contains all the 0-1 vectors, the inclusion relation above obviously holds. Now
assume that x # F is a 0-1 vector. Then there is a quadratic function p 1 (-, #, q, Q) #
PF such that
On the other hand, we know that the quadratic function
with the identity matrix as its Hessian matrix, is a member of c.cone(P 0 ), and that
Hence if # > 0 is su#ciently small, then
This implies that x # C #
As a consequence of the lemma above, we see that the 0-1 nonconvex quadratic
optimization problem (6.1) is equivalent to the 0-1 convex quadratic optimization
problem
subject to x #
Using this observation, we can prove that in the case of 0-1 nonconvex quadratic
optimization problem (6.1), our successive SDP relaxation method converges in (1+n)
iterations.
Theorem 6.3. The successive SDP relaxation method, applied to the 0-1 non-convex
quadratic optimization problem (6.1), using C as the initial approximation
of c.hull(F ) and in each iteration, terminates in at most (1 +n)
iterations with
Proof. We note that by Lemma 6.2, after one iteration of the successive SDP
relaxation method, we obtain the 0-1 convex quadratic optimization problem (6.2)
that can be used with the original Lov-asz-Schrijver procedure. We only have to note
that the successive SDP relaxation method becomes the Lov-asz-Schrijver procedure
after the first iteration. For this purpose, we compare conditions (i), (ii), and (iii) of
the Lov-asz-Schrijver procedure for to the conditions used to construct
in the successive SDP relaxation method. Here
First, we observe that #X # S n such that Y # 1 x T
if and only if # 0,
. Hence (i) is satisfied. For (ii), note that
implies the constraint Y e
implies Y e 0 # Diag(Y ). Finally, for (iii), note that a linear inequality a T x # is
valid for C k if and only if (#, -a T
Therefore, we see that
Step (3.1) of the successive SDP relaxation method implies that
. Thus, we conclude by noting that
Theorem 6.1 implies that n more steps of the procedure is su#cient.
The above discussion and the results show that our successive SDP relaxation
method generalizes the Lov-asz-Schrijver N+ procedure by ignoring condition (ii),
which is no longer valid. Our results in the previous sections already showed that
in this full generality, we still have the asymptotic convergence of the method. It is
therefore interesting to investigate the same questions about the weaker procedure
. What is the generalization of procedure N?
. Does the generalization of procedure N satisfy the same theoretical properties
as the successive SDP relaxation method?
We answer both of these questions in the next section. As is shown in [12], in
some cases the procedure N+ is significantly better than N . Procedure N is weaker,
but the relaxations given by it are always polyhedral sets (so LP techniques can be
employed) and N+ requires more general techniques. Hence, sometimes procedure N
might be more manageable even if the procedure N+ is not.
We should expect that the generalization of procedure N should be only using
condition (iii), Y K # K, in the definition of the lifting. We would also expect that
the generalization should lead to semi-infinite LP (rather than SDP) relaxations. We
show in the next section that the above-mentioned generalization of procedure N
leads to successive semi-infinite LP relaxations and all the analogs of the theoretical
properties established for our successive SDP relaxations can also be established for
the successive semi-infinite LP relaxations.
7. Successive semi-infinite LP relaxation.
Successive Semi-Infinite LP Relaxation Method.
Step 0: Let
Step 2: Choose a quadratic inequality representation P k for C k .
Step 3: Let
#X # S n such that
(The equalities above follow from Corollary 4.3.)
Step 4: Let to Step 1.
Theorem 7.1. Assume that PF is a semi-infinite quadratic inequality representation
of a compact subset F of R n , and that C 0 # F is a compact convex subset of
R n . If we choose P of each iteration in the successive semi-infinite
LP relaxation method, then the monotonicity property (a) and the asymptotic
convergence property (b) stated in the introduction hold.
Proof. We can apply the same proof as the one given for Theorem 3.2 in section 5.5
to the theorem.
Note that we can define another semi-infinite LP relaxation based on the semi-infinite
convex QOP relaxation. Clearly, if Q # S n
So, we can define a semi-infinite LP relaxation based on the above observation:
F L
q O
and
F L
q O
In this case, the equivalence -
F L
F L
is evident. The convergence of the successive
semi-infinite LP relaxation method using -
F L
can be established by following the proofs
of Theorems 3.1 and 3.2. Instead, we note -
F L
F L . Therefore, Theorem 7.1 also
implies that this particular semi-infinite LP relaxation method has the properties (a)
and (b) mentioned in the theorem.
8. Further discussions on successive convex relaxations.
8.1. Conic quadratic inequality representation. The conic quadratic inequality
presented below is a generalization of the linear matrix inequality [3, 28] and
the bilinear matrix inequality [14, 20]. It will be shown that any conic quadratic
inequality can be reduced to a semi-infinite system of standard quadratic inequalities
and vice versa.
Let K and K K} be a closed convex cone in R m
and its dual. Here u - v denotes an inner product of u . For all
lies in K. Now we introduce a conic quadratic
vectors in R m . We may assume
without loss of generality that . The inequality (8.1) turns out to be a system
of m usual quadratic inequalities on R n if we take the nonnegative orthant R m
for the cone K. The inequality (8.1) turns out to be a quadratic matrix inequality,
which is a generalization of linear and bilinear matrix inequalities [3, 28] if we identify
the space of # symmetric matrices with R m and we take the positive semidefinite
of matrices for the cone K, where
We can rewrite the conic quadratic inequality (8.1) as a semi-infinite system of
standard quadratic inequalities in the homogeneous form.
for some P # . This means that we can easily include any conic quadratic
inequality in the semi-infinite quadratic inequality representation of the feasible region
F of the maximization problem (1.1). To see the equivalence between (8.1) and (8.2)
for some P # we observe that (8.1) can be rewritten as
Therefore, if we define
772 MASAKAZU KOJIMA AND LEVENT TUNC-EL
we obtain the desired semi-infinite system (8.2) of standard quadratic inequalities,
which is equivalent to (8.1).
Let F (P) denote the solution set of (8.2) with its quadratic inequality representation
Applying the SDP relaxation to F (P), we obtain
that
and
and
and
The set in the last line corresponds to the SDP relaxation to the solution set of (8.1).
This implies that we can apply the SDP relaxation directly to the conic quadratic
inequality converting it into the semi-infinite system (8.2) of standard
quadratic inequalities.
Conversely, we can reduce any semi-infinite system of standard quadratic inequalities
to a conic quadratic inequality. To show this, consider a semi-infinite system (8.2)
of standard quadratic inequalities in the homogeneous form. We may assume without
loss of generality that P # S 1+n is a closed convex cone. We can rewrite (8.2) as
x
which is a conic quadratic inequality.
Let F denote the solution set of the conic quadratic inequality (8.3) that we have
derived from (8.2) above. Applying the SDP relaxation to F , we obtain that
and
# .
Note that the set in the last line corresponds to the SDP relaxation of the solution
set of the semi-infinite system (8.2) of standard quadratic inequalities.
In view of the discussions above, we know that the conic quadratic inequality
representation is as general as the semi-infinite quadratic inequality representation
and that the SDP relaxations to both representations are equivalent. When we deal
with the semi-infinite convex QOP relaxation, however, the semi-infinite quadratic
inequality representation seems more convenient than the conic quadratic inequality
representation.
8.2. A counterexample to the convergence for the rank-1 quadratic
inequality representation case. The example below shows that the rank-1 quadratic
inequality representation is not strong enough to ensure the convergence of the
successive SDP relaxation method. Let
where denotes the rank-1 quadratic inequality representation of the unit ball,
which consists of all quadratic functions such that (a T x - 1)(a
see that
Theorem 8.1. Suppose that we take P
representation of C k ) in the successive SDP relaxation method applied to the
example above. Then C
Proof. By definition, C which su#ces to establish
the theorem. First observe that C 1 # B. Hence it su#ces to show
equivalently for all p(-) # c.cone(P F ) # Q+ ,
fixed. Then we can choose # i # 0
#) such that
Now assume that # 0 > 0. In this case, we may further
assume without loss of generality that #
It follows from p(-) # Q+ that the Hessian matrix #
I # is positive
semidefinite. Hence if we denote the largest and the smallest eigenvalues of the matrix
We also see that
Hence
8.3. A counterexample to the finite termination for the strongest quadratic
inequality representation case. The example below shows that in the worst
case, even when we take the strongest quadratic inequality representation P # (C k ) for
C k at every iteration,
. the successive SDP relaxation method requires infinitely many iterations, and
. the convergence is extremely slow.
For every
5.
Then
Theorem 8.2. Suppose that we take P strongest quadratic inequality
representation of C k ) in the successive SDP relaxation method applied to the
example above.
(i) C k is symmetric with respect to the x 2 axis:
only if (-x 1 , x 2
(ii) Let
Then
Proof. We will prove (i) and (ii) by induction.
(i) Obviously the assertion is true for Assume that C k is symmetric with
respect to the x 2 axis. Then we know that
This ensures that C k+1 is symmetric with respect to the x 2 axis.
(ii) By definition, we know that # 2. Hence (8.4) holds for Assuming
that (8.4) holds, we prove that (8.5) holds. We first observe that
It su#ces to show that (0, -
# C k+1 or equivalently
Assume on the contrary that
such that
Here we remark that p 1 (-) can be incorporated into p # (-) since p 1 (-) # P k . By the
symmetry with respect to the x 2 axis, we see that
Thus, defining -
we obtain that
It follows from p # and the third inclusion relation of (8.6) that p # (0, -
We may further assume without loss of generality that
redefine all the relations above
remain valid. Since -
we see that Q 11 # 1 and Q 22 # 1. By (8.6) and
hence
776 MASAKAZU KOJIMA AND LEVENT TUNC-EL
Therefore, by the convexity of the quadratic function -
p(x), we obtain that
This contradicts (8.7).
The above example is simple, yet it illustrates great di#culties for the successive
relaxation method. For example, # k+1 /# k # 1. Therefore, the convergence is
slower than linear.
Note that, in any dimension, if we take a pair of ball constraints, one convex
(inclusion), the other nonconvex (exclusion), then both of the successive SDP and
semi-infinite LP relaxation methods stop in one iteration, returning the convex hull
of the intersection. Also, in the above example, if we knew that p 2 (-) a#ects only
the definition of F in the region x 1 # 0 and that p 3 (-) is only e#ective in the region
we could do elementary modifications to the method to speed up convergence
tremendously. This is a good elementary example to illustrate the fact that for such
methods to become more e#cient in practice, hybrid approaches including branch-
and-bound and branch-and-cut seem necessary. We make further remarks in the next
section.
9. Concluding remarks. We propose extensions of two fundamental lift-and-
project procedures N and N+ of Lov-asz and Schrijver [12]. The original procedures
were proposed for 0-1 integer programming problems to compute the convex hull
of feasible (integer) solutions. Our procedure applies to any nonconvex region and
as a result we do not use the key equations, Y e used in N and N+
procedures. Therefore, our relaxations are based either on two conditions: Y is
positive semidefinite and Y K # K (successive SDP relaxation method), or on only
one condition: Y K # K (successive semi-infinite LP relaxation method). In both
cases we established the properties (a) monotonicity and (b) asymptotic convergence.
The weakest version of our procedures satisfying the properties (a) and (b) uses only
rank-2 quadratic valid inequalities. We showed in section 6 that such inequalities
ensure the condition Y K # K. Finally, in section 8 we showed that even the strongest
of such relaxation procedures (using all quadratic valid inequalities) uses infinitely
many iterations to converge. In the above sense, the strongest positive result is given
in section 7 by the successive semi-infinite LP relaxation method based on rank-2
valid inequalities.
On the one hand, theoretically speaking, the best results are given in section 7:
the weakest algorithm achieving the strongest results. Moreover, the successive semi-infinite
LP relaxation method is more likely to be practical for a given general problem.
On the other hand, the relative value of SDP relaxations has been quite impressive
so far on some very special problems (e.g., the stable set problem [12]) and less
impressive on others (e.g., the matching problem [25]). Therefore, one interesting
research direction is to search for interesting classes of nonconvex sets for which the
successive SDP relaxation method is significantly better than the successive semi-infinite
LP relaxation method. For the same reason, (partial) characterizations of
nonconvex sets on which both methods perform comparably are also important.
Our convergence proofs are by contradiction, but the main argument is about
cutting o# a point using valid inequalities induced by the underlying construction.
The strongest convergence result (for the weakest algorithm) uses separating hyper-
spheres. In the other proofs, for the bad points, the separating hyperspheres may have
huge radii and converge to hyperplanes. However, for certain points and shapes, the
advantage of using more general convex quadratic inequalities is clear. This discussion
motivates us to suggest another avenue for research. It would be interesting to find
certain invariants and measures of the input of our procedures that lead to nontriv-
ial, descriptive convergence rates for our methods, perhaps only for some interesting
subclass of problems.
Recently, Kojima and Takeda [11] discussed the computational complexity of the
successive SDP and semi-infinite LP relaxation methods. They gave an upper bound
on the number of iterations which the methods require to attain a convex relaxation of
a quadratically constrained compact set F with a given accuracy # > 0, in terms of #,
the diameter of the initial relaxation C 0 , the diameter of F , and some other quantities
characterizing the Lipschitz continuity and the nonconvexity and nonlinearity of the
quadratic inequality representation PF of F .
The major di#culty in implementing the idea of the successive SDP (or semi-infinite
relaxation method in practice is the solution of a continuum of semi-infinite
SDPs (or semi-infinite LPs) to generate a new approximation C k+1 of the
convex hull of the feasible region F of a nonconvex quadratic program at each itera-
tion. In their succeeding paper [10], the authors propose implementable variants by
introducing two new techniques, a discretization technique for approximating continuum
of semi-infinite SDPs (or semi-infinite LPs) by a finite number of standard SDPs
(or LPs) with a finite number of linear inequality constraints, and a localization technique
for generating a convex relaxation of F that is accurate only in certain directions
in a neighborhood of the objective direction c. They established that, Given any positive
number #, there is an implementable discretized-localized variant of the successive
SDP (or semi-infinite LP) relaxation method which generates an upper bound of the
objective values within # of their maximum in a finite number of iterations. See also
[27] for a practical implementation of this variant and some numerical results.



--R

Interior point methods in semidefinite programming with applications to combinatorial optimization

Linear Matrix Inequalities in System and Control Theory
The Linear Complementarity Problem
The directions of the line segments and of the r-dimensional balls on the boundary of a convex body in Euclidean space


Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Discretization and Localization in Successive Convex Relaxation Methods for Nonconvex Quadratic Optimization Problems
Complexity Analysis of Conceptual Successive Convex Relaxation of Nonconvex Sets

2nd rev
A cone programming approach to the bilinear matrix inequality problem and its geometry


On the Generic Properties of Convex Optimization Problems in Conic Form
A recipe for semidefinite relaxation for (0
An Algorithmic Analysis of Multiquadratic and Semidefinite Programming Problems
Control system synthesis via bilinear matrix inequalities
A new reformulation-linearization technique for bilinear programming problems
A reformulation-convexification approach for solving nonconvex quadratic programming problems
Systems Sci.
Dual quadratic estimates in polynomial and boolean programming
On a representation of the matching polytope via semidefinite liftings
Convexity and Optimization in Finite Dimensions I
Towards the implementation of successive convex relaxation method for

Approximating quadratic programming with bound and quadratic constraints
--TR

--CTR
Masakazu Kojima , Levent Tunel, Some Fundamental Properties of Successive Convex Relaxation Methods on LCP and Related Problems, Journal of Global Optimization, v.24 n.3, p.333-348, November 2002
Akiko Takeda , Katsuki Fujisawa , Yusuke Fukaya , Masakazu Kojima, Parallel Implementation of Successive Convex Relaxation Methods for Quadratic Optimization Problems, Journal of Global Optimization, v.24 n.2, p.237-260, October 2002
Mituhiro Fukuda , Masakazu Kojima, Branch-and-Cut Algorithms for the Bilinear Matrix Inequality Eigenvalue Problem, Computational Optimization and Applications, v.19 n.1, p.79-105, April 2001
Henry Wolkowicz , Miguel F. Anjos, Semidefinite programming for discrete optimization and matrix completion problems, Discrete Applied Mathematics, v.123 n.1-3, p.513-577, 15 November 2002
nonconvex quadratic optimization problem;global optimization;semi-infinite programming;linear matrix inequality;bilinear matrix inequality;semidefinite programming