APPROXIMATIONS IN PROXIMAL BUNDLE METHODS AND DECOMPOSITION OF CONVEX-PROGRAMS

A proximal bundle method is presented for minimizing a nonsmooth conve x function f. At each iteration, it requires only one approximate eval uation of f and its epsilon-subgradient, and it finds a search directi on via quadratic programming. When applied to the Lagrangian decomposi tion of convex programs, it allows for inexact solutions of decomposed subproblems; yet, increasing their required accuracy automatically, i t asymptotically finds both the primal and dual solutions. It is an im plementable approximate version of the proximal point algorithm. Some encouraging numerical experience is reported.