Speaker:   Prof. Henry Wolkowicz
  Univ. of Waterloo
  Dept of Comb and Opt
  Waterloo, Ont./td>
  CANADA N2L 3G1


Title: Solving Semidefinite Programs for and via Nonlinear Programming

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.