Zagadnienia

11.1 Ograniczenia równościowe
11.2 Ograniczenia nierównościowe
11.3 Zadania

11. Teoria wrażliwości

Dotychczas mnożniki Lagrange'a wydawały się techniczną sztuczką służącą do znajdowania rozwiązania problemu optymalizacyjnego z ograniczeniami. W tym rozdziale pokażemy, że pełnią one rolę kosztu związanego ze zmianą ograniczeń. Oddzielnie zajmiemy się ograniczeniami równościowymi i nierównościowymi.

11.1. Ograniczenia równościowe

Rozważmy problem optymalizacyjny z ograniczeniami równościowymi:

f⁢x→min,hj⁢x=0,⁢j=1,…,l,x∈X,

(11.1)

gdzie X∈Rn jest zbiorem otwartym i f,h1,…,hl:X→R. Dla uproszczenia notacji połóżmy h⁢x=h1⁢x,…,hl⁢xT. Rozważmy problem zaburzony, tzn.

f⁢x→min,h⁢x=z,x∈X,

(11.2)

gdzie z∈Rl.

Twierdzenie 11.1

Niech x¯ będzie rozwiązaniem lokalnym problemu (11.1), zaś λ¯ wektorem jego mnożników Lagrange'a. Załóżmy, że funkcje f,h1,…,hl są klasy C2 na otoczeniu x¯, gradienty ograniczeń są liniowo niezależne (spełniony jest warunek liniowej niezależności) oraz

dT⁢Dx2⁢L⁢x¯,λ¯⁢d>0

(11.3)

dla d∈Rn∖0 spełniających D⁢hj⁢x¯⁢d=0, j=1,…,l. Wówczas istnieje otoczenie O~ punktu 0∈Rl oraz funkcja x:O~→X klasy C1, taka że x⁢0=x¯ oraz x⁢z jest ścisłym rozwiązaniem lokalnym problemu zaburzonego (11.2). Ponadto,

D⁢f∘x⁢0=-λ¯T.

Dowód

Na mocy tw. 8.1 punkt x¯ rozwiązuje układ równań:

Dx⁢L⁢x¯,λ¯=0T,h⁢x¯=0,

gdzie

Dx⁢L⁢x¯,λ¯=D⁢f⁢x¯+λ¯T⁢D⁢h⁢x¯=D⁢f⁢x¯+∑j=1lλ¯j⁢D⁢hj⁢x¯.

Zaburzając prawą stronę drugiej równości przez z będziemy chcieli pokazać, że istnieje rozwiązanie, które jest funkcją z klasy C1. Rozważmy więc układ:

Dx⁢L⁢x,λ=0T,⁢h⁢x=z,

gdzie niewiadomymi są λ oraz x. Zdefiniujmy funkcję G:Rn×Rl×Rl→Rn×Rl wzorem

G⁢x,λ,z=Dx⁢L⁢x,λTh⁢x-z.

Zaburzony układ możemy wówczas zapisać jako

G⁢x,λ,z=0.

Wiemy, że G⁢x¯,λ¯,0=0. Skorzystamy z twierdzenia o funkcji uwikłanej, aby rozwikłać pierwsze dwie zmienne w zależności od trzeciej. W tym celu rozważamy macierz pochodnych D⁢G⁢x¯,λ¯,0:

D⁢G⁢x¯,λ¯,0=Dx2⁢L⁢x¯,λ¯,D⁢h⁢x¯T,0D⁢h⁢x¯,0,-I.

Warunek liniowej niezależności gradientów ograniczeń implikuje nieosobliwość podmacierzy

Dx2⁢L⁢x¯,λ¯,D⁢h⁢x¯TD⁢h⁢x¯,0.

Spełnione są zatem założenia twierdzenia 8.4 i istnieje otoczenie O punktu 0∈Rl oraz funkcje x:O→X i λ:O→Rl klasy C1, takie że dla z∈O zachodzi G⁢x⁢z,λ⁢z,z=0, czyli

Dx⁢L⁢x⁢z,λ⁢z=0T,⁢h⁢x⁢z=z.

Korzystając z faktu, iż funkcje Dx2⁢L,D⁢h,x,λ są ciągłe oraz nierówność (11.3) spełniona jest dla niezaburzonego problemu, wnioskujemy, że istnieje być może mniejsze otoczenie O~ punktu 0∈Rl, takie że

dT⁢Dx2⁢L⁢x⁢z,λ⁢z⁢d>0

dla z∈O~ i d∈Rn∖0 spełniających D⁢hj⁢x⁢z⁢d=0, j=1,…,l. Kluczowa dla tego wyniku jest ostra nierówność w warunku (11.3). Na mocy tw. 9.3 punkt x⁢z jest zatem ścisłym rozwiązaniem lokalnym problemu zaburzonego (11.2). Przypomnijmy, że funkcja x jest klasy C1. Możemy zatem zdefiniować pochodną złożenia

D⁢f∘x⁢0=D⁢f⁢x¯⁢D⁢x⁢0.

Od zakończenia dowodu dzielą nas dwa spostrzeżenia. Po pierwsze, mnożąc obie strony warunku koniecznego pierwszego rzędu dla problemu niezaburzonego

D⁢f⁢x¯+λ¯T⁢D⁢h⁢x¯=0T.

przez D⁢x⁢0 dostajemy

D⁢f⁢x¯⁢D⁢x⁢0+λ¯T⁢D⁢h⁢x¯⁢D⁢x⁢0=0T.

Po drugie, rózniczkując h⁢x⁢z=z po z otrzymujemy w punkcie z=0 następującą pochodną D⁢h∘x⁢0=I, czyli D⁢h⁢x¯⁢D⁢x⁢0=I. Upraszcza to powyższe równanie do

D⁢f⁢x¯⁢D⁢x⁢0+λ¯T=0T.

Stąd już teza wynika natychmiast.

∎

Twierdzenie 11.1 można rozumieć następująco: nieznaczna zmiana j-tego ograniczenia z zera do ε prowadzi do zmiany optymalnej wartości funkcji f o -λ¯j⁢ε+o⁢ε, tzn. dla małych ε zmiana ta jest w przybliżeniu równa -λ¯j⁢ε.

11.2. Ograniczenia nierównościowe

W przypadku ograniczeń nierównościowych zastosujemy inne podejście. Skoncentrujemy się na zadaniu optymalizacji wypukłej:

f⁢x→min,gi⁢x≤0,⁢i=1,…,m,x∈X,

(11.4)

gdzie X⊂Rn jest wypukły, f,g1,…,gm:X→R są wypukłe. Dla uproszczenia notacji będziemy pisać g⁢x=g1⁢x,…,gm⁢xT. Problem (11.4) zapisujemy więc jako

f⁢x→min,g⁢x≤0,⁢x∈X.

(11.5)

Rozważmy zadanie zaburzone: dla z∈Rm

f⁢x→min,g⁢x≤z,⁢x∈X,

(11.6)

Definicja 11.1

Niech DM będzie zbiorem takich z∈Rm, dla których zbiór punktów dopuszczalnych Wz=x∈X:⁢g⁢x≤z jest niepusty. Funkcją perturbacji nazywamy funkcję

M⁢z=infx∈X,⁢g⁢x≤z⁡f⁢x

określoną dla z należących do dziedziny DM.

Zauważmy, że M⁢z<∞ dla z∈DM, ale może się zdarzyć, że M⁢z=-∞.

Twierdzenie 11.2

Zbiór DM jest wypukły.
Funkcja M:DM→R∪-∞ jest wypukła.
Jeśli istnieje punkt x*∈X, taki że gi⁢x*<0, i=1,…,m, to intDM≠∅ i 0∈intDM.

Dowód

Z wypukłości g wynika następująca implikacja:

g⁢x1≤z1,⁢g⁢x2≤z2⁢⟹⁢∀⁢λ∈0,1⁢⁢g⁢λ⁢x1+1-λ⁢x2≤λ⁢z1+1-λ⁢z2.

(11.7)

Będziemy korzystać z tego spostrzeżenia wielokrotnie w dowodzie.

(1) Niech z1,z2∈DM i λ∈0,1. Wówczas istnieją x1,x2∈X takie że g⁢x1≤z1 i g⁢x2≤z2. Z wzoru (11.7) dostajemy g⁢λ⁢x1+1-λ⁢x2≤λ⁢z1+1-λ⁢z2, skąd wynika λ⁢z1+1-λ⁢z2∈DM.

(2) Niech z1,z2∈DM i λ∈0,1. Wówczas

	λ⁢M⁢z1+1-λ⁢M⁢z2	=infx1∈X,⁢g⁢x1≤z1⁡λ⁢f⁢x1+infx2∈X,⁢g⁢x2≤z2⁡1-λ⁢f⁢x2
		=infx1∈X,⁢g⁢x1≤z1,⁢x2∈X,⁢g⁢x2≤z2⁡λ⁢f⁢x1+1-λ⁢f⁢x2
		≥infx1∈X,⁢g⁢x1≤z1,⁢x2∈X,⁢g⁢x2≤z2⁡f⁢λ⁢x1+1-λ⁢x2
		≥infx∈X,⁢g⁢x≤λ⁢z1+1-λ⁢z2⁡f⁢x,

gdzie pierwsza nierówność wynika z wypukłości f, zaś ostatnia – z własności (11.7):

λ⁢x1+1-λ⁢x2:⁢x1∈X,⁢g⁢x1≤z1,⁢x2∈X,⁢g⁢x2≤z2⊆x∈X:⁢g⁢x≤λ⁢z1+1-λ⁢z2.

(3) Musimy udowodnić, że zbiór dopuszczalny Wz jest niepusty dla z z pewnego otoczenia 0∈Rm. Wiemy, że istnieje punkt x*∈X, taki że gi⁢x*<0, i=1,…,m. Weźmy a=min⁡-gi⁢x*:⁢i=1,…,m. Wówczas dla każdego z∈-a,am mamy x*∈Wz. Zatem -a,am⊂DM.

∎

Uwaga 11.1

Jeśli M⁢z¯=-∞ dla pewnego z¯∈DM, to dla dowolnego z∈DM i λ∈0,1 mamy z wypukłości M⁢λ⁢z¯+1-λ⁢z=-∞.
Jeśli M⁢z¯=-∞ dla pewnego z¯∈DM, to M⁢z=-∞ dla z∈intDM. Wynika to wprost z powyższej uwagi.
Jeśli istnieje z¯∈intDM taki że M⁢z¯>-∞, to M⁢z>-∞ dla każdego z∈DM. Inaczej mielibyśmy sprzeczność z punktem (2).

Twierdzenie 11.3

Jeśli w problemie optymalizacji wypukłej istnieje punkt x*∈X, taki że gi⁢x*<0, i=1,…,m, oraz M⁢0>-∞, to M⁢z>-∞ dla każdego z∈DM oraz istnieje wektor μ∈0,∞m wyznaczający płaszczyznę podpierającą M:

M⁢z≥M⁢0-μT⁢z,⁢z∈DM.

Dowód

Z tw. 11.2 wynika, że M jest funkcją wypukłą i 0∈intDM. Zatem na mocy ostatniej z powyższych uwag mamy M⁢z>-∞ dla z∈DM. Istnienie płaszczyzny podpierającej wynika z tw. 3.8:

M⁢z≥M⁢0-μT⁢z,⁢z∈DM,

dla pewnego μ∈Rm. Udowodnimy teraz, że wszystkie współrzędne μ muszą być nieujemne. Przypuśćmy przeciwnie, tzn. μi<0 dla pewnego i∈1,…,m. Ponieważ 0∈intDM, to dla dostatecznie małego a>0 punkt z¯=0,…,0,a,0,…,0T, gdzie a jest na i-tej pozycji, należy do DM. Korzystając z ujemności μi mamy

M⁢z¯≥M⁢0-μi⁢a>M⁢0.

Z drugiej strony W0⊆Wz¯, czyli M⁢z¯≤M⁢0. To daje sprzeczność, czyli dowiedliśmy, że μ∈0,∞m.

∎

Wektor μ nazywamy wektorem wrażliwości dla problemu (11.4). Z tw. 3.8 wynika, że jeśli funkcja M jest różniczkowalna w punkcie 0, to μ=-D⁢M⁢0T. Zatem μ oznacza szybkość i kierunek zmian wartości minimalnej f przy zmianie ograniczeń, podobnie jak w przypadku ograniczeń równościowych omawianych wcześniej w tym rozdziale.

Zbadajmy teraz relacje pomiędzy wektorem wrażliwości a punktem siodłowym i warunkiem pierwszego rzędu. Zauważmy, że powiązanie punktu siodłowego z wektorem wrażliwości nie wymaga wypukłości problemu optymalizacyjnego.

Twierdzenie 11.4

Jeśli x¯,μ¯ jest punktem siodłowym funkcji Lagrange'a na zbiorze X×0,∞m, to μ¯ jest wektorem wrażliwości (tzn. wyznacza płaszczyznę podpierającą). Teza ta nie wymaga założenia o wypukłości problemu optymalizacyjnego.
Załóżmy, że funkcje f,g1,…,gm są różniczkowalne w x¯, i wypukłe. Jeśli w x¯ spełniony jest warunek pierwszego rzędu z mnożnikami Lagrange'a μ¯∈0,∞m, to μ¯ jest wektorem wrażliwości.

Dowód

(1) Oznaczmy przez Lz⁢x,μ funkcję Langrange'a dla problemu zaburzonego. Wówczas

Lz⁢x,μ=f⁢x+∑i=1mμi⁢gi⁢x-zi=L⁢x,μ-μT⁢z.

Z faktu, że x¯,μ¯ jest punktem siodłowym wynika, że

M⁢0=L⁢x¯,μ¯=infx∈X⁡L⁢x,μ¯.

Zatem

M⁢0=infx∈X⁡L⁢x,μ¯=infx∈X⁡Lz⁢x,μ¯+μ¯T⁢z=infx∈X⁡Lz⁢x,μ¯+μ¯T⁢z.

(11.8)

Zauważmy, że dla dowolnego x∈Wz i μ∈0,∞m mamy f⁢x≥Lz⁢x,μ, czyli, w szczególności,

M⁢z=infx∈Wz⁡f⁢x≥infx∈Wz⁡Lz⁢x,μ¯≥infx∈X⁡Lz⁢x,μ¯.

Wstawiając tą zależność do (11.8) otrzymujemy

M⁢0≤M⁢z+μ¯T⁢z.

(2) Z zadania 10.1 wynika, iż punkt x¯,μ¯ jest punktem siodłowym funkcji Lagrange'a. Tezę dostajemy z pierwszej części niniejszego twierdzenia.

∎

11.3. Zadania

Ćwiczenie 11.1

Dla problemu

x12+2⁢x22→min,x12+x22≤0,x1≤0.

Znaleźć DM.
Znaleźć wektor wrażliwości.
Znaleźć funkcję perturbacji.

Wskazówka:

Umieszczenie ograniczenia x12+x22≤0 było intencją autora zadania.

Ćwiczenie 11.2

Znajdź funkcję perturbacji i wektor wrażliwości dla problemu

x12+x22→min,x1+x2≤0.

Ćwiczenie 11.3

Załóżmy, że w zadaniu optymalizacyjnym (11.4) funkcje f i gi są klasy C1 oraz X=Rn. Czy funkcja perturbacji musi być wówczas klasy C1? Udowodnij lub podaj kontrprzykład.

Ćwiczenie 11.4

Załóżmy, że w zadaniu optymalizacyjnym (11.4) funkcje f i gi są ciągłe oraz X=Rn. Czy funkcja perturbacji musi być wówczas ciągła? Udowodnij lub podaj kontrprzykład.

Ćwiczenie 11.5

Rozważmy problem producenta. Dysponuje on budżetem b>0, który może spożytkować na wytworzenie dwóch rodzajów towarów. Pierwszy z towarów sprzedaje po cenie p1>0, zaś drugi – po cenie p2>0. Cena produkcji opisana jest funkcją c⁢x1,x2, gdzie wektor x opisuje wielkość produkcji każdego z towarów. Celem producenta jest maksymalizacja przychodów ze sprzedaży bez przekroczenia budżetu produkcyjnego:

p1⁢x1+p2⁢x2→max,c⁢x1,x2≤b.

Podaj warunki konieczne istnienia rozwiązania powyższego problemu.
Załóżmy, że c jest funkcją wypukłą. Jak należy zmodyfikować wielkość produkcji, jeśli budżet produkcyjny b wrośnie nieznacznie?

Ćwiczenie 11.6

Rozważmy funkcję f:0,∞→R zadaną wzorem

f⁢t=minx,y∈R⁡ex2-y+y2-x:⁢x2+x4-2⁢x⁢y+3⁢y2≤t.

Uzasadnij, że funkcja f jest dobrze określona i wypukła.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Optymalizacja II

Zagadnienia

11. Teoria wrażliwości

11.1. Ograniczenia równościowe

Twierdzenie 11.1

Dowód

11.2. Ograniczenia nierównościowe

Definicja 11.1

Twierdzenie 11.2

Dowód

Uwaga 11.1

Twierdzenie 11.3

Dowód

Twierdzenie 11.4

Dowód

11.3. Zadania

Ćwiczenie 11.1

Ćwiczenie 11.2

Ćwiczenie 11.3

Ćwiczenie 11.4

Ćwiczenie 11.5

Ćwiczenie 11.6