1
$\begingroup$

Is there a way to either make FindMinimum do an exact computation or Minimize find also the local minima? Or other ideas to find local minima exactly?

Example: find all local minima (exact values, not approximations) of $f(x,y)=x^2 − x + 2y^2$ on $E=\{(x,y)\in \mathbb{R}^2 : x^2+y^2\le 1\}$.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ We need an example from you to see what the problem is. FindMinimum usually does what is required. What do you mean by exact? $\endgroup$
    – Hugh
    Commented Apr 22, 2020 at 10:27
  • 1
    $\begingroup$ One may find all the critical points of that differentiable function through Reduce[{D[x^2 - x + 2*y^2 D[x^2 - x + 2*y^2, x] == 0, x] == 0, D[x^2 - x + 2*y^2, y] == 0, x^2 + y^2 <= 1}, {x, y}, Reals] . Its behavior on the boundary should be studied separately. $\endgroup$
    – user64494
    Commented Apr 22, 2020 at 10:53
  • 1
    $\begingroup$ @user64494, yes like that I know how to do it in general. However, I was wondering if there were pre-implemented functions that deal with the boundary altogether. Of course, my question mainly about what happens on the boundary. $\endgroup$
    – Maurizio Moreschi
    Commented Apr 22, 2020 at 11:08
  • 3
    $\begingroup$ FindMinimum might also find a global min and miss local ones. To get all of them in some region one can set up a KKT solver. $\endgroup$
    – Daniel Lichtblau
    Commented Apr 22, 2020 at 13:07
  • 2
    $\begingroup$ For an exercise class I think I'd go with a cardio machine over a Lagrange multiplier. Just my preference. $\endgroup$
    – Daniel Lichtblau
    Commented Apr 22, 2020 at 21:53

2 Answers 2

Reset to default
7
$\begingroup$

Extrema on the edge.

f = x^2 - x + 2 y^2;
g = x^2 + y^2 - 1;
L = f + \[Lambda] g;

pts = Solve[{Grad[L, {x, y}] == 0, g == 0}, {x, y, \[Lambda]}];
points = pts[[All, 1 ;; 2]];
critpts = Thread@{f /. points, points};

bordered Hessian:

hesseMatrix = {{0, D[g, x], D[g, y]}, {D[g, x], D[L, x, x], 
     D[L, x, y]}, {D[g, y], D[L, y, x], D[L, y, y]}} /. pts;
detHesse = Det /@ hesseMatrix
{-4, 6, 6, -12}

max = Cases[Thread@{Sign /@ detHesse, critpts}, {1, _}][[All, 2]];
min = Cases[Thread@{Sign /@ detHesse, critpts}, {-1, _}][[All, 2]];
sol = Association["Minima" -> min, "Maxima" -> max]

enter image description here

Extrema within the region.

sol2 = Solve[{Grad[f, {x, y}] == 0, x^2 + y^2 < 1}, {x, y}];
globalMin = Thread@{f /. sol2, sol2}

enter image description here

Eigenvalues@D[f, {{x, y}, 2}] /. sol2
{4, 2}

Eigenvalues are positive; this is the global minimum.

reg = ImplicitRegion[x^2 + y^2 <= 1, {x, y}];
Show[
 Plot3D[f, {x, y} \[Element] reg, Mesh -> 10, 
  MeshFunctions -> {#^2 + #2^2 &}, PlotTheme -> "FilledSurface"],
 Graphics3D[{
   Red, [email protected], Point[{x, y, f} /. sol["Minima"][[All, 2]]],
   Green, [email protected], Point[{x, y, f} /. sol["Maxima"][[All, 2]]],
   Blue, [email protected], Point[{x, y, f} /. globalMin[[1, 2]]]}]
 ]

enter image description here

Improve this answer
$\endgroup$
2
$\begingroup$

The exact minimization of a function can be done using Minimize:

  f[x_, y_] := x^2 - x + 2 y^2
  sol = Minimize[f[x, y], {x, y}]
  (*{-(1/4), {x -> 1/2, y -> 0}} <= output of Minimize*)
  Show[
    Plot3D[f[x, y], {x, y} \[Element] Disk[{0, 0}, 1]],
    Graphics3D[{Red, PointSize[Large], 
       Point[Flatten@{{x, y} /. sol[[2]], sol[[1]]}]}]
  ]

enter image description here

Improve this answer
$\endgroup$
5
  • $\begingroup$ I want all the points of LOCAL minima $\endgroup$
    – Maurizio Moreschi
    Commented Apr 22, 2020 at 11:04
  • $\begingroup$ @Maurizio, for Minimize[], you need to separately consider the boundary: Minimize[{f[x, y], x^2 + y^2 == 1}, {x, y}] $\endgroup$
    – J. M.'s missing motivation ♦
    Commented Apr 22, 2020 at 12:03
  • 2
    $\begingroup$ @MaurizioMoreschi, do you really think that your function has more than one minima? it is possible just if you know an alternative algebra.. $\endgroup$
    – Rom38
    Commented Apr 22, 2020 at 14:22
  • $\begingroup$ @Rom38 Hahaha, that was not really my point, but I understand the misunderstanding! I gave the numerical example because people asked for it in the comment. Your method of course finds the point of minimum it this case, but it uses the information that the minimum is strong and absolute! $\endgroup$
    – Maurizio Moreschi
    Commented Apr 22, 2020 at 14:47
  • $\begingroup$ @MaurizioMoreschi, working with arbitrary function you should divide the domain to sub-domains and run the minimization inside all of them. Thus, you will have all local minima. $\endgroup$
    – Rom38
    Commented Apr 22, 2020 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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