Michael Saunders
Experiments with iterative computation of search directions within interior methods for constrained optimization

Dept of Management Science & Engineering
Huang Engineering Center
475 Via Ortega
Stanford University
Stanford
CA 94305-4121
saunders@stanford.edu
Santiago Akle

Our primal-dual interior-point optimizer PDCO has found many applications for optimization problems of the form

$$\min\, \varphi(x)$$    st  $$Ax=b, \quad l \le x \le u,$$

in which $\varphi(x)$ is convex and $A$ is a sparse matrix or a linear operator. We focus on the latter case and the need for iterative methods to compute dual search directions from linear systems of the form

$$A D^2 \!A^T \Delta y = r,$$   $D$ diagonal and positive definite$$.$$

Although the systems are positive definite, they do not need to be solved accurately and there is reason to use MINRES rather than CG (see PhD thesis of David Fong (2011)). When the original problem is regularized, the systems can be converted to least-squares problems and there is similar reason to use LSMR rather than LSQR. Also, $D$ becomes increasingly ill-conditioned as the interior method proceeds and there is need for some kind of preconditioning, such as the partial Cholesky approach of Bellavia, Gondzio and Morini (2011).

We present numerical results on matters such as these.