Krzysztof C. Kiwiel
Systems Research Institute
Polish Academy of Sciences
Warsaw, Poland
E-mail: kiwiel@ibspan.waw.pl
The subgradient projection method for convex nondifferentiable optimization is used in many applications, mainly due to its simplicity, although it lacks stopping criteria and popular heuristic stepsize rules do not ensure convergence. We give the following remedies. We study subgradient methods that use projections onto successive approximations of the level sets of the objective corresponding to estimates of the optimal value. We establish, for the first time, convergence and efficiency estimates for simple ballstep level controls without requiring that the feasible set be compact. Further, we introduce stopping criteria based on optimality estimates. Our framework may handle accelerations based on ``cheap'' projections, surrogate constraints and conjugate subgradient techniques. This is joint work with T. Larsson and P.O. Lindberg (LiTH).