title:
Solving Semidefinite Programs for and via Nonlinear Programming

speaker:
Prof. Henry Wolkowicz    |Email hwolkowicz@uwaterloo.ca
Univ. of Waterloo        |URL http://orion.math.uwaterloo.ca/~hwolkowi
Dept of Comb and Opt     |Tel   (519) 888-4567, x5589
Waterloo, Ont. CANADA N2L 3G1          |Fax   (519) 725-5441




abstract:
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.

In the first part of this talk we look at the background and theory for SDP, as
well as several of the many applications.
In particular, we look at the Max-Cut problem.

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.

In the second part,
we take a different point of view. Rather than extend results from linear
programming,
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 include 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.