Complexity Analysis of Successive Convex Relaxation Methods for Nonconvex Sets.
This paper discusses computational complexity of conceptual successive convex relaxation methods proposed by Kojima and Tunel for approximating a convex relaxation of a compact subsetof the n-dimensional Euclidean spaceR n . Here,C0 denotes a nonempty compact convex subset ofR n , anda set of finitely or infinitely many quadratic functions. We evaluate the number of iterations which the successive convex relaxation methods require to attain a convex relaxation ofF with a given accuracy e, in terms of e, the diameter ofC0, the diameter ofF, and some other quantities characterizing the Lipschitz continuity, the nonlinearity, and the nonconvexity of the setof quadratic functions.
Introduction
.
In their paper [2], Kojima and Tun-cel proposed a class of successive convex relaxation
methods for a general nonconvex quadratic program:
maximize c T x subject to x 2 F; (1)
where
a constant column vector in the n-dimensional Euclidean space R n ;
(we often write F instead of F (C
compact convex subset of R n ;
set of finitely or infinitely many quadratic functions on
(2)
Their methods generate a sequence fC k g of compact convex sets satisfying
(a)
(b) if (detecting infeasibility),
Here c.hull(F ) denotes the convex hull of F .
In connection with the successive convex relaxation methods, Kojima [4] pointed out that
a wide class of nonlinear programs can be reduced to a nonconvex quadratic program of the
form (1). More generally, it is known that any closed subset G ae R n can be represented as
using some convex function g(\Delta) : R n ! R. See, for example, Corollary 3.5 of [10]. Thus,
given any closed subset G of R n and any compact convex subset C 0 of R n , we can rewrite
maximization of a linear function c T x over a compact set G " C 0 as
maximize c T x
subject to (x;
where g(\Delta) is a convex function on R n and - t - 0 is a sufficiently large number such that
turns out to be compact and convex, and the resultant
problem is a special case of the general nonconvex quadratic program (1). Although this
construction is not implementable because an explicit algebraic representation of such a
convex function g(\Delta) is usually impossible, it certainly shows theoretical potential of the
successive convex relaxation methods for quite general nonlinear programs.
The successive convex relaxation methods are extensions of the lift-and-project proce-
dure, which was proposed by Lov'asz and Schrijver [5] for 0-1 integer programs, to a general
quadratic program of the form (1). At each iteration of the methods, we first generate a
set of finitely or infinitely many quadratic functions such that each p(x) - 0
forms a valid inequality for the kth iterate C k . Since C k was chosen to include F in the
previous iteration, each p(x) - 0 serves as a (redundant) valid inequality for F ; hence F is
represented as
We then apply the SDP (semidefinite programming) relaxation or the SILP (semi-infinite
linear programming relaxation) to the set F with the above representation in terms of the
set P F [P k of quadratic functions to generate the next iterate C k+1 . (The latter relaxation
is also called the reformulation-convexification approach in the literature [7]). See also [1, 8].
The successive convex relaxation methods outlined above are conceptual in the sense
that we need to solve "infinitely many semidefinite programs (or linear programs) having
infinitely many linear inequality constraints" at each iteration. In their succeeding paper
[3], Kojima and Tun-cel presented two types of techniques which discretize and localize
"infinitely many semidefinite programs (or linear programs) having infinitely many linear
inequality constraints" to implement their conceptual methods under a certain assumption
on a finite representation of the feasible region F . They established that, for any given
ffl ? 0, we can discretize and localize the conceptual methods to generate a sequence fC k g
of compact convex sets satisfying the features (a), (b) above and
Each iteration of these discretized-localized versions of successive convex relaxation methods
requires to solve finitely many semidefinite programs (or linear programs) having finitely
many linear inequality constraints, so that these versions are implementable on computer.
However, they are still impractical because as a higher accuracy ffl is required, not only the
number of the semidefinite programs (or linear programs) to be solved at each iteration but
also their sizes explode quite rapidly.
More recently, Takeda, Dai, Fukuda and Kojima [9] presented practical versions of successive
convex relaxation methods by further slimming down the discretized-localized versions
to overcome the rapid explosion in the the number of the semidefinite programs (or
linear programs) to be solved at each iteration and their sizes. Although these versions no
more enjoy the feature (c)', numerical results reported in the paper [9] look promising.
This paper investigates computational complexity of the conceptual successive convex
relaxation methods given in the paper [2]. When they are applied to 0-1 integer programs,
they work as the Lov'asz and Schrijver lift-and-project procedure [5], and they terminate in
iterations, where n denotes the number of 0-1 variables. (See Section 6 of [2] and Section 7
of [3]. ) In the general case where P F consists of arbitrary quadratic functions, however, the
convergence of fC k g to c.hull(F ) is slower than linear in the worst case. (See an example in
Section 8.3 of [2]. ) In this paper, we bound the number k of iterations required to generate
an approximation of c.hull(F ) with a given "accuracy." To begin with, we need to clarify
the following issues.
ffl Input data of the conceptual successive convex relaxation methods.
ffl Output of the methods and its quality or "accuracy."
ffl What are assumed to be possible in the computation?
To discuss these issues in more detail, we need some notation.
the set of n \Theta n symmetric matrices:
the quadratic function having the constant term fl,
the linear term 2q T x, and the quadratic term x T Qx;
where
Our input data are a nonempty compact convex subset C 0 of R n and a set P F of finitely
or infinitely many quadratic functions. We do not care about how we represent the compact
may be represented in terms of finitely or infinitely many linear inequalities,
nonlinear convex inequalities and/or linear matrix inequalities. Although it seems nonsense
to try to define the size of such input data, we extract some quantity and quality from the
input data. The diameter diam(C 0 ) of C 0 and the diameter diam(F ) of F are relevant on
our complexity analysis since C 0 serves as an initial approximation of c.hull(F ) which we
want to compute. Concerning quality or difficulty of the input data, we introduce
(a common Lipschitz constant for all p(\Delta) 2 P F on C 0 );
Here - min (Q) denotes the minimum eigenvalue of Q . Note that all - lip
either a finite nonnegative value or +1. We will assume that
they are finite. If P F consists of a finite number of quadratic functions, this assumption
is satisfied. We may regard - nc (P F ) as a nonconvexity measure of the set P F of quadratic
all quadratic functions in P F are convex if and only if - nc (P F
involves more nonconvexity as - nc larger. On the other hand, we may regard
- nl (P F ) as a nonlinearity measure of the set P F of quadratic functions; all functions in P F
are linear if and only if - nl (P F involves more nonlinearity as - nl (P F
gets larger. - lip directly affect the upper bounds that we will
derive for the number k of iterations required to generate an approximation of c.hull(F )
with a given certain accuracy.
Our output is a compact set C k ae R n , which is an approximation of c.hull(F ). Again
we don't care about its representation and size. In order to evaluate the quality or accuracy
of the approximation, we introduce the notation
By definition, We say that a
compact convex subset C of C 0 is an ffl-convex-relaxation of F if it satisfies
We set up an ffl-convex-relaxation of F as our goal of the successive convex relaxation methods

Now we discuss what are assumed to be possible in the computation. First we assume
precise real arithmetic operations. At each iteration, we need to choose a set P k of finitely or
infinitely many quadratic functions that induce valid inequalities for C k before performing
the SDP or SILP relaxation. Secondly we assume that such a P k is available. Kojima
and Tun-cel [2] proposed and studied several candidates for P k . In this paper, we focus our
attention on the following three models of successive convex relaxation methods.
ffl Spherical-SDP Model: We take P k to be a set of spherical quadratic functions, and we
perform the SDP relaxation (Section 3).
ffl Rank-2-SDP Model: We take P k to be a set of rank-2 quadratic functions, and we
perform the SDP relaxation (Section 4).
ffl Rank-2-SILP Model: We take P k to be a set of rank-2 quadratic functions, and we
perform the semi-infinite LP relaxation (Section 4).
In each model, we assume that a set of infinitely many quadratic functions chosen for P k is
available.
Our complexity analysis of the Spherical-SDP Model is much simpler than that of the
latter two models, and the former analysis helps an easier understanding of the latter two
models, which are of more practical interest. The latter two models correspond to extensions
of the Lov'asz-Schrijver lift-and-project procedure with the use of the SDP relaxation and
the use of the SILP relaxation, respectively. See Section 6 of [2] and Section 7 of [3]. The
Rank-2-SDP and the Rank-2-SILP Models themselves are not implementable yet. Implementable
versions of successive convex relaxation methods given in the paper [3] correspond
to discretization and localization of these two models. See also [9].
We summarize our main results: For each of the models mentioned above, given an
arbitrary positive number ffl, we bound the number k of iterations which the successive
convex relaxation methods require to attain an ffl-convex-relaxation of
terms of the quantities 1=ffl, diam(C 0 ), 1=diam(F
upper bound derived there itself might not be so significant, and might be improved by a
more sophisticated analysis. It should be emphasized, however, that the upper bound is
polynomial in these quantities, and that this paper provides a new way of analyzing the
computational complexity of the successive convex relaxation methods for general nonlinear
programs.
Preliminaries.
After introducing notation and symbols which we will use throughout the paper, we describe
the SSDP and SSILP algorithms in Section 2.2. In Section 2.3, we present another accuracy
measure of convex relaxation which will be utilized in establishing our main results.
2.1 Notation and Symbols.
Let
the set of n \Theta n symmetric matrices;
= the set of n \Theta n symmetric positive semidefinite matrices;
trace of A T
the set of quadratic functions on R n
(see (3) for the definition of qf(\Delta; fl; q; Q));
the set of convex quadratic functions on R n
the set of linear functions on R n
the convex cone generated by P ae Q
the convex hull of G ae R n ;
(n-dimensional closed) ball
with a center - 2 R n and a radius ae ? 0);
(the radius of the minimum ball
with a center - 2 R n that contains G ae R n );
the diameter of G ae R
2.2 SSDP and SSILP Relaxation Methods.
Let C ae R n and p(\Delta) 2 Q. If p(x) - 0 for 8x 2 C, we say that
valid inequality for C, and that p(\Delta ) induces a quadratic valid inequality for C.
Let P be a nonempty subset of quadratic functions, i.e., ; 6= P ae Q. (In the algorithms
below, we will take P to be the union of P F and a P k of quadratic functions which induce
quadratic valid inequalities for the kth iterate C k ). We use the notation b
for the
SDP relaxation, and the notation b
F L
for the SILP relaxation applied to the set
is positive semidefinite,
F L
The lemma below provides a fundamental characterization of b
F L
which played an essential role in the global convergence analysis of the successive convex
relaxation methods in the papers [2, 3]. We will use the lemma in Sections 3 and 4.
Lemma 2.1. Let ; 6= P ae Q.
F L
Proof: See Theorem 4.2 and Corollary 4.3 of [2].
Algorithms 2.2 and 2.3 below are slight variants of the SSDP relaxation method given
in Section 3 of [2] and the SSILP relaxation method given in Section 7 of [2], respectively.
See also Section 3 of [3].
Algorithm 2.2. (SSDP relaxation method)
Step 0: Let
Step 1: Choose a set P k ae Q that induces quadratic valid inequalities for C k .
Step 2: Let C
Step 3: Let to Step 1.
Algorithm 2.3. (SSILP relaxation method)
Step 0: Let
Step 1: Choose a set P k ae Q that induces quadratic valid inequalities for C k .
Step 2: Let C
F
Step 3: Let to Step 1.
In Section 3 where we discuss the complexity of the Spherical-SDP Model, we will take
k to be a set of spherical functions, while in Section 4 where we discuss the complexity of
the Rank-2-SDP and the Rank-2-SILP Models, we take P k to be a set of rank-2 quadratic
functions. By definition, b
F L
make it possible for us to apply our complexity analysis to the Rank-2-SILP Model, and
simultaneously to the Rank-2-SDP Model in Section 4.
2.3 Accuracy Measures of Convex Relaxation.
In Section 1, we have introduced an ffl-convex-relaxation of using c.hull(F (ffl))
to measure the quality or accuracy of an approximation C k of c.hull(F )
which we want to compute. In our complexity analysis of Algorithms 2.2 and 2.3, this notion
is not easy to manipulate directly. In this section, we introduce another notion (/; \Xi)-
convex-relaxation of F which is easier to manipulate, and relate it to the ffl-convex-relaxation
of F .
Let / ? 0, and let \Xi ae R n be a nonempty compact convex set. We say that a compact
convex subset C of C 0 is an (/; \Xi)-convex-relaxation of F (C
The definition of c.relax(F (/); \Xi) is quite similar to that of (/; ae)-approximation of c.hull(F )
given in Section 5 of [3]. Note that B(-; ae(-; F (/))) in the definition of c.relax(F (/); \Xi)
corresponds to the minimum ball with the center - that contains F (/). It is easily verified
that given an arbitrary open convex set U containing F , if / ? 0 is sufficiently small and
if \Xi is a sufficiently large ball with its center in C 0 , then F ae c.relax(F (/); \Xi) ae U . See
Lemma 5.1 of [3] and its proof. By definition, we also see that
We assume in the remainder of this section that there exists a finite common Lipschitz
constant for all p(\Delta) 2
If P F consists of a finite number of quadratic functions, then this assumption is satisfied.
Lemma 2.4. Let - Choose positive numbers /, - and a compact convex
set \Xi such that
where
Proof: If F (/) is empty, then the desired inclusion relation holds with
So we will deal with the case that F (/) is not empty.
(i) Define a ffi-neighborhood G of F (/) within C 0 such that
We show that c.hull(G) ae c.hull(F (ffl)). Suppose that x 2 G. Then x 2 C 0 and there
exists a y 2 F (/) such that
(by y 2 F (/) and the definition of - lip )
Thus we have shown that G ae F (ffl), which implies that c.hull(G) ae c.hull(F (ffl)).
(ii) In view of (i), it suffices to prove that
Assuming that -
x 62 c.hull(G), we show that -
x 62 c.relax(F (/); \Xi). We will construct a
ball B( -) ae R n such that
x 62 c.relax(F (/); \Xi) follows from the definition of c.relax(F (/); \Xi). Let -
be the point that minimize the distance k- x \Gamma yk over y 2 c.hull(F (/)).
yk and -
fy
yg forms a supporting
hyperplane of c.hull(F (/)) such that
y for 8y 2 c.hull(F (/)):
We will show that - ffi ? ffi. Assume on the contrary that -
y lies in c.hull(F (/)),
there are y
Let
Then we see that
d
fy
dg
This implies that -
which contradicts to the hypothesis that -
x 62 c.hull(G).
Thus we have shown that -
(iii) Now defining -
d, we show that - and the ball B( -) satisfies
(8). From the definition of - above and -
first observe that
-) (i.e., the 2nd relation of (8));
Next we will show that the third relation of (8), i.e., c.hull(F (/)) ae B( - ). Suppose
that y 2 c.hull(F (/)). Then
d) (by (10))
Note that - d -
and
are orthogonal projection matrices onto the one dimensional
line f-
Rg in R n and its orthogonal complement, respectively. Therefore, from the
above equations, we see that
which derive that
(since both
Furthermore
y
(by (10))
(by
(by (7))
(by (7))
0:
Hence
d
(by (10))
Thus we have seen that c.hull(F (/)) ae B( -):
(iv) Finally we will show that the first relation of (8), i.e.,, - 2 \Xi. From the definition
of - , We know form (6) and (7) that
Hence if we choose a y 2 c.hull(F
This implies that -
Corollary 2.5. Assume that
Let
and
satisfies the inequality (7) of Lemma 2.4. We also see
that
(by
Hence if we take
, then - satisfies (6) and the desired result follows.
3 The Spherical-SDP Model.
Throughout this section, we assume that - lip
In the Spherical-SDP Model, we take P set of quadratic functions that
induce spherical valid inequalities for C k ) at Step 1 of Algorithm 2.2. Here we say that a
quadratic valid inequality p(x) - 0 for C k is spherical if p(\Delta) : R n ! R is of the form
for 9- 2 R n and 9ae ? 0. Let fC k g be the sequence of compact convex sets generated
by Algorithm 2.2 with at every iteration. Then the sequence fC k g enjoys
properties (a) monotonicity, (b) detecting infeasibility, and (c) asymptotic convergence,
which we stated in the Introduction. See Theorem 3.1 of [2]. Among these properties, only
the monotonicity property is relevant to the succeeding discussions.
Let / be an arbitrary positive number, and \Xi an arbitrary nonempty compact convex
set containing C 0 . In Lemma 3.2, we first present an upper bound -
k for the number k of
iterations at which C k attain an (/; \Xi)-convex-relaxation of F , i.e., C k ae c.relax(F (/); \Xi)
holds for the first time. Then in Theorem 3.3, we will apply Corollary 2.5 to this bound to
derive an upper bound k   for the number k of iterations at which C k attains an ffl-convex-
relaxation of F , i.e., C k ae c.hull(F (ffl)) for the first time. Here ffl denotes an arbitrarily given
positive number.
Let j=diam(\Xi). Define
1otherwise:
By definition, we see that 0 -
Lemma 3.1. Let k 2 f0; g. For 8- 2 \Xi, define
ae (-; F
Then
Proof: It suffices to show that C k+1 ae B(-; ae 0 (-)) for 8- 2 \Xi. For an arbitrarily fixed
ae (-; F
we see that
which will be used later. If ae (-; F (/)) - ae k then ae . In this case
the desired result follows from the monotonicity, i.e., C k+1 ae C k . Now suppose that
ae (-; F . Assuming that -
obviously see that -
Hence we only need to deal with the
case that
We will show that
for 9qf(\Delta; - fl; - q; -
in 3 steps (i), (ii) and
(iii) below. Then -
x 62 C k+1 follows from Lemma 2.1.
(i) The relations in (14) imply that -
x 62 F (/). Hence there exists a
quadratic function qf(\Delta; - fl; - q; -
(ii) By the definition of ae k , we also know that the quadratic function
is a member of P S (C k ). Let p(\Delta). By the definition of - nc , all the eigenvalues of
the Hessian matrix of the quadratic function qf(\Delta; -
are not less than \Gamma- nc .
Hence (15) follows.
(iii) Finally we observe that
(by the definition of -
Thus we have shown (16).
Lemma 3.2. Suppose that diam(F ) ? 0. Define
otherwise:
k, then C k ae c.relax(F (/); \Xi).
Proof: For every - 2 \Xi and
It suffices to show that if k - k then
ae k (- ae (-; F (/)) for 8- 2 \Xi: (17)
In fact, if (17) holds, then
By Lemma 3.1,
ae k+1 (- max
ae (-; F
for
This implies that
ae k (- max
ae (-; F
for
Hence, for each - 2 \Xi, if k satisfies the inequality
then ae k (- ae (-; F (/)). When - we see that -
by definition. Hence (18)
holds for Now assume that - nc
we see that
Hence, if -
equivalently, if
then (18) holds. We also see from the definition of - ffi that
Therefore if k/
holds. Consequently we have shown that if
holds.
Now we are ready to present our main result in this section.
Theorem 3.3. Assume (11) as in Corollary 2.5 and diam(F
otherwise:
It is interesting to note that the bound k   is proportional to the nonconvexity - nc of P F ,
and k  quadratic functions in P F are almost convex.
Proof of Theorem 3.3: Choose positive numbers /, - 0 and a compact convex set
\Xi ae R n as in (12) of Corollary 2.5. Then c.relax(F (/); \Xi) ae c.hull(F (ffl)). Let
as in Lemma 3.2. By Lemma 3.2, if k - k then
On the other hand, we see that
Hence the inequality - appeared in the definition of - k can be rewritten as
We also see that
ffl=2
Therefore k
k.
4 The Rank-2 Models.
We discuss the Rank-2-SDP and the Rank-2-SILP Models simultaneously. Let
the ith unit coordinate vector in R n ;
for 8d 2 D and 8nonempty compact C ae R n ;
We define
e
Suppose that C is a subset of C 0 . Then the two terms (d T
appeared in the definition of r2f(\Delta; d 0 ; d; C) are linear supporting functions for
C, respectively, and induce linear valid inequalities for C 0 ae C and C:
respectively. Hence the minus of their product forms a rank-2 quadratic supporting function,
and induces a rank-2 quadratic valid inequality for C:
0:
In the Rank-2-SDP and the Rank-2-SILP Models of successive convex relaxation meth-
ods, we take P
k ) at Step 1 of Algorithms 2.2 and 2.3, respectively. Let fC k g
be the sequence of compact convex sets generated by Algorithm 2.2 or Algorithm 2.3 with
Then the sequence fC k g enjoys properties (a) monotonicity, (b) detecting
infeasibility, and (c) asymptotic convergence, which we stated in the Introduction. We can
prove this fact by similar arguments used in the proof of Theorem 3.3 of [3]. See also Remark
3.8 of [3]. Let ffl be an arbitrarily given positive number. We will derive an upper bound k
in Theorem 4.4 at the end of this section for the number k of iterations at which C k attains
an ffl-convex-relaxation of F . The argument of the derivation of the bound k   will proceed
in a similar way as in the Spherical-SDP Model, although it is more complicated. In the
derivation of the bound in the Spherical-SDP Model, it was a key to show the existence
of a quadratic function g(\Delta) 2 c.cone
satisfying the relations (15)
and (16). We need a sophisticated argument, which we develop in Section 4.1, to construct
a quadratic function g(\Delta) 2 c.cone
~
satisfying the corresponding
relations (25) and (26) in the Rank-2-SDP and the SILP Models.
4.1 Convex Cones of Rank-2 Quadratic Supporting Functions for
n-dimensional Balls.
In this subsection, we are concerned with c.cone
e
Note that if C k ae B(-; ae), r2f(\Delta; d
(B(-; ae)) and r2f (\Delta; d
then r2f(\Delta; d 0 ; d; B(-; ae)) induces a weaker valid inequality for C k than r2f (\Delta; d
the sense that
This fact will be utilized in our complexity analysis of the Rank-2 Models in the next
subsection. For simplicity of notation, we only deal with the case that
For
D, and
sin '
sin '
For
D,
\Gammae T
\Gammae T
Essentially the same functions as the quadratic functions f
were introduced in the paper [3], and the lemma below is a further
elaboration of Lemma 4.4 of [3] on their basic properties.
Lemma 4.1. Let ae ? 0, ng.
e
The Hessian matrix of the quadratic function f
coincides with
the n \Theta n matrix
.
\Gamma The Hessian matrix of the quadratic function f \Gamma
coincides with
the n \Theta n matrix \Gamma
.
(iii) Suppose that ffi 2 [0; 1] and ffiaew 2 C 0 . Then
(iv) Suppose that - 0,
Proof: We will only show the relations on f
because we can derive the
corresponding relations on
similarly. First, assertion (i) follows directly
from the definitions (19).
. The Hessian matrix of the quadratic function f
turns out
to be the symmetric part of the matrix
sin '
\Gamma(w
sin '
\Gamma2(sin ')(e i e T
Thus we have shown (ii)
(iii) By definition, we have that
(w
\Gammae T
(w cos
We will evaluate each term appeared in the right hand side. We first observe that
where the last inequality follows from
Hence
Similarly
Since ffiaew 2 C 0 , we also see that
Therefore
sin '
sin '
sin '
Here ~
(iv) We see from (iii) that
4.2 Complexity Analisys.
In the remainder of the section, we assume that - lip
1. Let fC k g be the sequence of compact convex sets generated by either Algorithm 2.2 or
Algorithm 2.3 with taking
k ) at each iteration. Let / be an arbitrary positive
number, and \Xi an arbitrary compact convex set containing C 0 . In Lemma 4.3, we derive an
upper bound - k for the number k of iterations at which C k attains a (/; \Xi)-convex-relaxation
of F , i.e., C k ae c.relax(F (/); \Xi) holds for the first time. Then we will combine Lemmas 2.4
and 4.3 to derive an upper bound k   for the number k of iterations at which C k attains an
ffl-convex-relaxation of F . Here ffl denotes an arbitrarily given positive number.
Let j=diam(\Xi). Define
2/
It should be noted that -
- and -
' are not greater than 8
and -
8 , respectively, and also that
By definition, we see that
Lemma 4.2. Let k 2 f0; g. For 8- 2 \Xi, define
ae (-; F
Then
Proof: It suffices to show that C k+1 ae B(-; ae 0 (-)) for 8- 2 \Xi. For an arbitrarily fixed
ae (-; F
We may assume without loss of generality that Algorithms 2.2 and 2.3 with
taking
k ) at each iteration are invariant under any parallel transformation. See
[3] for more details. Since we see that
which will be used later. If ae (0; F (/)) - ae k then ae . In this case the
desired result follows from C k+1 ae C k . Now suppose that ae (0; F Assuming
that -
derive that -
x 62 C k , we obviously see -
because C k+1 ae C k . Hence we only need to deal with the case that
We will show that
for 9qf(\Delta; - fl; - q; -
steps (i), (ii) and (iii) below. Since
x 62 C k+1 in both cases of the Rank-2-SDP Model (Algorithm
2.2) and the SILP Model (Algorithm 2.3).
(i) The relations in (24) imply that -
x 62 F (/). Hence there exists a
quadratic function qf(\Delta; - fl; - q; -
x=k- xk, and . Then we see that
We will represent the symmetric matrix -
Q as the difference of two n \Theta n symmetric
matrices -
nonnegative elements such that
For 8x 2 R n ,
\Gammae T
\Gammae T
w) and f \Gamma
are defined as in (19). By construction, g(\Delta) 2
e
We also see that g(\Delta) has the same Hessian matrix -
Q as f(\Delta) does.
4.1. Hence the Hessian matrix of the quadratic function g(\Delta)
vanishes. Thus we have shown (25).
(iii) Finally we observe that
(by (iv) of Lemma 4.1)
- \Gamma/ (by (22)):
Therefore
Lemma 4.3. Suppose that diam(F ) ? 0. Define
k, then C k ae c.relax(F (/); \Xi).
Proof: For every - 2 \Xi and
It suffices to show that if k - k then
ae k (- ae (-; F (/)) for 8- 2 \Xi: (28)
In fact, if (28) holds, then
By Lemma 4.2,
ae k+1 (- max
ae (-; F
This implies that
ae k (- max
ae (-; F
for
Hence, for each - 2 \Xi, if k satisfies the inequality
then ae k (- ae (-; F (/)). When - nl - /
by (21) that -
Hence
(28) holds for Now assume that - nl ?
we see that
Hence, if -
equivalently, if
then (29) holds. We also see by the definition of -
and (20) that
0:
Therefore if k
holds. Consequently we have
shown that if k -
holds.
Theorem 4.4. Assume (11) as in Corollary 2.5 and diam(F
Note that the bound k   is proportional to the square of the nonlinearity - nl of P F , and
also that k  any function in P F is almost linear.
Proof of Theorem 4.4: Choose positive numbers /, - 0 and a compact convex set
\Xi ae R n as in (12) of Corollary 2.5. Then c.relax(F (/); \Xi) ae c.hull(F (ffl)). Let
as in Lemma 4.3. By Lemma 4.3, if k - k then
On the other hand, we see that
(by
Hence the inequality - nl - /
appeared in the definition of - k can be rewritten
as
We also see that
ffl=2
Therefore k
k.
Concluding Discussions.
(A) In the Spherical-SDP Model, we have assumed that every ball with a given center
that contains the kth iterate C k is available. This assumption is equivalent to the
assumption that for a given - 2 R n , we can solve a norm maximization problem
subject to x 2
In fact, if we denote the maximum value of this problem by ae(-; C k ), then we can represent
the set of all balls containing C k as
and consists of the spherical quadratic functions p(\Delta;
We can also observe from the argument in Section 3 that among the spherical quadratic
functions in P S (C k ), only the supporting spherical quadratic functions p(\Delta; -; ae(-; C k
are relevant in constructing the next iterate C
In the Rank-2-SDP and the Rank-2-SILP Models, we have assumed that the maximum
value ff(d; C k ) of the linear function d T x over x 2 C k is available for every d 2 D. From
the practical point of view, the latter assumption on the Rank-2-SDP and the Rank-2-
SILP Models looks much weaker than the former assumption on the Spherical-SDP Model
because a maximization of a linear function d T x over C k is a convex program while the
norm maximization problem (30) is a nonconvex program. But the latter assumption still
requires to know the maximum value ff(d; C k ) for 8d in the set D consisting of infinitely
many directions, so that these models are not implementable yet. Kojima and Tun-cel [3]
proposed discretization and localization techniques to implement the Rank-2-SDP and the
Rank-2-SILP Models, and Takeda, Dai, Fukuda and Kojima [9] reported numerical results
on practical versions of the Rank-2-SILP Model.
In Section 4, we have focused on the Rank-2-SILP Model and diverted its complexity
analysis to the Rank-2-SDP Model since the SDP relaxation is at least as tight as the semi-infinite
relaxation. But this is somewhat loose. In particular, we should mention one
important difference between the upper bounds required to attain an ffl-convex-relaxation of
F in Theorems 4.4 and 3.3: the upper bound in Theorems 4.4 depends on the nonlinearity
while the upper bound in Theorem 3.3 depends on the nonconvexity - nc (P F )
but not on the nonlinearity - nl . This difference is critical when all the quadratic functions
are convex but nonlinear. Here we state a complexity analysis on the Rank-2-SDP Model
which leads to an upper bound depending on the nonconvexity - nc of P F but not on the
nonlinearity - nl of P F .
' and ffi as
':
By definition, we see that - 0, 1 -
It is easily
seen that the assertion of Lemma 4.2 remains valid with the definition above. The proof is
quite similar except replacing the quadratic function g(\Delta) in (27) by
ii
By using similar arguments as in Lemma 4.3, Theorem 4.4 and their proofs, we consequently
obtain the following result: Assume (11) as in Corollary 2.5 and diam(F
Note that now the bound k   is proportional to the square of the nonconvexity - nc of P F ,
and also that k  quadratic functions in P F are almost convex.



--R

"A lift-and-project cutting plane algorithm for mixed 0-1 programs,"
"Cones of matrices and successive convex relaxations of nonconvex sets,"
"Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization problems,"
"Moderate


"A reformulation-convexification approach for solving nonconvex quadratic programming problems, "
"Dual quadratic estimates in polynomial and boolean programming,"
"Towards the Implementation of Successive Convex Relaxation Method for Nonconvex Quadratic Optimization Prob- lems,"
Convex analysis and
--TR

--CTR
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
global optimization;convex relaxation;complexity;nonconvex quadratic program;semidefinite programming;sdp relaxation;lift-and-project procedure