《1996 The Efficiency of Subgradient Projection Methods for Convex Optimization》.pdf

SIAM J. CONTROL AND OPTIMIZATION 1996 Society for Industrial and Applied Mathematics Vol. 34, No. 2, pp. 660-676, March 1996 014 THE EFFICIENCY OF SUBGRADIENT PROJECTION METHODS FOR CONVEX OPTIMIZATION, PART I: GENERAL LEVEL METHODS* KRZYSZTOF C. KIWIEL? Abstract. We study subgradient methods for convex optimization that use projections onto successive approximations of level sets of the objective corresponding to estimates of the optimal value. We present several variants and show that they enjoy almost optimal efficiency estimates. In another paper we discuss possible implementations of such methods. In particular, their projection subproblems may be solved inexactly via relaxation methods, thus opening the way for parallel implementations. They can also exploit accelerations of relaxation methods based on simultaneous projections, surrogate constraints, and conjugate and projected (conditional) subgradient techniques. Key words, nondifferentiable (nonsmooth) optimization, convex programming, relaxation methods, subgradient optimization, successive projections, linear inequalities, parallel computing AMS subject classifications. 65K05, 90C25 1. Introduction. This is the first of two papers in which we study various mod- ifications of Polyak’s [Po169] subgradient projection algorithm (SPA) and the recently proposed level method of [LNN95, LNN91] for solving the convex program (1.1) f* min{ f(x) x e S} under the following assumptions. S is a nonempty compact convex subset of ]RN; f is a convex function Lipschitz continuous on S with Lipschitz constant Lf; for each x e S we can compute f(x) and a subgradient gf(x) e Of(x) of f at x such that Igf(x)l _ Lf; and for each x e ]RN we can find Ps(x) argm