Improving Complexity of Structured Convex Optimization Problems Using Self-concordant Barriers

Glineur, François
(2002) European Journal of Operational Research — Vol. 143, n° 2, p. 291-310 (2002)

Files

EJOR02.pdf
  • Restricted Access
  • Adobe PDF
  • 262.51 KB
Request a copy

Details

Authors
Abstract
The purpose of this paper is to provide improved complexity results for several classes of structured convex optimization problems using the theory of self-concordant functions developed by Nesterov and Nemirovski in SIAM Studies in Applied Mathematics, SIAM Publications, Philadelphia, 1994. We describe the classical short-step interior-point method and optimize its parameters in order to provide the best possible iteration bound. We also discuss the necessity of introducing two parameters in the definition of self-concordancy and which one is the best to fix. A lemma due to den Hertog et al. in Mathematical Programming Series B 69 (1) (1995) is improved, which allows us to review several classes of structured convex optimization problems and improve the corresponding complexity results.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Glineur, F. (2002). Improving Complexity of Structured Convex Optimization Problems Using Self-concordant Barriers. European Journal of Operational Research, 143(2), 291-310. https://doi.org/10.1016/S0377-2217(02)00297-7 (Original work published 2002)