In generale x = (x 1 , x 2 , . . . , x n ) q(x) =

di grado 2 in n variabili.

In generale x = (x 1 , x 2 , . . . , x n ) q(x) =

n

X

i,j=1

a i,j x i x j =

n

X

i=1

a i,i x ² _i +

n

X

i6=j

a i,j x i x j

Scritta cos`ı, quanti sono i coefficienti di una forma quadratica in n variabili

? Sono n ² .

A = (a _i,j ) In forma di prodotto scalare

q(x) = Ax · x In forma matriciale

q(x) = x ^T Ax

Esercizi di riscrittura dalla forma alla matrice associata e viceversa.

q(x 1 , x 2 , x 3 ) = x ² ₁ + 3x ² ₂ + x ² ₃ − 24x ₁ x 2 − 6x ₁ x 3 + 2x 2 x 3

La matrice associata ` e





1 −12 −3

−12 3 1

−3 1 1





A una forma quadratica resta associata una matrice simmetrica.

Come riconoscere se la forma quadratica ( o la matrice associata) ` e definita positiva ossia

q(x ₁ , x ₂ , x ₃ , . . . x _n ) =

n

X

i,j=1

a _i,j x _i x _j ≥ 0, ∀x 6= 0 soluzione n. 1 (calcolo degli autovalori)

D(λ) =      

λ − 1 −12 −3

−12 λ − 3 1

−3 1 λ − 1

      D(λ) = 0,

(λ − 1)    

λ − 3 1 1 λ − 1

   

+ 12    

−12 1

−3 λ − 1    

− 3    

−12 λ − 3

−3 1

   

= 0

(λ − 1)((λ − 3)(λ − 1) − 1) − 144(λ − 1) + 36 + 36 − 9(λ − 3) = (λ − 1)(λ ² − 4λ + 3) − λ + 1 − 144λ + 144 + 72 − 9λ + 27 = λ ³ − 4λ ² + 3λ − λ ² + 4λ − 3 − λ + 1 − 144λ + 144 + 72 − 9λ + 27

λ ³ − 5λ ² − 147λ + 241 = 0 Osserviamo che

1

Tutte le soluzioni sono reali (due soluzioni sono positive e una negativa).

L’equazione di terzo grado per il Teorema Fondamentale dell’Algebra, ha tre soluzioni. L’equazione di terzo grado ha sempre almeno una radice reale, nel caso in esame sappiamo che tutte le soluzioni sono reali. Possiamo avere informazioni sul segno senza calcolarle?

Se r, s e t sono le sue tre radici, l’equazione si annulla se x = r o se x = s o sex = t, cio` e dovr` a essere:

(x – r) (x – s) (x – t) = 0 Si ottiene:

x ³ –(r + s + t)x ² + (rs + rt + st)x–rst = 0

Da cui si trova r + s + t = 5 e rst = −241. Almeno una dovr` a essere negativa, non non tutte e tre perch´ e la somma ` e positiva.

Data l’equazione di terzo grado (Tartaglia, Cardano).

x ³ + bx ² + cx + d = 0

la trasformiamo in un’equazione priva del termine di secondo grado x = y–b/3

(y–b/3) ³ + b(y–b/3) ² + c(y–b/3) + d = 0

(y ³ –3(b/3)y ² + 3(b ² /9)y–b ³ /27) + b(y ² –2(b/3)y + b ² /9) + cy–bc/3 + d = 0

y ³ –by ² + (b ² /3)y–b ³ /27 + by ² –(2b ² /3)y + b ³ /9 + cy–bc/3 + d = 0 y ³ + (−b ² /3 + c)y + 2b ³ /27–bc/3 + d = 0

p = −b ² /3 + c q = 2b ³ /27–bc/3 + d y ³ + py + q = 0

Introduciamo u e v

y = u + v p = −3uv

(u + v) ³ − 3uv(u + v) + q = 0 Da cui

u ³ + v ³ = −q u ³ v ³ = −p ³ /27 Risolviamo

z ³ + qz − p ³ /27 = 0 z 1,2 = −q ± pp ² + 4p ³ /27

2

Consideriamo un caso particolare : assumiamo

p ² + 4p ³ /27 ≥ 0

Si ottiene una radice reale

y = √

³

z ₁ + √

³

z ₂ . Dividiamo poi il polinomio per x − y.

Fare per esercizio il caso

p ² + 4p ³ /27 < 0,

e mostrare che anche in questo caso una radice ´ e reale.

0.1. Forme quadratiche in R ² e la matrice Hessiana. Una matrice Q si dice non negativa (rispettivamente, non positiva ) se la forma z ^T Qz (z = (x, y) is semidefinita positiva (rispettivamente negativa) cio` e se

z ^T Qz =

2

X

i,j=1

q i,j x i y j ≥ 0

(rispettivamente, z ^T Qz ≤ 0, ) ∀(x, y) ∈ R ² .

Una matrice Q si dice positiva (rispettivamente, negativa) se la forma z ^T Qz

`

e positiva (rispettivamente, negativa) z ^T Qz =

2

X

i,j=1

q _i,j x _i y _j 0 (z ^T Qz < 0)∀(x, y) ∈ R ² , x, y 6= 0.

Un esempio di matrice positiva ` e data da

(0.1) I =

 1 0 0 1



poich` e x <sup>2</sup> + y <sup>2</sup> > 0. Un esempio di matrice non negativa ` e data da

(0.2) Q =

 2 0 0 0

 mentre una matrice indefinita ` e data da

(0.3) Q =

 1 0 0 −2



Se restringiamo l’analisi alle matrici 2 × 2 allora abbiamo il seguente Teorema 0.1. Sia

(0.4) Q =

 q 11 q 12

q ₂₁ q ₂₂

 una matrice simmetrica.

|Q| = detQ = q ₁₁ q ₂₂ − (q ₁₂ ) ² . Allora

|Q| > 0 e q ₁₁ > 0, =⇒ Q > 0

|Q| > 0 e q ₁₁ < 0, =⇒ Q < 0

Se detQ < 0, allora Q ` e indefinita.

Proof. Data la forma quadratica

ax ² ₁ + 2bx 1 x 2 + cx ² ₂ , essa pu` o essere equivalentemente scritta

a

 x ₁ + b

a x ₂

 2

+ ac − b ² a x ² ₂ ,

da questa formula si evince chiaramente il risultato.  Consideriamo le forme quadratiche nel caso di dimensione due associate alla matrice hessiana. Ricordiamo che la matrice hessiana, o matrice di Hesse, nel caso n = 2 ` e la matrice quadrata 2 × 2 delle derivate parziali seconde della funzione.

(Hf ) _i,j = ∂ ² f

∂x _i ∂x _j

ove il simbolo ∂x i ∂x j indica che prima deriviamo rispetto a x i e poi rispetto a x j

1. Regressione lineare Minimi quadrati

Dati n > 2 di R ² con ascisse distinte tra loro si vuole determinare la retta che minimizza l’errore quadratico totale

F (a ₀ , a ₁ ) =

n

X

j=1

(a ₁ x _j + a ₀ − y _j ) ²

Funzione di due variabili di cui possiamo calcolare i punti critici ( ∂F

∂a

0

= 2 P n

j=1 (a ₁ x _j + a ₀ − y _j ) = 0

∂F

∂a

1

= 2 P n

j=1 x j (a 1 x j + a 0 − y _j ) = 0 Scritto sotto forma di sistema

( a 0 n + a 1 P n

j=1 x j
= P ⁿ _j=1 y j

a ₀ P n

j=1 x _j
+ a ₁ P n

j=1 x ² _j
= P ⁿ _j=1 x _j y _j D =

   

n P n

j=1 x _j P _n

j=1 x _j P _n

j=1 x ² _j    

= n

n

X

j=1

x ² _j
−

n

X

j=1

x j

2

Esercizio 1.1. Dimostrare, assumendo x _j distinti tra loro al variare di j = 1, . . . ,

n

X

j=1

x j

2

< n

n

X

j=1

x ² _j , n ∈ N, n ≥ 2

Proof. La disuguaglianza ` e verificata per n = 2. Assumendo vera la disuguaglianza al passo n dobbiamo dimostare

n+1

X

j=1

x j

2

< (n + 1)

n+1

X

j=1

x ² _j .

n+1

X

j=1

x j

2

=

n

X

j=1

x j + x n+1

2

n

X

j=1

x j

2

+ x ² _n+1 + 2x n+1 n

X

j=1

x j <

n

n

X

j=1

x ² _j + x ² _n+1 + 2x n+1 n

X

j=1

x j =

(n + 1)

n

X

j=1

x ² _j + nx ² _n+1 + x ² _n+1 − x ² _n+1 + . . . x ² _n+1

| {z }

n volte

−

n

X

j=1

x ² _j + 2x n+1 n

X

j=1

x j =

(n + 1)

n+1

X

j=1

x ² _j −

n

X

j=1

x j − x _n+1 ) ² < (n + 1)

n+1

X

j=1

x ² _j .

 Calcolo delle soluzioni

Un sistema con 2 equazioni e 2 incognite ha un’unica soluzione se e solo se il determinante D ` e diverso da zero. In questo caso, la soluzione ` e data da:

a ₀ =    

P n

j=1 y _j P n j=1 x _j P n

j=1 x j y j P n j=1 x ² _j

    

  

n P n

j=1 x _j P n

j=1 x _j P n j=1 x ² _j

   

a ₁ =    

n P n

j=1 y _j P n

j=1 x j P n j=1 x j y j

    

  

n P n

j=1 x _j P _n

j=1 x _j P _n

j=1 x ² _j    

Gruppi di lavoro per impostazione problema. La dieta peso altezza, tariffa bus percorso prezzo, planning: consumi/ aumento salariale.

Riflessioni sulla validit` a del metodo. Regressione polinomiale

2. Elementi di topologia di R ^m Ricordiamo che per x, y ∈ R valgono le seguenti propriet´a

• |x| ≥ 0

• x 6= 0 se e solo se |x| > 0

• |x| = | − x|

• |xy| = |x||y|

• |x + y| ≤ |x| + |y|

• ||x| − |y|| ≤ |x − y|

2.1. Norma. Dato un punto x = (x ₁ , . . . , x _m ) ∈ R ^m si definisce la norma euclidea di x

kxk ₂ = x ² ₁ + · · · + x ² _m
1/2

.

∀x, y, z ∈ R ^m e λ ∈ R, valgono le propriet`a:

• kxk ≥ 0,

• kxk = 0 ⇐⇒ x = 0,

• kλxk = |λ| · kxk,

• kx + yk ≤ kxk + kyk.

2.2. Il prodotto scalare. Il prodotto scalare in R ^m ` e un numero reale dato da

x · y = x ₁ y ₁ + · · · + x _m y _m per ogni x,y,z ∈ R ^N λ ∈ R x · y = y · x, (x + y) · z = x · z + y · z, λ(x · y) = λx · y.

(x, x) = kxk ²

Dato p > 1, p ∈ R diciamo coniugato di p il numero reale q tale che 1

p + 1 q = 1.

Teorema 2.1. Disuguaglianza di Young (esponenti reali): dati due numeri reali positivi a e b, e dati p, q numeri reali coniugati, si ha

ab ≤ a ^p p + b ^q

q Proof. Fissiamo b > 0

f : [0, +∞) → R f (t) = t ^p

p + b ^q q b ^q − tb

t→+∞ lim t ^p

p p + b ^q

q − tb = +∞

f (0) = b ^q q > 0 f ⁰ (t) = t ^p−1 − b t ^p−1 = b ⇐⇒ t = b

^p−11

f ⁰⁰ (b

^p−11

) > 0

Punto di minimo relativo che ` e anche punto di minimo assoluto f (b

^p−11

) = b

^p−1p

p + b ^q

q b ^q − b

^p−11

b =  1 p + 1

q − 1

 b ^q = 0 Allora risulta per ogni numero reale a ≥ 0

f (a) ≥ 0, ossia

ab ≤ 1 p a ^p + 1

q b ^q

 Teorema 2.2 (disuguaglianza di H¨ older). Per p, q esponenti coniugati e p, q ∈ [1, +∞) e ∀x, y ∈ R ^m abbiamo

(2.1) |x · y| ≤ kxk _p kyk _q .

Si fissi

a _i = |x _i |

kxk _p , b _i = |y _i | kyk _q Dalla disuguaglianza di Young

a i b i ≤ 1 p

|x _i | ^p kxk ^p _p + 1

q

|y _i | ^q kyk ^q _q Sommando

m

X

i=1

a i b i ≤ 1 p

P m i=1 |x _i | ^p

kxk ^p _p + 1 q

P m i=1 |y _i | ^q

kyk ^q _q = 1 Da cui si evince

m

X

i=1

a _i b _i =

m

X

i=1

|x _i | kxk _p

|y _i | kyk _q ≤ 1 e la disuguaglianza di H¨ older segue

(2.2) |x · y| ≤ kxk _p kyk _q .

Teorema 2.3 ( Disuguaglianza Minkowski ). Per p ∈ [1, +∞) e ∀ x, y ∈ R ^m abbiamo

(2.3) kx + yk _p ≤ kxk _p + kyk _p .

|x _i + y i | ^p = |x i + y i | ^p−1 |x _i + y i | ≤

|x _i + y _i | ^p−1 (|x _i | + |y _i |)

m

X

i=1

|x _i + y _i | ^p ≤

m

X

i=1

|x _i + y _i | ^p−1 |x _i | +

m

X

i=1

|x _i + y _i | ^p−1 |y _i |

Si ha

m

X

i=1

|x _i + y _i | ^p−1 |x _i | ≤ kxk _p k(x + y) ^(p−1) k _q = kxk _p

 m

X

i=1

|x _i + y _i | ^(p−1)q



¹_q

m

X

i=1

|x _i + y _i | ^p−1 |y _i | ≤ kyk _p k(x + y) ^(p−1) k _q = kyk _p

 m

X

i=1

|x _i + y _i | ^(p−1)q



¹_q

Quindi da (p − 1)q = p

kx + yk ^p _p ≤ kx + yk ^p−1 _p (kxk p + kyk p )

e dividendo per kx + yk ^p−1 p (assumendo non nullo) si ottiene la Disug- uaglianza di Minkowski

kx + yk _p ≤ kxk _p + kyk p . Esempio 2.4.

• La formula

kxk ₁ = |x ₁ | + · · · + |x _m | , x = (x ₁ , . . . , x _m ) ∈ R ^m definisce una norma su R ^m .

• La formula

kxk _∞ = max {|x ₁ | , . . . , |x _m |}

definisce una norma su R ^m .

Due norme kxk _a kxk _b si dicono equivalenti se esistono due costanti m e M tali che

m kxk _b ≤ kxk _a ≤ M kxk _b Vale la relazione

p→+∞ lim kxk _p = kxk _∞

Sfruttando la relazione tra le norme, valida per ogni p ≥ 1 kxk _∞ ≤ kxk _p ≤ m

^1p

kxk _∞

si ha che le norme p per p ≥ 1 sono tra loro equivalenti.

Definizione 2.5. Definiamo la distanza tra due punti di R ^m tramite la formula

d(x, y) := kx − yk

d(x, y) := kx − yk = v u u t

m

X

i=1

(x i − y _i ) ²

• d(x, y) ≥ 0

• d(x, y) = 0 ⇐⇒ x = y

• d(x, y) = d(y, x)

• d(x, y) ≤ d(x, z) + d(z, y)

La base canonica in R ^N ` e data da e ¹ = (1, 0, . . . , 0), e 2 = (0, 1, . . . , 0), e ^m = (0, 0, . . . , 1).

e ^j = (0, . . . 1, 0 . . . 0) e ^k = (0, . . . 0, 1 . . . 0).

d(e ^j , e ^k ) = √

2 j 6= k 2.3. Interno, Esterno, Frontiera di un insieme.

Definizione 2.6. Sia a ∈ R ^m e r > 0 un numero reale. B _r (a) di centro a e raggio r per

B _r (a) := {x ∈ R ^m : kx − ak < r} .

• Per m = 1 troviamo gli intervalli ]a − r, a + r[.

• Per m = 2 troviamo il cerchio privato dei suoi punti frontiera

• Per m = 3 troviamo la palla privata dei suoi punti frontiera Sia A ⊂ R ^m e x ∈ R ^m .

• x ` e un punto interno di A se esiste r > 0 tale B _r (x) ⊂ A.

• x ` e un punto esterno di A se esiste r > 0 tale che B _r (x) ⊂ R ^m \ A.

• x ` e un punto frontiera di A se B r (x) incontra A e R ^m \ A per ogni r > 0.

L’insieme dei punti interni esterni e di frontiera si chiama interno, esterno e la frontiera dia A, e si denota con int(A), ext(A) e ∂A. Si utilizza anche la notazione A ^◦ invece di int(A).

Sia A ⊂ R ^m .

• Gli insiemi int(A), ext(A), ∂A formano una partizione di R ^m : sono disgiunti e la loro riunione fornisce R ^m .

3. Insiemi aperti, chiusi, compatti

Definizione 3.1. Sia X ⊂ R ^m e x ∈ R ^m . Si dice che il punto x ` e di aderenza per X se la palla B <sub>r</sub> (x) incontra X per ogni r > 0. L’insieme dei punti x con questa propriet` a si chiama aderenza di X e si denota con X.

Proposizione 1. Sia X ⊂ R ^m e x ∈ R ^m , allora x ∈ X ⇐⇒ ∃ (x n ) ⊂ X e x n → x

Definizione 3.2. Sia X ⊂ R ^m . Si dice che X ` e un insieme aperto se per ogni x ∈ X se esiste r > 0 tale che la palla B <sub>r</sub> (x) ` e interamente contenuta in X.

Dati due punti distinti di R ^m x e y esistono due aperti X e Y tali che x ∈ X y ∈ X e X ∩ Y = ∅.

Proposizione 2. ∅ e R ^m sono aperti. L’ unione qualsiasi di insiemi aperti

`

e un insieme aperto. L’intersezione di un numero finito di insiemi aperti ` e

un insieme aperto.

Definizione 3.3. Un insieme X ` e chiuso se l’insieme complementare in R <sup>m</sup> ` e aperto

X ` e il pi` u piccolo insieme chiuso che contiene X.

Proposizione 3. ∅ e R ^m sono chiusi. L’unione di un numero finito di insiemi chiusi ` e un insieme chiuso. L’intersezione qualunque di insiemi chiusi ` e un insieme chiuso .

Definizione 3.4. K ` e limitato ⇐⇒ esiste una costante L tale che kxk < L per ogni x ∈ K Il diametro di K ` e definito come

diam(K) = sup{d(x, y), x, y ∈ K}.

Se diam(K) = +∞ diremo che K ` e illimitato.

Definizione 3.5. K ` e compatto se ∀(x n ) ⊂ X esiste una sottosuccessione (x _n

_k

) con lim x _n

_k

∈ X

Teorema 3.6. (Teorema di Heine-Borel) K compatto ⇐⇒ K ` e chiuso e limitato

L’intersezione infinita di una famiglia infinita di aperti pu` o non essere aperta. Esempio (− _n ¹ , _n ¹ ). L’intersezione {0}: un insieme chiuso.

∅ e R ^m sono gli unici insiemi che sono sia aperti che chiusi.

Ci sono insiemi che non sono n´ e aperti n´ e chiusi, ad esempio gli intervalli di R a cui appartiene un solo estremo.

4. Insiemi convessi

Definizione 4.1. Ω ⊂ R ^N si dice convesso se per ogni x e y ∈ Ω, λx + (1 − λ)y ∈ Ω per ogni λ ∈ [0, 1].

Se Ω contiene x e y, allora contiene tutti i punti del segmento di estremi x e y che indicheremo con [x, y]. Nel piano il cerchio B R (x) ` e un insieme convesso, mentre una corona circolare non ` e un insieme convesso. In R ^m l’insieme B r (a) := {x ∈ R ^m : kx − ak < r} ` e convesso. Siano x, y ∈ B r (a) allora per λ ∈ [0, 1]

kλx + (1 − λ)y − ak = kλ(x − a) + (1 − λ)(y − a)k ≤ λ k(x − a)k+(1−λ) ky − a)k ≤ r L’intersezione di due insieme convessi ` e un insieme convesso.

Esempio l’intersezione non vuota di un cerchio con un quadrato.

L’intersezione di un numero finito di insiemi convessi ` e un insieme con- vesso. Esempi di insieme convessi

• p non nullo.

Iperpiano (insieme chiuso)

H = {x ∈ R ^m : p ^T x = α},

ossia l’insieme dei vettori di R ^m ortogonali a p

• p non nullo.

Semispazi (insieme chiuso)

H ⁺ = {x ∈ R ^m : p ^T x ≥ α}, H − = {x ∈ R ^m : p ^T x ≤ α},

Un insieme X ` e un poliedro se ` e intersezione di un numero finito di semis- pazi chiusi e iperpiani. In R ³ un esempio di poliedro ` e il cubo. In R ² i poligoni piani.

Verificare che l’insieme

{(x, y) : y + x ≤ 1, x ≥ 0, y ≥ 0}

`

e un sottoinsieme convesso di R ² .

Dato un insieme Ω, l’involucro convesso di Ω, co(Ω) ` e il pi` u piccolo insieme convesso che contiene Ω.

Teorema 4.2 (Teorema di separazione). Siano C 1 e C 2 due sottoinsiemi convessi di ⊂ R ^N tali int(C ₁ ) ∩ C ₂ = ∅. allora esiste p ∈ R ^N , p 6= 0, tale che

(4.1) py ≥ px, ∀x ∈ C ₁ , ∀y ∈ C ₂ 5. Convergenza 5.1. Successioni.

Definizione 5.1. Una successione (x _n ) x _n ∈ R ^m ` e convergente, se esiste un punto a ∈ R ^m , detto limite della successione tale che kx _n − ak → 0 per n → ∞.

Diremo anche che (x _n ) converge ad a, e scriviamo x n → a anche lim x n = a .

Esempio 5.2.

• Per m = 1 si ha la nozione di convergenza per successioni reali Definizione 5.3. Una successione (x _n ) x _n ∈ R ^m ` e una successione di Cauchy se ∀ε > 0 ∃ν > 0 tale che kx n − x _m k < ε, ∀n, m > ν

Equivalentemente

Definizione 5.4. Una successione (x _n ) x _n ∈ R ^m ` e una successione di Cauchy se ∀ε > 0 ∃ν > 0 tale kx n+p − x _n k < ε, ∀n > ν, ∀p ∈ N

(Caratterizzazione della convergenza). Sia (x _n ) x _n ∈ R ^m , a ∈ R ^m scrivi- amo

x _n = (x _n1 , . . . , x _nm ) e a = (a ₁ , . . . , a _m ).

Allora x n → a in R ^m ⇐⇒ x _nk → a _k in R, per ciascuna componente k.

k = 1, . . . , m.

In R ^m non valgono pi` u i risultati che fanno uso della monotonia.

Proposizione 4. Siano (x n )(, y n ) due successioni con x n , y n ∈ R ^m e (λ _n ) ⊂ R.

• Il limite di una successione convergente ` e unico : se x n → a e x _n → b, allora a = b.

• Se x _n → a, allora x _n

_k

→ a per ogni sottosuccessione (x _n

_k

) della successione (x n ).

• Se x _n → a e y _n → b, allora x _n + y _n → a + b.

• Se λ _n → λ (in R) e x n → a (in R ^m ), allora λ n x n → λa (in R ^m ).

• Se x _n → a (in R ^m ), allora kx _n k → kak (in R).

Definizione 5.5. Una successione (x n ) x n ∈ R ^m ` e limitata, se esiste L ∈ R tale che kx _n k < L per ogni n.

Tutte le successioni convergenti sono limitate e vale

Teorema 5.6. (Bolzano–Weierstrass)Tutte le successioni limitate di R ^m ammettono una sottosuccessione convergente

Denotiamo con B(x, r) la palla di centro x ∈ R ^N e raggio r > 0, ossia B(x, r) = {y ∈ R ^N : ky − xk ≤ r},

Definizione 5.7. Dato Ω ⊂ R ^m , diciamo che x ∈ R ^m ` e un punto di accu- mulazione per Ω se esiste una successione (x n ) tale che x n ∈ Ω, x _n 6= x e lim _n→∞ kx _n − xk = 0.

Lemma 5.8. Sia f : A → R ⁿ (A ⊂ R ^m ) e a ∈ A di accumulazione per A Le due propriet` a seguenti sono equivalenti

(a) ∀ε > 0 ∃δ > 0 tale che se x ∈ A e kx − ak < δ, allora kf (x) − f (a)k <

ε;

(b) (x n ) x n ∈ D(f ) e x _n → a, allora f (x _n ) → f (a).

f ` e continua in A se ´ e continua in ogni punto a ∈ A, ossia

∀ε > 0 ∃δ > 0 tale che se x ∈ A e kx − ak < δ, allora kf (x) − f (a)k < ε 5.2. Teorema di Weierstrass. Una funzione continua in un compatto am- mette minimo e massimo assoluto.

6. Funzione Distanza

Consideriamo la funzione distanza di x ∈ R ^N non appartenente all’ in- sieme compatto e convesso D

(6.1) d D (x) = inf

y∈D |x − y| .

|x − y|: si tratta di una funzione continua, D ` e un insieme compatto, come applicazione del teorema di Weierstrass, abbiamo che il minimo ` e assunto.

Allora per qualche y ^∗ ∈ D.

d _D (x) = |x − y ^∗ |

d D : R ^N → R la funzione distanza di x ∈ R ^N dall’insieme chiuso D ` e allora definita

d _D (x) = min

y∈D |x − y| .

Proposizione 5. Sia D un insieme compatto. Allora d D ` e Lipschitz con- tinua

 d _D (x) − d _D (x ⁰ )   ≤ 

x − x ⁰ 

 ∀x, x ⁰ ∈ R ^N . Proof. d _D (x ⁰ ) = x ⁰ − ˆ y per qualche ˆ y ∈ D allora

d _D (x) − d _D (x ⁰ ) ≤ |x − ˆ y| −  x ⁰ − ˆ y 

 ≤  x − x ⁰ 

 .

La dimostrazione segue scambiando il ruolo di x and x ⁰ .  7. Test degli autovalori

Gli autovalori di una matrice simmetrica n × n sono numeri reali che possiamo ordinare dal pi` u piccolo al pi` u grande

λ 1 ≤ λ ₂ ≤ . . . λ _n

Teorema 7.1. Se λ ₁ e λ _n sono il pi` u piccolo e il pi` u grande autovalore di A allora

(7.1) λ ₁ khk ² ≤ Ah · h ≤ λ _n khk ² , ∀h ∈ R ⁿ Introduciamo la forma quadratica

f (h) = Ah · h =

n

X

i,j=1

a _i,j h _i h _j in

K = {h ∈ R ⁿ : khk = 1}

f (h) ` e una funzione continua su K (insieme chiuso e limitato). Per il teorema di Weierstrass ammette minimo e massimo in K, siano h <sub>1</sub> e h <sub>2</sub> rispettivamente con f (h <sub>1</sub> ) = m e f (h <sub>2</sub> ) = M. Se h = 0 la (7.1) ` e ovviamente verificata. Supponiamo h ∈ R ⁿ con h 6= 0. Poniamo

µ = h khk e consideriamo

Aµ · µ =

n

X

i,j=1

a _i,j µ _i µ _j . Si ha µ ∈ K, segue allora

m ≤

n

X

i,j=1

a i,j µ i µ j ≤

n

X

i,j=1

a i,j

h i

khk h j

khk = 1 khk ²

n

X

i,j=1

a i,j h i h j ≤ M

La funzione

g(h) = 1 khk ²

n

X

i,j=1

a i,j h i h j

in R ⁿ \ 0 ammette in h ₁ un punto di minimo e in h 2 un punto di massimo.

Rimane da dimostrare che m e M sono autovalori di A Ah ₁ = mh ₁ , Ah 2 = M h 2 , pi` u esattamente sono il pi` u piccolo e il pi` u grande autovalore di A.

Calcoliamo le derivate parziali della funzione g

∂g

∂h i

=

 n

X

i,j

a _i,j h _i h _j

 ∂

∂h i

 1 khk ²



+ 1

khk ²

 ∂

∂h i n

X

i,j=1

a _i,j h _i h _j



Calcoliamo

∂

∂h i

 1 khk ²



= ∂

∂h i

 1

h ² ₁ + h ² ₂ + . . . h ² _n



= − 2h _i

(h ² ₁ + h ² ₂ + . . . h ² _n ) ² == − 2h _i khk ⁴ e utilizzando a i,j = a j,i

 ∂

∂h i n

X

i,j=1

a _i,j h _i h _j



= 2

n

X

i,j=1

a _j,i h _j . Da cui si deduce

∂g

∂h i

= 2

khk ²

 n

X

i,j=1

a j,i h j − Ah · h khk ² h i



Dg(h ₁ ) = 0 ⇐⇒ Ah ₁ −g(h ₁ )h ₁ = 0 Dg(h ₂ ) = 0 ⇐⇒ Ah ₂ −g(h ₂ )h ₂ = 0 ossia m = g(h 1 ) e M = g(h 2 ) autovalori per A. Inoltre sono il pi` u piccolo e il pi` u grande autovalore come segue facilmente.

8. Funzioni convesse e concave

Definizione 8.1. Sia C un insieme aperto e convesso. f : C → R si dice i) convessa se

(8.1) f (λx + (1 − λ)y) ≤, λf (x) + (1 − λ)f (y) ∀x, y ∈ Cλ ∈ [0, 1].

Si dice strettamente convessa se in (8.2) si ha la disuguaglianza stretta per λ ∈ (0, 1)

ii) concava se −f ` e convessa ossia

(8.2) λf (x) + (1 − λ)f (y) ≤ f (λx + (1 − λ)y) ∀x, y ∈ C, λ ∈ [0, 1].

Le funzioni affini definite in R ^N sono convesse e concave, un esempio di funzione strettamente convessa ` e f (x) = kxk ² . La funzione f : R → R definita da

(8.3) f (x) =

( |x| ² , x ≥ 0,

|x| x < 0

`

e convessa, ma non strettamente convessa.

Per funzioni regolari si ha la seguente caratterizzazione della convessit` a . Proposizione 6. Sia f : C → R, con C sottoinsieme aperto e convesso di R ^N . Allora

i) Se f ∈ C ¹ (C), allora f ` e convessa in C se e solo se (8.4) f (y) − f (x) ≥ Df (x)(y − x)∀x, y ∈ C.

ii) Se f ∈ C ² (C), allora f ` e convessa in C se e solo se D ² f (x) ≥ 0

∀x ∈ C.

Proof. 

8.1. Funzione distanza. Assumiamo che D sia un insieme convesso. Segue che la funzione d D (x) ` e convessa. In ipotesi di convessit` a vediamo come dimostrare l’unicit` a del punto di minimo. Prima osservazione ` e che il punto di minimo si trova sulla frontiera, sia µ tale che

µ = |x − y ^∗ | e se supponiamo ne esista un altro punto y ⁻

µ = 

x − y ⁻  

I due punti non possono trovarsi sullo stesso segmento, pertanto x − y ⁻ x − y ^∗ sono linearmente indipendenti. In tal caso, prendendo y ⁻ e y ^∗ si ha

f (αy ⁻ + (1 − α)y ^∗ ) < αf (y ⁻ ) + (1 − α)f (y ^∗ ) = µ, una contraddizione. Resta univocamente determinata

proj _D (x) = {y ∈ D tale che d _D (x) = |x − y|} x ∈ R ^N .

8.2. Convessit` a delle forme quadratiche. Esercizio. Riprendere i conti sul paragrafo test degli autovalori q(h) = h <sup>T</sup> Qh convessa ⇐⇒ Q ` e semidefinita positiva.

8.3. Disuguaglianza discreta di Jensen. Si f : C → R una funzione convessa in C insieme convesso. Dati k punti con k ≥ 2

x 1 , x 2 , . . . , x k

si ha

x 1 + x 2 + · · · + x k

k ∈ C

e

f x 1 + x 2 + · · · + x _k

k
≤ 1

k



f (x 1 ) + f (x 2 ) + . . . f (x _k )



se k = 2 allora ^x

¹

^+x ₂

²

∈ C segue dalla combinazione convessa di due punti.

e f ^x

¹

^+x ₂

²

≤ ¹ ₂



f (x 1 ) + f (x 2 )), segue dalla convessit` a di f . Assumiamo che al passo k sussista (ipotesi induttiva) si ha

x ₁ + x ₂ + · · · + x _k

k ∈ C

e

f x ₁ + x ₂ + · · · + x _k

k
≤ 1

k



f (x ₁ ) + f (x ₂ ) + . . . f (x _k )

 e dimostriamo

x ₁ + x ₂ + · · · + x _k + x _k+1

k + 1 ∈ C

e

f x 1 + x 2 + · · · + x k + x k+1

k + 1
≤ 1

k + 1



f (x 1 )+f (x 2 )+. . . f (x _k )+f (x _k+1 )

 . Poniamo

λ = k

k + 1 1 − λ = 1 − k

k + 1 = 1 k + 1 , allora

x ₁ + x ₂ + · · · + x _k + x _k+1

k + 1 = λ x ₁ + x ₂ + · · · + x _k

k + (1 − λ)x _k+1 ∈ C Si ha

f x 1 + x 2 + · · · + x k + x k+1

k + 1
= f x 1 + x 2 + · · · + x k

k + 1 + 1

k + 1 x k+1

e

f x ₁ + x ₂ + · · · + x _k + x _k+1

k + 1
= f x ₁ + x ₂ + · · · + x _k

k + 1 + 1

k + 1 x _k+1
= f λ x 1 + x 2 + · · · + x _k

k + 1

k + 1 x _k+1
≤ λf x 1 + x 2 + · · · + x _k

k ) + (1 − λ)f (x _k+1 ) ≤ λ 1

k f (x 1 ) + f (x 2 ) + . . . f (x k )

+ (1 − λ)f (x _k+1 ) = 1

k + 1 f (x ₁ ) + f (x ₂ ) + . . . f (x _k ) + f (x _k+1 )

8.4. Trasformata di Legendre-Fenchel. La trasformata di Legendre ` e un procedimento che trasforma una funzione convessa a valori reali di vari- abile reale in un’ altra funzione convessa.

Sia f : R ^N → R, f ∈ C ² (R ^N ) e f tale che D ² f > 0 in C. Allora f ` e strettamente convessa e la trasformata di Legendre-Fenchel di f ` e definita come

(8.5) f ^∗ (x) = sup

y∈R

^N

x · y − f (y) x ∈ R ^N

Esempio 8.2. 1 − dimensione

f (x) = 1 2 x ² f ^∗ (x) = 1

2 x ² .

In dimensione n siano p.q esponenti coniugati.

f (x) = 1 p kxk ^p con

kxk ^p = (x ² ₁ + x ² ₂ + · · · + x ² _n )

^p2

Allora

f ^∗ (x) = 1 q kxk ^q . Infatti annullando il gradiente si ha

x j − kˆ yk ^p−1 y ˆ j

kˆ yk = 0 ⇐⇒ x j − kˆ yk ^p−2 y ˆ j = 0 Si ricava

kˆ yk ^p−1 = kxk ⇐⇒ kˆ yk = kxk

^p−11

. Perci` o

ˆ

y j = x j kxk ⁻

^p−2p−1

Sostituendo il valore si ottiene

f ^∗ (x) = X

j

x j y ˆ j − 1

p kˆ yk ^p = X

j

x _j x _j kxk ⁻

^p−2p−1

− 1

p kxk

^p−1p

= kxk ² kxk ⁻

^p−2p−1

− 1

p kxk

^p−1p

= kxk

^p−1p

− 1

p kxk

^p−1p

= 1 q kxk ^q

Esempio 8.3. Sia f (x) = x ² con x ∈ C = [2, 3]. Per ogni y fissato yx − x ²

`

e continua in un intervallo compatto. Ne segue cha f ^∗ ` e definite in R. Si ha un punto stazionario 2x = y con x ∈ [2, 3] ⇐⇒ y = <sup>x</sup> <sub>2</sub> 4 ≤ y ≤ 6, altrimenti (4 > y oppure y > 6) il massimo ` e assunto agli estremi (x = 2 oppure x = 3). In conclusione la trasformata ` e definita in tutto R e f ^∗ (y) vale

i) 2y − 4 y < 4 ii) ^y ₄

⁴

4 ≤ y ≤ 6 iii) 3y − 9 y > 6

Teorema 8.4. Sia C un insieme aperto e convesso. Sia f : C → R f ∈ C ² (C) e D ² f > 0 allora

i) Per ogni x, esiste y = y(x) tale che il sup in (8.5) ` e assunto.

ii) f ^∗ ` e convessa.

iii) f ^∗∗ = f

Nel caso unidimensionale: osserviamo che per le ipotesi di regolarit` a D _x xy − f (x) = 0 ⇐⇒ y = f ⁰ (x),

sia x la soluzione ossia x = g(y) con g = (f ⁰ ) ⁻¹ (y) allora D _y g(y) = 1

f ⁰⁰ (g(y))

D y f ^∗ (y) = g(y) + yg ⁰ (y) − f ⁰ (g(y))g ⁰ (y) = g(y).

Risulta (la derivata della funzione inversa ` e il reciproco della derivata della funzione calcolata nella controimmagine del punto)

D _y ² f ^∗ (y) = 1 f ⁰⁰ (g(y))

Esercizio 8.5. Se f ` e omogenea di grado p > 1 alllora f <sup>∗</sup> ` e omogenea di grado q con p e q coniugati tra loro. Sia λ > 0

(8.6) f ^∗ (λx) = sup

y∈R

^N

λx · y − f (y) = sup

y∈R

^N

λ ^q+1−q x · y − f (y) =

λ ^q sup

y∈R

^N

x · (λ ^1−q )y − λ ^−q f (y) = λ ^q sup

y∈R

^N

x · (λ ^1−q y) − f (λ ⁻

q p

y)  Osserviamo

q

p = q − 1, pertanto ponendo ξ = λ ^1−q y si ottiene

f ^∗ (λx) = λ ^q sup

ξ∈R

^N

x · ξ − f ξ) = λ ^q f ^∗ (x)

8.5. Esempio: Minimi e Massimi per funzioni di 2 variabili. f (x, y) = x ² + y ² , generalizzare a x = (x 1 , x 2 ) f (x) = x ^T Ax con A matrice definita positiva.

8.6. Esempio: Minimo e Massimo assoluti per funzioni di 2 vari- abili su un insieme chiuso e limitato. f (x, y) = x − y in un rettangolo (esempio −1 ≤ x ≤ 1, −2 ≤ y ≤ 2)

Esercizi su mimino e massimo assoluti in due variabili.

8.7. Esempio: Minimi e Massimi relativi per funzioni di 3 variabili.

f (x, y) = x ² + y ² + z ² , generalizzare a x = (x ₁ , x ₂ , x ₃ ) f (x) = x ^T Ax con

A matrice definita positiva.

8.8. Esempio: Minimo e Massimo assoluti per funzioni di 3 variabili su un insieme chiuso e limitato. f (x, y) = x−y −z in un parallelepipedo (esempio −1 ≤ x ≤ 1, −2 ≤ y ≤ 2, −3 ≤ z ≤ 3).

Tra tutti i parallelepipedi retti a base rettangolare inscritti in un ellissoide di equazione

x ² a ² + y ²

b ² + z ² c ² = 1

determinare quello di volume massimo. Se x, y, z indicano i semispigoli si tratta di massimizzare la funzione

f (x, y, z) = 8xyz,

soggetta al vincolo ^x _a

²2

+ ^y _b

²2

+ ^z _c

²2

= 1, x > 0, y > 0, z > 0. Il problema pu` o essere scritto nella forma



 

 

max _x,y,z 8xyz

x

²

a

²

+ ^y _b

²2

+ ^z _c

²2

= 1 x > 0, y > 0, z > 0 8.9. Metodo di Lagrange.

( max x,y,z 8xyz

x

²

a

²

+ ^y _b

2²

+ ^z _c

²2

= 1 L(x, y, z, λ) = max

x,y,z 8xyz + λ( x ² a ² + y ²

b ² + z ² c ² − 1) Si calcolano i punti stazionari della funzione L



 

 

 

 

8yz + ^2λx _a

2

= 0 8xz + ^2λy _b

2

= 0 8xy + ^2λz _c

2

= 0

x

²

a

²

+ ^y _b

2²

+ ^z _c

²2

= 1 Si ricava dalla prima equazione

λ = − 4a ² yz x



 

 

8x ² zb ² − 8a ² y ² z = 0 8x ² yc ² + 8yz ² a ² = 0

x

²

a

²

+ ^y _b

2²

+ ^z _c

²2

= 1 Semplificando



 

 

x

²

a

²

= ^y _b

2²

x

²

a

²

= ^z _c

²2

x

²

a

²

+ ^y _b

2²

+ ^z _c

²2

= 1 x ² = a ²

3 ,

la cui soluzione positiva ` e

x = a

√ 3 . Dunque

x = a

√

3 y = b

√

3 z = c

√ 3 .

In generale il problema di minimizzazione per funzioni a valori reali soggetta a m vincoli

min f (x), x ∈ Ω = {x ∈ R ^N : φ 1 (x) = φ 2 (x) = · · · = φ m (x) = 0}

L(x, λ) = f (x) +

m

X

i=1

λ i φ i (x) = f (x) + λ ^T φ(x)

In ipotesi di regolarit` a i punti stazionari sono dati dalla soluzione nelle N +m variabili

DL(x, λ) = Df (x) +

m

X

i=1

λ _i Dφ _i (x) = Df (x) + λ ^T Dφ(x) = 0

Vediamo le condizioni per il problema di minimizzazione per la forma quadratica

min x ^T Ax, x ∈ Ω = {x ∈ R ^N : Cx = d},

con A definita positiva, C matrice m × n, d ∈ R ^m m < n di rango m L(x, λ) = x ^T Ax + λ(Cx − d),

D _x L(x, λ) = Ax + C ^T λ = 0 D _λ L(x, λ) = Cx − d = 0 λ ∈ R ^m . Esempio.

8.10. Vincoli di disuguaglianza. Condizioni necessarie (KKT).

min x ² + y, x ∈ Ω = {x ∈ R ^N : x ² + y ² ≤ 4, x + y ≤ 1}, L(x, y, λ ₁ , λ ₂ ) = x ² + y + λ ₁ (x ² + y ² − 4) + λ ₂ (x + y − 1).

Minimizzazione sotto la condizione x ² + y ² ≤ 4, x + y ≤ 1, λ ₁ , λ ₂ ≥ 0 λ 1 (x ² + y ² − 4) = 0 λ ₂ (x + y − 1)=0

• x + y < 1, x ² + y ² < 4 il minimo non ` e influenzato dai vincoli λ ₁ = λ ₂ = 0.

D _x L(x, y, λ) = 2x D _y L(x, y, λ) = 1.

Non vi sono punti interni in cui si annulla il gradiente

• x + y = 1, x ² + y ² < 4 il minimo non ` e influenzato da un vincolo λ 1 = 0.

D x L(x, y, λ) = 2x + λ 2 D y L(x, y, λ) = 1 + λ 2 .

1 + λ ₂ = 0 non ` e possibile.

• x ² + y ² = 4, x + y < 1 il minimo non ` e influenzato da un vincolo λ ₂ = 0.

D x L(x, y, λ) = 2x + 2xλ 1 D y L(x, y, λ) = 1 + 2yλ 1 . Pertanto

λ ₁ = −1, non ` e possibile oppure

x = 0.

In tal caso

y = ±2.

Se y = 2 allora λ ₁ = − ¹ ₂ , non accettabile. Pertanto l’unica soluzione

` e

(0, −2, 1

4 , 0) f (0, −2, 1

4 , 0) = −2

• Entrambi i vincoli sono attivi x ² + y ² = 4, x + y = 1 2x + 2xλ ₁ + λ ₂ = 0,

1 + 2yλ ₁ + λ ₂ = 0 Completare e concludere il calcolo.

9. Convoluzione Inf-Sup per funzioni non regolari

Data una funzione f : R ^N → R, f ∈ C(R ^N ) la convoluzione Inf-Sup f indicate con f  e con f ^

(9.1) f  (x) = inf

y∈R

^N



f (y) + kx − yk ² 2

 e

(9.2) f ^ (x) = sup

y∈R

^N



f (y) − kx − yk ² 2



Per  che tende a 0 f ^ & f e f _ % f localmente uniformemente.

Ref. Fundamentals of Convex Analysis, Di Jean-Baptiste Hiriart-Urruty,Claude Lemar´ echal, Springer

Ref. A.Avantaggiati, P.Loreti, An approximation of Hopf-Lax type for- mula via idempotent analysis Tropical and Idempotent Mathematics and Applications, Proceedings of the International Workshop on Tropical and Idempotent Mathematics, Independent University of Moscow, Russia, Au- gust 26–31, 2012. Contemporary Mathematics, Publication Year 2014: Vol- ume 616, ISBNs: 978-0-8218-9496-5 (print); 978-1-4704-1684-3 (online) (pag 47-58) DOI: http://dx.doi.org/10.1090/conm/616) Consideriamo il seguente esempio. Sia

f = kxk . (9.3) f  (x) = inf

y∈R

^N

 N

X

k=1

y _k ²



¹

2

+ 1 2

N

X

k=1

(x k − y _k ) ²



.

Assumiamo y 6= 0, calcoliamo il gradiente e poniamolo uguale a 0. Trovi- amo

(9.4) y _k

kyk − 1

 (x _k − y _k ) = 0 ∀k = 1 . . . N.

Allora abbiamo, quadrando

 ² y ² _k

|y| ² = (x _k − y _k ) ² , e sommando su k

kx − yk ² =  ² . Questo implica

kx − yk = .

Moltiplichiamo (9.4) per y k e sommiamo allora si ottiene kyk − 1

 (yx − kyk ² ) = 0.

Dalla formula (9.4) otteniamo anche

y k (kyk + ) = kykx k ∀k = 1 . . . N.

Facendo il quadrato e addizionando

kyk ² (kyk + ) ² = kyk ² kxk ² . Ossia

kyk +  = kxk e quindi

kxk >  y = kxk − .

per questo valore di y si ha

f _ (x) = kxk − 1 2 . Assumiamo |y| 6= 0 e |x| ≤ , allora

kyk + 1

2 ky − xk ² ≥ kyk + 1

2 (kyk ² + |x| ² − 2kxkkyk = |y|(1 − kxk

 ) + kyk ² 2 + |x| ²

2 ≥ |x| ² 2 . Mentre f _ in 0 fornisce

f  (x) = kxk ² 2 . Allora si ottiene

f  (x) = ( _kxk

2

2 kxk ≤ 

kxk − ^ ₂ kxk > .

Esercizio: fare il grafico nel caso unidimensionale per alcuni valori di .

10. Ottimizzazione

min f (x) x ∈ F

• F = R ⁿ , non vincolato

• F ⊂ R ⁿ problema vincolato

F insieme chiuso. Caso particolare espresso come F = {x ∈ R ⁿ : g(x) ≤ 0 h(x) = 0},

con g : R ⁿ → R ^m , h : R ⁿ → R ^p un vincolo g _k si dice attivo in x ^∗ se g k (x ^∗ ) = 0.

Nella teoria che svilupperemo f , g e h sono assunte C ¹ , abbiamo come primo punto il problema dell’esistenza del minimo. Assumeremo che F 6= ∅.

Osserviamo che se g ` e una funzione convessa in R ⁿ allora l’insieme F = {x ∈ R ⁿ : g(x) ≤ 0},

`

e un insieme convesso perch´ e intersezione di un numero finito di insieme convessi.

Il problema di minimizzazione si dice convesso che la funzione da minimiz- zare ` e una funzione convessa e l’insieme dei vincoli ` e un insieme convesso.

Non ` e detto che una funzione convessa in un insieme convesso ammetta minimo. Sussiste il seguente risultato

Proposizione 7. Sia C ⊂ R ^N un insieme convesso e f : C → R una funzione strettamente convessa. Allora ogni punto di m´ınimo locale ` e punto di m´ınimo globale.

Proof. Assumiamo che ci sia un punto x ^∗ di minimo locale non globale.

Allora esiste δ > 0 tale che

f (x ^∗ ) ≤ f (x), ∀x ∈ C ∩ B _δ (x ^∗ )

e, per qualche ˆ x, f (ˆ x) < f (x ^∗ ). Poich` e ˆ x 6= x ^∗ , prendiamo λ ∈ (0, min{1, _{|ˆ x−x} ¹

?

| } e x λ = λˆ x + (1 − λ)x ^∗ . Allora

f (x _λ ) ≤ λf (ˆ x) + (1 − λ)f (x ^∗ ) < λf (x ^∗ ) + (1 − λ)f (x ^∗ ) = f (x ^∗ ), contraddicendo l’ipotesi che x ^∗ sia un punto di minimo locale.  10.1. Ottimizzazione con vincoli unilaterali e bilaterali. Il problema

`

e il seguente:

Data f : R ^N → R e g : R ^N → R ^M , h : R ^N → R ^P , trovare (10.1) min {f (x) : x ∈ R ^N s.t. g _i (x) ≥ 0, i = 1, . . . , m,

h i (x) = 0, i = 1, . . . , P }

11. Condizioni necessarie: il teorema di Fritz-John

Teorema 11.1. Sia I un sottoinsieme di R ^N , f : I → R, g : I → R ^M , h : I → R ^P , funzioni C ¹ (I) e x ₀ ∈ I. Se esiste un intorno aperto U di x ₀ in R ^N tale che

f (x 0 ) ≤ f (x) ∀x ∈ U ∩ {x ∈ I : g(x) ≤ 0, h(x) = 0}

allora esistono λ 0 , λ = (λ 1 , . . . , λ M ) e µ = (µ 1 , . . . , µ P ) tali che i)

(11.1)



 



 

 λ 0 ∂f

∂x

i

(x 0 ) + P M j=1 λ j ∂g

j

∂x

i

(x 0 ) + P P

j=1 µ j ∂h

j

∂x

i

(x 0 ) = 0, i = 1, . . . , N λ i g i (x 0 ) = 0, i = 1, . . . , M, (λ 0 , λ) ≥ 0, (λ 0 , λ, µ) 6= 0

g(x 0 ) ≤ 0, h(x 0 ) = 0

Proof. Dalla Definitione di minimo vincolato e dalla continuit` a di f , g e h possiamo considerare δ > 0 tale che per ogni x ∈ B(x ₀ , δ) ∩ {x ∈ I : g(x) ≤ 0, h(x) = 0}

f (x ₀ ) ≤ f (x)

g i (x) < 0 se g i (x 0 ) < 0 Introduzione il funzionale penalizzato

F _k (x) = f (x) + 1

2 kx − x ₀ k ² + k 2

M

X

i

1

g ⁺ _i (x) ² +

P

X

i

1

h i (x) ²

!

dove g _i (x) ⁺ = max{g _i (x), 0} il cui quadrato ` e una funzione C ¹ con gradiente 2g _i ⁺ (x)Dg _i (x). Consideriamo il problema di ottimizzazione

(11.2) min

x∈B(x

0

,δ)

F _k (x)

Dal teorema di Weierstrass, esiste x k punto di minimo per F k in B(x 0 , δ).

In particolare abbiamo

(11.3) F _k (x _k ) ≤ F _k (x ₀ ) = f (x ₀ )

(poich´ e g i (x 0 ) ≤ 0 e h i (x 0 ) = 0). Inoltre, per il teorema di Bolzano- Weierstrass (ogni successione reale limitata ammette almeno una sottosuc- cessione convergente), la successione {x k } _k∈N ammette una sottosuccessione che denotiamo ancora con {x _k } convergente a x ^∗ ∈ B(x ₀ , δ). Dalla (11.3)

M

X

i=1

g _i ⁺ (x _k ) ² +

P

X

i=1

h _i (x _k ) ² ≤ 2 k



f (x ₀ ) − f (x _k ) − 1

2 kx _k − x ₀ k ²



e per la continuit` a di g i , h i abbiamo per k → ∞

M

X

i=1

g ⁺ _i (x ^∗ ) ² +

P

X

i=1

h _i (x ^∗ ) ² ≤ 0

e quindi poich` e

g _i (x) ⁼

( g i (x) g i (x) > 0 0 g _i (x) ≤ 0 Esempio max(0, sin x) e max(0, sin x)) ²

fmax.pdf

Figure 1. max(0, sin x) e (max(0, sin x)) ²

(11.4) g _i (x ^∗ ) ≤ 0, i = 1, . . . , M , e h _i (x ^∗ ) = 0, i = 1, . . . , P . In pi` u dalla (11.3), abbiamo

f (x k ) + 1

2 kx _k − x ₀ k ² ≤ F _k (x k ) ≤ f (x 0 ) e passando al limite per k → ∞ abbiamo

(11.5) f (x ^∗ ) + 1

2 kx ^∗ − x ₀ k ² ≤ f (x ₀ ).

Dalla (11.4), x ^∗ ∈ {x ∈ I : g(x) ≤ 0, h(x) = 0} e quindi f (x ^∗ ) ≥ f (x 0 ).

Allora (11.6) concludiamo che

kx ^∗ − x ₀ k ² = 0 e quindi

x ^∗ = x 0 .

Poich´ e x k → x ₀ , possiamo concludere che per k sufficientemente grande x _k ∈ B(x ₀ , δ) e allora, per il Teorema di Fermat, si ottiene

∂F k

∂x i

(x k ) = ∂f

∂x i

(x k ) + (x k,i − x _0,i ) +

M

X

j=1

kg _j ⁺ (x k ) ∂g _j

∂x i

(x k )

+

P

X

j=1

kh j (x _k ) ∂h j

∂x _i (x _k ) = 0, i = 1, . . . , N

(11.6)

Definiamo L ^k , λ ^k ₀ ∈ R, λ ^k ∈ R ^M , µ ^k ∈ R ^P

L ^k =



1 +

M

X

j=1

(kg _j ⁺ (x k )) ² +

P

X

j=1

(kh j (x k )) ²





1 2

,

λ ^k ₀ = 1

L ^k , λ ^k _i = kg _i ⁺ (x k )

L ^k , µ ^k _i = kh i (x k ) L ^k allora

|(λ ^k ₀ , λ ^k , µ ^k )| ² =  1 L ^k

 2

+

M

X

j=1

kg ⁺ _j (x k ) L ^k

! 2

+

M

X

j=1

 kh _j (x _k ) L ^k

 2

=

=  1 L ^k

 2 

1 +

M

X

j=1



kg _j ⁺ (x _k )

 2

+

M

X

j=1

(kh j (x _k )) ²



 = 1 Per il teorema di Bolzano-Weierstrass la successione

(λ ^k ₀ , λ ^k , µ ^k ) _k∈N

ammette una sottosuccessione che denotiamo ancora con (λ ^k ₀ , λ ^k , µ ^k ) con- vergente a (λ ₀ , λ, µ), tale che |(λ ₀ , λ, µ)| = 1. Dividendo (11.6) per L ^k , si ha

(11.7) λ ^k ₀ ∂f

∂x i

(x _k ) + (x _k,i − x _0,i )

L ^k +

M

X

j=1

λ ^k _j ∂g _j

∂x i

(x _k ) +

P

X

j=1

µ ^k _j ∂h _j

∂x i

(x _k ) = 0 e ricordando che x _k → x ₀ e (λ ^k ₀ , λ ^k , µ ^k ) → (λ ₀ , λ, µ) otteniamo la prima condizione in (11.1). Poich´ e λ ^k ₀ , λ ^k ≥ 0 abbiamo al limite λ ₀ , λ ≥ 0.

Sia i tale che g i (x 0 ) < 0, allora g i (x _k ) < 0 e quindi (11.8) λ ^k _i = max{g _i (x _k ), 0} = 0 Quindi se g _i (x ₀ ) < 0, abbiamo

λ _i g( _i (x ₀ ) = 0.

Con gli stessi argomenti per gli altri indici i i, g _i (x ₀ ) = 0, possiamo scrivere λ i g i (x 0 ) = 0 per ogni i = 1, . . . , M ottenendo in questo modo (11.1).

 12. Penalizzazione

Problema vincolato (

min f (x) x ∈ R ⁿ x ∈ K

Problema libero con penalizzazione γ > 0 n

min f (x) + γP (x) x ∈ R ⁿ

ove P (x) verifica



 

 

P (x) ∈ C(R ⁿ )

P (x) ≥ 0 ∀x ∈ R ⁿ P (x) = 0 ⇐⇒ x ∈ K

Esercizio 12.1. Disegnare l’insieme ammissibile definito tramite le funzioni di penalizzazione Siano g 1 e g 2 due funzioni da R in R definite da

g ₁ (x) = x − 3 g ₂ (x) = −(x + 2) ³ Prendiamo

p ⁺ (x) = (max (p(x), 0)) ² g ⁺ ₁ (x)

( x − 3 x ≥ 3

0 x < 3

g ₂ ⁺ (x)

( −(x + 2) ³ x ≤ −2

0 x > −2

Esercizio 12.2. Costruire la soluzione penalizzata del problema con la fun- zione di penalizzazione di Courant-Beltrami

p ⁺ (x) = (max (p(x), 0)) ² ( min x

x ≥ a

p ⁺ (x) = (max(a − x, 0)) ² Per γ > 0 consideriamo

F _γ (x) = x + γ(max(a − x, 0)) ² . Completare confrontando il risultato.

Penalizzazione con vincolo di uguaglianza n = 2, min 1

2 (x ² ₁ + x ² ₂ ), Ax = b, A = [1 1], b = 2 n = 2, min 1

2 (x ² ₁ + x ² ₂ ), x 1 + x 2 = 2 Trovare la soluzione. Trovare la soluzione con penalizzazione

min 1

2 (x ² ₁ + x ² ₂ ) + γ(x ₁ + x ₂ − 2) ² e confrontare con la soluzione. Generalizzare al caso

F (x) = min 1

2 kxk ² + γ kAx − bk ²

13. Programmazione lineare (PL) Un problema di PL in forma standard ` e espresso come



 

 

min cx c ∈ R ⁿ

x ∈ K = {x ∈ R ⁿ : Ax = b, x ≥ 0},

A = (a i,j ) i = 1, . . . , m j = 1, . . . , n b ∈ R ^m Infatti vediamo come le altre condizioni possono essere

( min cx c ∈ R ⁿ

x ∈ K = {x ∈ R ⁿ : Ax ≥ b, x ≥ 0}

e

( min cx c ∈ R ⁿ

x ∈ K = {x ∈ R ⁿ : Ax ≤ b, x ≥ 0}

possono essere ricondotte al caso standard mediante aggiunta di variabile.

Caso I x ∈ R ⁿ : Ax ≥ b, x ≥ 0.

Vediamo come: la condizione

Ax = b ⇐⇒ a _i,1 x ₁ + a _i,2 x ₂ · · · + a _i,n x _n = b _i i = 1 , m Introduciamo

( min cx c ∈ R ⁿ

a i,1 x 1 + a i,2 x 2 · · · + a _i,n x n − y _i = b i i = 1 , x ≥ 0, y ≥ 0}

che possiamo riscrivere

Ax − I _m y = [A, −I _m ][x, y] ^T = b x ≥ 0, y ≥ 0 Caso II x ∈ R ⁿ : Ax ≤ b, x ≥ 0.

Intrduciamo

( min cx c ∈ R ⁿ

a _i,1 x ₁ + a _i,2 x ₂ · · · + a _i,n x _n + y _i = b _i i = 1 , x ≥ 0, y ≥ 0}

che possiamo riscrivere

Ax + I m y = [A, I m ][x, y] ^T = b x ≥ 0, y ≥ 0

A prima vista i problemi possono apparire differenti. In effetti geometri- camente la condizione legata alle disuguaglianze da luogo a intersezioni di semispazi nello spazio n-dimensionale mentre il problema con variabili ag- giunte da luogo a intersezioni di semispazi e iperpiani nello spazio n + m dimensionale.

Vediamo su un esempio

x 1 ≤ 3, diventa

( x 1 + x 2 = 3,

x ₂ ≥ 0

e

x ₁ ≥ 3, diventa

( x 1 − x ₂ = 3 x ₂ ≥ 0

Disegnare gli insiemi e verificare che possiamo associare al primo problema le soluzioni (x ₁ , 0).

Osserviamo che in un problema di programmazione lineare pu` o essere K = ∅ oppure il problema pu` o essere inferiormente illimitato. Vediamo in un semplice esempio il secondo caso

( min x x ≤ 2

Trattatiamo un problema di esistenza quando K 6= ∅ e il problema si assume essere inferiormente limitato. Dapprima ricordiamo

13.1. Cono convesso. Un cono ` e un sottoinsieme C di R <sup>m</sup> chiuso rispetto alla moltiplicazione per scalari positivi, cio` e

x ∈ C, λ > 0 =⇒ λx ∈ C

I coni appaiono naturalmente come rappresentazione dei vincoli. Consideri- amo

C = {y ∈ R ^m : y = Ax, x ≥ 0}.

C ` e un cono. Inoltre C ` e un cono convesso ossia se v e w appartengono a C allora se 0 ≤ α ≤ 1, risulta αv + (1 − α)w ∈ C. Si pu` o dimostrare che C ` e un cono convesso chiuso (un insieme C ` e chiuso se e solo se comunque presa una successione convergente {x _k } ⊂ C si ha lim _k∈+∞ x _k = x ∈ C).

Teorema 13.1. Se K 6= ∅, e la funzione cx ` e inferiormente limitata in K, allora il problema di minimizzazione

( min cx c ∈ R ⁿ

x ∈ K = {x ∈ R ⁿ : Ax ≥ b, x ≥ 0}

ammette soluzione ottimale

La dimostrazione utilizza principalmente la riduzione del problema in forma standard e le propriet` a del problema dei vincoli in forma standard viste precedentemente.

Esercizi.

Poliedro convesso: Si ottiene come intersezione di un numero finito di semispazi. Politopi: Un politopo n-dimensionale o n-politopo ` e l’analogo di un poligono nel piano (n=2). Politopo corrispone al caso poliedro limitato.

esempio di ottenimento di politopo e problema di minimizzazione con una funzione concava su un politopo. Ricordiamo che un problema con funzione obiettivo lineare e insieme ammissibile convesso ` e sia concavo che convesso.

Per le funzioni concave si ha il seguente