Barrier functions for interior point methods for nonlinear programming and their relation to the characteristic function

Sascha Lanser

Part I Until a few years ago, interior point methods were developed only for Linear Programming. The main activity, both theoretical and computational, was focused on Linear Programming and on the closely related field of Linear Constrained Quadratic Programming. For many researchers it was a challenge to extend the approach to more general classes of problems. Part I introduces the notion of the self-concordant function and barrier and thoroughly examines their structure and their relationship to Newton's method. Further it provides a theoretical foundation for efficient interior point algorithms for nonlinear problems, expressed in conical form, when the cone and its associated barrier are self-scaled. To obtain these self-scaled cones and barriers we have to impose some additional conditions on the logarithmically homogeneous self-concordant barriers. While the self-scaled cones must satisfy certain restrictive conditions, it appears that the class includes a number of important instances, for example, the nonnegative orthant, the cone of symmetric positive semi-definite matrices and the second-order or Lorentz cone. The consequences of these conditions are quite extensive. For our purposes, the key results are the existence of a symmetric primal-dual scaling and the fact that good approximations of self-scaled barriers and their gradients extend far beyond unit balls defined by the local norm, and in fact are valid up to a constant fraction of the distance to the boundary in any direction. Using these ideas we are able to derive primal long-step potential-reduction and path-following algorithms as well as a symmetric long-step primal-dual potential-reduction method.

Part II In 1990 Nesterov and Nemirovski proved that any closed convex domain admits an O(n)-self-concordant barrier. This barrier is given by a general construction, namely the volume of the polar set of that domain, and, for that reason, called the universal barrier. The universal barrier is usually too complicated numerically, since straightforward computation of a multi-dimensional integral involved into the construction is, typically, an untractable task. We show that there exists a much simpler representation of the universal barrier in terms of the characteristic function. We use this representation to identify some known barriers as universal barriers and to calculate some new ones for specific cones. In this calculation the automorphism group of a cone plays an important role. For a homogeneous cone, i.e. a cone for which the automorphism group contains a transitive subgroup, the universal barrier can be calculated, using this transitive subgroup, at least up to an additive constant.

05-04-2000

  Info: