Primal-dual interior-point algorithms for linear programs with many inequality constraints

Simple item page
dc.contributor.advisorTits, Andre Len_US
dc.contributor.authorWinternitz, Lukeen_US
dc.contributor.departmentElectrical Engineeringen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2010-07-02T06:07:12Z
dc.date.available2010-07-02T06:07:12Z
dc.date.issued2010en_US
dc.description.abstractLinear programs (LPs) are one of the most basic and important classes of constrained optimization problems, involving the optimization of linear objective functions over sets defined by linear equality and inequality constraints. LPs have applications to a broad range of problems in engineering and operations research, and often arise as subproblems for algorithms that solve more complex optimization problems. ``Unbalanced'' inequality-constrained LPs with many more inequality constraints than variables are an important subclass of LPs. Under a basic non-degeneracy assumption, only a small number of the constraints can be active at the solution--it is only this active set that is critical to the problem description. On the other hand, the additional constraints make the problem harder to solve. While modern ``interior-point'' algorithms have become recognized as some of the best methods for solving large-scale LPs, they may not be recommended for unbalanced problems, because their per-iteration work does not scale well with the number of constraints. In this dissertation, we investigate "constraint-reduced'' interior-point algorithms designed to efficiently solve unbalanced LPs. At each iteration, these methods construct search directions based only on a small working set of constraints, while ignoring the rest. In this way, they significantly reduce their per-iteration work and, hopefully, their overall running time. In particular, we focus on constraint-reduction methods for the highly efficient primal-dual interior-point (PDIP) algorithms. We propose and analyze a convergent constraint-reduced variant of Mehrotra's predictor-corrector PDIP algorithm, the algorithm implemented in virtually every interior-point software package for linear (and convex-conic) programming. We prove global and local quadratic convergence of this algorithm under a very general class of constraint selection rules and under minimal assumptions. We also propose and analyze two regularized constraint-reduced PDIP algorithms (with similar convergence properties) designed to deal directly with a type of degeneracy that constraint-reduced interior-point algorithms are often subject to. Prior schemes for dealing with this degeneracy could end up negating the benefit of constraint-reduction. Finally, we investigate the performance of our algorithms by applying them to several test and application problems, and show that our algorithms often outperform alternative approaches.en_US
dc.identifier.urihttp://hdl.handle.net/1903/10400
dc.subject.pqcontrolledApplied Mathematicsen_US
dc.subject.pquncontrolledcolumn generationen_US
dc.subject.pquncontrolledconstraint-reductionen_US
dc.subject.pquncontrolledinterior-pointen_US
dc.subject.pquncontrolledlinear programmingen_US
dc.subject.pquncontrollednumerical methodsen_US
dc.subject.pquncontrolledoptimizationen_US
dc.titlePrimal-dual interior-point algorithms for linear programs with many inequality constraintsen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Winternitz_umd_0117E_11245.pdf
Size:
1.71 MB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Electrical & Computer Engineering Theses and Dissertations