Barrier Functions and Interior-Point Algorithms for Linear Programming with Zero-, One-, or Two-Sided Bounds on the Variables
Published Online:1 May 1995https://doi.org/10.1287/moor.20.2.415
Abstract
This study examines two different barrier functions and their use in both path-following and potential-reduction interior-point algorithms for solving a linear program of the form: minimize cTx subject to Ax = b and l ≤ x ≤ u, where components of l and u can be nonfinite, so the variables xj, can have 0-, 1-, or 2-sided bounds, j = 1, …, n. The barrier functions that we study include an extension of the standard logarithmic barrier function and an extension of a barrier function introduced by Nesterov. In the case when both l and u have all of then components finite, these barrier functions are
$$\Psi(x)=\sum_j\left\{-\ln(u_j - x_j) -\ln (x_j - l_j)\right\}$$
and $$\Psi(x)=\sum_j\left\{-\ln\left(\min\{u_j - x_j, x_j - l_j\}\right)+\min \{u_j - x_j, x_j - l_j\} / ((u_j - l_j)/2)\right\}.$$
Each of these barrier functions gives rise to suitable primal and dual metrics that are used to develop both path-following and potential-reduction interior-point algorithms for solving such linear programming problems. The resulting complexity bounds on the algorithms depend only on the number of bounded variables, rather than on the number of finite inequalities in the system 1 ≤ x ≤ u, in contrast to the standard complexity bounds for interior-point algorithms. These enhanced complexity bounds stem directly from the choice of a “natural” metric induced by the barrier function. This study also demonstrates the inter-connection between the notion of self-concordance (introduced by Nesterov and Nemirovsky) and properties of the two barrier functions that drive the results contained herein.
