Linear programming with entropic perturbation
Tóm tắt
In this paper, we derive an unconstrained convex programming approach to solving standard form linear programs through an entropic perturbation. The whole duality theory is established by using only one simple inequality “lnz ≤ z −1 forz > 0”. A curved search algorithm is also proposed for obtaining a pair of primal and dualε-optimal solutions. The proposed algorithm is proven to be globally convergent with a quadratic rate of convergence. Computational results are included in support of theoretic findings.
Tài liệu tham khảo
Ben-Tal A, Melman A and Zowe J (1990) Curved Search Methods for Unconstrained Optimization. Optimization 21 (5): 669–695
Dantzig GB (1963) Linear Programming and Extensions. Princeton University Press, Princeton, NJ
Den Hertog D, Roos C and Terlaky T (1991) Inverse Barrier Methods for Linear Programming. Delft University of Technology, Report of the Faculty of Technical Mathematics and Informatics, No. 91-27
Dennis JE and Schnabel RB (1983) Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice Hall, Englewood, NJ
Erlander S (1981) Entropy in Linear Programs. Mathematical Programming 21:137–151
Erickson JR (1981) Algorithms for Entropy and Mathematical Programming. PhD Thesis, Linkoping University, Sweden
Erickson JR (1985) An Iterative Primal-Dual Algorithm for Linear Programming. Report LitH-MAT-R-1985-10, Department of Mathematics, Linkoping University, Sweden
Fang SC (1992) A New Unconstrained Convex Programming Approach to Linear Programming. North Carolina State University Operations Research Report No. 243 (Feb. 1990), Zeischrift fur Operations Research 36:149–161
Fang SC and Rajasekera JR (1989) Quadratically Constrained Minimum Cross-Entropy Analysis. Mathematical Programming 44:85–96
Fang SC and Tsao JHS (1991) A Quadratically Convergent Global Algorithm for the Linearly-Constrained Minimum Cross-Entropy Problem. North Carolina State University Operations Research Report 255 to appear in EJOR
Fiacco AV, McCormick GP (1968) Nonlinear Programming: Sequential Unconstrained Minimization Techniques. Wiley, New York
Goldfarb D, Todd MJ (1988) Linear Programming. Cornell University, School of OR and IE, Tech. Report 777
Guiasu S (1977) Information Theory with Applications. McGraw-Hill, New York
Gill PE, Murray W, Saunders M, Tomlin TA and Wright MH (1986) On Projected Newton Barriers for Linear Programming and An Equivalence to Karmarkar's Projective Method. Mathematical Programming 36:183–209
Karmarkar N (1984) A New Polynomial Time Algorithm for Linear Programming. Combinatorica 4:373–395
Minoux M (1986) Mathematical Programming Theory and Algorithms. John Wiley & Sons
Peterson EL (1976) Geometric Programming.SIAM Review 19:1–45
Rajasekera JR and Fang SC (1991) On the Convex Programming Approach to Linear Programming. North Carolina State University Operations Research Report 245 (April 1990), Operations Research Letters 10:309–312
Rockaffelar RT (1970) Convex Analysis. Princeton University Press, Princeton, New Jersey