Paper Info
Title
A sparse proximal implementation of the LP dual active set algorithm
Abstract
We present an implementation of the LP Dual Active Set Algorithm (LP DASA) based on a quadratic proximal approximation, a strategy for dropping inactive equations from the constraints, and recently developed algorithms for updating a sparse Cholesky factorization after a low-rank change. Although our main focus is linear programming, the first and second-order proximal techniques that we develop are applicable to general concave–convex Lagrangians and to linear equality and inequality constraints. We use Netlib LP test problems to compare our proximal implementation of LP DASA to Simplex and Barrier algorithms as implemented in CPLEX.
Year
DOI
Venue
2008
10.1007/s10107-006-0017-0
Mathematical Programming
Keywords
Field
DocType
sparse proximal implementation,netlib lp test problem,lp dasa,active set algorithm,linear programming,linear equality,proximal implementation,dual active set algorithm · linear programming · simplex method · barrier method · interior point method · equation dropping,lp dual active set,lp dual,convex lagrangians,second-order proximal technique,quadratic proximal approximation,linear program,cholesky factorization,interior point method,simplex method,second order
Mathematical optimization,Simplex algorithm,Active set method,Netlib,Matrix decomposition,Algorithm,Linear programming,Interior point method,Sparse matrix,Mathematics,Cholesky decomposition
Journal
Volume
Issue
ISSN
112
2
1436-4646
Citations 
PageRank 
References 
6
0.98
23
Authors
2
Name
Order
Citations
PageRank
TIMOTHY A. DAVIS11447144.19
William W. Hager21603214.67