3
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ You will have a better chance by reducing your problem to 1D; replace y with Sqrt[1-x^2] with the constraint -1<=x<=1 (your Cost function depends only on y^2 anyways). $\endgroup$
    – b.gates.you.know.what
    May 21, 2015 at 17:39
  • $\begingroup$ @b.gatessucks That worked. But I do need to extend this function to a large number of variables. So, is there any general thing that will work. $\endgroup$
    – hardik24
    May 21, 2015 at 17:49
  • 4
    $\begingroup$ Why not parametrize? {Cos[t], Sin[t]} /. t -> ArgMin[{Cost[0.27, 0.96286, Cos[t], Sin[t]], 0 <= t < 2 π}, t] $\endgroup$
    – J. M.'s eventual burnout ♦
    May 21, 2015 at 18:27

3 Answers 3

Reset to default
12
$\begingroup$

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"} *)
Improve this answer
$\endgroup$
7
  • $\begingroup$ Perfect. I tried introducing more variables and it worked. Also, it is clear now why it was not working earlier. Thanks $\endgroup$
    – hardik24
    May 21, 2015 at 19:01
  • $\begingroup$ @hardik24 Excellent, I'm glad I could help. Thank you for the accept! $\endgroup$
    – MarcoB
    May 21, 2015 at 19:07
  • 1
    $\begingroup$ Have you seen this, by any chance? $\endgroup$
    – J. M.'s eventual burnout ♦
    May 21, 2015 at 19:09
  • $\begingroup$ @Guesswhoitis. I had not, I was still only starting to wonder how to go about extracting that information. Thanks for the pointer! I added a bit to my answer using the code you had provided there, to see what was going on here. (and +1 on that answer!) $\endgroup$
    – MarcoB
    May 21, 2015 at 19:27
  • $\begingroup$ No prob; I was actually sure that downhill simplex is almost always used by NMinimize[], but I linked you to that thread so you can check for yourself. I imagine that poor simplex tumbling around, not knowing how to get out of the rut it's stuck in… :) $\endgroup$
    – J. M.'s eventual burnout ♦
    May 21, 2015 at 19:30
2
$\begingroup$

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}} *)
Improve this answer
$\endgroup$
2
  • $\begingroup$ No, I need to optimize it over the ring only. x^2 and y^2 are probabilities and I need to make their sum equal to 1 $\endgroup$
    – hardik24
    May 21, 2015 at 18:05
  • $\begingroup$ @hardik24 OK I see. I think I was going after the wrong issue then. I posted a second answer on this point. Can you give it a look? $\endgroup$
    – MarcoB
    May 21, 2015 at 18:38
1
$\begingroup$

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}]:

enter image description here

Improve this answer
$\endgroup$
3
  • $\begingroup$ But can you tell me why the thing that I am trying is not working? $\endgroup$
    – hardik24
    May 21, 2015 at 17:53
  • $\begingroup$ Modify the constraint statement: Minimize[{Cost[0.27, 0.96286, x, y]}, {x, y} \[Element] Disk[]] outputs {0.873162, {x -> 0.244627, y -> -0.969617}}. $\endgroup$
    – dantopa
    May 21, 2015 at 18:15
  • $\begingroup$ But I do need to optimize it over the circle only. $\endgroup$
    – hardik24
    May 21, 2015 at 18:18

Your Answer

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

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