UNIVERSITA DEGLI STUDI DI FERRARA
FACOLTA DI SCIENZE MATEMATICHE, FISICHE E
NATURALI
Corso di Laurea Specialistica in
MATEMATICA
IL LEMMA DI FARKAS E LE CONDIZIONIDI KARUSH-KUHN-TUCKER
NELL’OTTIMIZZAZIONE LINEARE ENON LINEARE
Relatori:
Chiar.mo Prof.Josef Eschgfaller
Dott.ssa Silvia Bonettini
Laureanda:
Monica Gazzetta
Anno Accademico 2008-2009
Indice
Introduzione 3
I. IL METODO DEL SIMPLESSO
1. Il lemma di Farkas 5
2. Programmi lineari in forma standard 13
3. Programmi lineari in forma normale 18
4. Il metodo del simplesso 26
5. Geometria elementare degli insiemi convessi 31
II. ALCUNE APPLICAZIONI
6. Il separatore di Bennett-Mangasarian 37
7. Grafi 40
8. Flussi in un grafo diretto 44
III. OTTIMIZZAZIONE NON LINEARE
9. Il cono tangente 54
10. Le condizioni di Karush-Kuhn-Tucker 57
11. Il caso generale 60
12. Restrizioni lineari 64
13. Restrizioni convesse 65
Bibliografia 69
1
2
Introduzione
Lo scopo di questa tesi e quello di presentare ed approfondire (anchedal punto di vista geometrico ed algebrico) alcuni concetti basilari del-la programmazione lineare e non lineare che sono il lemma di Farkas ele condizioni di Karush-Kuhn-Tucker (dette anche condizioni di KKT).In questo lavoro inoltre, e stato descritto un algoritmo di risoluzioneper problemi di programmazione lineare, il metodo del simplesso, esono state presentate alcune sue possibili applicazioni pratiche.
Il lemma di Farkas e l’argomento del primo capitolo ed e forse il piuimportante teorema di alternativa per sistemi lineari e viene inoltreutilizzato in numerosi contesti come la programmazione lineare e nonlineare, la teoria dei sistemi di disequazioni lineari, i modelli economi-ci multisettoriali e la teoria dei giochi.
Questo lemma afferma che il sistema Ax = b ( dove A e una matricem × n e x e b sono vettori rispettivamente appartenenti ad R
m ed Rn)
con la condizione x ≥ 0 ammette soluzione se e solo se non la ammetteil sistema costituito dalle due condizioni yA ≥ 0 e yb < 0 con y ∈ Rm.
Grazie al lemma di Farkas, si puo dimostrare, sotto opportune ipo-tesi, che se un punto e soluzione di un problema di programmazione ingenerale non lineare, allora in tale punto sono soddisfatte le condizionidi KKT.
Le condizioni di Karush-Kuhn-Tucker sono descritte nel capitolo 10e costituiscono la parte fondamentale della terza sezione della tesi.Esse sono una generalizzazione del metodo dei moltiplicatori di La-grange applicato a problemi in cui sono presenti anche vincoli di di-suguaglianza e rappresentano lo scheletro della programmazione nonlineare costituendo condizioni necessarie per la soluzione di un pro-blema di programmazione non lineare in cui i vincoli soddisfano op-portune condizioni di regolarita dette condizioni di qualificazione deivincoli. Esempi di queste qualificazioni che vengono trattate nella tesisono il requisito di indipendenza lineare dei vincoli e il requisito diMangasarian-Fromovitz. Per problemi di programmazione lineare in-vece, le condizioni di KKT sono sia necessarie che sufficienti. Questequestioni vengono descritte nei capitoli 11, 12 e 13 dove sono presentirispettivamente vincoli generici, vincoli lineari e vincoli convessi. Nelcapitolo 9 diamo alcune definizioni che caratterizzano le condizioni diKKT dal punto di vista geometrico.
La prima parte della tesi riguarda la teoria e l’implementazione delmetodo del simplesso. Questo algoritmo e stato inventato dal matema-tico e statistico statunitense George B. Dantzig nel 1947 e rappresentaancora oggi uno dei metodi piu famosi e piu efficaci nella risoluzione diproblemi di programmazione lineare, problemi in cui si cerca di mas-simizzare o minimizzare una funzione lineare sotto opportuni vincolidi uguaglianza e disuguaglianza anch’essi lineari.
L’insieme di definizione dei vincoli e detto insieme ammissibile ed eun poliedro convesso. Se il problema di programmazione lineare am-
3
mette una soluzione ottimale, questa e anche un vertice del poliedro(teorema fondamentale della programmazione lineare, cap. 3).Queste considerazioni geometriche sono alla base del metodo inventa-to da Dantzig, la cui idea principale puo quindi essere cosı descritta:si determina un vertice iniziale del poliedro e si decide se tale puntoe una soluzione ottima; se non lo e si determina in modo adeguato unnuovo vertice del poliedro e se ne testa l’ottimalita e cosı via.
L’algoritmo del simplesso si applica in una prima formulazione aiprogrammi lineari nella forma fx = max (risp. min), x ≥ 0, Ax = b (for-ma normale) oggetto del capitolo 3. Questo tuttavia non e limitativoperche, come viene descritto nel cap. 2, ogni altro programma linearepuo essere ricondotto alla forma normale utilizzando opportune varia-bili di slack o di surplus. Gli aspetti teorici del metodo del simplessovengono approfonditi nel capitolo 3 mentre l’algoritmo tradotto in Mat-lab (o Octave) e presentato nel quarto capitolo. Nel capitolo 5 vengonoinvece descritte alcune proprieta degli insiemi convessi.
Nella seconda parte della tesi esponiamo alcuni possibili campi diapplicazione del metodo del simplesso: la teoria dei grafi e dei flussi,risp. capitoli 7 e 8, e il separatore di Bennett-Mangasarian nel cap. 6.In quest’ultimo in particolare si cerca di far vedere come il problemadi trovare un iperpiano che separa due insiemi di punti distinti possaessere ricondotto ad un problema di programmazione lineare. E unrisultato che viene ad esempio utilizzato nella ricerca sperimentaleriguardante la diagnosi e la prognosi del carcinoma mammario.
E opportuno ricordare che oltre al metodo del simplesso esistonoaltri metodi altrettanto efficaci per la risoluzione di problemi di pro-grammazione lineare e non lineare: i metodi a punto interno.Questi dal punto di vista geometrico si differenziano notevolmente dalmetodo del simplesso in quanto la ricerca della soluzione ottimale nonviene effettuata esaminando i vertici del poliedro ammissibile ma ri-manendo all’interno dell’insieme di definizione dei vincoli. I metodia punto interno discendono dalla condizioni di KKT opportunamen-te modificate (in modo da rimanere sempre all’interno della regioneammissibile) a cui viene applicato il metodo di Newton.
4
I. IL METODO DEL SIMPLESSO
1. Il lemma di Farkas
Situazione 1.1. n,m ∈ N + 1.
Definizione 1.2. Usiamo le seguenti notazioni:
Rnm := insieme delle matrici reali con n righe ed m colonne
Rm := R1m = insieme dei vettori riga reali con m coefficienti
Rn+ := x ∈ R
n | x ≥ 0
R+m := f ∈ Rm | f ≥ 0
R+ := [0,∞)
Definizione 1.3. Siano A ∈ Rmn , X ⊂ R
n, U ⊂ Rm, b ∈ Rm,
f ∈ Rn. Definiamo allora:
AX := Ax | x ∈ X
UA := uA | u ∈ U
(AX = b) := x ∈ X | Ax = b
(UA = f) := u ∈ U | uA = f
(AX ≤ b) := x ∈ X | Ax ≤ b
(UA ≥ f) := u ∈ U | uA ≥ f
In modo analogo sono definiti (AX ≥ b), (UA ≤ f), ecc.Avremo quindi ad esempio (AR
n+ = b) = x ∈ R
n+ | Ax = b.
Nota 1.4. Useremo le seguenti notazioni e formule ben note del calcolomatriciale:
(1) Per A ∈ Rmn denotiamo con Ai la i-esima riga, con Aj la j-esima
colonna di A.
(2) Per A ∈ Rmn , B ∈ R
ns abbiamo allora
(AB)ij = AiBj
(AB)i = AiB
(AB)j = ABj
AB =
n∑
α=1
AαBα
Abbiamo quindi in particolare, per x ∈ Rn ed f ∈ Rm,
5
Ax =n∑
α=1
Aαxα
fA =
m∑
α=1
fαAα
(3) Con ‖x, y‖ = xty risp. ‖f, g‖ = fgt denoteremo il prodotto scalaredi x, y ∈ R
n risp. f, g ∈ Rm.
(4) Per vettori v1, ..., vk in uno spazio vettoriale sia SV(v1, ..., vk) ilsottospazio vettoriale generato da questi vettori. Similmenteper un sottoinsieme X denoteremo con SV(X) il sottospazio vet-toriale generato da X.
(5) Per X ⊂ Rn sia X⊥ := v ∈ R
n | ‖x, v‖ = 0 per ogni x ∈ X.X⊥ e un sottospazio vettoriale di R
n, anche quando X stessonon e un sottospazio vettoriale.
(6) W sia un sottospazio vettoriale di Rn. Allora:
dim W + dimW⊥ = n
W⊥⊥ = W
Rn = W
⊕W⊥
(7) Per vettori v1, ..., vk in uno spazio vettoriale reale siaPOS(v1, ..., vk) := λ1v1 + ... + λkvk | λ1, ..., λk ∈ R
+.Similmente per un sottoinsieme X siaPOS(X) := λ1x1 + ... + λkxk | k ≥ 1, λi ∈ R
+, xi ∈ X peri = 1, ..., k.
Osservazione 1.5. Sia A ∈ Rmn . Allora:
(1) ARn = SV(A1, ..., An).
(2) ARn+ = POS(A1, ..., An).
Dimostrazione. (1) Sia x ∈ Rn. Allora Ax =
n∑
k=1
Akxk ∈ SV(A1, ..., An)
e viceversa. Il punto (2) si dimostra in modo analogo considerandox ∈ R
n+.
Lemma 1.6. Siano A ∈ Rmn e b ∈ R
m. Allora sono equivalenti:
(1) b ∈ ARn.
(2) (RmA = 0)b = 0.
Dimostrazione. (1) =⇒ (2): Sia f ∈ Rm con fA = 0. Poiche per ipotesib ∈ AR
n, esiste x ∈ Rn tale che b = Ax. Allora fb = fAx = 0.
(2) =⇒ (1): Sia b /∈ ARn = SV(A1, ..., An) =: W .
Per la nota 1.4 b = w + y con w ∈ W e y ∈ W⊥.Necessariamente y 6= 0 perche b 6∈ W . Abbiamo
6
‖b, y‖ = ‖w + y, y‖ = ‖w, y‖ + ‖y, y‖ = ‖y, y‖ 6= 0
Inoltre ‖Aj , y‖ = 0 per ogni j perche y ∈ W⊥. Con f := yt abbiamoallora fA = 0 ed fb 6= 0.
Definizione 1.7. V sia uno spazio vettoriale reale ed x, y ∈ V .Poniamo allora
[x, y] := x + [0, 1](y − x) = x + t(y − x) | t ∈ [0, 1]
Un sottoinsieme X ⊂ V si dice convesso se per ogni x, y ∈ X si ha[x, y] ⊂ X.
Per t ∈ R sia [x, y]t := x + t(y − x).
Osservazione 1.8. V e W siano spazi vettoriali reali ed x, y ∈ V .ϕ : V → W sia un’applicazione affine. Allora:
(1) ϕ([x, y]t) = [ϕ(x), ϕ(y)]t per ogni t ∈ R.
(2) ϕ([x, y]) = [ϕ(x), ϕ(y)].
(3) Se X e un sottoinsieme convesso di V , allora ϕ(X) e un sottoin-sieme convesso di W .
Dimostrazione. (1) Per ipotesi esistono un’applicazione lineareϕ0 : V −→ W e un vettore b ∈ W tali che ϕ = ϕ0 + b. Abbiamo alloraϕ(x + t(y − x)) = ϕ0(x + t(y − x)) + b = ϕ0(x) + tϕ0(y) − tϕ0(x) + b =ϕ0(x)+b+ t(ϕ0(y)+b−ϕ0(x)−b) = ϕ(x)+ t(ϕ(y)−ϕ(x)) = [ϕ(x), ϕ(y)]t.
(2) Dal punto (1) abbiamo direttamente ϕ([x, y]) ⊂ [ϕ(x), ϕ(y)].
Sia z ∈ [ϕ(x), ϕ(y)], ad esempio z = [ϕ(x), ϕ(y)]t con t ∈ [0, 1]. Alloraz = ϕ([x, y]t) ∈ ϕ([x, y]).
(3) Siano u = ϕ(x) e v = ϕ(y) con x, y ∈ X. Allora[u, v] = [ϕ(x), ϕ(y)] = ϕ([x, y]) ⊂ ϕ(X). Nell’ultima inclusione abbiamosfruttato il fatto che [x, y] ⊂ X perche X e convesso.
Lemma 1.9. v1, ..., vk siano vettori linearmente indipendenti di Rm.
Allora l’insieme POS(v1, ..., vk) e chiuso.
Dimostrazione. Possiamo trovare vk+1, ..., vm tali chev1, ..., vk, vk+1, ..., vm sia una base di R
m. Per ogni x ∈ Rm esistono
λ1(x), ..., λm(x) ∈ R tali che x = λ1(x)v1 + ... + λm(x)vm. Le funzioniλi : R
m → R che cosı otteniamo sono continue. Percio l’insiemePOS(v1, ..., vk) = (λ1 ≥ 0, ..., λk ≥ 0, λk+1 = 0, ..., λm = 0) e chiuso.
Proposizione 1.10 (lemma di Caratheodory). Sia X ⊂ Rm e
SV(X) 6= 0. Sia d := dimSV(X). Allora:
(1) Ogni punto di POS(X) e combinazione lineare a coefficienti nonnegativi di al massimo d punti linearmente indipendenti di X.
(2) Sia D la famiglia di tutti gli insiemi che consistono di esatta-mente d vettori linearmente indipendenti di X.
Allora POS(X) =⋃
D∈D
POS(D).
7
Dimostrazione. (1) Sia v ∈ POS(X). Esistono quindi λ1, ..., λk ≥ 0 edx1, ..., xk ∈ X tali che v = λ1x1 + ... + λkxk. Scegliamo k minimale (cioimplica λj > 0 per ogni j) e supponiamo per assurdo che k > d.
Siccome per ipotesi dim SV(X) = d, i vettori x1, ..., xk devono esserelinearmente dipendenti, percio esistono α1, ..., αk ∈ R non tutti nullitali che α1x1 + ... + αkxk = 0.
Possiamo assumere che α1 > 0 e cheα1
λ1≥
αj
λjper ogni j. Cio implica
λj ≥αj
α1λ1 per ogni j. Abbiamo pero
k∑
j=1
(λj −αj
α1λ1)xj = v.
In questa rappresentazione tutti i coefficienti sono ≥ 0 e il primo enullo, in contraddizione alla minimalita di k.
(2) Cio implica anche che POS(X) ⊂⋃
D∈D
POS(D) perche per il punto
(1) per ogni elemento x ∈ POS(X) esistono elementi x1, ..., xk ∈ Xlinearmente indipendenti con x ∈ POS(x1, ..., xk) e k ≤ d; se k < d,allora possiamo trovare xk+1, ..., xd tali chex1, ..., xk, xk+1, ..., xd =: D ∈ D con naturalmente ancora x ∈ POS(D).Viceversa POS(D) ⊂ POS(X) per ogni D ∈ D.
Proposizione 1.11. Siano v1, ..., vk ∈ Rm. Allora l’insieme POS(v1, ..., vk)
e chiuso.
Dimostrazione. Sia X = v1, ..., vk. D sia definito come nella prop.
1.10. Allora POS(X) =⋃
D∈D
POS(D). Per il lemma 1.9 per ogni
D ∈ D l’insieme POS(D) e chiuso. Nel nostro caso D e un insieme finitoe quindi anche POS(X) e chiuso.
Corollario 1.12. Sia A ∈ Rmn . Allora l’insieme AR
n+ e chiuso in R
m.
Dimostrazione. Per l’oss. 1.5 abbiamo ARn+ = POS(A1, ..., An).
L’enunciato segue dalla proposizione 1.11.
Osservazione 1.13. L’enunciato del cor. 1.12 non e banale, perche ingenere un’applicazione lineare R
n −→ Rm non trasforma chiusi in
chiusi. Un esempio e la proiezione sulla prima coordinata R2 → R che
trasforma l’iperbole x | x1x2 = 1, un insieme chiuso, in R \ 0.
Osservazione 1.14. X sia un sottoinsieme chiuso e non vuoto di Rm
ed y ∈ Rm. Allora esiste un punto p ∈ X che possiede distanza mini-
male da y.
Dimostrazione. Siccome X 6= ∅, possiamo scegliere un punto (arbi-trario) z ∈ X. Allora l’insieme A =: a ∈ X | |a−y| ≤ |z−y| e compattoe non vuoto, per cui la funzione continua ©
a|a − y| : A −→ R assume
un minimo in qualche punto p.
Lemma 1.15 (legge del parallelogramma). Siano x, y ∈ Rm. Allora
8
|x + y|2 + |x − y|2 = 2|x|2 + 2|y|2
Dimostrazione. |x + y|2 + |x− y|2 = |x|2 + |y|2 + 2‖x, y‖ + |x|2 + |y|2 −2‖x, y‖ = 2|x|2 + 2|y|2.
Teorema 1.16. X sia un sottoinsieme chiuso, convesso e non vuoto diR
m ed y ∈ Rm. Allora esiste un punto p ∈ X che possiede distanza
minimale da y. p e univocamente determinato.
Dimostrazione. (1) L’esistenza e stata dimostrata nell’oss.1.14.
(2) Dimostriamo l’unicita . Sia q ∈ X tale che |p − y| = |q − y|.Allora r := p+q
2 ∈ X perche X e convesso. Inoltre
|r − y|2 = |p − y|2 − 14 |p − q|2 (*)
Infatti per il lemma 1.15 applicato a x = p − y e y = q − y risulta
4|r − y|2 = 4|p + q
2− y|2
= |(p − y) + (q − y)|2
= 2|p − y|2 + 2|q − y|2 − |p − q|2
= 4|p − y|2 − |p − q|2
dove abbiamo utilizzato l’ipotesi |p−y| = |q−y|. Cio mostra l’uguaglianza(*). Se fosse p 6= q, risulterebbe |r − y| < |p − y| e p non avrebbe piudistanza minimale da y.
L’uguaglianza (*) e la relazione |r−y|2 < |p−y|2 per p 6= q sono ancheevidenti dalla figura.
yp
q
r
Definizione 1.17. Nella situazione del teorema 1.16 il punto p si chia-ma la proiezione di y su X. E immediato che y = p se e solo se y ∈ X.
Definizione 1.18. Per p, v ∈ Rm poniamo:
H(p, v) := x ∈ Rm | ‖x − p, v‖ = 0
O(p, v) := x ∈ Rm | ‖x − p, v‖ ≤ 0
SO(p, v) := x ∈ Rm | ‖x − p, v‖ < 0
Se v 6= 0, allora H(p, v) e l’iperpiano ortogonale a v passante per p,O(p, v) l’insieme dei punti che, riferendoci a p + v, si trovano oltre osu questo iperpiano, O(p,−v) l’insieme dei punti che non si trovanooltre questo iperpiano, cioe dalla stessa parte di p + v. SO significastrettamente oltre.
9
Proposizione 1.19. X sia un sottoinsieme chiuso, convesso e non vuoto
di Rm ed y ∈ R
m. Per un punto p ∈ X sono allora equivalenti:
(1) p e la proiezione di y su X.
(2) X ⊂ O(p, y − p).
Dimostrazione. (1) =⇒ (2): Siano p la proiezione di y su X ed x ∈ X.Allora per ogni t ∈ [0, 1] il punto p + t(x − p) ∈ X perche X e convesso.Per la definizione di p abbiamo
|y − p|2 ≤|y − (p + t(x − p))|2 =
|(y − p) − t(x − p)|2 =
|y − p|2 + t2|x − p|2 − 2t‖y − p, x − p‖
.
ovvero
2t‖y − p, x − p‖ ≤ t2|x − p|2
Per ogni t ∈ (0, 1] abbiamo percio 2‖y − p, x − p‖ ≤ t|x − p|2.Cio e possibile solo se ‖y − p, x − p‖ ≤ 0.
(2) =⇒ (1): Siano X ⊂ O(p, y − p) ed x ∈ X. Allora ‖y − p, p − x‖ ≥ 0e quindi
|y−x|2 = |y− p+ p−x|2 = |y− p|2 + |p−x|2 +2‖y− p, p−x‖ ≥ |y− p|2
Lemma 1.20. X sia un sottoinsieme chiuso, convesso e non vuoto di
Rm ed y ∈ R
m. p sia la proiezione di y su X. Allora:
(1) X ⊂ O(p + t(y − p), y − p) per ogni t ≥ 0.
(2) In particolare X ⊂ O(y, y − p).
(3) Se y /∈ X, allora X ⊂ SO(y, y − p).
Dimostrazione. Sia x ∈ X. Allora per t ≥ 0 si ha
‖(x − p) − t(y − p), y − p‖ = ‖x − p, y − p‖ − t|y − p|2 ≤ 0
essendo per la prop 1.19 ‖x − p, y − p‖ ≤ 0.
Sia ora y /∈ X. Allora y 6= p e quindi per t = 1 otteniamo
‖x − y, y − p‖ = ‖x − p, y − p‖ − |y − p|2 < 0.
Lemma 1.21. X sia un sottoinsieme chiuso, convesso e non vuoto di
Rm ed y ∈ R
m \ X. p sia la proiezione di y su X ed y∗ := p+y2 . Allora:
y ∈ SO(y∗, p − y)
X ⊂ SO(y∗, y − p)
10
Dimostrazione.
(1) 2‖y − y∗, p − y‖ = 2‖y −p + y
2, p − y‖ = −‖y − p, y − p‖ < 0
(2) Sia x ∈ X. Allora
2‖x − y∗, y − p‖ = 2‖x −p + y
2, y − p‖
= ‖x − p, y − p‖ + ‖x − y, y − p‖ < 0
Infatti per la prop. 1.19 abbiamo ‖x − p, y − p‖ ≤ 0, mentre dal lemma1.20 segue che ‖x − y, y − p‖ < 0.
y
p
X
Corollario 1.22. X sia un sottoinsieme chiuso, convesso e non vuoto di
Rm ed y ∈ R
m \ X. p sia la proiezione di y su X. Sia ancora y∗ := p+y2 .
Allora
‖y, y − p‖ > ‖y∗, y − p‖ > ‖x, y − p‖
per ogni x ∈ X.
Dimostrazione. Sia x ∈ X. Per il lemma 1.21 abbiamo
‖y − y∗, y − p‖ > 0 > ‖x − y∗, y − p‖
ovvero
‖y, y − p‖ − ‖y∗, y − p‖ > 0 > ‖x, y − p‖ − ‖y∗, y − p‖
e quindi
‖y, y − p‖ > ‖y∗, y − p‖ > ‖x, y − p‖
Corollario 1.23. X sia un sottoinsieme chiuso e convesso di Rm ed
y ∈ Rm \ X. Allora esistono α ∈ R ed f ∈ Rm tali che fy > α > fx per
ogni x ∈ X. Sostituendo f con −f ed α con −α possiamo naturalmente
anche ottenere fy < α < fx per ogni x ∈ X.
Dimostrazione. L’enunciato e banale per X = ∅ e segue altrimentidal corollario 1.22, se poniamo f := (y − p)t ed α := ‖y∗, y − p‖
Osservazione 1.24. Sia X ⊂ Rm. Allora POS(X) e convesso.
Dimostrazione. Siano u, v ∈ POS(X). Allora esistonoλ1, ..., λk, µ1, ..., µl ∈ R
+ e x1, ..., xk, y1, ..., yl ∈ X tali cheu = λ1x1 + ... + λkxk e v = µ1y1 + ... + µlyl. Sia t ∈ [0, 1]. Allora
11
u + t(v − u) = λ1x1 + ... + λkxk + tµ1y1 + ... + tµlyl − tλ1x1 − ... − tλkxk
= (1 − t)λ1x1 + ... + (1 − t)λkxk + tµ1y1 + ... + tµlyl
I coefficienti (1− t)λi e tµj sono tutti non negativi, per cui vediamo cheu + t(v − u) ∈ POS(X).
Corollario 1.25. Sia A ∈ Rmn . Allora AR
n+ e convesso.
Dimostrazione. Cio segue dall’oss. 1.24 perche ARn+ = POS(A1, ..., An)
per l’oss. 1.5.
Teorema 1.26 (lemma di Farkas). Siano A ∈ Rmn e b ∈ R
m. Allora
sono equivalenti:
(1) b ∈ ARn+.
(2) (RmA ≥ 0)b ≥ 0.
Dimostrazione. (1) =⇒ (2): Siano x ∈ Rn+ ed f ∈ Rm tali che b = Ax
ed fA ≥ 0. Allora fb = fAx ≥ 0.
(2) =⇒ (1): Sia b /∈ ARn+. Dai corollari 1.12 e 1.25 sappiamo che AR
n+
e un sottoinsieme convesso, chiuso e non vuoto di Rm; quindi per il
corollario 1.23 esistono α ∈ R e f ∈ Rm tali che fb < α < fAx per ognix ∈ R
n+. Cio deve valere in particolare per x = 0 e questo implica α < 0
e quindi anche fb < 0.
D’altra parte pero fA ≥ 0 e cio e in contraddizione con l’ipotesi (2).Infatti sia ad esempio fAj < 0. Siccome x := tAj = Atδj ∈ AR
n+,
abbiamo α < ftAj = tfAj per ogni t ≥ 0, ma cio non e possibileperche lim
t−→∞tfAj = −∞.
Osservazione 1.27. Siano A ∈ Rmn e b ∈ R
m. Denotiamo con δ lamatrice identica in R
nn. Allora:
(1) (A δ)Rn+ = Ax + u | x ∈ R
n+, u ∈ R
m+.
(2) (ARn+ ≤ b) 6= ∅ ⇐⇒ b ∈ (A δ)Rn
+.
Proposizione 1.28. Siano A ∈ Rmn e b ∈ R
m. Allora sono equivalenti:
(1) (ARn+ ≤ b) 6= ∅.
(2) (R+mA ≥ 0)b ≥ 0.
Dimostrazione. (1) =⇒ (2): Siano x ∈ Rn+ ed f ∈ R
+m tali che Ax ≤ b
ed fA ≥ 0. Allora fb ≥ fAx ≥ 0.
(2) =⇒ (1): Supponiamo che (ARn+ ≤ b) = ∅. Per l’oss. 1.27 cio signi-
fica che b /∈ (A δ)Rn+. Per il teorema 1.26 possiamo quindi trovare un
f ∈ Rm tale che f(A δ) ≥ 0 ed fb < 0. Ma f(A δ) = (fA f) ≥ 0 e equi-valente alle due condizioni fA ≥ 0 ed f ≥ 0, cioe ad f ∈ (R+
mA ≥ 0).Adesso pero fb < 0 e in contrasto con la nostra ipotesi.
12
2. Programmi lineari in forma standard
Situazione 2.1. n,m ∈ N + 1 ed A ∈ Rmn , f ∈ Rn, b ∈ R
m, quando nonindicato diversamente.
Definizione 2.2. Un programma lineare di massimizzazione in formastandard e un problema di ottimizzazione della forma
fx = max
x ≥ 0
Ax ≤ b
con A, f, b come nella situazione 2.1.
Si cercano quindi vettori non negativi x ∈ Rn per i quali fx e massi-
male sotto il vincolo Ax ≤ b.
Denotiamo con (f(ARn+ ≤ b) = max) l’insieme degli x ∈ R
n+ (detti
soluzioni del problema) con Ax ≤ b in cui fx assume un massimo su(AR
n+ ≤ b), mentre indichiamo con f(AR
n+ ≤ b) = max (senza parentesi
esterne) il problema stesso.
Gli elementi di (ARn+ ≤ b) si chiamano punti ammissibili del proble-
ma.
Definizione 2.3. Un programma lineare di minimizzazione in forma
standard e un problema di ottimizzazione della forma
ub = min
u ≥ 0
uA ≥ f
con A, f, b come nella situazione 2.1.
Si cercano quindi vettori riga non negativi u ∈ Rm per i quali ub eminimale sotto il vincolo uA ≥ f .
Denotiamo con ((R+mA ≥ f)b = min) l’insieme degli u ∈ R
+m (detti
soluzioni del problema) con uA ≥ f in cui ub assume un minimo su(R+
mA ≥ f), mentre indichiamo con (R+mA ≥ f)b = min (senza parentesi
esterne) il problema stesso.
Gli elementi di (R+mA ≥ f) si chiamano punti ammissibili del pro-
blema duale.
Osservazione 2.4. I problemi f(ARn+ ≤ b) = max e (R+
mA ≥ f)b = minsi determinano a vicenda e si dicono uno il duale dell’altro.
Lemma 2.5. Siano x una soluzione del problema f(ARn+ ≤ b) = max
ed u una soluzione del problema (R+mA ≥ f)b = min.
Allora fx ≤ uAx ≤ ub.
Dimostrazione. Per ipotesi Ax ≤ b e f ≤ uA con x ≥ 0 e f ≥ 0, percui fx ≤ uAx ≤ ub.
Proposizione 2.6. Siano x ∈ (ARn+ ≤ b) ed u ∈ (R+
mA ≥ f) tali che
fx ≥ ub.
13
Allora x e una soluzione di f(ARn+ ≤ b) = max ed u una soluzione di
(R+mA ≥ f)b = min.
Dimostrazione. Siano y ∈ (ARn+ ≤ b) e v ∈ (R+
mA ≥ f). Per il lemma2.5 abbiamo fy ≤ ub ≤ fx ≤ vb.
Proposizione 2.7. (1) Sia (ARn+ ≤ b) = ∅. Allora o (R+
mA ≥ f) = ∅oppure l’insieme (R+
mA ≥ f)b non e limitato inferiormente. Il problema
(R+mA ≥ f)b = min quindi non possiede soluzione.
(2)Sia (R+mA ≥ f) = ∅. Allora o (AR
n+ ≤ b) = ∅ oppure l’insieme
f(ARn+ ≤ b) non e limitato superiormente.
Il problema f(ARn+ ≤ b) = max quindi non possiede soluzione.
Dimostrazione. Dimostriamo solo il primo enunciato essendo il se-condo il suo duale. Sia (AR
n+ ≤ b) = ∅. Per la prop. 1.28 esiste quindi
un elemento g ∈ R+m tale che gA ≥ 0 e gb < 0.
Se (R+mA ≥ f) = ∅ e chiaro che il problema (R+
mA ≥ f)b = min nonpossiede soluzione.
Assumiamo quindi che (R+mA ≥ f) 6= ∅. Sia ad esempio u ∈ R
+m tale
che uA ≥ f . Allora per ogni λ ≥ 0 si ha che u + λg ≥ 0 e(u+λg)A = uA+λgA ≥ f , per cui u+λg ∈ (R+
mA ≥ f). Siccome gb < 0,si ha che lim
λ−→∞(u + λg)b = lim
λ−→∞(ub + λgb) = −∞.
Osservazione 2.8. Se il problema f(ARn+ ≤ b) = max possiede una
soluzione x, allora il valore max f(ARn+ ≤ b) = fx e ben definito.
Similmente, se il problema (R+mA ≥ f)b = min possiede una soluzio-
ne u, allora il valore min(R+mA ≥ f)b = ub e ben definito.
Teorema 2.9. Gli insiemi (ARn+ ≤ b) e (R+
mA ≥ f) siano entrambi nonvuoti. Allora i problemi f(AR
n+ ≤ b) = max e (R+
mA ≥ f)b = min sono
entrambi risolubili e si ha
max f(ARn+ ≤ b) = min(R+
mA ≥ f)b
Dimostrazione. (1) E sufficiente dimostrare che esistonox ∈ (AR
n+ ≤ b) ed u ∈ (R+
mA ≥ f) tali che fx ≥ ub. L’enunciato allora siottiene applicando la prop. 2.6.
(2) Il nostro scopo quindi e quello di trovare un elemento x ∈ Rn+ ed
un elemento u ∈ R+m tali che Ax ≤ b, uA ≥ f (cioe −Atut ≤ −f t) ed
fx ≥ ub. L’ultima disuguaglianza e equivalente a −fx + btu ≤ 0.
(3) Scrivendo il problema in forma matriciale, ponendo
B :=
A 00 −At
−f bt
∈ R
m+n+1m+n e c :=
b−f t
0
∈ R
m+n+1
dobbiamo dimostrare che (BRm+n+ ≤ c) 6= ∅.
(4) Ma per la prop.1.28 in caso contrario esiste p ∈ R+m+n+1 tale che
pB ≥ 0 e pc < 0.
p e quindi della forma p = (g h α) con g ∈ R+m, h ∈ R
+n ed α ∈ R
+.Inoltre
14
pB = (g h α)
A 00 −At
−f bt
= (gA − αf − hAt + αbt) ≥ 0
e
pc = (g h α)
b−f t
0
= gb − hf t < 0
cosicche otteniamo
(I) gA ≥ αf
(II) αbt ≥ hAt
(III) gb < hf t
Essendo α ∈ R+, abbiamo α = 0 oppure α > 0. Dimostriamo che entr-
ambi i casi implicano una contraddizione.
(5) Sia α = 0. Allora gA ≥ 0 ≥ hAt. Per ipotesi gli insiemi (ARn+ ≤ b)
e (R+mA ≥ f) sono entrambi non vuoti. Percio esistono x ∈ R
n+ ed
u ∈ R+m tali che Ax ≤ b ed uA ≥ f , quindi anche Atut ≥ f t. Ma allora
gb ≥ gAx ≥ 0 ≥ hAtut ≥ hf t
e questo contraddice la disuguaglianza (III).
(6) Rimane il caso α > 0. Le disuguaglianze (I) e (II) significano pero
cheg
α∈ (R+
mA ≥ f) eht
α∈ (AR
n+ ≤ b).
Dal lemma 2.5 segue fht
α≤
g
αb ovvero hf t = fht ≤ gb, ancora in
contrasto con (III).
Corollario 2.10. Siano x ∈ (ARn+ ≤ b) ed u ∈ (R+
mA ≥ f). Allora sono
equivalenti:
(1) x e una soluzione di f(ARn+ ≤ b) = max ed u una soluzione di
(R+mA ≥ f)b = min.
(2) fx = ub.
(3) fx = uAx = ub.
(4) fx ≥ ub.
Dimostrazione. (1) =⇒ (2): Teorema 2.9.
(2) =⇒ (3): Per il lemma 2.5 si ha fx ≤ uAx ≤ ub, ma essendo peripotesi fx = ub segue che fx = uAx = ub.
(3) =⇒ (4): Chiaro.
(4) =⇒ (1): Proposizione 2.6.
15
Nota 2.11. Come nella dimostrazione del teorema 2.9 siano
B :=
A 00 −At
−f bt
∈ R
m+n+1m+n e c :=
b−f t
0
∈ R
m+n+1.
(1) Sia z ∈ (BRm+n+ ≤ c) con z =
(xy
), x ∈ R
n+ ed y ∈ R
m+ .
Se poniamo u := yt, allora x e una soluzione di f(ARn+ ≤ b) = max ed u
e una soluzione di (R+mA ≥ f)b = min.
(2) Siano viceversa x una soluzione di f(ARn+ ≤ b) = max ed u una
soluzione di (R+mA ≥ f)b = min. Allora con y := ut abbiamo
z :=
(xy
)∈ (BR
m+n+ ≤ c).
Dimostrazione. Siano z, x, y, u come nell’enunciato. Abbiamo quindile seguenti disuguaglianze:
x ≥ 0, y ≥ 0
Ax ≤ b
−Atut ≤ −f t
−fx + btut ≤ 0
La terza disuguaglianza e equivalente ad uA ≥ f , la quarta, essendobtut = ub, e equivalente a fx ≥ ub.
Il punto (1) segue adesso dalla prop. 2.6, il punto (2) combinando ilteorema 2.9 con la prop. 2.6.
Osservazione 2.12. Il teorema 2.9 e la nota 2.11 dimostrano l’importanzae l’utilita del principio di dualita nella programmazione lineare. Vedia-mo in particolare che la sola ricerca di un punto ammissibile (senza uncompito di massimizzazione o minimizzazione) non e piu facile dellasoluzione del problema di ottimizzazione che, come visto nella nota2.11, puo essere ricondotta alla ricerca di un punto ammissibile.
Esempio 2.13. Consideriamo il seguente problema di massimo:
x1 + 2x2 = max
7x1 + 4x2 ≤ 28
4x1 + 5x2 ≤ 20
3x1 + 10x2 ≤ 30
Per la nota 2.11 questo problema di ottimizzazione e equivalente aquello della ricerca di un punto
z =
x1
x2
y1
y2
y3
che soddisfa la disuguaglianza
16
7 4 0 0 04 5 0 0 03 10 0 0 00 0 −7 −4 −30 0 −4 −5 −3−1 −2 28 20 30
x1
x2
y1
y2
y3
≤
282030−1−20
Corollario 2.14. (1) x sia una soluzione di f(ARn+ ≤ b) = max
e 1 ≤ k ≤ m. Se esiste una soluzione u di (R+mA ≥ f)b = min tale che
uk 6= 0, allora Akx = bk.
(2) u sia una soluzione di (R+mA ≥ f)b = min e 1 ≤ k ≤ n. Se esiste
una soluzione x di f(ARn+ ≤ b) = max tale che xk 6= 0, allora uAk = fk.
Dimostrazione. Dimostriamo solo il primo enunciato, essendo il se-condo il suo duale.
Per il corollario 2.10 uAx = ub, e quindi u(b − Ax) = 0, cioem∑
j=1
uj(bj − Ajx) = 0. Per ipotesi pero u ≥ 0 e b − Ax ≥ 0, quindi
uj(bj − Ajx) ≥ 0 per ogni j = 1, ...,m. Ma allora necessariamente
uj(bj − Ajx) = 0 per ogni j = 1, ...,m, per cui l’ipotesi uk 6= 0 implica
bk − Akx = 0.
17
3. Programmi lineari in forma normale
Situazione 3.1. n,m ∈ N + 1 ed A ∈ Rmn , f ∈ Rn, b ∈ R
m, quando nonindicato diversamente.
Definizione 3.2. Un programma lineare di massimizzazione (risp. mi-
nimizzazione) in forma normale e un problema di ottimizzazione dellaforma
fx = max (risp. min)
x ≥ 0
Ax = b
con A, f , b come nella situazione 3.1. Gli elementi di (ARn+ = b) sono
detti punti ammissibili.
Nota 3.3. (1) Sia dato un problema f(ARn+ ≤ b) = max in forma stan-
dard. Introducendo un vettore variabile ausiliario p otteniamo un pro-blema in forma normale
(f 0)
(xp
)= max
(xp
)≥ 0
(A δ)
(xp
)= b
equivalente al primo, nel senso che da ogni soluzione del problema informa normale otteniamo una soluzione del problema in forma stan-dard.
(2) Viceversa, dato un problema f(ARn+ = b) = max in forma norma-
le, considerando
fx = max
x ≥ 0
Ax ≤ b
−Ax ≤ −b
otteniamo un problema in forma standard equivalente al primo, nelsenso che da ogni soluzione del problema in forma standard otteniamouna soluzione del problema in forma normale.
(3) In modo analogo (usando le matrici trasposte) ogni problema diminimizzazione in forma standard (def. 2.3) e equivalente ad un pro-blema in forma normale e viceversa.
Osservazione 3.4. V e W siano spazi vettoriali reali, ϕ : V −→ Wun’applicazione affine ed Y sia un sottoinsieme convesso di W .Allora ϕ−1(Y ) e convesso.
Dimostrazione. Siano a, b ∈ ϕ−1(Y ), cioe ϕ(a), ϕ(b) ∈ Y . Per l’oss. 1.8pero ϕ([a, b]) = [ϕ(a), ϕ(b)] ⊂ Y e quindi, utilizzando l’ipotesi che Y siaconvesso, si ha che [a, b] ⊂ ϕ−1(Y ).
18
Corollario 3.5. L’insieme (ARn+ = b) e chiuso e convesso.
Dimostrazione. Identificando A con l’applicazione ©x
Ax possiamo
scrivere (ARn+ = b) = A−1(b)∩R
n+. Poiche A e continua, l’insieme A−1(b)
e chiuso. Inoltre, essendo A un’applicazione affine e b un convesso, perl’oss. 3.4 anche A−1(b) e convesso. Infine R
n+ e un chiuso convesso e,
siccome l’intersezione di insiemi chiusi e convessi e ancora chiuso econvesso, otteniamo l’enunciato.
Definizione 3.6. V sia uno spazio vettoriale reale ed X un suo sotto-insieme convesso. Un vertice (o punto estremale) di X e un punto x ∈ Xche soddisfa la seguente condizione:
Se u, v ∈ X ed x ∈ [u, v], allora x ∈ u, v
Denotiamo con vertici(X) l’insieme dei vertici di X.
Esempio 3.7.
(1) X sia un poligono convesso in R2. I vertici di X nel senso della
geometria elementare coincidono con i vertici nel senso delladefinizione 3.6.
(2) vertici(Rn) = ∅.
(3) vertici(Rn+) = 0.
(4) X := z ∈ Rn | |z| ≤ 1 sia la palla unitaria chiusa in R
n. Alloravertici(X) = z ∈ R
n | |z| = 1.
(5) X := z ∈ Rn | |z| < 1 sia la palla unitaria aperta in R
n. Alloravertici(X) = ∅.
Lemma 3.8. V sia uno spazio vettoriale reale, X un sottoinsieme con-
vesso di V ed x ∈ X. Allora sono equivalenti:
(1) x ∈ vertici(X).
(2) X \ x e convesso.
(3) x =u + v
2con u, v ∈ X implica u = v.
Dimostrazione. (1) =⇒ (2): Supponiamo per assurdo che esistanou, v ∈ X\x tali che [u, v] 6⊂ X\x. Allora x ∈ [u, v], ma per ipotesi cioimplica che x ∈ u, v. Quindi ad esempio u = x, una contraddizione.
(2) =⇒ (1): X \ x sia convesso ed u, v ∈ X con x ∈ [u, v]. Dobbiamodimostrare che x ∈ u, v. Se cosı non fosse avremmo u, v ∈ X \ x equindi per ipotesi [u, v] ⊂ X \ x, una contraddizione.
(1) =⇒ (3): Sia 2x = u + v con u, v ∈ X. Per ipotesi x ∈ u, v, adesempio x = u. Allora x = v e quindi u = v.
(3) =⇒ (1): Siano u, v ∈ X ed x = u + t(v − u) con t ∈ [0, 1].
Per t = 0 e t = 1 si ha rispettivamente x = u e x = v.
19
Per t =1
2l’ipotesi implica u = v e quindi x = u = v.
Rimangono i casi 0 < t <1
2e
1
2< t < 1. Per simmetria e sufficiente
trattare il caso 0 < t <1
2.
Poniamo y := u + 2t(v − u). Allora y ∈ X perche 0 < 2t < 1. Inoltre
y = u + 2(x − u) = 2x − u, cosicche x =u + y
2. L’ipotesi implica u = y e
quindi x = u.
u y vx =
u + y
2
Definizione 3.9. Sia α ⊂ 1, ..., n un sottoinsieme di cardinalita|α| = s. Poniamo allora:
(1) Aα := matrice in Rms che si ottiene da A cancellando tutte le
colonne Aj per cui j /∈ α.
(2) fα := vettore in Rs che si ottiene da f cancellando gli elementifj per cui j /∈ α.
(3) Per x ∈ Rn sia xα il vettore in R
s che si ottiene da x cancellandogli elementi xj per cui j /∈ α.
Poniamo inoltre 1 − α := 1, ..., n \ α.
Per s = 0 abbiamo Rm0 = R
0 = R0 = 0, per cui A∅ = f∅ = x∅ = ∅.
Con queste convenzioni possiamo scrivere
Ax = Aαxα + A1−αx1−α
fx = fαxα + f1−αx1−α
Esempio 3.10. Siano A ∈ R35 ed x ∈ R
5. Con α = 1, 4 si ha1 − α = 2, 3, 5. Percio
Aαxα + A1−αx1−α =
A11 A1
4
A21 A2
4
A31 A3
4
(x1
x4
)+
A12 A1
3 A15
A22 A2
3 A25
A32 A3
3 A35
x2
x3
x5
=
A11x
1 + A14x
4
A21x
1 + A24x
4
A31x
1 + A34x
4
+
A12x
2 + A13x
3 + A15x
5
A22x
2 + A23x
3 + A25x
5
A32x
2 + A33x
3 + A35x
5
= Ax
Definizione 3.11. Per x ∈ Rn sia [x] := i ∈ 1, ..., n | xi 6= 0.
Osservazione 3.12. 0 ∈ vertici(ARn+ = 0).
Dimostrazione. Usiamo il lemma 3.8. Siano u, v ∈ (ARn+ = 0) e tali
che 0 =u + v
2. E chiaro che cio implica u = v = 0.
20
Teorema 3.13. Per x ∈ (ARn+ = b) sono equivalenti:
(1) x ∈ vertici(ARn+ = b).
(2) Le colonne di A[x] sono linearmente indipendenti.
Dimostrazione. Se x = 0, allora [x] = ∅ e l’enunciato segue dall’oss.3.9, perche l’insieme vuoto e linearmente indipendente. Possiamo quin-di assumere che x 6= 0 e che [x] = 1, ..., s con 1 ≤ s ≤ n.
(1) =⇒ (2): Sia x ∈ vertici(ARn+ = b) e sia λ1A1 + ... + λsAs = 0
una combinazione lineare delle colonne Ai con i ∈ [x] e λi ∈ R peri = 1, ..., s. Supponiamo per assurdo che i λi non siano tutti nulli, adesempio possiamo supporre λ1 6= 0. Siccome xi > 0 per ogni i = 1, . . . , s,possiamo trovare un elemento ε > 0 tale che xi ± ελi ≥ 0 per ognii = 1, ..., s. Definiamo i vettori
u :=
x1 + ελ1...
xs + ελs
0...0
e v :=
x1 − ελ1...
xs − ελs
0...0
Allora u, v ∈ Rn+ ed x =
u + v
2.
Inoltre Au =s∑
k=1
Ak(xk + ελk) = Ax + ε
s∑k=1
λkAk = Ax = b, e simil-
mente Av = b. Percio u, v ∈ (ARn+ = b). Per ipotesi x ∈ vertici(AR
n+ = b)
e quindi per il punto (3) della prop. 3.8 risulta u = v. Ma cio non epossibile perche λ1 6= 0.
(2) =⇒ (1): Le colonne di A[x] siano linearmente indipendenti. Siano
u, v ∈ (ARn+ = b) tali che x =
u + v
2. Cio implica ui + vi = 0 per ogni
i = 1, . . . , s, e quindi ui = vi = 0, essendo u, v ≥ 0. D’altra parte abbia-
mo Au = Av = b e quindi 0 = A(u − v) =s∑
i=1(ui − vi)Ai. Per ipotesi cio
implica ui = vi per ogni i = 1, . . . , s, e quindi u = v. Per la prop. 3.8quindi risulta che x ∈ vertici(AR
n+ = b).
Definizione 3.14. Sia α ⊂ 1, ..., n. A si dice α-invertibile, se|α| = m ≤ n e la matrice quadratica Aα e invertibile.
Osservazione 3.15. Un insieme di indici α tale che A sia α-invertibileesiste se e solo se rango(A) = m. Si noti che rango(A) = m da soloimplica m ≤ n.
Lemma 3.16. K sia un campo e V uno spazio vettoriale su K. Siano
v1, . . . , vn ∈ V e W := SV(v1, . . . , vn). Siano m := dimW e 1 ≤ s ≤ mtali che i vettori v1, . . . , vs siano linearmente indipendenti.
21
Allora possiamo trovare m − s indici j1, . . . , jm−s ∈ s + 1, . . . , n in
modo tale che gli m vettori v1, . . . , vs, vj1 , . . . , vjm−ssiano linearmente
indipendenti.
Dimostrazione. (1) Se s = m non c’e nulla da dimostrare.
Supponiamo quindi che s < m e dimostriamo che esiste un indicej ∈ s+1, . . . , n tale che gli s+1 vettori v1, . . . , vs, vj sono linearmenteindipendenti.
Infatti, se cosı non fosse, avremmo vj ∈ SV(v1, . . . , vs) per ognij ∈ 1, . . . , n e quindi W = SV(v1, . . . , vs) in contraddizione all’ipotesidim W = m.
(2) Se adesso s + 1 = m, non c’e piu nulla da dimostrare. Altrimentiripetiamo il ragionamento con s + 1 al posto di s.
Corollario 3.17. x sia un vertice di (ARn+ = b).
Se rango(A) = m, allora [x] e contenuto in un insieme di indici α tali
che A sia α-invertibile.
Osservazione 3.18. Sia x ∈ (ARn+ = b) ed [x] contenuto in un insieme
di indici α tali che A sia α-invertibile. Allora abbiamo x1−α = 0 e quindib = Ax = Aαxα + A1−αx1−α = Aαxα, per cui xα = A−1
α b. Percio x eunivocamente determinato dalle relazioni
xα = A−1α b
x1−α = 0
Definizione 3.19. Sia rango(A) = m. Poniamo
J(A) := α ⊂ 1, ..., n | |α| = m ed Aα invertibile
J+(A, b) := α ∈ J(A) | A−1α b ≥ 0
Proposizione 3.20. Sia rango(A) = m. Allora l’applicazione
θ : J+(A, b) −→ vertici(ARn+ = b) definita da θ(α) = x con
xα = A−1α b
x1−α = 0
e suriettiva.
Dimostrazione. Cio segue dall’oss. 3.18 e dal cor. 3.17.
Corollario 3.21. Sia rango(A) = m. Allora l’insieme dei vertici di(AR
n+ = b) e finito.
Dimostrazione. J+(A, b) e finito e quindi, poiche l’immagine di uninsieme finito e finito, anche vertici(AR
n+ = b) e un insieme finito.
Proposizione 3.22. Sia (ARn+ = b) 6= ∅. Allora vertici(AR
n+ = b) 6= ∅.
Dimostrazione. Scegliamo x ∈ (ARn+ = b) in modo tale che |[x]| sia
minimale.
(1) Se x = 0, allora b = 0 ed x ∈ vertici(ARn+ = b) per l’oss. 3.12.
22
(2) Sia quindi x 6= 0. Poniamo α := [x]. Dobbiamo dimostrare che lecolonne di Aα sono linearmente indipendenti. Supponiamo che non losiano. Allora possiamo trovare un vettore λ ∈ R
s \ 0 tale che Aαλ = 0.Possiamo assumere che almeno uno dei coefficienti di λ sia minore di 0.Siccome xi > 0 per ogni i ∈ α, esiste ε > 0 tale che xi + ελi ≥ 0 per ognii ∈ α ed xh + ελh = 0 per almeno un h ∈ α. Sia ora y ∈ R
n+1 definitodalle relazioni
yα = xα + ελ
y1−α = 0
Allora y ≥ 0, inoltre
Ay = Aαyα + A1−αy1−α = Aαyα = Aα(xα + ελ)
= Aαxα + εAαλ = Aαxα = Ax = b
Quindi y ∈ (ARn+ = b) e |[y]| < |[x]|, una contraddizione al fatto che
abbiamo scelto x in modo tale che |[x]| sia minimale.
Osservazione 3.23. Il problema f(ARn+ = b) = max abbia una
soluzione. Se poniamo µ := max f(ARn+ = b), allora con
B :=
(Af
), c :=
(bµ
)
si ha (f(ARn+ = b) = max) = (BR
n+ = c).
Per il cor. 3.5 l’insieme (f(ARn+ = b) = max) e percio chiuso e conves-
so (cio e banalmente vero anche quando e vuoto).
Proposizione 3.24.
vertici(f(ARn+ = b) = max) = (f(AR
n+ = b) = max) ∩ vertici(AR
n+ = b)
Dimostrazione. (1) Se il problema f(ARn+ = b) = max non ha solu-
zione, l’enunciato e banalmente vero.
(2) Altrimenti con µ := max f(ARn+ = b) poniamo P := (AR
n+ = b),
R := (fRn+ = µ). Allora (f(AR
n+ = b) = max) = P ∩R, per cui dobbiamo
dimostrare che vertici(P ∩ R) = P ∩ R ∩ vertici(P ). Adesso usiamo illemma 3.8.
Sia x ∈ vertici(P ∩R). Dobbiamo dimostrare che x ∈ vertici(P ). Siano
u, v ∈ P tali che x =u + v
2. Pero fu ≤ µ, fv ≤ µ, e se ad esempio
fu < µ, si avrebbe fx =fu + fv
2< µ. Percio fu = fv = µ, cosicche
u, v ∈ P ∩ R, e quindi u = v, perche x ∈ vertici(P ∩ R).
Viceversa, sia x ∈ P ∩ R ∩ vertici(P ). Siano u, v ∈ P ∩ R tali che
x =u + v
2. Allora u = v perche x ∈ vertici(P ). Quindi x ∈ vertici(P ∩R).
Teorema 3.25 (teorema fondamentale della programmazione
lineare). Se il problema f(ARn+ = b) = max possiede una soluzione,
allora esiste anche una soluzione che e un vertice di (ARn+ = b).
Dimostrazione. Con le notazioni dell’oss. 3.23, dalla prop. 3.24 ab-biamo (f(AR
n+ = b) = max) ∩ vertici(AR
n+ = b) = vertici(BR
n+ = c).
23
Siccome per ipotesi l’insieme (BRn+ = c) = (f(AR
n+ = b) = max) non e
vuoto, dalla prop. 3.22 segue che anche vertici(BRn+ = c) 6= ∅.
Nota 3.26. Mediante l’algoritmo di eliminazione di Gauss possiamosempre ottenere la condizione rango(A) = m richiesta nella prop. 3.20e nel corollario 3.21. L’insieme dei vertici di (AR
n+ = b) allora e finito
e per il teorema 3.25 una soluzione del problema di massimo si trovapercorrendo tutti i vertici e calcolando max fx | x ∈ vertici(AR
n+ = b).
Il numero dei vertici e pero molto alto gia in problemi di modeste di-mensioni, per cui e necessario un algoritmo migliore, il metodo del
simplesso, che verra presentato nel prossimo capitolo.
Esempio 3.27. Consideriamo il problema di massimo
3x1 + x2 − x3 + 2x4 − 2x5 + x6 = max
3x1 + 2x2 − 5x3 + 4x4 − x5 − x6 = 18
x1 − x2 − x3 + 4x4 − 6x5 + x6 = 15
che possiamo scrivere nella solita forma
fx = max
Ax = b
x ≥ 0
con
f :=(
3 1 −1 2 −2 1)
A :=
(3 2 −5 4 −1 −11 −1 −1 4 −6 1
)
b :=
(1815
)
Chiaramente rango(A) = 2. Per applicare l’idea della nota 3.26 dob-
biamo considerare le
(62
)= 15 sottomatrici 2 × 2 Aα di A e calcolare
xα = A−1α b ogni volta che Aα sia invertibile. Se xα ≥ 0, calcoliamo fαxα.
Il massimo dei valori cosı ottenuti e il massimo cercato. Alla pagina se-guente riportiamo la tabella con i calcoli effettuati. Il valore massimoche si ottiene e 81.
24
α Aα A−1α xα = A−1
α b x fx
1,2
(3 21 −1
)−1
5
(−1 −2−1 3
) (48/5−27/5
) (48/5−27/5
)
1,3
(3 −51 −1
)12
(−1 5−1 3
) (57/227/2
) (57/227/2
)72
1,4
(3 41 4
)18
(4 −4−1 3
) (3/227/8
) (3/227/8
)45/4
1,5
(3 −11 −6
)− 1
17
(−6 1−1 3
) (93/17−27/17
) (93/17−27/17
)
1,6
(3 −11 1
)14
(1 1−1 3
) (33/427/4
) (33/427/4
)63/2
2,3
(2 −5−1 −1
)−1
7
(−1 51 2
) (−57/7−48/7
) (−57/7−48/7
)
2,4
(2 4−1 4
)112
(4 −41 2
) (14
) (14
)9
2,5
(2 −1−1 −6
)− 1
13
(−6 11 2
) (93/13−48/13
) (93/13−48/13
)
2,6
(2 −1−1 1
) (1 11 2
) (3348
) (3348
)81
3,4
(−5 4−1 4
)− 1
16
(4 −41 −5
) (−3/457/16
) (−3/457/16
)
3,5
(−5 −1−1 −6
)129
(−6 11 −5
) (−93/29−57/29
) (−93/29−57/29
)
3,6
(−5 −1−1 1
)−1
6
(1 11 −5
) (−11/257/6
) (−11/257/6
)
4,5
(4 −14 −6
)− 1
20
(−6 1−4 4
) (93/203/5
) (93/203/5
)18
4,6
(4 −14 1
)18
(1 1−4 4
) (33/8−3/2
) (33/8−3/2
)
5,6
(−1 −1−6 1
)−1
7
(1 16 −1
) (−33/7−53/7
) (−33/7−53/7
)
25
4. Il metodo del simplesso
Situazione 4.1. n,m ∈ N + 1 ed A ∈ Rmn , f ∈ Rn, b ∈ R
m.Supponiamo inoltre che rango(A) = m.
Definizione 4.2. Per x ∈ Rn sia J(x,A) := α ∈ J(A) | [x] ⊂ α.
Osservazione 4.3. Sia x ∈ (ARn+ = b). Allora
x ∈ vertici(ARn+ = b) ⇐⇒ J(x,A) 6= ∅
Dimostrazione. (1) Sia x ∈ vertici(ARn+ = b). Poiche rango(A) = m,
dal corollario 3.17 segue che J(x,A) 6= ∅.
(2) Sia α ∈ J(A) con [x] ⊂ α. Allora le colonne di Aα sono linearmenteindipendenti e quindi anche le colonne di A[x] lo sono. Per il teorema3.13 si ha che x ∈ vertici(AR
n+ = b).
Lemma 4.4. Siano x, y ∈ (ARn = b) ed α ∈ J(x,A). Allora
fy = fx + (f − fαA−1α A)1−αy1−α
Dimostrazione. L’ipotesi implica xα = A−1α b ed x1−α = 0.
Inoltre b = Ay = Aαyα + A1−αy1−α, per cui
yα = A−1α b − A−1
α A1−αy1−α = xα − A−1α A1−αy1−α
cosicche
fy = fαyα + f1−αy1−α = fαxα − fαA−1α A1−αy1−α + f1−αy1−α
= fx + (f − fαA−1α A)1−αy1−α
Corollario 4.5. Siano x ∈ (ARn+ = b) ed α ∈ J(x,A) tali che
(f − fαA−1α A)1−α ≤ 0.
Allora x e una soluzione del problema f(ARn+ = b) = max.
Dimostrazione. Infatti dal lemma 4.4 si ha che fy ≤ fx per ogniy ∈ (AR
n+ = b).
Definizione 4.6. Siano x ∈ Rn ed α ∈ J(x,A).
Per j ∈ 1 − α e t ∈ R definiamo x(t, j, α) ∈ Rn mediante
xα(t, j, α) := xα − tA−1α Aj
xj(t, j, α) := t
xi(t, j, α) := 0 per i ∈ (1 − α) \ j
Osservazione 4.7. Siano x ∈ (ARn = b), α ∈ J(x,A), j ∈ 1−α e t ∈ R.
Allora:
(1) Ax(t, j, α) = b.
(2) fx(t, j, α) = fx + t(fj − fαA−1α Aj).
(3) x(0, j, α) = x.
26
Dimostrazione.
(1) Ax(t, j, α) = Aαxα(t, j, α) + A1−αx1−α(t, j, α)
= Aα(xα − tA−1α Aj) + Ajx
j(t, j, α)
= Aαxα − tAj + tAj = Aαxα = b
(2) Per il punto (1) possiamo applicare il lemma 4.4, ottenendo
fx(t, j, α) = fx + (f − fαA−1α A)1−αx1−α(t, j, α)
= fx + t(f − fαA−1α A)j = fx + t(fj − fαA−1
α Aj)
(3) Chiaro.
Corollario 4.8. Nelle ipotesi dell’oss. 4.7 sia fj − fαA−1α Aj > 0.
Allora fx(t, j, α) > fx per ogni t > 0.
Proposizione 4.9. Siano x ∈ (ARn+ = b), α ∈ J(x,A), j ∈ 1 − α ed
fj − fαA−1α Aj > 0. Se A−1
α Aj ≤ 0, allora il problema f(ARn+ = b) = max
non possiede soluzioni.
Dimostrazione. Per l’oss. 4.7 limt−→∞
fx(t, j, α) = ∞. Dobbiamo pero ve-
rificare che x(t, j, α) ≥ 0 per ogni t ≥ 0. Ma per t ≥ 0 l’ipotesi A−1α Aj ≤ 0
implica
x(t, j, α) = xα(t, j, α) + x1−α(t, j, α)
= xα − tA−1α Aj + xj(t, j, α) = xα − tA−1
α Aj + t ≥ 0
Nota 4.10. Siano x ∈ vertici(ARn+ = b), α ∈ J(x,A), j ∈ 1 − α e
w := A−1α Aj ∈ R
m. Scriviamo α nella forma α = α1, . . . , αm.Assumiamo che fj−fαw > 0 e che esista almeno un indice i ∈ 1, . . . ,mtale che wi > 0. Siano t := minxαi/wi | i ∈ 1, . . . ,m, wi > 0, ad es-
empio t =xαk
wk, e β := (α ∪ j) \ αk. Allora:
(1) |β| = m.
(2) [x(t, j, α)] ⊂ β.
(3) β ∈ J(A).
(4) x(t, j, α) ∈ vertici(ARn+ = b).
(5) Se t > 0, allora fx(t, j, α) > fx.
Dimostrazione. (1) Chiaro.
(2) Bisogna dimostrare che xαk(t, j, α) = 0.Ma xαk(t, j, α) = xαk − twk = 0.
(3) Dobbiamo dimostrare che le colonne di A[β] sono linearmenteindipendenti. Possiamo assumere che α = 1, . . . ,m, k = m ej > m. In particolare allora wm > 0.
Siano λ1, . . . , λm−1, λj ∈ R tali che λ1A1 + . . .+λm−1Am−1 +λjAj = 0.Pero Aj = Aαw, per cui abbiamo
27
0 = λ1A1 + . . . + λm−1Am−1 + λjAαw
= λ1A1 + . . . + λm−1Am−1 + λj(A1w1 + . . . + Amwm)
= (λ1 + λjw1)A1 + . . . + (λm−1 + λjw
m−1)Am−1 + λjwmAm
Siccome le colonne di α sono linearmente indipendenti, segue cheλ1 + λjw
1 = . . . = λm−1 + λjwm−1 = λjw
m = 0. Ma wm 6= 0 e quindiλj = 0 e cio a sua volta implica λ1 = . . . = λm−1 = 0.
(4) Teorema 3.13 (oppure oss. 4.3).
(5) Cio segue dal cor. 4.8.
Definizione 4.11. Un vertice di (ARn+ = b) si dice non degenere se
|[x]| = m.
Osservazione 4.12. Sia x ∈ (ARn+ = b). Allora sono equivalenti:
(1) x e un vertice non degenere di (ARn+ = b).
(2) J(x,A) = [x].
Dimostrazione. Chiaro per l’oss. 4.3, perche per ogni α ∈ J(x,A) vale|α| = m.
Teorema 4.13. x sia un vertice non degenere di (ARn+ = b).
Sia α := [x] = α1, . . . , αm. Allora:
(1) Se (f − fαA−1α A)1−α ≤ 0, allora x e una soluzione del problema
f(ARn+ = b) = max.
(2) Altrimenti esiste j ∈ 1 − α tale che fj − fαA−1α Aj > 0.
In questo caso poniamo w := A−1α Aj .
Se w ≤ 0, allora il problema f(ARn+ = b) = max non possiede
soluzioni.
Altrimenti, posto t := minxαi/wi | i ∈ 1, . . . ,m, wi > 0, si ha
fx(t, j, α) > fx.
Dimostrazione. (1) Cor. 4.5.
(2) Il caso w ≤ 0 segue dalla prop. 4.9. Se non vale w ≤ 0, per la nota4.10 e sufficiente dimostrare che t > 0. Ma per ipotesi α = [x], per cuixαi > 0 per ogni i ∈ 1, . . . ,m, cosicche anche t > 0.
Nota 4.14. L’algoritmo del simplesso per la risoluzione del problemadi massimo f(AR
n+ = b) = max puo cosı essere formulato nel modo
seguente (x e un vertice non degenere di (ARn+ = b)):
(1) α = [x] (necessariamente |α| = m). Scriviamo α = α1, . . . , αmcon α1 < . . . < αm.
(2) β = 1 − α.
(3) g = fαA−1α .
28
(4) Determiniamo il piu piccolo indice j ∈ 1 − α tale che fj > gAj ,se un tale j esiste.
(5) Se j non esiste, x e un punto di massimo, l’algoritmo restituiscex e termina.
(6) w = A−1α Aj ; t = ∞. Cerchiamo l’insieme I := i ∈ α | wi > 0.
(7) Per i = 1, . . . ,m controlliamo se wi > 0; in tal caso sia s = xαi/wi
e se s < t, allora poniamo t = s e k = i.
(8) Se dopo il ciclo in (7) risulta ancora t = ∞, allora il problemanon possiede soluzione e viene restituito il valore ∞ (o un altrovalore che esprime la non risolubilita).
(9) x = x(t, j, α).
(10) α = (α \ αk) ∪ j.
(11) Torniamo al punto (2).
La scelta di j e k nei punti (4) e (7) porta il nome di regola di Bland
e garantisce che l’algoritmo termina sempre e non incorre in cicli in-finiti; una dimostrazione si trova ad esempio in Geiger/Kanzow, pagg.108-111.
Nota 4.15. Traduciamo l’algoritmo in Octave (o in Matlab):
function y=simplesso(A,b,f,x,mostra=0)
n=length(x);alfa=find(x)’;
while 1
if mostra X=x’, Ax=(A*x)’ endif
beta=complement(alfa,1:n);
f_alfa=f(alfa); A_alfa=A(:,alfa); g=f_alfa/A_alfa;
trovatoj=0;
for j=beta Aj=A(:,j);
if f(j)>g*Aj trovatoj=1;break; endif; endfor
if !trovatoj y=x; break; endif
w=A_alfa\Aj; t=Inf;
for i=1:length(alfa)
if w(i)>0 s=x(alfa(i))/w(i);
if s<t t=s; k=i; endif; endif; endfor
if t==Inf y=Inf; break; endif
x=sostituzione(x,t,j,alfa,w,n);
alfa=union(complement(alfa(k),alfa),j);
endwhile; end
function y=sostituzione(x,t,j,alfa,w,n)
y=zeros(n,1); y(alfa)=x(alfa)-t*w; y(j)=t;
end
Osservazione 4.16. Octave per il calcolo di programmi lineari preve-de la funzione glpk; cfr. Eaton/Bateman/Hauberg, pagg. 339-345.
29
Osservazione 4.17. Quando il problema e dato nella forma standard,
fx = max
x ≥ 0
Ax ≤ b
con la tecnica della nota 3.3 la possiamo trasformare in forma normale
(f 0)
(xp
)= max
(xp
)≥ 0
(A δ)
(xp
)= b
In questo caso il vettore
(0b
)e un vertice non degenere del nuovo
problema e possiamo applicare l’algoritmo della nota 4.14.
Osservazione 4.18. Consideriamo adesso un problema della forma
fx = max
x ≥ 0
Ax = b
con A, f, b definiti come in precedenza. Esso evidentemente e equiva-lente al problema
fx−∞u1 − . . . −∞um = max
x ≥ 0, u ≥ 0
Ax + u = b
dove con ∞ calcoliamo in modo naturale. ∞ in Matlab (o Octave) vienerappresentato da Inf e i calcoli vengono eseguiti correttamente.
Cio ci permette di applicare di nuovo l’algoritmo del simplesso. Unadimostrazione dettagliata si trova in Geiger/Kanzow, pagg. 111-115.
30
5. Geometria elementare degli insiemi convessi
Nota 5.1. V sia uno spazio vettoriale reale. Continuiamo la discus-sione delle proprieta geometriche elementari degli insiemi convessiiniziata nel primo capitolo.
Definizione 5.2. Usiamo le notazioni introdotte in precedenza e po-niamo inoltre:
Rn++ := x ∈ R
n | x > 0
R++m := f ∈ Rm | f > 0
Rnstoc := λ = (λ1, . . . , λn) ∈ R
n+ |
n∑
h=1
λh = 1
La condizione x > 0 significa che xh > 0 per ogni h; la condizione f > 0e definita similmente.
Rnstoc e l’insieme dei vettori stocastici in R
n.
Per un sottoinsieme A di uno spazio topologico sia int A l’interno di A.
Lemma 5.3. Siano a, x ∈ Rm e t, ρ ∈ R
++. Allora
a + t(|Rm − x| < ρ) = (|Rm − (a + tx)| < tρ)
Dimostrazione. Per y ∈ Rm sono equivalenti:
(1) |y − (a + tx)| < tρ
(2) |y−at
− x| < ρ
(3) y−at
∈ (|Rm − x| < ρ)
(4) y ∈ a + t(|Rm − x| < ρ)
Proposizione 5.4. X sia un sottoinsieme convesso di Rm.
Allora anche int X e X sono convessi.
Dimostrazione. (1) Siano x, y ∈ int X e t ∈ (0, 1). Allora esiste ρ > 0tale che (|Rm−x| < ρ) ⊂ X. Sia z := tx+(1−t)y. Dobbiamo dimostrareche z ∈ int X. Usando la convessita di X e il lemma 5.3 con a = (1− t)ysi ha che
X ⊃ (1 − t)y + t(|Rm − x| < ρ)5.3= (|Rm − ((1 − t)y + tx)| < tρ) =
(|Rm − z| < tρ)
Abbiamo quindi trovato un intorno aperto di z contenuto in X per cuiz ∈ intX.
(2) Siano u, v ∈ X e t ∈ [0, 1]. Allora esistono due successioni x, y inX tali che x −→ u, y −→ v. Cio implica tx+(1−t)y −→ tu+(1−t)v =: z.Per la convessita di X pero gli elementi di tx + (1 − t)y appartengonotutti ad X e quindi z ∈ X.
31
Definizione 5.5. Per sottoinsiemi X,Y di V e λ ∈ R poniamo:
X + Y := x + y | x ∈ X, y ∈ Y
λX := λx | x ∈ X
Osservazione 5.6. X ed Y siano sottoinsiemi convessi di V e siaλ ∈ R. Allora anche gli insiemi X + Y e λX sono convessi.
Dimostrazione. (1) Cio e evidente per λX.
(2) Siano u1, u2 ∈ X + Y . Allora esistono x1, x2 ∈ X e y1, y2 ∈ Y taliche u1 = x1 + y1 e u2 = x2 + y2. Per t ∈ [0, 1] allora
tx1 + (1 − t)x2 ∈ X e ty1 + (1 − t)y2 ∈ Y , per cui
tu1 + (1 − t)u2 = t(x1 + y1) + (1 − t)(x2 + y2)
= (tx1 + (1 − t)x2) + (ty1 + (1 − t)y2) ∈ X + Y
X Y
X + Y
Definizione 5.7. Un cono di V e un sottoinsieme non vuoto X di Vtale che λX ⊂ X per ogni λ > 0.
Esempio 5.8. Gli insiemi Rm+ e R
m++ sono coni convessi di R
m.
L’insieme (R+ × 0) ∪ (0 × R+) in R
2 (l’unione dei due semiassi dellecoordinate) e un cono, ma non e convesso.
Osservazione 5.9. X sia un cono di V .
Allora X e convesso se e solo se X + X ⊂ X.
Dimostrazione. Siano x, y ∈ X.
(1) X sia convesso. Allora x+y2 ∈ X perche X e convesso, e quindi
x + y = 2x + y
2∈ X perche X e un cono.
(2) Sia X + X ⊂ X e siano t ∈ [0, 1] e z := tx + (1 − t)y.Per t = 0 risp. t = 1 si ha rispettivamente z = y ∈ X e z = x ∈ X.
Per t ∈ (0, 1) invece tx ∈ X e (1 − t)y ∈ X perche X e un cono.Per ipotesi quindi z ∈ X.
Osservazione 5.10. L’intersezione di una famiglia arbitraria di sotto-
insiemi convessi di V e ancora convessa.
Abbiamo utilizzato questa osservazione gia nel cor. 3.5.
Definizione 5.11. Generalizzando la notazione della def. 1.7 per sot-toinsiemi non vuoti X1, . . . ,Xn ⊂ V poniamo
32
[X1, . . . ,Xn] := n∑
k=1
λkxk | n ∈ N + 1, x1 ∈ X1, . . . , xn ∈ Xn, λ ∈ Rnstoc
Si noti che [X1] = X1.
Definizione 5.12. Per X ⊂ V sia conv X l’intersezione di tutti i sotto-insiemi convessi di V che contengono X.
Per l’oss. 5.10 questo insieme, la chiusura convessa di X, e il piupiccolo insieme convesso in V che contiene X.
Per X = x1, . . . , xn scriviamo conv(x1, . . . , xn) invece di conv X.
Osservazione 5.13. Sia X un sottoinsieme non vuoto di V . Allora
conv X = n∑
k=1
λkxk | n ∈ N + 1, x1, . . . , xn ∈ X, λ ∈ Rnstoc =
∞⋃
n=1
[X, . . . , X ]︸ ︷︷ ︸n
Dimostrazione. E immediato che l’insieme alla destra e convesso econtenuto in ogni insieme convesso che contiene X.
Osservazione 5.14. Siano X1, . . . ,Xn sottoinsiemi non vuoti di V .
Allora [X1, . . . ,Xn] ⊂ conv(X1 ∪ . . . ∪ Xn)
Teorema 5.15. X1, . . . ,Xn siano sottoinsiemi convessi e non vuoti di V .
Allora l’insieme [X1, . . . ,Xn] e convesso e
[X1, . . . ,Xn] = conv(X1 ∪ . . . ∪ Xn).
Dimostrazione. Per l’oss. 5.14 e sufficiente dimostrare che [X1, . . . ,Xn]e convesso. Siano u, v ∈ [X1, . . . ,Xn] e t ∈ [0, 1]. Allora esistonox1, y1 ∈ X1, . . . , xn, yn ∈ Xn e λ, µ ∈ R
nstoc tali che u = λ1x1 + . . . + λnxn
e v = µ1y1 + . . . µnyn. Ponendo s := 1 − t abbiamo
su + tv =
n∑
k=1
(sλkxk + tµkyk) =
n∑
k=1
ρkzk
dove per ogni k abbiamo posto ρk := sλk + tµk e
zk :=
sλk
ρk xk + tµk
ρk yk per ρk 6= 0
xk altrimenti
Dalla convessita di Xk segue che zk ∈ Xk per ogni k. Inoltren∑
k=1
ρk =
n∑
k=1
(sλk + tµk) = s
n∑
k=1
λk + t
n∑
k=1
µk = s + t = 1
Cio mostra che su + tv ∈ [X1, . . . ,Xn].
Corollario 5.16. Siano x1, . . . , xn ∈ V . Alloraconv(x1, . . . , xn) = [x1, . . . , xn].
Osservazione 5.17. Siano X1, . . . ,Xn sottoinsiemi non vuoti di V .Allora
[X1, . . . , Xn] =⋃
(x1,...,xn)∈X1×...×Xn
[x1, . . . , xn] =⋃
(x1,...,xn)∈X1×...×Xn
conv(x1, . . . , xn)
33
Corollario 5.18. X1, . . . ,Xn siano sottoinsiemi convessi e non vuo-
ti di V . Allora
conv(X1 ∪ . . . ∪ Xn) =⋃
(x1,...,xn)∈X1×...×Xn
conv(x1, . . . , xn)
Proposizione 5.19. X sia un sottoinsieme limitato di Rm.
Allora conv X e limitato.
Dimostrazione. Siccome X e limitato, esiste una palla K tale cheX ⊂ K. Allora conv X ⊂ conv K = K.
Proposizione 5.20. X sia un aperto di Rm.
Allora anche conv X e un aperto.
Dimostrazione. Dobbiamo dimostrare che conv X ⊂ int conv X.Per ipotesi pero int X = X, per cui
conv X = conv intX ⊂ conv int conv X5.4= int conv X
Osservazione 5.21. La chiusura convessa di un chiuso di Rm invece
in generale non e piu un chiuso.
Infatti sia X := (R×0)∪i in R2 = C l’insieme costituito dalla retta
reale e dal numero immaginario i. Per il cor. 5.18 allora
conv X =⋃
a∈R
[a, i] = (R × [0, 1]) ∪ i. Ma questo insieme non e chiuso.
Definizione 5.22. Per X ⊂ Rm ed Y ⊂ R
k usiamo l’abbreviazione
X2Y :=
(xy
)| x ∈ X, y ∈ Y
⊂ R
m+k
Per k = 1 ed Y = 1 abbiamo in particolare X21 ⊂ Rm+1.
Similmente per x ∈ Rm abbiamo x21 =
(x1
)∈ R
m+1.
Lemma 5.23. Siano X ⊂ Rm e v ∈ R
m. Allora
v ∈ conv X ⇐⇒ v21 ∈ POS(X21)
Dimostrazione. Per X = ∅ l’enunciato e banalmente vero.Sia quindi X 6= ∅.
(1) Sia v ∈ conv X. Allora esistono x1, . . . , xn ∈ X e λ ∈ Rnstoc tali che
v = λ1x1 + . . . λnxn. Cio implica
v21 = (λ1x1 + . . . + λnxn)21
= λ1(x121) + . . . + λn(xn21) ∈ POS(x21)
(2) Sia viceversa v21 ∈ POS(X21). Allora esistono x1, . . . , xn ∈ Xe λ1, . . . , λn ≥ 0 tali che v21 = λ1(x121) + . . . + λn(xn21). Ma cio eequivalente alle relazioni v = λ1x1 + . . . λnxn e λ1 + . . . + λn = 1.
34
Definizione 5.24. I punti x1, . . . , xs ∈ V si dicono affinemente indipen-
denti, se una coppia di relazioni
λ1x1 + . . . + λsxs = 0
λ1 + . . . + λs = 0
con λ1, . . . , λs ∈ R implica λ1 = . . . = λs = 0.
Definizione 5.25. X sia un sottoinsieme non vuoto di V . La dimensio-ne dim X di X e definita come la dimensione dello spazio affine aff Xgenerato da X.
E chiaro che dimX e uguale alla dimensione usuale di X, se X e unsottospazio affine di X.
Si dimostra facilmente che dim X coincide con il massimo d ∈ N taleche esistono d + 1 punti affinemente indipendenti in X.
Osservazione 5.26. Siano x1, . . . , xs ∈ Rm e λ1, . . . , λs ∈ R.
Allora sono equivalenti:
(1) λ1x1 + . . . + λsxs = 0 e λ1 + . . . + λs = 0.
(2) λ1(x121) + . . . + λs(xs21) = 0.
Corollario 5.27. X sia un sottoinsieme non vuoto di Rm. Allora
dimX = dim SV(X21) − 1
Corollario 5.28. Siano x1, . . . , xs ∈ Rm. Allora sono equivalenti:
(1) I punti x1, . . . , xs sono affinemente indipendenti.
(2) x121, . . . , xs21 sono linearmente indipendenti.
Teorema 5.29 (teorema di Caratheodory). X sia un sottoinsieme
non vuoto di Rm con dim X = d. Allora conv X = [X, . . . ,X]︸ ︷︷ ︸
d+1
.
Dimostrazione. Sia v ∈ conv X. Per il lemma 5.23 v21 ∈ POS(X21).Per il lemma di Caratheodory (prop. 1.10) e il cor. 5.27 esistonox1, . . . , xd+1 ∈ X e λ1, . . . , λd+1 ∈ R
+ tali che
v21 = λ1(x121) + . . . + λd+1(xd+121)
Cio significa che v = λ1x1 + . . . λd+1xd+1 e λ1 + . . .+λd+1 = 1 e vediamoche v ∈ [x1, . . . , xd+1].
Lemma 5.30. X1, . . . ,Xn siano sottoinsiemi compatti e non vuoti di
Rm. Allora [X1, . . . ,Xn] e compatto.
Dimostrazione. L’applicazione
f : X1 × . . . × Xn × Rnstoc −→ R
m
(x1, . . . , xn, λ) −→ λ1x1 + . . . λnxn
e continua e si ha [X1, . . . ,Xn] = f(X1 × . . . × Xn × Rnstoc).
Anche il simplesso Rnstoc e compatto e cio implica l’enunciato.
35
Proposizione 5.31. X sia un compatto di Rm. Allora anche conv X e
compatto, quindi chiuso e limitato.
Dimostrazione. Segue dal teorema 5.29 e dal lemma 5.30.
Corollario 5.32. Siano x1, . . . , xn ∈ Rm. Allora conv(x1, . . . , xn) e com-
patto.
Proposizione 5.33. Siano x1, . . . , xn ∈ Rm ed y ∈ R
m. Per un puntop ∈ X sono allora equivalenti:
(1) p e la proiezione di y su conv(x1, . . . , xn).
(2) |xk − p, y − p| ≤ 0 per ogni k = 1, . . . , n.
Dimostrazione. Sia z =
n∑
k=1
λkxk con λ ∈ Rnstoc. Per la prop. 1.19 e
sufficiente dimostrare che la condizione (2) implica ‖ z − p, y − p ‖≤ 0.
Osserviamo che z − p =
n∑
k=1
λkxk − p =
n∑
k=1
λk(xk − p) perche
n∑
k=1
λk = 1.
Percio
‖ z − p, y − p ‖=n∑
k=1
λk ‖ xk − p, y − p ‖(2)
≤ 0
dove abbiamo anche usato che i coefficienti λk sono tutti non negativi.
Lemma 5.34. X sia un sottoinsieme chiuso e convesso di Rm tale che
0 /∈ X. Allora esistono α ∈ R ed f ∈ Rm tali che fx > α > 0 per ogni
x ∈ X.
Dimostrazione. Cio segue dal cor. 1.23 per y = 0.
Corollario 5.35. Siano x1, . . . , xn ∈ Rm tali che 0 /∈ conv(x1, . . . , xn).
Allora esistono α ∈ R ed f ∈ Rm tali che fxk > α > 0 per ogni
k = 1, . . . , n.
Osservazione 5.36. Siano x1, . . . , xn ∈ Rm ed α ∈ R tali che fxk > α
risp. fxk ≥ α per ogni k = 1, . . . , n.
Allora fz > α risp. fz ≥ α per ogni z ∈ conv(x1, . . . , xn).
Dimostrazione. Supponiamo che fxk > α per ogni k = 1, . . . , n.
Sia z =
n∑
k=1
λkxk con λ ∈ Rnstoc. Allora
fz =
n∑
k=1
λkfxk > α
n∑
k=1
λk = α
Qui abbiamo usato che
n∑
k=1
λk = 1 e che i coefficienti λk, i quali sono
non negativi, non possono essere tutti nulli.
Nello stesso modo si dimostra la seconda parte dell’enunciato.
36
II. ALCUNE APPLICAZIONI
6. Il separatore di Bennett-Mangasarian
Situazione 6.1. Siano X ∈ Rmn , Y ∈ R
kn.
Osservazione 6.2. Consideriamo i sottoinsiemi X := X1, . . . ,Xm ed
Y := Y 1, . . . , Y k di Rn. Seguendo il lavoro di Bennett/Mangasarian,
faremo vedere come il compito di separare in modo approssimato (maottimale) i punti di X ed Y tramite un iperpiano possa essere ricon-dotto ad un compito di programmazione lineare.
Definizione 6.3. Per l ∈ N + 1 siano 1(l) :=
1...1
∈ R
l,
1(l) := (1, . . . , 1) ∈ Rl.
Definizione 6.4. Per α ∈ R sia α+ := max(α, 0).
Per v =
v1
...vn
∈ R
n siano v+ :=
v1+...
vn+
e ‖v‖1 :=
n∑
i=1
|vi|.
Si osservi che per v ≥ 0 si ha ‖v‖1 = 1(n)v.
Definizione 6.5. Gli insiemi X e Y si dicono linearmente separabili,se esiste v ∈ R
n tale che
min1≤i≤m
Xiv > max1≤j≤k
Y jv
Lemma 6.6. Sono equivalenti:
(1) X e Y sono linearmente separabili.
(2) Esistono w ∈ Rn ed α ∈ R tali che
Xw ≥ (α + 1)1(m)
Y w ≤ (α − 1)1(k)
Dimostrazione. (1) =⇒ (2): Ponendo MIN := min1≤i≤m
Xiv,
MAX := max1≤j≤k
Y jv, α := MIN +MAXMIN−MAX e w := 2v
MIN−MAX , abbiamo
Xiw ≥ 2MINMIN−MAX = MIN−MAX+ MIN+ MAX
MIN−MAX = 1 + α per ogni i e
Y jw ≤ 2MAXMIN−MAX = MIN+ MAX−(MIN−MAX)
MIN−MAX = α − 1 per ogni j
(2) =⇒ (1): Chiaro.
37
Lemma 6.7. Sono equivalenti:
(1) X e Y sono linearmente separabili.
(2) min 1m‖(−Xw + (α + 1)1(m))+‖1 + 1
k‖(Y w − (α − 1)1(k))+‖1
| w ∈ Rn, α ∈ R = 0.
Dimostrazione. E chiaro che (2) e equivalente alla condizione cheesistono w ∈ R
n ed α ∈ R tali che −Xw + (α + 1)1(n) ≤ 0 eY w−(α−1)1(k) ≤ 0 e quindi, per il lemma 6.6, alla lineare separabilita
di X e Y .
Osservazione 6.8. min(1 + α)+ + (1 − α)+ | α ∈ R = 2.
Dimostrazione. Per α ∈ R sia f(α) := (1 + α)+ + (1 − α)+.Allora f(0) = 2. Consideriamo 3 casi:
(1) Sia α ≤ −1. Allora (1 + α)+ = 0, (1 − α)+ = 1 + |α| e quindif(α) = 0 + 1 + |α| ≥ 2.
(2) Sia −1 ≤ α ≤ 1. Allora (1 + α)+ = 1 + α, (1−α)+ = 1−α e quindif(α) = 1 + α + 1 − α = 2.
(3) Sia α ≥ 1. Allora (1 + α)+ = 1 + α, (1 − α)+ = 0 e quindif(α) = 1 + α + 0 ≥ 2.
Osservazione 6.9. X e Y siano linearmente separabili.Allora nel punto (2) del lemma 6.7 w 6= 0.
Dimostrazione. Altrimenti avremmo la contraddizione
0 = min 1m
‖ ((α + 1)+1(m))+ ‖1 + 1k‖ ((1 − α)1(k))+ ‖1 | α ∈ R
= min(1 + α)+ + (1 − α)+ | α ∈ R6.9= 2
Lemma 6.10. Siano g : Rn −→ R
m, h : Rn −→ R
k ed E ⊂ Rn.
Sia x0 ∈ E. Allora sono equivalenti:
(1) ‖g(x0)+‖1 + ‖h(x0)+‖1 = min‖g(x)+‖1 + ‖h(x)+‖1 | x ∈ E.
(2) Esistono y0 ∈ Rm+ e z0 ∈ R
k+ tali che y0 ≥ g(x0), z0 ≥ h(x0) e
1(m)y0 + 1(k)z0 =min1(m)y + 1(k)z | y ∈ R
n+, z ∈ R
m+ , x ∈ E, y ≥ g(x), z ≥ h(x).
Dimostrazione. Nelle soluzioni in (2) necessariamente y = g(x)+ ez = h(x)+. Per y ≥ 0 pero 1(m)y =‖ y ‖1 e similmente per z ≥ 0.
Proposizione 6.11. Il compito di minimizzazione
min 1m‖(−Xw + (α + 1)1(m))+‖1 + 1
k‖(Y w − (α − 1)1(k))+‖1
| w ∈ Rn, α ∈ R
e equivalente al compito di ottimizzazione lineare
38
min 1m
1(m)y + 1k1(k)z | y ∈ R
m+ , z ∈ R
k+, w ∈ R
n,
Xw − α1(m) + y ≥ 1(m),−Y w + α1(k) + z ≥ 1(k).
Dimostrazione. La dimostrazione discende dal lemma 6.10 cong(x) = −Xw + (α + 1)1(m) e h(x) = Y w − (α − 1)1(k).
Nota 6.12. Nei lavori di Bennett/Mangasarian e Mangasarian/Street/Wolbergquesti risultati vengono applicati a compiti di diagnosi e prognosi peril carcinoma mammario.
39
7. Grafi
Definizione 7.1. Un grafo diretto e una coppia (P, S) in cui P e uninsieme finito ed S ⊂ P × P una relazione binaria su P .
Gli elementi di P si dicono posizioni (o vertici) del grafo diretto, glielementi di S archi (o spigoli).
Per un arco s = (a, b) ∈ S la posizione a si chiama l’inizio (o laprovenienza) di s, la posizione b la fine (o il punto d’arrivo) di s.
Poniamo allora s1 := a, s2 := b e, per A,B ⊂ P ,
S(A,B) := s ∈ S | s1 ∈ A, s2 ∈ B = S ∩ (A × B)
Nota 7.2. Un grafo diretto viene spesso rappresentato disegnando leposizioni come punti nel piano e unendo per ogni arco (a, b) le posizionia e b con una freccia diretta da a verso b.
Esempio 7.3.
a
b
c
de
La figura corrisponde al grafo diretto (P, S) con:
P = a, b, c, d, e
S = (a, b), (a, c), (a, e), (b, a), (b, c), (c, d), (c, e), (d, c), (d, e)
Definizione 7.4. Un cappio in un grafo diretto e un arco della forma(a, a), cioe e un arco in cui la fine coincide con l’inizio.
Nota 7.5. Fissando una numerazione a1, . . . , an dell’insieme delle po-sizioni di un grafo diretto (P, S) con |P | = n, gli possiamo associareuna matrice di adiacenza A ∈ 0, 1n
n ponendo
Aij =
1 se (ai, aj) ∈ S
0 se (ai, aj) /∈ S
Viceversa ogni matrice A ∈ 0, 1nn determina, a meno di isomorfia, un
grafo diretto che risulta senza cappi se e solo se la matrice contienesolo zeri nella diagonale principale.
Esempio 7.6. Per il grafo dell’esempio 7.3 con le posizioni elencatenell’ordine a, b, c, d, e, la matrice di adiacenza diventa
40
0 1 1 0 11 0 1 0 00 0 0 1 10 0 1 0 10 0 0 0 0
Viceversa la matrice
0 1 0 11 0 1 00 0 0 10 0 0 0
corrisponde ad un grafo diretto della forma
Definizione 7.7. Una posizione a in un grafo diretto (P, S) si diceisolata, se sono soddisfatte le seguenti condizioni:
(1) (a, y) /∈ S per ogni y ∈ P .
(2) (x, a) /∈ S per ogni x ∈ P .
Cio significa che non ci sono archi che hanno a come inizio o fine.
Nella figura le posizioni a e c sono isolate.
a b
c
d
e
Definizione 7.8. Un grafo diretto (P, S) si dice bipartito, se non pos-siede posizioni isolate e se esistono sottoinsiemi A,B ⊂ P tali che:
(1) A ∩ B = ∅.
(2) S ⊂ (A × B) ∪ (B × A).
Si noti che la condizione che (P, S) non abbia posizioni isolate implicaP = A∪B. Inoltre e chiaro che un grafo diretto bipartito non possiedecappi.
Gli insiemi A e B non sono univocamente determinati, nemmenoquando si trascura l’ordine in cui vengono presi, come mostra il grafodiretto bipartito (P, S) dato da P := 1, 2, 3, 4, S := (1, 2), (3, 4), incui possiamo prendere ad esempio A = 1, 3, B = 2, 4 oppureA = 1, 4, B = 2, 3.
41
Definizione 7.9. Un grafo diretto (P, S) si dice unidirezionalmente
bipartito, se non possiede posizioni isolate e se esistono sottoinsiemiA,B ⊂ P tali che:
(1) A ∩ B = ∅.
(2) S ⊂ (A × B).
E chiaro che (P, S) e allora anche bipartito, per cui non possiede cappie P = A ∪ B. In questo caso pero gli insiemi A e B sono univocamentedeterminati, infatti
A = a ∈ P | esiste b ∈ P con (a, b) ∈ S
B = b ∈ P | esiste a ∈ P con (a, b) ∈ S
Le posizioni in A si chiamano sorgenti, le posizioni in B destinazioni.
Definizione 7.10. Nella teoria dei grafi si considerano anche multi-
grafi diretti. Questi possono essere definiti come coppie (P,G) in cuiP e un insieme finito e G : P × P −→ N e un’applicazione. Anche inquesto caso gli elementi di P si chiamano posizioni o vertici.
Nota 7.11. Un multigrafo diretto (P,G) viene spesso rappresentatodisegnando le posizioni nel piano e unendo, per (a, b) ∈ P × P , le posi-zioni a e b con tante frecce (dirette da a verso b) quante sono indicatedalla molteplicita G(a, b).
Fissando una numerazione a1, . . . , an dell’insieme delle posizioni diun multigrafo diretto (P,G) con |P | = n, gli possiamo associare unamatrice di adiacenza A ∈ N
nn ponendo Ai
j = n con n = G(ai, aj).
Viceversa ogni matrice A ∈ Nnn determina, a meno di isomorfia, un
multigrafo diretto con n posizioni.
Cosı ad esempio la matrice
0 1 0 0 30 0 1 0 01 1 0 1 10 0 0 0 00 0 0 2 0
corrisponde ad un multigrafo diretto della forma
Nella numerazione usata la prima posizione si trova in alto a sinistra,le altre si ottengono procedendo in senso orario.
42
Nota 7.12. Ogni grafo diretto (P, S) puo essere considerato come unmultigrafo diretto (P,G) se poniamo
G(a, b) :=
1 se (a, b) ∈ S
0 altrimenti
Viceversa ogni multigrafo diretto (P,G) con G ≤ 1 e essenzialmente lastessa cosa come un grafo diretto.
43
8. Flussi in un grafo diretto
Definizione 8.1. Una rete e una quintupla R = (P, S, α, ω, c) in cui:
(1) (P, S) e un grafo diretto senza cappi.
(2) α, ω ∈ P sono due posizioni con α 6= ω.α si chiama la sorgente della rete, ω la destinazione.
(3) c : S −→ R+ e un’applicazione.
c si chiama la capacita della rete.
Situazione 8.2. R = (P, S, α, ω, c) sia una rete.
Per A,B ⊂ P usiamo la notazione
S(A,B) := s ∈ S | s1 ∈ A, s2 ∈ B
introdotta nella def. 7.1.
Definizione 8.3. Un flusso in R e una funzione f : S −→ R+.
Definizione 8.4. Per un flusso f in R ed A,B ⊂ P sia
f(A,B) :=∑
s∈S(A,B)
f(s)
Per s ∈ S abbiamo in particolare f(s) = f(s1, s2).
Definizione 8.5. Per un flusso f : S −→ R+ ed a ∈ P definiamo
ingresso(a, f) := f(P, a)
uscita(a, f) := f(a, P )
∂f(a) := ingresso(a, f) − uscita(a, f) = f(P, a) − f(a, P )
∂f(a) si chiama il flusso locale in a indotto da f .
Otteniamo cosı un’applicazione ∂f : P −→ R.
Osservazione 8.6. f sia un flusso in R ed a ∈ P . Allora
f(P, a) = f(P \ a, a)
f(a, P ) = f(a, P \ a)
Dimostrazione. Chiaro perche, per definizione di rete, il grafo direttoe senza cappi, per cui S(P, a) = S(P \ a, a) e S(a, P ) = S(a, P \ a).
Osservazione 8.7. Per A,B,C ⊂ P con A ∩ B = ∅ abbiamo
S(A ∪ B,C) = S(A,C)∪S(B,C)
S(C,A ∪ B) = S(C,A)∪S(C,B)
Per un flusso f abbiamo quindi
f(A ∪ B,C) = f(A,C) + f(B,C)
f(C,A ∪ B) = f(C,A) + f(C,B)
44
Lemma 8.8. f sia un flusso in R ed A ⊂ P . Allora∑
a∈A
∂f(a) = f(P \ A,A) − f(A,P \ A)
Dimostrazione. Usando l’oss. 8.7 abbiamo∑
a∈A
∂f(a) =∑
a∈A
(f(P, a) − f(a, P )) = f(P,A) − f(A,P )
= f(A,A) + f(P \ A,A) − f(A,A) − f(A,P \ A)
= f(P \ A,A) − f(A,P \ A)
Corollario 8.9. Sia f un flusso in R. Allora∑
a∈P
∂f(a) = 0.
Dimostrazione. Per il lemma 8.8 abbiamo∑
a∈P
∂f(a) = f(∅, P ) − f(P, ∅) = 0
Definizione 8.10. Un flusso f : S −→ R+ si dice ammissibile, se sono
soddisfatte le seguenti condizioni:
(1) f ≤ c.
(2) ∂f(a) = 0 per ogni a ∈ P \ α, ω.
La prima condizione significa che il flusso non supera la capacita dis-ponibile, la seconda che per ogni a ∈ P \ α, ω si ha
uscita(a, f) = ingresso(a, f)
Osservazione 8.11. Esiste sempre un flusso ammissibile in R.Infatti il flusso nullo ©
s0 e ammissibile.
Proposizione 8.12. f sia un flusso ammissibile in R.
Allora ∂f(ω) = −∂f(α).
Dimostrazione. Dal cor. 8.9 e dalla condizione (2) nella def. 8.10 ab-biamo
0 =∑
a∈P
∂f(a) =∑
a∈P\α,ω
∂f(a) + ∂f(α) + ∂f(ω) = ∂f(α) + ∂f(ω)
Definizione 8.13. f sia un flusso in R. Allora val(f) := ∂f(ω) si chia-ma il valore del flusso.
val(f) e quindi il flusso locale nella destinazione.
Se f e ammissibile, allora val(f) = −∂f(α).
Osservazione 8.14. Spesso la sorgente α e la destinazione ω sonoscelte in modo tale che S(P,α) = ∅ e S(w,P ) = ∅.
In questo caso val(f) = ingresso(ω, f) e, se f e ammissibile, si haanche val(f) = uscita(α, f).
45
Definizione 8.15. Un flusso massimale in R e un flusso ammissibiledi valore massimale.
Definizione 8.16. Un taglio (o una sezione, in inglese cut) di R e unsottoinsieme X ⊂ P tale che α ∈ X, ω /∈ X.
cap(X) := c(X,P \ X) =∑
s∈S(X,P\X)
c(s)
si chiama allora la capacita di X.
Denotiamo con T (R) l’insieme dei tagli di R.Siccome per ipotesi α 6= ω, si ha sempre T (R) 6= ∅. Ad esempioα ∈ T (R) e P \ ω ∈ T (R).
Osservazione 8.17. f sia un flusso ammissibile in R ed A,B ⊂ P .Allora f(A,B) ≤ c(A,B).
Lemma 8.18. f sia un flusso ammissibile in R ed X un taglio di R.Allora
val(f) = f(X,P \ X) − f(P \ X,X) ≤ cap(X)
Dimostrazione. Siccome α /∈ P \ X si ha ∂f(a) = 0 per ogni elementoa ∈ P \ X diverso da ω. Percio
val(f) = ∂f(ω) =∑
a∈P\X
∂f(a)8.8= f(X,P \ X) − f(P \ X,X)
≤ f(X,P \ X)8.17≤ c(X,P \ X) = cap(X)
Corollario 8.19. f sia un flusso ammissibile in R. Allora
val(f) ≤ c(α,P \ α)
val(f) ≤ c(P \ ω, ω)
Corollario 8.20. f sia un flusso ammissibile in R ed X un taglio di Rtale che val(f) = cap(X). Allora f e un flusso massimale ed X un taglio
di capacita minimale.
Corollario 8.21. f sia un flusso ammissibile in R ed X un taglio di R.
Assumiamo che
f(s) =
c(s) per s ∈ S(X,P \ X)
0 per s ∈ S(P \ X,X)
Allora val(f) = cap(X), per cui f e un flusso massimale ed X un taglio
di capacita minimale.
Dimostrazione. L’ipotesi implica
val(f)8.18= f(X,P \ X) − f(P \ X,X) = f(X,P \ X) = c(X,P \ X)
= cap(X)
46
Esempio 8.22. Nella figura e rappresentato un flusso ammissibile convalore 6. Per ogni arco s abbiamo indicato f(s) e c(s) nella formaf(s) : c(s).
α
ω
A B
C
D
E
F
5 : 7
1 : 3
3 : 5
2 : 7
2 : 6
1 : 3
1 : 31 : 3
5 : 6
4 : 5
1 : 2
In questo esempio cap(α) = c(α,P \α) = 10, cap(P \ω) = c(P \ω, ω) = 9,quindi ogni flusso ammissibile in questa rete possiede un valore ≤ 9.
Definizione 8.23. Un cammino in R e una successione γ = (a0, a1, . . . , an)di punto distinti con n ≥ 1 tale che (ai−1, ai) ∈ S per ogni i = 1, . . . , n.
γ si chiama allora un cammino da a0 ad an.
Per a, b ∈ P sia C(a, b) l’insieme dei cammini da a a b.
Proposizione 8.24. X sia un taglio di R e γ = (a0, . . . , an) ∈ C(α, ω).Allora esiste un i ∈ 1, . . . , n tale che (ai−1, ai) ∈ S(X,P \ X).
Dimostrazione. Siccome a0 = α ∈ X ed an = ω ∈ P \ X, deve esistereun piu piccolo i ≥ 1 tale che ai ∈ P \ X . Allora (ai−1, ai) ∈ S(X,P \ X).
Osservazione 8.25. f sia un flusso ammissibile in R eγ = (a0, . . . , an) ∈ C(α, ω). Per l’ipotesi (1) della def. 8.10 allorac(ai−1, ai) − f(ai−1, ai) ≥ 0 per ogni i = 1, . . . , n.
Sia ∆ := ∆(γ, f) := min1≤i≤n
c(ai−1, ai) − f(ai−1, ai).
Se allora definiamo un flusso g : S −→ R+ ponendo
g(s) :=
f(s) + ∆ se s = (ai−1, ai) per un i ∈ 1, . . . , n
f(s) altrimenti(*)
allora g e un flusso ammissibile in R con val(g) = val(f) + ∆.
Dimostrazione. (1) E chiaro che g ≤ c.
(2) Sia b ∈ P \ α, ω. Se b /∈ a0, . . . , an, allora g(P, b) = f(P, b) eg(b, P ) = f(b, P ), per cui ∂g(b) = ∂f(b) = 0.
Sia b ∈ a0, . . . , an. Siccome b 6= α, ω, deve esistere uni ∈ 1, . . . , n−1 tale che b = ai. Siccome i punti che appaiono in γ sonotutti distinti, i e univocamente determinato e gli unici archi in S(P, b)risp. S(b, P ) in cui avviene l’aumento in (∗) sono (ai−1, ai) e (ai, ai+1).Cio implica
ingresso(b, g) = ingresso(b, f) + ∆
uscita(b, g) = uscita(b, f) + ∆
47
per cui ∂g(b) = ∂f(b) = 0.
(3) Nello stesso modo si vede che ingresso(ω, g) = ingresso(ω, f) + ∆mentre uscita(ω, g) = uscita(ω, f), perche ω non puo apparire all’internodi γ. Cio implica val(g) = ∂g(ω) = ∂f(ω) + ∆ = val(f) + ∆.
Esempio 8.26. Nella rete dell’esempio 8.22 possiamo prima consi-derare il cammino (α,A,B,C, ω) in cui ∆ = 2, ottenendo il flusso
α
ω
A B
C
D
E
F
7 : 7
1 : 3
5 : 5
2 : 7
4 : 6
1 : 3
3 : 31 : 3
5 : 6
4 : 5
1 : 2
di valore 8, e successivamente il cammino (α,F,E,D, ω) in cui∆ = 1, ottenendo cosı un flusso di valore 9 il quale, come abbiamo vistonell’esempio 8.22, e gia un flusso massimale:
α
ω
A B
C
D
E
F
7 : 7
2 : 3
5 : 5
2 : 7
4 : 6
1 : 3
3 : 31 : 3
6 : 6
5 : 5
2 : 2
Nota 8.27. Puo accadere pero che la tecnica dell’oss. 8.25 non sia ap-plicabile, cioe puo accadere che ∆(γ, f) = 0 per ogni γ ∈ C(α, ω), purnon essendo f massimale. Consideriamo ad esempio il flusso f descrit-to dalla figura
α
ω
A B
C
5 : 5
4 : 73 : 4
4 : 7
6 : 6
1 : 31 : 5
Calcoliamo ∆(γ, f) per ogni γ ∈ C(α, ω):
48
γ ∆(γ, f)(α,A,B,w) 0
(α,A,B,C,w) 0(α,A,C,w) 0(α,C,w) 0
Quindi non possiamo aumentare il valore del flusso con il metododell’oss. 8.25. Se pero diminuiamo di 1 il carico sull’arco (B,C), pos-siamo aumentare di 1 il carico sugli archi (B,ω) e (α,C), ottenendo ilflusso ammissibile
α
ω
A B
C
5 : 5
4 : 74 : 4
5 : 7
6 : 6
1 : 30 : 5
Per il cor. 8.19 questo e un flusso ammissibile di valore massimale.
Definizione 8.28. Un semicammino in R e una successioneγ = (a0, ε1, a1, ε2, . . . , an−1, εn, an) tale che:
(1) n ≥ 1.
(2) a0, . . . , an sono punti distinti di P .
(3) ε1, . . . , εn ∈ 1,−1.
(4) Per ogni i = 1, . . . , n vale:εi = 1 =⇒ (ai−1, ai) ∈ Sεi = −1 =⇒ (ai, ai−1) ∈ S
γ si chiama allora un semicammino da a0 ad an.Per a, b ∈ P sia S(a, b) l’insieme dei semicammini da a a b.
Poniamo vertici(γ) := a0, . . . , an.
Definizione 8.29. f sia un flusso ammissibile in R eγ = (a0, ε1, a1, . . . , an−1, εn, an) un semicammino in R. Diciamo che γ ef -aumentante se per ogni i = 1, . . . , n si ha
εi = 1 =⇒ f(ai−1, ai) < c(ai−1, ai)
εi = −1 =⇒ f(ai, ai−1) > 0
Per a, b ∈ P denotiamo con Sf (a, b) l’insieme dei semicammini f -aumentantida a a b.
Esempio 8.30. Nella prima figura dell’oss. 8.27 il semicammino(α, 1, C,−1, B, 1, ω) da α a ω e f -aumentante. Infatti per ε1 = 1 si haf(α,C) < c(α,C) perche 4 < 7; per ε2 = −1 si ha f(B,C) = 1 > 0 edinfine per ε3 = 1 si ha f(B,w) < c(B,w) perche 3 < 4.
Definizione 8.31. γ = (a0, ε1, a1, . . . , an−1, εn, an) sia un semicamminoin R. Poniamo allora
49
S+γ := (ai−1, ai) | i = 1, . . . , n ed εi = 1
S−γ := (ai, ai−1) | i = 1, . . . , n ed εi = −1
Sγ := S+γ ∪ S−
γ
E chiaro che S+γ ∩ S−
γ = ∅.
Infatti sia (ai−1, ai) = (aj , aj−1), ovvero ai−1 = aj e ai = aj−1. Siccomei punti a0, . . . , an sono distinti, cio implica i − 1 = j e i = j − 1, e cio eimpossibile.
Definizione 8.32. f sia un flusso ammissibile in R eγ = (a0, ε1, a1, . . . , an−1, εn, an) un semicammino in R.Per s ∈ Sγ poniamo
∆(γ, f, s) := c(ai−1, ai) − f(ai−1, ai) se (ai−1, ai) ∈ S+γ
∆(γ, f, s) := f(ai, ai−1) se (ai, ai−1) ∈ S−γ
Definiamo adesso
∆(γ, f) := mins∈Sγ
∆(γ, f, s)
Esempio 8.33. Nella prima figura della nota 8.27 consideriamo an-cora il semicammino γ = (α, 1, C,−1, B, 1, ω). Allora
∆(γ, f, (α,C)) = c(α,C) − f(α,C) = 7 − 4 = 3
∆(γ, f, (B,C)) = f(B,C) = 1
∆(γ, f, (B,ω)) = c(B,ω) − f(B,ω) = 4 − 3 = 1
per cui ∆(γ, f) = 1.
Osservazione 8.34. Nella situazione della def. 8.29γ e f -aumentante se e solo se ∆(γ, f) > 0.
Proposizione 8.35. f sia un flusso ammissibile in R e γ ∈ S(α, ω).Sia ∆ := ∆(γ, f). Se allora definiamo un flusso g : S −→ R
+ ponendo
g(s) :=
f(s) + ∆ per s ∈ S+γ
f(s) − ∆ per s ∈ S−γ
f(s) per s ∈ S \ Sγ
(*)
allora g e un flusso ammissibile in R e val(g) = val(f) + ∆.
Dimostrazione. (1) E chiaro che 0 ≤ g ≤ c.
(2) Sia γ = (a0, ε1, a1, . . . , an−1, εn, an). Sia b ∈ P \ α, ω.Se b /∈ a0, . . . , an, allora g(b, P ) = f(b, P ) e g(P, b) = f(P, b) per cui,essendo f un flusso ammissibile, si ha ∂g(b) = ∂f(b) = 0.
Supponiamo ora che b ∈ a0, . . . , an. Siccome b 6= α, ω, deve esistereun i ∈ 1, . . . , n − 1 tale che b = ai. Siccome i punti che appaiono in γsono tutti distinti, i e univocamente determinato e gli aumenti in (∗)avvengono solo su semicammini di una delle quattro forme seguentiper le quali abbiamo calcolato i cambiamenti:
50
(ai−1,−1, b,−1, ai+1) . . . ingresso(b, g) = ingresso(b, f) − ∆
. . . uscita(b, g) = uscita(b, f) − ∆
(ai−1,−1, b, 1, ai+1) . . . ingresso(b, g) = ingresso(b, f)
. . . uscita(b, g) = uscita(b, f) − ∆ + ∆
(ai−1, 1, b,−1, ai+1) . . . ingresso(b, g) = ingresso(b, f) + ∆ − ∆
. . . uscita(b, g) = uscita(b, f)
(ai−1, 1, b, 1, ai+1) . . . ingresso(b, g) = ingresso(b, f) + ∆
. . . uscita(b, g) = uscita(b, f) + ∆
In tutti questi casi risulta ∂g(b) = ∂f(b) = 0.
(3) Per calcolare val(g) consideriamo i due casi possibili εn = 1 eεn = −1:
εn = 1 . . . ingresso(ω, g) = ingresso(ω, f) + ∆
. . . uscita(ω, g) = uscita(ω, f)
εn = −1 . . . ingresso(ω, g) = ingresso(ω, f)
. . . uscita(ω, g) = uscita(ω, f) − ∆
perche ω non puo apparire all’interno di γ. Cio implicaval(g) = ∂g(ω) = ∂f(ω) + ∆ = val(f) + ∆.
Corollario 8.36. f sia un flusso ammissibile in R. Se esiste un semi-
cammino f -aumentante da α ad ω, allora f non e un flusso massimale.
Osservazione 8.37. f sia un flusso ammissibile in R tale cheSf (α, ω) = ∅. Siano
Γ := γ ∈ Sf (α, a) | a ∈ P
X := α ∪⋃
γ∈Γ
vertici(γ)
L’ipotesi implica che ω /∈ X, percio X e un taglio di R.
Se Γ 6= ∅, si ha naturalmente X =⋃
γ∈Γ
vertici(γ).
Teorema 8.38. f sia un flusso ammissibile in R.Allora sono equivalenti:
(1) f e massimale.
(2) Non esiste un semicammino f -aumentante da α a ω.
(3) Esiste un taglio X di R di capacita minimale tale che
val(f) = cap(X).
(4) Esiste un taglio X di R tale che val(f) = cap(X).
Dimostrazione. (1)=⇒(2): Corollario 8.36.
(2)=⇒(3): Sia Sf (α, ω) = ∅. Definiamo il taglio X come nell’oss. 8.37.Per costruzione allora
s ∈ S(X,P \ X) =⇒ f(s) = c(s)
51
s ∈ (P \ X,X) =⇒ f(s) = 0
Per il cor. 8.21 val(f) = cap(X) ed X e un taglio di capacita minimale.
(3)=⇒(4): Chiaro.
(4)=⇒(1): Corollario 8.20.
Teorema 8.39. f sia un flusso massimale in R ed Y un taglio di capa-cita minimale di R. Allora val(f) = cap(Y ).
Dimostrazione. (1) Dal lemma 8.18 sappiamo che val(f) ≤ cap(Y ).
(2) Per il teorema 8.38 esiste un taglio X di R di capacita minimaletale che val(f) = cap(X). Siccome anche Y e di capacita minimale,abbiamo cap(X) = cap(Y ).
Proposizione 8.40. Per ogni s ∈ S sia c(s) ∈ N. Allora:
(1) Esiste sempre un taglio di capacita minimale di R.
(2) Esiste sempre un flusso massimale f in R tale che f(s) ∈ N perogni s ∈ S.
Dimostrazione. (1) Chiaro, perche P e un insieme finito.
(2) Iniziando con il flusso nullo f0 := ©s
0, per ogni i = 0, 1, . . . proce-
diamo nel modo seguente:
Se Sfi(α, ω) = ∅, ci fermiamo.
Altrimenti sia γ ∈ Sfi(α, ω). E chiaro che ∆(γ, fi) ∈ N + 1. Per la
prop. 8.35 troviamo un flusso ammissibile fi+1 con
val(fi+1) = val(fi) + ∆(γ, fi) ≥ val(fi) + 1
Per costruzione inoltre fi+1(s) ∈ N per ogni s ∈ S. Siccomeval(fi+1) ≤ c(P \ ω, ω) per il cor. 8.19, l’algoritmo deve terminare.
Nota 8.41. Seguendo Aigner, pagg. 305-307, facciamo vedere adessocome il problema dei flussi massimali possa essere risolto nell’ambitodella programmazione lineare.
Definiamo una matrice M ∈ RPS ponendo, per p ∈ P ed s ∈ S,
Mps :=
1 se p = s2
−1 se p = s1
0 altrimenti
Senza perdere di generalita possiamo assumere che (ω,α) ∈ S e che
c(ω,α) = ∞ (oppure che c(ω,α) >∑
s∈S\ω,α
c(s)).
Numerando P ∈ S, possiamo identificare P con 1, . . . ,m ed S con1, . . . , n. Allora M ∈ R
mn .
Per la rete della nota 8.27, aggiungendo l’arco (ω,α), M e data dallatabella
52
αA αC AB AC BC Bω Cω ωαα -1 -1 0 0 0 0 0 1A 1 0 -1 -1 0 0 0 0B 0 0 1 0 -1 -1 0 0C 0 1 0 1 1 0 -1 0ω 0 0 0 0 0 1 1 -1
La capacita c puo essere identificata con un vettore c ∈ Rn+, e simil-
mente un flusso ammissibile f con un vettore x ∈ Rn+ tale che x ≤ c
con Mx = 0. Quest’ultima equazione esprime proprio la condizione (2)della def. 8.10. Il valore del flusso e uguale alla componente x(ω,α).
Il problema del flusso massimale e quindi equivalente al problemadi ottimizzazione lineare
Mx = 0
0 ≤ x ≤ c (∗)
(0 . . . 01)x = max
Usando il comando glpk di Matlab per il nostro esempio troviamo cosıuna soluzione con le istruzioni:
M=[-1 -1 0 0 0 0 0 1; 1 0 -1 -1 0 0 0 0;
0 0 1 0 -1 -1 0 0; 0 1 0 1 1 0 -1 0; 0 0 0 0 0 1 1 -1];
A=[M; eye(8)];
b=[0 0 0 0 0 5 7 7 3 5 4 6 Inf]’;
f=[0 0 0 0 0 0 0 1];
[x,m]=glpk(f’,M,b,[],[],’SSSSSUUUUUUUU’,’CCCCCCCC’,-1)
Usando il teorema 2.9 con questo ragionamento possiamo dimostrarel’esistenza di un flusso massimale anche senza la condizione chec(s) ∈ N per ogni s ∈ S (cfr. prop. 8.40). Infatti con
A :=
M−M
δ
, b :=
00c
, f := (0 . . . 01)
il problema (*) puo essere scritto nella forma
fx = max
x ≥ 0
Ax ≤ b
Siccome c ≥ 0 e quindi anche b ≥ 0, abbiamo X := (ARn+ ≤ b) 6= ∅
perche 0 ∈ X e Y := (R+mA ≥ f) 6= ∅ perche (0 f) ∈ Y . Dal teorema
2.9 segue che il nostro problema possiede una soluzione.
53
III. OTTIMIZZAZIONE NON LINEARE
9. Il cono tangente
Situazione 9.1. X sia un sottoinsieme di Rn, Ω un aperto di R
n taleche X ⊂ Ω ed f : Ω −→ R una funzione di classe C1.
In questa parte della tesi seguiamo soprattutto Geiger/Kanzow,pagg. 41-76.
Nota 9.2. Usiamo le seguenti abbreviazioni:
(1) [R++ ↓ 0] := ©k
tk ∈ RN | t0 > t1 > t2 > . . . > 0 e lim
k−→∞tk = 0
(2) Per y ∈ Rn sia
[X −→ y] := ©k
xk ∈ XN | limk−→∞
xk = y
Ponendo X = Rn e X = R
++ abbiamo in particolare definito gliinsiemi [Rn −→ y] e [R++ −→ 0].
Osservazione 9.3. Sia ©k
tk ∈ [R++ −→ 0]. Ponendo n0 := 0 troviamo
un indice n1 > n0 tale che tn1< tn0
, poi un indice n2 > n1 tale chetn2
< tn1ecc. In questo modo otteniamo una successione
©j
tnj∈ [R++ ↓ 0].
Definizione 9.4. Sia x ∈ X. Un vettore v ∈ Rn si dice tangente ad X
in x, se esistono due successioni ©k
xk ∈ [X −→ x] e ©k
tk ∈ [R++ −→ 0]
tali che ©k
xk − x
tk∈ [Rn −→ v], cioe tali che lim
k−→∞
xk − x
tk= v.
L’insieme T(X,x) di tutti i vettori tangenti ad X in x si chiama ilcono tangente di X in x.
Osservazione 9.5. Siano x ∈ X e v ∈ Rn. Usando l’oss. 9.3 vediamo
che v ∈ T(X,x) se e solo se esistono due successioni ©k
xk ∈ [X −→ x]
e ©k
tk ∈ [R++ ↓ 0] tali che ©k
xk − x
tk∈ [Rn −→ v].
Osservazione 9.6. Sia x ∈ X. Allora T(X,x) e un cono di Rn (nel
senso della def. 5.7).
Dimostrazione. E chiaro che 0 ∈ T(X,x), per cui T(X,x) 6= ∅.
Se v ∈ T(X,x) e λ > 0, e se ©k
xk ∈ [X −→ x] e ©k
tk ∈ [R++ −→ 0]
sono tali che limk−→∞
xk − x
tk= v, allora evidentemente
©k
tk/λ ∈ [R++ −→ 0] e limk−→∞
xk − x
tk/λ= λv, per cui λv ∈ T(X,x).
Osservazione 9.7. x sia un punto interno di X (rispetto alla topologiadi R
n). Allora T(X,x) = Rn.
54
Dimostrazione. Sia v ∈ Rn. Dobbiamo far vedere che v e tangente ad
X in x. Siccome x e un punto interno di X, esiste un m ∈ N + 1 taleche xk = x + 1
m+kv ∈ X per ogni k ∈ N. Poniamo tk := 1
m+k.
Allora ©k
tk ∈ [R++ −→ 0], ©k
xk ∈ [X −→ x], mentre xk−xtk
= v per ogni
k ∈ N, per cui sicuramente ©k
xk − x
tk∈ [Rn −→ v].
Lemma 9.8. Sia x ∈ X. Allora T(X,x) e un sottoinsieme chiuso di Rn.
Dimostrazione. Siano v ∈ T(X,x) e ©j
vj ∈ [T(X,x) −→ v].
Allora per ogni j ∈ N esistono due successioni ©k
x(j)k ∈ [X −→ x] e
©k
t(j)k ∈ [R++ ↓ 0] tali che lim
k−→∞
x(j)k − x
t(j)k
= vj.
Cio implica che possiamo trovare una successione ©j
mj ∈ NN tale
che per ogni j ∈ N + 1 si abbia |x(j)mj
− x| ≤ 1j, 0 < t
(j)mj
≤ 1j
e∣∣∣∣∣x
(j)mj
− x
t(j)mj
− vj
∣∣∣∣∣ ≤1j. L’ultima disuguaglianza implica
∣∣∣∣∣x
(j)mj
− x
t(j)mj
− v
∣∣∣∣∣ ≤∣∣∣∣∣x
(j)mj
− x
t(j)mj
− vj
∣∣∣∣∣ + |vj − v|
e vediamo che ©j
x(j)mj
∈ [X −→ x], ©j
t(j)mj∈ [R++ −→ 0] e
limj−→∞
x(j)mj
− x
t(j)mj
= v, cosicche v ∈ T(X,x).
Definizione 9.9. x ∈ X e un punto di minimo locale di f in X, seesiste un intorno U ∈ U(x, in X) tale che
f(x) ≤ f(u) per ogni u ∈ U
Per la definizione di topologia in Rn (e quindi su X) cio e equivalente
alla condizione che esista r > 0 tale che f(x) ≤ f(u) ogni u ∈ X per cui|x − u| < r.
Definizione 9.10. Per x ∈ Ω e v ∈ Rn sia
f ′(x; v) := limt−→0
f(x + tv) − f(x)
t
la derivata in direzione v di f in x.
E noto dall’analisi che f ′(x; v) =‖ ∇f(x), v ‖.
Osservazione 9.11. x sia un punto interno di X.Allora sono equivalenti:
(1) f ′(x; v) ≥ 0 per ogni v ∈ T(X,x).
(2) f ′(x; v) = 0 per ogni v ∈ T(X,x).
(3) ∇f(x) = 0.
55
Dimostrazione. Le implicazioni (3)=⇒(2)=⇒(1) sono banali.
L’implicazione (1)=⇒(3) segue dall’oss. 9.7.
Lemma 9.12. x sia un punto di minimo locale di f in X.Allora f ′(x; v) ≥ 0 per ogni v ∈ T(X,x).
Dimostrazione. Sia v ∈ T(X,x). Allora esistono successioni
©k
xk ∈ [X −→ x] e ©k
tk ∈ [R++ −→ 0] tali che ©k
xk − x
tk∈ [Rn −→ v].
Per il teorema del valor medio esiste una successione ©k
ξk tale che
ξk ∈ [x, xk] e f(xk) − f(x) =‖ ∇f(ξk), xk − x ‖ per ogni k.
L’ipotesi che x sia un punto di minimo locale di f in X implica chef(xk) − f(x) ≥ 0 per k >> 0 e quindi anche ‖ ∇f(ξk),
xk−xtk
‖≥ 0 per
k >> 0. Inoltre ©k
ξk −→ x perche ξk ∈ [x, xk] per ogni k. Cio implica
f ′(x; v) =‖ ∇f(x), v ‖= limk−→∞
‖ ∇f(ξk),xk − x
tk‖≥ 0
Esempio 9.13. Consideriamo il caso n = 1, X = [0, 1] e Ω un intervalloaperto che contiene [0, 1]. Il cono tangente di X coincide con [0,∞), ilcono tangente in 1 con (−∞, 0].
Il lemma 9.12 afferma che se 0 e un punto di minimo locale di f inX, allora f ′(0) ≥ 0, e se 1 e un punto di minimo locale in X, alloraf ′(1) ≤ 0.
Osservazione 9.14. Il cono tangente T(X,x) in generale e piuttostocomplicato, cosicche spesso non e possibile applicare direttamente illemma 9.12. Descriveremo adesso, in alcuni casi importanti, condizio-ni di ottimalita piu pratiche.
56
10. Le condizioni di Karush-Kuhn-Tucker
Situazione 10.1. Siano date funzioni f, g1, . . . , gm, h1, . . . , hp : Rn −→ R
tutte di classe C1. Sono ammessi i casi m = 0 o p = 0.
Sia X := (g1 ≤ 0, . . . , gm ≤ 0, h1 = 0, . . . , hp = 0).
Poniamo anche g := (g1, . . . , gm), h := (h1, . . . , hp).
Il risultato principale di questo capitolo e il teorema 10.11 che, comeconseguenza del lemma di Farkas, ci fornisce una condizione necessa-ria e facilmente verificabile per un minimo locale di f in X.
Definizione 10.2. Per x ∈ X sia I(x) := i ∈ 1, . . . ,m | gi(x) = 0.
Definizione 10.3. Per x ∈ X sia
Tl(x) := v ∈ Rn |‖ ∇gi(x), v ‖≤ 0 per ogni i ∈ I(x),
‖ ∇hj(x), v ‖= 0 per ogni j ∈ 1, . . . , p
Tl(x) si chiama il cono tangente linearizzato di X in x.
Si noti che esso nel caso generale dipende non solo da X, ma anchedalla scelta delle restrizioni gi ed hj che usiamo per descrivere X.
E immediato che Tl(x) e un cono nel senso della def. 5.7.
Proposizione 10.4. Sia x ∈ X. Allora T(X,x) ⊂ Tl(x).
Dimostrazione. La dimostrazione e molto simile alla dimostrazionedel lemma 9.12.
Sia v ∈ T(X,x). Allora esistono successioni ©k
xk ∈ [X −→ x] e
©k
tk ∈ [R++ −→ 0] tali che ©k
xk − x
tk∈ [Rn −→ v].
(1) Sia i ∈ I(x). Per il teorema del valor medio esiste una successione©k
ξk tale che ξk ∈ [x, xk] e gi(xk) = gi(x)+ ‖ ∇gi(ξk), xk − x ‖ per ogni
k. Per ipotesi pero gi(x) = 0 perche i ∈ I(x) e gi(xk) ≤ 0 perche ognixk ∈ X. Percio ‖ ∇gi(ξk), xk−x ‖≤ 0 e quindi anche ‖ ∇gi(ξk),
xk−xtk
‖≤ 0
per ogni k. Passando al limite otteniamo ‖ ∇gi(x), v ‖≤ 0.
(2) Nello stesso modo si dimostra che ‖ ∇hj(x), v ‖= 0 per ognij = 1, . . . , p.
Definizione 10.5. Un punto x ∈ X si dice regolare nel senso di Abadie,se T(X,x) = Tl(x).
Esempio 10.6. Troveremo fra poco semplici condizioni sufficienti af-finche un punto sia regolare nel senso di Abadie. Non e comunquesempre cosı, come mostra il seguente esempio.
Sia X := x ∈ R2 | 0 ≤ x2 ≤ (x1)3
= x ∈ R2 | −x2 ≤ 0, x2 − (x1)3 ≤ 0
X e quindi l’insieme dei punti nel primo quadrante che si trovano aldi sotto della parabola cubica data dall’equazione x2 = (x1)3.
57
Sia x0 :=
(00
). E chiaro che T(X,x) = R
+ × 0.
Con g1(x) := −x2 e g2(x) := x2 − (x1)3 troviamo invece
∇g1(x) =
(0−1
), da cui ∇g1(x0) =
(0−1
), e ∇g2(x) =
(−3(x1)2
1
)
da cui ∇g2(x0) =
(01
).
Siccome g1(x0) = g2(x0) = 0, abbiamo I(x0) = 1, 2, cosicche perv ∈ R
2 si ha v ∈ Tl(x0) ⇐⇒ −v2 ≤ 0 e v2 ≤ 0 ⇐⇒ v2 = 0, per cuiTl(x0) = R × 0.
T(X,x0) non coincide percio con Tl(x0), cosicche x0 non e un puntoregolare nel senso di Abadie.
Definizione 10.7. Definiamo un’applicazione L : Rn × Rm × Rp −→ R
tramite
L(x, λ, µ) := f(x) +m∑
i=1
λigi(x) +
p∑
j=1
µjhj(x)
= f(x)+ ‖ λ, g(x) ‖ + ‖ µ, h(x) ‖
L’applicazione L si chiama la funzione di Lagrange di (X, f) (o piuprecisamente della situazione descritta dalle funzioni f, g, h).
Definizione 10.8. Le condizioni di Karush-Kuhn-Tucker (KKT)
rispetto alla situazione 10.1 sono
∇xL(x, λ, µ) = 0
g(x) ≤ 0
h(x) = 0
λ ≥ 0
‖ λ, g(x) ‖= 0
Il gradiente ∇x rispetto alla variabile x e definito da
∇xL(x, λ, µ) := ∇f(x) +m∑
i=1
λi∇gi(x) +
p∑
j=1
µj∇hj(x)
I parametri λ1, . . . , λm, µ1, . . . , µp (oppure anche i vettori λ, µ) vengonodetti moltiplicatori di Lagrange.
Un punto (x, λ, µ), in cui le condizioni di KKT sono soddisfatte, sichiama un punto di KKT di (X, f) (o piu precisamente della situazionedescritta dalle funzioni f, g, h).
Si noti che la seconda e la terza condizione implicano che x ∈ X.
Osservazione 10.9. Se m = p = 0, le condizioni KKT si riducono allacondizione ∇f(x) = 0.
Osservazione 10.10. (x, λ, µ) sia un punto di KKT di (X, f). Alloraλigi(x) = 0 per ogni i = 1, . . . ,m. Quindi per ogni i = 1, . . . ,m almenouno dei due numeri λi e gi(x) deve essere uguale a zero.
58
Se inoltre λi + gi(x) 6= 0 per ogni i = 1, . . . ,m (cioe se λi e gi(x) nonsi annullano simultaneamente per nessun indice i), allora (x, λ, µ) sidice un punto di KKT stretto di (X, f).
Teorema 10.11. Sia x ∈ X un punto regolare nel senso di Abadie.x sia un punto di minimo locale di f in X.
Allora esistono λ ∈ Rm e µ ∈ Rp tali che (x, λ, µ) sia un punto di KKT
di (X, f).
Dimostrazione. Per il lemma 9.12 abbiamo f ′(x; v) ≥ 0 per ogniv ∈ T(X,x) e quindi, per ipotesi, per ogni v ∈ Tl(x).
Sia I(x) = i1, . . . , ik con i1 < . . . < ik, quindi k = |I(x)| (e ammessoil caso I(x) = ∅ e quindi k = 0).
Consideriamo la matrice
A := (−∇gi1(x), . . . ,−∇gik(x),∇h1(x),−∇h1(x), . . . ,∇hp(x),−∇hp(x))
che appartiene a Rnk+2p. Allora
v ∈ Tl(x) ⇐⇒ vtA ≥ 0 ⇐⇒ vt ∈ (RnA ≥ 0)
Siccome f ′(x; v) = vt∇f(x), abbiamo quindi (RnA ≥ 0)∇f(x) ≥ 0.
Per il lemma di Farkas (teorema 1.26) cio implica ∇f(x) ∈ ARk+2p+ .
E quindi possibile trovare coefficienti (λi1, . . . , λik, µ11, µ12, . . . , µp1, µp2) ∈ R+
tali che
∇f(x) = −λi1∇gi1(x) − . . . − λik∇gik(x) + (µ11 − µ12)∇h1(x) + . . . +
+(µp1 − µp2)∇hp(x)
Ponendo λi := 0 per i /∈ I(x) e µj := µj1 − µj2 per j = 1, . . . , p abbiamo
∇xL(x, λ, µ) := ∇f(x) +
m∑
i=1
λi∇gi(x) +
p∑
j=1
µj∇hj(x) = 0
con g(x) ≤ 0, h(x) = 0, λ ≥ 0, ‖ λ, g(x) ‖= 0.
(x, λ, µ) e percio un punto di KKT.
59
11. Il caso generale
Situazione 11.1. Come nel capitolo precedente siano date funzionif, g1, . . . , gm, h1, . . . , hp : R
n −→ R tutte di classe C1.
Sia ancora X := (g1 ≤ 0, . . . , gm ≤ 0, h1 = 0, . . . , hp = 0).
Poniamo g := (g1, . . . , gm), h := (h1, . . . , hp).
Denotiamo con ∇h := (∇h1, . . . ,∇hp) la trasposta della jacobiana di h.
L’insieme di indici I(x) e stato definito nella def. 10.2.
Lemma 11.2. Sia x ∈ X. I vettori ∇h1(x), . . . ,∇hp(x) siano linearmen-
te indipendenti e v ∈ Rn tale che ‖ ∇hj(x), v ‖= 0 per ogni j = 1, . . . , p.
Allora esistono ε > 0 e una curva ϕ : (−ε, ε) −→ Rp con le seguenti
proprieta:
(1) ϕ e di classe C1.
(2) ϕ(0) = 0.
(3) ϕ(0) = 0.
(4) hj(x+tv+∇h(x)ϕ(t)) = 0 per ogni t ∈ (−ε, ε) ed ogni j = 1, . . . , p.
Se le funzioni hj sono tutte di classe C2, anche ϕ e di classe C2.
Dimostrazione. Per ogni j = 1, . . . , p definiamo un’applicazioneHj : R
p+1 −→ R tramite
Hj(y, t) := hj(x + tv + ∇h(x)y)
ottenendo cosı una funzione H : Rp+1 −→ R
p con H(0, 0) = 0.
La jacobiana H ′y(0, 0) e data da H ′
y(0, 0) = (∇h(x))t∇h(x) ed e quin-di invertibile essendo per ipotesi i vettori ∇h1(x), . . . ,∇hp(x), cioe lecolonne della matrice ∇h(x), linearmente indipendenti.
Per il teorema delle funzioni implicite esistono ε > 0 ed una funzioneϕ : (−ε, ε) −→ R
p di classe C1 (risp. di classe C2 se anche le funzionihj sono tutte di classe C2) tali che ϕ(0) = 0 e H(ϕ(t), t) = 0 per ognit ∈ (−ε, ε).
Inoltre ϕ(t) = −(H ′y(ϕ(t), t))−1H ′
t(ϕ(t), t), per cui
ϕ(0) = −(H ′y(0, 0))
−1H ′t(0, 0) = −(H ′
y(0, 0))−1(∇h(x))tv = 0
H(ϕ(t), t)) = 0 significa pero proprio hj(x+tv+∇h(x)ϕ(t)) = 0 per ognij = 1, . . . , p.
Corollario 11.3. Sia x ∈ X. I vettori ∇h1(x), . . . ,∇hp(x) siano
linearmente indipendenti e v ∈ Rn tale che ‖ ∇hj(x), v ‖= 0 per ogni
j = 1, . . . , p. Allora esistono ε > 0 e una curva γ : (−ε, ε) −→ Rn con le
seguenti proprieta:
(1) γ e di classe C1.
(2) γ(0) = x.
60
(3) γ(0) = v.
(4) hj(γ(t)) = 0 per ogni t ∈ (−ε, ε) ed ogni j = 1, . . . , p.
Se le funzioni hj sono tutte di classe C2, anche γ e di classe C2.
Dimostrazione. Nel lemma 11.2 e sufficiente porreγ(t) := x + tv + ∇h(x)ϕ(t).
Proposizione 11.4. Sia x ∈ X. I vettori ∇h1(x), . . . ,∇hp(x) siano li-
nearmente indipendenti e v ∈ Rn tale che ‖ ∇hj(x), v ‖= 0 per ogni
j = 1, . . . , p, come nel lemma 11.2, ma anche ‖ ∇gi(x), v ‖< 0 per ognii ∈ I(x).
Allora esistono ε > 0 e una curva γ : (−ε, ε) −→ Rn con le seguenti
proprieta:
(1) γ e di classe C1.
(2) γ(0) = x.
(3) γ(0) = v.
(4) hj(γ(t)) = 0 per ogni t ∈ (−ε, ε) ed ogni j = 1, . . . , p.
(5) gi(γ(t)) < 0 per ogni t ∈ (0, ε) ed ogni i = 1, . . . ,m.
Se le funzioni gi ed hj sono tutte di classe C2, anche γ e di classe C2.
Dimostrazione. Usiamo la curva γ del cor. 11.3, restringendo, se ne-cessario, ε. Infatti per i /∈ I(x), dalla continuita di gi seguegi(γ(t)) < 0 per ogni t sufficientemente piccolo. Possiamo quindi assu-mere che gi(γ(t)) < 0 per ogni t ∈ (−ε, ε) ed ogni i = 1, . . . ,m.
Sia i /∈ I(x) fissato. Definiamo α : (−ε, ε) −→ R tramiteα(t) := gi(γ(t)). Allora α(t) =‖ ∇gi(γ(t)), γ(t) ‖ e quindiα(0) =‖ ∇gi(γ(0)), γ(0) ‖=‖ ∇gi(x), v ‖< 0. Cio implica α(t) < 0 perogni t > 0 sufficientemente piccolo. Restringendo ancora ε troviamoche gi(γ(t)) < 0 per ogni i = 1, . . . ,m ed ogni t ∈ (0, ε).
Definizione 11.5. Un punto x ∈ X si dice regolare nel senso di Mangasarian-Fromovitz, se sono soddisfatte le seguenti condizioni:
(1) I vettori ∇h1(x), . . . ,∇hp(x) sono linearmente indipendenti.
(2) Esiste un vettore v ∈ Rn tale che ‖ ∇hj(x), v ‖= 0 per ogni
j = 1, . . . , p e tale che ‖ ∇gi(x), v ‖< 0 per ogni i ∈ I(x).
In tal caso v si chiama un vettore di Mangasarian-Fromovitz per x.
Queste condizioni coincidono con le ipotesi della prop. 11.4.
Lemma 11.6. Sia x ∈ X un punto regolare nel senso di Mangasarian-
Fromovitz e sia v un vettore di Mangasarian-Fromovitz per x.
Sia u ∈ Tl(x). Allora u + θv ∈ T(X,x) per ogni θ > 0.
Dimostrazione. Sia θ > 0 fissato.
(1) Allora anche u + θv e un vettore di Mangasarian-Fromovitzper x. Infatti, usando l’ipotesi che u ∈ Tl(x), abbiamo
61
‖ ∇hj(x), u + θv ‖=‖ ∇hj(x), u ‖ +θ ‖ ∇hj(x), v ‖= 0
per ogni j = 1, . . . , p e
‖ ∇gi(x), u + θv ‖=‖ ∇gi(x), u ‖ +θ ‖ ∇gi(x), v ‖< 0
per ogni i ∈ I(x).
(2) Per la prop. 11.4 esistono ε > 0 e una curva γ : (−ε, ε) −→ Rn con
le proprieta enunciate in quella proposizione, con u + θv al posto di v.In particolare abbiamo γ(0) = x e γ(0) = u + θv. Ma allora
u + θv = γ(0) = limk−→∞
γ(1/k) − γ(0)
1/k= lim
k−→∞
γ(1/k) − x
1/k
e siccome limk−→∞
γ(1/k) = γ(0) = x, vediamo che u + θv ∈ T(X,x).
Proposizione 11.7. Sia x ∈ X un punto regolare nel senso di Mangasarian-Fromovitz. Allora x e un punto regolare nel senso di Abadie.
Dimostrazione. Per la prop. 10.4 dobbiamo dimostrare cheTl(x) ⊂ T(X,x).
Siano u ∈ Tl(x) e v un vettore di Mangasarian-Fromovitz per x. Peril lemma 11.6 u + θv ∈ T(X,x) per ogni θ > 0. Ma lim
θ−→0u + θv = u,
quindi vediamo che u ∈ T(X,x). Dal lemma 9.8 sappiamo pero cheT(X,x) e chiuso e quindi u ∈ T(X,x).
Teorema 11.8. Sia x ∈ X regolare nel senso di Mangasarian-Fromovitz.x sia inoltre un punto di minimo locale di f in X.
Allora esistono λ ∈ Rm e µ ∈ Rp tali che (x, λ, µ) sia un punto di KKTdi (X, f).
Dimostrazione. Cio segue dal teorema 10.11 applicando la prop. 11.7.
Definizione 11.9. Sia x ∈ X. Diciamo che x e un punto a vincoli
linearmente indipendenti, se i gradienti ∇gi(x) per i ∈ I(x) e∇h1(x), . . . ,∇hp(x) sono linearmente indipendenti.
Lemma 11.10. x sia un punto a vincoli linearmente indipendenti. Al-lora x e regolare nel senso di Mangasarian-Fromovitz.
Dimostrazione. La condizione (1) della def. 11.5 e evidentementesoddisfatta.
(2) Possiamo assumere che I(x) = 1, . . . , q con 0 ≤ q ≤ m. Per ipo-tesi esistono vettori Aq+p+1, . . . , An ∈ R
n tali che la matriceA := (∇g1(x), . . . ,∇gq(x),∇h1(x), . . . ,∇hp(x), Aq+p+1, . . . , An) sia inver-tibile. Sia b := (−1, . . . ,−1︸ ︷︷ ︸
q
, 0, . . . , 0︸ ︷︷ ︸p
, 1 . . . 1)t. Allora l’equazione Atv = b
possiede un’unica soluzione v perche la matrice A e invertibile.E immediato che v soddisfa la condizione (2) della def. 11.5.
Teorema 11.11. x sia un punto di minimo locale di f in X e allo stesso
tempo anche un punto a vincoli linearmente indipendenti.
62
Allora esistono, univocamente determinati, λ ∈ Rm e µ ∈ Rp tali che
(x, λ, µ) sia un punto di KKT di (X, f).
Dimostrazione. (1) Per il lemma 11.10 l’esistenza di λ e µ segue dalteorema 11.8.
(2) Dimostriamo l’unicita. Assumiamo di nuovo che I(x) = 1, . . . , kcon 0 ≤ k ≤ m. Dall’oss. 10.10 sappiamo che λi = 0 per i > k. Inoltre
k∑
i=1
λi∇gi(x) +
p∑
j=1
µj∇hj(x) = −∇f(x)
Questa rappresentazione, e quindi i numeri λ1, . . . , λk, µ1, . . . , µp, sonounivocamente determinati perche, per ipotesi, i vettori∇g1(x), . . . ,∇gk(x),∇h1(x), . . . ,∇hp(x) sono linearmente indipendenti.
63
12. Restrizioni lineari
Situazione 12.1. Siano f : Rn −→ R di classe C1 ed a1, . . . , am, b1, . . . , bp ∈ Rn,
α1, . . . , αm, β1, . . . , βp ∈ R. Sia
X := x ∈ Rn | a1x ≤ α1, . . . , a
mx ≤ αm, b1x = β1, . . . , bpx = βp
Ponendo gi := ©x
aix − αi per i = 1, . . . ,m ed hj := ©x
bjx − βj per
j = 1, . . . , p abbiamo X = (g1 ≤ 0, . . . , gm ≤ 0, h1 = 0, . . . , hp = 0) comenei capitoli precedenti.
Proposizione 12.2. Ogni punto di X e regolare nel senso di Abadie.
Dimostrazione. Sia x ∈ X. Per la prop. 10.4 dobbiamo solo dimostra-re che Tl(x) ⊂ T(X,x).
Sia v ∈ Tl(x). Siccome ∇gi(x) = (ai)t e ∇hj(x) = (bj)t per ogni i, j,cio significa che aiv ≤ 0 per ogni i ∈ I(x) e bjv = 0 per ogni j = 1, . . . , p.
Per k ∈ N + 1 siano tk := 1k
ed xk := x + tkv. Per k sufficientementegrande abbiamo allora
aixk = ai(x + tkv) = αi + tkaiv ≤ αi per i ∈ I(x)
aixk = ai(x + tkv) = aix + tkaiv < αi per i /∈ I(x)
bjxk = bj(x + tkv) = βj + tkbjv = βj per j = 1, . . . , p
Cio mostra che xk ∈ X per k >> 0. Inoltre da un lato ©k
xk −→ x,
dall’altro ©k
xk − x
tk= ©
k
v −→ v, per cui v ∈ T(X,x).
Teorema 12.3. x sia un punto di minimo locale di f . Allora esistono
λ ∈ Rm e µ ∈ Rp tali che sono soddisfatte le seguenti condizioni:
(∇f(x))t +
m∑
i=1
λiai +
p∑
j=1
µjbj = 0
aix ≤ αi per i = 1, . . . ,m
bjx = βj per j = 1, . . . , p
λ ≥ 0
λi(aix − αi) = 0 per i = 1, . . . ,m
Dimostrazione. Per la prop. 12.2 x e regolare nel senso di Abadie, percui possiamo applicare il teorema 10.11. Le condizioni nell’enunciatosono esattamente le condizioni di KKT, tenendo conto dell’oss. 10.10.
64
13. Restrizioni convesse
Osservazione 13.1. X sia un sottoinsieme convesso di Rn ed
f : Rn −→ R una funzione convessa. Se x e un punto di minimo locale
di f in X, allora x e anche un punto di minimo globale, cioe f(x) ≤ f(y)per ogni y ∈ X. Possiamo quindi tralasciare le specificazioni ”locale”risp. ”globale”.
Dimostrazione. Altrimenti esiste un y ∈ X tale che f(y) < f(x).Siccome x e un punto di minimo locale, possiamo trovare t ∈ (0, 1] conf(x + t(y − x)) ≥ f(x). La funzione f e pero convessa, per cui
f(x + t(y − x)) ≤ f(x) + tf(y) − tf(x) < f(x) + tf(x) − tf(x) = f(x)
una contraddizione. Nell’ultima disuguaglianza abbiamo utilizzato lacondizione che t > 0.
Lemma 13.2. La funzione f : Rn −→ R sia di classe C1.
Allora sono equivalenti:
(1) f e convessa.
(2) Per x, y ∈ Rn vale ‖ ∇f(x), y − x ‖≤ f(y) − f(x).
Dimostrazione. Corsi di Analisi.
Situazione 13.3. Siano f, g1, . . . , gm : Rn −→ R funzioni convesse di
classe C1 e b1, . . . , bm ∈ Rn, β1, . . . , βp ∈ R. Siano
X := x ∈ Rn | g1(x) ≤ 0, . . . , gm(x) ≤ 0, b1x = β1, . . . , b
px = βp
X := x ∈ Rn | g1(x) < 0, . . . , gm(x) < 0, b1x = β1, . . . , b
px = βp
E immediato che gli insiemi X e X sono convessi.
Osservazione 13.4. Sia (x, λ, µ) ∈ Rn × Rm × Rp. Allora sono equiva-
lenti:
(1) (x, λ, µ) e un punto di KKT di (X, f).
(2) ∇f(x) +∑
i∈I(x)
λi∇gi(x) +
p∑
j=1
µj(bj)t = 0
gi(x) ≤ 0 per ogni i = 1, . . . ,m
bjx = βj per ogni j = 1, . . . , p
λ ≥ 0
‖ λ, g(x) ‖= 0
Dimostrazione. E sufficiente osservare che λi = 0 per i /∈ I(x) perl’oss. 10.10.
Proposizione 13.5. (x, λ, µ) ∈ Rn × Rm × Rp sia un punto di KKT di
(X, f). Allora x e un punto di minimo di f in X.
65
Dimostrazione. Per definizione abbiamo x ∈ X. Sia y ∈ X.Dalle condizioni di KKT e dal lemma 13.2 segue
f(y) ≥ f(x)+ ‖ ∇f(x), y − x ‖
= f(x) −∑
i∈I(x)
λi ‖ ∇gi(x), y − x ‖ −
p∑
j=1
µjbj(y − x)
= f(x) −∑
i∈I(x)
λi ‖ ∇gi(x), y − x ‖
dove abbiamo tenuto conto dell’oss. 13.4 e del fatto che anche y ∈ X.
Pero anche le funzioni gi sono convesse, percio dal lemma 13.2 otte-niamo∑
i∈I(x)
λi ‖ ∇gi(x), y − x ‖≤∑
i∈I(x)
λi(gi(y) − gi(x))
=∑
i∈I(x)
λigi(y) ≤ 0
e cio mostra f(x) ≤ f(y).
Definizione 13.6. Per x ∈ X sia
Tls(x) := v ∈ Rn |‖ ∇gi(x), v ‖< 0 per ogni i ∈ I(x),
bjv = 0 per j = 1, . . . , p
Tls(x) si chiama il cono tangente linearizzato stretto di X in x.
Lemma 13.7. Sia x ∈ X. Allora Tls(x) ⊂ T(X,x).
Dimostrazione. Sia v ∈ Tls(x). Per k ∈ N + 1 poniamo tk := 1k
e
xk := x + tkv. Allora ©k
xk −→ x, ©k
tk ∈ [R++ −→ 0] e
©k
xk − x
tk= ©
k
v ∈ [Rn −→ v]. Pertanto e sufficiente dimostrare che
xk ∈ X per k >> 0.
(1) In primo luogo per ogni j = 1, . . . , p ed ogni k ∈ N + 1 abbiamo
bjxk = bj(x + tkv) = bjx + tkbjv = βj
perche x ∈ X e v ∈ Tls(x).
(2) Sia i ∈ 1, . . . ,m ed i /∈ I(x). Allora gi(x) < 0 e quindi gi(xk) < 0per k >> 0.
(3) Sia i ∈ I(x) e quindi gi(x) = 0. Per ipotesi
0 >‖ ∇gi(x), v ‖= limt−→0
gi(x + tv) − gi(x)
t= lim
t−→0
gi(x + tv)
t= lim
k−→∞
gi(xk)
tkCio implica gi(xk) < 0 per k >> 0.
Lemma 13.8. Sia x ∈ X. Se X 6= ∅, allora
Tls(x) = T(X,x) = Tl(x).
Dimostrazione. (1) Siccome per il lemma 9.8 T(X,x) e chiuso, la
prop. 10.4 e il lemma 13.7 implicano che Tls(x) ⊂ T(X,x) ⊂ Tl(x).
66
(2) E sufficiente dimostrare quindi che Tl(x) ⊂ Tls(x).Sia v ∈ Tl(x) e quindi ‖ ∇gi(x), v ‖≤ 0 per ogni i ∈ I(x) e bjv = 0 perogni j = 1, . . . , p.
Per ipotesi X 6= ∅, percio possiamo trovare y ∈ Rn tale che gi(y) < 0
per ogni i = 1, . . . ,m e bjy = βj per ogni j = 1, . . . , p.
Dal lemma 13.2 abbiamo ‖ ∇gi(x), y − x ‖≤ gi(y) − gi(x) = gi(y) < 0per ogni i ∈ I(x), mentre bj(y − x) = bjy − bjx = βj − βj = 0 per ognij = 1, . . . , p. Se per k ∈ N + 1 poniamo tk := 1
ke wk := v + tk(y − x),
abbiamo quindi
‖ ∇gi(x), wk ‖=‖ ∇gi(x), v ‖ +tk ‖ ∇gi(x), y − x ‖< 0
per ogni i ∈ I(x) e bjwk = bjv = 0, cosicche wk ∈ Tls(x) per ogni
k ∈ N + 1. Pero limk−→∞
wk = v e vediamo che v ∈ Tls(x).
Teorema 13.9. Sia X 6= ∅. Allora per x ∈ X sono equivalenti:
(1) x e un punto di minimo per f in X.
(2) Esiste (λ, µ) ∈ Rm × Rp tale che (x, λ, µ) e un punto di KKT di
(X, f).
Dimostrazione. (1)=⇒(2): Lemma 13.8 e teorema 10.11
(2)=⇒(1): Prop. 13.5.
Teorema 13.10. Le funzioni gi per i = 1, . . . ,m siano della formagi(x) = aix − αi con ai ∈ R
n ed αi ∈ R.
Allora per x ∈ X sono equivalenti:
(1) x e un punto di minimo per f in X.
(2) Esiste (λ, µ) ∈ Rm × Rp tale che (x, λ, µ) e un punto di KKT di
(X, f).
Dimostrazione. Se qui X = ∅, allora possiamo aggiungere le fun-zioni ©
xaix − αi alle funzioni ©
xbjx − βj , trovandoci cosı in un caso
in cui le ipotesi del teorema 13.9 (o del lemma 13.8) sono banalmentesoddisfatte.
67
68
Bibliografia
M. Aigner: Diskrete Mathematik. Vieweg 2004.
W. Alt: Nichtlineare Optimierung. Vieweg 2002.
I. Baroncelli: Ottimizzazione genetica. Tesi, Ferrara 1991.
K. Bennett/O. Mangasarian: Robust linear programming discriminati-on of two linearly inseparable sets.Opt. Meth. Software 1 (1992), 23-34.
D. Bertsekas: Nonlinear programming. Athena Scientific 1999.
S. Boyd/L. Vandenberghe: Convex optimization. Cambridge UP 2008.
R. Cottle/E. Johnson/R. Wets: George B. Dantzig (1914-2005).Notices AMS March 2007, 344-362.
G. Dantzig: Linear programming. Operations Res. 50/1 (2002), 42-47.
J. Eaton/D. Bateman/S. Hauberg: GNU Octave. Network Theory 2008.
S. Gass: The life and times of the father of linear programming.OR/MS Today August 2005, 10p.
C. Geiger/C. Kanzow: Theorie und Numerik restringierter Optimierungs-aufgaben. Springer 2002.
J. Gross/J. Yellen: Graph theory and its applications.Chapman & Hall 2006.
F. Jarre/J. Stoer: Optimierung. Springer 2004.
D. Jungnickel: Optimierungsmethoden. Springer 1999.
O. Mangasarian/W. Street/W. Wolberg: Breast cancer diagnosis andprognosis via linear programming. Op. Res. 43/4 (1995), 570-578.
J. Matousek/B. Gartner: Understanding and using linear programming.Springer 2007, 220p. Eur 41.
J. Nocedal/S. Wright: Numerical optimization. Springer 2006.
69
Top Related