Back to search

Cornell University

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

Abstract

dc:description.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 Kp associated to an arbitrary hyperbolic polynomial $p$, little is known about its dual cone {Kp}*. This problem is closely related to LP itself: for the case of p(x)=En(x)=\prodi=1 \ldots n xi the (closure of the) hyperbolicity cone is self-dual and is, in fact, \Ren+. Elementary symmetric polynomials can be thought of as derivative polynomials (in a certain sense) of En(x), and are building blocks for hyperbolic polynomials themselves, their associated hyperbolicity cones giving a natural sequence of relaxations for \Ren++. We give an algebraic characterization for the dual cone associated with p'(x)=En-1(x)=\sum1 \leq i \leq n \prodj \neq i xj 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).

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zinchenko, Yuriy A.

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
6476034

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zinchenko, Yuriy A.. THE LOCAL BEHAVIOR OF THE SHRINK-WRAPPING ALGORITHM FOR LINEAR PROGRAMMING. 2005. https://hdl.handle.net/1813/2197