Deriving an unconstrained convex program for linear programming |
| |
Authors: | J R Rajasekera S C Fang |
| |
Institution: | (1) AT&T Bell Laboratories, Princeton, New Jersey;(2) Graduate Program in Operations Research and Department of Industrial Engineering, North Carolina State University, Raleigh, North Carolina |
| |
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.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. |
| |
Keywords: | Linear programming convex programming geometric programming duality theory |
本文献已被 SpringerLink 等数据库收录! |
|