Mirror descent and convex optimization problems with non-smooth inequality constraints

DOI10.1007/978-3-319-97478-1_8zbMATH Open1421.90112arXiv1710.06612OpenAlexW2767083550MaRDI QIDQ2415205FDOQ2415205

Authors: Anastasia Bayandina, Pavel Dvurechensky, Alexander V. Gasnikov, F. S. Stonyakin, Alexander A. Titov 

Publication date: 21 May 2019

Abstract: We consider the problem of minimization of a convex function on a simple set with convex non-smooth inequality constraint and describe first-order methods to solve such problems in different situations: smooth or non-smooth objective function; convex or strongly convex objective and constraint; deterministic or randomized information about the objective and constraint. We hope that it is convenient for a reader to have all the methods for different settings in one place. Described methods are based on Mirror Descent algorithm and switching subgradient scheme. One of our focus is to propose, for the listed different settings, a Mirror Descent with adaptive stepsizes and adaptive stopping rule. This means that neither stepsize nor stopping rule require to know the Lipschitz constant of the objective or constraint. We also construct Mirror Descent for problems with objective function, which is not Lipschitz continuous, e.g. is a quadratic function. Besides that, we address the problem of recovering the solution of the dual problem.

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

Recommendations

• Mirror-Descent Methods in Mixed-Integer Convex Optimization
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• A weighted mirror descent algorithm for nonsmooth convex optimization problem
• On the convergence of mirror descent beyond stochastic convex programming
• A version of the mirror descent method to solve variational inequalities
• Adaptive mirror descent algorithms for convex and strongly convex optimization problems with functional constraints
• Algorithms of inertial mirror descent in convex problems of stochastic optimization
• Algorithms of inertial mirror descent in stochastic convex optimization problems
• scientific article; zbMATH DE number 3972657
• Mirror descent and constrained online optimization problems

zbMATH Keywords

primal-dual methodsrestartsadaptive stepsizeadaptive stopping ruleconstrained non-smooth convex optimizationstochastic adaptive mirror descent

Mathematics Subject Classification ID

Convex programming (90C25) Complexity and performance of numerical algorithms (65Y20) Large-scale problems in mathematical programming (90C06) Nonlinear programming (90C30)

Cited In (25)

• Stochastic incremental mirror descent algorithms with Nesterov smoothing
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• First-order methods for convex optimization
• Adaptive algorithms for relatively Lipschitz continuous convex optimization problems
• Adaptive subgradient methods for mathematical programming problems with quasiconvex functions
• Mirror descent and constrained online optimization problems
• An accelerated directional derivative method for smooth stochastic convex optimization
• The CoMirror algorithm for solving nonsmooth constrained convex problems
• On modification of an adaptive stochastic mirror descent algorithm for convex optimization problems with functional constraints
• Mirror descent algorithms for minimizing interacting free energy
• Algorithms of inertial mirror descent in stochastic convex optimization problems
• A weighted mirror descent algorithm for nonsmooth convex optimization problem
• Analogues of switching subgradient schemes for relatively Lipschitz-continuous convex programming problems
• Generalized mirror prox algorithm for monotone variational inequalities: Universality and inexact oracle
• Stochastic saddle-point optimization for the Wasserstein barycenter problem
• Recent theoretical advances in decentralized distributed convex optimization
• Mirror-Descent Methods in Mixed-Integer Convex Optimization
• An inexact gradient mirror descent algorithm for non-smooth convex optimization
• Some analogue of quadratic interpolation for a special class of non-smooth functionals and one application to adaptive mirror descent
• On some methods for strongly convex optimization problems with one functional constraint
• Adaptive mirror descent algorithms for convex and strongly convex optimization problems with functional constraints
• Composite optimization for the resource allocation problem
• Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization
• Alternating minimization methods for strongly convex optimization
• Mirror Prox algorithm for multi-term composite minimization and semi-separable problems

This page was built for publication: Mirror descent and convex optimization problems with non-smooth inequality constraints

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