An optimal variant of Kelley's cutting-plane method

DOI10.1007/S10107-016-0985-7zbMATH Open1349.90880arXiv1409.2636OpenAlexW1931370844MaRDI QIDQ344947FDOQ344947

Authors: Yoel Drori, Marc Teboulle 

Publication date: 25 November 2016

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

Abstract: We propose a new variant of Kelley's cutting-plane method for minimizing a nonsmooth convex Lipschitz-continuous function over the Euclidean space. We derive the method through a constructive approach and prove that it attains the optimal rate of convergence for this class of problems.

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

Recommendations

• scientific article; zbMATH DE number 3904352
• scientific article; zbMATH DE number 4172771
• Minimizing Nonconvex Nonsmooth Functions via Cutting Planes and Proximity Control
• A sequential cutting plane algorithm for solving convex NLP problems
• scientific article; zbMATH DE number 3948004

zbMATH Keywords

rate of convergencecomplexitydualitynonsmooth convex optimizationbundle and subgradient methodsKelley's cutting-plane method

Mathematics Subject Classification ID

Quadratic programming (90C20) Convex programming (90C25) Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60) Discrete approximations in optimal control (49M25)

Cites Work

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

Cited In (19)

• Title not available (Why is that?)
• Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization
• Worst-Case Convergence Analysis of Inexact Gradient and Newton Methods Through Semidefinite Programming Performance Estimation
• Tight ergodic sublinear convergence rate of the relaxed proximal point algorithm for monotone variational inequalities
• Interpolation conditions for linear operators and applications to performance estimation problems
• Optimally cutting a surface into a disk
• Efficient first-order methods for convex minimization: a constructive approach
• Tight Sublinear Convergence Rate of the Proximal Point Algorithm for Maximal Monotone Inclusion Problems
• Optimal complexity and certification of Bregman first-order methods
• Title not available (Why is that?)
• Analysis of optimization algorithms via sum-of-squares
• Linear Programming on the Stiefel Manifold
• Generalizing the Optimized Gradient Method for Smooth Convex Minimization
• Another Look at the Fast Iterative Shrinkage/Thresholding Algorithm (FISTA)
• Assessment of surgical strategies for addressing keloids: an optimization problem
• The exact information-based complexity of smooth convex minimization
• On the convergence analysis of the optimized gradient method
• Principled analyses and design of first-order methods with inexact proximal operators
• Accelerated proximal point method for maximally monotone operators

Uses Software

• PNEW

This page was built for publication: An optimal variant of Kelley's cutting-plane method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q344947)