Exact Primal-Dual Regularization of Linear Programs (06rit322)

Objectives

Linear programming is widely regarded as a vital tool of applied mathematics. Linear programs occur in their own right in such diverse application areas as resource allocation, scheduling, network problems, machine learning and tumor detection, and also as subproblems in the process of solving nonlinear optimization problems. Many practitioners and researchers rely heavily on software for solving large-scale linear programs. Such software must be robust---i.e., can dependably find solutions even for difficult or ill-posed problems---and it must be fast.

This proposal outlines a research project for improving the reliability and robustness of one of the workhorse class of algorithms for linear programming: that of primal-dual path-following algorithms. We have already started this project and have brought together the many pieces of the puzzle. We hope that with a concentrated period of work at BIRS, we will be able to finally put the final pieces into place and finish our paper.

Primal-dual (PD) methods (also known as "barrier" or "interior-point" methods) for solving linear programs are often an important alternative to the classical simplex method. Primal-dual methods avoid the combinatorial complexity inherent in the simplex method, and the underlying theory guarantees fast convergence to a strictly complementary solution. Relative to the simplex method, they are also straightforward to implement. Most linear programming software packages (e.g., CPLEX, Xpress-MP, OOPS, PCx) now offer a PD implementation as a standard option if not by default.

The computational kernel of a PD method for a linear program lies in the solution of a sequence of indefinite linear equations, arising from the linearization of the optimality conditions. The solutions of these linear systems are used to generate search directions. The linear systems are often solved "as is". Often, these systems can be very difficult to solve, or their solution does not yield good search directions. In that case, there exist various commonly used approaches [1,2,3] for perturbing these linear systems. These modifications are often ad-hoc and are justified only by the necessities of the numerical linear algebra.

There currently does not exist a convergence theory for PD methods that also shows us how to systematically modify the linear systems in numerically favorable ways. Interestingly, the assumptions on the problem data that are required for convergence of the PD method are closely tied to assumptions that are needed for these linear systems to have favorable numerical properties. The approach that we are formulating exploits this close relationship.

Our approach is based on a little-used fact: all linear programs admit small perturbations that either contract the solution set or leave it unchanged. We call such perturbations "exact regularizations" because they, like regularization for other problem classes, can be used to influence the properties of the problem; they are "exact" because it is still possible to recover a solution of the original problem from its perturbation.

An appropriate choice of the regularization has the fortunate side-effect of influencing the numerical properties of the indefinite linear systems described above. We have been able to establish a connection between this kind of regularization and the proximal-point and augmented Lagrangian methods that are commonly used in other contexts. With this theory, we can design a sequence of automatic regularizations that are exact, and that do not interfere with the favorable convergence properties of PD methods.

Any such improvements that can be made to PD algorithms can have an immediate effect to software based on these algorithms and improve their robustness.

We have been collaborating on this paper over email and have been making steady progress. However, an intensive session of working fact-to-face and away from distractions of the university is needed in order to finish and submit our paper.

Our goals for the present proposal are as follows.

1. To finalize the convergence theory of our approach,

2. To implement the algorithm and demonstrate its numerical behavior on a set of wisely selected degenerate linear programs,

3. To finish writing the paper,

4. To design a strategy for follow-up research.

References

[1] A. Altman and J. Gondzio. Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization. Optimization Methods and Software 11(12), pp. 275-302, 1999.

[2] M. A. Saunders and J. A. Tomlin. Solving regularized linear programs usingg barrier methods and KKT systems. SOL Report 96-4, Dept. of EESOR, Stanford Univeristy, 1996.

[3] A. Waechter and L. T. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming 106(1), pp. 25-57, 2006.