Bernd Sturmfels – Optimization Online

The Euclidean distance degree of an algebraic variety

Published: 2013/08/30

Constrained Nonlinear Optimization, Unconstrained Optimization algebraic variety, critical points, duality, euclidean distance degree

The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. For instance, for varieties of low rank matrices, the Eckart-Young Theorem states that this map is given by the singular value decomposition. This article develops a theory of such nearest point maps from the perspective of computational … Read more

The central curve in linear programming

Published: 2010/12/17

Jesús A. De Loera

Bernd Sturmfels

Cynthia Vinzant

Convex Optimization, Linear Programming, Nonlinear Optimization central path, curvature, degree, gauss map, groebner basis, hyperbolic polynomial, hyperplane arrangement, interior point methods, linear programming, matroid, projective variety, tutte polynomial

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