Abstract:

Recently, Fang proposed approximating a linear program in the Karmarkar standard form by adding an entropic barrier function to the objective function and derived an unconstrained dual concave program. We present in this note a necessary and sufficient condition for the existence of a dual optimal solution to the perturbed problem. In addition, a sharp upper bound of error estimation in this approximation scheme is provided.