FindMinimum

[Adalbert Hanssen <hsse@XXXXXXX.de>]

Hallo, Anwender mathematischer Optimierung,

manchmal liefert FindMinimum die Meldung

FindMinimum::fmcv  FindMinimum failed to converge....

und bricht kurz vor dem Ziel ab. Dann kann man MaxIterations 
(defaultmaeszig 30) hochsetzen, aber trotzdem bricht FindMinimum 
wieder kurz vor dem Ziel ab, wenn man vom alten Startpunkt ausgeht.

Wenn man hingegen die Funktion mit dem Ergebnis der alten Suche erneut 
startet, kommt man naeher ans Ziel. Hier ein Beispiel:

Toru[x_,y_,rm_,rt_,{px_,py_,pz_}]:= (* spez. Teil einer Torus-Flaeche *)
Module[{m,sm,st,w}
      ,m=rm-rt; 
       w=rt^2-(x-px)^2;
       -N[-Sqrt[m^2+w-(y-py)^2 - 2*m*Sqrt[w]]-pz]
     ];

(* Testdaten fuer App-Ziel... *)
Clear[x,y]
xyg={{-33.5, 0}, {-16.75, -16.75}, {-16.75, 0}, {-16.75, 16.75}, 
{0, -33.5}, {0, -16.75}, {0, 16.75}, {0, 33.5}, {16.75, -16.75}, 
{16.75, 0}, {16.75, 16.75}, {33.5, 0}, {0, 0}};
xyz=xyg/.{{x_,y_}->{x,y,Toru[x,y,-200.,-100.,{0,5,-200}]}};

fehler[r1_,r2_,xt_,yt_,zt_]:=   (* Z-Fehlerquadr. der xyg von Toru... *)
Module[{i,x,y,z}
      ,Plus @@ Table[{x,y,z}=xyz[[i]]; 
                     (z-Toru[x,y,r1,r2,{xt,yt,zt}])^2
                    ,{i,Length[xyz]}
                    ]
      ];
      
Das Minimum dieser Funktion ist 0:     
      
fehler[-200,-100,0,5,-200]
8.07793566946316*10^-28

Nun suchen wir die Parameter des Torus, starten aber - zugegebener-
maszen - ein erkleckliches Stueck vom Ziel. 

Clear[r1,r2,xt,yt,zt];
zts=r1s=-180;                           (* Ziel ist -200 *)
r2s=-150;                                       (* Ziel ist -100 *)
xts=0.;                                         (* am Ziel           *)
yts=1.;                                         (* Ziel ist 5    *)

Print["100 Iterationen ab Start..."];
Print[FindMinimum[fehler[r1,r2,xt,yt,zt]
              ,{r1,r1s},{r2,r2s},{xt,xts},{yt,yts},{zt,zts}
              ,MaxIterations->100
              ]
     ];


100 Iterationen ab Start...
FindMinimum::fmmp: 
   Machine precision is insufficient to achieve the requested accuracy 
   or precision.
                                                            -15
{0.676629, {r1 -> -195.407, r2 -> -111.932, xt -> -2.4972 10   , 
    yt -> 5.15462, zt -> -195.558}}


Print["das gleiche mit 10 Starts und jeweils wenigen Iterationen..."];
Do[erg=
   FindMinimum[fehler[r1,r2,xt,yt,zt]
              ,{r1,r1s},{r2,r2s},{xt,xts},{yt,yts},{zt,zts}
              ,MaxIterations->10 (* bei 5 geht's noch nicht - not bracketed... *)
              ];
   {r1s,r2s,xts,yts,zts}={r1,r2,xt,yt,zt}/.erg[[2]];
   Print[i,". erg=",erg];
  ,{i,1,10}
  ];

FindMinimum::fmcv: 
   FindMinimum failed to converge to the prescribed accuracy within 
   10 iterations.
(weitere Auftritte dieser Meldung habe ich der Kuerze halber
herausgeschnitten...)
                                                                  -15
1. erg={1.84113, {r1 -> -192.519, r2 -> -89.2307, xt -> 1.76776 10   , 
    yt -> 7.90443, zt -> -192.269}}

                                                                    -15
2. erg={0.0153736, {r1 -> -192.187, r2 -> -99.3107, xt -> 5.96635 10   , 
    yt -> 4.8028, zt -> -192.147}}

                                                                   -15
3. erg={0.0135764, {r1 -> -192.59, r2 -> -99.1715, xt -> 6.28339 10   , 
    yt -> 4.81856, zt -> -192.549}}

                                                                     -15
4. erg={0.00676924, {r1 -> -196.913, r2 -> -98.7738, xt -> 5.44024 10   , 
    yt -> 4.96178, zt -> -196.881}}

                                                                    -15
5. erg={0.00232589, {r1 -> -196.93, r2 -> -99.7685, xt -> 5.65352 10   , 
    yt -> 4.90344, zt -> -196.916}}

                                                                   -15
6. erg={0.00207251, {r1 -> -197.036, r2 -> -99.6587, xt -> 5.679 10   , 
    yt -> 4.92142, zt -> -197.02}}


                  -8                                                   -15
7. erg={3.49907 10  , {r1 -> -200.012, r2 -> -100.002, xt -> 8.86954 10   , 
    yt -> 5.0002, zt -> -200.012}}

                  -8                                                   -15
8. erg={1.04066 10  , {r1 -> -200.004, r2 -> -100.002, xt -> 8.87829 10   , 
    yt -> 5.0001, zt -> -200.004}}

                  -13                                             -15
9. erg={3.30299 10   , {r1 -> -200., r2 -> -100., xt -> 8.88155 10   , 
    yt -> 5.,  zt -> -200.}}


                  -17                                             -15
10. erg={5.8885 10   , {r1 -> -200., r2 -> -100., xt -> 8.88155 10   , 
     yt -> 5.,  zt -> -200.}}




Ich habe absichtlich FindMinimum fuer jeden Optimierungsparameter 
nur einen Startwert gegeben. Da die zu minimierende Funktion 
hier symbolisch differenzierbar ist, mueszte die Jacobimatrix deshalb 
symbolisch berechnet weren.

Ich vermute: FindMinimum stellt fuer die Iterationen EINE Jacobimatrix 
auf und berechnet nur EINE Pseudoinverse. Das geht gut, solange die 
Startwerte nahe genug beim gesuchten Minimum liegen. Wenn man aber - 
nachdem der Algorithmus weit vom Start weggeschritten ist - hin und 
wieder eine neue Jacobimatrix berechnet, kommt man auch bei entfernte-
rem Start ans Ziel.

Ist dies in Mathematica 3.0 irgendwie anders geworden? Der Artikel im
"Mathematica Journal Vol6 No4 p 49f" sagt nur, dasz es nun die neue
Option Method->QuasiNewton gibt, aber nicht, was sich dahinter verbirgt
(vermutlich nur die Art der Relaxation) oder ob es etwas mit der Neube-
rechnung der Matrizen zu tun hat.

Deshalb die Frage: kann man FindMinimum veranlassen - z.B. 3 oder 4 
Schritte, nachdem es in Suchrichtung einen Einschlusz gefunden hat 
- oder - wenn es mit der alten Matrix nicht mehr recht vom Fleck kommt 
- eine neue Matrix berechnet?


Dipl-Math. Adalbert Hanszen