Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization

DOI10.1137/16M108104XzbMath1371.90108arXiv1512.07516OpenAlexW2951335402MaRDI QIDQ5275297

Adrien B. Taylor, François Glineur, Julien M. Hendrickx

Publication date: 11 July 2017

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.07516

zbMATH Keywords

convex optimizationsemidefinite programmingworst-case analysisfirst-order methodsperformance estimationconvex interpolationcomposite convex optimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30)

Related Items (27)

Optimal complexity and certification of Bregman first-order methods ⋮ A frequency-domain analysis of inexact gradient methods ⋮ Generalizing the Optimized Gradient Method for Smooth Convex Minimization ⋮ Exact worst-case convergence rates of the proximal gradient method for composite convex minimization ⋮ Potential Function-Based Framework for Minimizing Gradients in Convex and Min-Max Optimization ⋮ On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions ⋮ The exact worst-case convergence rate of the gradient method with fixed step lengths for \(L\)-smooth functions ⋮ An optimal gradient method for smooth strongly convex minimization ⋮ Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods ⋮ A Systematic Approach to Lyapunov Analyses of Continuous-Time Models in Convex Optimization ⋮ Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods ⋮ An elementary approach to tight worst case complexity analysis of gradient based methods ⋮ Principled analyses and design of first-order methods with inexact proximal operators ⋮ Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022 ⋮ Another Look at the Fast Iterative Shrinkage/Thresholding Algorithm (FISTA) ⋮ Worst-Case Convergence Analysis of Inexact Gradient and Newton Methods Through Semidefinite Programming Performance Estimation ⋮ Efficient first-order methods for convex minimization: a constructive approach ⋮ Operator Splitting Performance Estimation: Tight Contraction Factors and Optimal Parameter Selection ⋮ Tight Sublinear Convergence Rate of the Proximal Point Algorithm for Maximal Monotone Inclusion Problems ⋮ Accelerated proximal point method for maximally monotone operators ⋮ On the convergence analysis of the optimized gradient method ⋮ Analysis of biased stochastic gradient descent using sequential semidefinite programs ⋮ Fast gradient descent for convex minimization problems with an oracle producing a \(( \delta, L)\)-model of function at the requested point ⋮ Analysis of the gradient method with an Armijo–Wolfe line search on a class of non-smooth convex functions ⋮ Analysis of optimization algorithms via sum-of-squares ⋮ Optimal step length for the Newton method: case of self-concordant functions ⋮ Robust and structure exploiting optimisation algorithms: an integral quadratic constraint approach

Uses Software

• SeDuMi
• YALMIP
• Mosek
• SDPLR
• LMIRank
• UNLocBoX
• PESTO

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Optimized first-order methods for smooth convex minimization
• An optimal variant of Kelley's cutting-plane method
• Gradient methods for minimizing composite functions
• First-order methods of smooth convex optimization with inexact oracle
• Smooth strongly convex interpolation and exact worst-case performance of first-order methods
• The exact information-based complexity of smooth convex minimization
• A Newton-like method for solving rank constrained linear matrix inequalities
• Quadratic programming with one negative eigenvalue is NP-hard
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Introductory lectures on convex optimization. A basic course.
• On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions
• Performance of first-order methods for smooth convex minimization: a novel approach
• Proximal Splitting Methods in Signal Processing
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• Double Smoothing Technique for Large-Scale Linearly Constrained Convex Optimization
• Low-Rank Optimization on the Cone of Positive Semidefinite Matrices
• Smooth Optimization with Approximate Gradient
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• On the Convergence of the Proximal Point Algorithm for Convex Minimization
• Monotone Operators and the Proximal Point Algorithm
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Variational Analysis
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• What is the Subdifferential of the Closed Convex Hull of a Function?
• Semidefinite Programming
• Equivalent Subgradient Versions of Hamiltonian and Euler–Lagrange Equations in Variational Analysis
• Computationally Related Problems
• Proximité et dualité dans un espace hilbertien
• Convex analysis and monotone operator theory in Hilbert spaces

This page was built for publication: Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization