Abstract:
We present a primal-dual interior/exterior-point method for linear (LP) and semidefinite programming (SDP). We begin with the usual perturbed primal-dual optimality equations. Under nondegeneracy assumptions, this nonlinear system is well-posed, i.e. it has a full rank Jacobian at optimality and is not necessarily ill-conditioned as the iterates approach optimality. We use a simple preprocessing step to eliminate both the primal and dual feasibility equations. This results in one single bilinear equation that maintains the well-posedness property. We then apply a preconditioned conjugate gradient method (PCG), within an inexact Newton framework, directly on the linearized equations. This is changed to a Gauss-Newton method for the SDP case. Sparsity is maintained. The work of an iteration consists almost entirely in the (approximate) solution of this well-posed linearized system, using a (matrix-free) iterative method.
This approach avoids the ill-conditioning that is introduced when forming the "Schur-complement/normal" equations for the search direction in current interior-point methods. In addition, the Gauss-Newton approach for SDP avoids the ill-conditioning that is introduced by symmetrization steps in current popular codes. Exact primal and dual feasibility are guaranteed throughout the iterations when starting feasible.
In addition, we can use affine scaling and not maintain positivity once we are close enough to the optimum, i.e., we apply a crossover technique that allows iterates to lose positivity. The well-posedness allows for warm starts for small perturbations of the data. Numerical test results for both LP and SDP are included.
(This is based on work with Xuan Vinh Doan, Maria Gonzales Lima, Hua Wei.)