Penalty/Barrier Multiplier Algorithm for Semidefinite Programming

Leonid Mosheyev and Michael Zibulevsky

We present a generalization of the Penalty/Barrier Multiplier algorithm for the semidefinite programming, based on a matrix form of Lagrange multipliers. Our approach allows to use among others logarithmic, shifted logarithmic, exponential and a very effective quadratic-logarithmic penalty/barrier functions. We present dual analysis of the method, based on its correspondence to a proximal point algorithm with nonquadratic distance-like function. We give computationally tractable dual bounds, which are produced by the Legendre transformation of the penalty function. Numerical results for large-scale problems from robust control, stable truss topology design and optimal material design demonstrate high efficiency of the algorithm.

Preprint, September, 1999