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

Nesterov, Yurii
(2022) , 15 pages

Files

CORE_DP_2022-15.pdf
  • Open Access
  • Adobe PDF
  • 836.39 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. (2022). Set-Limited Functions and Polynomial-Time Interior-Point Methods (LIDAM Discussion Paper CORE 2022/15). https://hdl.handle.net/2078.5/273286