An approximate decomposition algorithm for convex minimization

作者：Lu, Yuan; Pang, Li-Ping^*; Liang, Xi-Jun; Xi, Zun-Quan

来源：Journal of Computational and Applied Mathematics, 2010, 234(3): 658-666.

DOI：10.1016/j.cam.2010.01.003

• Nonsmooth convex optimization
• VU-decomposition
• Approximate U-Lagrangian
• Proximal bundle method
• Smooth path

For nonsmooth convex optimization, Robert Mifflin and Claudia Sagastizkal introduce a VU-space decomposition algorithm in Mifflin and Sagastizabal (2005) [11]. An attractive property of this algorithm is that if a primal-dual track exists, this algorithm uses a bundle subroutine. With the inclusion of a simple line search, it is proved to be globally and superlinearly convergent. However, a drawback is that it needs the exact subgradients of the objective function, which is expensive to compute. In this paper an approximate decomposition algorithm based on proximal bundle-type method is introduced that is capable to deal with approximate subgradients. It is shown that the sequence of iterates generated by the resulting algorithm converges to the optimal solutions of the problem. Numerical tests emphasize the theoretical findings.

• 出版日期2010-6-1
• 单位大连理工大学; 沈阳大学