Linear programming with entropic perturbation

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.The work is partially supported by the North Carolina Supercomputing Center, the Cray Research Award, and the National Science Council of the Republic of China # NSC 81-0415-E-007-10.