Error Bounds for Strongly Convex Programs and (Super)Linearly Convergent Iterative Schemes for the Least 2-Norm Solution of Linear Programs

摘要

We derive bounds on the distance between an arbitrary point and the unique solution of a strongly convex constrained optimization problem in terms of known violations of the optimality conditions of the problem. These bounds are then used to construct effective schemes for finding the unique smallest solution of very large sparse linear programs. Given an arbitrary point (x,u) in R superscript n x R sub + superscript m, we give bounds on the Euclidean distance between x and the unique solution x-bar to a strongly convex program in terms of the violations of the Karush Kuhn Tucker conditions by the arbitrary point (x, u). These bounds are then used to derive linearly and superlinearly convergent iterative schemes for obtaining the unique least 2-norm solution of a linear program. These schemes can be used effectively in conjunction with the successive overrelaxation methods for solving very large sparse linear programs. Keywords: Convex programs; Linear programs; Error bounds; Iterative methods.