Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value

Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective valuez^*. These new methods combine the approach of Goldfarb and Mehrotra for relaxing the requirement that certain projections be computed exactly with the approach of Todd and Burrell for generating an improving sequence of lower bounds forz^* using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402, and ONR Contract N0014-87-K0214.