JavaScript is disabled for your browser. Some features of this site may not work without it.

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

#####
**Author**

Zinchenko, Yuriy A.

#####
**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).

#####
**Description**

James Renegar, ORIE
Sidney Resnick, ORIE
Louis Billera, Mathematics

#####
**Date Issued**

2005-09-15#####
**Subject**

Mathematical programming; Linear programming; Hyperbolic polynomials; Elementary symmetric polynomials; Conic programming; Interior-point methods

#####
**Type**

dissertation or thesis