UC Davis Mathematics

News Feature

Select a news year:2019 2017 2016 2015 2013 2012 2009 2008

February 2019
By Jesus De Loera

Is there really a separation between pure and applied mathematics? The great mathematician Lobachevsky is attributed with saying “there is no branch of mathematics, however abstract, which may not some day be applied to phenomena of the real world.” There are plenty of examples of how this is evidently true for algebra (broadly including number theory too), geometry, and topology.

Here is one way in which algebraic geometry, sometimes mistakenly considered a pure and non-applicable part of mathematics, has helped us understand a well-known algorithm in Optimization. Optimization deals with finding the best solution or best choice among multiple valid solutions.

The concrete challenge in question is to maximize a linear functional under linear inequality and equation constraints. A very simple example is to find two numbers x1 and x2, with xi ≥ 0 and so that 2x1 + 3x2 is as large as possible. In matrix form we can write this as

Maximize cTx subject to Ax = b and x ≥ 0.

Here A is a real m × n matrix, and c, b are n and m vectors respectively. Despite its simplicity this is engine used in solving other optimization problems.

To solve the problem, Interior point methods follow a piecewise-linear approximation to the central path using Newton methods steps . In reality, the central path is an algebraic curve, given by the following system of quadratic and linear polynomial equations. When λ = 0, we obtain the optimum solution

Ax = b, ATy − s = c, and xisi = λ for i = 1, 2, …, n.

Understanding the exact central path is important. How “curvy” can the central path really be? Our intuition is that curves with small curvature are easier to approximate using fewer line segments and fewer Newton steps. Recently, using exciting new methods from tropical algebraic geometry, X. Allamigeon, P. Benchimol, S. Gaubert, and M. Joswig showed that the total curvature of the central path can grow exponentially with the input data. This implies a major breakthrough, that some interior-point methods cannot run in strongly polynomial time! Tropical algebraic geometry is a method to go from a polynomial system to a simpler combinatorial version. These techniques are fresh and unexpected, and there are many other examples like this with novel applications of algebraic and geometric techniques in Optimization. Here at UC Davis we have a thriving research group on this subject.