Dual–primal proximal point algorithms for extended convex programming

Abstract

This paper presents a class of dual–primal proximal point algorithms (PPAs) for extended convex programming with linear constraints. By choosing appropriate proximal regularization matrices, the application of the general PPA to the equivalent variational inequality of the extended convex programming with linear constraints can result in easy proximal subproblems. In theory, the sequence generated by the general PPA may fail to converge since the proximal regularization matrix is asymmetric sometimes. So we construct descent directions derived from the solution obtained by the general PPA. Different step lengths and descent directions are chosen with the negligible additional computational load. The global convergence of the new algorithms is proved easily based on the fact that the sequences generated are Fejér monotone. Furthermore, we provide a simple proof for the O(1/t) convergence rate of these algorithms.

Keywords:

• convergence rate
• dual–primal
• convex programming
• linear constraints
• proximal point algorithm

2010 AMS Subject Classifications::

• 65K10
• 90C25
• 90C30

Acknowledgements

This work was supported by the National Natural Science Foundation of China [grant number 11001053], Natural Science Foundation of Jiangsu Province, China [grant number BK2012662], Qing Lan Project and the Fundamental Research Funds for the Central Universities [grant number 2242014S20070].