Rounding of convex sets and efficient gradient methods for linear programming problems

Nesterov, Yurii
(2008) Optimization Methods and Software — Vol. 23, n° 1, p. 109-128 (2008)

Files

rounding.pdf
  • Restricted Access
  • Adobe PDF
  • 182.9 KB
Request a copy

Details

Authors
  • Nesterov, YuriiUCLouvain
    Author
Abstract
(en) In this paper, we propose new efficient gradient schemes for two non-trivial classes of linear programming problems. These schemes are designed to compute approximate solutions with relative accuracy δ. We prove that the upper complexity bound for both schemes is O((√(n ln m)/δ)ln n) iterations of a gradient-type method, where n and m (n<m) are the sizes of the corresponding linear programming problems. The proposed schemes are based on preliminary computation of an ellipsoidal rounding for some polytopes in R n . In both cases, this computation can be performed very efficiently, in O(n 2 m ln m) operations at most.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Nesterov, Y. (2008). Rounding of convex sets and efficient gradient methods for linear programming problems. Optimization Methods and Software, 23(1), 109-128. https://doi.org/10.1080/10556780701550059 (Original work published 2008)