Optimization Online


Shrink-Wrapping trajectories for Linear Programming

Yuriy Zinchenko (yzinchen***at***ucalgary.ca)

Abstract: Hyperbolic Programming (HP) --minimizing a linear functional over an affine subspace of a finite-dimensional real vector space intersected with the so-called hyperbolicity cone-- is a class of convex optimization problems that contains well-known Linear Programming (LP). In particular, for any LP one can readily provide a sequence of HP relaxations. Based on these hyperbolic relaxations, a new Shrink-Wrapping approach to solve LP has been proposed by Renegar. The resulting Shrink-Wrapping trajectories, in a sense, generalize the notion of central path in interior-point methods. We study the geometry of Shrink-Wrapping trajectories for Linear Programming. In particular, we analyze the geometry of these trajectories in the proximity of the so-called central line, and contrast the behavior of these trajectories with that of the central path for some pathological LP instances. In addition, we provide an elementary proof of convexity of hyperbolicity cones over reals.

Keywords: Hyperbolic polynomials; hyperbolicity cones; hyperbolic programming; linear programming; Shrink-Wrapping

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: University of Calgary, May 2010

Download: [PDF]

Entry Submitted: 05/28/2010
Entry Accepted: 05/28/2010
Entry Last Modified: 05/30/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society