Barrier subgradient method

• 成果类型: Article
• 署名作者: Nesterov, Yurii
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0421-3
• 发表日期: 2011
• 页码: 31-56
• 关键词: variational-inequalities; convex

摘要

In this paper we develop a new affine-invariant primal-dual subgradient method for nonsmooth convex optimization problems. This scheme is based on a self-concordant barrier for the basic feasible set. It is suitable for finding approximate solutions with certain relative accuracy. We discuss some applications of this technique including fractional covering problem, maximal concurrent flow problem, semidefinite relaxations and nonlinear online optimization. For all these problems, the rate of convergence of our method does not depend on the problem's data.