Barrier subgradient method (Q633113)

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.