Set-Limited Functions and Polynomial-Time Interior-Point Methods
Open Access
- 13 February 2023
- journal article
- research article
- Published by Springer Nature in Journal of Optimization Theory and Applications
- Vol. 202 (1) , 11-26
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.Keywords
All Related Versions
Funding Information
- H2020 European Research Council (788368)
- Multidisciplinary Institute in Artificial Intelligence, Grenoble Alpes (ANR-19-P3IA-0003)
This publication has 17 references indexed in Scilit:
- An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and Its Implications to Second-Order MethodsSIAM Journal on Optimization, 2013
- Complexity bounds for second-order optimality in unconstrained optimizationJournal of Complexity, 2012
- Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical resultsMathematical Programming, 2009
- Accelerating the cubic regularization of Newton’s method on convex problemsMathematical Programming, 2007
- Cubic regularization of Newton method and its global performanceMathematical Programming, 2006
- Smooth minimization of non-smooth functionsMathematical Programming, 2004
- Path-Following Methods for Linear ProgrammingSIAM Review, 1992
- Conic formulation of a convex programming problem and dualityOptimization Methods and Software, 1992
- A polynomial-time algorithm, based on Newton's method, for linear programmingMathematical Programming, 1988
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984