2016
Rescaled coordinate descent methods for linear programming
Publication
Publication
Presented at the
International Conference on Integer Programming and Combinatorial Optimization, Liège, Belgium
We propose two simple polynomial-time algorithms to find a
positive solution to
Ax
= 0. Both algorithms iterate between coordinate
descent steps similar to von Neumann’s algorithm, and rescaling steps. In
both cases, either the updating step leads to a substantial decrease in the
norm, or we can infer that the condition measure is small and rescale in
order to improve the geometry. We also show how the algorithms can be
extended to find a solution of maximum support for the system
Ax
=0,
x
≥
0.
This is an extended abstract. The missing proofs will be provided
in the full version
| Additional Metadata | |
|---|---|
| Springer | |
| Q. Louveaux , M. Skutella | |
| doi.org/10.1007/978-3-319-33461-5_3 | |
| Lecture Notes in Computational Science and Engineering | |
| International Conference on Integer Programming and Combinatorial Optimization | |
| Organisation | Networks and Optimization |
|
Dadush, D., Végh, L., & Zambelli, G. (2016). Rescaled coordinate descent methods for linear programming. In Q. Louveaux & M. Skutella (Eds.), Proceedings of International Conference on Integer Programming and Combinatorial Optimization 2016 (IPCO 18) (pp. 26–37). Springer. doi:10.1007/978-3-319-33461-5_3 |
|
