Interior-Point Algorithms for Semidefinite Programming Based on a Nonlinear Formulation.
Recently in Burer et al. (Mathematical Programming A, submitted), the authors of this paper introduced a nonlinear transformation to convert the positive definiteness constraint on an n  n matrix-valued function of a certain form into the positivity constraint on n scalar variables while keeping the number of variables unchanged. Based on this transformation, they proposed a first-order interior-point algorithm for solving a special class of linear semidefinite programs. In this paper, we extend this approach and apply the transformation to general linear semidefinite programs, producing nonlinear programs that have not only the n positivity constraints, but also n additional nonlinear inequality constraints. Despite this complication, the transformed problems still retain most of the desirable properties. We propose first-order and second-order interior-point algorithms for this type of nonlinear program and establish their global convergence. Computational results demonstrating the effectiveness of the first-order method are also presented.
Introduction
Semidefinite programming (SDP) is a generalization of linear programming in which a
linear function of a matrix variable X is maximized or minimized over an affine subspace
Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice
University acquired in part with support from NSF Grant DMS-9872009.
y School of Mathematics, Georgia Tech., Atlanta, Georgia 30332, USA. This author was supported in part
by NSF Grants INT-9910084 and CCR-9902010. (E-mail: burer@math.gatech.edu).
z School of ISyE, Georgia Tech., Atlanta, Georgia 30332, USA. This author was supported in part by NSF
Grants INT-9600343, INT-9910084 and CCR-9902010. (Email: monteiro@isye.gatech.edu).
x Department of Computational and Applied Mathematics, Rice University, Houston, Texas 77005, USA.
This author was supported in part by DOE Grant DE-FG03-97ER25331, DOE/LANL Contract 03891-99-23
and NSF Grant DMS-9973339. (Email: zhang@caam.rice.edu).
of symmetric matrices subject to the constraint that X be positive semidefinite. Due to
its nice theoretical properties and numerous applications, SDP has received considerable
attention in recent years. Among its theoretical properties is that semidefinite programs
can be solved to a prescribed accuracy in polynomial time. In fact, polynomial-time interior-point
algorithms for SDP have been extensively studied, and these algorithms, especially
the primal-dual path-following algorithms, have proven to be efficient and robust in practice
on small- to medium-sized problems.
Even though primal-dual path-following algorithms can in theory solve semidefinite
programs very efficiently, they are unsuitable for solving large-scale problems in practice
because of their high demand for storage and computation. In [1], Benson et al have
proposed another type of interior-point algorithm - a polynomial-time potential-reduction
dual-scaling method - that can better take advantage of the special structure of the SDP
relaxations of certain combinatorial optimization problems. Moreover, the efficiency of the
algorithm has been demonstrated on several specific large-scale applications (see [2, 6]). A
drawback to this method, however, is that its operation count per iteration can still be
quite prohibitive due to its reliance on Newton's method as its computational engine. This
drawback is especially critical when the number of constraints of the SDP is significantly
greater than the size of the matrix variable.
In addition to - but in contrast with - Benson et al 's algorithm, several methods have
recently been proposed to solve specially structured large-scale SDP problems, and common
to each of these algorithms is the use of gradient-based, nonlinear programming techniques.
In [8], Helmberg and Rendl have introduced a first-order bundle method to solve a special
class of SDP problems in which the trace of the primal matrix X is fixed. This subclass
includes the SDP relaxations of many combinatorial optimization problems, e.g., Goemans
and Williamson's maxcut SDP relaxation and Lov'asz's theta number SDP. The primary
tool for their spectral bundle method is the replacement of the positive-semidefiniteness
constraint on the dual slack matrix S with the equivalent requirement that the minimum
eigenvalue of S be nonnegative. The maxcut SDP relaxation has received further attention
from Homer and Peinado in [9]. Using the original form of the Goemans-Williamson relax-
ation, i.e., not doing the change of variables n\Thetan is the original
variable, they show how the maxcut SDP can be reformulated as an unconstrained maximization
problem for which a standard steepest ascent method can be used. Burer and
Monteiro [3] improved upon the idea of Homer and Peinado by simply noting that, without
loss of generality, V can be required to be lower triangular. More recently, Vavasis [14] has
shown that the gradient of the classical log-barrier function of the dual maxcut SDP can
be computed in time and space proportional to the time and space needed for computing
the Cholesky factor of the dual slack matrix S. Since S is sparse whenever the underlying
graph is sparse, Vavasis's observation may potentially lead to efficient, gradient-based
implementations of the classical log-barrier method that can exploit sparsity.
In our recent paper [5], we showed how a class of linear and nonlinear SDPs can be
reformulated into nonlinear optimization problems over very simple feasible sets of the
is the size of matrix variable X , m is a problem-dependent,
nonnegative integer, and ! n
++ is the positive orthant of ! n . The reformulation is based
on the idea of eliminating the positive definiteness constraint on X by first applying the
substitution done in [3], where L is a lower triangular matrix, and then
using a novel elimination scheme to reduce the number of variables and constraints. We also
showed how to compute the gradient of the resulting nonlinear objective function efficiently,
hence enabling the application of existing nonlinear programming techniques to many SDP
problems.
In [5], we also specialized the above approach to the subclass of linear SDPs in which
the diagonal of the primal matrix X is fixed. By reformulating the dual SDP and working
directly in the space of the transformed problem, we devised a globally convergent, gradient-based
nonlinear interior-point algorithm that simultaneously solve the original primal and
dual SDPs. We remark that the class of fixed-diagonal SDPs includes most of the known
SDP relaxations of combinatorial optimization problems.
More recently, Vanderbei and Benson [13] have shown how the positive semidefinite
constraint on X can be replaced by the n nonlinear, concave constraints [D(X)] ii - 0,
is the unique diagonal matrix D appearing in the standard
of a positive semidefinite matrix X . Moreover, they show how
these concave constraints can be utilized in the solution of any linear SDP using an interior-point
algorithm for general convex, nonlinear programs. Since the discussion of Vanderbei
and Benson's method is mainly of theoretical nature in [13], the question of whether or not
this method offers practical advantages on large-scale SDPs is yet to be determined.
In this paper, we extend the ideas of [5] to solve general linear SDPs. More specifically,
in [5] we showed that if the diagonal of the primal matrix variable X was constrained to
equal a vector d, then the dual SDP could be transformed to a nonlinear programming
problem over the simple feasible set ! n
is the size of the matrix variable
and m is the number of additional primal constraints. The general case described here (that
is, the case in which the diagonal of X is not necessarily constrained as above) is based
on similar ideas but requires that the feasible points of the new nonlinear problem satisfy
nonlinear inequality constraints in addition to lying in the set ! n
These new
inequality constraints, however, can be handled effectively from an algorithmic standpoint
using ideas from interior-point methods.
We propose two interior-point algorithms for solving general linear SDPs based on the
above ideas. The first is a generalization of the first-order (or gradient-based) log-barrier
algorithm presented in [5], whereas the second is a potential reduction algorithm that employs
the use of second-derivative information via Newton's method. We believe that the
first algorithm is a strong candidate for solving large, sparse SDPs in general form and that
the second algorithm will also have relevance for solving small- to medium-sized SDPs, even
though our current perspective is mainly theoretical.
This paper is organized as follows. In Section 2, we introduce the SDP problem studied
in this paper along with our corresponding assumptions, and we briefly summarize the main
results of our previous paper. We then reformulate the SDP into the nonlinear programming
problem mentioned in the previous subsection and introduce and analyze a certain
Lagrangian function which will play an important role in the algorithms developed in this
paper. In Sections 3 and 4, respectively, we develop and prove the convergence of the
two aforementioned algorithms - one being a first-order log-barrier algorithm, another a
second-order potential reduction algorithm - for solving the SDP. In Section 5, we present
computational results that show the performance of the first-order log-barrier algorithm on
a set of SDPs that compute the so-called Lov'asz theta numbers of graphs from the liter-
ature. Also in Section 5, we discuss some of the advantages and disadvantages of the two
algorithms presented in the paper. In the last section, we conclude the paper with a few
final comments.
1.1 Notation and terminology
We use !, n\Thetan to denote the space of real numbers, real n-dimensional column
vectors, and real n \Theta n matrices, respectively, and ! n
++ to denote those subsets of ! n
consisting of the entry-wise nonnegative and positive vectors, respectively. By S n we denote
the space of real n \Theta n symmetric matrices, and we define S n
++ to be the subsets of
consisting of the positive semidefinite and positive definite matrices, respectively. We
to indicate that A 2 S n
++ , respectively. We will also
make use of the fact that each A 2 S n
has a unique matrix square root A 1=2 that satisfies
denotes the space of real n \Theta n lower triangular matrices, and L n
and L n
++ are the subsets of L n consisting of those matrices with nonnegative and positive
diagonal entries, respectively. In addition, we define L nae L n to be the set of all n \Theta n
strictly lower triangular matrices.
We let tr(A) denote the trace of a matrix A 2 ! n\Thetan , namely the sum of the diagonal
elements of A. Moreover, for n\Thetan , we define A In addition,
for denotes the Hadamard product of u and v, i.e., the entry-wise
multiplication of u and v, and if
++ , we define u \Gamma1 to be the unique vector satisfying
e, where e is the vector of all ones. We also define Diag n\Thetan by
U is the diagonal matrix having U
diag is defined to be the adjoint of Diag, i.e.,
We use the notation e to denote the i-th coordinate vector that has
a 1 in position i and zeros elsewhere.
We will use k \Delta k to denote both the Euclidean norm for vectors and its induced operator
norm, unless otherwise specified. The Frobenius norm of a matrix A is defined as
2 The SDP Problem and Preliminary Results
In this section, we introduce a general-form SDP problem, state two standard assumptions
on the problem, and discuss the optimality conditions and the central path for the SDP. We
then describe the transformation that converts the dual SDP into a constrained nonlinear
optimization problem. The consideration of optimality conditions for the new problem
leads us to introduce a certain Lagrangian function, for which we then develop derivative
formulas and several important results. We end the section with a detailed description of
the properties of a certain "primal estimate" associated with the Lagrangian function; these
properties will prove crucial for the development of the algorithms in Sections 3 and 4.
2.1 The SDP problem and corresponding assumptions
In this paper, we study the following slight variation of the standard form SDP problem:
is the matrix variable, and the data of the problem is given by the matrix
the vectors d and the linear function A : S which is
defined by [A(X)] for a given set of matrices fA k g m
ae S n . We remark that
differs from the usual standard form SDP only by the
additional inequality diag(X) - d, but we also note that every standard form SDP can be
written in the form of (P ) by simply adding the redundant constraint diag(X) - d for any
nonpositive vector d 2 ! n . So, in fact, the form (P ) is as general as the usual standard
form SDP.
The need for considering the general form (P ) rather than the usual standard form SDP
arises from the requirement that, in order to apply the transformation alluded to in the
introduction, the dual SDP must possess a special structure. The dual SDP of (P ) is
s.t. Diag(z) +A
z - 0; S - 0
is the matrix variable, z are the vector variables and
A  is the adjoint of the operator A defined by A
. The term
Diag(z) found in the equality constraint of (D) is precisely the "special structure" which
our transformation will exploit. We will describe the transformation in more detail in the
following subsection.
We denote by F 0 (P ) and F 0 (D) the sets of strictly feasible solutions for problems (P )
and (D), respectively, i.e.,
and we make the following assumptions throughout our presentation.
Assumption 1: The set F 0 (P ) \Theta F 0 (D) is nonempty.
Assumption 2: The matrices fA k g m
are linearly independent.
Note that, when a standard form SDP is converted to the form (P ) by the addition of
the redundant constraint diag(X) - d, for any nonpositive d 2 ! n , the strict inequality
diag(X) ? d in the definition of F 0 (P ) is redundant, i.e., for each feasible X - 0, the
inequality diag(X) ? d is automatically satisfied. Hence, F 0 (P ) equals the usual set of
strictly feasible solutions defined by fX 2 0g. In particular, if we
assume that the usual set of interior solutions is nonempty, then F 0 (P ) is also nonempty.
In addition, it is not difficult to see that the set f(y;
of dual strictly feasible solutions for the usual standard form SDP is nonempty if and only
if the set F 0 (D) is nonempty. In total, we conclude that, when a standard form SDP is
put in the form (P ), Assumption 1 is equivalent to the usual assumption that the original
primal and dual SDPs both have strictly feasible solutions.
Under Assumption 1, it is well-known that problems (P ) and (D) both have optimal
solutions respectively, such that C ffl X  This last
condition, called strong duality, can be alternatively expressed as the requirement that
or equivalently that X   S
In addition, under Assumptions 1 and 2, it is well-known that, for each
the problems
(D - ) min
log(\Gammaz
have unique solutions X - and (z respectively, such that
where I 2 ! n\Thetan is the identity matrix and e 2 ! n is the vector of all ones. The set of
solutions known as the primal-dual central path for problems
(D). In the upcoming sections, this central path will play an important role in the
development of algorithms for solving problems (P ) and (D).
2.2 The transformation
In this subsection, we present the primary result of [5] which allows us to transform problem
(D) into an equivalent nonlinear program with n nonlinear inequality constraints. We then
introduce a certain Lagrangian function associated with the new nonlinear program and
prove some key results regarding this function.
Recall that L nae L n denotes the set of all n \Theta n strictly lower triangular matrices. The
following result is stated and proved in [5] (see theorem 4 of section 6 therein).
Theorem 2.1 The following statements hold:
(a) for each (w;
there exists a unique ( ~
(b) the functions ~
L(w; y) and z(w; y) defined according to (2) are each infinitely differentiable
and analytic on their domain ! n
(c) the spaces ! n
are in bijective correspondence according to the assignment (w; y) 7! (z;
It is important to note that the set in (3) differs from the strictly feasible set F 0 (D) in
that the inequality z ! 0 is not enforced.
An immediate consequence of Theorem 2.1 is that the dual SDP (D) can be recast as
the nonlinear program
s.t.
are the vector variables. A few remarks are in order concerning
(NLD) and its relationship to (D). Firstly, the functions ~
L(w; y) and z(w; y) introduced in
the above theorem cannot be uniquely extended to the boundary of ! n
so it is
necessary that w be strictly positive in (NLD). Secondly, the vector constraint z(w; y) !
0, which arises directly from the corresponding constraint of (D), could equivalently be
replaced by z(w; y) - 0. We have chosen the strict inequality because, with z(w; y) ! 0,
there is a bijective correspondence between F 0 (D) and the feasible set of (NLD). Finally,
because the elements of w are not allowed to take the value zero, (NLD) does not in general
have an optimal solution. In fact, only when (d; does (NLD) have an optimal
solution set.
Even though the feasible set of (NLD) does not include its boundary points, we may
still consider the hypothetical situation in which the inequalities w ? 0 and z(w;
are relaxed to w - 0 and z(w; y) - 0. In particular, we can investigate the first-order
optimality conditions of the resulting hypothetical, constrained nonlinear program using
the Lagrangian function
defined by
'(w;
If additional issues such as regularity are ignored in this hypothetical discussion, then the
first-order necessary conditions for optimality could be stated as follows: if (w;
is a local minimum of the function d T z(w; y)+b T y subject to the constraint that z(w; y) - 0,
then there exists
such that
rw '(w;
r y '(w;
One may suspect that these optimality conditions are of little use since they are based on
the hypothetical assumption that z(w; y) and ~
L(w; y) are defined on the boundary of ! n
\Theta
In the following sections, however, we show that these are precisely the conditions which
guarantee optimality when satisfied "in the limit" by a sequence of points f(w k ; y
++ .
2.3 The first and second derivatives of the Lagrangian
In this subsection, we establish some key derivative results for the Lagrangian function '
introduced in the last subsection. In addition to the definition (4) of the Lagrangian, we
define the functions L and S, each respectively mapping the set ! n
++ and
++ , by the formulas
We note that S(w; y) and L(w; y) are the positive definite slack matrix and its Cholesky
factor, respectively, which are associated with (w; y) via the bijective correspondence of
Theorem 2.1.
By (4), it is evident that the derivatives of the Lagrangian are closely related to the
derivatives of the function h
defined as
for all (w;
is an arbitrary, fixed vector. Theorems 2.3 and 2.4
below establish the derivatives of h v based on an auxiliary matrix X that is defined in the
following proposition. Since Proposition 2.2 is an an immediate consequence of lemma 3 of
[5], we omit its proof. (See also proposition 7 in [5].)
Proposition 2.2 Let L 2 L n
++ and v 2 ! n be given. Then the system of linear equations
has a unique solution X in S n .
We remark that the proof of the following theorem is basically identical to the one of
theorem 2 in [5]. It is included here for the sake of completeness and for paving the way
towards the derivation of the second derivatives of h v in Theorem 2.4.
Theorem 2.3 Let (w;
denote the unique
solution of
(a) rw h v (w;
(b) r y h v (w;
Proof. To prove (a), it suffices to show that (@h v =@w i )(w;
Differentiating (8) with respect to w i , we obtain
(w; y)
(w; y)
(w; y)
where the last equality follows from the fact that differentiating (2) with
respect to w i , we obtain
Diag
(w; y)
(w; y)
(w; y)
Taking the inner product of both sides of this equation with X and using the fact that X
is symmetric, we obtain
(w; y)
@ ~
where the second equality follows from the fact that (@ ~
strictly lower triangular
and XL is upper triangular in view of (9). Combining (10) and (12), we conclude
that (a) holds.
Differentiating (8) with respect to y k for a fixed k 2
(w; y)
(w; y)
where the second equality is due to the fact that Differentiating (2) with
respect to y k , we obtain
Diag
(w; y)
@ ~
(w; y)
@ ~
(w; y)
Taking the inner product of both sides of this equation with X and using arguments similar
to the ones above, we conclude that
(w; y)
@ ~
(w; y)
Statement (b) now follows from (13), the last identity, and the definition of A.
Theorem 2.4 Let (w;
denote the unique
solution of (9) in S n , where L j L(w; y). Then, for every ng and k; l 2
@y k @y l
where
(w;
Proof. We will only prove (15) since the proofs of equations (16) and (17) follow by similar
arguments. Note also that the proof of (15) is similar to the proofs of Theorems 2.3(a)
and 2.3(b), and so the proof has been somewhat abridged. Indeed, differentiating (8) with
respect to w i and then with respect to w j , we obtain
(w; y)
Now differentiating (11) with respect to w j , we obtain
Diag
(w; y)
(w; y)
(w; y)
which immediately implies
(w; y)
Combining (19) and (20), we conclude that (15) holds.
Now assume that X - 0. Using (15), (16) and (17), it is straightforward to see that
F
This proves the final statement of the theorem.
Before giving the first and second derivatives of the Lagrangian as corollaries to the
Theorems 2.3 and 2.4, we establish another technical result that will be used later in Section
4.
Lemma 2.5 Let (w;
denote the
unique solution of (9), where L j L(w; y). Suppose also that q
and q T r 2 h v (w; diagonal matrix, where q y is the vector of
the last m components of q.
Proof. and recall from the proof of Theorem 2.4 that the
positive semidefiniteness of X implies
for all q 2 ! n+m , where R is given by (21). Now, using the hypotheses of the lemma, it
is straightforward to see from (22) that Using the
definition of R, (11), (14), and (18), we have
where D i is defined as Diag((@z=@w i )(w; y)) and D k is defined similarly. From the above
equation, it is thus evident that
diagonal matrix.
We remark that the final statement of Theorem 2.4 can be strengthened using Lemma 2.5
if the linear independence of the matrices fe i e T
k=1 is assumed. In particular, it
can be shown that r 2 h v (w; y) - 0 whenever X - 0 and the above collection of the
data matrices is linearly independent. Such an assumption, however, is stronger than our
Assumption 2, and since we intend that the results in this paper be directly applicable
to SDPs that satisfy the usual assumptions, we only assume the linear independence of
k=1 .
Theorems 2.3 and 2.4 and Lemma 2.5 have immediate consequences for the derivatives
of the Lagrangian ', detailed in the following definition and corollary. Note that, in the
result below, we define
wy '
to be the (n m) \Theta (n + m) leading principal block of the Hessian r 2 '(w; y; -) of the
Lagrangian function.
Definition 2.6 For any (w;
denote the unique
solution of (9) in S n with v j -+ d and L j L(w; y). We refer to X(w; as the primal
estimate for (P ) associated with (w;
Corollary 2.7 Let (w;
n be given and define L j L(w; y) and X j
(a) rw '(w;
(b) r y '(w;
(c) r - '(w;
diagonal matrix,
where q y is the vector of the last m components of q.
We again mention that had we assumed linear independence of the matrices fe i e T
k=1 , we would also be able to claim that -
However, with the
weaker Assumption 2, the claim does not necessarily hold.
2.4 Properties of the primal estimate
This subsection establishes several important properties of the primal estimate X(w;
given by Definition 2.6. The following proposition is the analogue of lemma 5 of [5].
Lemma 2.8 Let (w;
(a) XL is upper triangular, or equivalently, L T XL is diagonal;
only if rw ' - 0; in addition, X - 0 if and only if rw ' ? 0;
(c) w   rw
Proof. The upper triangularity of XL follows directly from (9). Since L T and XL are both
upper triangular, so is the product L T XL which is also symmetric. Hence L T XL must be
diagonal. On the other hand, if L T XL is diagonal, say it equals D, then
upper triangular. So, (a) follows.
To prove the first part of (b), we note that the nonsingularity of L implies that X - 0
if and only if L T XL - 0, but since L T XL is diagonal by (a), L T XL - 0 if and only
if diag(L T XL) - 0. Given that both L T and XL are upper triangular matrices, it is
easy to see that diag(L T XL) is the Hadamard product of diag(L T ) and diag(XL). Since
only if diag(XL) - 0. The first
statement of (b) now follows from the sequence of implications just derived and the fact
that rw by Corollary 2.7(a).
The second part of (b) can be proved by an argument similar to the one given in the
previous paragraph; we need only replace the inequalities by strict inequalities.
Statement (c) follows from (7), Proposition 2.7(a), and the simple observation that the
diagonal of L T XL is the Hadamard product of diag(L T since both L T
and XL are upper triangular.
The following proposition establishes that the matrix X(w; plays the role of a
(possibly primal estimate for any (w;
justification to its name in Definition 2.6. In particular, it gives necessary and sufficient
conditions for X(w; y; -) to be a feasible or strictly feasible solution of (P ). It is interesting
to note that these conditions are based entirely on the gradient of the Lagrangian function
Proposition 2.9 Let (w;
(a) X is feasible for (P) if and only if rw ' - 0 and r y
(b) X is strictly feasible for (P) if and only if rw ' ? 0 and r y
Proof. By the definition of X , we have X 2 S n and d. The theorem is
an easy consequence of Corollary 2.7(b) and Lemma 2.8(b).
The following proposition provides a measure of the duality gap, or closeness to optimal-
ity, of points (w;
and X(w;
are feasible for (NLP ) and (P ), respectively.
Proposition 2.10 Let (w;
is feasible for (D), and
Proof. The feasibility of X follows from Proposition 2.9, and that of (z; y; S) from the
definitions of z and S, and the assumption z - 0. The above equality follows from the
substitutions as well as from Lemma 2.8(c).
3 A Log-Barrier Algorithm
It is well known that under a homeomorphic transformation -, any path in the domain of -
is mapped into a path in the range of -, and vice versa. Furthermore, given any continuous
function f from the range of - to !, the extremers of f in the range of - are mapped into
corresponding extremers of the composite function f(-(\Delta)) in the domain of -. In particular,
if f has a unique minimizer in the range of -, then this minimizer is mapped into the unique
minimizer of f(-(\Delta)) in the domain of -.
In view of these observations, it is easy to see that, under the transformation introduced
in Section 2, the central path of the SDP problem (D) becomes a new "central path" in
the transformed space. Furthermore, since the points on the original central path are the
unique minimizers of a defining log-barrier function corresponding to different parameter
values, the points on the transformed central path are therefore unique minimizers of the
transformed log-barrier function corresponding to different parameter values. In general,
however, it is possible that extraneous, non-extreme stationary points could be introduced
to the transformed log-barrier function by the nonlinear transformations applied. In this
section, we show that the transformed log-barrier functions in fact have no such non-extreme
stationary points, and we use this fact to establish a globally convergent log-barrier algorithm
for solving the primal and dual SDP.
In the first subsection, we describe the central path in the transformed space, and then
some technical results that ensure the convergence of a sequence of primal-dual points are
given in the second subsection. Finally, the precise statement of the log-barrier algorithm
as well as its convergence are presented in the last subsection.
3.1 The central path in the transformed space
Given the strict inequality constraints of (NLD), a natural problem to consider is the
following log-barrier problem associated with (NLD), which depends on the choice of a
log
log(\Gammaz
is the i-th coordinate
function of z(w; y). (The reason for the factor 2 will become apparent shortly.) Not sur-
prisingly, (NLD - ) is nothing but the standard dual log-barrier problem (D - ) introduced in
Section 2.1 under the transformation given by Theorem 2.1, i.e., (D - ) is equivalent to the
nonlinear program
min
log(\Gammaz
which is exactly (NLD - ) after the simplification
log(det
log
and the next-to-last equality follows from the fact that
the determinant of a triangular matrix is the product of its diagonal entries.
Recall from the discussion in Section 2.1 that the primal and dual log-barrier problems
(D - ) and (P - ) each have unique solutions (z respectively, such that (1)
holds. One can ask whether (NLD - ) also has a unique solution, and if so, how this unique
solution relates to (z . The following theorem establishes that (NLD - )
does in fact have a unique stationary point (w which is simply the inverse image of
the point (z under the bijective correspondence given in Theorem 2.1.
Theorem 3.1 For each - ? 0, the problem (NLD - ) has a unique minimum point, which
is also its unique stationary point. This minimum (w - ; y - ) is equal to the inverse image
of the point (z under the bijective correspondence of Theorem 2.1. In particular,
Proof. Let (w; y) be a stationary point of (NLD - ), and define -
rw z j r z z(w; y) and r y z j r y z(w; y). Since (w; y) is a stationary point, it satisfies the
first-order optimality conditions of (NLD - )
(Recall that rw z is an n \Theta n matrix and that r y z is an m \Theta n matrix.) Using the definitions
of f and ', we easily see that [rz]-. Using this relation, the definition of -, we
easily see that the above optimality conditions are equivalent to
is the vector of all ones. It is now clear from (24) and Proposition 2.9 that X
is a strictly feasible solution of (P ).
Corollary 2.7(a) implies that the first equation of (24) is equivalent to diag(XL)
and so the equality which in turn
implies that diag(L T since XL is upper triangular by the definition of X . Since
L T XL is diagonal, it follows that L T hence that Note also that,
by the definitions of - and X(w;
satisfy the conditions of (1), and this clearly implies
We conclude that (NLD - ) has a unique stationary point satisfying all the conditions stated
in the theorem. That this stationary point is also a global minimum follows from the fact
that is the global minimum of (D - ).
3.2 Sufficient conditions for convergence
In accordance with the discussion in the last paragraph of Section 2.2, we now consider the
Lagrangian function '(w; only on the open set
Given a sequence of points f(w k ; y
The following
result gives sufficient conditions for the sequences f(z
to be bounded.
Lemma 3.2 Let f(w
ae\Omega be a sequence of points such that
ffl the sequences f(w k ) T rw ' k g and f(- k ) T z k g are both bounded.
Then the sequences f(z are bounded.
Proof. By Assumption 1, there exists a point -
the definition of F 0 (P ), we have -
Clearly, N 0 is a bounded open set containing -
Hence, by the linearity of A, A(N 0 )
is an open set containing
2.7(b) and the assumption that
we conclude that lim k!1 A(X k hence that A(X k
all k sufficiently large, say k . Hence, there exists ~
for all k - k 0 . We define ~
for each k - k 0 , and since ~
and moreover that f ~
is a bounded sequence.
Now let (-z
a point in F 0 (D), that is, a feasible solution of (D) such that
For each k - k 0 , we combine the information from the previous
paragraph, the fact that diag and A are the adjoints of Diag and A   , respectively, and the
inequalities to obtain the following inequality:
z 0
Using this inequality and the fact that ~
for all k - k 0 , where the last inequality follows from the fact that X k - 0, which itself
follows from Proposition 2.9(b) and the assumption that rw ' - 0. By Proposition 2.8,
the assumption that f(w k ) T rw ' k g is bounded implies that fX k ffl S k g is bounded which,
together with the fact that f(- k ) T z k g and f ~
are bounded, implies that the left-hand
side of the above inequality is bounded for all k - k 0 . It thus follows from the positive
definiteness of -
S 0 and jI that both fX k g and fS k g are bounded.
The boundedness of fS k g clearly implies the boundedness of fL k g and hence the boundedness
of fw k )g. In addition, since - the
boundedness of fX k g implies that f- k g is bounded which, together with the boundedness
of f(- k ) T z k g, implies that fz k g is bounded. Now, using the boundedness of fS k g and fz k g
along with Assumption 2, we easily see that fy k g is bounded.
In Section 2.2, we used a hypothetical discussion of the optimality conditions of (NLD)
to motivate the use of the Lagrangian function '. In the following theorem, we see that the
hypothetical optimality conditions (5) do in fact have relevance to the solution of (NLD).
In particular, the theorem shows that if f(w k ; y is a sequence of points satisfying (5a)
for each k - 0 and if (5b), (5c) and (5d) are satisfied in the limit, then any accumulation
points of the corresponding sequences fX k g and f(z are optimal solutions of (P )
and (D), respectively.
Theorem 3.3 Let f(w
ae\Omega be a sequence of points such that z k ! 0 and
and such that
lim
z k   -
Then:
(a) the sequences fX k g and f(z are bounded, and;
(b) any accumulation points of fX k g and f(z are optimal solutions of (P ) and
(D), respectively.
Proof. The proof of statement (a) follows immediately from Lemma 3.2. To prove (b), let
accumulation points of the sequences fX k g, f(z
and f- k g, respectively, where the boundedness of f- k g also follows from Lemma 3.2. The
assumptions and Proposition 2.9 imply that
lim
This clearly implies that
and
that is, X 1 is a feasible solution of (P ). Since each (z k ; y k feasible solution of (D),
it follows that (z 1 feasible solution of (D). Moreover, by Proposition 2.8,
we have that (w k 0, from which it follows that X 1 ffl S
and also that [diag(X k 0, from which it follows that
We have thus shown that X 1 and (z 1 are optimal
solutions of (P ) and (D).
3.3 A globally convergent log-barrier algorithm
In this short subsection, we introduce a straightforward log-barrier algorithm for solving
(NLD). The convergence of the algorithm is a simple consequence of Theorem 3.3.
Let constants be given, and for each - ? 0, define
m to be the set of all points (w; y) satisfying
e,
ffl kr y 'k - \Gamma-,
is the vector of all ones. Note that each
and that the unique minimizer (w - ; y - )
of (NLD - ) is in N (-). (See the proof of Theorem 3.1 and equation (24) in particular.) We
propose the following algorithm:
Log Barrier Algorithm:
For
1. Use an unconstrained minimization method to solve (NLD - k
approximately, obtaining a point (w
2. Set - increment k by 1, and return to step 1.
End
We stress that since (NLD - k
) has a unique stationary point for all - k ? 0 which is also the
unique minimum, step 1 of the algorithm will succeed using any reasonable unconstrained
minimization method. Specifically, any convergent, gradient-based method will eventually
produce a point in the set N (- k ).
If we define - then based on the definition of N (-) and
Proposition 2.8(b), the algorithm clearly produces a sequence of points f(w k ; y
that satisfies the hypotheses of Theorem 3.3. Hence, the log-barrier algorithm converges in
the sense of the theorem.
4 A Potential Reduction Algorithm
In this section, we describe and prove the convergence of a potential reduction interior-point
algorithm for solving (NLD). The basic idea is to produce a sequence of points
satisfying the hypotheses of Theorem 3.3 via the minimization of a special
merit function defined
This minimization is performed using an Armijo line search
along the Newton direction of a related equality system.
Throughout this section, we assume that a point (w
2\Omega is given that satisfies
4.1 Definitions, technical results and the algorithm
We define f
\Phi (w;
Note that (w \Xi. The potential reduction algorithm, which we state explicitly at
the end of this subsection, will be initialized with the point (w subsequently
produce a sequence of points f(w k ; y
requirement that rw '(w nonnegative for all k is reasonable in light of our goal
of producing a sequence satisfying the hypotheses of Theorem 3.3. The third requirement
that f(w k ; y k ) be less than f + for all k - 0 is technical and will be used to prove special
properties of the sequence produced by the algorithm.
We also define F : \Xi
!\Omega by
F (w;
r y '(w;
\Gamma-   z(w; y)7 5 j6 4
e
\Gamma-
is the vector of all ones. For m, we let F i denote the i-th
coordinate function of F . Note that fF are the n scalar functions corresponding
to the elements of w   rw '(w; hold between fF
and r y '(w; as well as between fF and \Gamma-   z(w; y). In addition,
we define N ng [ fn +m+ mg.
With the definition of F , our goal of producing a sequence of points satisfying the
hypotheses of Theorem 3.3 can be stated more simply as the goal of producing a sequence
ae \Xi such that
lim
The primary tool which allows us to accomplish (27) is the merit function
by
log
is an arbitrary constant satisfying i ? n. The
usefulness of this merit function comes from the fact that (27) can be accomplished via
the iterative minimization of M by taking a step along the Newton direction of the system
F (w; at the current point. In what follows, we investigate this minimization
scheme.
Since we will apply Newton's method to the nonlinear system F (w; need
to study the nonsingularity of the Jacobian F 0 (w; To simplify our notation, for all
(w;
2\Omega we define
Recall that -
is the leading principal block of r 2 ' as defined in (23). Straightforward
differentiation of F (w;
e
\Gamma-
e
\Gamma-
Now multiplying F 0 (w; by the diagonal matrix Diag([w \GammaT
For (w; the Newton equation F 0 (w; z; -)[\Deltaw; \Deltay;
equivalent to
\Deltaw
\Deltay
\Delta-
e
Note that P (w; y; -) is a (2n+m) \Theta (2n+m) matrix which is in general asymmetric. We will
use the matrix P (w; y; -) to help establish the nonsingularity of F 0 (w; in the following
lemma.
Lemma 4.1 For (w; \Xi, the matrix P (w; positive definite and consequently,
the Jacobian F 0 (w;
Proof. Since F 0 (w; is the product of P (w; with a positive diagonal matrix, it
suffices to prove the first part of the lemma. Combining the fact that (w;
Lemma 2.8(b) and Corollary 2.7(d), we see that -
(However, it is not necessarily
positive definite even though X - 0; see the discussion after Corollary 2.7). Moreover, we
have
Hence, we conclude from (29) that is the sum of two positive semidefinite
matrices and one skew-symmetric matrix. It follows that P is positive semidefinite.
It remains to show that P is invertible, or equivalently that (\Deltaw; \Deltay;
the unique solution to the system
\Deltaw
\Deltay
\Delta-
where the sizes of the zero-vectors on the right-hand side should be clear from the context.
\Delta-) be a solution to (32). Pre-multiplying both sides of (32) by the row
vector using (29), we obtain a sum of three terms corresponding to
the three matrices in (29) that add to zero. By skew-symmetry of the third matrix in (29),
the corresponding term is zero; and by positive semidefiniteness of the first two matrices,
the first two terms are both nonnegative and thus each of them must be zero. The term
corresponding to the first matrix in (29) leads to
\Deltaw
which, together with (31), implies that (\Deltaw; \Delta-) = (0; 0). Rewriting (32) to reflect this
information, we obtain the equations
"\Deltay
"0
"\Deltay
where again the sizes of the zero-vectors should be clear from the context.
Since (w; we see from Lemma 2.8(b) that X(w; This fact together
with the first equation of (33) implies that the hypotheses of Corollary 2.7(e) hold with
It follows that A   (\Deltay) is a diagonal matrix.
A   (\Deltay), and let X 2 S n denote the unique solution of with respect to v and L j L(w; y).
Using the second equation of (33), the fact that rh v, and Theorem 2.3(b), we obtain
\Deltay T [r y
where the fifth equality is due to the identity and the sixth is due to the
fact that diag(X) = v. Hence, we conclude that Assumption 2,
this implies that \Deltay = 0, thus completing the proof that P is positive definite.
We remark that, if we had assumed linear independence of the entire collection fe
, then the proof that P (w; positive definite in the above proof would have
been trivial due to the fact that X(w;
(see the discussion
after Corollary 2.7). In any case, even though the proof was more difficult, our weaker
Assumption 2 still suffices to establish the nonsingularity of F 0 (w;
A direct consequence of Lemma 4.1 is that, for each (w; \Xi, the Newton direction
(\Deltaw; \Deltay; \Delta-) for the system F (w; exists at (w; y; -). Stated differently, Lemma
4.1 shows that the system
has a unique solution for all (w; \Xi. The following lemmas show that this Newton
direction is a descent direction for f (when (\Deltaw; \Deltay) is used as the direction) and also for
M.
Lemma 4.2 Let (w; \Delta-) be the Newton direction at (w;
given by (34). Then (\Deltaw; \Deltay) is a descent direction for f at (w; y).
Proof. Let -
P be the (n +m) \Theta (n +m) leading minor of P (w;
r'
r' consists of the first components of r'. Note that -
P is positive definite
since P (w; positive definite by Lemma 4.1.
Equation (34) implies that (30) holds. Using (26), (29), and (35), it is easy to see that
(30) can be rewritten as the following two equations:
\Deltaw
\Deltay
\Deltaw
\Deltay
Solving for \Delta- in the second equation and substituting the result in the first equation, we
obtain
\Deltaw
\Deltay
\Gammaz
\Deltaw
\Deltay
Multiplying the above equation on the left by the row vector [\Deltaw T ; \Deltay T ], noting that
using the positive definiteness of -
P , we have
\Deltaw
\Deltay
\Deltaw
\Deltay
\Deltaw
\Deltay
0:
The fact that \Gammaz \Gamma1   - ? 0 clearly implies that the matrix rz Diag(\Gammaz \Gamma1   -)rz T is positive
semidefinite. This combined with the above inequality proves that (\Deltaw; \Deltay) is a descent
direction for f at (w; y).
Lemma 4.3 Let (w; \Delta-) be the Newton direction at (w;
given by (34). Then (\Deltaw; \Deltay; \Delta-) is a descent direction for M at (w;
Proof. We first state a few simple results which we then combine to prove the lemma. Let
Then equation (34) implies that
\Deltaw
\Deltay
\Delta-
\Deltaw
\Deltay
\Delta-
We have from Lemma 4.2 that
\Deltaw
\Deltay
0: (37)
In addition, using (28), we have that
rf#
where we note that r - f(w;
using (36), (37), (38) and the inequalities i ? n and f(w; y)
\Deltaw
\Deltay
\Delta-
which proves that (\Deltaw; \Deltay; \Delta-) is a descent direction for M at (w;
Given (w;
where (\Deltaw; \Deltay; \Delta-) is the Newton direction given by (34). An important step in the
potential reduction algorithm is the Armijo line
the line search selects a step-size ff ? 0 such that (w(ff); y(ff); -(ff)) 2 \Xi and
\Deltaw
\Deltay
\Delta-
-). Due to the
fact that \Xi is an open set and also due to Lemma 4.3, such an ff can be found in a finite
number of steps.
We are now ready to state the potential reduction algorithm.
Potential Reduction (PR) Algorithm:
For
1. Solve system (34) for (w; to obtain the Newton
direction
2. Let j k be the smallest nonnegative integer such that
(w and such that (40) holds with
3. Set (w increment k by 1,
and return to step 1.
End
We remark that, due to Lemma 4.3, Algorithm PR monotonically decreases the merit
function M.
4.2 Convergence of Algorithm PR
In this subsection, we prove the convergence of the potential reduction algorithm given
in the previous subsection. A key component of the analysis is the boundedness of the
sequence produced by the algorithm, which is established in Lemmas 4.5 and 4.7.
k-0 be the sequence produced by the potential reduction algorithm,
and define f
Lemma 4.4 The sequence fF k g is bounded. As a result, the sequences fX k ffl S k g and
are also bounded.
Proof. Consider the function p
defined by
log
log
where i is the same constant appearing in (28). It is not difficult to verify (see Monteiro
and Pang [12], for example) that p is coercive, i.e., for every sequence f(r
1. This property implies that the
level set
is compact for all
The definition of M implies that, for all (w;
By the assumption that both the primal SDP (P ) and the dual SDP (D) are feasible,
duality implies that there exists a constant f \Gamma such that the dual objective value
implies that
for all (w; combining (42) with the fact that the potential reduction algorithm
decreases the merit function M in each iteration, we see that
for all k - 0. This in turn shows that
We conclude that fF k g is contained in a compact set and hence is bounded.
The boundedness of fX k ffl S k g and fA(X k now follows immediately from (26),
Lemma 2.8(c) and Corollary 2.7(b).
Lemma 4.5 The sequences f(z are bounded.
Proof. It suffices to show that the sequences fS k g and fz k g are bounded since, as in the
proof of Lemma 3.2, the boundedness of fS k g and fz k g immediately implies the boundedness
of fy k g, fL k g and fw k g. Let -
that, for each k - 0,
It follows from the inequalities -
is bounded. In addition, since
0, the above relation and the boundedness of fz k g imply
that fS k g is bounded.
Lemma 4.6 The sequence fC ffl X k g is bounded.
Proof. By Lemma 4.4, there exists
This implies the following relation, which holds for all k - 0:
is bounded and since fA(X k fy k g are bounded by Lemmas 4.4 and
4.5, we conclude from the above relation that fC ffl X k g is bounded.
Lemma 4.7 The sequences fX k g and f- k g are bounded.
Proof. Let (-z
note that -
Consider the following relation,
which holds for all k - 0:

From this relation, Lemmas 4.4 and 4.6, and the fact that -
we conclude that fX k g
is bounded. In addition, since diag(X k we conclude that f- k g is
bounded.
The following theorem proves the convergence of the potential reduction algorithm. We
remark that the key result is the convergence of fF k g to zero, which is stated in part (a)
of the theorem. Part (b) is already implied by Lemmas 4.5 and 4.7, and once (a) has been
established, part (c) follows immediately from Theorem 3.3.
Theorem 4.8 Let f(w be the sequence produced by algorithm PR. Then:
(a) lim
(b) the sequences fX k g and f(z are bounded;
(c) any accumulation points of fX k g and f(z are optimal solutions of (P ) and
(D), respectively.
Proof. To prove (a), assume for contradiction that (a) does not hold. Then Lemma 4.4
implies that there exists a convergent subsequence fF k g k2K such that F 1 j lim k2K F k 6= 0.
By Lemmas 4.5 and 4.7, we may also assume that the sequence f(w k ; y
to a point (w
is bounded, and due to the weak duality between (P ) and
(D), there exist constants such that
log
log F k
These three inequalities together imply that
lim
since otherwise, M(w towards infinity, an impossibility since the algorithm
has produced a sequence which monotonically decreases the merit function M.
Hence, we conclude that F 1 2 \Omega\Gamma and so we clearly have that (w 1 It follows
that the Newton direction (\Deltaw exists at (w 1
and in addition, the sequence f(\Deltaw k ; \Deltay k ; \Delta- k )g k2K of Newton directions converges to
Moreover, by the inequality (39) found in the proof of Lemma 4.3, we
have that
\Deltay 1
\Delta-
converges in \Xi and since M is continuous on \Xi, it follows that
converges. Using the relation
\Deltaw k
\Deltay k
\Delta-
and where the first and second inequalities follow from (40) and (39), re-
spectively, we clearly see that lim k2K ae since the left-hand side tends to zero as k 2 K
tends to infinity. This implies lim k2K
tends to infinity as k 2 K tends to infinity, we conclude that the Armijo
line search requires more and more trial step-sizes as k 2 K increases. Recall that the
line search has two simultaneous objectives: given (w; \Xi, the line search finds a
step-size ff ? 0 such that (w(ff); y(ff); -(ff)) 2 \Xi and such that relation (40) is satisfied.
converge to (w 1
respectively, where \Xi is an open set, it is straightforward to see that
there exist ~ j - 0 and ~
K such that
(w
for all j - ~ j and all k 2 K such that k - ~ k. Hence, due to the fact that lim k2K
there exists -
k such that, for all k -
k, we have which implies (46) holds with
but (40) is not satisfied for the step-size ae
\Deltaw k
\Deltay k
\Delta-
Letting k 2 K tend to infinity in the above expression, we obtain
\Deltay 1
\Delta-
\Deltay 1
\Delta-
which contradicts (45) and the fact that oe 2 (0; 1). Hence, we conclude that statement (a)
does in fact hold.
Statements (b) and (c) hold as discussed prior to the statement of the theorem.
Computational Results and Discussion
In this section, we discuss some of the advantages and disadvantages of the two algorithms
presented in Sections 3 and 4, and we also present some computational results for the
first-order log-barrier algorithm.
5.1 First-order versus second-order
It is a well-known phenomenon in nonlinear programming that first-order (f-o) methods,
i.e., those methods that use only gradient information to calculate their search directions,
typically require a large number of iterations for convergence to a high accuracy, while
second-order (s-o) methods, i.e., those that also use Hessian information, converge to the
same accuracy in far fewer iterations. The benefit of f-o methods over s-o methods, on the
other hand, is that gradient information is typically much less expensive to obtain than
Hessian information, and so f-o iterations are typically much faster than s-o iterations.
For many problems, s-o approaches are favored over f-o approaches since the small
number of expensive iterations produces an overall solution time that is better than the
f-o method's large number of inexpensive iterations. For other problems, the reverse is
true. Clearly, the relative advantages and disadvantages must be decided on a case-by-case
analysis.
For semidefinite programming, the current s-o interior-point methods (either primal-dual
or dual-scaling) have proven to be very robust for solving small- to medium-sized problems
to high accuracy, but their performance on large-sized problems (with large n and/or m)
has been mostly discouraging because the cost per iteration increases dramatically with
the problem size. In fact, these methods are often inappropriate for obtaining solutions of
even low accuracy. This void has been filled by f-o methods, which have proven capable
of obtaining moderate accuracy in a reasonable amount of time (see the discussion in the
introduction).
It is useful to consider the two algorithms presented in this paper in light of the above
comments. We feel that the f-o log-barrier algorithm will have its greatest use for the
solution of large SDPs. In fact, in the next section we give some computational results indicating
this is the case when n is of moderate size and m is large. The s-o potential reduction
method, however, will most likely not have an immediate impact except possibly on small-
to medium-sized problems. In addition, there may be advantages of the potential-reduction
algorithm over the conventional s-o interior-point methods. For example, the search direction
computation may be less expensive in the (w; y)-space, either if one solves the Newton
system directly or approximates its solution using the conjugate gradient method. (This is
a current topic of investigation.) Overall, the value of the potential reduction method is
two-fold: (i) it demonstrates that the convexity of the Lagrangian in the neighborhood \Xi
allows one to develop s-o methods for the transformed problem; and (ii) such s-o methods
may have practical advantages for solving small- to medium-sized SDPs.
5.2 Log-barrier computational results
Given a graph G with vertex set ng and edge set E, the Lov'asz theta number
# of G (see [11]) can be computed as the optimal value of the following primal-dual SDP
min
where are the variables, I is the n \Theta n identity matrix, e 2 ! n is the vector of
all ones, and e k 2 ! n is the k-th coordinate vector. Note that both the primal and dual
problems have strictly feasible solutions.
We ran the log-barrier algorithm on nineteen graphs for which n was of small to moderate
size but m was large. In particular, the size of m makes the solution of most of these Lov'asz
theta problems difficult for second-order interior-point methods. The first nine graphs
were randomly generated graphs on 100 vertices varying in edge density from 10% to 90%,
while the last ten graphs are the complements of test graphs used in the Second DIMACS
Challenge on the Maximum Clique Problem [10]. (Note that, for these graphs, the Lov'asz
theta number gives an upper bound on the size of a maximum clique.)
We initialized the log-barrier algorithm with
the specific w ? 0 corresponding to z = \Gammae. (Such a w was found by a direct Cholesky
factorization.) In this way, we were able to begin the algorithm with a feasible point. The
initial value of - was set to 1, and after each log-barrier subproblem was solved, - was
decreased by a factor of 10. Moreover, the criterion for considering a subproblem to be
solved was slightly altered from the theoretical condition described in Section 3.3. For the
computational results, we found it more efficient to consider a subproblem solved once the
norm of the gradient of the barrier function became less than 10 \Gamma3 . The overall algorithm
was terminated once - reached the value 10 \Gamma6 .
Our computer code was programmed in ANSI C and run on an SGI Origin2000 with
Gigabytes of RAM at Rice University, although we
stress that our code is not parallel. In Table 5.2, we give the results of the log-barrier
algorithm on the nineteen test problems. In the first four columns, information regarding
the problems are listed, including the problem name, the sizes of n and m, and a lower
bound on the optimal value for the SDP. We remark that
that the lower bounds were computed with the primal SDP code described in [4]. In the
next four columns, we give the objective value obtained by our code, the relative accuracy
of the final solution with respect to the given lower bound, the time in seconds taken by
the method, and the number of iterations performed by the method. From the table, we
can see that the method can obtain a nearly optimal solution (as evidenced by the good
relative accuracies) in a small amount of time even though m can be quite large. We also
see that the number of iterations is quite large, which is not surprising since the method is
a first-order algorithm.
6 Concluding Remarks
Conventional interior-point algorithms based on Newton's method are generally too costly
for solving large-scale semidefinite programs. In search of alternatives, some recent papers
have focused on formulations that facilitate in one way or another the application of
gradient-based algorithms. The present paper is one of the efforts in this direction.
In this paper, we apply the nonlinear transformation derived in [5] to a general linear
SDP problem to obtain a nonlinear program with both positivity constraints on variables
and additional inequality constraints as well. Under the standard assumptions of the primal-dual
strict feasibility and the linear independence of constraint matrices, we establish global
convergence for a log-barrier algorithmic framework and a potential-reduction algorithm.
Our initial computational experiments indicate that the log-barrier approach based on
our transformation is promising for solving at least some classes of large-scale SDP problems
including, in particular, problems where the number of constraints is far greater than the
size of the matrix variables. The potential reduction algorithm is also interesting from a
theoretical standpoint and for the advantages it may provide for solving small- to medium-scale
problems. We believe both methods are worth more investigation and improvement.

Table

1: Performance of the Log-Barrier Algorithm on Lov'asz Theta Graphs
low bd obj val acc time iter
rand2 100 992 22.1225 22.1234 4.2e\Gamma05 528 18877
rand3 100 1487 17.0210 17.0221 6.4e\Gamma05 629 21264
rand4 100 1982 13.1337 13.1355 1.4e\Gamma04 682 22560
rand5 100 2477 10.4669 10.4678 8.6e\Gamma05 696 22537
rand6 100 2972 8.3801 8.3814 1.5e\Gamma04 829 24539
rand7 100 3467 7.0000 7.0001 2.1e\Gamma05 137 4106
rand8 100 3962 5.0000 5.0000 9.5e\Gamma06 176 5218
rand9 100 4457 4.0000 4.0000 4.5e\Gamma06 118 3612
brock200-1.co 200 5068 27.4540 27.4585 1.6e\Gamma04 3605 16083
brock200-4.co 200 6813 21.2902 21.2946 2.1e\Gamma04 4544 20092
c-fat200-1.co 200 18368 12.0000 12.0029 2.5e\Gamma04 2560 9337
johnson08-4-4.co 70 562 14.0000 14.0004 3.1e\Gamma05 28 2519
san200-0.7-1.co 200 5972 30.0000 30.0002 5.5e\Gamma06 273 973



--R

Solving large-scale sparse semidefinite programs for combinatorial optimization
Approximating Maximum Stable Set and Minimum Graph Coloring Problems with the Positive Semidefinite Relaxation.
A Projected Gradient Algorithm for Solving the Max-cut SDP Relaxation
A Nonlinear Programming Algorithm for Solving Semidefinite Programs via Low-rank Factorization
Solving a Class of Semidefinite Programs via Nonlinear Programming.
Application of Semidefinite Programming to Circuit Partitioning.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.
A spectral bundle method for semidefinite programming.
Design and performance of parallel and distributed approximation algorithms for maxcut.

On the Shannon Capacity of a graph.
A potential reduction Newton method for constrained equations.
On Formulating Semidefinite Programming Problems as Smooth Convex Nonlinear Optimization Problems.
A Note on Efficient Computation of the Gradient in Semidefinite Program- ming
--TR
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Design and performance of parallel and distributed approximation algorithms for Maxcut
Cliques, Coloring, and Satisfiability
A Potential Reduction Newton Method for Constrained Equations
Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
A Spectral Bundle Method for Semidefinite Programming
nonlinear programming;semidefinite program;interior-point methods;semidefinite relaxation