Barrier subgradient method
type: Item
instance of: scholarly article
title: Barrier subgradient method
zbMATH Open document ID: 1233.90235
published in: Mathematical Programming. Series A. Series B
publication date: 2011-03-31T00:00:00Z
full work available at URL: http://hdl.handle.net/2078.1/19673
review text: The author focusses on a class of problems of minimizing a nonsmooth convex function over a feasible set endowed by a self-concordant barrier. After studying the smoothing of the support function of a convex set by a self-concordant barrier, the author describes the corresponding barrier subgradient method (BSM). If \(\varepsilon\) is the required absolute accuracy, then the complexity bound of the BSM is \(O(\frac{1}{\varepsilon^2})\). The method is applied to maximize a non-negative concave function. If \(\delta\) is the required accuracy in this case, then the result is an approximate solution in the relative scale with the complexity bound \(O(\frac{1}{\delta^2})\). Several applications of BSM are presented: fractional covering problems, maximal concurrent flow problems, minimax problems with nonnegative components and semidefinite relaxation of Boolean quadratic problems. BSM is also applied to online optimization, as an alternative to the single-stage stochastic optimization. The practical domains of decision-making in uncertain environments, portfolio management and processes with full production cycles are taken into account. For all these problems, the rate of convergence of the method described in this paper is independent on the problem's data.
reviewed by: Gabriela Cristescu
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C06
Mathematics Subject Classification ID: 90C51
zbMATH DE Number: 5872556
zbMATH Keywords: convex optimization
zbMATH Keywords: subgradient methods
zbMATH Keywords: non-smooth optimization
zbMATH Keywords: minimax problems
zbMATH Keywords: saddle points
zbMATH Keywords: variational inequalities
zbMATH Keywords: stochastic optimization
zbMATH Keywords: black-box methods
zbMATH Keywords: lower complexity bounds
author: Yuri Nesterov
MaRDI profile type: Publication
OpenAlex ID: W2157959686
cites work: First-Order Methods for Sparse Covariance Selection
cites work: Potential function methods for approximately solving linear programming problems: theory and practice.
cites work: Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
cites work: Approximate minimum-cost multicommodity flows in \(\widetilde O(\varepsilon^{-2}KNM)\) time
cites work: Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
cites work: Semidefinite relaxation and nonconvex quadratic optimization
cites work: Introductory lectures on convex optimization. A basic course.
cites work: Smooth minimization of non-smooth functions
cites work: Excessive Gap Technique in Nonsmooth Convex Minimization
cites work: Dual extrapolation and its applications to solving variational inequalities and related problems
cites work: Smoothing technique and its applications in semidefinite optimization
cites work: Primal-dual subgradient methods for convex problems
cites work: Rounding of convex sets and efficient gradient methods for linear programming problems
cites work: Q4324980
cites work: Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems
cites work: Fast Approximation Algorithms for Fractional Packing and Covering Problems
cites work: The maximum concurrent flow problem
DOI: 10.1007/S10107-010-0421-3
description: scientific article; zbMATH DE number 5872556