2021/10/29 by Pavel Dvurechensky, Dvurechensky, Pavel, Mathias Staudigl +1 · 2 citations
Computer Science · Mathematics · #65K05 #68Q25 #90C26 #90C30 #90C60 #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2111.00100
openalex publication_date 2021/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the minimization of a continuous function over the intersection of a regular cone with an affine set via a new class of adaptive first- and second-order optimization methods, building on the Hessian-barrier techniques introduced in [Bomze, Mertikopoulos, Schachinger, and Staudigl, Hessian barrier algorithms for linearly constrained optimization problems, SIAM Journal on Optimization, 2019]. Our approach is based on a potential-reduction mechanism and attains a suitably defined class of approximate first- or second-order KKT points with the optimal worst-case iteration complexity O(ε-2) (first-order) and O(ε-3/2) (second-order), respectively. A key feature of our methodology is the use of self-concordant barrier functions to construct strictly feasible iterates via a disciplined decomposition approach and without sacrificing on the iteration complexity of the method. To the best of our knowledge, this work is the first which achieves these worst-case complexity bounds under such weak conditions for general conic constrained optimization problems.