Automorphisms of rank-one generated hyperbolicity cones and their derivative relaxations

A hyperbolicity cone is said to be rank-one generated (ROG) if all its extreme rays have rank one, where the rank is computed with respect the underlying hyperbolic polynomial. This is a natural class of hyperbolicity cones which are strictly more general than the ROG spectrahedral cones. In this work, we present a study of … Read more

The central curve in linear programming

The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. We determine the degree, arithmetic genus and defining prime ideal … Read more

Central Swaths (A Generalization of the Central Path)

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 … Read more

Polynomial time algorithms to approximate mixed volumes within a simply exponential factor

We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets. Our main result is a randomized poly-time algorithm which approximates $V(K_1,…,K_n)$ with multiplicative error $e^n$ and with better rates if the affine dimensions of most of the sets $K_i$ are small.\\ Even such rate is impossible to achieve … Read more

An LMI description for the cone of Lorentz-positive maps

Let $L_n$ be the $n$-dimensional second order cone. A linear map from $\mathbb R^m$ to $\mathbb R^n$ is called positive if the image of $L_m$ under this map is contained in $L_n$. For any pair $(n,m)$ of dimensions, the set of positive maps forms a convex cone. We construct a linear matrix inequality (LMI) that … Read more

Hyperbolic Programs, and Their Derivative Relaxations

We study the algebraic and facial structures of hyperbolic programs, and examine natural relaxations of hyperbolic programs, the relaxations themselves being hyperbolic programs. Citation TR 1406, School of Operations Research, Cornell University, Ithaca, NY 14853, U.S., 3/04 Article Download View Hyperbolic Programs, and Their Derivative Relaxations

The Lax conjecture is true

In 1958 Lax conjectured that hyperbolic polynomials in three variables are determinants of linear combinations of three symmetric matrices. This conjecture is equivalent to a recent observation of Helton and Vinnikov. Citation Department of Mathematics, Simon Fraser University, Canada Article Download View The Lax conjecture is true

The mathematics of eigenvalue optimization

Optimization problems involving the eigenvalues of symmetric and nonsymmetric matrices present a fascinating mathematical challenge. Such problems arise often in theory and practice, particularly in engineering design, and are amenable to a rich blend of classical mathematical techniques and contemporary optimization theory. This essay presents a personal choice of some central mathematical ideas, outlined for … Read more