Central swaths

DOI10.1007/S10208-013-9148-XMaRDI QIDQ358633zbMATH OpenOpenAlexFDO

Authors James Renegar

Publication date 9 August 2013

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.5495

zbMATH Keywords

central pathconic programmingderivative conehyperbolic programminghyperbolicity cone

Mathematics Subject Classification ID

Symmetry properties of polytopes (52B15) Linear programming (90C05) Semidefinite programming (90C22) Interior-point methods (90C51)

Abstract: We develop a natural generalization to the notion of the central path -- a notion that lies at the heart of interior-point methods for convex optimization. The generalization is accomplished via the "derivative cones" of a "hyperbolicity cone," the derivatives being direct and mathematically-appealing relaxations of the underlying (hyperbolic) conic constraint, be it the non-negative orthant, the cone of positive semidefinite matrices, or other. We prove that a dynamics inherent to the derivative cones generates paths always leading to optimality, the central path arising from a special case in which the derivative cones are quadratic. Derivative cones of higher degree better fit the underlying conic constraint, raising the prospect that the paths they generate lead to optimality quicker than the central path.

Review text

The author considers a class of extended linear programming problems where the set of non-negativity constraints are replaced with the closure of the so-called hyperbolicity cone, which is defined as the connected component of the set where hyperbolic homogeneous polynomials are positive. It is well known that one of the most popular methods for linear programming are interior point ones based on the concept of the central path. The author suggests a more general concept called the central swath, which is based on proper extensions of positive cones with the help of derivative cones where the derivatives are taken for hyperbolic polynomials. After establishing some properties of these direction sets, the author shows that the corresponding dynamics creates trajectories converging to the optimal set.

Recommendations

• Central configurations
• Central regions and dependency
• Central trajectories
• scientific article; zbMATH DE number 2061008
• Central motions
• scientific article; zbMATH DE number 1098786
• Centralizing the centralizers
• On central configurations

Cites work

• scientific article; zbMATH DE number 3146819 (Why is no real title available?)
• scientific article; zbMATH DE number 46305 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 6843252 (Why is no real title available?)
• Hyperbolic polynomials and convex analysis
• Hyperbolic Polynomials and Interior Point Methods for Convex Programming
• Hyperbolic programs, and their derivative relaxations
• Linear matrix inequality representation of sets
• Multivariate Pólya-Schur classification problems in the Weyl algebra
• Obstructions to determinantal representability
• The Lax conjecture is true
• The primal-dual second-order cone approximations algorithm for symmetric cone programming
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all

Cited in

(4)

• Hyperbolicity cones of elementary symmetric polynomials are spectrahedral
• Dynamical system characterization of the central path and its variants -- a revisit
• Solutions to two problems on permanents
• Smooth hyperbolicity cones are spectrahedral shadows

This page was built for publication: Central swaths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q358633)