minimizzare funzioni

Si puo' trovare il minimo di una funzione con un programma seguendo due strade, dato un dominio di definizione dove trovare il minimo e la tolleranza richiesta.

• si suddivide l'intervallo di definizione in tanti sotto-intervalli, ciascuno lungo quanto la tolleranza (una sorta di binning) e si cerca l'intervallo tale per cui la funzione nel punto medio dell'intervallo assume valore minimo. A patto di scegliere la precisione adeguata e che la funzione sia definita con "buone" proprieta' (quindi non la funzione di Dirichlet ad esempio :) ) il minimo di trova. Chiaramente e' un metodo molto lento e che dipende linearmente dalla dimensione dell'intervallo scelto.
  
• si cercano algoritmi che restringano l'intervallo di ricerca basandosi su considerazioni analitiche, per evitare di valutare la funzione su una ditribuzione di punti uniforme nel suo domino.
  

Nel secondo caso, data una funzione continua, definita su un intervallo chiuso [a,b], con un unico estremante in (a,b) che sia minimo, un possibile algoritmo e' il seguente.

• Si divide l'intervallo in 3 parti, quindi si trovano due punti in (a,b), siano essi c, d tali che a < c < d < b.
  
• Si valuta f(c) ed f(d). Nel caso in cui f(c) < f(d) allora il minimo cercato e' compreso fra a e d, quindi si re-itera la procedura fra a e d; altrimenti, fra c e b.
  
• Ci si arresta quando la distanza fra gli estremi dell'intervallo di volta in volta considerato sono abbastanza vicini fra loro rispetto alla tolleranza, vale a dire che | max-min | < tolerance. A questo punto, il minimo della funzione e' |max-min| / 2.
  

Il metodo ideale in questo caso e' utilizzare una funzione ricorsiva, cioe' segua il seguente prototipo.

double ricorsiva (/*ingresso*/)
{
  if (/*condizione soddisfatta*/) return /*risultato finale*/ ;
  else return ricorsiva (/*ingresso modificato*/) ;
}

Questa tecnica funziona in un caso speciale, in cui la funzione abbia un unico minimo nell'insieme aperto e non abbia massimi nello stesso insieme. La parte piu' complessa del problema rimarra', a questo punto, riuscire ad isolare l'intervallo di dominio dove effettuare la minimizzazione.
Di seguito un esempio di funzione di minimizzazione, con il prototipo in minmaxMIB.h, l'implementazione in minmaxMIB.cc ed un test in testminmaxMIB.cpp. Come si vede, pare che l'ordine degli estremi non sia influente; come mai?

minmaxMIB.h

#ifndef minmaxMIB_h
#define minmaxMIB_h

//! funzione iterativa per trovare il massimo
//! locale di una funzione con errore assoluto "tolerance"
double trisection (double func (double),
                   const double & left,
                   const double & right,
                   const double & tolerance) ;

#endif

minmaxMIB.cc

#include <cmath>
#include <iostream>
#include "minmaxMIB.h"


double trisection (double func (double),
                   const double & left,
                   const double & right,
                   const double & tolerance) 
{
  if (fabs (right-left) < tolerance) return 0.5 * (right + left) ;
  double medLeft = left + (right - left) * 0.3 ;
  double medRight = left + (right - left) * 0.6 ;
  if ( func (medLeft) > func (medRight)) 
    return trisection (func,medLeft,right,tolerance) ;
  if ( func (medLeft) < func (medRight)) 
    return trisection (func,left,medRight,tolerance) ;
  // questo nel caso di indecisione
  if (right < left) return right - 1. ;
  else return left - 1.  ;
}

testminmaxMIB.cpp

#include <iostream>
#include <cmath>
#include "minmaxMIB.h"

double funzione (double x) ;


// ------------------------------------------------


int main ()
{
  std::cout << "minimo di cos(x) fra 0 e 4 :"
            << trisection (cos,0,4,0.001) 
//            << trisection (funzione,0,4,0.001) 
            << std::endl ;
  std::cout << "minimo di cos(x) fra 4 e 0 :"
            << trisection (cos,0,4,0.001) 
//            << trisection (funzione,4,0,0.001) 
            << std::endl ;

  return 0 ;
}


// ------------------------------------------------


double funzione (double x)
{
  return cos (x) ;
}