Approximation of linear programs by Bregman's DF projections

Abstract

The motivation of this paper is twofold: to contribute to the theory of Bregman's D-F projections and to point out its link to finding epsilon-optimal solutions to linear programming problems. A symmetric primal-dual pair of the D-F projection problem is presented, we call it Young programming problem, because the usual inequality that relates the primal and dual objective functions reduces to the well-known Young inequality. Some basic properties of Young programs are derived and an associated linear program is defined in a natural way. It will be shown that an epsilon-optimal solution of the associated linear program is obtained by solving an epsilon-parametric Young program and the optimal solutions of epsilon-parametric Young programs converge to an optimal solution of the associated linear program when epsilon approaches 0. It may also be interesting that the explicit formulation of the dual program enables us to give a dual interpretation of row-action methods, a powerful tool for solving D-F projection problems in general, and allows us to find new functions satisfying sufficient conditions for the convergence of row-action methods. (C) 2000 Elsevier Science B.V. All rights reserved.