Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming.
The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities (LMI's). In particular, we show that our approach leads to a polynomial-time approximation scheme for the standard quadratic optimzation problem. This is an improvement on the previous complexity result by Nesterov who showed that a 2/3-approximation is always possible. Numerical examples from various applications are provided to illustrate our approach.
Introduction
A standard quadratic optimization problem (standard QP) consists of nding global minimizers of a
quadratic form over the standard simplex, i.e. we consider global optimization problems of the form
x > Qx (1)
where Q is an arbitrary symmetric n  n matrix; a > denotes transposition; and  is the standard
simplex in the n-dimensional Euclidean space IR n ,
denotes the non-negative orthant in IR n . To avoid trivial cases,
we assume throughout the paper that the objective is not constant over , which means that fQ; En g
are linearly independent where ee > is the n  n matrix consisting entirely of unit entries, so
that x > on . For a review on standard QPs and its applications, see [3]. We
only mention here that this problem is known to be NP-hard, and contains the max-clique problem
in graphs as special case.
Note that the minimizers of (1) remain the same if Q is replaced with Q+
En where
is an arbitrary
constant. So without loss of generality assume henceforth that all entries of Q are non-negative.
Furthermore, the question of nding minimizers of a general quadratic function x > Ax
can be homogenized considering the rank-two update ce > in (1) which has the same
objective values on .
ISDS, Universitat Wien, Austria. E-mail: immanuel.bomze@univie.ac.at
y Faculty of Information Technology and Systems, Delft University of Technology, P.O. Box 5031, 2600 GA Delft,
The Netherlands. E-mail: E.deKlerk@ITS.TUDelft.NL
In this paper we will show how to derive approximation guarantees for this problem via semidenite
programming (SDP). The main idea is as follows: we can give an exact reformulation of the standard
quadratic optimization problem as a copositive programming problem, and subsequently approximate
the copositive cone using either linear inequality systems, yielding LP relaxations; or, more rened,
systems of linear matrix inequalities (LMI's), yielding an SDP formulation. Both SDP and copositive
programming problems are examples of conic programming problems, and we begin by reviewing these
concepts.
1.1 Preliminaries; conic programming
We dene the following convex cones:
The n  n symmetric matrices:
the n  n symmetric positive semidenite matrices:
the n  n symmetric copositive matrices:
the n  n symmetric completely positive matrices:
the n  n symmetric nonnegative matrices:
the n  n symmetric doubly nonnegative matrices:
We consider the usual inner product hX; Y i := Tr(XY ) on Sn and recall that the completely positive
cone is the dual of the copositive cone, and that the nonnegative and semidenite cones are self-dual
with respect to this inner product. Furthermore, the dual cone of Dn is D
a cone which
is contained in Cn and which will play an important role in the relaxations to follow.
For a given cone K and its dual cone K  we dene the primal and dual pair of conic linear programs:
(D) d  := sup y
(2)
If
n we refer to semidenite programming, if to linear programming, and if
copositive programming.
The well-known conic duality theorem, see, e.g., [15], gives the duality relations between (P ) and (D).
Theorem 1.1 (Conic duality theorem) If there exists an interior feasible solution X
of (P ), and a feasible solution of (D) then p and the supremum in (D) is attained. Similarly,
if there exist y
feasible solution of (P ), then
the inmum in (P ) is attained.
As is well known [10], optimization over the cones S
n and Nn can be done in polynomial time (to
compute an -optimal solution), but copositive programming is NP-hard, as we will see in the next
section.
1.2 Standard quadratic optimization via copositive programming
In [4] it is shown that we can reformulate problem (1) as the copositive programming problem
Problem (3) is called a copositive program because of its dual formulation
(note that the optimal values of both (3) and (4) are attained and equal due to Theorem 1.1; see [4]).
The reformulation makes it clear that copositive programming is not tractable (see e.g. [16, 4]). In
fact, even the problem of determining whether a matrix is not copositive is NP-complete [9].
In [4], some ideas from interior point methods for semidenite programming are adapted for the
copositive programming case, but convergence cannot be proved. The absence of a computable self-
concordant barrier for this cone basically precludes the application of interior point methods to copos-
itive programming.
A solution to this problem was recently proposed by Parillo [12], who showed that one can approximate
the copositive cone to a given accuracy by a suciently large set of linear matrix inequalities. In other
words, each copositive programming problem can be approximated to a given accuracy by a suciently
large SDP. Of course, the size of the SDP can be exponential in the size of the copositive program.
In the next section we will review the approach of Parillo, and subsequently work out the implications
for the copositive formulation of the general quadratic optimization problem by applying the
approach of De Klerk and Pasechnik [5]. The basic idea is to replace the copositive cone in (4) by an
approximation: either a polyhedral cone or a cone dened by linear matrix inequalities. In this way
we obtain a tractable approximation problem.
2 Approximations of the copositive cone
Since any y 2 IR n
can be written as indicates the componentwise
(Hadamard) product, we can represent the copositivity requirement for an (n  n) symmetric matrix
M as
There are many possible representations of the polynomial P as a homogeneous polynomial of degree
four, if we allow for nonzero coecients of terms like
In particular, if we represent
M is a symmetric matrix of order n+ 1n(n 1),
then f
M is not uniquely determined. The non-uniqueness follows from the identities:
It is easy to see that the possible choices for f
dene an ane space (see below for a closer description
of that space).
2.1 Sum-of-squares decompositions
Condition (5) will certainly hold if the polynomial P can be written as a sum of squares (s.o.s., in
for some polynomial functions f sum of squares decomposition is possible if
and only if a representation of P (x) exists where f
M in (6) is positive semidenite. We will show
this for any homogeneous polynomial of degree 2r below, but introduce some convenient notation
beforehand: for any x 2 IR n and any multi-index m 2 IN n
(with IN
i the corresponding monomial of degree jmj. Also, denote
by I n
sg the set of all possible exponents of monomials of degree s (there are
s
of them) and, as usual, 2I n (s)g. Finally, given a set of multi-indices
I , we dene [x] m2I as the vector with components x m for each m 2 I .
Lemma 2.1 If
P (x) is a homogeneous polynomial of degree 2s in n variables
has a representation
l
for some polynomials f i (x) then there are polynomials h i (x) which are homogeneous of
degree s for all i such that
P has a s.o.s. representation
as above if and only if there is a symmetric positive-semidenite matrix d  d matrix f
d such
that
s
and e
Proof: It is easy to see that the degree of f i is at most s for each i: if we assume to the contrary
that f j has maximal degree of all f i and its degree exceeds s, then the square of its leading term which
appears in the s.o.s. will never cancel out, since there can be no monomials of the same degree with
negative coecients.
We can therefore decompose each f i as f is homogeneous of degree s (or zero, but
without loss of generality we assume that this happens only if t < i  l, including the possibility of
and the degree of g i is less than s. Now
that g has degree less than 2s while h, as
P itself, is homogeneous
of degree 2s. Thus
that any homogeneous h i can be
written as h i
a i a >
d . The
converse is obvious via spectral decomposition of f
Next let us characterize all the matrices f
which allow for a representation
x >f Me x for
a given homogeneous polynomial
Lemma 2.2 Let
2m be a homogeneous polynomial of degree 2s in n variables
d as in Lemma 2.1. Then
only
if
(j;k)2[I
f
(j;k)2[I
f
Proof: Observe that f
. The assertion now follows by equating the corresponding
coecients of the polynomials e x >f Me x and
Parillo showed [12] that P (x) in (5) allows a sum of squares decomposition if and only if M
which is a well-known sucient condition for copositivity. For completeness of presentation, we give
a new proof here, which follows easily from the preceding lemmas.
Let us dene the cone K 0
n , the cone dual to that of all doubly nonnegative matrices.
Theorem 2.1 (Parillo [12]) P allows for a polynomial s.o.s. if and only if
Proof: In this case, the degree 2s of P equals four, so that Obviously,
A 2e i
of M . Therefore Lemma 2.2 yields
f
M is assumed to
be symmetric. Note that we may and do assume that f
M is positive-semidenite by Lemma 2.1. Now
diagonal elements of f
cannot be negative. Further,
for all i; j, which means that S is
a principal submatrix of the positive-semidenite matrix f
M . Hence also S
n , which shows the
necessity part of the assertion. To establish suciency, observe that (x  x) > S(x  x) is, by spectral
decomposition of S, even a s.o.s. in the variables z
obviously a s.o.s. Hence (x  x) > M(x  x) is, as the sum of two s.o.s. decompositions, itself a s.o.s. 2
Higher order sucient conditions can be derived by considering the polynomial:
and asking when P (r) (x) has a sum of squares decomposition. It is clear from Lemma 2.1 that the
set of matrices M which satisfy this condition forms a convex cone.
Denition 2.1 (De Klerk and Pasechnik [5]) The convex cone K r
n consists of the matrices for
which P (r) (x) in (10) allows a polynomial sum of squares decomposition.
Obviously, these cones are contained in each other: K r
n for all r. This follows from
By explicitly calculating the coecients Am (M) of the homogeneous polynomial P (r) (x) of degree
summarizing the above auxiliary results, we arrive at a characterization of K r
n which has
not appeared in the literature before.
Theorem 2.2 Let n; r 2 IN and
. Further, abbreviate m(i;
and introduce the multinomial coecients
For a symmetric matrix M 2 Sn , dene
n if and only if there is a symmetric positive-semidenite dd matrix f
d such that
(j;k)2[I
f
(j;k)2[I
f
Proof: By the multinomial law,
c(k)x 2k
The last identity follows by setting Hence Am (M) as given by (12) are the coecients
of P (r) , and the assertions follow by observing with the help of Lemma 2.1 and Lemma 2.2. 2
The following auxiliary result simplies the expressions Am (M) considerably.
Lemma 2.3 Let M be an arbitrary n  n matrix, and denote by diag the vector
obtained by extracting the diagonal elements of M . If Am (M) is dened as in (12), then
diag M
for all m 2 I n
Proof: Note that by denition, c(m(i; case i 6= j while even c(m(i;
so that nonzero coecients of M ij occur only for some (i; pairs depending on m. Hence
straightforward calculation shows, using
which exactly corresponds to (15). 2
Observe that for we have, from m >
Parillo [12] showed that M 2 K 1
n if the following system of linear matrix inequalities has a solution.
where M (i) 2 Sn for
The converse is also true: if M 2 K 1
n then the system of LMI's (17){(20) has a solution; this was used
by De Klerk and Pasechnik [5] without giving a rigorous proof. We will now give a complete proof,
by using our new characterizations of the cones K r
n in Theorem 2.2 for 1. Note that
in this case. We will use a shorthand notation where ijk as a subscript indicates the multi-index
Theorem 2.3 M 2 K 1
n if and only if there are n symmetric nn matrices M (i) 2 Sn for
such that the system of LMI's (17){(20) is satised.
Proof: First assume that M 2 K 1
. By Theorem 2.2 there exists a f
d satisfying (13) such
that
where e
By (15), we have A iii
n. Similarly, the left-hand sides of (13) read in case
f
f
f
Now put S (i)
M ijj;ikk for all triples (ijk). Then S (i)
since it is a principal submatrix of the
positive-semidenite matrix f
M . Hence setting M we see that condition (17) is satised.
It remains to show that (18){(20) hold. Now
and similarly
ii 2S (i)
whereas
f
f
because the diagonal entries of f
M cannot be negative. Thus we have constructed a solution to the
system of LMI's (17){(20).
Conversely, assume that a solution to (17){(20) is given. Observe that
The rst sum is obviously a s.o.s., since M M (i)
n for every i. The second sum can likewise be
written as a s.o.s. because of
i<j<k
ii x 3
i<j<k
rh
where we have used the non-negativity condition (20) to obtain the last equality. Note that the rst
two sums of the last expression vanish due to (18) and (19). Thus P (1) (x) is represented as a s.o.s. 2
By closer inspection of the preceding proof we see that the condition (17) can be relaxed, to arrive at
a (seemingly) less restrictive system of LMI's, namely:
Indeed, the rst sum in (22) is still a s.o.s., since M M (i)
n for every i, and because
of Theorem 2.1. Hence (24){(27) constitute an alternative characterization of K 1
n , which in the next
section will turn out to be quite insightful. There we will also specify an (apparently) even more
relaxed characterization of K 1
n , see (40)|(43) in Subsection 2.2 below. With slightly more eort, one
could derive similar systems of LMI's for the cones K r
2. However, d then increases so rapidly
with n (recall that that the resulting problems become too large for current SDP solvers
| even for small values of n.
We therefore change our perspective in the next subsection, to arrive at a series of LP approximations
of the copositive cone. These approximations are weaker than the SDP ones, but can be solved more
easily.
2.2 LP relaxations yielded by nonnegativity
We start with a simple observation: If the polynomial P (r) (x) has only nonnegative coecients, then
it is already allows a sum-of-squares decomposition. This motivates the following denition.
Denition 2.2 (De Klerk and Pasechnik [5]) The convex cone C r
n consists of the matrices for
which P (r) (x) in (10) has no negative coecients. Hence for any r, we have C r
Again, we obviously have C r
n for all r. We can immediately derive a polyhedral representation
of the cones C r
this characterization has not appeared in the literature.
Theorem 2.4 For any m 2 IR n , dene Diag m as the n  n diagonal matrix containing m as its
diagonal, i.e., satisfying diag (Diag m) = m. Then for all r 2 IN 0 and n 2 IN,
Proof: Follows from (14) in Theorem 2.2 and Lemma 2.3, with the help of the basic relations
Note that C 0
n if and only if M 2 Sn with
This follows from Theorem 2.4 by the same arguments as in Theorem 2.3. We can also establish an
alternative characterization of C 1
n similar to that in Theorem 2.3:
Theorem 2.5 M 2 C 1
n if and only if if and only if there are n symmetric n  n matrices M (i) 2 Sn
such that the following system of linear inequalities has a solution:
Proof: Suppose that M 2 C 1
n and dene N (i)
jk as follows:
Then N (i) 2 Sn and because of (28) and (29) we get N (i) 2 Nn . Further, M
Finally, (30) implies (34) because M (i)
contains three distinct elements due to the
denition of N (i) . The converse follows as in the proof of Theorem 2.3, without taking square roots
in (23). 2
By comparing (31){(34) to (24){(27) we see that merely S
in (24) has been shrunk to Nn
in (31). This re
ects the fact that C 1
Further, the two equalities (32) and (33) can be replaced with inequalities, without changing the
characterization:
n if and only if there are n symmetric nn matrices M (i) 2 Sn for
such that the following system of linear inequalities has a solution:
Similarly, also M 2 K 1
n if and only if there are n symmetric n  n matrices M (i) 2 Sn for
such that the following system of LMI's has a solution:
ii  0;
Indeed, we may use non-negativity via (41), (42) and (43) in (23) to obtain the desired s.o.s. decomposition
there, and an analoguous argument without taking square roots applies to establish suciency
of (36)|(39).
Every strictly copositive matrix M lies in some cone C r
suciently large; this follows from a
famous theorem of Polya [13]. In summary, we have the following theorem.
Theorem 2.6 (De Klerk and Pasechnik [5]) Let
n +Nn be strictly copositive. Then there
are integers r K (M) and r C (M) with 1  r K (M)  r C (M) < +1, such that
for all r  r K (M) while
n , and similarly
for all r  r C (M) while
n .
The rst part of the theorem (concerning the cones K r
already follows from arguments by Parillo
[12].
In order to bound the number r C (M) from above we need the following result from De Klerk and
Pasechnik [5], which in turn is a consequence of a result of Powers and Reznick [14].
Theorem 2.7 (De Klerk and Pasechnik [5]) If a symmetric (n  n) matrix M is strictly copos-
itive, the function
has no negative coecients, and hence allows for a sum of squares decomposition, if
r > L= 2;
where
and
z > Mz: (45)
In other words, if a strictly copositive matrix M satises L= 1  r for some integer r, where L and
are respectively dened in (44) and (45), then M 2 C r
equivalently,
r K (M)  r C (M)  dL= 1e :
Note that  is a 'condition number' of M which can be arbitrarily small in general, and which is
NP-hard to compute.
3 Approximation results
In this section we consider families of LP and SDP approximations to p
prove a bound on the quality of these approximations.
3.1 LP-based approximations
Let us dene:
for which has dual formulation
Note that problem (47) is a relaxation of problem (4) where the copositive cone is approximated by
n . It therefore follows that p (r)
C  p  for all r. We now provide an alternative representation of p (r)
C .
This representation uses the following rational grid which approximates the standard simplex:
r+2 I n (r fy
A naive approximation of problem (1) would be
The next theorem shows that there is a close link between p (r)
C and the naive approximation p (r) . In
particular, one can obtain p (r)
C in a similar way as the naive approximation p (r) is obtained, i.e. by
only doing function evaluations at points on the grid (r).
Theorem 3.1 For any r 2 IN 0 consider the rational discretization (r) of the standard simplex
from (48). If Q is an arbitrary symmetric n  n matrix and q
r+2 diag Q, then
Proof: First we use the representation of C r
n from Theorem 2.4, putting
observing that from (15) and (16),
diag Q
Then by (47) we have
diag Q
which gives (49) by putting
3.2 SDP-based approximations
Similarly as in the denition of p (r)
C , we can dene SDP-based approximations to p  using the cones
n instead of C r
for which has dual formulation
It may not immediately be clear that the optimal values in (50) and (51) are attained and equal.
However, this follows from Theorem 1.1 by noting that
feasible in problem
(50) as well as strictly completely positive and therefore in the interior of (K r
similarly, feasible solution of (51) in the interior of K 0
n , and consequently in the
interior of K r
n for all
Note that p (r)
C for all
n .
3.3 A bound on the quality of approximation
We will show that the dierence p  p (r)
C can be bounded in terms of r and of the range Qmax Q min
of the data, where we put
Recall that we assumed linear independence of fQ; En g which implies in particular Q min  p  < Qmax
(indeed, otherwise we got 0  z > (QmaxEn Q)z  Qmax p which were only
possible
Theorem 3.2 Consider an instance of the standard quadratic optimization problem (1). For a given
integer r  1, dene p (r)
C as in (47), and Qmax and Q min as in (52). One has
Proof: First note that the assertion is trivial in the exact case p (r)
whence we assume that
in the sequel. Further, as Q Q min En 2 Nn  C r
C  Q min . Next,
without loss of generality we may and do assume that p  Qmin
if the contrary were
the case, then we are done because of
If now p  Qmin
holds, then in particular necessarily p  > Q min . Let us consider the
function
which is continuous, positive and strictly increasing on the interval [Q min
while '(p) % +1 as p % p  . Hence there is a  p 2]Q min ; p  [ such that
pEn .
We claim that M 2 C r
. To this end, we proceed to bound the parameters  and L in Theorem 2.7
for this matrix M :
z
z > Qz
and also
Hence
and by Theorem 2.7, we obtain M 2 C r
n . Invoking again (47), we deduce
C < p  . Now ' is
increasing, thus
'(p (r)
Finally, the obvious relation Qmax Q min  maxfQmax p (r)
yields
'(p (r)
which in turn immediately implies the assertion via (54). 2
Finally we notice that a direct derivation of this approximation result via the alternative grid representation
in Theorem 3.1 does not seem to be straightforward.
4 Comparison with known approximation results
Consider the generic optimization problem:
:=
for some nonempty, bounded convex set S, and let
Denition 4.1 ([11]) A value approximates   with relative accuracy  2 [0; 1] if
We say approximates   with relative accuracy  2 [0; 1] in the weak sense if
The approximation is called implementable if    .
It is known from Bellare and Rogaway [1] that there is no -approximation of the optimal value of
the problem

for some  2 0; 1 in the weak sense, unless
Using semidenite programming techniques, the problem

can be approximated with the relative accuracy (1 O(1= log(n))), see [11] and the references therein.
Note the the standard quadratic optimization problem (1) is a special case of this problem where
we pass from minimization to maximization. The result in Theorem 3.2 can be restated
as: p (r)
C is a -approximation of p  in the weak sense for
r  Qmax Q min
1:
Thus p (r)
C is only a polynomial-time -approximation of p  for instances where Qmax Q
4.1 Special case: the maximal stable set problem
E) be a simple graph and let (G) denote its stability number (cardinality of the largest
stable set). It is known from Motzkin-Straus [8] (see also De Klerk and Pasechnik [5])
x
where A is the adjacency matrix of G and I n denotes, as usual, the n  n identity matrix.
The stability number (G) cannot be approximated in polynomial time to within a factor jV j 1
2  for
any  > 0 unless or within a factor jV j 1  for any  > 0 unless
If we denote I n and dene
C is dened in (46), then we may assume
without loss of generality  (r)  2 (assume G is not a complete graph). This means p (r)
2 and
hence with and ' from (53), we get
(p  p (r)
Now we apply the inequality (54), to arrive at(G) (r)
(r)
If we set then we can rewrite (56) as the equivalent inequality, by isolating  (r)
and subtracting (G):
Hence we get  (r) (G) < 1 which implies b (r)
This was the main result by De Klerk and Pasechnik [5]; in other words, Theorem 3.2 generalizes this
result.
5 Examples
Here we give some examples for problems of various origin.
Example 5.1 Consider an instance of the standard quadratic optimization problem (1), where the
matrix Q is given by:
This example corresponds to computation of the largest stable set in a pentagon (see Section 4.1 and
[5]). We have p (0)
5  0:44721, and p (1)
1. The proof that p (1)
1requires the observation that the matrix
is known to be in K 1
(but it is not in K 0
n +Nn ); for a proof, see [12].
Example 5.2 Consider an instance of the standard quadratic optimization problem (1), where the
matrix Q is given by:
This example corresponds to computation of the largest stable set in the complement of the graph
dened by the skeleton of a dodecahedron (see Section 4.1 and [5]). Here p
0:309 but the
approximation yield the trivial lower bound: p (1)
This example shows that { even though the
approximation p (1)
is much more expensive to compute than p (1)
(see Section { it can yield a much
better lower bound on p  . This example | rst considered in [5] | is the smallest problem we know
where the p (1)
approximation to p  is not exact. It remains an open problem to nd the smallest value
of n where the p (1)
K approximation to p  is not exact.
Example 5.3 This example is from a mathematical model in population genetics [18], where, among
others, the following matrix 410A is considered:
and the objective is to maximize x >
Qx subject to x 2 . There are 5 dierent local solutions to
this problem. The globally optimal value here is 16 1which corresponds to
changing to a minimization problem of the form (1) with a nonnegative coecient matrix, we obtain the
upper bound 21 for the optimal value via computation of p (1)
, while the approximation via computation
of p (1)
K is exact.
Example 5.4 This example deals with portfolio optimization and is taken from Berkelaar et al. [2].
Here, x 2  corresponds to a portfolio: x i is the fraction of your capital to be invested in investment i.
Given a portfolio x 2  there is a risk x >
Qx associated with the portfolio which should be minimized,
and an expected return r > x to be maximized. An example from [2] has data:
0:82 0:23 0:155 0:013 0:314
0:23 0:484 0:346 0:197 0:592
0:155 0:346 0:298 0:143 0:419
0:013 0:197 0:143 0:172 0:362
and
(note that the matrix
Q is not positive semidenite). We can formulate this (multi-objective) problem
in the form (1) as follows:
min x2
x >
for some parameter c > 0 measuring risk-aversion; this problem is now of the form (1) if we set
. For
K  0:4839 and p (1)
yields the objective value 0:3015, which suggests that the SDP relaxation is exact.
6 Numerical results
We rst compare the LP approximation p (1)
C of p  with the stronger approximation p (1)
K .
To this end, we generated 1000 instances of (1) with and where the matrices Q are symmetric
with entries uniformly distributed in [0; 1].
In

Figure

1 we show a histogram with the 'distribution' of the ratios p (1)
K for the 1000 test
problems. Note that in about 3
4 of the cases the ratio is (close to) unity. This shows that the LP-based
approximations are comparable to the SDP ones in this sense. However, the computation of
C is much cheaper than that of p (1)
K | in

Table

some typical solution times are given for growing
values of n. In all cases the computer used was a Pentium II (450 MHz). The LP and SDP solver was
SeDuMi [17] by Jos Sturm running under Matlab 5.3.
K (sec)
25 4.12 not run
6.86 not run
11.2 not run
40 26.5 not run

Table

1: Typical CPU times for solving the respective LP and SDP relaxations for growing n.
The next set of experiments we performed was to approximate the stability number of random graphs
by computing the p (1)
and p (1)
approximations to the optimal value of problem (55). For this purpose
we generated 20 graphs on 12 vertices to have stability number 6. The edges outside the maximal
of LP:SDP approximation

Figure

1: Histogram showing the distribution of the ratio p (1)
K approximation values for 1000
random instances of (1) with
stable set were generated at random with the probability of including an edge between two given
vertices outside the maximal stable set being 1. In all cases the p (1)
approximation was exact while
the p (1)
approximation gave the trivial zero lower bound. 1 This indicates that Example 5.2 is quite
special | it is dicult to nd a graph on 12 vertices where p (1)
K does not give the stability number.
It also shows that | although the p (1)
C approximation is quite useful for random instances of (1) | it
fails for most maximum stable set problems.
Conclusions
We have suggested a novel approach to approximating the optimal value of the standard quadratic
optimization problem (1) | the problem (1) is rst rewritten as a copositive programming problem,
and subsequently the copositive cone is approximated by using systems of linear or linear matrix
inequalities. The resulting approximations are therefore LP's or SDP's, depending on which approximation
scheme is used. Higher order approximations are also possible, where the resulting LP's and
SDP's become larger, but the approximation is also provably better. In particular, we have quantied
the quality of the approximation as a function of the order of approximation (Theorem 3.2).
Moreover, we have presented numerical evidence showing the quality of the approximations.

Acknowledgement

The authors would like to thank Kees Roos for his comments on a draft version of this paper.
1 It is possible to see a priori that the p
(1)
approximation will be useless, by using Theorem 2.4; see also De Klerk
and Pasechnik [5].



--R

The complexity of approximating a nonlinear program.
Sensitivity analysis in (degenerate) quadratic programming.
On standard quadratic optimization problems.

Approximation of the stability number of a graph via copositive programming.
Improved approximation algorithms for maximum cut and satis
Clique is hard to approximate within jV 1
Maxima for graphs and a new proof of a theorem of T
Some NP-complete problems in quadratic and linear programming
Interior point methods in convex programming: theory and applications.
Nonconvex quadratic optimization.
Structured Semide

A new bound for P
A mathematical view of interior-point methods in convex optimization
Copositive relaxation for general quadratic programming.
Using SeDuMi 1.02
Patterns of ESS's I.
--TR

--CTR
Kurt M. Anstreicher , Samuel Burer, D.C. Versus Copositive Bounds for Standard QP, Journal of Global Optimization, v.33 n.2, p.299-312, October   2005
E. Klerk , D. V. Pasechnik, A linear programming reformulation of the standard quadratic optimization problem, Journal of Global Optimization, v.37 n.1, p.75-84, January   2007
Etienne de Klerk , Monique Laurent , Pablo A. Parrilo, A PTAS for the minimization of polynomials of fixed degree over the simplex, Theoretical Computer Science, v.361 n.2, p.210-225, 1 September 2006
linear matrix inequalities;approximation algorithms;stability number;standard quadratic optimization;semidefinite programming;copositive cone