Efficient first-order methods for convex minimization: a constructive approach

DOI10.1007/S10107-019-01410-2zbMath1451.90118arXiv1803.05676OpenAlexW3104372163WikidataQ127675233 ScholiaQ127675233MaRDI QIDQ2205976

Yoel Drori, Adrien B. Taylor

Publication date: 21 October 2020

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

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)

Related Items (16)

Optimal complexity and certification of Bregman first-order methods ⋮ A frequency-domain analysis of inexact gradient methods ⋮ Primal–dual accelerated gradient methods with small-dimensional relaxation oracle ⋮ An engineering interpretation of Nesterov's convex minimization algorithm and time integration: application to optimal fiber orientation ⋮ An optimal gradient method for smooth strongly convex minimization ⋮ Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods ⋮ Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization 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 ⋮ Worst-Case Convergence Analysis of Inexact Gradient and Newton Methods Through Semidefinite Programming Performance Estimation ⋮ Accelerated proximal point method for maximally monotone operators ⋮ Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions ⋮ Provably faster gradient descent via long steps ⋮ Interpolation conditions for linear operators and applications to performance estimation problems ⋮ Analysis of optimization algorithms via sum-of-squares ⋮ Robust and structure exploiting optimisation algorithms: an integral quadratic constraint approach

Uses Software

• CVX
• YALMIP
• Mosek
• PESTO
• Saga

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• A new semidefinite programming relaxation scheme for a class of quadratic matrix problems
• Smooth strongly convex interpolation and exact worst-case performance of first-order methods
• The exact information-based complexity of smooth convex minimization
• On the convergence analysis of the optimized gradient method
• Information-based complexity of linear operator equations
• Variable metric bundle methods: From conceptual to implementable forms
• Introductory lectures on convex optimization. A basic course.
• Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
• 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
• Coordinate descent algorithms
• Quasi-monotone subgradient methods for nonsmooth convex minimization
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
• Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
• Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
• Efficient Numerical Methods for Nonlinear MPC and Moving Horizon Estimation
• Numerical Optimization
• An Optimal First Order Method Based on Optimal Quadratic Averaging
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Analysis of Optimization Algorithms via Integral Quadratic Constraints: Nonstrongly Convex Problems
• Operator Splitting Performance Estimation: Tight Contraction Factors and Optimal Parameter Selection
• Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization
• Quadratic Matrix Programming
• Some methods of speeding up the convergence of iteration methods
• Methods of conjugate gradients for solving linear systems

This page was built for publication: Efficient first-order methods for convex minimization: a constructive approach