Schemi, Ottimizzazione

Il gradiente è dove metto le derivate parziali

presa f(x₁, ..., x_n), ∇f(x) = [^δf(x)⁄_δx1, ..., ^δf(x)⁄_δxn]̂

L'hessiano ∇²f(x) = [^δ2f(x)⁄_δx1δx1, ..., ^δ2f(x)⁄_δx1δxn; ^δ2f(x)⁄_δxnδx1, ..., ^δ2f(x)⁄_δxnδxn]

una funzione è differenziabile se è possibile farne le derivate

Teorema 1:

(dim sul quaderno) min f(x) x ∈ S , f(x) convesso, S convesso 1) preso x^* minimo locale è anche minimo globale 2) l’insieme delle soluzioni ottime X^* è convesso (cioè possono esserci 3 casi: 1 sola, soluzione è unica, 3 infinite soluzioni)

Insieme convesso:

S convesso se ∀x, y ∈ S il segmento [x, y] ∈ S

convessità stretta della funzione implica che se la soluzione ottima esiste, è unica

x ∈ S , f(x) convesso, S convesso

Funzione convessa:

presi 2 punti ∀x, y ∈ S e il segmento [x, y] = λx + (1 - λ)y, ∀λ ∈ [0,1] (diverse combinazioni di A danno diversi punti su segmento) f(x) convessa se f[λx + (1 - λ)y] ≤ λf(x) + (1 - λ)f(y) Cioè se prendo un punto sul segmento, la funzione in quel punto sta sotto il segmento unendo la funzione nel punto x e la funzione nel punto y f(x) è concava se -f(x) è convessa

Norma

è una funzione che prende un vettore x ∈ Rⁿ e mi da un numero: x ∈ Rⁿ → ‖x‖ mi permette di definire la distanza tra 2 punti: d(x, y) = ‖x - y‖ gode di alcune proprietà: ‖x‖ > 0 ∀x ∈ Rⁿ ‖x‖ = 0 ⇔ x = 0 (tutte le componenti =0) ‖λx‖ = |λ| ‖x‖ ∀x, y ∈ Rⁿ

Cercheremo di risolvere problemi del tipo min f(x) x ∈ S ⊆ Rⁿ Una soluzione è un punto di minimo globale x^* ∈ S : f(x^*) ≤ f(x), ∀x ∈ S

f(x) continua se lim_x→x0 f(x) = f(lim_x→x0 x)

f(x) ∈ C¹ funzioni continuante derivabili se f(x + d) ?⃗ f(x) a meno di un resto che va a zero al crescere di d f(x) ∈ C² funzioni doppiamente continuante derivabili se f(x + d) ≅ f(x) + ∇f(x)̂ᵀd + 1⁄2 dᵀ∇²f(x)d

B(x₀, ρ) = {x ∈ Rⁿ : ‖x - x₀‖ < ρ}

x^* ∈ S è un minimo locale se

t.c f(x^*) ≤ f(x) ∀x ∈ S ∩ B(x^*, ρ) con ρ > 0

Minimo locale se dici isolated se f(x^*) < f(x)

non sempre esiste

Se minore stretto f(x^*) < f(x)

Allora la soluzione x^* è unica

Formula generale della norma:

‖x‖_p = (∑_i=1ⁿ|x_i|^p)^1⁄p Le norme più usate sono:

norma 1 p = 1, ‖x‖₁ = ∑_i=1ⁿ|x_i| d₁(v, w) = ‖v - w‖₁ = ∑_i=1ⁿ|v_i - w_i|

norma euclidea p = 2, ‖x‖₂ = √∑_i=1ⁿ|x_i|² d(v, w) = ‖v - w‖ = √∑_i=1ⁿ|v_i - w_i|²

norma infinito p = ∞, ‖x‖_∞ = max^i=1...n|x_i| d_∞(v, w) = ‖v - w‖_∞ = max^i=1...n|v_i - w_i|

(Disuguaglianza triangolare: La lunghezza di un lato del triangolo < della somma degli altri 2)

se vuoi la distanza tra 2 punti ma con ostacoli

la norma euclidea non ha senso la norma 1 vale 5 la norma lagrangiana vale 3

Se V ha dimensione finita, tutte le norme sono EQUIVALENTI

cioè comunque si fissino due norme ‖‖.‖‖_a e ‖‖.‖‖_b, esistono due costanti C₁ e C₂ tale che C₁‖v‖_b ≤ ‖v‖_a ≤ C₂‖v‖_b ∀v ∈ V Le distanze indotte dalle norme sono equivalenti

Convessità

come dire se una funzione è convessa

f(x) convessa, f(x) ∈ C¹ → ∀x, y ∈ Rⁿ si ha f(y) ≥ f(x) + ∇f(x)(y-x)

Fare il gradiente vuol dire fare la tg, se la funzione è convessa la tg sta sempre al di sotto della funzione

f(x) convessa, f(x) ∈ C² ⇔ ∇²f(x) ≽ 0, ∀x ∈ S

L’hessiano calcolato in un qualsiasi punto è semidefinito positivo

basta trovare un punto in cui l’hessiano è <0 per dire che la funzione non è convessa

Condizione necessaria affinché una funzione sia strettamente convessa è che ∇²f(x) > 0, ∀x ∈ S

Se la funzione è quadratica, ovvero:

q(x) = ₁/²x^TQx + c^Tx + c

∇q(x) = Qx + c ∇²q(x) = Q

L’hessiano non dipende dal punto quindi la condizione diventa anche sufficiente, Q ≻ 0

come dire se un insieme è convesso

Un insieme ammissibile è definito come l’intersezione di + vincoli, ogni vincolo è una funzione, se tutte le funzioni sono convesse ⇒ anche l’insieme sarà convesso

Teo 2: (dim sul quaderno)

g_i(x)convexse ⇒ S = {g_i(x) ≤ 0}_convex

OSS:

• Intersezione di insiemi convessi è ancora convessa
• Vincolo di uguaglianza e convesso e vincolo lineare: g(x) = c^Tx + d ⇒ ∇g(x) = 0,
• vincolo sia concavo che convesso ∑_iα_if_i(x) se α_i ≥ 0, f_i(x) convessa
• f(x) = max {f_i(x)} con f_i(x) convesse è convessa

Semidefinita positiva ≽

Q ∈ R^nxn

Q = Q^T ⇒ y^TQy ≥ 0, ∀y ∈ Rⁿ

Q ≠ 0

Definita positiva ≻

Q ∈ R^nxn

Q = Q^T ⇒ y^TQy > 0, ∀y ∈ Rⁿ

Q > 0

3. Concetto matrice diagonale dominante:

se q_ii ≥ ∑ⁿ_j=1|q_ij| ⇒ Q ≽ 0

se q_ii = 0,∃q_ij ≠ 0 ⇒ Q ≠ 0

2. Criterio dei minori di Nord-Ovest

Q = \(\begin{bmatrix} a & b \\ d & e \end{bmatrix}\) >0 se:

a > 0, det \(\begin{bmatrix} a & b \\ d & e \end{bmatrix}\) > 0, det Q > 0

Q ≽ 0 se tutti i minori hanno determinante ≥ 0

1. Guardo gli autovalori:

Q ≽ 0 ⇔ λ_i ≥ 0, ∀i = 1 ... n

Q ≻ 0 ⇔ λ_i > 0, ∀i = 1 ... n

λ ∈ R è autovalore se ∃ autovettore u_i: Qu_i = λu_i, ∀i = 1 ... n

λ ∈ R sono le soluzioni dell’eq:

det(Q - λI) = 0

SE NELL'ENUNCIATO RIMUOVO LA COMPATTEZZA DELL'INSIEME

Sto risolvendo un problema min f(x), f ∈ C¹,

uso il metodo x_k+1 = x_k + α_kd_k

d_k ≠ 0 se ∇f(x_k) ≠ 0

Ho le stesse ipotesi

CONCLUSIONI:

• ∃ indice v t. c. x_v ∈ Ω (convergenza finita)
• Oppure
• L'algoritmo genera una successione infinita {x_k} t. c.:
• lim_k→∞ f(x_k) = −∞ (problema non ha soluzione)
• Oppure f(x_k) è limitata inferiormente e in questo caso:
• {f(x_k)} converge
• lim_k→∞ ∇f(x_k) = 0 (convergenza forte)
• Ogni eventuale punto di accumulazione x̄ di {x_k} ∈ L₀ e soddisfa la condizione ∇f(x̄) = 0 (non è però garantita l’esistenza dei punti di accumulazione)

INIZIO:

sto risolvendo un problema min f(x), f ∈ C¹,

uso il metodo x_k+1 = x_k + α_kd_k

L(x₀) ∈ ℝⁿ, {x | f(x) ≤ f(x₀)} compatto

d_k ≠ 0 se ∇f(x_k) ≠ 0

Teo: C.S. di convergenza globale

CONCLUSIONI:

• ∃ indice v t. c. x_v ∈ Ω (convergenza finita)
• Oppure
• L’algoritmo genera una successione infinita {x_k} t. c.:
• a) x_k ∈ L₀ ∀k e {x_k} ammette punti di accumulazione
• b) {f(x_k)} converge (la successione dei valori della funzione)
• c) lim_k→∞ ∇f(x_k) = 0 (convergenza forte)
• d) Tutti i punti di accumulazione della sequenza sono stazionari

DIMOSTRO d)

∄ punto di accumulazione di {x_k} se

∃ x̄ insieme infinito di indici t. c.: lim_k→∞ x_ki = x̄

Dal punto c) lim_k→∞ ∇f(x_k) = 0

quindi lim_k→∞ x_ki = ∇f(x_i) = ∇f(x̄)

Siccome f ∈ C¹ e continua e differenziabile ∇f(x̄) = 0 ∴ x̄ punto di accumulazione è stazionario

DIMOSTRO c)

Dall’hp 3 [∇f(x_k)]^Td_k|d_k| ≥ σ(‖∇f(x_k)‖) ≥ 0 (perché la norma è ≥ 0 e per la definizione di funzione di sforzamento σ: [0, ∞) )

Dall’hp 2 lim_k→∞ [∇f(x_k)]^Td_k|d_k| = 0

Allora lim σ(‖∇f(x_k)‖) = 0 perché compreso tra 2 valori che vanno a 0

Per la definizione di funzione di sforzamento lim_k→∞ ‖∇f(x_k)‖ = 0

Dalle proprietà della norma, la norma di qualcosa va a 0 se il qualcosa va a 0 ∴ lim_k→∞ ‖∇f(x_k)‖ = 0

DIMOSTRO a)

Per l’hp 1, f(x_k+1) ≤ f(x_k) ≤ ... ≤ f(x₁) ≤ f(x₀)

Siccome L₀ ∈ ℝⁿ: f(x_κ) < f(x₀) [κ] ammette punti di accumulazione

Siccome L₀ ∈ compatto {x_k} ammette punti di accumulazione

DIMOSTRO b)

{f(x_k)} è monotona non crescente dall’hp 1

Da a) x_k ∈ L₀ ∀k e f ∈ C¹ + L₀ è compatto ∃ un lim_K→∞ f(x_k) (la funzione è limitata inferiormente)

Data una funzione limitata inferiormente e continua, questa converge