title:
Solving Semidefinite Programs for and via Nonlinear Programming
title change to:
Semidefinite Programming and Some Closest Matrix Approximation
Problems
Semidefinite Programming, SDP, refers to optimization problems where the
vector variable is a symmetric matrix, which is required to be positive
semidefinite. Though SDPs (under various names)
have been studied as far back as the 1940s, the interest has grown
tremendously during the last ten years. This is due partly to the many
diverse applications in e.g. engineering, combinatorial optimization,
and statistics; and due partly to the great advances in
efficient solutions for these types of problems.
The efficient solution techniques for SDP are based on extensions of
interior-point methods from linear programming. These methods have
proved efficient in practice and in theory, i.e. many are based on
polynomial time algorithms.
We take a different point of view.
We solve SDPs using standard nonlinear programming techniques
applied to the overdetermined system of nonlinear equations obtained from
the optimality conditions. This results in a Gauss-Newton method for
SDP. We present convergence analysis and numerical experience.
We then look at applications of SDP for solving nonlinear programming
problems. We look at two of the most popular methods for
unconstrained and constrained optimization:
trust region methods for
general unconstrained nonlinear problems and
sequential quadratic programming for constrained problems.