A sparse proximal implementation of the LP dual active set algorithm Academic Article

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. 2006 Springer-Verlag.

authors

• Davis, Timothy

published proceedings

• MATHEMATICAL PROGRAMMING

author list (cited authors)

• Davis, T. A., & Hager, W.

citation count

• 9

complete list of authors

• Davis, Timothy A||Hager, WilliamW

publication date

• April 2008

publisher

• Springer Nature  Publisher

published in

• Mathematical programming  Journal

keywords

• Barrier Method
• Dual Active Set Algorithm
• Equation Dropping
• Interior Point Method
• Linear Programming
• Simplex Method

Digital Object Identifier (DOI)

• 10.1007/s10107-006-0017-0

start page

• 275

end page

• 301

volume

• 112

issue

• 2

URL

• http://dx.doi.org/10.1007/s10107-006-0017-0