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