Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities

• 成果类型: Article
• 署名作者: Auslender, Alfred; Teboulle, Marc
• 署名单位: Tel Aviv University; Centre National de la Recherche Scientifique (CNRS); Ecole Centrale de Lyon; Institut National des Sciences Appliquees de Lyon - INSA Lyon; Universite Claude Bernard Lyon 1; Universite Jean Monnet
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0147-z
• 发表日期: 2009
• 页码: 27-48
• 关键词: interior gradient; mirror descent; optimization

摘要

We study subgradient projection type methods for solving non-differentiable convex minimization problems and monotone variational inequalities. The methods can be viewed as a natural extension of subgradient projection type algorithms, and are based on using non-Euclidean projection-like maps, which generate interior trajectories. The resulting algorithms are easy to implement and rely on a single projection per iteration. We prove several convergence results and establish rate of convergence estimates under various and mild assumptions on the problem's data and the corresponding step-sizes.