《1999 Convergence of a simple subgradient level method》.pdf

Math. Program. 85: 207–211 (1999) / DOI 10.1007/s10107980003a  Springer-Verlag 1999 Jean-Louis Goffin Krzysztof C. Kiwiel Convergence of a simple subgradient level method Received December 3, 1996 / Revised version received January 29, 1998 Published online October 21, 1998 Abstract. We study the subgradient projection method for convex optimization with Brännlund’s level control for estimating the optimal value. We establish global convergence in objective values without additional assumptions employed in the literature. Key words. nondifferentiable optimization – subgradient optimization 1. Introduction We consider a method for the minimization problem f infS f under the following assumptions. S is a nonempty closed convex set in IRn , f IRn IR is a convex function, for each x S we can compute f x and a subgradient gf x f x of f at x , and for each x IRn we can find P x arg min x −y , its orthogonal projection S y S on S, where is the Euclidean norm. The optimal set Arg minS f may be empty. Given the kth iterate x k S and a target level f k that estimates f , we may use lev Hk x f x k gk x − x k f k with gk gf x k f x k (1) lev to approximate the level set f k x f x f k H (2) f lev lev k The subgradient projection algorithm [13] generates the next iterate k1 k k k k k k k k 2 x P