Henry Wolkowicz
Department of Combinatorics and Optimization
University of Waterloo
Waterloo, Ontario N2L 3G1
This talk provides a simple approach for solving a linear program, LP. As is common with many other approaches, we apply a primal-dual method that uses the perturbed optimality equations for SDP, Fu(x,y,z)=0, where x,z are n vectors and y in Rm. What is different in this approach is a preprocessing step that results in one single, well-conditioned, overdetermined bilinear equation. We do not form a normal equation for the linearized system. In addition, asymptotic q-quadratic convergence is obtained with a crossover approach that switches to affine scaling without maintaining positivity of x and z. This results in a marked reduction in the number and the complexity of the iterations.
We use the long accepted method for nonlinear least squares problems, the Gauss-Newton method. For large sparse data, we use an inexact Gauss-Newton approach with a preconditioned conjugate gradient method applied directly on the linearized equations in matrix space. This does not require any operator formations into a Schur complement system. Exact primal and dual feasibility are guaranteed throughout the iterations. We include the derivation of the optimal diagonal preconditioner. The numerical tests show that the algorithm exploits sparsity and obtains q-quadratic convergence.