Ottimizzazione Non Lineare

Ottimizzazione Non Lineare

G. Liuzzi¹

Mercoled`ı 19 Dicembre 2018

logo.pdf

Problemi vincolati

Problema vincolato nonlineare generale minx f (x ) c.v h(x ) = 0

g (x ) ≤ 0

(P0)

con F insieme ammissibile di (P0)

Ottimizzazione Non Lineare G. Liuzzi

Definizione

Teoricamente `e possibile definire

q∞(x ) =

 0 se x ∈ F +∞ se x 6∈ F e quindi

P∞(x ) = f (x ) + q∞(x )

`E evidente che:

risolvere il problema min P∞(x ) fornisce soluzioni del problema (P₀).

minimizzare P∞(x ) `e (o pu`o essere) molto “complicato”

logo.pdf

Definizione

Anzich´e q∞(x ), definiamo

q(x ) =

 0 se x ∈ F

> 0 se x 6∈ F e quindi

P(x ) = f (x ) + 1

q(x ) N.B.:

se f (x ) e q(x ) sono cont. differenziabili, allora anche P(x ) lo

` e

per ogni x ∈ Rⁿ, lim

→0P(x ) = P∞(x )

Ottimizzazione Non Lineare G. Liuzzi

Espressione di q(x)

Il termine q(x ) deve “penalizzare con continuit`a” l’eventuale inammissibilit`a di x

P.es., con riferimento a (P0),

q(x ) =

p

X

i =1

[h_i(x )]²+

m

X

i =1

[max{0, g_i(x )}]²

per nessun valore di  > 0, min P(x ) `e equivalente a (P0) per ogni valore di  > 0, una min. non vincolata di P(x ) produce (in genere) un punto x<sup>∗</sup>6∈ F , cio`e q(x^∗) > 0

logo.pdf

Algoritmo di soluzione

Algoritmo SEQPEN

Input: maxit, τ > 0, k = 0, 0> 0 for k = 0, 1, . . . , maxit

Trova una soluzione (x (_k)) del problema

x ∈RminⁿPk(x ). (2) if q(x (_k)) ≤ τ then STOP

_k+1 = _k/2 endfor

Output: una sol. approssimata x^∗= x (k)

Ottimizzazione Non Lineare G. Liuzzi

Propriet` a di monotonicit` a

Teorema

Siano soddisfatte le ipotesi seguenti:

esiste x^∗∈ F soluzione globale del problema vincolato;

per ogni k, la funzione P_k(x ) ammette minimo globale x^k. Allora,

1 Pk(xk) ≤ f (x^∗);

2 q(x^k) ≥ q(x^k+1);

3 f (x^k) ≤ f (x^k+1);

4 P_k(x^k) ≤ P_k+1(x^k+1).

logo.pdf

Propriet` a di monotonicit` a – dim.

Dim.

Pk(x^k) = min

x ∈Rⁿf (x )+q(x )/k ≤ min

x ∈Ff (x )+q(x )/k = min

x ∈Ff (x ) = f (x^∗).

che prova la (1).

P_k(x^k) ≤ P_k(x^k+1) Pk+1(x^k+1) ≤ P_k+1(x^k) Ovvero

f (x^k) + q(x^k)/_k ≤ f (x^k+1) + q(x^k+1)/_k f (x^k+1) + q(x^k+1)/_k+1 ≤ f (x^k) + q(x^k)/_k+1

f (x^k) + q(x^k)/k ≤ f (x^k+1) + q(x^k+1)/k

−f (x^k) − q(x^k)/_k+1 ≤ −f (x^k+1) − q(x^k+1)/_k+1

Ottimizzazione Non Lineare G. Liuzzi

Propriet` a di monotonicit` a – dim. (segue)

da cui segue

q(x^k)(1/k− 1/_k+1) ≤ q(x^k+1)(1/k − 1/_k+1) tenendo conto del fatto che _k+1 < _k

q(x^k+1) ≤ q(x^k) che prova la (2). Ora, ricordando che

f (x^k) − f (x^k+1) ≤ (q(x^k+1) − q(x^k))/k ≤ 0 che prova la (3). La (4) segue da

f (x^k)+q(x^k)/_k ≤ f (x^k+1)+q(x^k+1)/_k ≤ f (x^k+1)+q(x^k+1)/_k+1

logo.pdf

Propriet` a di convergenza

Teorema

Siano soddisfatte le ipotesi seguenti:

esiste x^∗∈ F soluzione globale del problema vincolato;

per ogni k, la funzione Pk(x ) ammette minimo globale x^k; tutti i punti x^k rimangono in un insieme compatto D.

Allora,

1 lim_k→∞q(x^k) = 0;

2 limk→∞f (x^k) = f (x^∗);

3 limk→∞Pk(x^k) = f (x^∗);

4 ogni punto di accumulazione di {x^k} `e soluzione globale del problema vincolato;

5 limk→∞q(x^k)k = 0;

Ottimizzazione Non Lineare G. Liuzzi

Propriet` a di convergenza – dim.

Dim. Sappiamo che

f (x^∗) ≥ P_k(x^k) = f (x^k) + q(x^k)/_k ≥ f (x⁰) + q(x^k)/_k ovvero

f (x^∗) − f (x⁰) ≥ q(x^k)/k. Quando k → ∞, deve risultare

k→∞lim q(x^k) = 0

(altrimenti si avrebbe un assurdo) il che prova la (1).

Sia ora ¯x un qualunque punto di accumulazione di {x^k} ⊂ D compatto. Risulta intanto che q(¯x ) = 0, cio`e che ¯x ∈ F .

logo.pdf

Propriet` a di convergenza – dim. (segue)

f (x^∗) ≥ Pk(x^k) ≥ f (x^k)

Quindi, le successioni {Pk(x^k)} e {f (x^k)} sono monotone non decrescenti e limitate superiormente, quindi ammettono limite.

f (x^∗) ≥ lim

k→∞P_k(x^k) = lim

k→∞f (x^k) + q(x^k)/_k f (x^∗) ≥ lim

k→∞Pk(x^k) = f (¯x ) + lim

k→∞q(x^k)/k ≥ f (¯x ) ≥ f (x^∗).

Da qui segue che valgono (2) e (3). Inoltre, che f (¯x ) = f (x^∗), cio`e che ¯x `e soluzione globale del problema vincolato e inoltre che vale

la (5). 

Ottimizzazione Non Lineare G. Liuzzi

logo.pdf

Esempio 1

Consideriamo il seguente problema vincolato (banale) min x²

x ≥ 1

Ammete x^∗ = 1 come unico punto di minimo globale La funzione di penalit`a esterna `e:

P(x ) = x²+1

max{0, 1 − x }² Grafici di P_(x ) ( = 1, 0.5, 0.2, 0.1, 0.05)

0.5 1 1.5 2

Χ 1.2

1.4

P
^Χ;Ε

Ε0.5

Ε0.2

Ε0.1 Ε0.05

Ottimizzazione Non Lineare G. Liuzzi

logo.pdf

Esempio 2

Consideriamo il seguente problema vincolato (banale) min −x⁴

x = 1

Ammete (ovviamente) x^∗= 1 come unico punto di minimo globale La funzione di penalit`a esterna `e:

P(x ) = −x⁴+1

(x − 1)² Grafici di P(x ) ( = 1, 0.5, 0.2, 0.1, 0.05)

3
2
1 1 2 3

Χ

10 10 20 30

P
^Χ;Ε

Ε1 Ε0.5

Ε0.2 Ε0.1

Ε0.05

Ottimizzazione Non Lineare G. Liuzzi