Shrink-Wrapping trajectories for Linear Programming

Details Shrink-Wrapping trajectories for Linear Programming Shrink-Wrapping trajectories for Linear Programming

2010-05-30

arxiv.org/abs/1005.5522v1

Mathematics

Optimization and Control

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Shrink-Wrapping trajectories for Linear Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Shrink-Wrapping trajectories for Linear Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shrink-Wrapping trajectories for Linear Programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-161921