《1995 A descent proximal level bundle method for convex nondifferentiable optimization》.pdf

operations research letters E L S E V I E R Operations Research Letters 17 (1995) 121-126 A descent proximal level bundle method for convex nondifferentiable optimization* U l f Br~innlund a*, K r z y s z t o f C. K i w i e l h,l, E O . L i n d b e r g a2 a Royal Institute of Technology,S-IO0 44 Stockholm, Sweden b Systems Research Institute, PolishAcademy of Sciences, Newelska 6, 01-447 Warsaw,Poland Received 1 April 1994;revised 1 September 1994 Abstract We give a proximal level method for convex minimization that uses projections onto successive approximations of level sets of the objective. In contrast to the original level methods of Lemarechal, Nemirovskii and Nesterov, our method is globally convergent without any compactness assumptions and requires bounded storage. It does not employ potentially expensive linesearches as does the level method of Br~innlund. Keywords: Nondifferentiable (nonsmooth) optimization;Convexprogramming;Proximal bundle methods; level methods 1. Introduction We give a descent bundle method for minimizing a (possibly nondifferentiable) convex function f : I~N --~ over a nonempty closed convex set S C R to. We assume that at each x E S we can compute f ( x ) and an arbitrary subgradient g( x ) E af (x ) . At the kth iteration, having generated linearizations fJ (.) = f (yJ) + (g(yJ),.