Relaxation methods for problems with strictly convex costs and linear constraints

Relaxation methods for problems with strictly convex costs and linear constraints

0.00 Avg rating0 Votes
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: ,
Keywords: programming: nonlinear
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.