1
$\begingroup$

According to the Minimize documentation, when provided with approximate inputs, Minimize invokes NMinimize. However, different specifications of the same domain give different results when NMinimize is invoked explicitly versus implicitly via Minimize.

For example, defining a random input sample:

A = {{0.4277047469835642`, 
    0.16878397349541197`}, {0.6416571036236569`, 0.5910551264554926`}};
B = {{0.9699948146542698`, 
    0.8036723082029285`}, {0.02882838531248111`, 0.9544230849675173`}};
b = {0.29803837933767596`, 0.6635349216438007`};

Minimize[
 {Norm[A.x - b, Infinity] + Norm[B.x - b, Infinity],
  x \[VectorGreaterEqual] 0},
 x \[Element] Rectangle[{0, 0}, {1, 1}]]

(* {0.727324, {x -> {0.0802987, 0.50132}}} *)

But calling NMinimize explicitly gives a higher value:

NMinimize[
 {Norm[A.x - b, Infinity] + Norm[B.x - b, Infinity],
  x \[VectorGreaterEqual] 0},
 x \[Element] Rectangle[{0, 0}, {1, 1}]]
(* {0.746419, {x -> {0.185227, 0.441771}}} *)

Interestingly, other forms of specifying the domain for NMinimize seem to give the global minimum:

NMinimize[
 {Norm[A.x - b, Infinity] + Norm[B.x - b, Infinity],
  x \[VectorGreaterEqual] 0},
 x \[Element] Vectors[2, Reals]]
(* {0.727324, {x -> {0.0802988, 0.50132}}} *)

FWIW, all of this is in 12.0.0 for Mac OS X

Any thoughts? I'm mostly curious how the different domain specifications are changing the numerical optimization procedure.

$\endgroup$
2
$\begingroup$

From the Trace it look like Minimize does not run NMinimize in this case.


By default NMinimize will use the same methods as LinearProgramming and for vector minimization it will give completely unreliable result (see here).

This can be seen by running:

NMinimize;

Optimization`NMinimizeDump`$DiagnosticLevel = 3;

NMinimize[{Norm[A.x - b, Infinity] + Norm[B.x - b, Infinity],
   x \[VectorGreaterEqual] 0}, x ∈ Rectangle[{0, 0}, {1, 1}]]
(* {0.925839, {x -> {0.692173, 0.291364}}} *)

Because of no debug output (see here), it doesn't use any minimization methods.

You can try to use different methods:

NMinimize[{Norm[A.x - b, Infinity] + Norm[B.x - b, Infinity],
   x \[VectorGreaterEqual] 0}, x ∈ Rectangle[{0, 0}, {1, 1}],
  Method -> "Automatic"]
(* {0.735908, {x -> {0.127568, 0.474466}}} *)

NMinimize[{Norm[A.x - b, Infinity] + Norm[B.x - b, Infinity],
   x \[VectorGreaterEqual] 0}, x ∈ Rectangle[{0, 0}, {1, 1}],
  Method -> "NelderMead"]
(* {0.727324, {x -> {0.0802987, 0.50132}}} *)

You can get the list of available methods with:

Optimization`NMinimizeDump`$Methods
(* {"Automatic", "DifferentialEvolution", "MeshSearch", \
"NelderMead", "SimulatedAnnealing", "RandomSearch", \
"NonlinearInteriorPoint"} *)
$\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.