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.