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

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 withrelative accuracy . We prove that the upper complexity bound for both ln schemes is O( n 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 Rn . In both cases this computation can be performed very efficiently, in O(n2 m ln m) operations at most.

• metadata
• relations

Document type	Document de travail (Working Paper)
Access type	Accès libre
Publication date	2004
Collection	CORE Discussion Papers - 2004/4
Affiliation	UCL - CORE - Center for Operations Research and Econometrics
Keywords	Nonlinear optimization ; Convex optimization ; Complexity bounds ; Relative accuracy ; Fully polynomial approximation schemes ; Gradient methods ; Optimal methods
Links	http://www.core.ucl.ac.be/services/psfiles/dp04/dp2004_4.pdf http://hdl.handle.net/2078.1/4734[Handle]

See also
	[boreal:116941]	Rounding of convex sets and efficient gradient methods for linear programming problems