Paper ID sheet UCL-INMA-2012.03

Title

Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization

Authors

Luke B. Winternitz, André L. Tits, P.-A. Absil

Abstract

In earlier work (Tits et al., SIAM J. Optim., 17(1):119--146, 2006; Winternitz et al., COAP, doi=10.1007/s10589-010-9389-4, 2011), the present authors and their collaborators proposed primal-dual interior-point (PDIP) algorithms for linear optimization that, at each iteration, use only a subset of the (dual) inequality constraints in constructing the search direction. For problems with many more constraints than (dual) variables, this can yield a major speedup in the computation of search directions. However, in order for the Newton-like PDIP steps to be well defined, it is necessary that the gradients of the constraints included in the working set span the full dual space. In practice, in particular in the case of highly sparse problems, this often results in an undesirably large working set---or in an expensive trial-and-error process for its selection. In this paper we present two approaches that remove this non-degeneracy requirement, while retaining the convergence results obtained in the earlier work.

Key words

linear programming; linear optimization; constraint reduction; primal-dual interior-point; regularization

Status

Journal of Optimization Theory and Applications, January 2014, Volume 160, Issue 1, pp 127-157

Download

• Publisher's version: doi:10.1007/s10957-013-0323-7
• http://www.optimization-online.org/DB_HTML/2012/02/3368.html
• Preprint

BibTeX entry

    @ARTICLE{WinTitAbs2014,
    author = "Luke B. Winternitz and André L. Tits and P.-A. Absil",
    title = "Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization",
    fjournal = "Journal of Optimization Theory and Applications",
    journal = "J. Optim. Theory Appl.",
    year = 2014,
    volume = 160,
    issue = 1,
    pages = "127--157",
    doi = "10.1007/s10957-013-0323-7",
    }