Solving a linear programming problem by perturbing its primal objective functiun with a barrier or penalty function for the development of interior-point methods has attracted much attention recently. However, the idea of perturbing the feasible region has not been fully explored. In this paper , we propose such an approach. Given a linear program with inequality constraints, aperturbed feasible region based on a measure of “constraint violation” in l p-norm is defined . Th e optimal so lution to the perturbed program is shown to converge to an optimal solution of the given linear program as the l p-norm tends to the l ∞, -norm. A simple formula which converts the optimal solution of a perturbed program to a dual feasible solution, which in turn converges to a dual optimal solution, of the given linear program is provided . In addition, an ε-optimality theory that specifies the perturbation parameter in terms of required accuracy level ε and other program parameters is studied.
Available at: http://works.bepress.com/jacob_tsao/30/