Skip to main content
Entropic Perturbation Method for Solving Systems of Linear Inequalities
Journal of Computational and Applied Mathematics (2002)
  • Shyh-Huei Chen
  • Shu-Cherng Fang, North Carolina State University at Raleigh
  • Jacob Tsao, San Jose State University

The problem of finding an View the MathML source such that Ax⩽b and x⩾0 arises in numerous contexts. We propose a new optimization method for solving this feasibility problem. After converting Ax⩽b into a system of equations by introducing a slack variable for each of the linear inequalities, the method imposes an entropy function over both the original and the slack variables as the objective function. The resulting entropy optimization problem is convex and has an unconstrained convex dual. If the system is consistent and has an interior solution, then a closed-form formula converts the dual optimal solution to the primal optimal solution, which is a feasible solution for the original system of linear inequalities. An algorithm based on the Newton method is proposed for solving the unconstrained dual problem. The proposed algorithm enjoys the global convergence property with a quadratic rate of local convergence. However, if the system is inconsistent, the unconstrained dual is shown to be unbounded. Moreover, the same algorithm can detect possible inconsistency of the system. Our numerical examples reveal the insensitivity of the number of iterations to both the size of the problem and the distance between the initial solution and the feasible region. The performance of the proposed algorithm is compared to that of the surrogate constraint algorithm recently developed by Yang and Murty. Our comparison indicates that the proposed method is particularly suitable when the number of constraints is larger than that of the variables and the initial solution is not close to the feasible region.

Publication Date
Publisher Statement
SJSU users: use the following link to login and access the article via SJSU databases
Citation Information
Shyh-Huei Chen, Shu-Cherng Fang and Jacob Tsao. "Entropic Perturbation Method for Solving Systems of Linear Inequalities" Journal of Computational and Applied Mathematics Vol. 145 (2002)
Available at: