Monica Gazzetta

by user

on 06 июля 2016

Category: Documents

>> Downloads: 2

views

Report

Comments

Description

Download Monica Gazzetta

Transcript

Monica Gazzetta

UNIVERSITÀ DEGLI STUDI DI FERRARA
FACOLTÀ DI SCIENZE MATEMATICHE, FISICHE E
NATURALI
Corso di Laurea Specialistica in
MATEMATICA
IL LEMMA DI FARKAS E LE CONDIZIONI
DI KARUSH-KUHN-TUCKER
NELL’OTTIMIZZAZIONE LINEARE E
NON LINEARE
Relatori:
Laureanda:
Chiar.mo Prof.
Josef Eschgfäller
Monica Gazzetta
Dott.ssa Silvia Bonettini
Anno Accademico 2008-2009
Indice
Introduzione
3
I.
IL METODO DEL SIMPLESSO
1.
Il lemma di Farkas
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.
5
ALCUNE APPLICAZIONI
6.
Il separatore di Bennett-Mangasarian
37
7.
Grafi
40
8.
Flussi in un grafo diretto
44
III.
9.
OTTIMIZZAZIONE NON LINEARE
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 (anche
dal punto di vista geometrico ed algebrico) alcuni concetti basilari della programmazione lineare e non lineare che sono il lemma di Farkas e
le condizioni di Karush-Kuhn-Tucker (dette anche condizioni di KKT).
In questo lavoro inoltre, è stato descritto un algoritmo di risoluzione
per problemi di programmazione lineare, il metodo del simplesso, e
sono state presentate alcune sue possibili applicazioni pratiche.
Il lemma di Farkas è l’argomento del primo capitolo ed è forse il più
importante teorema di alternativa per sistemi lineari e viene inoltre
utilizzato in numerosi contesti come la programmazione lineare e non
lineare, la teoria dei sistemi di disequazioni lineari, i modelli economici multisettoriali e la teoria dei giochi.
Questo lemma afferma che il sistema Ax = b ( dove A è una matrice
m × n e x e b sono vettori rispettivamente appartenenti ad Rm ed Rn )
con la condizione x ≥ 0 ammette soluzione se e solo se non la ammette
il sistema costituito dalle due condizioni yA ≥ 0 e yb < 0 con y ∈ Rm .
Grazie al lemma di Farkas, si può dimostrare, sotto opportune ipotesi, che se un punto è soluzione di un problema di programmazione in
generale non lineare, allora in tale punto sono soddisfatte le condizioni
di KKT.
Le condizioni di Karush-Kuhn-Tucker sono descritte nel capitolo 10
e costituiscono la parte fondamentale della terza sezione della tesi.
Esse sono una generalizzazione del metodo dei moltiplicatori di Lagrange applicato a problemi in cui sono presenti anche vincoli di disuguaglianza e rappresentano lo scheletro della programmazione non
lineare costituendo condizioni necessarie per la soluzione di un problema di programmazione non lineare in cui i vincoli soddisfano opportune condizioni di regolarità dette condizioni di qualificazione dei
vincoli. Esempi di queste qualificazioni che vengono trattate nella tesi
sono il requisito di indipendenza lineare dei vincoli e il requisito di
Mangasarian-Fromovitz. Per problemi di programmazione lineare invece, le condizioni di KKT sono sia necessarie che sufficienti. Queste
questioni vengono descritte nei capitoli 11, 12 e 13 dove sono presenti
rispettivamente vincoli generici, vincoli lineari e vincoli convessi. Nel
capitolo 9 diamo alcune definizioni che caratterizzano le condizioni di
KKT dal punto di vista geometrico.
La prima parte della tesi riguarda la teoria e l’implementazione del
metodo del simplesso. Questo algoritmo è stato inventato dal matematico e statistico statunitense George B. Dantzig nel 1947 e rappresenta
ancora oggi uno dei metodi più famosi e più efficaci nella risoluzione di
problemi di programmazione lineare, problemi in cui si cerca di massimizzare o minimizzare una funzione lineare sotto opportuni vincoli
di uguaglianza e disuguaglianza anch’essi lineari.
L’insieme di definizione dei vincoli è detto insieme ammissibile ed è
un poliedro convesso. Se il problema di programmazione lineare am3
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 inventato da Dantzig, la cui idea principale può quindi essere cosı̀ descritta:
si determina un vertice iniziale del poliedro e si decide se tale punto
è una soluzione ottima; se non lo è si determina in modo adeguato un
nuovo vertice del poliedro e se ne testa l’ottimalità e cosı̀ via.
L’algoritmo del simplesso si applica in una prima formulazione ai
programmi lineari nella forma f x = max (risp. min), x ≥ 0, Ax = b (forma normale) oggetto del capitolo 3. Questo tuttavia non è limitativo
perchè, come viene descritto nel cap. 2, ogni altro programma lineare
può essere ricondotto alla forma normale utilizzando opportune variabili di slack o di surplus. Gli aspetti teorici del metodo del simplesso
vengono approfonditi nel capitolo 3 mentre l’algoritmo tradotto in Matlab (o Octave) è presentato nel quarto capitolo. Nel capitolo 5 vengono
invece descritte alcune proprietà degli insiemi convessi.
Nella seconda parte della tesi esponiamo alcuni possibili campi di
applicazione 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 problema
di trovare un iperpiano che separa due insiemi di punti distinti possa
essere ricondotto ad un problema di programmazione lineare. È un
risultato che viene ad esempio utilizzato nella ricerca sperimentale
riguardante la diagnosi e la prognosi del carcinoma mammario.
È opportuno ricordare che oltre al metodo del simplesso esistono
altri metodi altrettanto efficaci per la risoluzione di problemi di programmazione lineare e non lineare: i metodi a punto interno.
Questi dal punto di vista geometrico si differenziano notevolmente dal
metodo del simplesso in quanto la ricerca della soluzione ottimale non
viene effettuata esaminando i vertici del poliedro ammissibile ma rimanendo all’interno dell’insieme di definizione dei vincoli. I metodi
a punto interno discendono dalla condizioni di KKT opportunamente modificate (in modo da rimanere sempre all’interno della regione
ammissibile) 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 ∈ Rn | x ≥ 0}
R+
m := {f ∈ Rm | f ≥ 0}
R+ := [0, ∞)
n
m
Definizione 1.3. Siano A ∈ Rm
n , X ⊂ R , U ⊂ Rm , b ∈ R ,
f ∈ Rn . Definiamo allora:
AX := {Ax | x ∈ X}
U A := {uA | u ∈ U }
(AX = b) := {x ∈ X | Ax = b}
(U A = f ) := {u ∈ U | uA = f }
(AX ≤ b) := {x ∈ X | Ax ≤ b}
(U A ≥ f ) := {u ∈ U | uA ≥ f }
In modo analogo sono definiti (AX ≥ b), (U A ≤ f ), ecc.
Avremo quindi ad esempio (ARn+ = b) = {x ∈ Rn+ | Ax = b}.
Nota 1.4. Useremo le seguenti notazioni e formule ben note del calcolo
matriciale:
i
(1) Per A ∈ Rm
n denotiamo con A la i-esima riga, con Aj la j-esima
colonna di A.
n
(2) Per A ∈ Rm
n , B ∈ Rs abbiamo allora
(AB)ij = Ai Bj
(AB)i = Ai B
(AB)j = ABj
AB =
n
X
Aα B α
α=1
Abbiamo quindi in particolare, per x ∈ Rn ed f ∈ Rm ,
5
Ax =
n
X
Aα xα
α=1
fA =
m
X
fα Aα
α=1
(3) Con kx, yk = xt y risp. kf, gk = f gt denoteremo il prodotto scalare
di x, y ∈ Rn risp. f, g ∈ Rm .
(4) Per vettori v1 , ..., vk in uno spazio vettoriale sia SV(v1 , ..., vk ) il
sottospazio vettoriale generato da questi vettori. Similmente
per un sottoinsieme X denoteremo con SV(X) il sottospazio vettoriale generato da X .
(5) Per X ⊂ Rn sia X ⊥ := {v ∈ Rn | kx, vk = 0 per ogni x ∈ X}.
X ⊥ è un sottospazio vettoriale di Rn , anche quando X stesso
non è un sottospazio vettoriale.
(6) W sia un sottospazio vettoriale di Rn . Allora:
dim W + dim W ⊥ = n
W ⊥⊥ = W
L ⊥
Rn = W
W
(7) Per vettori v1 , ..., vk in uno spazio vettoriale reale sia
POS(v1 , ..., vk ) := {λ1 v1 + ... + λk vk | λ1 , ..., λk ∈ R+ }.
Similmente per un sottoinsieme X sia
POS(X) := {λ1 x1 + ... + λk xk | k ≥ 1, λi ∈ R+ , xi ∈ X per
i = 1, ..., k}.
Osservazione 1.5. Sia A ∈ Rm
n . Allora:
(1) ARn = SV(A1 , ..., An ).
(2) ARn+ = POS(A1 , ..., An ).
Dimostrazione. (1) Sia x ∈
Rn .
Allora Ax =
n
X
Ak xk ∈ SV(A1 , ..., An )
k=1
e viceversa. Il punto (2) si dimostra in modo analogo considerando
x ∈ Rn+ .
m
Lemma 1.6. Siano A ∈ Rm
n e b ∈ R . Allora sono equivalenti:
(1) b ∈ ARn .
(2) (Rm A = 0)b = 0.
Dimostrazione. (1) =⇒ (2): Sia f ∈ Rm con f A = 0. Poiché per ipotesi
b ∈ ARn , esiste x ∈ Rn tale che b = Ax. Allora f b = f Ax = 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
kb, yk = kw + y, yk = kw, yk + ky, yk = ky, yk =
6 0
Inoltre kAj , yk = 0 per ogni j perché y ∈ W ⊥ . Con f := y t abbiamo
allora f A = 0 ed f b 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 sottoinsieme 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]. Allora
z = ϕ([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 abbiamo
sfruttato 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 che
v1 , ..., vk , vk+1 , ..., vm sia una base di Rm . Per ogni x ∈ Rm esistono
λ1 (x), ..., λm (x) ∈ R tali che x = λ1 (x)v1 + ... + λm (x)vm . Le funzioni
λi : Rm → R che cosı̀ otteniamo sono continue. Perciò l’insieme
POS(v1 , ..., vk ) = (λ1 ≥ 0, ..., λk ≥ 0, λk+1 = 0, ..., λm = 0) è chiuso.
Proposizione 1.10 (lemma di Carathéodory). Sia X ⊂ Rm e
SV(X) 6= 0. Sia d := dim SV(X). Allora:
(1) Ogni punto di POS(X) è combinazione lineare a coefficienti non
negativi di al massimo d punti linearmente indipendenti di X .
(2) Sia D la famiglia di tutti gli insiemi che consistono di esattamente d vettori linearmente
indipendenti di X .
[
Allora POS(X) =
POS(D).
D∈D
7
Dimostrazione. (1) Sia v ∈ POS(X). Esistono quindi λ1 , ..., λk ≥ 0 ed
x1 , ..., xk ∈ X tali che v = λ1 x1 + ... + λk xk . Scegliamo k minimale (ciò
implica λj > 0 per ogni j ) e supponiamo per assurdo che k > d.
Siccome per ipotesi dim SV(X) = d, i vettori x1 , ..., xk devono essere
linearmente dipendenti, perciò esistono α1 , ..., αk ∈ R non tutti nulli
tali che α1 x1 + ... + αk xk = 0.
αj
α1
Possiamo assumere che α1 > 0 e che
≥
per ogni j . Ciò implica
λ1
λj
k
X
αj
αj
λj ≥
(λj −
λ1 per ogni j . Abbiamo però
λ1 )xj = v .
α1
α1
j=1
In questa rappresentazione tutti i coefficienti sono ≥ 0 e il primo è
nullo, in contraddizione alla minimalità di k.
[
(2) Ciò implica anche che POS(X) ⊂
POS(D) perché per il punto
D∈D
(1) per ogni elemento x ∈ POS(X) esistono elementi x1 , ..., xk ∈ X
linearmente indipendenti con x ∈ POS(x1 , ..., xk ) e k ≤ d; se k < d,
allora possiamo trovare xk+1 , ..., xd tali che
{x1 , ..., 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.
= {v1 , ..., vk }. D sia definito come nella prop.
Dimostrazione. Sia X[
1.10. Allora POS(X) =
POS(D). Per il lemma 1.9 per ogni
D∈D
D ∈ D l’insieme POS(D) è chiuso. Nel nostro caso D è un insieme finito
e quindi anche POS(X) è chiuso.
m
n
Corollario 1.12. Sia A ∈ Rm
n . Allora l’insieme AR+ è chiuso in R .
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́ in
genere un’applicazione lineare Rn −→ Rm non trasforma chiusi in
chiusi. Un esempio è la proiezione sulla prima coordinata R2 → R che
trasforma l’iperbole {x | x1 x2 = 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 minimale da y .
Dimostrazione. Siccome X 6= ∅, possiamo scegliere un punto (arbitrario) z ∈ X . Allora l’insieme A =: {a ∈ X | |a−y| ≤ |z−y|} è compatto
e non vuoto, per cui la funzione continua |a − y| : A −→ R assume
a
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 + 2kx, yk + |x|2 + |y|2 −
2kx, yk = 2|x|2 + 2|y|2 .
Teorema 1.16. X sia un sottoinsieme chiuso, convesso e non vuoto di
Rm 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
p+q
− y|2
2
= |(p − y) + (q − y)|2
4|r − y|2 = 4|
= 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 piú
distanza minimale da y .
L’uguaglianza (*) e la relazione |r−y|2 < |p−y|2 per p 6= q sono anche
evidenti dalla figura.
q
r
y
p
Definizione 1.17. Nella situazione del teorema 1.16 il punto p si chiama 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 | kx − p, vk = 0}
O(p, v) := {x ∈ Rm | kx − p, vk ≤ 0}
SO(p, v) := {x ∈ Rm | kx − p, vk < 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 o
su questo iperpiano, O(p, −v) l’insieme dei punti che non si trovano
oltre questo iperpiano, cioè dalla stessa parte di p + v . SO significa
strettamente oltre.
9
Proposizione 1.19. X sia un sottoinsieme chiuso, convesso e non vuoto
di Rm ed y ∈ Rm . 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 =
2
2
.
2
|y − p| + t |x − p| − 2tky − p, x − pk
ovvero
2tky − p, x − pk ≤ t2 |x − p|2
Per ogni t ∈ (0, 1] abbiamo perciò 2ky − p, x − pk ≤ t|x − p|2 .
Ciò è possibile solo se ky − p, x − pk ≤ 0.
(2) =⇒ (1): Siano X ⊂ O(p, y − p) ed x ∈ X . Allora ky − p, p − xk ≥ 0
e quindi
|y − x|2 = |y − p + p − x|2 = |y − p|2 + |p − x|2 + 2ky − p, p − xk ≥ |y − p|2
Lemma 1.20. X sia un sottoinsieme chiuso, convesso e non vuoto di
Rm ed y ∈ Rm . 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
k(x − p) − t(y − p), y − pk = kx − p, y − pk − t|y − p|2 ≤ 0
essendo per la prop 1.19 kx − p, y − pk ≤ 0.
Sia ora y ∈
/ X . Allora y 6= p e quindi per t = 1 otteniamo
kx − y, y − pk = kx − p, y − pk − |y − p|2 < 0.
Lemma 1.21. X sia un sottoinsieme chiuso, convesso e non vuoto di
Rm ed y ∈ Rm \ X . p sia la proiezione di y su X ed y ∗ := p+y
2 . Allora:
y ∈ SO(y ∗ , p − y)
X ⊂ SO(y ∗ , y − p)
10
Dimostrazione.
(1) 2ky − y ∗ , p − yk = 2ky −
p+y
, p − yk = −ky − p, y − pk < 0
2
(2) Sia x ∈ X . Allora
p+y
, y − pk
2
= kx − p, y − pk + kx − y, y − pk < 0
2kx − y ∗ , y − pk = 2kx −
Infatti per la prop. 1.19 abbiamo kx − p, y − pk ≤ 0, mentre dal lemma
1.20 segue che kx − y, y − pk < 0.
X
p
y
Corollario 1.22. X sia un sottoinsieme chiuso, convesso e non vuoto di
Rm ed y ∈ Rm \ X . p sia la proiezione di y su X . Sia ancora y ∗ := p+y
2 .
Allora
ky, y − pk > ky ∗ , y − pk > kx, y − pk
per ogni x ∈ X .
Dimostrazione. Sia x ∈ X . Per il lemma 1.21 abbiamo
ky − y ∗ , y − pk > 0 > kx − y ∗ , y − pk
ovvero
ky, y − pk − ky ∗ , y − pk > 0 > kx, y − pk − ky ∗ , y − pk
e quindi
ky, y − pk > ky ∗ , y − pk > kx, y − pk
Corollario 1.23. X sia un sottoinsieme chiuso e convesso di Rm ed
y ∈ Rm \ X . Allora esistono α ∈ R ed f ∈ Rm tali che f y > α > f x per
ogni x ∈ X . Sostituendo f con −f ed α con −α possiamo naturalmente
anche ottenere f y < α < f x per ogni x ∈ X .
Dimostrazione. L’enunciato è banale per X = ∅ e segue altrimenti
dal corollario 1.22, se poniamo f := (y − p)t ed α := ky ∗ , y − pk
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 che
u = λ1 x1 + ... + λk xk e v = µ1 y1 + ... + µl yl . Sia t ∈ [0, 1]. Allora
11
u + t(v − u) = λ1 x1 + ... + λk xk + tµ1 y1 + ... + tµl yl − tλ1 x1 − ... − tλk xk
= (1 − t)λ1 x1 + ... + (1 − t)λk xk + tµ1 y1 + ... + tµl yl
I coefficienti (1 − t)λi e tµj sono tutti non negativi, per cui vediamo che
u + t(v − u) ∈ POS(X).
n
Corollario 1.25. Sia A ∈ Rm
n . Allora AR+ è convesso.
Dimostrazione. Ciò segue dall’oss. 1.24 perché ARn+ = POS(A1 , ..., An )
per l’oss. 1.5.
m
Teorema 1.26 (lemma di Farkas). Siano A ∈ Rm
n e b ∈ R . Allora
sono equivalenti:
(1) b ∈ ARn+ .
(2) (Rm A ≥ 0)b ≥ 0.
Dimostrazione. (1) =⇒ (2): Siano x ∈ Rn+ ed f ∈ Rm tali che b = Ax
ed f A ≥ 0. Allora f b = f Ax ≥ 0.
(2) =⇒ (1): Sia b ∈
/ ARn+ . Dai corollari 1.12 e 1.25 sappiamo che ARn+
è un sottoinsieme convesso, chiuso e non vuoto di Rm ; quindi per il
corollario 1.23 esistono α ∈ R e f ∈ Rm tali che f b < α < f Ax per ogni
x ∈ Rn+ . Ciò deve valere in particolare per x = 0 e questo implica α < 0
e quindi anche f b < 0.
D’altra parte però f A ≥ 0 e ciò è in contraddizione con l’ipotesi (2).
Infatti sia ad esempio f Aj < 0. Siccome x := tAj = Atδj ∈ ARn+ ,
abbiamo α < f tAj = tf Aj per ogni t ≥ 0, ma ciò non è possibile
perché lim tf Aj = −∞.
t−→∞
m
Osservazione 1.27. Siano A ∈ Rm
n e b ∈ R . Denotiamo con δ la
n
matrice identica in Rn . Allora:
(1) (A δ)Rn+ = {Ax + u | x ∈ Rn+ , u ∈ Rm
+ }.
(2) (ARn+ ≤ b) 6= ∅ ⇐⇒ b ∈ (A δ)Rn+ .
m
Proposizione 1.28. Siano A ∈ Rm
n e b ∈ R . Allora sono equivalenti:
(1) (ARn+ ≤ b) 6= ∅.
(2) (R+
m A ≥ 0)b ≥ 0.
Dimostrazione. (1) =⇒ (2): Siano x ∈ Rn+ ed f ∈ R+
m tali che Ax ≤ b
ed f A ≥ 0. Allora f b ≥ f Ax ≥ 0.
(2) =⇒ (1): Supponiamo che (ARn+ ≤ b) = ∅. Per l’oss. 1.27 ciò significa che b ∈
/ (A δ)Rn+ . Per il teorema 1.26 possiamo quindi trovare un
f ∈ Rm tale che f (A δ) ≥ 0 ed f b < 0. Ma f (A δ) = (f A f ) ≥ 0 è equivalente alle due condizioni f A ≥ 0 ed f ≥ 0, cioè ad f ∈ (R+
m A ≥ 0).
Adesso però f b < 0 è in contrasto con la nostra ipotesi.
12
2. Programmi lineari in forma standard
m
Situazione 2.1. n, m ∈ N + 1 ed A ∈ Rm
n , f ∈ Rn , b ∈ R , quando non
indicato diversamente.
Definizione 2.2. Un programma lineare di massimizzazione in forma
standard è un problema di ottimizzazione della forma
f x = 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 f x è massimale sotto il vincolo Ax ≤ b.
Denotiamo con (f (ARn+ ≤ b) = max) l’insieme degli x ∈ Rn+ (detti
soluzioni del problema) con Ax ≤ b in cui f x assume un massimo su
(ARn+ ≤ b), mentre indichiamo con f (ARn+ ≤ b) = max (senza parentesi
esterne) il problema stesso.
Gli elementi di (ARn+ ≤ b) si chiamano punti ammissibili del problema.
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 è
minimale sotto il vincolo uA ≥ f .
+
Denotiamo con ((R+
m A ≥ f )b = min) l’insieme degli u ∈ Rm (detti
soluzioni del problema) con uA ≥ f in cui ub assume un minimo su
+
(R+
m A ≥ f ), mentre indichiamo con (Rm A ≥ f )b = min (senza parentesi
esterne) il problema stesso.
Gli elementi di (R+
m A ≥ f ) si chiamano punti ammissibili del problema duale.
Osservazione 2.4. I problemi f (ARn+ ≤ b) = max e (R+
m A ≥ f )b = min
si 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+
m A ≥ f )b = min.
Allora f x ≤ uAx ≤ ub.
Dimostrazione. Per ipotesi Ax ≤ b e f ≤ uA con x ≥ 0 e f ≥ 0, per
cui f x ≤ uAx ≤ ub.
Proposizione 2.6. Siano x ∈ (ARn+ ≤ b) ed u ∈ (R+
m A ≥ f ) tali che
f x ≥ ub.
13
Allora x è una soluzione di f (ARn+ ≤ b) = max ed u una soluzione di
(R+
m A ≥ f )b = min.
Dimostrazione. Siano y ∈ (ARn+ ≤ b) e v ∈ (R+
m A ≥ f ). Per il lemma
2.5 abbiamo f y ≤ ub ≤ f x ≤ vb.
Proposizione 2.7. (1) Sia (ARn+ ≤ b) = ∅. Allora o (R+
mA ≥ f ) = ∅
oppure l’insieme (R+
A
≥
f
)b
non
è
limitato
inferiormente.
Il problema
m
(R+
A
≥
f
)b
=
min
quindi
non
possiede
soluzione.
m
n
(2)Sia (R+
m A ≥ f ) = ∅. Allora o (AR+ ≤ b) = ∅ oppure l’insieme
n
f (AR+ ≤ b) non è limitato superiormente.
Il problema f (ARn+ ≤ b) = max quindi non possiede soluzione.
Dimostrazione. Dimostriamo solo il primo enunciato essendo il secondo il suo duale. Sia (ARn+ ≤ b) = ∅. Per la prop. 1.28 esiste quindi
un elemento g ∈ R+
m tale che gA ≥ 0 e gb < 0.
+
Se (R+
m A ≥ f ) = ∅ è chiaro che il problema (Rm A ≥ f )b = min non
possiede soluzione.
+
Assumiamo quindi che (R+
m A ≥ f ) 6= ∅. Sia ad esempio u ∈ Rm 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+
m A ≥ 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) = f x è ben definito.
Similmente, se il problema (R+
m A ≥ f )b = min possiede una soluzio+
ne u, allora il valore min(Rm A ≥ f )b = ub è ben definito.
Teorema 2.9. Gli insiemi (ARn+ ≤ b) e (R+
m A ≥ f ) siano entrambi non
vuoti. Allora i problemi f (ARn+ ≤ b) = max e (R+
m A ≥ f )b = min sono
entrambi risolubili e si ha
max f (ARn+ ≤ b) = min(R+
m A ≥ f )b
Dimostrazione. (1) È sufficiente dimostrare che esistono
x ∈ (ARn+ ≤ b) ed u ∈ (R+
m A ≥ f ) tali che f x ≥ ub. L’enunciato allora si
ottiene applicando la prop. 2.6.
(2) Il nostro scopo quindi è quello di trovare un elemento x ∈ Rn+ ed
t t
t
un elemento u ∈ R+
m tali che Ax ≤ b, uA ≥ f (cioè −A u ≤ −f ) ed
f x ≥ ub. L’ultima disuguaglianza è equivalente a −f x + bt u ≤ 0.
(3) Scrivendo il problema in forma matriciale, ponendo




A
0
b
B :=  0 −At  ∈ Rm+n+1
e c :=  −f t  ∈ Rm+n+1
m+n
t
−f
b
0
≤ c) 6= ∅.
dobbiamo dimostrare che (BRm+n
+
(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 ∈ Rn ed α ∈ R .
Inoltre
14

e
A
pB = (g h α)  0
−f

0
−At  = (gA − αf
bt
− hAt + αbt ) ≥ 0


b
pc = (g h α)  −f t  = gb − hf t < 0
0
cosicché otteniamo
(I) gA ≥ αf
(II) αbt ≥ hAt
(III) gb < hf t
Essendo α ∈ R+ , abbiamo α = 0 oppure α > 0. Dimostriamo che entrambi i casi implicano una contraddizione.
(5) Sia α = 0. Allora gA ≥ 0 ≥ hAt . Per ipotesi gli insiemi (ARn+ ≤ b)
n
e (R+
m A ≥ f ) sono entrambi non vuoti. Perciò esistono x ∈ R+ ed
t
t
t
+
u ∈ Rm tali che Ax ≤ b ed uA ≥ f , quindi anche A u ≥ f . Ma allora
gb ≥ gAx ≥ 0 ≥ hAt ut ≥ hf t
e questo contraddice la disuguaglianza (III).
(6) Rimane il caso α > 0. Le disuguaglianze (I) e (II) significano però
ht
g
A
≥
f
)
e
∈ (ARn+ ≤ b).
che ∈ (R+
m
α
α
ht
g
Dal lemma 2.5 segue f
≤ b ovvero hf t = f ht ≤ gb, ancora in
α
α
contrasto con (III).
Corollario 2.10. Siano x ∈ (ARn+ ≤ b) ed u ∈ (R+
m A ≥ f ). Allora sono
equivalenti:
(1) x è una soluzione di f (ARn+ ≤ b) = max ed u una soluzione di
(R+
m A ≥ f )b = min.
(2) f x = ub.
(3) f x = uAx = ub.
(4) f x ≥ ub.
Dimostrazione. (1) =⇒ (2): Teorema 2.9.
(2) =⇒ (3): Per il lemma 2.5 si ha f x ≤ uAx ≤ ub, ma essendo per
ipotesi f x = ub segue che f x = uAx = ub.
(3) =⇒ (4): Chiaro.
(4) =⇒ (1): Proposizione 2.6.
15
Nota 2.11. Come nella dimostrazione del teorema 2.9 siano




A
0
b
B :=  0 −At  ∈ Rm+n+1
e c :=  −f t  ∈ Rm+n+1 .
m+n
−f
bt
0
x
≤ c) con z =
(1) Sia z ∈ (BRm+n
, x ∈ Rn+ ed y ∈ Rm
+.
+
y
Se poniamo u := y t , allora x è una soluzione di f (ARn+ ≤ b) = max ed u
è una soluzione di (R+
m A ≥ f )b = min.
(2) Siano viceversa x una soluzione di f (ARn+ ≤ b) = max ed u una
+
t
soluzione
di (Rm A ≥ f )b = min. Allora con y := u abbiamo
x
≤ c).
∈ (BRm+n
z :=
+
y
Dimostrazione. Siano z, x, y, u come nell’enunciato. Abbiamo quindi
le seguenti disuguaglianze:
x ≥ 0, y ≥ 0
Ax ≤ b
−At ut ≤ −f t
−f x + bt ut ≤ 0
La terza disuguaglianza è equivalente ad uA ≥ f , la quarta, essendo
bt ut = ub, è equivalente a f x ≥ ub.
Il punto (1) segue adesso dalla prop. 2.6, il punto (2) combinando il
teorema 2.9 con la prop. 2.6.
Osservazione 2.12. Il teorema 2.9 e la nota 2.11 dimostrano l’importanza
e l’utilità del principio di dualità nella programmazione lineare. Vediamo in particolare che la sola ricerca di un punto ammissibile (senza un
compito di massimizzazione o minimizzazione) non è più facile della
soluzione del problema di ottimizzazione che, come visto nella nota
2.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 a
quello della ricerca di un punto
 1 
x
 x2 
 1 

z=
 y2 
 y 
y3
che soddisfa la disuguaglianza
16










7
4
0
0
0

4
5
0
0
0 

3 10 0
0
0 


0
0 −7 −4 −3 

0
0 −4 −5 −3 
−1 −2 28 20 30
x1
x2
y1
y2
y3



 
 
≤
 
 

28
20
30
−1
−2
0








Corollario 2.14. (1) x sia una soluzione di f (ARn+ ≤ b) = max
e 1 ≤ k ≤ m. Se esiste una soluzione u di (R+
m A ≥ f )b = min tale che
uk 6= 0, allora Ak x = bk .
(2) u sia una soluzione di (R+
m A ≥ f )b = min e 1 ≤ k ≤ n. Se esiste
n
una soluzione x di f (AR+ ≤ b) = max tale che xk 6= 0, allora uAk = fk .
Dimostrazione. Dimostriamo solo il primo enunciato, essendo il secondo il suo duale.
Per il corollario 2.10 uAx = ub, e quindi u(b − Ax) = 0, cioè
m
X
uj (bj − Aj x) = 0. Per ipotesi però u ≥ 0 e b − Ax ≥ 0, quindi
j=1
uj (bj − Aj x) ≥ 0 per ogni j = 1, ..., m. Ma allora necessariamente
uj (bj − Aj x) = 0 per ogni j = 1, ..., m, per cui l’ipotesi uk 6= 0 implica
bk − Ak x = 0.
17
3. Programmi lineari in forma normale
m
Situazione 3.1. n, m ∈ N + 1 ed A ∈ Rm
n , f ∈ Rn , b ∈ R , quando non
indicato diversamente.
Definizione 3.2. Un programma lineare di massimizzazione (risp. minimizzazione) in forma normale è un problema di ottimizzazione della
forma
f x = 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 standard. Introducendo un vettore variabile ausiliario p otteniamo un problema in forma normale
x
(f 0)
= max
p
x
≥0
p
x
(A δ)
=b
p
equivalente al primo, nel senso che da ogni soluzione del problema in
forma normale otteniamo una soluzione del problema in forma standard.
(2) Viceversa, dato un problema f (ARn+ = b) = max in forma normale, considerando
f x = max
x≥0
Ax ≤ b
−Ax ≤ −b
otteniamo un problema in forma standard equivalente al primo, nel
senso che da ogni soluzione del problema in forma standard otteniamo
una soluzione del problema in forma normale.
(3) In modo analogo (usando le matrici trasposte) ogni problema di
minimizzazione in forma standard (def. 2.3) è equivalente ad un problema in forma normale e viceversa.
Osservazione 3.4. V e W siano spazi vettoriali reali, ϕ : V −→ W
un’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.8
però ϕ([a, b]) = [ϕ(a), ϕ(b)] ⊂ Y e quindi, utilizzando l’ipotesi che Y sia
convesso, 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 Ax possiamo
x
scrivere (ARn+ = b) = A−1 (b)∩Rn+ . Poiché A è continua, l’insieme A−1 (b)
è chiuso. Inoltre, essendo A un’applicazione affine e b un convesso, per
l’oss. 3.4 anche A−1 (b) è convesso. Infine Rn+ è un chiuso convesso e,
siccome l’intersezione di insiemi chiusi e convessi è ancora chiuso e
convesso, otteniamo l’enunciato.
Definizione 3.6. V sia uno spazio vettoriale reale ed X un suo sottoinsieme convesso. Un vertice (o punto estremale) di X è un punto x ∈ X
che 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 della
definizione 3.6.
(2) vertici(Rn ) = ∅.
(3) vertici(Rn+ ) = {0}.
(4) X := {z ∈ Rn | |z| ≤ 1} sia la palla unitaria chiusa in Rn . Allora
vertici(X) = {z ∈ Rn | |z| = 1}.
(5) X := {z ∈ Rn | |z| < 1} sia la palla unitaria aperta in Rn . Allora
vertici(X) = ∅.
Lemma 3.8. V sia uno spazio vettoriale reale, X un sottoinsieme convesso di V ed x ∈ X . Allora sono equivalenti:
(1) x ∈ vertici(X).
(2) X \ {x} è convesso.
(3) x =
u+v
con u, v ∈ X implica u = v .
2
Dimostrazione. (1) =⇒ (2): Supponiamo per assurdo che esistano
u, v ∈ X \{x} tali che [u, v] 6⊂ X \{x}. Allora x ∈ [u, v], ma per ipotesi ciò
implica 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]. Dobbiamo
dimostrare che x ∈ {u, v}. Se cosı̀ non fosse avremmo u, v ∈ X \ {x} e
quindi per ipotesi [u, v] ⊂ X \ {x}, una contraddizione.
(1) =⇒ (3): Sia 2x = u + v con u, v ∈ X . Per ipotesi x ∈ {u, v}, ad
esempio 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
1
l’ipotesi implica u = v e quindi x = u = v .
2
1 1
Rimangono i casi 0 < t < e < t < 1. Per simmetria è sufficiente
2 2
1
trattare il caso 0 < t < .
2
Poniamo y := u + 2t(v − u). Allora y ∈ X perché 0 < 2t < 1. Inoltre
u+y
y = u + 2(x − u) = 2x − u, cosicché x =
. L’ipotesi implica u = y e
2
quindi x = u.
Per t =
u
x=
u+y
2
y
v
Definizione 3.9. Sia α ⊂ {1, ..., n} un sottoinsieme di cardinalità
|α| = s. Poniamo allora:
(1) Aα := matrice in Rm
s 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 elementi
fj per cui j ∈
/ α.
(3) Per x ∈ Rn sia xα il vettore in Rs che si ottiene da x cancellando
gli elementi xj per cui j ∈
/ α.
Poniamo inoltre 1 − α := {1, ..., n} \ α.
0
∅
Per s = 0 abbiamo Rm
0 = R = R0 = 0, per cui A∅ = f∅ = x = ∅.
Con queste convenzioni possiamo scrivere
Ax = Aα xα + A1−α x1−α
f x = fα xα + f1−α x1−α
Esempio 3.10. Siano A ∈ R35 ed x ∈ R5 . Con α = {1, 4} si ha
1 − α = {2, 3, 5}. Perciò
 1
 1


1 A1 A14
A2 A13 A15
x
Aα xα + A1−α x1−α =  A21 A24 
+  A22 A23 A25  
x4
3
3
A1 A4
A32 A33 A35


 1 1
A12 x2 + A13 x3 + A15 x5
A1 x + A14 x4
4
1
2
2



A22 x2 + A23 x3 + A25 x5
A1 x + A4 x
+
=
4
1
3
3
A32 x2 + A33 x3 + A35 x5
A1 x + A4 x
= Ax

x2
x3 
x5


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
u+v
che 0 =
. È chiaro che ciò implica u = v = 0.
2
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 quindi assumere che x 6= 0 e che [x] = {1, ..., s} con 1 ≤ s ≤ n.
(1) =⇒ (2): Sia x ∈ vertici(ARn+ = b) e sia λ1 A1 + ... + λs As = 0
una combinazione lineare delle colonne Ai con i ∈ [x] e λi ∈ R per
i = 1, ..., s. Supponiamo per assurdo che i λi non siano tutti nulli, ad
esempio possiamo supporre λ1 6= 0. Siccome xi > 0 per ogni i = 1, . . . , s,
possiamo trovare un elemento ε > 0 tale che xi ± ελi ≥ 0 per ogni
i = 1, ..., s. Definiamo i vettori


 1
 1
x − ελ1
x + ελ1
..
..




.
.






 s
 s
 x − ελs 
 x + ελs 
u := 

 e v := 
0
0








..
..




.
.
0
0
u+v
Allora u, v ∈ Rn+ ed x =
.
2
s
s
P
P
λk Ak = Ax = b, e similAk (xk + ελk ) = Ax + ε
Inoltre Au =
k=1
k=1
mente Av = b. Perciò u, v ∈ (ARn+ = b). Per ipotesi x ∈ vertici(ARn+ = b)
e quindi per il punto (3) della prop. 3.8 risulta u = v . Ma ciò non è
possibile perchè λ1 6= 0.
(2) =⇒ (1): Le colonne di A[x] siano linearmente indipendenti. Siano
u+v
. Ciò implica ui + v i = 0 per ogni
u, v ∈ (ARn+ = b) tali che x =
2
i = 1, . . . , s, e quindi ui = v i = 0, essendo u, v ≥ 0. D’altra parte abbias
P
mo Au = Av = b e quindi 0 = A(u − v) =
(ui − v i )Ai . Per ipotesi ciò
i=1
implica ui = v i per ogni i = 1, . . . , s, e quindi u = v . Per la prop. 3.8
quindi risulta che x ∈ vertici(ARn+ = 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 α-invertibile
esiste se e solo se rango(A) = m. Si noti che rango(A) = m da solo
implica 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 := dim W e 1 ≤ s ≤ m
tali 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−s siano linearmente
indipendenti.
Dimostrazione. (1) Se s = m non c’è nulla da dimostrare.
Supponiamo quindi che s < m e dimostriamo che esiste un indice
j ∈ {s + 1, . . . , n} tale che gli s + 1 vettori v1 , . . . , vs , vj sono linearmente
indipendenti.
Infatti, se cosı̀ non fosse, avremmo vj ∈ SV(v1 , . . . , vs ) per ogni
j ∈ {1, . . . , n} e quindi W = SV(v1 , . . . , vs ) in contraddizione all’ipotesi
dim W = m.
(2) Se adesso s + 1 = m, non c’è più nulla da dimostrare. Altrimenti
ripetiamo 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 quindi
b = Ax = Aα xα + A1−α x1−α = Aα xα , per cui xα = A−1
α b. Perciò x è
univocamente 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
(ARn+ = b) è finito.
Dimostrazione. J + (A, b) è finito e quindi, poichè l’immagine di un
insieme finito è finito, anche vertici(ARn+ = b) è un insieme finito.
Proposizione 3.22. Sia (ARn+ = b) 6= ∅. Allora vertici(ARn+ = 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 le
colonne di Aα sono linearmente indipendenti. Supponiamo che non lo
siano. Allora possiamo trovare un vettore λ ∈ Rs \ 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 ogni
i ∈ α ed xh + ελh = 0 per almeno un h ∈ α. Sia ora y ∈ Rn+1 definito
dalle relazioni
y α = xα + ελ
y 1−α = 0
Allora y ≥ 0, inoltre
Ay = Aα y α + A1−α y 1−α = 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
A
b
B :=
, c :=
f
µ
si ha
(f (ARn+ = b) = max) = (BRn+ = c).
Per il cor. 3.5 l’insieme (f (ARn+ = b) = max) è perciò chiuso e convesso (ciò è banalmente vero anche quando è vuoto).
Proposizione 3.24.
vertici(f (ARn+ = b) = max) = (f (ARn+ = b) = max) ∩ vertici(ARn+ = b)
Dimostrazione. (1) Se il problema f (ARn+ = b) = max non ha soluzione, l’enunciato è banalmente vero.
(2) Altrimenti con µ := max f (ARn+ = b) poniamo P := (ARn+ = b),
R := (f Rn+ = µ). Allora (f (ARn+ = b) = max) = P ∩ R, per cui dobbiamo
dimostrare che vertici(P ∩ R) = P ∩ R ∩ vertici(P ). Adesso usiamo il
lemma 3.8.
Sia x ∈ vertici(P ∩R). Dobbiamo dimostrare che x ∈ vertici(P ). Siano
u+v
u, v ∈ P tali che x =
. Però f u ≤ µ, f v ≤ µ, e se ad esempio
2
fu + fv
f u < µ, si avrebbe f x =
< µ. Perciò f u = f v = µ, cosicché
2
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
u+v
. Allora u = v perché x ∈ vertici(P ). Quindi x ∈ vertici(P ∩ R).
x=
2
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 abbiamo (f (ARn+ = b) = max) ∩ vertici(ARn+ = b) = vertici(BRn+ = c).
23
Siccome per ipotesi l’insieme (BRn+ = c) = (f (ARn+ = 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 possiamo
sempre ottenere la condizione rango(A) = m richiesta nella prop. 3.20
e nel corollario 3.21. L’insieme dei vertici di (ARn+ = b) allora è finito
e per il teorema 3.25 una soluzione del problema di massimo si trova
percorrendo tutti i vertici e calcolando max {f x | x ∈ vertici(ARn+ = b)}.
Il numero dei vertici è però molto alto già in problemi di modeste dimensioni, 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
f x = max
Ax = b
x≥0
con
3 1 −1 2 −2 1
f :=
3 2 −5 4 −1 −1
A :=
1 −1 −1 4 −6 1
18
b :=
15
Chiaramente rango(A) = 2. Per applicare l’idea della nota 3.26 dob6
biamo considerare le
= 15 sottomatrici 2 × 2 Aα di A e calcolare
2
α
α
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 seguente riportiamo la tabella con i calcoli effettuati. Il valore massimo
che si ottiene è 81.
24
α
{1,2}
{1,3}
{1,4}
{1,5}
{1,6}
{2,3}
{2,4}
{2,5}
{2,6}
{3,4}
{3,5}
{3,6}
{4,5}
{4,6}
{5,6}
Aα 3 2
1 −1 3 −5
1 −1 3 4
1 4 3 −1
1 −6 3 −1
1 1 2 −5
−1
−1 2 4
−1
4 2 −1
−1 −6 2 −1
−1
1 −5 4
−1 4 −5 −1
−1 −6 −5 −1
−1 1 4 −1
4 −6 4 −1
4 1 −1 −1
−6 1
−1
Aα
−1 −2
1
−5
−1 3 −1 5
1
2
−1 3 4 −4
1
8
−1
3 −6 1
1
− 17
−1 3
1 1
1
4
−1
3 −1
5
− 17
1
2
4 −4
1
12
1 2 −6 1
1
− 13
1 2
1 1
1 2
4 −4
1
− 16
1 −5 −6 1
1
29
1 −5 1 1
− 16
1 −5 −6 1
1
− 20
−4 4
1 1
1
8
−4 4 1 1
− 17
6 −1
25
α
−1 b
x = Aα 48/5
−27/5
57/2
27/2 3/2
27/8
93/17
−27/17
33/4
27/4 −57/7
−48/7
1
4
93/13
−48/13
33
48 −3/4
57/16
−93/29
−57/29 −11/2
57/6 93/20
3/5 33/8
−3/2 −33/7
−53/7
x
48/5
−27/5 57/2
27/2 3/2
27/8
93/17
−27/17
33/4
27/4 −57/7
−48/7
1
4
93/13
−48/13
33
48 −3/4
57/16
−93/29
−57/29 −11/2
57/6 93/20
3/5 33/8
−3/2 −33/7
−53/7
fx
72
45/4
63/2
9
81
18
4. Il metodo del simplesso
m
Situazione 4.1. n, m ∈ N + 1 ed A ∈ Rm
n , f ∈ Rn , b ∈ R .
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 linearmente
indipendenti e quindi anche le colonne di A[x] lo sono. Per il teorema
3.13 si ha che x ∈ vertici(ARn+ = b).
Lemma 4.4. Siano x, y ∈ (ARn = b) ed α ∈ J(x, A). Allora
1−α
f y = f x + (f − fα A−1
α A)1−α y
1−α = 0.
Dimostrazione. L’ipotesi implica xα = A−1
α b ed x
α
1−α
Inoltre b = Ay = Aα y + A1−α y
, per cui
−1
1−α = xα − A−1 A
1−α
y α = A−1
1−α y
α b − Aα A1−α y
α
cosicché
1−α + f
1−α
f y = fα y α + f1−α y 1−α = fα xα − fα A−1
1−α y
α A1−α y
−1
1−α
= f x + (f − fα Aα A)1−α y
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 f y ≤ f x per ogni
y ∈ (ARn+ = 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) f x(t, j, α) = f x + 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, α)
j
= Aα (xα − tA−1
α Aj ) + Aj x (t, j, α)
= Aα xα − tAj + tAj = Aα xα = b
(2) Per il punto (1) possiamo applicare il lemma 4.4, ottenendo
1−α
f x(t, j, α) = f x + (f − fα A−1
(t, j, α)
α A)1−α x
−1
= f x + t(f − fα A−1
α A)j = f x + t(fj − fα Aα Aj )
(3) Chiaro.
Corollario 4.8. Nelle ipotesi dell’oss. 4.7 sia fj − fα A−1
α Aj > 0.
Allora f x(t, j, α) > f x per ogni t > 0.
Proposizione 4.9. Siano x ∈ (ARn+ = b), α ∈ J(x, A), j ∈ 1 − α ed
n
−1
fj − fα A−1
α Aj > 0. Se Aα Aj ≤ 0, allora il problema f (AR+ = b) = max
non possiede soluzioni.
Dimostrazione. Per l’oss. 4.7 lim f x(t, j, α) = ∞. Dobbiamo però vet−→∞
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, α)
j
α
−1
= xα − tA−1
α Aj + x (t, j, α) = x − tAα Aj + t ≥ 0
Nota 4.10. Siano x ∈ vertici(ARn+ = b), α ∈ J(x, A), j ∈ 1 − α e
m
w := A−1
α Aj ∈ R . Scriviamo α nella forma α = {α1 , . . . , αm }.
Assumiamo che fj −fα w > 0 e che esista almeno un indice i ∈ {1, . . . , m}
tale che wi > 0. Siano t := min{xαi /wi | i ∈ {1, . . . , m}, wi > 0}, ad esxαk
empio t = k , e β := (α ∪ {j}) \ {αk }. Allora:
w
(1) |β| = m.
(2) [x(t, j, α)] ⊂ β .
(3) β ∈ J(A).
(4) x(t, j, α) ∈ vertici(ARn+ = b).
(5) Se t > 0, allora f x(t, j, α) > f x.
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 linearmente
indipendenti. Possiamo assumere che α = {1, . . . , m}, k = m e
j > m. In particolare allora wm > 0.
Siano λ1 , . . . , λm−1 , λj ∈ R tali che λ1 A1 + . . . + λm−1 Am−1 + λj Aj = 0.
Però Aj = Aα w, per cui abbiamo
27
0 = λ1 A1 + . . . + λm−1 Am−1 + λj Aα w
= λ1 A1 + . . . + λm−1 Am−1 + λj (A1 w1 + . . . + Am wm )
= (λ1 + λj w1 )A1 + . . . + (λm−1 + λj wm−1 )Am−1 + λj wm Am
Siccome le colonne di α sono linearmente indipendenti, segue che
λ1 + λj w1 = . . . = λm−1 + λj wm−1 = λj wm = 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
A
.
j
α
Se w ≤ 0, allora il problema f (ARn+ = b) = max non possiede
soluzioni.
Altrimenti, posto t := min{xαi /wi | i ∈ {1, . . . , m}, wi > 0}, si ha
f x(t, j, α) > f x.
Dimostrazione. (1) Cor. 4.5.
(2) Il caso w ≤ 0 segue dalla prop. 4.9. Se non vale w ≤ 0, per la nota
4.10 è sufficiente dimostrare che t > 0. Ma per ipotesi α = [x], per cui
xαi > 0 per ogni i ∈ {1, . . . , m}, cosicché anche t > 0.
Nota 4.14. L’algoritmo del simplesso per la risoluzione del problema
di massimo f (ARn+ = b) = max può cosı̀ essere formulato nel modo
seguente (x è un vertice non degenere di (ARn+ = b)):
(1) α = [x] (necessariamente |α| = m). Scriviamo α = {α1 , . . . , αm }
con α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 restituisce
x e termina.
i
(6) w = A−1
α Aj ; t = ∞. Cerchiamo l’insieme I := {i ∈ α | w > 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 problema
non possiede soluzione e viene restituito il valore ∞ (o un altro
valore 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 infiniti; 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 prevede la funzione glpk; cfr. Eaton/Bateman/Hauberg, pagg. 339-345.
29
Osservazione 4.17. Quando il problema è dato nella forma standard,
f x = max
x≥0
Ax ≤ b
con la tecnica della nota 3.3 la possiamo trasformare in forma normale
x
(f 0)
= max
p
x
≥0
p
x
(A δ)
=b
p
0
è un vertice non degenere del nuovo
In questo caso il vettore
b
problema e possiamo applicare l’algoritmo della nota 4.14.
Osservazione 4.18. Consideriamo adesso un problema della forma
f x = max
x≥0
Ax = b
con A, f, b definiti come in precedenza. Esso evidentemente è equivalente al problema
f x − ∞u1 − . . . − ∞um = max
x ≥ 0, u ≥ 0
Ax + u = b
dove con ∞ calcoliamo in modo naturale. ∞ in Matlab (o Octave) viene
rappresentato da Inf e i calcoli vengono eseguiti correttamente.
Ciò ci permette di applicare di nuovo l’algoritmo del simplesso. Una
dimostrazione 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 discussione delle proprietà geometriche elementari degli insiemi convessi
iniziata nel primo capitolo.
Definizione 5.2. Usiamo le notazioni introdotte in precedenza e poniamo inoltre:
Rn++ := {x ∈ Rn | x > 0}
R++
m := {f ∈ Rm | f > 0}
Rnstoc
:= {λ = (λ1 , . . . , λn ) ∈ Rn+ |
n
X
λh = 1}
h=1
La condizione x > 0 significa che xh > 0 per ogni h; la condizione f > 0
è definita similmente.
Rnstoc è l’insieme dei vettori stocastici in Rn .
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−a
t − x| < ρ
(3)
y−a
t
∈ (|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 ρ > 0
tale che (|Rm − x| < ρ) ⊂ X . Sia z := tx+ (1− t)y . Dobbiamo dimostrare
che z ∈ int X . Usando la convessità di X e il lemma 5.3 con a = (1 − t)y
si ha che
5.3
X ⊃ (1 − t)y + t(|Rm − x| < ρ) = (|Rm − ((1 − t)y + tx)| < tρ) =
(|Rm − z| < tρ)
Abbiamo quindi trovato un intorno aperto di z contenuto in X per cui
z ∈ int X .
(2) Siano u, v ∈ X e t ∈ [0, 1]. Allora esistono due successioni x̃, ỹ in
X 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̃ appartengono
tutti 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 tali
che 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 V
tale che λX ⊂ X per ogni λ > 0.
m
m
Esempio 5.8. Gli insiemi Rm
+ e R++ sono coni convessi di R .
L’insieme (R+ × 0) ∪ (0 × R+ ) in R2 (l’unione dei due semiassi delle
coordinate) 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+y
2 ∈ X perché X è convesso, e quindi
x+y
∈ X perché X è un cono.
x+y =2
2
(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 sottoinsiemi 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 sottoinsiemi non vuoti X1 , . . . , Xn ⊂ V poniamo
32
n
X
[X1 , . . . , Xn ] := {
λk xk | n ∈ N + 1, x1 ∈ X1 , . . . , xn ∈ Xn , λ ∈ Rnstoc }
k=1
Si noti che [X1 ] = X1 .
Definizione 5.12. Per X ⊂ V sia conv X l’intersezione di tutti i sottoinsiemi convessi di V che contengono X .
Per l’oss. 5.10 questo insieme, la chiusura convessa di X , è il più
piccolo 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
X
λk xk | n ∈ N + 1, x1 , . . . , xn ∈ X, λ ∈ Rnstoc } =
∞
[
n=1
k=1
[X, . . . , X]
| {z }
n
Dimostrazione. È immediato che l’insieme alla destra è convesso e
contenuto 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 esistono
x1 , y1 ∈ X1 , . . . , xn , yn ∈ Xn e λ, µ ∈ Rnstoc tali che u = λ1 x1 + . . . + λn xn
e v = µ1 y1 + . . . µn yn . Ponendo s := 1 − t abbiamo
n
n
X
X
ρk zk
(sλk xk + tµk yk ) =
su + tv =
k=1
k=1
ρk
dove per ogni k abbiamo posto
:= sλk + tµk e
( k
tµk
sλ
per ρk 6= 0
k xk + ρk yk
ρ
zk :=
xk
altrimenti
Dalla convessità di Xk segue che zk ∈ Xk per ogni k. Inoltre
n
n
n
n
X
X
X
X
ρk =
(sλk + tµk ) = s
λk + t
µk = s + t = 1
k=1
k=1
k=1
k=1
Ciò mostra che su + tv ∈ [X1 , . . . , Xn ].
Corollario 5.16. Siano x1 , . . . , xn ∈ V . Allora
conv(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
33
conv(x1 , . . . , xn )
Corollario 5.18. X1 , . . . , Xn siano sottoinsiemi convessi e non vuoti di V . Allora
[
conv(x1 , . . . , xn )
conv(X1 ∪ . . . ∪ Xn ) =
(x1 ,...,xn )∈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 che
X ⊂ 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
5.4
conv X = conv int X ⊂ conv int conv X = 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, i] = (R × [0, 1]) ∪ {i}. Ma questo insieme non è chiuso.
a∈R
Definizione 5.22. Per X ⊂ Rm ed Y ⊂ Rk usiamo l’abbreviazione
x
| x ∈ X, y ∈ Y ⊂ Rm+k
X2Y :=
y
Per k = 1 ed Y = {1} abbiamo in particolare
⊂ Rm+1 .
X21
x
∈ Rm+1 .
Similmente per x ∈ Rm abbiamo x21 =
1
Lemma 5.23. Siano X ⊂ Rm e v ∈ Rm . 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 = λ1 x1 + . . . λn xn . Ciò implica
v21 = (λ1 x1 + . . . + λn xn )21
= λ1 (x1 21) + . . . + λn (xn 21) ∈ POS(x21)
(2) Sia viceversa v21 ∈ POS(X21). Allora esistono x1 , . . . , xn ∈ X
e λ1 , . . . , λn ≥ 0 tali che v21 = λ1 (x1 21) + . . . + λn (xn 21). Ma ciò è
equivalente alle relazioni v = λ1 x1 + . . . λn xn e λ1 + . . . + λn = 1.
34
Definizione 5.24. I punti x1 , . . . , xs ∈ V si dicono affinemente indipendenti, se una coppia di relazioni
λ1 x1 + . . . + λs xs = 0
λ1 + . . . + λs = 0
con λ1 , . . . , λs ∈ R implica λ1 = . . . = λs = 0.
Definizione 5.25. X sia un sottoinsieme non vuoto di V . La dimensione dim X di X è definita come la dimensione dello spazio affine aff X
generato da X .
È chiaro che dim X è uguale alla dimensione usuale di X , se X è un
sottospazio affine di X .
Si dimostra facilmente che dim X coincide con il massimo d ∈ N tale
che esistono d + 1 punti affinemente indipendenti in X .
Osservazione 5.26. Siano x1 , . . . , xs ∈ Rm e λ1 , . . . , λs ∈ R.
Allora sono equivalenti:
(1) λ1 x1 + . . . + λs xs = 0
e
λ1 + . . . + λs = 0.
(2) λ1 (x1 21) + . . . + λs (xs 21) = 0.
Corollario 5.27. X sia un sottoinsieme non vuoto di Rm . Allora
dim X = dim SV(X21) − 1
Corollario 5.28. Siano x1 , . . . , xs ∈ Rm . Allora sono equivalenti:
(1) I punti x1 , . . . , xs sono affinemente indipendenti.
(2) x1 21, . . . , xs 21 sono linearmente indipendenti.
Teorema 5.29 (teorema di Carathéodory). X sia un sottoinsieme
non vuoto di Rm con dim X = d. Allora conv X = [X, . . . , X].
| {z }
d+1
Dimostrazione. Sia v ∈ conv X . Per il lemma 5.23 v21 ∈ POS(X21).
Per il lemma di Carathéodory (prop. 1.10) e il cor. 5.27 esistono
x1 , . . . , xd+1 ∈ X e λ1 , . . . , λd+1 ∈ R+ tali che
v21 = λ1 (x1 21) + . . . + λd+1 (xd+1 21)
Ciò significa che v = λ1 x1 + . . . λd+1 xd+1 e λ1 + . . . + λd+1 = 1 e vediamo
che 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 −→ Rm
(x1 , . . . , xn , λ) −→ λ1 x1 + . . . λn xn
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̀ compatto.
Proposizione 5.33. Siano x1 , . . . , xn ∈ Rm ed y ∈ Rm . Per un punto
p ∈ 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
X
λk xk con λ ∈ Rnstoc . Per la prop. 1.19 è
k=1
sufficiente dimostrare che la condizione (2) implica k z − p, y − p k≤ 0.
n
n
n
X
X
X
k
k
λk = 1.
λ (xk − p) perchè
λ xk − p =
Osserviamo che z − p =
k=1
k=1
k=1
Perciò
k z − p, y − p k=
n
X
(2)
λk k xk − p, y − p k ≤ 0
k=1
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 f x > α > 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 f xk > α > 0 per ogni
k = 1, . . . , n.
Osservazione 5.36. Siano x1 , . . . , xn ∈ Rm ed α ∈ R tali che f xk > α
risp. f xk ≥ α per ogni k = 1, . . . , n.
Allora f z > α risp. f z ≥ α per ogni z ∈ conv(x1 , . . . , xn ).
Dimostrazione. Supponiamo che f xk > α per ogni k = 1, . . . , n.
n
X
λk xk con λ ∈ Rnstoc . Allora
Sia z =
k=1
fz =
n
X
k=1
k
λ f xk > α
n
X
λk = α
k=1
Qui abbiamo usato che
n
X
λk = 1 e che i coefficienti λk , i quali sono
k=1
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
k
Situazione 6.1. Siano X ∈ Rm
n , Y ∈ Rn .
e := {X 1 , . . . , X m } ed
Osservazione 6.2. Consideriamo i sottoinsiemi X
Ye := {Y 1 , . . . , Y k } di Rn . Seguendo il lavoro di Bennett/Mangasarian,
faremo vedere come il compito di separare in modo approssimato (ma
e ed Ye tramite un iperpiano possa essere riconottimale) i punti di X
dotto ad un compito di programmazione lineare.
 
1
 .. 
(l)
Definizione 6.3. Per l ∈ N + 1 siano 1 :=  .  ∈ Rl ,
1
1(l) := (1, . . . , 1) ∈ Rl .
Definizione 6.4. Per α ∈ R sia α+ := max(α, 0).
 1 
 1 
v
v+
n
X
 .. 
 .. 
n
Per v =  .  ∈ R siano v+ :=  .  e kvk1 :=
|v i |.
n
i=1
vn
v+
Si osservi che per v ≥ 0 si ha kvk1 = 1(n) v .
e e Ye si dicono linearmente separabili,
Definizione 6.5. Gli insiemi X
n
se esiste v ∈ R tale che
min X i v > max Y j v
1≤i≤m
1≤j≤k
Lemma 6.6. Sono equivalenti:
e e Ye sono linearmente separabili.
(1) X
(2) Esistono w ∈ Rn ed α ∈ R tali che
Xw ≥ (α + 1)1(m)
Y w ≤ (α − 1)1(k)
Dimostrazione. (1) =⇒ (2): Ponendo MIN := min X i v ,
MAX := max Y j v , α :=
1≤j≤k
MIN + MAX
MIN − MAX
e w :=
1≤i≤m
2v
MIN − MAX , abbiamo
X iw ≥
2 MIN
MIN − MAX
=
MIN − MAX + MIN + MAX
MIN − MAX
Y jw ≤
2 MAX
MIN − MAX
=
MIN + MAX −(MIN − MAX)
MIN − MAX
(2) =⇒ (1): Chiaro.
37
=1+α
=α−1
per ogni i
per ogni j
e
Lemma 6.7. Sono equivalenti:
e e Ye sono linearmente separabili.
(1) X
1
(2) min{ m
k(−Xw + (α + 1)1(m) )+ k1 + k1 k(Y w − (α − 1)1(k) )+ k1
| w ∈ Rn , α ∈ R} = 0.
Dimostrazione. È chiaro che (2) è equivalente alla condizione che
esistono w ∈ Rn ed α ∈ R tali che −Xw + (α + 1)1(n) ≤ 0 e
Y w −(α−1)1(k) ≤ 0 e quindi, per il lemma 6.6, alla lineare separabilità
e e Ye .
di X
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 quindi
f (α) = 0 + 1 + |α| ≥ 2.
(2) Sia −1 ≤ α ≤ 1. Allora (1 + α)+ = 1 + α, (1 − α)+ = 1 − α e quindi
f (α) = 1 + α + 1 − α = 2.
(3) Sia α ≥ 1. Allora (1 + α)+ = 1 + α, (1 − α)+ = 0 e quindi
f (α) = 1 + α + 0 ≥ 2.
e e Ye siano linearmente separabili.
Osservazione 6.9. X
Allora nel punto (2) del lemma 6.7 w 6= 0.
Dimostrazione. Altrimenti avremmo la contraddizione
1
k ((α + 1)+ 1(m) )+ k1 + k1 k ((1 − α)1(k) )+ k1
0 = min{ m
| α ∈ R}
6.9
= min{(1 + α)+ + (1 − α)+ | α ∈ R} = 2
Lemma 6.10. Siano g : Rn −→ Rm , h : Rn −→ Rk ed E ⊂ Rn .
Sia x0 ∈ E . Allora sono equivalenti:
(1) kg(x0 )+ k1 + kh(x0 )+ k1 = min{kg(x)+ k1 + kh(x)+ k1 | x ∈ E}.
k
(2) Esistono y0 ∈ Rm
+ e z0 ∈ R+ tali che y0 ≥ g(x0 ), z0 ≥ h(x0 ) e
1(m) y0 + 1(k) z0 =
min{1(m) y + 1(k) z | y ∈ Rn+ , z ∈ Rm
+ , x ∈ E, y ≥ g(x), z ≥ h(x)}.
Dimostrazione. Nelle soluzioni in (2) necessariamente y = g(x)+ e
z = h(x)+ . Per y ≥ 0 però 1(m) y =k y k1 e similmente per z ≥ 0.
Proposizione 6.11. Il compito di minimizzazione
1
k(−Xw + (α + 1)1(m) )+ k1 + k1 k(Y w − (α − 1)1(k) )+ k1
min{ m
| w ∈ Rn , α ∈ R}
è equivalente al compito di ottimizzazione lineare
38
1
n
k
min{ m
1(m) y + k1 1(k) z | y ∈ Rm
+ , z ∈ R+ , w ∈ R ,
Xw − α1(m) + y ≥ 1(m) , −Y w + α1(k) + z ≥ 1(k) }.
Dimostrazione. La dimostrazione discende dal lemma 6.10 con
g(x) = −Xw + (α + 1)1(m) e h(x) = Y w − (α − 1)1(k) .
Nota 6.12. Nei lavori di Bennett/Mangasarian e Mangasarian/Street/Wolberg
questi risultati vengono applicati a compiti di diagnosi e prognosi per
il carcinoma mammario.
39
7. Grafi
Definizione 7.1. Un grafo diretto è una coppia (P, S) in cui P è un
insieme finito ed S ⊂ P × P una relazione binaria su P .
Gli elementi di P si dicono posizioni (o vertici) del grafo diretto, gli
elementi di S archi (o spigoli).
Per un arco s = (a, b) ∈ S la posizione a si chiama l’inizio (o la
provenienza) 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 le
posizioni come punti nel piano e unendo per ogni arco (a, b) le posizioni
a e b con una freccia diretta da a verso b.
Esempio 7.3.
b
a
c
e
d
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 posizioni di un grafo diretto (P, S) con |P | = n, gli possiamo associare
una matrice di adiacenza A ∈ {0, 1}nn ponendo
(
1
se (ai , aj ) ∈ S
Aij =
0
se (ai , aj ) ∈
/S
Viceversa ogni matrice A ∈ {0, 1}nn determina, a meno di isomorfia, un
grafo diretto che risulta senza cappi se e solo se la matrice contiene
solo zeri nella diagonale principale.
Esempio 7.6. Per il grafo dell’esempio 7.3 con le posizioni elencate
nell’ordine a, b, c, d, e, la matrice di adiacenza diventa
40






0
1
0
0
0
1
0
0
0
0
1
1
0
1
0
0
0
1
0
0
1
0
1
1
0






Viceversa la matrice


0 1 0 1
 1 0 1 0 


 0 0 0 1 
0 0 0 0
corrisponde ad un grafo diretto della forma
Definizione 7.7. Una posizione a in un grafo diretto (P, S) si dice
isolata, 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 possiede 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 implica
P = A ∪ B . Inoltre è chiaro che un grafo diretto bipartito non possiede
cappi.
Gli insiemi A e B non sono univocamente determinati, nemmeno
quando si trascura l’ordine in cui vengono presi, come mostra il grafo
diretto bipartito (P, S) dato da P := {1, 2, 3, 4}, S := {(1, 2), (3, 4)}, in
cui possiamo prendere ad esempio A = {1, 3}, B = {2, 4} oppure
A = {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 sottoinsiemi
A, B ⊂ P tali che:
(1) A ∩ B = ∅.
(2) S ⊂ (A × B).
È chiaro che (P, S) è allora anche bipartito, per cui non possiede cappi
e P = A ∪ B . In questo caso però gli insiemi A e B sono univocamente
determinati, 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 multigrafi diretti. Questi possono essere definiti come coppie (P, G) in cui
P è un insieme finito e G : P × P −→ N è un’applicazione. Anche in
questo caso gli elementi di P si chiamano posizioni o vertici.
Nota 7.11. Un multigrafo diretto (P, G) viene spesso rappresentato
disegnando le posizioni nel piano e unendo, per (a, b) ∈ P × P , le posizioni a e b con tante frecce (dirette da a verso b) quante sono indicate
dalla molteplicità G(a, b).
Fissando una numerazione a1 , . . . , an dell’insieme delle posizioni di
un multigrafo diretto (P, G) con |P | = n, gli possiamo associare una
matrice di adiacenza A ∈ Nnn ponendo Aij = 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 3
 0 0 1 0 0 


 1 1 0 1 1 


 0 0 0 0 0 
0 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 un
multigrafo diretto (P, G) se poniamo
(
1
se (a, b) ∈ S
G(a, b) :=
0
altrimenti
Viceversa ogni multigrafo diretto (P, G) con G ≤ 1 è essenzialmente la
stessa 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
X
f (A, B) :=
f (s)
s∈S(A,B)
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 diretto
è 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
X
∂f (a) = f (P \ A, A) − f (A, P \ A)
a∈A
Dimostrazione. Usando l’oss. 8.7 abbiamo
X
X
∂f (a) =
(f (P, a) − f (a, P )) = f (P, A) − f (A, P )
a∈A
a∈A
= 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
X
∂f (a) = 0.
a∈P
Dimostrazione. Per il lemma 8.8 abbiamo
X
∂f (a) = f (∅, P ) − f (P, ∅) = 0
a∈P
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̀ disponibile, 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 0 è ammissibile.
s
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 abbiamo
X
X
0=
∂f (a) =
∂f (a) + ∂f (α) + ∂f (ω) = ∂f (α) + ∂f (ω)
a∈P
a∈P \{α,ω}
Definizione 8.13. f sia un flusso in R. Allora val(f ) := ∂f (ω) si chiama 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 ω sono
scelte in modo tale che S(P, α) = ∅ e S(w, P ) = ∅.
In questo caso val(f ) = ingresso(ω, f ) e, se f è ammissibile, si ha
anche val(f ) = uscita(α, f ).
45
Definizione 8.15. Un flusso massimale in R è un flusso ammissibile
di valore massimale.
Definizione 8.16. Un taglio (o una sezione, in inglese cut) di R è un
sottoinsieme X ⊂ P tale che α ∈ X , ω ∈
/ X.
X
cap(X) := c(X, P \ X) =
c(s)
s∈S(X,P \X)
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)
/ P \ X si ha ∂f (a) = 0 per ogni elemento
Dimostrazione. Siccome α ∈
a ∈ P \ X diverso da ω . Perciò
X
8.8
val(f ) = ∂f (ω) =
∂f (a) = f (X, P \ X) − f (P \ X, X)
a∈P \X
8.17
≤ f (X, P \ X) ≤ 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 R
tale 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
(
c(s)
per s ∈ S(X, P \ X)
f (s) =
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
8.18
val(f ) = 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 con
valore 6. Per ogni arco s abbiamo indicato f (s) e c(s) nella forma
f (s) : c(s).
D
5:6
ω
4:5
F
1:3
1:3
1:2
E
C
1:3
2:7
1:3
2:6
α
5:7
3:5
B
A
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 esistere
un 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 allora
c(ai−1 , ai ) − f (ai−1 , ai ) ≥ 0 per ogni i = 1, . . . , n.
Sia ∆ := ∆(γ, f ) := min {c(ai−1 , ai ) − f (ai−1 , ai )}.
1≤i≤n
Se allora definiamo un flusso g : S −→ R+ ponendo
(
f (s) + ∆
se s = (ai−1 , ai ) per un i ∈ {1, . . . , n}
g(s) :=
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) e
g(b, P ) = f (b, P ), per cui ∂g(b) = ∂f (b) = 0.
Sia b ∈ {a0 , . . . , an }. Siccome b 6= α, ω , deve esistere un
i ∈ {1, . . . , n − 1} tale che b = ai . Siccome i punti che appaiono in γ sono
tutti 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’interno
di γ . Ciò implica val(g) = ∂g(ω) = ∂f (ω) + ∆ = val(f ) + ∆.
Esempio 8.26. Nella rete dell’esempio 8.22 possiamo prima considerare il cammino (α, A, B, C, ω) in cui ∆ = 2, ottenendo il flusso
D
5:6
ω
4:5
F
3:3
1:3
1:2
E
C
1:3
1:3
2:7
4:6
7:7
α
5:5
B
A
di valore 8, e successivamente il cammino (α, F, E, D, ω) in cui
∆ = 1, ottenendo cosı̀ un flusso di valore 9 il quale, come abbiamo visto
nell’esempio 8.22, è già un flusso massimale:
D
6:6
ω
5:5
F
3:3
1:3
2:2
E
C
2:3
2:7
1:3
4:6
7:7
α
5:5
B
A
Nota 8.27. Può accadere però che la tecnica dell’oss. 8.25 non sia applicabile, cioè può accadere che ∆(γ, f ) = 0 per ogni γ ∈ C(α, ω), pur
non essendo f massimale. Consideriamo ad esempio il flusso f descritto dalla figura
A
B
4:7
3:4
5:5
ω
1:3
1:5
α
6:6
4:7
C
Calcoliamo ∆(γ, f ) per ogni γ ∈ C(α, ω):
48
γ
(α, A, B, w)
(α, A, B, C, w)
(α, A, C, w)
(α, C, w)
∆(γ, f )
0
0
0
0
Quindi non possiamo aumentare il valore del flusso con il metodo
dell’oss. 8.25. Se però diminuiamo di 1 il carico sull’arco (B, C), possiamo aumentare di 1 il carico sugli archi (B, ω) e (α, C), ottenendo il
flusso ammissibile
A
B
4:7
4:4
5:5
ω
1:3
0:5
α
6:6
5:7
C
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 γ è
f -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 -aumentanti
da 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 ha
f (α, C) < c(α, C) perché 4 < 7; per ε2 = −1 si ha f (B, C) = 1 > 0 ed
infine 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 semicammino
in R. Poniamo allora
49
Sγ+ := {(ai−1 , ai ) | i = 1, . . . , n
ed εi = 1}
Sγ−
ed εi = −1}
:= {(ai , ai−1 ) | i = 1, . . . , n
Sγ := Sγ+ ∪ Sγ−
È chiaro che Sγ+ ∩ Sγ− = ∅.
Infatti sia (ai−1 , ai ) = (aj , aj−1 ), ovvero ai−1 = aj e ai = aj−1 . Siccome
i punti a0 , . . . , an sono distinti, ciò implica i − 1 = j e i = j − 1, e ciò è
impossibile.
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 ) := min ∆(γ, f, s)
s∈Sγ
Esempio 8.33. Nella prima figura della nota 8.27 consideriamo ancora 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


per s ∈ Sγ+
f (s) + ∆
(*)
g(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 esistere
un 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 seguenti
per le quali abbiamo calcolato i cambiamenti:
50
(ai−1 , −1, b, −1, ai+1 ) . . .
(ai−1 , −1, b, 1, ai+1 )
(ai−1 , 1, b, −1, ai+1 )
(ai−1 , 1, b, 1, ai+1 )
ingresso(b, g) = ingresso(b, f ) − ∆
...
uscita(b, g) = uscita(b, f ) − ∆
...
ingresso(b, g) = ingresso(b, f )
...
uscita(b, g) = uscita(b, f ) − ∆ + ∆
...
ingresso(b, g) = ingresso(b, f ) + ∆ − ∆
...
uscita(b, g) = uscita(b, f )
...
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
εn = −1
...
ingresso(ω, g) = ingresso(ω, f ) + ∆
...
uscita(ω, g) = uscita(ω, f )
...
ingresso(ω, g) = ingresso(ω, f )
...
uscita(ω, g) = uscita(ω, f ) − ∆
perché ω non può apparire all’interno di γ . Ciò implica
val(g) = ∂g(ω) = ∂f (ω) + ∆ = val(f ) + ∆.
Corollario 8.36. f sia un flusso ammissibile in R. Se esiste un semicammino f -aumentante da α ad ω , allora f non è un flusso massimale.
Osservazione 8.37. f sia un flusso ammissibile in R tale che
Sf (α, ω) = ∅. Siano
Γ := {γ ∈ Sf (α, a) | a ∈ P }
[
X := {α} ∪
vertici(γ)
γ∈Γ
L’ipotesi implica che ω ∈
/ X , perciò [
X è un taglio di R.
vertici(γ).
Se Γ 6= ∅, si ha naturalmente X =
γ∈Γ
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 capacità 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̀ minimale
tale 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 per
ogni s ∈ S .
Dimostrazione. (1) Chiaro, perché P è un insieme finito.
(2) Iniziando con il flusso nullo f0 := 0, per ogni i = 0, 1, . . . proces
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 . Siccome
val(fi+1 ) ≤ c(P \ ω, ω) per il cor. 8.19, l’algoritmo deve terminare.
Nota 8.41. Seguendo Aigner, pagg. 305-307, facciamo vedere adesso
come il problema dei flussi massimali possa essere risolto nell’ambito
della programmazione lineare.
Definiamo una matrice M ∈ RPS ponendo, per p ∈ P ed s ∈ S ,


se p = s2
1
Msp := −1
se p = s1


0
altrimenti
Senza perdere di generalità possiamo
Xassumere che (ω, α) ∈ S e che
c(ω, α) = ∞ (oppure che c(ω, α) >
c(s)).
s∈S\{ω,α}
Numerando P ∈ S , possiamo identificare P con {1, . . . , m} ed S con
{1, . . . , n}. Allora M ∈ Rm
n.
Per la rete della nota 8.27, aggiungendo l’arco (ω, α), M è data dalla
tabella
52
α
A
B
C
ω
αA
-1
1
0
0
0
αC
-1
0
0
1
0
AB
0
-1
1
0
0
AC
0
-1
0
1
0
BC
0
0
-1
1
0
Bω
0
0
-1
0
1
Cω
0
0
0
-1
1
ωα
1
0
0
0
-1
La capacità c può essere identificata con un vettore c ∈ Rn+ , e similmente un flusso ammissibile f con un vettore x ∈ Rn+ tale che x ≤ c
con M x = 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 problema
di 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 dimostrare
l’esistenza di un flusso massimale anche senza la condizione che
c(s) ∈ N per ogni s ∈ S (cfr. prop. 8.40). Infatti con


 
M
0
A :=  −M , b :=  0 , f := (0 . . . 01)
δ
c
il problema (*) può essere scritto nella forma
f x = max
x≥0
Ax ≤ b
Siccome c ≥ 0 e quindi anche b ≥ 0, abbiamo X := (ARn+ ≤ b) 6= ∅
perché 0 ∈ X e Y := (R+
m A ≥ 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 Rn tale
che X ⊂ Ω ed f : Ω −→ R una funzione di classe C 1 .
In questa parte della tesi seguiamo soprattutto Geiger/Kanzow,
pagg. 41-76.
Nota 9.2. Usiamo le seguenti abbreviazioni:
(1) [R++ ↓ 0] := { tk ∈ RN | t0 > t1 > t2 > . . . > 0
e lim tk = 0}
k−→∞
k
(2) Per y ∈ Rn sia
[X −→ y] := { xk ∈ X N | lim xk = y}
k−→∞
k
Ponendo X = Rn e X = R++ abbiamo in particolare definito gli
insiemi [Rn −→ y] e [R++ −→ 0].
Osservazione 9.3. Sia tk ∈ [R++ −→ 0]. Ponendo n0 := 0 troviamo
k
un indice n1 > n0 tale che tn1 < tn0 , poi un indice n2 > n1 tale che
tn2 < tn1 ecc. In questo modo otteniamo una successione
tnj ∈ [R++ ↓ 0].
j
Definizione 9.4. Sia x ∈ X . Un vettore v ∈ Rn si dice tangente ad X
in x, se esistono due successioni xk ∈ [X −→ x] e tk ∈ [R++ −→ 0]
k
k
xk − x
xk − x
∈ [Rn −→ v], cioè tali che lim
= v.
tali che k−→∞
t
tk
k
k
L’insieme T(X, x) di tutti i vettori tangenti ad X in x si chiama il
cono 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 xk ∈ [X −→ x]
e tk ∈ [R
k
++
k
xk − x
∈ [Rn −→ v].
↓ 0] tali che tk
k
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 xk ∈ [X −→ x] e tk ∈ [R++ −→ 0]
k
k
xk − x
= v , allora evidentemente
sono tali che lim
k−→∞
tk
xk − x
tk /λ ∈ [R++ −→ 0] e lim
= λv , per cui λv ∈ T(X, x).
k−→∞ tk /λ
k
Osservazione 9.7. x sia un punto interno di X (rispetto alla topologia
di Rn ). 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 tale
1
1
che xk = x + m+k
v ∈ X per ogni k ∈ N. Poniamo tk := m+k
.
++
xk −x
Allora tk ∈ [R
−→ 0], xk ∈ [X −→ x], mentre tk = v per ogni
k
k
k ∈ N, per cui sicuramente k
xk − x
∈ [Rn −→ v].
tk
Lemma 9.8. Sia x ∈ X . Allora T(X, x) è un sottoinsieme chiuso di Rn .
Dimostrazione. Siano v ∈ T(X, x) e vj ∈ [T(X, x) −→ v].
j
(j)
Allora per ogni j ∈ N esistono due successioni xk
∈ [X −→ x] e
k
(j)
xk − x
(j)
tk ∈ [R++ ↓ 0] tali che lim
k−→∞
k
(j)
tk
= vj .
Ciò implica che possiamo trovare una successione mj ∈ NN tale
(j)
|xmj
1
j,
(j)
tmj
− x| ≤ 0 <
che per ogni j ∈ N + 1 si abbia
x(j) − x
mj
(j) − vj ≤ 1j . L’ultima disuguaglianza implica
tm
j
x(j) − x
x(j) − x
mj
mj
(j) − v ≤ (j) − vj + |vj − v|
tm
tm
j
e
j
e vediamo che
(j)
xmj −
lim
(j)
j−→∞
tmj
j
≤ 1j
x
x(j)
mj
j
++
−→ 0] e
∈ [X −→ x], t(j)
mj ∈ [R
j
= v , cosicché v ∈ T(X, x).
Definizione 9.9. x ∈ X è un punto di minimo locale di f in X , se
esiste 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 + tv) − f (x)
f ′ (x; v) := lim
t−→0
t
la derivata in direzione v di f in x.
È noto dall’analisi che f ′ (x; v) =k ∇f (x), v k.
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
xk − x
∈ [Rn −→ v].
xk ∈ [X −→ x] e tk ∈ [R++ −→ 0] tali che t
k
k
k
k
Per il teorema del valor medio esiste una successione ξk tale che
k
ξk ∈ [x, xk ] e f (xk ) − f (x) =k ∇f (ξk ), xk − x k per ogni k.
L’ipotesi che x sia un punto di minimo locale di f in X implica che
f (xk ) − f (x) ≥ 0 per k >> 0 e quindi anche k ∇f (ξk ), xkt−x
k≥ 0 per
k
k >> 0. Inoltre ξk −→ x perché ξk ∈ [x, xk ] per ogni k. Ciò implica
k
f ′ (x; v) =k ∇f (x), v k= lim k ∇f (ξk ),
k−→∞
xk − x
k≥ 0
tk
Esempio 9.13. Consideriamo il caso n = 1, X = [0, 1] e Ω un intervallo
aperto che contiene [0, 1]. Il cono tangente di X coincide con [0, ∞), il
cono tangente in 1 con (−∞, 0].
Il lemma 9.12 afferma che se 0 è un punto di minimo locale di f in
X , allora f ′ (0) ≥ 0, e se 1 è un punto di minimo locale in X , allora
f ′ (1) ≤ 0.
Osservazione 9.14. Il cono tangente T(X, x) in generale è piuttosto
complicato, cosicché spesso non è possibile applicare direttamente il
lemma 9.12. Descriveremo adesso, in alcuni casi importanti, condizioni 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, come
conseguenza del lemma di Farkas, ci fornisce una condizione necessaria 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 |k ∇gi (x), v k≤ 0 per ogni
k ∇hj (x), v k= 0
i ∈ I(x),
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 anche
dalla 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 dimostrazione
del lemma 9.12.
Sia v ∈ T(X, x). Allora esistono successioni xk ∈ [X −→ x] e
k
tk ∈ [R
k
++
xk − x
∈ [Rn −→ v].
−→ 0] tali che tk
k
(1) Sia i ∈ I(x). Per il teorema del valor medio esiste una successione
ξk tale che ξk ∈ [x, xk ] e gi (xk ) = gi (x)+ k ∇gi (ξk ), xk − x k per ogni
k
k. Per ipotesi però gi (x) = 0 perché i ∈ I(x) e gi (xk ) ≤ 0 perché ogni
k≤ 0
xk ∈ X . Perciò k ∇gi (ξk ), xk −x k≤ 0 e quindi anche k ∇gi (ξk ), xkt−x
k
per ogni k. Passando al limite otteniamo k ∇gi (x), v k≤ 0.
(2) Nello stesso modo si dimostra che k ∇hj (x), v k= 0 per ogni
j = 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 affinché un punto sia regolare nel senso di Abadie. Non è comunque
sempre 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 al
di sotto della parabola cubica data dall’equazione x2 = (x1 )3 .
57
Sia x0 :=
0
0
. È chiaro che T(X, x) = R+ × 0.
2
2
1 3
Con g1 (x)
invece := −x
e g2 (x) := x − (x) troviamo
0
0
−3(x1 )2
, da cui ∇g1 (x0 ) =
∇g1 (x) =
, e ∇g2 (x) =
−1 −1
1
0
da cui ∇g2 (x0 ) =
.
1
Siccome g1 (x0 ) = g2 (x0 ) = 0, abbiamo I(x0 ) = {1, 2}, cosicché per
v ∈ R2 si ha v ∈ Tl(x0 ) ⇐⇒ −v 2 ≤ 0 e v 2 ≤ 0 ⇐⇒ v 2 = 0, per cui
Tl(x0 ) = R × 0.
T(X, x0 ) non coincide perciò con Tl(x0 ), cosicché x0 non è un punto
regolare nel senso di Abadie.
Definizione 10.7. Definiamo un’applicazione L : Rn × Rm × Rp −→ R
tramite
p
m
X
X
µj hj (x)
λi gi (x) +
L(x, λ, µ) := f (x) +
j=1
i=1
= f (x)+ k λ, g(x) k + k µ, h(x) k
L’applicazione L si chiama la funzione di Lagrange di (X, f ) (o più
precisamente della situazione descritta dalle funzioni f, g, h).
Definizione 10.8. Le condizioni di Karush-Kuhn-Tucker (KKT)
rispetto alla situazione 10.1 sono
∇x L(x, λ, µ) = 0
g(x) ≤ 0
h(x) = 0
λ≥0
k λ, g(x) k= 0
Il gradiente ∇x rispetto alla variabile x è definito da
p
m
X
X
µj ∇hj (x)
λi ∇gi (x) +
∇x L(x, λ, µ) := ∇f (x) +
j=1
i=1
I parametri λ1 , . . . , λm , µ1 , . . . , µp (oppure anche i vettori λ, µ) vengono
detti moltiplicatori di Lagrange.
Un punto (x, λ, µ), in cui le condizioni di KKT sono soddisfatte, si
chiama un punto di KKT di (X, f ) (o più precisamente della situazione
descritta 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 alla
condizione ∇f (x) = 0.
Osservazione 10.10. (x, λ, µ) sia un punto di KKT di (X, f ). Allora
λi gi (x) = 0 per ogni i = 1, . . . , m. Quindi per ogni i = 1, . . . , m almeno
uno 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) non
si annullano simultaneamente per nessun indice i), allora (x, λ, µ) si
dice 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 ogni
v ∈ 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̀ ammesso
il 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) ⇐⇒ v t A ≥ 0 ⇐⇒ v t ∈ (Rn A ≥ 0)
Siccome f ′ (x; v) = v t ∇f (x), abbiamo quindi (Rn A ≥ 0)∇f (x) ≥ 0.
k+2p
Per il lemma di Farkas (teorema 1.26) ciò implica ∇f (x) ∈ AR+
.
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
∇x L(x, λ, µ) := ∇f (x) +
m
X
λi ∇gi (x) +
p
X
j=1
i=1
con g(x) ≤ 0, h(x) = 0, λ ≥ 0, k λ, g(x) k= 0.
(x, λ, µ) è perciò un punto di KKT.
59
µj ∇hj (x) = 0
11. Il caso generale
Situazione 11.1. Come nel capitolo precedente siano date funzioni
f, g1 , . . . , gm , h1 , . . . , hp : Rn −→ 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 linearmente indipendenti e v ∈ Rn tale che k ∇hj (x), v k= 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’applicazione
Hj : Rp+1 −→ R tramite
Hj (y, t) := hj (x + tv + ∇h(x)y)
ottenendo cosı̀ una funzione H : Rp+1 −→ Rp con H(0, 0) = 0.
La jacobiana Hy′ (0, 0) è data da Hy′ (0, 0) = (∇h(x))t ∇h(x) ed è quindi invertibile essendo per ipotesi i vettori ∇h1 (x), . . . , ∇hp (x), cioè le
colonne della matrice ∇h(x), linearmente indipendenti.
Per il teorema delle funzioni implicite esistono ε > 0 ed una funzione
ϕ : (−ε, ε) −→ Rp di classe C1 (risp. di classe C2 se anche le funzioni
hj sono tutte di classe C2 ) tali che ϕ(0) = 0 e H(ϕ(t), t) = 0 per ogni
t ∈ (−ε, ε).
Inoltre ϕ̇(t) = −(Hy′ (ϕ(t), t))−1 Ht′ (ϕ(t), t), per cui
ϕ̇(0) = −(Hy′ (0, 0))−1 Ht′ (0, 0) = −(Hy′ (0, 0))−1 (∇h(x))t v = 0
H(ϕ(t), t)) = 0 significa però proprio hj (x+tv +∇h(x)ϕ(t)) = 0 per ogni
j = 1, . . . , p.
Corollario 11.3. Sia x ∈ X . I vettori ∇h1 (x), . . . , ∇hp (x) siano
linearmente indipendenti e v ∈ Rn tale che k ∇hj (x), v k= 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 linearmente indipendenti e v ∈ Rn tale che k ∇hj (x), v k= 0 per ogni
j = 1, . . . , p, come nel lemma 11.2, ma anche k ∇gi (x), v k< 0 per ogni
i ∈ 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 necessario, ε. Infatti per i ∈
/ I(x), dalla continuità di gi segue
gi (γ(t)) < 0 per ogni t sufficientemente piccolo. Possiamo quindi assumere 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) =k ∇gi (γ(t)), γ̇(t) k e quindi
α̇(0) =k ∇gi (γ(0)), γ̇(0) k=k ∇gi (x), v k< 0. Ciò implica α(t) < 0 per
ogni t > 0 sufficientemente piccolo. Restringendo ancora ε troviamo
che 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 MangasarianFromovitz, se sono soddisfatte le seguenti condizioni:
(1) I vettori ∇h1 (x), . . . , ∇hp (x) sono linearmente indipendenti.
(2) Esiste un vettore v ∈ Rn tale che k ∇hj (x), v k= 0 per ogni
j = 1, . . . , p e tale che k ∇gi (x), v k< 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 MangasarianFromovitz 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-Fromovitz
per x. Infatti, usando l’ipotesi che u ∈ Tl(x), abbiamo
61
k ∇hj (x), u + θv k=k ∇hj (x), u k +θ k ∇hj (x), v k= 0
per ogni j = 1, . . . , p e
k ∇gi (x), u + θv k=k ∇gi (x), u k +θ k ∇gi (x), v k< 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
γ(1/k) − γ(0)
γ(1/k) − x
u + θv = γ̇(0) = lim
= lim
k−→∞
k−→∞
1/k
1/k
e siccome lim γ(1/k) = γ(0) = x, vediamo che u + θv ∈ T(X, x).
k−→∞
Proposizione 11.7. Sia x ∈ X un punto regolare nel senso di MangasarianFromovitz. Allora x è un punto regolare nel senso di Abadie.
Dimostrazione. Per la prop. 10.4 dobbiamo dimostrare che
Tl(x) ⊂ T(X, x).
Siano u ∈ Tl(x) e v un vettore di Mangasarian-Fromovitz per x. Per
il lemma 11.6 u + θv ∈ T(X, x) per ogni θ > 0. Ma lim u + θv = u,
θ−→0
quindi vediamo che u ∈ T(X, x). Dal lemma 9.8 sappiamo però che
T(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 KKT
di (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. Allora x è regolare nel senso di Mangasarian-Fromovitz.
Dimostrazione. La condizione (1) della def. 11.5 è evidentemente
soddisfatta.
(2) Possiamo assumere che I(x) = {1, . . . , q} con 0 ≤ q ≤ m. Per ipotesi esistono vettori Aq+p+1 , . . . , An ∈ Rn tali che la matrice
A := (∇g1 (x), . . . , ∇gq (x), ∇h1 (x), . . . , ∇hp (x), Aq+p+1 , . . . , An ) sia invertibile. Sia b := (−1, . . . , −1, 0, . . . , 0, 1 . . . 1)t . Allora l’equazione At v = b
| {z } | {z }
q
p
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 dal
teorema 11.8.
(2) Dimostriamo l’unicità. Assumiamo di nuovo che I(x) = {1, . . . , k}
con 0 ≤ k ≤ m. Dall’oss. 10.10 sappiamo che λi = 0 per i > k. Inoltre
k
X
i=1
λi ∇gi (x) +
p
X
µj ∇hj (x) = −∇f (x)
j=1
Questa rappresentazione, e quindi i numeri λ1 , . . . , λk , µ1 , . . . , µp , sono
univocamente 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 | a1 x ≤ α1 , . . . , am x ≤ αm , b1 x = β1 , . . . , bp x = βp }
Ponendo gi := ai x − αi per i = 1, . . . , m ed hj := bj x − βj per
x
x
j = 1, . . . , p abbiamo X = (g1 ≤ 0, . . . , gm ≤ 0, h1 = 0, . . . , hp = 0) come
nei 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 dimostrare 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 ai v ≤ 0 per ogni i ∈ I(x) e bj v = 0 per ogni j = 1, . . . , p.
Per k ∈ N + 1 siano tk :=
grande abbiamo allora
1
k
ed xk := x + tk v . Per k sufficientemente
ai xk = ai (x + tk v) = αi + tk ai v ≤ αi per i ∈ I(x)
ai xk = ai (x + tk v) = ai x + tk ai v < αi per i ∈
/ I(x)
bj xk = bj (x + tk v) = βj + tk bj v = βj per j = 1, . . . , p
Ciò mostra che xk ∈ X per k >> 0. Inoltre da un lato xk −→ x,
xk − x
= v −→ v , per cui v ∈ T(X, x).
dall’altro tk
k
k
k
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
X
λi ai +
p
X
µj bj = 0
j=1
i=1
ai x ≤ αi
per i = 1, . . . , m
bj x
per
= βj
j = 1, . . . , p
λ≥0
λi (ai x − αi ) = 0
per
i = 1, . . . , m
Dimostrazione. Per la prop. 12.2 x è regolare nel senso di Abadie, per
cui possiamo applicare il teorema 10.11. Le condizioni nell’enunciato
sono 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] con
f (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 la
condizione 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 k ∇f (x), y − x k≤ 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, b1 x = β1 , . . . , bp x = βp }
e := {x ∈ Rn | g1 (x) < 0, . . . , gm (x) < 0, b1 x = β1 , . . . , bp x = βp }
X
e sono convessi.
È immediato che gli insiemi X e X
Osservazione 13.4. Sia (x, λ, µ) ∈ Rn × Rm × Rp . Allora sono equivalenti:
(1) (x, λ, µ) è un punto di KKT di (X, f ).
(2) ∇f (x) +
X
λi ∇gi (x) +
i∈I(x)
gi (x) ≤ 0 per ogni
bj x
= βj
p
X
µj (bj )t = 0
j=1
i = 1, . . . , m
per ogni j = 1, . . . , p
λ≥0
k λ, g(x) k= 0
/ I(x) per
Dimostrazione. È sufficiente osservare che λi = 0 per i ∈
l’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)+ k ∇f (x), y − x k
= f (x) −
X
λi k ∇gi (x), y − x k −
= f (x) −
µj bj (y − x)
j=1
i∈I(x)
X
p
X
λi k ∇gi (x), y − x k
i∈I(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 otteniamo
X
X
λi k ∇gi (x), y − x k≤
λi (gi (y) − gi (x))
i∈I(x)
i∈I(x)
=
X
λi gi (y) ≤ 0
i∈I(x)
e ciò mostra f (x) ≤ f (y).
Definizione 13.6. Per x ∈ X sia
Tls(x) := {v ∈ Rn |k ∇gi (x), v k< 0 per ogni
bj v = 0
per
i ∈ I(x),
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 :=
xk := x + tk v . Allora xk −→ x, tk ∈ [R++ −→ 0] e
k
1
k
e
k
xk − x
= v ∈ [Rn −→ v]. Pertanto è sufficiente dimostrare che
tk
k
k
xk ∈ X per k >> 0.
(1) In primo luogo per ogni j = 1, . . . , p ed ogni k ∈ N + 1 abbiamo
bj xk = bj (x + tk v) = bj x + tk bj v = β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 ) < 0
per k >> 0.
(3) Sia i ∈ I(x) e quindi gi (x) = 0. Per ipotesi
gi (x + tv) − gi (x)
gi (xk )
gi (x + tv)
0 >k ∇gi (x), v k= lim
= lim
= lim
t−→0
t−→0
k−→∞
t
t
tk
Ciò implica gi (xk ) < 0 per k >> 0.
e 6= ∅, allora
Lemma 13.8. Sia x ∈ X . Se X
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 k ∇gi (x), v k≤ 0 per ogni i ∈ I(x) e bj v = 0 per
ogni j = 1, . . . , p.
e 6= ∅, perciò possiamo trovare y ∈ Rn tale che gi (y) < 0
Per ipotesi X
per ogni i = 1, . . . , m e bj y = βj per ogni j = 1, . . . , p.
Dal lemma 13.2 abbiamo k ∇gi (x), y − x k≤ gi (y) − gi (x) = gi (y) < 0
per ogni i ∈ I(x), mentre bj (y − x) = bj y − bj x = βj − βj = 0 per ogni
j = 1, . . . , p. Se per k ∈ N + 1 poniamo tk := k1 e wk := v + tk (y − x),
abbiamo quindi
k ∇gi (x), wk k=k ∇gi (x), v k +tk k ∇gi (x), y − x k< 0
per ogni i ∈ I(x) e bj wk = bj v = 0, cosicché wk ∈ Tls(x) per ogni
k ∈ N + 1. Però lim wk = v e vediamo che v ∈ Tls(x).
k−→∞
e 6= ∅. Allora per x ∈ X sono equivalenti:
Teorema 13.9. Sia X
(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 forma
gi (x) = ai x − αi con ai ∈ Rn 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 ).
e = ∅, allora possiamo aggiungere le funDimostrazione. Se qui X
i
zioni a x − αi alle funzioni bj x − βj , trovandoci cosı̀ in un caso
x
x
in cui le ipotesi del teorema 13.9 (o del lemma 13.8) sono banalmente
soddisfatte.
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 discrimination 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 Optimierungsaufgaben. 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 and
prognosis via linear programming. Op. Res. 43/4 (1995), 570-578.
J. Matoušek/B. Gärtner: Understanding and using linear programming.
Springer 2007, 220p. Eur 41.
J. Nocedal/S. Wright: Numerical optimization. Springer 2006.
69