Primal-dual proximal point algorithm for linearly constrained convex programming problems |
| |
Authors: | Satoru Ibaraki Masao Fukushima Toshihide Ibaraki |
| |
Institution: | (1) Department of Applied Mathematical and Physics, Faculty of Engineering, Kyoto University, 606 Kyoto, Japan |
| |
Abstract: | A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs. |
| |
Keywords: | proximal point algorithm primal-dual method convex programming Lagrangian |
本文献已被 SpringerLink 等数据库收录! |