About a year ago I had the pleasure of having a number of conversations with Abhishek Bhardwaj about the area of mathematics his PhD is on. This pair of posts is based on the fond memories I have of these conversations. Part two can be found here.
Optimization and Summing Squares
Optimization is a huge area of both pure and applied mathematics. Many questions and problems can be reduced to finding the minimum or maximum value of some function. That is we have a function and we wish to find the number such that
By considering the function we can reduce finding the maximum of to finding the minimum of another function. Minimizing a function isn’t always easy. Even when the function is a relative simple function such as a polynomial, it can be a very difficult problem.
A different way of thinking about the problem of minimizing the function , is to instead think about the function were is a real number. The minimum of is the largest value of such that the function is non-negative for all values . Thus we have a reduced our optimization problem into the problem of working out for which values of is the function non-negative.
Suppose our function was the following function that takes in two variables
To minimize this function we can look at the function which is equal to
We wish to work for which values of is this function non-negative. By doing the following algebraic manipulations we can rewrite like so
which is in turn equal to
Since and are both squares of real numbers, they are both non-negative. Furthermore at the point , we have that . Thus is non-negative if and only if , that is if and only if . Thus we can conclude that the minimum of is .
Sums of Squares
Note that the number can be written as if and only if . Thus, in the above example we have that is non-negative if and only if can be written as a sum of squares. That is is non-negative if and only if can be written as for some polynomials .
In general, if a polynomial can be written as a sum of squares of other polynomials, then the polynomial must be non-negative. A natural question to ask is if every non-negative polynomial can be written as a sum of squares. This would make our optimization problem a lot easier. To minimize , we can check for which values of can be written as a sum of squares.
This question of whether every non-negative polynomial can be written as a sum of squares was answered in the negative by David Hilbert in 1888. However, Hilbert’s proof was non-constructive, it didn’t give an explicit example of such a polynomial. The proof only showed that such polynomials exist out there somewhere. It took nearly nearly 80 years for the first explicit example to be given by the mathematician Theodore Motzkin in 1967. We will take a look at Motzkin’s polynomial in the next blog post.
One thought on “Sums of Squares – Part 1: Optimization”