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$
  • 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 Apr 22 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 Apr 22 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 Apr 22 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 Apr 22 at 13:07
  • 1
    $\begingroup$ For an exercise class I think I'd go with a cardio machine over a Lagrange multiplier. Just my preference. $\endgroup$ – Daniel Lichtblau Apr 22 at 21:53
5
$\begingroup$

All minima should be searched:

f[x_, y_] = x^2 - x + 2 y^2;
g[x_, y_] = x^2 + y^2 - 1;

First we look for the minima on the edge. With Langrange we get:

L = f[x, y] + λ*g[x, y];
sol = Solve[{Grad[L, {x, y}] == 0, g[x, y] == 0}, {x, y}, λ, Reals]

results

hessian = D[f[x, y], {{x, y}, 2}] /. sol;

hessian: positive definite -> strict local minimum

hessian: negative definite -> strict local maximum

test = Transpose[{{x, y, f[x, y]} /. sol,
    PositiveDefiniteMatrixQ /@ hessian,
    NegativeDefiniteMatrixQ /@ hessian}];

TableForm[Partition[Flatten[test], 5], TableAlignments -> Right, 
 TableHeadings -> {None, {"x", "y", "f[x,y]", "pos. definite", "neg. definite"}}]

enter image description here

All points are minima! Now we are looking for minima within the region.

rsol = First@Solve[Grad[f[x, y], {x, y}] == 0, {x, y} \[Element] ImplicitRegion[x^2 + y^2 < 1, {x, y}]]

enter image description here

rhessian = D[f[x, y], {{x, y}, 2}] /. rsol;
{PositiveDefiniteMatrixQ @ rhessian, NegativeDefiniteMatrixQ @ rhessian}
{True, False}

{f[x, y] /. rsol , rsol}

enter image description here

This is the global minimum.

| improve this answer | |
$\endgroup$
1
$\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$
  • $\begingroup$ I want all the points of LOCAL minima $\endgroup$ – Maurizio Moreschi Apr 22 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 discontentment♦ Apr 22 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 Apr 22 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 Apr 22 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 Apr 22 at 15:58

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.