Convergence of a Simple Subgradient Level Method

We study the subgradient projection method for convex optimization with Brannlund '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 = inf S f under the following assumptions. S is a nonempty closed convex set in IR n , f : IR n ! IR is a convex function, for each x 2 S we can compute f(x) and a subgradient g f (x) 2 @f(x) of f at x, and for each x 2 IR n we can find P S x = arg min y2S jx \Gamma yj, its orthogonal projection on S, where j \Delta j is the Euclidean norm. The optimal set Arg min S f may be empty. Given the kth iterate x k 2 S and a target level f k lev that estimates f , we may use H k = n x : f(x k ) + D g k ; x \Gamma x k E f k lev o with g k = g f (x k ) 2 @f(x k ) (1.1) to approximate t..