Minimize method is not giving minimum. Why?

Question

I was doing an optimization but facing a problem getting what exactly Minimize function do. I run the following code:

    Log1[x_] := If[x == 0, 0, Log2[Abs[x]]];
    VEntropy[x_] := -(x Log1[x] + (1 - x) Log1[1 - x]);
    Prob[a_, b_, x_, y_] := 1 - 1/((a/x)^2 + (b/y)^2);
    Cost[a_, b_, x_, y_] := VEntropy[x^2] + Prob[a, b, x, y];
    Minimize[{Cost[0.27, 0.96286, x, y], x^2 + y^2 == 1}, {x, y}]
    Cost[0.27, 0.96286, 0.244627, 0.969617]
    Norm[{0.244627, 0.969617}]

Output of the code is:

    {1., {x -> 1., y -> -5.84379*10^-9}}
    0.873162
    1.

But as you can see Minimize is not giving the minimum cost. As MarcoB suggested in comment to plot the graph in 3D and it seems that it is giving the local minimum. But as far as I know Minimize gives global minimum but then why is it giving local minimum here?

Answer 1

I think I finally understand what you were asking (takes me a while to get in gear in the morning...), and I believe that you are simply running into numerical problems.

In fact, according to its documentation, Minimize will call NMinimize automatically when given numerical input. NMinimize (docs here) will still attempt a search for a global minimum on the specified domain, but it is guaranteed to find one only if the function and the constraints are linear, and yours do not appear to be. Otherwise, NMinimize may find only a local minimum.

For instance, you can see that different algorithms for NMinimize give you different results. Let's try them all using the unit ring constraint you want, and with each method's stock parameters:

NMinimize[{Cost[0.27, 0.96286, x, y], x^2 + y^2 == 1}, {x, y}, Method -> #]& 
  /@ {"NelderMead", "DifferentialEvolution", "SimulatedAnnealing", "RandomSearch"}

Here are the results:

Nelder-Mead             0.999993    x->1.           y->-2.50072*10^-7
Differential evolution  0.873162    x->-0.244627    y->-0.969618
Simulated annealing     0.999996    x->1.           y->-0.0000166821
Random search           1.          x->1.           y->-6.6605*10^-9

Notice that the differential evolution method stumbles upon one of your lower minima (given the symmetry of the problem, there is more than one), but others only find a local minimum, at least with the stock parameters. I'll have to leave it to you to play with the parameters to see if you can make them behave better.

As an aside, NMinimize has internal methods to determine which algorithm to use when you don't specifically request one. I did not know how to figure out which one is being used for a certain optimization, until @GuessWhoItIs pointed me in the direction of an older discussion, aptly titled Determining the default Method used in optimization and root-finding algorithms, in which he provided code to answer that very question.

Lifting @Guess's code bodily, and applying it to your minimization, we discover that the Nelder - Mead method is automatically chosen in your case:

Cases[
 Trace[NMinimize[{Cost[0.27, 0.96286, x, y], x^2 + y^2 == 1}, {x, y}],
   Optimization`NMinimizeDump`method, TraceInternal -> True],
 {HoldForm[Optimization`NMinimizeDump`method], 
   m_ /; FreeQ[m, Automatic]} :> m, Infinity
]

(* Out: {"NelderMead"} *)

Answer 2

With the constraint x^2 + y^2 == 1, you are minimizing the Cost function on the boundary of the unit disk centered on the origin, i.e. only along the rim of that circle.

What you seem to want is optimizing anywhere within the unit disk. You want an inequality there in the constraint:

Minimize[{Cost[0.27, 0.96286, x, y], x^2 + y^2 <= 1}, {x, y}]

(* Out: {0.873162, {x -> 0.244627, y -> -0.969617}}*)

You could obtain the same result using the newer Region variable specifications:

Minimize[Cost[0.27, 0.96286, x, y], {x, y} \[Element] Disk[{0, 0}, 1]]

(* Out: {0.873162, {x -> 0.244627, y -> -0.969617}} *)

You can now see the difference with what you were doing before with the equality constraint, where you were constraining $(x,y)$ to be a point on the unit circle instead:

Minimize[Cost[0.27, 0.96286, x, y], {x, y} \[Element] Circle[{0, 0}, 1]]

(* Out: {0.999993, {x -> 1., y -> 2.50416*10^-7}} *)

Answer 3

This sidesteps the question. To find the minimum on the constrained surface try FindMinimum[Cost[0.27, 0.96286, x, Sqrt[1 - x^2]], {x, 0.1}] with the result {0.873162, {x -> 0.244627}}.

The curve takes this form Plot[Cost[0.27, 0.96286, x, Sqrt[1 - x^2]], {x, -1, 1}]: