Abstract
Consider a linear programming problem in Karmarkar's standard form. By perturbing its linear objective function with an entropic barrier function and applying generalized geometric programming theory to it, Fang recently proposed an unconstrained convex programming approach to finding an epsilon-optimal solution. In this paper, we show that Fang's derivation of an unconstrained convex dual program can be greatly simplified by using only one simple geometric inequality. In addition, a system of nonlinear equations, which leads to a pair of primal and dual epsilon-optimal solutions, is proposed for further investigation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Karmarkar, N.,A New Polynomial Time Algorithm for Linear Programming, Combinatorica, Vol. 4, pp. 373–395, 1984.
Goldfarb, D., andTodd, M. J.,Linear Programming, Technical Report No. 777, School of Operations Research and Industrial Engineering, Cornell University, 1988.
Gill, P. E., Murray, W., Saunders, M., Tomlin, T. A., andWright, M. H.,On Projected Newton Barriers for Linear Programming and Equivalence to Karmarkar's Projective Method, Mathematical Programming, Vol. 36, pp. 183–209, 1986.
Lagarias, J. C., andBayer, D. A.,Karmarkar's Linear Programming Method and Newton's Method, Technical Report 11218-870810-22TM, AT&T Bell Laboratories, 1987.
Renegar, J.,A Polynomial-Time Algorithm Based on Newton's Method for Linear Programming, Mathematical Programming, Vol. 40, pp. 59–93, 1988.
Shannon, D. F., andBagchi, A.,A Unified View of Interior-Point Methods for Linear Programming,Rutcor Research Report No. 35–88, Rutgers University, 1988.
Sheu, R. L., andFang, S. C.,Insights into the Interior-Point Methods, Operations Research Report No. 252, North Carolina State University, 1990; ZOR, Vol. 36, pp. 227–257, 1992.
Erlander, S.,Entropy in Linear Programs, Mathematical Programming, Vol. 21, pp. 137–151, 1981.
Eriksson, J. R.,Algorithms for Entropy and Mathematical Programming, PhD Thesis, Linkoping University, Linkoping, Sweden, 1981.
Fang, S. C., andRajasekera, J. R.,Quadratically Constrained Minimum Cross-Entropy Analysis, Mathematical Programming, Vol. 44, pp. 85–96, 1989.
Fang, S. C.,A New Unconstrained Convex Programming Approach to Linear Programming, Operations Research Report No. 243, North Carolina State University, 1990; ZOR, Vol. 36, pp. 149–161, 1992.
Dennis, J.,Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, Englewood Cliffs, New Jersey, 1986.
Fiacco, A. V., andMcCormick, G. P.,Nonlinear Programming: Sequential Unconstrained Minimization Technique, John Wiley, New York, New York, 1968.
Eriksson, J. R.,An Iterative Primal-Dual Algorithm for Linear Programming, Report No. LITH-MAT-R-1985-10, Department of Mathematics, Linkoping University, Linkoping, Sweden, 1985.
Peterson, E. L.,Geometric Programming, SIAM Review, Vol. 19, pp. 1–45, 1976.
Duffin, R. J., Peterson, E. L., andZener, C.,Geometric Programming: Theory and Applications, John Wiley, New York, New York, 1967.
Wang, D.,Experiments on the Unconstrained Convex Programming Approach to Linear Programming, Technical Report No. 90–12, Industrial Engineering, North Carolina State University, 1990.
Fang, S. C., andTsao, J. H. S.,Solving Standard Form Linear Programs via Unconstrained Convex Programming Approach with a Quadratically Convergent Global Algorithm, Operations Research Report No. 259, North Carolina State University, 1991.
Rajasekera, J. R., andFang, S. C.,On the Convex Programming Approach to Linear Programming, Operations Research Letters, Vol. 10, pp. 309–312, 1991.
Author information
Authors and Affiliations
Additional information
Communicated by D. Q. Mayne
This work was partially supported by the North Carolina Supercomputing Center and a 1990 Cray Research Grant. The authors are indebted to Professors E. L. Peterson and R. Saigal for stimulating discussions.
Rights and permissions
About this article
Cite this article
Rajasekera, J.R., Fang, S.C. Deriving an unconstrained convex program for linear programming. J Optim Theory Appl 75, 603–612 (1992). https://doi.org/10.1007/BF00940495
Issue Date:
DOI: https://doi.org/10.1007/BF00940495