International Journal of Mathematics and Mathematical Sciences
Volume 19 (1996), Issue 1, Pages 177-184
doi:10.1155/S0161171296000257
Linear programming with inequality constraints via entropic perturbation
1Institute of Transportation Studies, University of California, Berkeley 94720, California, USA
2Graduate Program in Operations Research, North Carolina State University, Raleigh 27695-7913, North Carolina, USA
Received 11 January 1994; Revised 22 May 1995
Copyright © 1996 H.-S. Jacob Tsao and Shu-Cherng Fang. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
A dual convex programming approach to solving linear programs with inequality constraints through entropic perturbation is derived. The amount of perturbation required depends on the desired accuracy of the optimum. The dual program contains only non-positivity constraints. An ϵ-optimal solution to the linear program can be obtained effortlessly from the optimal solution of the dual program. Since cross-entropy minimization subject to linear inequality constraints is a special case of the perturbed linear program, the duality result becomes readily applicable. Many standard constrained optimization techniques can be specialized to solve the dual program. Such specializations, made possible by the simplicity of the constraints, significantly reduce the computational effort usually incurred by these methods. Immediate applications of the theory developed include an entropic path-following approach to solving linear semi-infinite programs with an infinite number of inequality constraints and the widely used entropy optimization models with linear inequality and/or equality constraints.