Subgradient ellipsoid method for nonsmooth convex problems

DOI10.1007/S10107-022-01833-4zbMATH Open1518.90070arXiv2106.13340OpenAlexW3174574580MaRDI QIDQ6038646FDOQ6038646

Authors: Anton Rodomanov, Yuri Nesterov 

Publication date: 2 May 2023

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

Abstract: In this paper, we present a new ellipsoid-type algorithm for solving nonsmooth problems with convex structure. Examples of such problems include nonsmooth convex minimization problems, convex-concave saddle-point problems and variational inequalities with monotone operator. Our algorithm can be seen as a combination of the standard Subgradient and Ellipsoid methods. However, in contrast to the latter one, the proposed method has a reasonable convergence rate even when the dimensionality of the problem is sufficiently large. For generating accuracy certificates in our algorithm, we propose an efficient technique, which ameliorates the previously known recipes.

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

Recommendations

• Subgradient method for nonconvex nonsmooth optimization
• scientific article; zbMATH DE number 3858859
• A subgradient method for unconstrained nonconvex nonsmooth optimization
• Using two successive subgradients in the ellipsoid method for nonlinear programming
• scientific article; zbMATH DE number 727769
• Subgradient and bundle methods for nonsmooth optimization
• scientific article; zbMATH DE number 4131965
• The subdifferential descent method in a nonsmooth variational problem
• Subgradient methods for saddle-point problems
• An improved ellipsoid method for solving convex differentiable optimization problems

zbMATH Keywords

convex optimizationnonsmooth optimizationvariational inequalitiessaddle-point problemssubgradient methodellipsoid methodaccuracy certificatesseparating oracle

Mathematics Subject Classification ID

Convex programming (90C25) Analysis of algorithms and problem complexity (68Q25) Minimax problems in mathematical programming (90C47)

Cites Work

• Adaptive subgradient methods for online learning and stochastic optimization
• Primal-dual subgradient methods for convex problems
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Robust Stochastic Approximation Approach to Stochastic Programming
• The ellipsoid method and its consequences in combinatorial optimization
• Title not available (Why is that?)
• Accuracy certificates for computational problems with convex structure
• An optimal method for stochastic composite optimization
• Stochastic intermediate gradient method for convex problems with stochastic inexact oracle
• Feature Article—The Ellipsoid Method: A Survey
• Title not available (Why is that?)
• Title not available (Why is that?)
• Location of the Maximum on Unimodal Surfaces
• Title not available (Why is that?)
• Brève communication. Résolution numérique d'inégalités variationnelles
• Lectures on convex optimization
• First-order and stochastic optimization methods for machine learning

Cited In (7)

• Best ellipsoidal relaxation to solve a nonconvex problem.
• An improved ellipsoid method for solving convex differentiable optimization problems
• Accuracy certificates for computational problems with convex structure
• On the convergence of broadcast incremental algorithms with applications
• Using two successive subgradients in the ellipsoid method for nonlinear programming
• Title not available (Why is that?)
• Accuracy certificates for convex minimization with inexact oracle

This page was built for publication: Subgradient ellipsoid method for nonsmooth convex problems

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