THE LOCAL BEHAVIOR OF THE SHRINK-WRAPPING ALGORITHM FOR LINEAR PROGRAMMING

Abstract

Hyperbolic polynomials and their associated hyperbolicity cones have origins in partial differential equations. Recently, these structures have drawn considerable attention in the optimization community as well. It turns out that most of interior point methods (IPM) theory applies naturally to the class of conic programming problems arising from hyperbolicity cones. In particular, linear programming (LP), second-order conic programming (SOCP) and positive semi-definite programming (SDP) are themselves instances of conic programming problems of this kind.

The thesis consists of two parts. The first part is devoted to the structure of a particular family of hyperbolicity cones which give a sequence of relaxations to the nonnegative orthant. The second part contains analysis of the newly proposed algorithm for LP based on these relaxations.

While one can easily construct a logarithmic self-concordant barrier (SCB) functional for the hyperbolicity cone $K_p$ associated to an arbitrary hyperbolic polynomial $p$, little is known about its dual cone ${K_p}_*$. This problem is closely related to LP itself: for the case of $p(x)=E_n(x)=\prod_{i=1 \ldots n} x_i$ the (closure of the) hyperbolicity cone is self-dual and is, in fact, $\Re^n_+$. Elementary symmetric polynomials can be thought of as derivative polynomials (in a certain sense) of $E_n(x)$, and are building blocks for hyperbolic polynomials themselves, their associated hyperbolicity cones giving a natural sequence of relaxations for $\Re^n_{++}$. We give an algebraic characterization for the dual cone associated with $p'(x)=E_{n-1}(x)=\sum_{1 \leq i \leq n} \prod_{j \neq i} x_j$ which was previously unknown and show how one can easily construct a SCB functional for this cone. We comment on possible extensions of this result.

Recently a new paradigm for LP has been proposed (J. Renegar). It relies on the consecutive relaxations of the nonnegative orthant using hyperbolicity cones associated with elementary symmetric functions. In a way this gives a generalization to the notion of a central path in IPM. We analyze the local behavior of the newly proposed algorithm in the neighborhood of the optimal LP solution demonstrating that the resulting sequence of iterates will converge at least super-linearly to the solution (under some non-degeneracy assumptions).