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