An optimal variant of Kelley's cutting-plane method

DOI10.1007/s10107-016-0985-7zbMath1349.90880arXiv1409.2636OpenAlexW1931370844MaRDI QIDQ344947

Yoel Drori, Marc Teboulle

Publication date: 25 November 2016

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

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

zbMATH Keywords

complexityrate of convergencedualitynonsmooth convex optimizationbundle and subgradient methodsKelley's cutting-plane method

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) Quadratic programming (90C20) Discrete approximations in optimal control (49M25)

Related Items

Optimal complexity and certification of Bregman first-order methods, Generalizing the Optimized Gradient Method for Smooth Convex Minimization, Principled analyses and design of first-order methods with inexact proximal operators, Another Look at the Fast Iterative Shrinkage/Thresholding Algorithm (FISTA), Linear Programming on the Stiefel Manifold, 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, Tight Sublinear Convergence Rate of the Proximal Point Algorithm for Maximal Monotone Inclusion Problems, Accelerated proximal point method for maximally monotone operators, The exact information-based complexity of smooth convex minimization, On the convergence analysis of the optimized gradient method, Analysis of optimization algorithms via sum-of-squares, Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization

Uses Software

• PNEW

Cites Work

• Unnamed Item
• Unnamed Item
• Optimized first-order methods for smooth convex minimization
• Positive definite completions of partial Hermitian matrices
• Proximity control in bundle methods for convex nondifferentiable minimization
• Partitioning procedures for solving mixed-variables programming problems
• Newton's method for convex programming and Tschebyscheff approximation
• A bundle-Newton method for nonsmooth unconstrained minimization
• Variable metric bundle methods: From conceptual to implementable forms
• Introductory lectures on convex optimization. A basic course.
• Efficiency of proximal bundle methods
• Non-Euclidean restricted memory level method for large-scale convex optimization
• Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities
• New variants of bundle methods
• Performance of first-order methods for smooth convex minimization: a novel approach
• Lectures on Modern Convex Optimization
• The Cutting-Plane Method for Solving Convex Programs
• A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
• Numerical methods for nondifferentiable convex optimization
• Survey of Bundle Methods for Nonsmooth Optimization
• Interior Gradient and Epsilon-Subgradient Descent Methods for Constrained Convex Minimization
• Minimax Theorems