BARRIER FUNCTIONS AND INTERIOR-POINT ALGORITHMS FOR LINEAR-PROGRAMMING WITH ZERO-SIDED, ONE-SIDED, OR 2-SIDED BOUNDS ON THE VARIABLES

This study examines two different barrier functions and their use in b oth path-following and potential-reduction interior-point algorithms f or solving a linear program of the form: minimize c(T)x subject to Ru = b and I less than or equal to x less than or equal to u, where compo nents of I and u can be nonfinite, so the variables x can have O-, 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 I and u have all of their components finite, these barrier functions are [GRAPHICS] and [GRAPHICS] Each of these barrier function s gives rise to suitable primal and dual metrics that are used to deve lop both path-following and potential-reduction interior-point algorit hms for solving such linear programming problems. The resulting comple xity bounds on the algorithms depend only on the number of bounded var iables, rather than on the number of finite inequalities in the system l less than or equal to g less than or equal to u, in contrast to the standard complexity bounds for interior-point algorithms. These enhan ced complexity bounds stem directly from the choice of a ''natural'' m etric induced by the barrier function. This study also demonstrates th e inter-connection between the notion of self-concordance (introduced by Nesterov and Nemirovsky) and properties of the two barrier function s that drive the results contained herein.