##
A primitive interior-point algorithm for semidefinite programs in Mathematica

###
Masakazu Kojima

In these few years, SDPs (semidefinite programs) have been studied
intensively in mathematical programming circles. Particularly SDPs
have important applications to combinatorial optimization and
systems and control theory. The References include a partial list
of literatures on applications of SDPs to these fields and computational
methods for SDPs. Recently Kojima, Shindoh and Hara proposed an
interior-point algorithm for monotone linear complementarity problems
in symmetric matrices. When their algorithm is applied to SDPs, it
works as a primal-dual interior-point algorithm which simultaneously
generates approximate optimal solutions of a given SDP and its dual.
The aim of this working paper is to present a simple and basic version
of their primal-dual interior-point algorithm for SDPs together with
a computer program of the algorithm in *Mathematica*, placing
the emphasis on easy understanding of the fundamental idea of the
algorithm without going into its theoretical details.
Section 1 describes a primal-dual pair of SDPs, and Section 2 describes
the existence of the central trajectory which plays an essential role
in the primal-dual interior-point algorithm for SDPs. Sections 3 and 4
are devoted to a Primitive Interior Point ALgorithm for SDPs. Although
the PINPAL in *Mathematica* can solve only small dimensional SDPs,
it will provide useful information on how we develop practical and/or
more efficient computer programs of the primal-dual interior-point
algorithm for SDPs. "PINPAL in *Mathematica* for Macintosh" and
"PINPAL in *Mathematica* for Windows" are available via anonymous
ftp into ftp.is.titech.ac.jp. The
pinpal package is in tar-ed and
compress-ed format with the name pinpal.tar.Z in the directory
pub/OpRes/software.

Research Reports on Information Sciences B-293, December 1994.