Abstract: Over the past decades, Linear Programming(LP) has been widely used in different areas and considered as one of the mature technologies in numerical optimization. However, the complexity offered by state-of-the-art algorithms (i.e. interior-point method and primal, dual simplex methods) is still unsatisfactory for problems in machine learning with huge number of variables and constraints. In this paper, we investigate a general LP algorithm based on the combination of Augmented Lagrangian and Coordinate Descent (AL-CD), giving an iteration complexity of O((log(1/eps))^2) with O(nnz(A)) cost per iteration, where nnz(A) is the number of non-zeros in the m×n constraint matrix A, and in practice, one can further reduce cost per iteration to the order of non-zeros in columns (rows) corresponding to the active primal (dual) variables through an active-set strategy. The algorithm thus yields a tractable alternative to standard LP methods for large-scale problems of sparse solutions and nnz(A)
- Sparse Linear Programming via Primal and Dual Augmented Coordinate Descent (pdf, code)
I. Yen, K. Zhong, C. Hsieh, P. Ravikumar, I. Dhillon.
In Neural Information Processing Systems (NIPS), December 2015.