Global Optimization and Real Algebraic Geometry

Solution 1:

This is a very good question and can be answered more concretely if we decide to restrict ourselves to certain types of problems.

Suppose we have a system that we want to maximize or minimize that is subject to certain equality and inequality constraints and that the systems in question are all polynomial.

We can then find a global optimal solution using the Karush-Kuhn-Tucker criteria (or alternatively the Fritz-John conditions).

Consider the following contrived example.

Suppose we want to maximize $x_1^2 + 2x_1x_2 + x_2x_3 + 2x_1 - 4$ subject to points on the unit sphere, i.e. $x_1^2 + x_2^2 + x_3^2 - 1$. This actually reduces down to using LaGrange multipliers.

We then consider the zero locus (the set of common zeroes, also known as the variety) of the following system of equations:

$f_1(x_1,x_2,x_3,\mu_1) = 2x_1 + 2x_2 + 2 + 2\mu_1x_1 = 0$

$f_2(x_1,x_2,x_3,\mu_1) = 2x_1 + x_3 + 2\mu_1x_2 = 0$

$f_3(x_1,x_2,x_3,\mu_1) = x_2 + 2\mu_1x_3 = 0$

$f_4(x_1,x_2,x_3,\mu_1) = x_1^2 + x_2^2 + x_3^2 - 1 = 0$

Solving this system with any software package that does homotopy continuation (possibly HOMPACK or Phcpack) gives us two solutions that are approximately

$(-.7179056815169287, .6495969519526578, -.2502703187745829, 1.29779063520861)$

and

$(.9205188417273060, .3831260888917872, .07654712297337447, -2.502550546707357)$.

(with the last coordinate representing the lagrange multiplier)

Plugging these into the equation we want to maximize gives us $-6.015696316725544$ for the first solution and $-0.576930611565337$ for the second.

As such, $(.9205188417273060, .3831260888917872, .07654712297337447)$ is the approximate point on the sphere that maximizes our potential function.

Solution 2:

https://epubs.siam.org/doi/book/10.1137/1.9781611972290

I think the book is quite accessible and well written. At least the first few chapters should be easy to digest if you enough patience to read through them.

There is also a very nice survey:

https://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf

Reading parts of the survey (possibly skipping moment stuff for the moment :) ) or reading the second and the third chapters of the book should give you an idea.