Convergence and error bound for perturbation of linear programs

Authors
Citation
P. Tseng, Convergence and error bound for perturbation of linear programs, COMPUT OP A, 13(1-3), 1999, pp. 221-230
Citations number
25
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Engineering Mathematics
Journal title
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
ISSN journal
0926-6003 → ACNP
Volume
13
Issue
1-3
Year of publication
1999
Pages
221 - 230
Database
ISI
SICI code
0926-6003(199904)13:1-3<221:CAEBFP>2.0.ZU;2-M
Abstract
In various penalty/smoothing approaches to solving a linear program, one re gularizes the problem by adding to the linear cost function a separable non linear function multiplied by a small positive parameter. Popular choices o f this nonlinear function include the quadratic function, the logarithm fun ction, and the x ln(x)-entropy function. Furthermore, the solutions generat ed by such approaches may satisfy the linear constraints only inexactly and thus are optimal solutions of the regularized problem with a perturbed rig ht-hand side. We give a general condition for such an optimal solution to c onverge to an optimal solution of the original problem as the perturbation parameter tends to zero. In the case where the nonlinear function is strict ly convex, we further derive a local (error) bound on the distance from suc h an optimal solution to the limiting optimal solution of the original prob lem, expressed in terms of the perturbation parameter.