A Simple Iterative Method for Linear and Semidefinite Programming
Henry Wolkowicz
Department of Combinatorics and Optimization
University of Waterloo
Waterloo, Ontario N2L 3G1
Abstract
Many hard numerical problems can be modelled
as the minimization (or maximization) of a quadratic function subject to
quadratic constraints, denoted QQP.
These models are nonconvex in general; so
finding a global solution is itself a hard problem.
We look at Lagrangian relaxations for these QQPs. These Lagrangian
relaxations are equivalent to semidefinite programming
relaxations, i.e. to the
minimization of a linear function of symmetric matrices subject to
linear and semidefinite constraints, denoted SDP.
These relaxations are
convex problems that can be solved efficiently using interior-point
methods. Moreover, the bounds they provide are surprisingly tight.
We discuss several applications:
the max-cut; quadratic assignment; graph partitioning; matrix completion
problems. In each case, the aim is to exploit the special structure of the
problem and solve large scale instances.
In particular, the simple approach uses a preprocessing step
that results in one single,
well-conditioned, overdetermined bilinear equation.
We apply an inexact Gauss-Newton method, within an
interior-point framework, to solve this nonlinear system
of optimality conditions. To solve the linear least squares problem that
arises at each iteration,
we use a preconditioned conjugate gradient
type method. As a preconditioner we use an incomplete $Q$-less QR
factorization.
As an illustration, we present numerical results for the SDP
relaxation of the Max-Cut problem.