Ottimizzazione Globale in RN - Home - Corsi · 2016. 11. 5. · soluzione globale. Figure 1:...
1
Ottimizzazione Globale in R N Daniela Lera Dipartimento di Matematica e Informatica Introduzione Problema Determinare x * ∈ S, tale che F(x * ) ≤ F(x), ∀x ∈ S, (1) dove F:S → R ` e una funzione assegnata in S ⊆ R N . Problemi reali che modellizzati conducono a (1) si incontrano in economia, analisi di immagini, progettazione di circuiti elettronici, reti di comunicazione etc. Le funzioni obiettivo che derivano da applicazioni reali sono molto spesso multiestremali, non differenziabili e difficili da valutare. Algoritmi per la risoluzione di (1) in senso locale, ovvero per la determinazione di un minimo locale, sono stati proposti da molto tempo. In tempi recenti il problema (1) ` e stato studiato in modo sistematico e sono stati proposti algoritmi in grado di determinare, sotto varie ipotesi, la soluzione globale. Figure 1: Funzioni Griewank e Michalewics. Difficolt` a di risoluzione i) Non esiste un criterio generale per stabilire se un dato punto ` e un punto di minimo globale. Ci` o` e rilevante soprattutto perch` e non consente una facile definizione di criteri di stop dei metodi iterativi di minimizzazione. ii) Generalmente non ` e possibile determinare un punto di minimo globale in un tempo finito (Dixon 1978). Usualmente si cerca un punto nell’insieme S * ε = {x ∈ S: kx - x * k≤ ε, x * ∈ S * } ε> 0 iii) Nemirovsky, Yudin e Vavasis (1995) hanno dimostrato che, sotto opportune ipotesi, la complessit` a computazionale del problema dell’Ottimizzazione Globale ` e esponenziale. Anche in dimensioni basse, per es. N=6, il problema pu`o essere intrattabile. Tecniche di risoluzione I Approccio deterministico Garanzia di successo. Teoremi di convergenza. Condizioni a volte restrittive per la funzione obiettivo. I Approccio stocastico Generalmente ipotesi molto deboli sulla funzione obiettivo. Ampliamento della classe delle funzioni obiettivo. Non assoluta garanzia di successo del metodo. Convergenza in probabilit` a. I Approccio euristico Spesso riescono a trovare la soluzione globale. Non riescono a dimostrare teoricamente l’ottimalit` a della soluzione trovata! Figure 2: Funzione test GKLS Figure 3: Funzione Shubert Funzioni Lipschitziane Se la funzione obiettivo soddisfa la condizione di Lipschitz |F(x) - F(y)|≤ L||x - y ||, 0 ≤ L ≤∞ esiste un’ampia classe di metodi di risoluzione che prevede una partizione del dominio. Generalmente la costante L non ` e nota. Una delle problematiche pi` u importanti in un problema di ottimizzazione globale Lipschitziano ` e proprio il trattamento della costante. Si dimostra che stime appropriate della costante globale L e delle costanti locali L i relative a sottointervalli del dominio di ricerca possono influenzare significativamente la velocit` a e la convergenza dei metodi. Utilizzo delle curve di Peano Un possibile approccio deterministico introdotto da Strongin nel 1972 prevede l’utilizzo delle curve “riempi-spazio” di Peano per ridurre la dimensione N del problema originale. In particolare Strongin ha dimostrato che il minimo globale di un problema N-dimensionale Lipschitziano ` e uguale al minimo globale della funzione monodimensionale f(x) = F(p(x)), x ∈ [0, 1] dove p(x) ` e la curva di Peano. Inoltre la funzione f diventaH¨olderiana |F(x) - F(y)|≤ H||x - y || 1/N con H = 2L √ N+3, costante di H¨older. Figure 4: Approssimazioni della curva di Peano in dimensione 2 e 3. -1 -0.5 0 0.5 1 -1 -0.5 0 0.5 1 -1 0 1 2 3 4 5 6 0 0.2 0.4 0.6 0.8 1 -1 0 1 2 3 4 5 Figure 5: Funzione test in 2 dimensioni con curva di Peano di livello 5 e corrispondente funzione ridotta. Bibliografia Gaviano M., Kvasov D.E., Lera D., and Sergeyev Ya.D., Software for generation of classes of test functions with known local and global minima for global optimization, ACM TOMS, 29(4), 469–480 (2003). Strongin R.G. and Sergeyev Ya.D., Global Optimization with Non-convex Constraints: Sequential and Parallel Algorithms, Kluwer, Dordrecht (2000). Lera D. and Sergeyev Ya.D., Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and H¨older constants., Communications in Nonlinear Science and Numerical Simulation, 23, 328–342 (2015). Lera D. and Sergeyev Ya.D., Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives, SIAM J. Optim., 23(1), 508–529 (2013). Sergeyev Ya.D., Strongin R.G., and Lera D., Introduction to Global Optimization Exploiting Space-Filling Curves, Springer, New York (2013). 17-20 Ottobre 2016 Corso di Studi in Matematica
Transcript of Ottimizzazione Globale in RN - Home - Corsi · 2016. 11. 5. · soluzione globale. Figure 1:...
Ottimizzazione Globale in RN
Daniela Lera
Dipartimento di Matematica e Informatica
Introduzione
Problema
Determinare x∗ ∈ S, tale che F(x∗) ≤ F(x), ∀x ∈ S, (1)
dove F : S→ R e una funzione assegnata in S ⊆ RN.
Problemi reali che modellizzati conducono a (1) si incontrano in economia,analisi di immagini, progettazione di circuiti elettronici, reti dicomunicazione etc.
Le funzioni obiettivo che derivano da applicazioni reali sono molto spessomultiestremali, non differenziabili e difficili da valutare.
Algoritmi per la risoluzione di (1) in senso locale, ovvero per ladeterminazione di un minimo locale, sono stati proposti da molto tempo.In tempi recenti il problema (1) e stato studiato in modo sistematico e sonostati proposti algoritmi in grado di determinare, sotto varie ipotesi, lasoluzione globale.
Figure 1: Funzioni Griewank e Michalewics.
Difficolta di risoluzione
i) Non esiste un criterio generale per stabilire se un dato punto e un punto diminimo globale. Cio e rilevante soprattutto perche non consente una faciledefinizione di criteri di stop dei metodi iterativi di minimizzazione.
ii) Generalmente non e possibile determinare un punto di minimo globale in untempo finito (Dixon 1978).Usualmente si cerca un punto nell’insieme
S∗ε = {x ∈ S : ‖x− x∗‖ ≤ ε, x∗ ∈ S∗} ε > 0
iii) Nemirovsky, Yudin e Vavasis (1995) hanno dimostrato che, sotto opportuneipotesi, la complessita computazionale del problema dell’OttimizzazioneGlobale e esponenziale. Anche in dimensioni basse, per es. N=6, il problemapuo essere intrattabile.
Tecniche di risoluzione
I Approccio deterministico Garanzia disuccesso. Teoremi di convergenza.Condizioni a volte restrittive per lafunzione obiettivo.
I Approccio stocastico Generalmenteipotesi molto deboli sulla funzioneobiettivo. Ampliamento della classe dellefunzioni obiettivo.Non assoluta garanzia di successo delmetodo. Convergenza in probabilita.
I Approccio euristico Spesso riescono atrovare la soluzione globale.Non riescono a dimostrare teoricamentel’ottimalita della soluzione trovata!
Figure 2: Funzione test GKLS
Figure 3: Funzione Shubert
Funzioni Lipschitziane
Se la funzione obiettivo soddisfa la condizione di Lipschitz
|F(x)− F(y)| ≤ L||x− y||, 0 ≤ L ≤ ∞esiste un’ampia classe di metodi di risoluzione che prevede una partizionedel dominio.
Generalmente la costante L non e nota. Una delle problematiche piuimportanti in un problema di ottimizzazione globale Lipschitziano e proprioil trattamento della costante.
Si dimostra che stime appropriate della costante globale L e delle costantilocali Li relative a sottointervalli del dominio di ricerca possono influenzaresignificativamente la velocita e la convergenza dei metodi.
Utilizzo delle curve di Peano
Un possibile approccio deterministico introdotto da Strongin nel 1972prevede l’utilizzo delle curve “riempi-spazio” di Peano per ridurre ladimensione N del problema originale.
In particolare Strongin ha dimostrato che il minimo globale di un problemaN-dimensionale Lipschitziano e uguale al minimo globale della funzionemonodimensionale
f(x) = F(p(x)), x ∈ [0, 1]
dove p(x) e la curva di Peano. Inoltre la funzione f diventa Holderiana
|F(x)− F(y)| ≤ H||x− y||1/N
con H = 2L√
N + 3, costante di Holder.
Figure 4: Approssimazioni della curva di Peano in dimensione 2 e 3.
−1
−0.5
0
0.5
1
−1
−0.5
0
0.5
1
−1
0
1
2
3
4
5
6
0 0.2 0.4 0.6 0.8 1
−1
0
1
2
3
4
5
Figure 5: Funzione test in 2 dimensioni con curva di Peano di livello 5 e corrispondente funzione
ridotta.
Bibliografia
Gaviano M., Kvasov D.E., Lera D., and Sergeyev Ya.D., Software for generation of classesof test functions with known local and global minima for global optimization, ACM TOMS,29(4), 469–480 (2003).
Strongin R.G. and Sergeyev Ya.D., Global Optimization with Non-convex Constraints:Sequential and Parallel Algorithms, Kluwer, Dordrecht (2000).
Lera D. and Sergeyev Ya.D., Deterministic global optimization using space-filling curvesand multiple estimates of Lipschitz and Holder constants., Communications in NonlinearScience and Numerical Simulation, 23, 328–342 (2015).
Lera D. and Sergeyev Ya.D., Acceleration of univariate global optimization algorithmsworking with Lipschitz functions and Lipschitz first derivatives, SIAM J. Optim., 23(1),508–529 (2013).
Sergeyev Ya.D., Strongin R.G., and Lera D., Introduction to Global OptimizationExploiting Space-Filling Curves, Springer, New York (2013).
17-20 Ottobre 2016 Corso di Studi in Matematica
