Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
Ottimizzazione di sistemi complessi
Prof. Marco Sciandrone
Esame 2 Parziali
- I Lunedì 20 Aprile
- II Martedì 9 Giugno
Solo orale
Def. minx∈S f(x)
- f: ℝn → ℝ Funzione Obiettivo
- S ⊆ ℝn Insieme Ammissibile
Complessità
- (melevato) → Metodi di Decomposizione
minx∈S {f1(x), f2(x), ..., fm(x)}
Ottimizzazione Multiobiettivo
- Prima decisione → x ∈ ℝn
- Seconda Decisione → y ∈ ℝm
- Decisione 1 f1(x,y)
- Decisione 2 f2(x,y)
Giochi ed Equilibri di Nash
Ottimizzazione Sparsa
- minx∈X f(x)
|| x ||0 = Norma 0 = n. di componenti diversi da 0 di x
|| x ||0 ≤ s
Vincolo di Sparsità
Programmazione Matematica Mista
DEFINIZIONI:
min f(x)
x < X
Problema d'ottimizzazione
Risolvere un prob. d'ottimizzazione significa trovare un
MINIMO GLOBALE
x < X f(x) < f(x) x < X
MINIMO LOCALE
x < x0 x < B(x0,p) = {x < Rm: ||x-x0|| < p }
f(x) < f(x0) ∀ x < X ∩ B(x0,p)
Concetto tra minimi locali e globali:
- Convessità di un insieme X
- Convessità di una funzione su X
INSIEME CONVESSO
X < Rm è convesso se
∀ x, y < X ⇒ (1- λ) x + λ y < X ∀ λ < [0,1]
X = [x1, x2]
0 < λ < 1
FUNZIONE CONVESSA SU INSIEME CONVESSO X
f è convessa su X se
∀ x, y < X ⇒ f((1-λ) x + λ y) < (1-λ) f(x) + λ f(y) ∀ λ < [0,1]
(Funzione sotto il segmento (ordi))
Prop: (Corrispondenza di minimi locali e globali: caso convesso)
- X convesso ⇒ ogni minimo locale
- f convessa su x ⇒ è anche globale
Condizioni di Ottimalità x Convesso
Prop: C.N. Ottimo Locale
x̄ x minimo locale
Allora ∇f(x̄)T(x-x̄) ≥ 0 ∀ x ∈ X
Dem.
Assurdo x̄ non tc. ∃ y ∈ X y≠x̄
∇f(x̄)T(y-x̄) < 0
x - x̄ direz. discesa
assurdo
Prop: C.N.S. Ottimo Globale
f convessa
x̄ è minimo globale se e solo se ∇f(x̄)T(x-x̄) ≥ 0 ∀ x ∈ X
Dem.
C.N. se
∇f(x̄)T(x-x̄) ≥ 0 ∀ x ∈ X
f convessa
→ ∀ x ∈ X
f(x) ≥ f(x̄) + ∇f(x̄)T(x-x̄) ≥ f(x̄)
≥ 0
Condizioni di Ottimalità Caso Non Vincolato (X = ℝn)
Prop: C.N.
x̄ minimo locale allora ∃ direz. di discesa in x̄
Prop.
x̄ minimo locale
∇f(x̄) = 0
Prop.
x̄ minimo locale allora ∇f(x̄) = 0
Dem:
x̄ minimo locale
per assurdo ∇f(x̄) ≠ 0, d = -∇f(x̄) → ≠ direz. di discesa in x̄ → assurdo
Prop: C.N.S Minimo Globale
f convessa
x̄ è minimo globale se e solo se ∇f(x̄) = 0
Prop: C.N minimo locale II ordine
x̄ minimo locale allora
- ∇f(x̄) = 0
- ∇2f(x̄) semi-definita positiva
Esempio
f(x) = 1/2 xTQx + cTx Q sym simmetrico
C.N. affinché x* min f(x) ammettava sol.
x ∈ ℝm
Q semi-definita positiva → C.N. → 0 non ammette sol. o infinite sol.
Q definita positiva → C.S. ammette unica sol.
Il caso di problemi con vincoli di simplest.
Considero min f(x)
I = x -> x > 0
Prop C.N.
Le x c Rn minimo locale del problema.
Allora
I x = b x > 0 x con h.
∂ f(x) dx
Le g implica che le tentative delle componenti strettamente.
Dim
L(xi, μi) = f(x) + l (h x - b) - μi b
∂ L(x, λ, μ) ∂ f(x)∂ x xj + λ μi = 0
Di complemento st. se x > 0 -> μi = 0
-> x3 > 0 -> ∂ L(x) ∂ x = - λ
-> x x < 0 -> ∂ f(x) ∂ x = - λ + μi x > λ
Metodo dell'ascendente
min f(x) ← ottimo non vincolato
x ∈ ℜn xk + λk dk (xk direz del grad)
deteministico ó di Armijo
Metodo globalmente convergente → qualunque sia x0, k
seq generata tale che lim f(xk) = 0
m → ∞
Metodo del proietto proiettato
min f(x) ← ott vincolato
x ∈ X X convesso compatto non vuoto
a, chiuso, e limitato.
Def Proiezione su insieme convesso
Sia X ⊆ ℜn insieme convesso chiuso e non vuoto,
x ∈ ℜn un punto esterno e ||... esterno dall.
Considero min { || ... y ||, y ∈ X } → Determinare il punto in X → distanza minima da x
Funzione diott. obiettivo convesso → s ... sol,
norma euclidea ... &/coact; convesso → sol ottima unica
Definizione: Proiezione di x su X la soluzione p(x)
del problema min { || x-y ||, y ∈ X }
s.s.t. (p(x) ∈ X → il punto che tottiscle (dir) p(x),11,i||11 y ∈ X
N.B. In generale la proiezione conclude la soluzione di un problema di ottimizzazione
... caso la proezione puo essere effettuata in modo analitico
es. Proiezione su un insieme definito da vincoli di box.
Considero x = { x ∈ ℜ, R ≤ x ≤ a }
sia x ∈ X e proiez. di x su X ye ha componente
yi = { xi, xi
...
Algoritmo di Gauss-Seidel
Det: punto iniziale x0 = (x0, ... xm) ∈ ℝn
For k = 0,1
Calcola xk+11 ∈ Arg minξ ∈ ℝn f (ξ, x2k, ... ξ, ... xmk)
End For
Osservazioni:
I) Richiede di determinare punti di stima flessi
II) Garentire convergenze globale ma non è banale
Convergenza del metodo Gauss-Seidel
Proprietà di convergenza globale possono essere stabilite:
- sotto ipotesi di convessità delle f. da
- t. di f. strict convessi per componenti
- senza ipotesi di convessità nel caso particolare di m = 2 bloc
Se m ≥ 2, modifica il metodo di "two proximal point" per garantirla convergenze senza ipotesi di convessità.
Metodo di Gauss-Seidel a due blocchi
Dividi p-i-iz x = (x1, x2) ∈ ℝm
For k = 0,1
Calcola xk+11 ∈ Arg minξ ∈ ℝn f (ξ, x2k)
Calcola xk+12 ∈ Arg minξ ∈ ℝm-1 fϕ (x1k+1, ξ)
Poni xk+1 = (x1k+1, x2k+1)
End For
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
