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.