Interior-Point Abstracts

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.