On Lagrangian Relaxation of Quadratic Matrix Constraints.
Quadratically constrained quadratic programs (QQPs) play an important modeling role for many diverse problems. These problems are in general NP hard and numerically intractable. Lagrangian relaxations often provide good approximate solutions to these hard problems. Such relaxations are equivalent to semidefinite programming relaxations.For several special cases of QQP, e.g., convex programs and trust region subproblems, the Lagrangian relaxation provides the exact optimal value, i.e., there is a zero duality gap. However, this is not true for the general QQP, or even the QQP with two convex constraints, but a nonconvex objective. In this paper we consider a certain QQP where the quadratic constraints correspond to the matrix orthogonality condition XXT=I. For this problem we show that the Lagrangian dual based on relaxing the constraints XXT=I  and the seemingly redundant constraints XT X=I has a zero duality gap. This result has natural applications to quadratic assignment and graph partitioning problems, as well as the problem of minimizing the weighted sum of the largest eigenvalues of a matrix. We also show that the technique of relaxing quadratic matrix constraints can be used to obtain a strengthened semidefinite relaxation for the max-cut problem.
Introduction
. Quadratically constrained quadratic programs (QQPs) play
an important modeling role for many diverse problems. They often provide a much
improved model compared to the simpler linear relaxation of a problem. However, very
large linear models can be solved e#ciently, whereas QQPs are in general NP-hard
and numerically intractable. Lagrangian relaxations often provide good approximate
solutions to these hard problems. Moreover these relaxations can be shown to be
equivalent to semidefinite programming (SDP) relaxations, and SDP problems can be
solved e#ciently, i.e., they are polynomial time problems; see, e.g., [31].
relaxations provide a tractable approach for finding good bounds for many
hard combinatorial problems. The best example is the application of SDP to the
max-cut problem, where a 87% performance guarantee exists [11, 12]. Other examples
include matrix completion problems [23, 22], as well as graph partitioning problems
and the quadratic assignment problem (references given below).
In this paper we consider several quadratically constrained quadratic (nonconvex)
programs arising from hard combinatorial problems. In particular, we look at the
orthogonal relaxations of the quadratic assignment and graph partitioning problems.
We show that the resulting well-known eigenvalue bounds for these problems can
be obtained from the Lagrangian dual of the orthogonally constrained relaxations,
# Received by the editors June 9, 1998; accepted for publication (in revised form) by P. Van Dooren
July 30, 1999; published electronically May 31, 2000.
http://www.siam.org/journals/simax/22-1/34029.html
Department of Management Sciences, University of Iowa, Iowa City, IA 52242-1000
(kurt-anstreicher@uiowa.edu).
# University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario N2L
3G1, Canada (henry@orion.uwaterloo.ca). This author's research was supported by Natural Sciences
and Engineering Research Council of Canada.
42 KURT ANSTREICHER AND HENRY WOLKOWICZ
but only if the seemingly redundant constraint X T I is explicitly added to the
orthogonality constraint XX Our main analytical tool is a strong duality
result for a certain nonconvex QQP, where the quadratic constraints correspond to
the orthogonality conditions XX We also show that the technique
of applying Lagrangian relaxation to quadratic matrix constraints can be used to
obtain a strengthened SDP relaxation for the max-cut problem.
Our results show that current tractable (nonconvex) relaxations for the quadratic
assignment and graph partitioning problems can, in fact, be found using Lagrangian
relaxations. converse statement is well known, i.e., the Lagrangian dual is equivalent
to an (tractable) SDP relaxation.) Our results here provide further evidence to
the following conjecture: the Lagrangian relaxation of an appropriate QQP provides
the strongest tractable relaxation for QQPs.
1.1. Outline. We complete this section with the notation used in this paper.
In section 2, we present several known results on QQPs. We start with convex
QQPs where a zero duality gap always holds. Then we look at the minimum eigenvalue
problem and the trust region subproblem, where strong duality continues to hold. We
conclude with the two trust region subproblem, the max-cut problem, and general
nonconvex QQPs where nonzero duality gaps can occur.
The main results are in section 3. We show that strong duality holds for a
class of orthogonally constrained quadratic programs if we add seemingly redundant
constraints before constructing the Lagrangian dual.
In section 4 we apply this result to several problems, i.e., relaxations of quadratic
assignment and graph partitioning problems, and a weighted sum of eigenvalue prob-
lem. In section 5 we present strengthened semidefinite relaxations for the max-cut
problem. In section 6 we summarize our results and describe some promising directions
for future research.
1.2. Notation. We now describe the notation used in the paper.
Let S n denote the space of n-n symmetric matrices equipped with the trace inner
product, positive semidefiniteness
positive definiteness) and A # B denote A - B # 0, i.e., S n is equipped with
the L-owner partial order. We let P denote the cone of symmetric positive semidefinite
matrices; M m,n denotes the space of general m- n matrices also equipped with the
trace inner product, #A, denotes the space of general m-m
matrices; O denotes the set of orthonormal (orthogonal) matrices; # denotes the set
of permutation matrices.
We let Diag(v) be the diagonal matrix formed from the vector v; its adjoint
operator is diag(M ), which is the vector formed from the diagonal of the matrix M.
For , the vector formed (columnwise) from M .
The Kronecker product of two matrices is denoted
A# B, and the Hadamard
product is denoted A # B.
We use e to denote the vector of all ones, and ee T to denote the matrix of
all ones.
2. Some known results. The general QQP is
x. We now present several QQP problems where the
Lagrangian relaxation is important and well known. In all these cases, the Lagrangian
QUADRATIC MATRIX CONSTRAINTS 43
dual provides an important theoretical tool for algorithmic development, even where
the duality gap may be nonzero.
2.1. Convex quadratic programs. Consider the convex quadratic program
where all q i (x) are convex quadratic functions. The dual is
min
x
If # is attained at # , x # , then a su#cient condition for x # to be optimal for CQP is
primal feasibility and complementary slackness, i.e.,
In addition, it is well known that the Karush-Kuhn-Tucker (KKT) conditions
are su#cient for global optimality, and under an appropriate constraint qualification
the KKT conditions are also necessary. Therefore strong duality holds if a constraint
qualification is satisfied, i.e., there is no duality gap and the dual is attained.
However, surprisingly, if the primal value of CQP is bounded, then it is attained
and there is no duality gap; see, e.g., [44, 36, 34, 35] and, more recently, [26]. However,
the dual may not be attained, e.g., consider the convex program
and its dual
min
x
Algorithmic approaches based on Lagrangian duality appear in, e.g., [19, 25, 31].
2.2. Rayleigh quotient. Suppose that A = A T
. It is well known that the
smallest eigenvalue # 1 of A is obtained from the Rayleigh quotient, i.e.,
Since A is not necessarily positive semidefinite, this is the minimization of a nonconvex
function on a nonconvex set. However, the Rayleigh quotient forms the basis for many
algorithms for finding the smallest eigenvalue, and these algorithms are very e#cient.
In fact, it is easy to see that there is no duality gap for this nonconvex problem, i.e.,
min
x
To see this, note that the inner minimization problem in (2.2) is unconstrained. This
implies that the outer maximization problem has the hidden semidefinite constraint
(an ongoing theme in the paper)
i.e., # is at most the smallest eigenvalue of A. With # set to the smallest eigenvalue,
the inner minimization yields the eigenvector corresponding to # 1 . Thus, we have an
example of a nonconvex problem for which strong duality holds. Note that the problem
(2.1) has the special norm constraint and a homogeneous quadratic objective.
44 KURT ANSTREICHER AND HENRY WOLKOWICZ
2.3. Trust region subproblem. We will next see that strong duality holds for
a larger class of seemingly nonconvex problems. The trust region subproblem (TRS)
is the minimization of a quadratic function subject to a norm constraint. No convexity
or homogeneity of the objective function is assumed.
Assuming that the constraint in TRS is written "#," the Lagrangian dual is
min
x
This is equivalent to (see [43]) the (concave) nonlinear semidefinite program
s.t. Q+ #I # 0,
Moore-Penrose inverse. It is shown in [43] that strong duality holds
for TRS, i.e., there is a zero duality gap - # , and both the primal and dual
are attained. Thus, as in the eigenvalue case, we see that this is an example of a
nonconvex program where strong duality holds.
Extensions of this result to a two-sided general, possibly nonconvex constraint are
discussed in [43, 28]. An algorithm based on Lagrangian duality appears in [40] and
(implicitly) in [29, 41]. These algorithms are extremely e#cient for the TRS problem,
i.e., they solve this problem almost as quickly as they can solve an eigenvalue problem.
2.4. Two trust region subproblem. The two trust region subproblem (TTRS)
consists of minimizing a (possibly nonconvex) quadratic function subject to a norm
and a least squares constraint, i.e., two convex quadratic constraints. This problem
arises in solving general nonlinear programs using a sequential quadratic programming
approach and is often called the Celis-Dennis-Tapia (CDT) problem; see [4].
In contrast to the above single TRS, the TTRS can have a nonzero duality gap;
see, e.g., [33, 47, 48, 49]. This is closely related to quadratic theorems of the alterna-
tive, e.g., [5]. In addition, if the constraints are not convex, then the primal may not
be attained; see, e.g., [26].
In [27], Martinez shows that the TRS can have at most one local and nonglobal
optimum, and the Lagrangian at this point has one negative eigenvalue. Therefore, if
we have such a case and add another ball constraint that contains the local, nonglobal
optimum in its interior and also makes this point the global optimum, we obtain a
TTRS where we cannot close the duality gap due to the negative eigenvalue. It is
uncertain what constraints could be added to close this duality gap. In fact, it is still
an open problem whether TTRS is an NP-hard or a polynomial-time problem.
2.5. Max-cut problem. Suppose that E) is an undirected graph with
vertex set
and weights w ij on the edges (v i , The max-cut problem
consists of finding the index set I # {1, 2, . , n}, in order to maximize the weight of
the edges with one end point with index in I and the other in the complement. This is
equivalent to the following discrete optimization problem with a quadratic objective:
We equate x I and x otherwise. Define the homogeneous
quadratic objective
where Q is an n - n symmetric matrix. Then the MC problem is equivalent to the
QQP
This problem is NP-hard, i.e., intractable.
Since the above QQP has many nonconvex quadratic constraints, a duality gap
for the Lagrangian relaxation is expected and does indeed occur most of the time.
However, the Lagrangian dual is equivalent to the SDP relaxation (upper bound)
e,
which has proven to have very strong theoretical and practical properties, i.e., the
bound has an 87% performance guarantee for the problem MC and a 97% performance
in practice; see, e.g., [12, 18, 15]. Other theoretical results for general objectives and
further relaxed constraints appear in [30, 46].
In [38], several unrelated, though tractable, bounds for MC are shown to be
equivalent. These bounds include the box relaxation -e # x # e, the trust region
relaxation
an eigenvalue relaxation. Furthermore, these bounds are
all shown to be equivalent to the Lagrangian relaxation; see [37]. Thus we see that
the Lagrangian relaxation is equivalent to the best of these tractable bounds.
2.6. General QQP. The general, possibly nonconvex QQP has many applications
in modeling and approximation theory; see, e.g., the applications to SQP
methods in [21]. Examples of approximations to QQPs also appear in [9].
The Lagrangian relaxation of a QQP is equivalent to the SDP relaxation and is
sometimes referred to as the Shor relaxation; see [42]. The Lagrangian relaxation can
be written as an SDP if one takes into the account the hidden semidefinite constraint,
i.e., a quadratic function is bounded below only if the Hessian is positive semidefinite.
The SDP relaxation is then the Lagrangian dual of this semidefinite program. It can
also be obtained directly by lifting the problem into matrix space using the fact that
relaxing xx T to a semidefinite matrix X.
One can relate the geometry of the original feasible set of QQP with the feasible
set of the SDP relaxation. The connection is through valid quadratic inequalities, i.e.,
nonnegative (convex) combinations of the quadratic functions; see [10, 20].
3. Orthogonally constrained programs with zero duality gaps. Consider
the orthonormal constraint
(The set of such X is sometimes known as the Stiefel manifold; see, e.g., [7]. Applications
and algorithms for optimization on orthonormal sets of matrices are discussed
in [7].) In this section we will show that for holds for a certain
(nonconvex) quadratic program defined over orthonormal matrices. Because of the
similarity of the orthonormality constraint to the norm constraint x T the result
of this section can be viewed as a matrix generalization of the strong duality result
for the Rayleigh quotient problem (2.1).
Let A and B be n - n symmetric matrices, and consider the orthonormally constrained
homogeneous QQP
This problem can be solved exactly using Lagrange multipliers (see, e.g., [14]) or using
the classical Ho#man-Wielandt inequality (see, e.g., [3]). We include a simple proof
for completeness.
Proposition 3.1. Suppose that the orthogonal diagonalizations of A, B are
respectively, where the eigenvalues in # are ordered
nonincreasing and the eigenvalues in # are ordered nondecreasing. Then the optimal
value of QQPO is - O = tr # and the optimal solution is obtained using the
orthogonal matrices that yield the diagonalizations, i.e.,
Proof. The constraint G(X) := XX T
- I maps M n to S n . The Jacobian of the
constraint at X acting on the direction h is . The adjoint of
the Jacobian acting on S # S n is J #
tr
But J # is one-one for all X orthogonal. Therefore,
J is onto, i.e., the standard constraint qualification holds at the optimum. It follows
that the necessary conditions for optimality are that the gradient of the Lagrangian
is 0, i.e.,
Therefore,
i.e., AXBX T is symmetric, which means that A and XBX T commute and so are
mutually diagonalizable by the orthogonal matrix U . Therefore, we can assume that
both A and B are diagonal and we choose X to be a product of permutations that
gives the correct ordering of the eigenvalues.
The Lagrangian dual of QQPO is
min
tr AXBX T
However, there can be a nonzero duality gap for the Lagrangian dual; see [50] for
an example. The inner minimization in the dual problem (3.3) is an unconstrained
quadratic minimization in the variables vec (X), with Hessian
I# S.
this minimization is unbounded if the Hessian is not positive semidefinite. In
order to close the duality gap, we need a larger class of quadratic functions.
Note that in QQPO the constraints XX are equivalent.
Adding the redundant constraints X T we arrive at
Using symmetric matrices S and T to relax the constraints XX
respectively, we obtain a dual problem
s.t.
(B# A),
Theorem 3.2. Strong duality holds for QQPOO and DQQPOO , i.e., -
and both primal and dual are attained.
Proof. Let and U are orthonormal matrices
whose columns are the eigenvectors of A and B, respectively, # and # are the corresponding
vectors of eigenvalues, and Diag(#). Then for any S and
U# V is nonsingular, tr
S, and
tr
T , the dual problem DQQPOO is equivalent to
s.t.
However, since # and # are diagonal matrices, (3.4) is equivalent to the ordinary
linear program:
But LD is the dual of the linear assignment problem:
s.t.
Assume without loss of generality that # 1
Then LP can be interpreted as the problem of finding a permutation #(-) of {1, . , n}
so that
But the minimizing permutation is then
Proposition 3.1 the solution value - D is exactly - O .
48 KURT ANSTREICHER AND HENRY WOLKOWICZ
4. Applications. We now present three applications of the above strong duality
result.
4.1. Quadratic assignment problem. Let A and B be n - n symmetric ma-
trices, and consider the homogeneous quadratic assignment problem (QAP) (see, e.g.,
[32]),
QAP min tr AXBX T
s.t. X #,
where # is the set of n - n permutation matrices. The set of orthonormal matrices
contains the permutation matrices, and the orthonormally constrained problem (3.1)
is an important relaxation of QAP. The bounds obtained are usually called the eigenvalue
bounds for QAP; see [8, 13]. Theorem 3.2 shows that the eigenvalue bounds
are in fact obtained from a Lagrangian relaxation of (3.1) after adding the seemingly
redundant constraint XX
4.2. Weighted sums of eigenvalues. Consider the problem of minimizing the
weighted sum of the k largest eigenvalues of an n - n symmetric matrix Y , subject
to linear equality constraints. An SDP formulation for this problem involving 2k
semidefiniteness constraints on n - n matrices is given in [1, section 4.3]. We will
show that the result of section 3 can be applied to obtain a new SDP formulation of
the problem having only k semidefiniteness constraints on n - n matrices.
For convenience we consider the equivalent problem of maximizing the weighted
sum of the k minimum eigenvalues of Y . Let w
are interested in the problem
s.t. A vec (Y
are the eigenvalues of Y , and A is a
matrix. From Proposition 3.1 it is clear that, for any Y ,
tr Y XWX T ,
and therefore from Theorem 3.2 the problem WEIG is equivalent to the problem
s.t.
A vec (Y
Note that, for any Y , the matrix
W# Y is block diagonal, with the final n- k blocks
identically zero. Since
I# S is also block diagonal, and tr T is a function of the diagonal
of T only, it is obvious that T can be assumed to be a diagonal matrix
Writing the problem (4.1) in terms of t, and separating the block diagonal constraints,
results in the SDP
We have thus obtained an SDP representation for the problem WEIG with
semidefiniteness constraints on n - n matrices, as claimed.
4.3. Graph partitioning problem. Let E) be an edge-weighted undirected
graph with node set
The graph partitioning (GP) problem consists of partitioning the node set N into k
disjoint subsets S 1 , . , S k of specified sizes
as to minimize the total weight of the edges connecting nodes in distinct subsets of
the partition. This problem is well known to be NP-hard. GP can be modeled as a
quadratic problem
z := min tr X T LX
where L is the Laplacian of the graph and P is the set of n - k partition matrices
(i.e., each column of X is the indicator function of the corresponding set;
node i is in set j and 0 otherwise).
The well-known Donath-Ho#man bound [6] z DH # z for GP is
z DH := max
are the eigenvalues
of We will now show that the Donath-Ho#man bound can be obtained by
applying Lagrangian relaxation to an appropriate QQP relaxation of GP. (An SDP
formulation for this bound is given in [1].) Clearly, if P is a partition matrix, then
i is the ith row of X. Moreover, the columns of X
are orthogonal with one another, and the norm of the jth column of X is # m j . It
follows that if X is a partition matrix, there is an n - n orthogonal matrix -
X such
that
where M is the k - k matrix
# .
In addition, note that x T
is the ith diagonal element of XX T , so the constraint
equivalent to -
i is the ith row of -
X. Since tr X T
50 KURT ANSTREICHER AND HENRY WOLKOWICZ
tr LXX T , a lower bound z 1 # z can be defined by
We will now obtain a second bound z 2 # z 1 by applying a Lagrangian procedure to
all of the constraints in (4.2). Using symmetric matrices S and T for the constraints
respectively, and a vector of multipliers u i for the constraints
u,S,T
min
tr L -
Theorem 4.1. z
Proof. Rearranging terms and using Kronecker product notation, the definition
of z 2 can be rewritten as
u,S,T
+min
X),
and we are using the fact that
solves the implicit
minimization problem in the definition of z 2 , and if this constraint fails to hold, the
minimum is -#. Using this hidden semidefinite constraint, we can write
Note that if u
M for any scalar #, then
M# I),
M# I).
In addition, tr T It follows that we may choose
any normalization for e T u without a#ecting the value of z 2 . Choosing e T
arrive at
QUADRATIC MATRIX CONSTRAINTS 51
However, as in the previous section, Proposition 3.1 and Theorem 3.2 together imply
that for any U , the solution value in the problem
is exactly
Therefore, we immediately have z
SDP relaxations for the GP problem are obtained via Lagrangian relaxation in
[45]. A useful corollary of Theorem 4.1 is that any Lagrangian relaxation based on a
more tightly constrained problem than (4.2) will produce bounds that dominate the
Donath-Ho#man bounds.
A problem closely related to the orthogonal relaxation of GP is the orthogonal
Procrustes problem on the Stiefel manifold; see [7, section 3.5.2]. This problem has a
linear term in the objective function, and there is no known analytic solution for the
general case.
5. A strengthened relaxation for max-cut. As discussed above, the SDP
relaxation for MC performs very well in practice and has strong theoretical proper-
ties. There have been attempts at further strengthening this relaxation. For example,
a copositive relaxation is presented in [39]. Adding cuts to the SDP relaxation is discussed
in [15, 16, 17, 18]. These improvements all involve heuristics, such as deciding
which cuts to choose or solving a copositive problem, which is NP-hard in itself.
The relaxation in (2.3) is obtained by lifting the vector x into matrix space using
. Though the matrix X in the lifting is not an orthogonal matrix, it is a
partial isometry up to normalization, i.e.,
We will now show that we can improve the semidefinite relaxation presented in
section 2.5 by considering Lagrangian relaxations using the matrix quadratic constraint
(5.1). In particular, consider the relaxation of MC
s.t. diag e,
where X is a symmetric matrix. Note that if X
and diag(X 2 ne. As a result, the above relaxation is equivalent to the relaxation
tr QX 2
ith row of X, and x 0 is a scalar. (Note that if
replacing X with -X leaves the objective and
constraints in (5.2) unchanged.) We will obtain an upper bound - 2 # - 1 by applying
a Lagrangian procedure to all of the constraints in (5.2). Using multipliers u i for the
52 KURT ANSTREICHER AND HENRY WOLKOWICZ
constraints x T
for the constraint x 2
matrix S for the matrix equality X 2
we obtain a Lagrangian problem
tr QX 2
Letting - x problem can be written in
Kronecker product form as
ne T u
Q-x,
where
Applying the hidden semidefinite constraint -
we obtain an equivalent problem,
ne T u
Note that if we take clearly optimal and the problem
reduces to
s.t. -Q+ U # 0,
which is exactly the dual of (2.3), the usual SDP relaxation for MC. It follows that we
have obtained an upper bound - 2 which is a strengthening of the usual SDP bound,
The strengthened relaxation (5.3) involves a semidefiniteness constraint on a (n 2
as opposed to an n-n matrix in the usual SDP relaxation (2.3).
This dimensional increase can be mitigated by taking note of the fact that X in (5.2)
must be a symmetric matrix, and therefore (5.2) can actually be written as a problem
over a vector x of dimension n(n + 1)/2. In addition, alternative relaxations can be
obtained by not making the substitutions based on (5.1) used to obtain the problem
(5.2). The e#ect of these alternatives on the performance of strengthened SDP bounds
for MC is the topic of ongoing research; for up-to-date developments, see the URL
http://orion.uwaterloo.ca/-hwolkowi/henry/reports/strngthMC.ps.gz.
6. Conclusion. In this paper we have shown that a class of nonconvex quadratic
problems with orthogonal constraints can satisfy strong duality if certain seemingly redundant
constraints are added before the Lagrangian dual is formed. As applications
of this result we showed that well-known eigenvalue bounds for QAP and GP problems
can actually be obtained from the Lagrangian dual of QQP relaxations of these
problems. We also showed that the technique of relaxing quadratic matrix constraints
can be used to obtain strengthened SDP relaxations for the max-cut problem.
Adding constraints to close the duality gap is akin to adding valid inequalities in
cutting plane methods for discrete optimization problems. In [2, 24] this approach, in
QUADRATIC MATRIX CONSTRAINTS 53
combination with a lifting procedure, is used to solve discrete optimization problems.
In our case we add quadratic constraints. The idea of quadratic valid inequalities has
been used in [10]; and closing the duality gap has been discussed in [20].
Our success in closing the duality gap for the QQPO problem considered in section
3, where we have the special Kronecker product in the objective function, raises
several interesting questions. For example, can the strong duality result for QQPO
be extended to the same problem with an added linear term in the objective, or are
there some other special classes of objective functions where this is possible? Another
outstanding question is whether it is possible to add quadratic constraints to close
the duality gap for the TTRS.



--R

Interior point methods in semidefinite programming with applications to combinatorial optimization

Perturbation Bounds for Matrix Eigenvalues

An alternative theorem for quadratic forms and extensions
Lower bounds for the partitioning of graphs
The geometry of algorithms with orthogonality constraints

Approximation algorithms for quadratic programming
Semidefinite programming relaxation for nonconvex quadratic pro- grams
Semidefinite programming in combinatorial optimization
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Bounds for the quadratic assignment problems using continuous optimization
A new lower bound via projection for the quadratic assignment problem
An Interior Point Method for Semidefinite Programming and Max-Cut Bounds
Fixing Variables in Semidefinite Relaxations
A spectral bundle method for semidefinite programming
An interior-point method for semidefinite programming
On the convergence of the method of analytic centers when applied to convex quadratic programs
Cones of Matrices and Successive Convex Relaxations of Non-convex Sets


A tour d'horizon on positive semidefinite and Euclidean distance matrix completion problems

An Analytic Center Based Column Generation Algorithm for Convex Quadratic Feasibility Problems
On the Extension of Frank-Wolfe Theorem
Local minimizers of quadratic functions on Euclidean balls and spheres



Interior Point Polynomial Algorithms in Convex Program- ming
The quadratic assignment problem: A survey and recent developments
Optimality conditions for the minimization of a quadratic with two quadratic constraints
Duality in quadratic programming and l p-approximation
Duality in quadratic programming and l p-approximation
Duality in quadratic programming and l p-approximation
A recipe for semidefinite relaxation for (0
Convex relaxations of 0-1 quadratic programming
Copositive relaxation for general quadratic programming
A semidefinite framework for trust region subproblems with applications to large scale minimization
A New Matrix-Free Algorithm for the Large-Scale Trust-Region Subproblem
Nauk SSSR Tekhn.
Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations
On l p programming
Semidefinite relaxations for the graph partitioning problem
Approximating quadratic programming with bound and quadratic constraints
Some Properties of Trust Region Algorithms for Nonsmooth Optimization
On a subproblem of trust region algorithms for constrained optimization
A dual algorithm for minimizing a quadratic function with two quadratic constraints
Semidefinite programming relaxations for the quadratic assignment problem
--TR

--CTR
Henry Wolkowicz , Miguel F. Anjos, Semidefinite programming for discrete optimization and matrix completion problems, Discrete Applied Mathematics, v.123 n.1-3, p.513-577, 15 November 2002
quadratically constrained quadratic programs;lagrangian relaxations;quadratic assignment;max-cut problems;graph partitioning;semidefinite programming