Article ID: | iaor1992291 |
Country: | United States |
Volume: | 16 |
Issue: | 3 |
Start Page Number: | 462 |
End Page Number: | 481 |
Publication Date: | Aug 1991 |
Journal: | Mathematics of Operations Research |
Authors: | Bertsekas Dimitri P., Tseng Paul |
Keywords: | programming: nonlinear |
Consider the problem of minimizing a strictly convex (possibly nondifferentiable and nonseparable) cost subject to linear constraints. The authors propose a dual coordinate ascent method for this problem that uses inexact line search and either essentially cyclic or Gauss-Southwell order of coordinate relaxation. They show, under very weak conditions, that this method generates a sequence of primal vectors converging to the optimal primal solution. Under an additional regularity assumption, and assuming that the effective domain of the cost function is polyhedral, the authors show that a related sequence of dual vectors converges in cost to the optimal cost. If the constraint set has an interior point in the effective domain of the cost function, then this sequence of dual vectors is bounded and each of its limit point(s) is an optimal dual solution. When the cost function is strongly convex, the authors show that the order of coordinate relaxation can become progressively more chaotic. These results significantly improve upon those obtained previously.