Set-Limited Functions and Polynomial-Time Interior-Point Methods

Nesterov, Yurii
(2023) Journal of Optimization Theory and Applications — (2023)

Files

CORE_RP_3250.pdf
  • Open Access
  • Adobe PDF
  • 604.98 KB
Download

Details

Authors
  • Nesterov, YuriiUCLouvain
    Author
Abstract
In this paper, we revisit some elements of the theory of self-concordant functions. We replace the notion of self-concordant barrier by a new notion of set-limited function, which forms a wider class. We show that the proper set-limited functions ensure polynomial time complexity of the corresponding path-following method (PFM). Our new PFM follows a deviated path, which connects an arbitrary feasible point with the solution of the problem. We present some applications of our approach to the problems of unconstrained optimization, for which it ensures a global linear rate of convergence even in for nonsmooth objective function.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Nesterov, Y. (2023). Set-Limited Functions and Polynomial-Time Interior-Point Methods. Journal of Optimization Theory and Applications. Accepted/in-press. https://doi.org/10.1007/s10957-023-02163-x (Original work published 2023)