15
$\begingroup$

Wikipedia suggests that:

"Methods based on real algebraic geometry" are some of the "most successful general strategies" for solving global optimization problems.

Could someone suggest an reference for learning about how algebraic geometry can be used to solve optimization problems? Preferably one that doesn't assume advanced knowledge beyond that of ye average graduate with a Math degree.

Of course, if someone would like to add a short explanation of their own as to why and how this method is used, they are more than welcome.

$\endgroup$
  • 1
    $\begingroup$ @PeterSheldrick - linear least squares is a solution to a subset of convex optimization problems. By "global optimization" one generally means non-convex problems with many many local minima, with the goal of finding the global minimum. $\endgroup$ – nbubis Feb 19 '14 at 19:02
  • $\begingroup$ @nbubis were you able to find any textbook on this subject? $\endgroup$ – dineshdileep Jul 19 '14 at 9:26
  • $\begingroup$ @dineshdileep - no :( why is why I did not yet accept the answer below. Feel free to add your own. $\endgroup$ – nbubis Jul 19 '14 at 17:19
4
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! though I'm not I'm clear about where the algebraic geometry comes in - are you saying that I should look into homotopy continuation methods? $\endgroup$ – nbubis Feb 21 '14 at 23:53
  • $\begingroup$ One of the objects of study in algebraic geometry is the $0$ locus of nonlinear polynomial systems of equations. Homotopy methods utilize classical algebraic geometry results in such a way where one can be assured of finding all the (complex) solutions. $\endgroup$ – vertical.void Feb 22 '14 at 0:03
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.