On Copositive Programming and Standard Quadratic Optimization Problems.
A standard quadratic problem consists of finding global maximizers of a quadratic form over the standard simplex. In this paper, the usual semidefinite programming relaxation is strengthened by replacing the cone of positive semidefinite matrices by the cone of completely positive matrices (the positive semidefinite matrices which allow a factorization FFT where F is some non-negative matrix). The dual of this cone is the cone of copositive matrices (i.e., those matrices which yield a non-negative quadratic form on the positive orthant). This conic formulation allows us to employ primal-dual affine-scaling directions. Furthermore, these approaches are combined with an evolutionary dynamics algorithm which generates primal-feasible paths along which the objective is monotonically improved until a local solution is reached. In particular, the primal-dual affine scaling directions are used to escape from local maxima encountered during the evolutionary dynamics phase.
Introduction
A standard quadratic problem (standard QP) consists of nding global maximizers of a
quadratic form over the standard simplex, i.e. we consider global optimization problems
of the form
subject to x 2  ; (1)
Paper presented at the GO99 conference, Firenze, Sept. 28{Oct. 2, 1999. I.M.B. and M.D. thank
M. Locatelli and F. Schoen for their hospitality and perfect organization. Large part of the work was
done while T.T. was working at TU Delft.
c
1999 Kluwer Academic Publishers. Printed in the Netherlands.
I.M. Bomze, M. Dur, E. de Klerk, C. Roos, A. Quist, T.
where A 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 (of course, the
region fy 2 IR n
can always be represented by   IR n+1 , introducing a slack
variable). To avoid trivial cases, we assume throughout the paper that the objective is
not constant over , which means that fA; Eg are linearly independent where
is the n  n matrix consisting entirely of unit entries, so that x >
. For a review on standard QPs and its applications, which also oers a justication
for terminology see [9].
Note that the maximizers of (1) remain the same if A is replaced with A
where
is an arbitrary constant. So without loss of generality assume henceforth that
all entries of A are non-negative. Furthermore, the question of nding maximizers of a
general quadratic function x > Qx can be homogenized in a similar way
by considering the rank-two update ce > in (1) which has the same
objective values on .
Of course, quadratic optimization problems like (1) are NP-hard [23]. Nevertheless,
there are several exact procedures which try to exploit favourable data structures in a
systematic way, and to avoid the worst-case behaviour whenever possible. One example
for this type of algorithms is specied in this paper: the proposed procedure exploits
extensively the special structure of a standard QP (e.g., that the feasible set is the
standard simplex), as opposed to the general formulation of a quadratic problem.
This article is organized as follows: Section 2 contains a concise exposition of primal
and dual problems in copositive programming which involves copositive rather than
positive-semidenite matrices, using an explicit characterization of the dual cone of
the convex, non-polyhedral cone of all copositive matrices. We also shortly treat the
(relaxation of copositive programming to) all-quadratic problems on the simplex as
considered in [41]. In Section 3, this will be then specialized to be applied to standard
QPs, which enjoy the property that the copositive programming relaxation becomes
an exact reformulation of (1). Here the dual is in fact a univariate copositive-feasibility
problem which can be seen as a straightforward generalization of an eigenvalue bound
problem. Section 4 contains a short review on the replicator dynamics, which by now
has become an increasingly popular local optimization procedure for standard QPs.
This technique is combined with primal-dual search directions from general conic programming
[28, 45], which are used to escape from ine-cient local solutions returned by
the replicator dynamics iteration.
On copositive programming and standard quadratic optimization problems 3
2. Copositive programming problems: general setup
Consider the following primal-dual pair of linear programming problems over a pointed
convex cone K  IR d , see, e.g. [37, 17, 28, 45]:
subject to
where D is an m d matrix with full row rank and b 2 IR m while c 2 IR d , and
subject to D > y
where K Kg is the dual cone of K. In semidefinite
programming, coincides with the cone P of all symmetric
positive-semidenite n  n matrices, which is self-dual under the usual inner
product trace (SX) on the d-dimensional Euclidean space S n constructed by
identifying the upper triangular half of a symmetric n  n matrix with its vectorized
version.
However, we need not restrict ourselves to cases of self-dual cones K if we can handle
the dual cone K  , even if the geometry of K and K  becomes more complicated. In fact,
it turns out useful to study more general cases, e.g. putting K  equal to the cone of
copositive matrices.
Recall that a symmetric n  n matrix M is said to be copositive (more precisely,
i.e., if the quadratic form generated by M takes only non-negative values on the positive
orthant
. The matrix M is said to be strictly (IR n
-)copositive, if the inequality in (4)
is strict whenever v 6= o. Clearly, this cone K  has non-empty interior and so does its
(pre-)dual cone K (see Proposition 1 below) which can be described as follows, see,
e.g. [19, 43]:
the convex hull of all symmetric rank-one matrices, i.e. dyadic products generated by
non-negative vectors. Elements of K are called completely positive matrices. Note that
dropping non-negativity requirement, we again arrive at the semidenite case. Even
without constraints, checking whether or not a matrix belongs to K  is co-NP-hard [36].
Some algorithms for this problem can be found, e.g. in [33, 18, 46, 5, 47, 48, 14, 6],
to mention just a few. Less obvious is the primal feasibility problem (also without
constraints). In fact, the authors are not aware of any nite and exact procedure to
determine whether or not a given symmetric nn matrix is completely positive if
See also [32, 29, 20, 4, 3, 25, 15, 49]. However, the following result may be helpful:
4 I.M. Bomze, M. Dur, E. de Klerk, C. Roos, A. Quist, T.
PROPOSITION 1. Let K be as in (5), d = n+1 , and denote by
X has no negative
Then
is a non-negative n  (d
Proof. In view of Caratheodory's theorem, the rst identity (cf. Theorem 1 of [32]) is
obvious by taking
1g, and by noting that the
middle set in (7) necessarily is a subset of K due to the fact that hM;FF >
are the columns of F . But then the inclusion
K+  K is also immediate. To nalize the proof, observe that
x > x
implies that K  co K+ .
Unfortunately, the cone K+ itself is not convex and therefore strictly smaller than
K, as the following example shows:
Example 1. The nonsingular 3  3 matrix
with a =6 403
belongs to K (cf. [3]). However, its square root is approximately
0:908 0:092 0:408
0:092 0:908 0:408
0:408 0:408 1:6337 5
whence
although the rank-one matrices aa > , bb > and cc > as seen above belong
to K+ . A singular variant is obtained by aa > +bb > , i.e. replacing the lower right corner
entry of X with 2.
As a general application of the primal-dual approach given by (2) and (3) consider
the so-called all-quadratic problem on  which appears as a subproblem in [41]:
subject to x 2
Note that also inhomogeneous quadratic constraints can be written in this form (see
above), so that by introducing slacks we also can write problems with quadratic inequality
constraints in the form (8). Further, additional linear constraints of the form
d can be written as hD; does not change
On copositive programming and standard quadratic optimization problems 5
sign over the feasible set (otherwise one has to subdivide this set accordingly). So the
normalization condition in  can be written as hE; Hence with K
as in (5), we may view the following copositive programming problem as a relaxation
of
subject to hE;
Indeed, linearity (in fact, convexity) of the objective ensures that one solution X to
the problem (9) is attained at an extreme point of the feasible set. If X happens to
lie also on an extreme ray of K, then automatically so that this condition
can be dropped without loss of generality. In this case, the relaxation (9) becomes an
exact reformulation of (8). Unfortunately, this is not always the case, as the following
example shows:
Example 2. Consider the problem (9) to maximize hA subject to
and, of course, X 2 K as well as hE; 1. Obviously, the
only solution to this problem is given by the rank-two matrix X  with x
We proceed as in the general case with the primal-dual pair (2),(3) to establish the
dual problem of (9) which has m+ 1 structural variables y 0 and
also d slacks contained in S:
subject to y
Given that we can solve the primal and dual feasibility problems with limited eort, it
is possible to use the search directions for a feasible primal-dual interior point algorithm.
Indeed, the following results of Nesterov and Nemirovskii [37] are valid for a general
class of convex cones which include the cone K given by (5):
There exist so-called self-concordant barrier functions for the cones K and K
Interior point methods which converge in a polynomially bounded number of steps
can be formulated using the self-concordant barriers.
Unfortunately, the self-concordant barriers for K and K  are not known, for an elaborate
discussion on this topic see [43]. However, Tuncel [45] has recently noticed that even in
this case one can still formulate a class of interior point methods known as primal{dual
a-ne scaling algorithms.
For ease of reference we now reproduce a generic roster for a primal-dual interior-point
method from [21, 27, 34]. Of course, it is in general not harder to solve (8) to
6 I.M. Bomze, M. Dur, E. de Klerk, C. Roos, A. Quist, T.
optimality than to resolve the feasibility questions (i.e., to check membership of K or
there could be special instances where the procedure is still helpful.
Generic Interior-Point Primal-Dual Algorithm
1. Choose an initial point (X
and that
2. Until a stopping criterion is satised, repeat the following step: choose an improving
feasible direction (dX; dy; dS) and step length  > 0 such that still X+dX 2 int K
as well as S
Feasibility w.r.t. the equality constraints is maintained by the so-called primal-dual
a-ne scaling (or zero-order) search direction provided by Kojima and Tuncel [28, 45].
Slightly simplied, this class of directions is the solution of the linear system in S n
where H is an arbitrary positive-denite, symmetric linear operator on S n and
As usual, the remaining (strict) feasibility requirements are guaranteed by a suitable
choice of the step lengths. Note that a solution to (11) always exists as also QH
is positive-denite provided hX; Si > 0 which is guaranteed for interior point pairs
Theorem 3.3 in [45]), since we assume that fE; A
are linearly independent, in correspondence with the full row rank assumption on D
in (2). Thus we have the same situation as in the classical SDP case for the search
direction commonly used there, cf., e.g. [16].
Kojima and Tuncel prove in [28] (cf. Theorem 3.4 in [45]) that if we choose the search
directions from (12), then the duality gap decreases linearly with a factor essentially
being the step length, and both primal and dual objectives will be improved, unless
optimality is reached. Decisive for their arguments is the positive deniteness of H and
the property that
Looking at formula (12), it is evident that much would be gained if the terms
containing HS vanished, which of course is impossible if H is positive-denite. We
On copositive programming and standard quadratic optimization problems 7
therefore propose a positive-semidenite variant of the above-mentioned result where
H has a single zero eigenvalue belonging to the direction S. Note that we no longer
assume that (X; S) 2 int Kint K  , but only hX; Si > 0. Recall that the latter relation
characterizes non-optimality of pairs (X; S).
THEOREM 2. Suppose that H is a positive-semidenite, symmetric linear operator on
Consider a pair (X; S) 2 K  K  with hX; Si > 0 and dene the symmetric linear
operator RH on S n by
Then RH is positive-denite and satises
Furthermore, the solution (dX; dy; dS) to the system in S n  IR m+1  S n
is unique and satises hX
Proof. The rst argument is quite similar to that in Theorem 3.3 of [45]. For any
which is non-negative and can vanish only if both hX;
O this is absurd as the latter relation implies
assumption whereas hX; again by assumption, hX; Si > 0. Hence
the operator is positive-denite. Finally,
Turning to system (14), we show that the related homogeneous system in (dX; dy; dS)
has only the trivial solution. Indeed, substituting for dS in the equation
yields
dy
and substituting then for dX in the rst m+ 1 equations of (14) gives, after changing
the signs, a homogeneous system in dy with coe-cient matrix6 6 6 4
8 I.M. Bomze, M. Dur, E. de Klerk, C. Roos, A. Quist, T.
which is, due to linear independence of fE; A easily seen to be positive-
denite as RH is so. Thus dy = o, yielding Hence (14) has always
a unique solution. To establish reduction of the duality gap, let us rst deal with the
second-order term hdX; dSi which vanishes because of the feasibility conditions imposed
on (dX; dy; dS) in (14): indeed,
Now the rst-order terms hX; dSi because of
This establishes hX
Using similar arguments as in [28], one can also show that both primal and dual
objectives are improved by the directions given by (14). We will establish this result
directly in the next section for the special case we focus upon in this paper.
Remarks
In semidenite programming (SDP) where there are many possible choices
of the operator RH ; only one choice is known to allow convergent algorithms, namely
the Nesterov-Todd primal{dual a-ne-scaling direction, where
Note that that RH is a positive denite linear operator. Also note
that this choice of RH is not possible for copositive programming, since
X is
not positive-denite for all copositive matrices S. For SDP, the primal-dual algorithm
using this search direction is globally convergent and polynomial for a suitable choice
of the step length [26].
Another choice of primal-dual scaling direction is the so-called (primal) HKM a-ne-
scaling direction, where
. As mentioned, this search
direction is not globally convergent for any choice of step length. In particular, it
can converge to a non-optimal point [35]. Moreover, it cannot be used for copositive
programming because a copositive matrix S can be singular despite hX; Si > 0 for all
, which is linearly independent from E.
Finally, a primal-dual a-ne scaling direction for SDP which is also dened for
copositive programming is the so-called dual HKM direction, which is given as the
On copositive programming and standard quadratic optimization problems 9
solution of
As with the (primal) HKM direction, no primal-dual SDP algorithm using this search
direction is globally convergent [35].
The preceding observations prove two things:
Using only primal-dual a-ne scaling directions in interior point methods for conic
programming does not necessarily lead to a globally convergent algorithm;
One cannot guarantee a xed feasible step length for all primal-dual a-ne scaling
directions (even in the SDP case); in other words, 'jamming' can occur.
For these reasons we will discuss a hybrid algorithm in Section 4 which uses primal-dual
a-ne-scaling steps only as an escape strategy.
3. Standard quadratic optimization and copositive programming
First note that the standard QP (1) is a special case of the all-quadratic problem (8)
with no quadratic constraints and A A. Hence in this case we arrive at the copositive
programming problem (9) with a single constraint:
subject to hE;
so that the dual has only one structural variable
subject to yE
This amounts to search for the smallest y such that yE A is copositive. In this sense,
the dual problem (16) is related to the question of eigenvalue bounds (replace E with
the identity matrix I and \copositive" with \semidenite").
Further observe that in this case, (15) is no relaxation but indeed an exact reformulation
of the standard QP (1), due to the following
LEMMA 3. The extremal points of the feasible set of (15) are exactly the rank-one
matrices
1 From this point on y will denote a scalar variable.
I.M. Bomze, M. Dur, E. de Klerk, C. Roos, A. Quist, T.
Proof. Of course all belong to 1g. Now
suppose that for a vector x 2 , we have xx
and some  with 0 <  < 1. Choose an orthogonal basis fx 1 of IR n with
. Then since Z and U also are positive semidenite, we get from
that x >
both Z and U have rank one. As
both belong to K, we thus obtain
. But then
we obtain x >
Z and U must be positive multiples of
xx > . The requirement hE; shows that
To show the converse, suppose that X is an extremal point of M  K. Then
as well as
i. Hence
is, due to (17), a convex combination of matrices U i in M, whence by the extremality
assumption is of the form stated.
In principle, the roster of the algorithm of Section 2 applies, but the update equations
now reduce to
which for the dual part means simply that we have to continue the line search for the
generalized eigenvalue bound of A as in (16). Of course, a similar reduction applies to
the Kojima-Tuncel search directions from (11), where QH replaces RH .
Now let us calculate the update steps explicitly, in order to avoid unnecessary
numerical complications. Remember that we have still freedom in choosing the positive-
semidenite operator H as long as S gives the unique direction to the zero eigenvalue of
H (note that by assumption on linear independence of fA; Eg, the matrix
never can vanish regardless whether it belongs to K  or not). For instance, we may
assume that the orthoprojection of E onto the orthogonal complement of S in S n is
also an eigenvector of H with a suitably chosen eigenvalue  > 0. As this is
On copositive programming and standard quadratic optimization problems 11
equivalent to imposing
THEOREM 4. Put and denote by (dX; dy; dS) the
solution of (18). Then (19) implies
Proof. From Inserting
further obtain
the result for dy, observing that hE;
Similarly, we derive
hX;Si X, and
the proof is complete.
For further formulation, it may be convenient to write X
with
We now directly show that both objectives are indeed improved by the chosen
directions.
THEOREM 5. Assume that (X; S) 2 KK  with hX; Si > 0. If the improving feasible
direction (dX; dy; dS) is chosen as in Theorem 4, then for  > 0 both primal and dual
objective function improve strictly, i.e.
Proof. First, dy is strictly negative, since n 2 hE;Si 2
by the
Cauchy-Schwarz inequality (note that also fE; Sg are linearly independent).
To see the strict monotonicity in the primal objective function, compare the reduction
of the duality gap with the improvement in the dual objective. From Theorem 2, we
know that the reduction of the duality gap is hX; Si. Therefore, to show that also the
primal objective contributes to this reduction, we have to show that dy < hX; Si.
But
since the denominator of the above fraction is a positive number bigger than 1.
12 I.M. Bomze, M. Dur, E. de Klerk, C. Roos, A. Quist, T.
For the sake of completeness, we now also provide explicit update formulae for the
original Kojima/Tuncel search direction, i.e. for the solutions to the system
with H now again positive-denite but otherwise arbitrary, and QH from (12). Of
course, for concrete implementation it remains to specify the values HE and
HA.
THEOREM 6. Assume that (X; S) 2 K  K  with hX; Si > 0. Put
denote by (dX; dy; dS) the solution of (22). Then
Furthermore, both primal and dual objectives are strictly improved if  > 0.
Proof. The arguments are very similar to that of Theorems 4 and 5, and therefore
omitted.
4. A hybrid method: replicator dynamics and primal-dual escape steps
To nd local solutions to the standard QP (1), we propose to use replicator dynamics.
For the reader's convenience, we here provide a short overview, and refer for more detail
to [7, 11, 12]. Consider the following dynamical system operating on :
_
where a dot signies derivative w.r.t. time t, and a discrete time version
ng : (25)
Note that x(0) 2 IR n
implies
since A is nonnegative by
assumption.
The stationary points under (24) and (25) coincide, and all local solutions of (1)
are among these. Of course, there are quite many stationary points, e.g. all vertices
of . However, it can be shown [7] that x is a strict local solution if and only if x is
On copositive programming and standard quadratic optimization problems 13
asymptotically stable, i.e. every solution to (24) or (25) which starts close enough to x,
will converge to x as t %1.
Both (24) and (25) arise in population genetics under the name selection equations
where they are used to model time evolution of haploid genotypes, A being the
(symmetric) tness matrix, and x i (t) representing the relative frequency of allele i in
the population. The Fundamental Theorem of Selection states that average tness,
i.e. the objective function x(t) > Ax(t) is (strictly) increasing over time along trajectories
[13, 22], and moreover every trajectory x(t) converges to a stationary point [31, 22].
Furthermore, one can prove [7, 12] the following facts: if no principal minor of
vanishes, then with probability one any trajectory converges to a strict local solution
x of (1); further, if ng
with y 6= x; and  -
is contained in the basin of attraction of x, where for a subset
we shall denote the face of  corresponding to  by
and its relative interior by
The dynamical systems (24) and (25) are frequently called replicator dynamics, and
are well suited for implementation in practical applications, see [40, 11, 8]. This is
re
ected also in theory by the result that (24) is most e-ciently approaching xed points
in the sense that it is a Shahshahani gradient system [44]. The discrete time version (25)
also corresponds to a particular instance of an algorithm widely popular in computer
vision. These relaxation labeling processes are closely related to articial neural network
learning systems, and have found applications in a variety of practical tasks, e.g. to
solve certain labeling problems arising in the 3-D interpretation of ambiguous line
drawings [42, 24, 39]. Furthermore, the dynamics (25) belongs to a class of dynamical
systems investigated in [1, 2], which has proven to be useful in the speech recognition
domain [30].
Although strictly increasing objective values are guaranteed as we follow trajectories
under (24) or (25), we could get stuck in an ine-cient local solution x of (1). From the
preceding results, then necessarily x One possibility to escape from x
is by the G.E.N.F. approach [12]. An alternative is to merge the replicator dynamics
method with the usual interior-point steps borrowed from semidenite programming,
and this will be described in the sequel. But given any escape procedure, we are now
ready to describe the principal algorithm for solving (1) globally. Note that this procedure
stops after nitely many repetitions, since it yields strict local solutions (in every
14 I.M. Bomze, M. Dur, E. de Klerk, C. Roos, A. Quist, T.
there is at most one of these) with strictly increasing objective
values:
Replicator Dynamics Algorithm
1. Start with
n e or nearby, iterate (25) until convergence; the limit
lim t!1 x(t) is a strict local solution with probability one (provided all principal
minors of A do not vanish);
2. call an escape procedure to improve the objective, if this is still possible; denote
the improving point e x;
3. repeat 1., starting with
x.
Now we are ready to present a combination of the above procedure and the interior-point
method yielding improving direction, in the hope that it will be possible to escape
from ine-cient local solutions.
A Hybrid Algorithm
1. Initialisation: choose
n e or nearby. Put y
2. Replicator dynamics for fast primal updates: starting from x(0) iterate (25) until
convergence; the limit is a strict local solution with probability
3. Dual update: check copositivity of yE A via shortcuts (cf. Fig. 1 in [6], for a
special case see [10]).
In the a-rmative, x is the global solution of (1), since the duality gap is zero (cf.
also Theorem 7 in [7]); stop.
If however a point e
is found such that e x > (yE A)ex < 0, then e x improves the
objective; repeat step 2 starting with this point.
Else (no decision), keep the old value of y 0 , and proceed to step 4.
4. Step back from the boundary: Choose  > 0 so small, that the point
and the matrix
I satises (with b x the previous iterate,
so that x > Ax b
x > Abx is the previously obtained improvement)
x > Abx  1
This is a quadratic inequality for . Note that by construction, X is both positive-
denite and has a non-negative square root:
r
On copositive programming and standard quadratic optimization problems 15
5. Since X is both positive-denite and has a non-negative square root, one can choose
Y as in (21) and  > 0 su-ciently small such that e
the same properties. This is possible because the mapping X 7!
X is Holder
continuous around X. Hence primal feasibility of e
X is maintained (cf. Lemma 1),
and we get an explicit positive (square root) factorization of e
are all non-negative. Thus e
with  i  0 and x
1g.
6. Primal update: Now x > Ax  hA; Xi < hA; e
possible, choose
e
x such that
x >
This will always be possible if hA; e
Repeat from step 2, starting with
The following small example illustrates the ideas behind the hybrid algorithm. In par-
ticular, the example is meant to illustrate how the escape strategy in steps 4 through
6 works.
Example 3. Let A =
and suppose we arrived via replicator dynamics starting
at
already at the (suboptimal) local solution x
. Then
and improvement
As x is not the global solution, the matrix
is not copositive.
Following step 3 of the hybrid algorithm, we return to the old y
arrive at the dually feasible (i.e., copositive) matrix
which
incidentially coincides with the optimal S (see below). Note that although
neither X nor S is interior, we have hX;
Suppose for the moment we ignored step 4 above and tried to proceed directly in
forming the matrix
Y (the signshall emphasize the preliminarity of this trial) for the
escape step along (20) and (21). The key quantities in (20) and (21) are hE;
9. Hence
I.M. Bomze, M. Dur, E. de Klerk, C. Roos, A. Quist, T.
and, furthermore,
Therefore
dy
9
which is positive-denite but has negative o-diagonal entries so that
Y
is infeasible for all positive . This shows that the step back from the boundary, i.e. step 4
in the hybrid algorithm is really necessary. Note that ignoring primal feasibility in this
respect, one could investigate instead whether the vector
Y e belongs
to  (i.e., has no negative coordinate, as automatically e >
improves the objective. With regard to the latter aim, it is desirable to take  as large
as possible (recall that x is locally optimal and the objective is quadratic so that the
improvement will be largest for the largest possible distance { if there is one at all). In
our case, this means considering as a candidate for an improving point in  the vector
3+9
38
as
and indeed we manage to escape because we get an improvement if  is chosen large
enough, as (
But let us return to the hybrid algorithm as proposed above: choose, e.g.,
step 4, so that
0:9
0:1
and xx
0:81 0:09
0:09 0:01
as well as
I
0:748 0:072
0:072 0:108
with
so that the duality gap will be slightly increased, as expected. Note that S and the update
part (26) of Y remain the same as the dual variable y does not change, and observe
that, as required in step 4, the choice of
Now
Motivated by the trial with
above, we choose  large enough to enable an escape, e.g.
and arrive at the positive-denite matrix
On copositive programming and standard quadratic optimization problems 17
Hence the primal feasibility requirement e
will be met if and
only if all entries of the latter matrix are non-negative, which means   0:864
1:792  0:482.
A typical choice of  in step 5 would be
2 (cf.[45]), but for simplicity we choose
here
3 . Then
e
0:6306 0:0222
0:0222 0:3250
int K with
0:7939 0:0163
0:0163 0:5699
and h e
In step 6 of the hybrid algorithm we therefore
obtain
by normalizing the last column of
X, with objective value e
x > Aex  2:8912 > 2. The
last steps in the hybrid algorithm are as follows: use the improving point e x as the starting
vector for the replicator dynamics iteration, which nally leads to the global solution
. For the nal check for optimality we now calculate X
5. Conclusions
The problem of maximizing a quadratic form over the simplex has an exact reformulation
as a copositive programming problem, i.e. a conic programming problem over the
cone of copositive matrices. The advantage of such a reformulation is that successful
ideas from the theory of interior point methods can thus be applied to nonconvex
quadratic optimization. In particular, primal-dual a-ne scaling directions can be used
in escape strategies if ine-cient local solutions are obtained from local optimization
procedures like replicator dynamics.



--R

An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology.

Complete positivity.

Remarks on the recursive structure of copositivity.







An introduction to population genetics theory
A recursive algorithm to detect (strict) copositivity of a symmetric matrix.
Completely positive matrices associated with M- matrices
Exploiting sparsity in primal-dual interior-point methods for semide nite programming

On copositive matrices.


An interior-point method for semide nite programming
The Theory of Evolution and Dynamical Systems.
Introduction to Global Optimization
On the foundations of relaxation labeling processes.
On nonnegative factorization matrices.
Polynomial primal-dual a-ne scaling algorithms in semide nite programming


Square triangular factorizations of completely positive matrices.
An introduction to the application of the theory of probabilistic functions of a Markov process to automatic speech recognition.

Factorizations of completely positive matrices.
Copositive matrices and de


Some NP-complete problems in quadratic and linear program- ming
Interior point methods in convex programming: theory and applications.
A new semide
On the dynamics of relaxation labeling processes.

Nonconvex all-quadratic global optimization problems: solution methods
Scene labeling by relaxation operations.
Copositive relaxation for general quadratic programming.
Game dynamics




Notes on completely positive matrices.
--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
Immanuel M. Bomze , Etienne De Klerk, Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming, Journal of Global Optimization, v.24 n.2, p.163-185, October 2002
Immanuel M. Bomze, Branch-and-bound approaches to standard quadratic optimization problems, Journal of Global Optimization, v.22 n.1-4, p.17-37, January 2002
positive semidefinite matrices;copositive programming;standard quadratic optimization;global maximization