Addressing Rank Degeneracy in Constraint-Reduced Interior-Point Methods for Linear Optimization

Luke B. Winternitz (), André L. Tits () and P.-A. Absil ()
Additional contact information
Luke B. Winternitz: University of Maryland
André L. Tits: University of Maryland
P.-A. Absil: Université catholique de Louvain

Journal of Optimization Theory and Applications, 2014, vol. 160, issue 1, No 7, 127-157

Abstract: Abstract In earlier works (Tits et al. SIAM J. Optim., 17(1):119–146, 2006; Winternitz et al. Comput. Optim. Appl., 51(3):1001–1036, 2012), 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 variables than constraints in primal form, 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.

Keywords: Linear programming; Linear optimization; Constraint reduction; Primal–dual interior point; Regularization (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-013-0323-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:160:y:2014:i:1:d:10.1007_s10957-013-0323-7

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-013-0323-7

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().