Relaxation methods for problems with strictly convex separable costs and linear constraints |
| |
Authors: | Paul Tseng Dimitri P Bertsekas |
| |
Institution: | (1) Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 02139 Cambridge, MA, USA |
| |
Abstract: | We consider the minimization problem with strictly convex, possibly nondifferentiable, separable cost and linear constraints.
The dual of this problem is an unconstrained minimization problem with differentiable cost which is well suited for solution
by parallel methods based on Gauss-Seidel relaxation. We show that these methods yield the optimal primal solution and, under
additional assumptions, an optimal dual solution. To do this it is necessary to extend the classical Gauss-Seidel convergence
results because the dual cost may not be strictly convex, and may have unbounded level sets.
Work supported by the National Science Foundation under grant NSF-ECS-3217668. |
| |
Keywords: | Gauss-Seidel relaxation Fenchel duality strict convexity strong convexity |
本文献已被 SpringerLink 等数据库收录! |
|