Metodi per la soluzione di problemi di programmazione non lineare

Metodi per la soluzione di problemi diprogrammazione non lineare

Metodi vincolati

Luca Vitale

Dipartimento di InformaticaUniversita degli studi di Salerno

Outline

Introduzione al problema

Metodi non vincolatiFunzioni di penalita sequenzialiFunzioni Lagrangiane aumentate sequenzialiFunzioni di penalita esatteFunzioni Lagrangiane aumentate esatte

Metodi di programmazione quadratica ricorsivaVincoli di disuguaglianzaVincoli di uguaglianza

Conclusioni

Tipologie di problemi

I problemi che affronteremo avranno la seguente forma:

minx

f(x) Rn → R

h(x) = 0 Rn → Rp p ≤ n

g(x) ≤ 0 Rn → Rm

(1)

O forme con solo vincoli di uguaglianza o vincoli di diseguaglianza.

Condizioni di ottimalita

Le condizioni di ottimalita che verrano sempre consideratesoddisfatte sono le seguenti:

I Condizioni necessarie del primo ordine (KKT)

I Condizioni sufficienti del secondo ordine

Condizioni necessarie del primo ordine

Theorem (Condizioni necessarie del primo ordine)

se x* e una soluzione locale del problema, e se in x* e soddisfattala condizione di regolarita dei vincoli, esistono e sono unici imoltiplicatori µ*, λ* che insieme a x*, soddisfano le seguenticondizioni:

∇xL(x∗, µ∗, λ∗) = 0

h(x∗) = 0

g(x∗) ≤ 0

λ∗ ≥ 0

λ∗′g(x∗) = 0

(2)

Tali condizioni sono dette di Kuhn-Tucker.

Condizioni sufficienti del secondo ordine

Theorem (Condizioni sufficienti del secondo ordine)

se x∗, λ∗, µ∗ soddisfano le condizioni del primo ordine; se x∗, λ∗

soddisfano le condizioni di stretta complementarita; se infine risultache:

y ’∇2xxL(x∗, µ∗, λ∗)y > 0∀y 6= 0 :

[∂h(x∗)∂x

∂ga(x∗)∂x

]y = 0 (3)

allora x* e una soluzione locale stretta del problema.

Problemi di programmazione non lineare

I metodi per la soluzione di problemi di programmazione nonlinearesu cui negli ultimi anni si e maggiormente concentrata l’attivita diricerca si riconducono fondamentalmente a due categorie:

I metodi basati sulla trasformazione di un problema vincolato inun problema non vincolato o in una successione di probleminon vincolati.

I metodi basati sulla trasformazione del problema vincolato inuna successione di problemi di programmazione quadratica.

Outline




Conclusioni

Funzioni di penalita sequenziali I

Data una funzione f(x) che vogliamo minimizzare effettuiamo laminimizzazione tramite una nuova funziona F(x). Il primo passo equello di definire una funzione q(x) nel seguente modo:

q(x) =

{0 se x ∈ X

+∞, se x 6∈ X(4)

dove X e l’insieme della regione ammisibile.

e si definisce la funziona F(x) nel seguente modo:

F (x) , f (x) + q(x) (5)

Funzioni di penalita sequenziali II

E immediato verificare che la soluzione di F(x) fornisce la soluzioneal problema di f(x) ma presenta principalmente due problemi:

I l’applicazione di questo metodo solo a casi banali

I la discontinuita della funzione sulla frontiera di X

Per risolvere questo problema ci presupponiamo di costruire unasuccessione di funzioni che risultano continuamente differenziabili

Funzioni di penalita sequenziali III

Quindi definiremo una nuova funzione che sostituira q(x), chechiameremo p(x) e la definiremo nel seguente modo:

p(x) =

{0 se x ∈ X

> 0, se x 6∈ X(6)

e definiremo la nuova F (x , ε)

F (x ; ε) , f (x) +1

εp(x) ε > 0 (7)

e evidente che quando ε→ 0,F (x , ε)→ F (x)

Il termine 1εp(x) viene detto termine di penalita.

Funzioni di penalita sequenziali IV

Data una successione εk di valore di ε, strettamente decrescente etale che εk → 0 il metodo delle funzioni di penalita sequenzialiconsiste nel risolvere la successione di problemi non vincolati:

minx

F(x , εk) (8)

Per valori di ε che tendono a zero:

I si produce un malcondizionamento sulla matrice hessianaF(x,ε)

I e quindi un rallentamento di convergenza

Funzioni di penalita sequenziali V

Quindi dato un punto iniziale x e una sequenza di εk si effettuanouna serie di minimizzazioni di F(xk ,εk+1) che restituisce il puntoxk+1 nella aspettativa che xk sia una buona stima per xk+1,tuttavia questo e vero solo se εk non differisce molto da εk+1.Inoltre e possibile dimostrare che la velocita di convergenzadell’algoritmo dipende dalla velocita di convergenza della sequenzaεk.

Questo metodo viene utilizzando quando non e richiesta moltaprecisione della soluzione del problema o del soddisfacimento deivincoli. Anche per fornire una soluzione iniziale ad un altroproblema.

Outline




Conclusioni

Funzioni Lagrangiane aumentate I

Per semplicita consideriamo solo il problema con vincoli diuguaglianza.Definiamo la funzione Lagrangiana nel seguente modo:

L(x , µ) , f (x) + µ′h(x), µ ∈ Rm; (9)

dove µ viene detto moltiplicatore lagrangiano.E possibile convessificare la funzione lagrangiana con l’aggiunta diun termine di penalita:

La(x , µ, ε) , L(x , µ) +1

ε||h(x)||2 (10)

che, per ε sufficientemente piccolo ma comunque tale che 1ε sia

finito, abbia, sotto opportune ipotesi, un minimo non vincolato inx∗. La(x , µ, ε) viene chiamata funzione lagrangiana aumentata.

Funzioni Lagrangiane aumentate II

dato ε1 > 0 e µ1 ∈ Rn;while k = 1,2 . . . do

Partendo da xk-1 trova yk = La(xk, µk, εk)if yk soddisfa KKT then

poni xk = yk e STOP;else

scegli εk+1;scegli µk+1;poni xk = yk;

endk=k+1

end

Funzioni Lagrangiane aumentate III

Nell’algoritmo prima descritto bisogna scegliere come aggiornare iparametri di ε e µ

I εk di solito viene aggiornato tenendo conto dell’ammisibilita dixk

I µk viene aggiornato tramite la proprieta della funzione duale

Funzioni Lagrangiane aumentate IV

Le funzioni Lagrangiani aumentate sequenziali presentano dueprincipali vantaggi rispetto alle funzioni di penalita sequenziali:

I superano i problemi di malcondizionamento

I maggiore velocita di convergenza

Outline




Conclusioni

Funzioni di penalita esatte I

Il termine esatto, denota il fatto che e richiesta una solaminimizzazione per ottenere la soluzione del problema.

Per semplicita noi consideriamo solo le funzioni continuamentedifferenziabili.

Funzioni di penalita esatte II

L’idea delle funzioni di penalita esatte e quella di sostituire ilmoltiplicatore µ, nella funzione lagrangiana aumentata, con unafunzione µ(x), continuamente differenziabile, e con la proprietaµ(x∗) = µ∗ cosı da avere una funzione che dipende solo da x

La(x , µ(x), ε) = f (x) + µ(x)′h(x) +1

ε||h(x)||2. (11)

Funzioni di penalita esatte III

Per identificare una formula opportuna per la funzione µ(x),facciamo attenzione a:

∇f (x∗) +∂h(x∗)

∂xµ∗ = 0 (12)

da cui, nell’ipotesi di validita della condizione di regolarita in x∗, siha che:

µ∗ = −[∂h(x∗)

∂x

∂h(x∗)′

∂x

]−1∂h(x∗)

∂x∇f (x∗) (13)

l’uguaglianza sopra riportata consiglia di scegliere la funzione µ(x)nel seguente modo:

µ(x) , −[∂h(x)

∂x

∂h(x)′

∂x

]−1∂h(x)

∂x∇f (x) (14)

Funzioni di penalita esatte IV

E possibile dimostrare che questa scelta di µ(x) effettivamentefornisce una funzione di penalita esatta.

Questo metodo presenta principalmente due svantaggi al momentodella valutazione della funzione:

I calcolare le derivate prime della funzione

I invertire una matrice la cui dimensione e pari a quella deivincoli

Questi svantaggi limitano il suo campo di utilizzabilita.

Outline




Conclusioni

Funzioni Lagrangiane aumentate esatte I

Partendo dalla funzione lagrangiana aumentata descrittaprecedentemente. Per cercare di aumentare la convessita dellafunzione viene aggiunto un ulteriore termine di penalita

S(x , µ, ε) , f (x) + µ′h(x) +1

ε||h(x)||2+

η

∥∥∥∥∂g(x)

∂x∇xL(x , µ)

∥∥∥∥2 (15)

in cui l’ultimo addendo η > 0, rappresenta l’altro termine dipenalita sopra descritto.

Funzioni Lagrangiane aumentate esatte II

La funzione S(x , µ, ε) risulta :

I continuamente differenziabile rispetto a x e µ

I ε→ 0 i relativi moltiplicatori possono essere messi incorrispondenza con le coppie di valori (x , µ) che danno luogoa minimi locali di S(x , µ, ε)

La ricerca delle soluzione locali del problema puo essere effettuatarispetto a (x , µ).

Metodi di programmazione quadratica ricorsiva

I metodi di programmazione basati sulla trasformazione delproblema vincolato in una successione di problemi diprogrammazione quadratica si distinguono in due classi:

I RIQP (recursive inequality quadratic programming)

I REQP (recursive equality quadratic programming)

Anche se simili, vengono studiati separatamente per sfruttare almassimo le loro proprieta.

Outline




Conclusioni

RIQP I

I problemi che ci presupponiamo di risolvere sono della seguenteforma:

minx

f(x)

h(x) ≤ 0(16)

RIQP II

Effettuando uno sviluppo in serie di Taylor della funzione L(x , µ∗)nell’intorno di x∗, si ottiene troncando ai termini del secondoordine:

L(x , µ∗) = f (x∗) +1

2(x − x∗)′∇2

xxL(x∗, µ∗)(x − x∗) + . . . (17)

e possibile verificare che il problema

minx

f(x∗) +1

2(x − x∗)′∇2

xxL(x∗, µ∗)(x − x∗)

∂h(x∗)

∂x(x − x∗) = 0

(18)

ha una soluzione in x∗.

RIQP III

Tuttavia il moltiplicatore associato alla soluzione risulta diverso daµ∗. Per evitare questo problema bisogna aggiungere alla funzioneobbiettivo il seguente termine, ∂f (x∗)

∂x (x − x∗) e quindi avremo unproblema del seguente tipo:

minx

f(x∗) +1

2(x − x∗)′∇2

xxL(x∗, µ∗)(x − x∗) +∂h(x∗)

∂x(x − x∗)

∂h(x∗)

∂x(x − x∗) = 0

(19)che ha come soluzione x∗ e come moltiplicatore µ∗

RIQP IV

Questa osservazione suggerisce di considerare una successione disottoproblemi di programmazione quadratica del tipo

minδ

1

2δ′∇2

xxL(xk , µk)δ +∇f (xk)′δ + f (xk)

∂h(xk)

∂xδ = −h(xk)

(20)

con k indica il numero di iterazione. Invece per quanto riguarda δlo definiamo nel seguente modo: δ = x − xk dove (xk , µk) sono lestime delle soluzione all’iterazione k-esima.

E possibile dimostrare che la successione di problemi converge allasoluzione ottima.

RIQP V

Gli algoritmi RIQP presentano due caratteristiche:

I non dipendono da coefficienti di penalita.

I il numero di vincoli dei sottoproblemi da risolvere neisottoproblemi e sempre equivalente al numero di vincoli comenel problema originale.

RIQP VI

Gli algoritmi RIQP, assicurano la convergenza solo se (x0, µ0) sonoabbastanza prossimi alla soluzione ottima.E possibile allargare la regione di convergenza combinando talealgoritmo con algoritmi che godono di proprieta di convergenzaglobale.

Outline




Conclusioni

REQP I

I metodi REQP derivano dai metodi di penalita sequenziale

F (x , ε) = f (x) +1

ε||c(x)||2, (21)

dove con c(x) si indica il vettore formato dai vincoli di uguaglianzae dai vincoli di disuguaglianza non soddisfatti.Le funzioni di penalita sequenziali soffrono di problemimalcondizionamento.L’obbiettivo dei problemi REQP e quello di eliminare il problemadel malcondizionamento, quindi creare una successione di problemiben condizionati.

REQP II

Indicando con xk la stima attuale della soluzione del problema.La stima successiva e ottenuta minimizzando rispetto a δ, e con unvalore opportuno di ε, la funzione F (xk + δ, ε).Questa minimizzazione a sua volta puo essere effettuata in modoapprossimato determinando il valore di δ per cui uno sviluppo delgradiente ∇F (xk + δ, ε) troncato ai termini del primo ordine siannulla

∇F (xk , ε) +∇2F (xk , ε)δ = 0 (22)

Tale equazione per piccoli valori di ε e afflitta dalmalcondizionamento (∇2F ).

REQP III

Per risolvere il problema del malcondizionamento, bisognaeffettuare delle trasformazione del problema.

W (xk , ε) , ∇2f (xk)∑i=1

[∇c i(xk)]c i(x

k) (23)

Effettuando vari trasformazione e possibile arrivare ad un problemache fornisce la soluzione al problema originale aggirando ilproblema del malcondizionamento:

minδ

1

2δ′W (xk , ε)δ +∇f (xk)′δ

∂c(xk)

∂xδ = − ε

2u − c(xk) ≤ 0

(24)

la cui soluzione, se W e definita positiva, esiste ed e unica.

REQP IV

E possibile dimostrare la convergenza degli algoritmi REQP, maquesta risulta molto articolata e quindi non verra trattata.

Il principale vantaggio degli algoritmi REQP rispetto agli algoritmiRIQP e quello che nel sottoproblema quadratico ci possono esseresolo un sottoinsieme dei vincolo originali e questo permettel’abbattimento del carico computazionale.

Conclusioni

Abbiamo descritto vari tipologie di approcci per risolvere problemidi programmazione non lineare. Ogni metodo risulta essere piuadatto in base alla specificita del problema o all’obbiettivo che sivuole raggiungere.

Conclusioni

GRAZIE PER L’ATTENZIONE.

Metodi per la soluzione di problemi di programmazione non lineare

Education

Transcript of Metodi per la soluzione di problemi di programmazione non lineare