SIAGA: Polynomial Optimization

Seven pictures from Applied Algebra and Geometry: Picture #1

The Society for Industrial and Applied Mathematics, SIAM, has recently released a journal of Applied Algebra and Geometry called SIAGA. The poster for this journal (see here) features seven pictures. In this blog post I will write about the mathematics represented by the first picture. This is part of a series of seven blog posts – one for each picture.

In the first section of this post “The Context”, I’ll set the mathematical scene. In the second section “The Picture” I’ll talk about the specifics of this particular image, representing Polynomial Optimization.

The Context

Optimization is a central pillar of applied mathematics, with applications in everything from biology to engineering to finance. Polynomial optimization is the study of how to maximize or minimize a polynomial function subject to constraints given by polynomial equations. The set of points in space that satisfy the required constraints is called the feasible region. This is our geometric object of interest. For particular structure on the constraints of an optimization problem, we have corresponding information on the kind of shape the feasible region can take. We are particularly interested in the boundary of the feasible region, since this is where the optimizing solution will often be found.

The geometry of a feasible region elucidates important aspects of the optimization problem. For example, it may indicate the type of algorithm best suited to maximizing a function on that shape. In return, the family of geometrical shapes naturally associated with an optimization problem connects it to the expertise of other areas of mathematics.

Semi-definite optimization is a generalization of linear optimization. Here, we extend from constraints given by positivity conditions on the entries of a vector to the notion of positivity for a matrix. The constraints take the form of positive semi-definiteness of real symmetric matrices. Feasible regions take the form of spectrahedra. These are obtained from the space of positive definite matrices by intersecting with a linear space. Semi-definite optimization problems are often a valuable stepping-stone in understanding more complicated problems, and can be used as a relaxation of the harder problem. For more about semi-definite optimization and its connection to algebraic geometry, see the book by Blekherman, Parrilo and Thomas: “Semidefinite Optimization and Convex Algebraic Geometry”.

The Picture

A naturally occurring feasible region with a non-linear boundary is the circle

$(x- u_1)^2 + (y - v_1)^2 = d^2 ,$

the collection of points a fixed distance away from the center.

Perhaps instead you want to be a fixed distance away from two points – close-by to both the train station and the ferry terminal, for example. The collection of points whose sum of distances from two points is a constant describes an ellipse

$\left\{ (x, y) \in \mathbb{R}^2 : \sum_{i = 1}^2 \sqrt{ (x - u_i)^2 + (y - v_i)^2 } = d \right\}$

For problems involving, say, three factories, five train stations and a ferry terminal, we want to generalize this notion to the so-called $k$-ellipse. This is the set of points whose sum of distances from $k$ given points is equal to some constant.

We fix the locations of $k$ focal points $(u_i, v_i)$ and consider the distance $d$ to be an unknown. The picture shows the surface

$\left\{ (x, y,d) \in \mathbb{R}^3 : \sum_{i = 1}^k \sqrt{ (x - u_i)^2 + (y - v_i)^2 } = d \right\}$

of points for which the sum of the distances from $(x,y)$ to the focal points is $d$. This constraint can be described by a polynomial equation, and is the non-linear boundary of the feasible region in a particular semi-definite optimization problem.

The central convex part of the picture holds the solution to this minimization problem. Its lowest point is the Fermat-Weber point which we often seek to find. If the distance of interest, $d$, is fixed then we take a horizontal slice through the picture and optimize on this slice. The external components are also algebraic solutions to the polynomial constraints.

This picture first appeared in the article “Semidefinite representation of the k-ellipse” by Nie, Parrilo and Sturmfels. This version of the image is due to Cynthia Vinzant, and appeared as cover art for the May 2014 issue of the Notices of the AMS.

6 thoughts on “SIAGA: Polynomial Optimization”

1. MSRI March 4, 2016 / 11:46 pm

We’ve shared your blog on the Mathematical Sciences Research Institute Facebook page. We’re excited for the full series of posts – thanks for sharing!

Liked by 1 person

2. ABDULMALEEK Wasiu shina November 5, 2016 / 4:01 am

Thanks for this … I would like to know the techniques for solving a constrained polynomial optimization with inequality and equality constraints

Like