  


ShrinkWrapping trajectories for Linear Programming
Yuriy Zinchenko (yzinchenucalgary.ca) Abstract: Hyperbolic Programming (HP) minimizing a linear functional over an affine subspace of a finitedimensional real vector space intersected with the socalled hyperbolicity cone is a class of convex optimization problems that contains wellknown Linear Programming (LP). In particular, for any LP one can readily provide a sequence of HP relaxations. Based on these hyperbolic relaxations, a new ShrinkWrapping approach to solve LP has been proposed by Renegar. The resulting ShrinkWrapping trajectories, in a sense, generalize the notion of central path in interiorpoint methods. We study the geometry of ShrinkWrapping trajectories for Linear Programming. In particular, we analyze the geometry of these trajectories in the proximity of the socalled 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; ShrinkWrapping Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: University of Calgary, May 2010 Download: [PDF] Entry Submitted: 05/28/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  