Masarykova univerzita
Ondřej Došlý
Základy konvexní analýzy a optimalizace v Rn. První vydání
Brno 2004
Došlý Ondřej Název knihy
c prof. RNDr. Ondřej Došlý, DrSc., 2005
Největší životní umění je neoptimalizovat konstantní funkce.
Předmluva Tato skripta jsou určena pro posluchače bakalářského a magisterského studia odborné matematiky a matematické ekonomie. Svým rozsahem odpovídají přednášené látce v předmětu Matematické programování a pokrývají i část předmětu Optimalizace. Učební text vznikl na základě přednášek autora na Přírodovědecké fakultě MU Brno v letech 1995 – 2004. Text byl připraven sázecím systémem TEX ve formátu LATEX 2ε .
Brno, říjen 2005
Autor
iii
Obsah 1 Úvod 1.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Základní pojmy z konvexní analýzy a teorie optimalizace . . . 1.3 Základní pojmy z numerické minimalizace . . . . . . . . . . . 2 Konvexní množiny 2.1 Základní pojmy . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Oddělování konvexních množin . . . . . . . . . . . . . . . . 2.3 Krajní body konvexních množin . . . . . . . . . . . . . . . . 2.4 Kombinatorické a topologické vlastnosti konvexních množin 2.5 Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Konvexní funkce 3.1 Základní vlastnosti konvexních funkcí . . 3.2 Kriteria konvexnosti diferencovatelných funkcí . . . . . . . . . . . . . . . . . . . . 3.3 Spojitost a směrová derivace konvexních funkcí . . . . . . . . . . . . . . . . . . . . 3.4 Další vlastnosti konvexních funkcí . . . . . 3.5 Subgradient a subdiferenciál . . . . . . . . 3.6 Fenchelova transformace . . . . . . . . . . 3.7 Systémy konvexních a afinních nerovností 3.8 Cvičení . . . . . . . . . . . . . . . . . . .
. . . . .
5 5 12 18 19 22
. . . . . . . . . . .
25 25
. . . . . . . . . . .
33
. . . . . .
. . . . . .
37 40 41 44 50 53
. . . . . . . . . . . . . . . . . . . . . . . .
57 57 59 64
. . . . . . . . . . . . . . . .
73 81
. . . . . .
. . . . . .
4 Nutné a dostatečné podmínky optimality 4.1 Extrémy konvexních funkcí . . . . . . . . . . . 4.2 Lagrangeův princip . . . . . . . . . . . . . . . . 4.3 Dualita v úlohách matematického programování 4.4 Závislost řešení úlohy matematického programování na parametrech . . . . . . . . . . 4.5 Cvičení . . . . . . . . . . . . . . . . . . . . . .
v
1 1 2 3
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
Kapitola 1
Úvod 1.1
Základní pojmy
Nechť X ⊂ Rn a f : X → R. V celém textu se budeme zabývat hledáním bodu množiny X, ve kterém funkce f nabývá svého minima resp. maxima na X, v některých případech pro nás tento bod nebude podstatný, nýbrž budeme pouze hledat hodnotu f ∗ = inf x∈X f (x) (resp. f¯ = supx∈X f (x)). Celou problematiku budeme nejdříve studovat z teoretického pohledu, budeme hledat nutné a postačující podmínky pro to, aby bod x ∗ ∈ X byl bodem minima funkce f na X (úlohu hledání maxima funkce f nebudeme až na vyjímky v kapitole o dualitě vyšetřovat, neboť hledání maxima funkce f je ekvivalentní hledání minima funkce −f ), ve druhé části textu budou tyto teoretické poznatky využity při konstrukci numerických metod minimalizace. Základní minimalizační úlohu budeme zapisovat ve tvaru f (x) → min,
x ∈ X.
(1.1)
Funkci f budeme nazývat cílovou funkcí (jiná terminologie je účinková resp. účelová funkce), množinu X nazýváme přípustnou množinou, body x ∈ X budeme nazývat přípustnými body nebo přípustnými řešeními a číslo f ∗ = inf x∈X f (x) nazýváme hodnotou úlohy (1.1) (je-li X = ∅, klademe f ∗ = ∞). Definice 1.1. Bod x∗ ∈ X nazveme bodem globálního minima nebo také řešením úlohy (1.1), jestliže f (x∗ ) ≤ f (x) pro všechna x ∈ X. Bod x∗ ∈ X nazveme bodem lokálního minima nebo také lokálním řešením úlohy (1.1)), jestliže existuje okolí Oε (x∗ ) = {x ∈ Rn : ||x − x∗ || < ε} bodu x∗ takové, že f (x∗ ) ≤ f (x) pro každé x ∈ X ∩ Oε (x∗ ). Jsou-li výše uvedené nerovnosti ostré pro x 6= x∗ , mluvíme o ostrých globálních resp. lokálních minimech. Nyní připomeňme základní tvrzení týkající se nutných a postačujících podmínek pro existenci globálního, resp. lokálního, minima funkce f na X. Důkazy těchto tvrzení je možno nalézt např. v [6, 13]. 1
Věta 1.2. ( Weierstrassova věta). Nechť X ⊆ Rn je kompaktní (tj. uzavřená a ohraničená) a f je spojitá na X. Pak existují body globálního minima a maxima funkce f na X. Hledáme-li pouze řešení úlohy (1.1) (tj. body maxima nás nezajímají), můžeme předpoklady Věty 1.2 poněkud zeslabit. Věta 1.3. Nechť X ⊆ Rn je kompaktní a f je zdola polospojitá na X (t.j. pro každé x0 ∈ X a každou posloupnost xn ∈ X, pro níž xn → x0 platí lim inf f (xn ) ≥ f (x0 )). Pak existuje globální řešení úlohy (1.1).
Věta 1.4. Nechť f : Rn → R je diferencovatelná v bodě x0 a x0 je lokálním extrémem funkce f . Pak ∂ ∂x1 f (x0 ) .. f 0 (x0 ) = = 0. . ∂ ∂xn f (x0 )
Věta 1.5. Nechť f je dvakrát spojitě diferencovatelná na R n , f 0 (x0 ) = 0 a (symetrická) matice n 2 ∂ f (x0 ) f 00 (x0 ) = ∂xi ∂xj i,j=1 je pozitivně definitní. Pak x0 je bodem ostrého lokálního minima funkce f . Věta 1.6. Nechť X ⊆ Rn je kompaktní a f je spojitá na X. Pak f nabývá svého minima a maxima na X ve stacionárním bodě ležícím uvnitř X nebo v některém hraničním bodě množiny X. Z předchozích vět by se mohlo zdát, že je již vybudován dostatečně silný teoretický aparát k rozpracování numerických metod řešení úlohy (1.1) (exaktní analytické řešení této úlohy lze v praktických případech nalézt jen zřídka). Z pohledu numerických metod však již pouhé hledání stacionárních bodů funkce může být obtížným numerickým problémem, který je často obtéžnější, než numerické zvládnutí přímých minimalizačních metod. Tyto metody vyžadují teoretický základ, který je poněkud odlišný od obsahu vět 1.2 – 1.6 a v tomto textu je prezentován v kapitole IV.
1.2
Základní pojmy z konvexní analýzy a teorie optimalizace
Ve druhé a třetí kapitole tohoto textu budeme věnovat pozornost základům konvexní analýzy, kde budeme studovat základní vlastnosti konvexních množin a konvexních funkcí. Připomeňme, že množina X ⊆ R n se nazývá konvexní, jestliže pro každé x1 , x2 ∈ X a každé λ ∈ [0, 1] je λx1 + (1 − λ)x2 ∈ X. 2
Je-li X ⊆ Rn konvexní, řekneme, že funkce f : X → R je konvexní na X, jestliže f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ), pro každé x1 , x2 ∈ X a každé λ ∈ [0, 1]. Následující věta zdůvodňuje důležitost konvexních funkcí v extremálních úlohách. Věta 1.7. Nechť (1.1) je konvexní úloha, tj. X je konvexní a f je konvexní na X. Je-li x∗ lokální řešení úlohy (1.1), pak je i jejím globálním řešením. Důkaz. Je-li x∗ lokálním řešením, existuje ε-ové okolí O ε (x∗ ) bodu x∗ takové, že f (x∗ ) ≤ f (x) pro ∀x ∈ Oε (x∗ )∩X. Nyní nechť x ∈ X, x 6= x∗ je libovolné. ε ¯ = λx + (1 − λ)x∗ je kx∗ − x ¯k ≤ ε, Zvolme λ = min{ kx−x ∗ k , 1}. Pak pro x ∗ ∗ tedy f (x ) ≤ f (¯ x) ≤ λf (x)+(1−λ)f (x ) a odtud snadnou úpravou f (x∗ ) ≤ f (x). Další tvrzení charakterizující význačnost konvexních funkcí v extremálních úlohách jsou uvedena v kapitolách III. a IV. S některými pojmy z teorie optimalizace se již čtenář setkal v kursu lineárního programování. Zde se zavádí pojem duální úlohy, studuje se souvislost této úlohy s původní, primární, úlohou, byl zde prezentován i praktický výpočetní algoritmus pro řešení úlohy lineárního programování. V kapitole IV. tohoto textu věnované teoretickým základům řešení extremálních úloh typu (1.1) uvedeme tvrzení která jsou zobecněním vět z předchozího odstavce, zavedeme pojem duální úlohy k obecné úloze matematického programování a ukážeme, že mezi těmito úlohami je podobný vztah jeko mezi primární a duální úlohou v lineárním programování. Tato tvrzení představují teoretický aparát řešení extremálních úloh. Tyto teoretické poznatky jsou pak využity ke konstrukci numerických metod řešení extremálních úloh, které jsou obsahem kapitol VI. a VII.
1.3
Základní pojmy z numerické minimalizace
Numerické metody řešení úlohy (1.1) je možno rozdělit zhruba do dvou skupin. Jednodušší případ, kdy X = Rn (tzv. nepodmíněná minimalizace), je probírán v VI. kapitole, v následující VII. kapitole je studován složitější případ X 6= Rn (tzv. podmíněná minimalizace). Pro oba případy je společné schéma postupu. Je dán bod x0 ∈ X (tzv. počáteční aproximace) a konstruuje se posloupnost {xk } zadaná předpisem xk+1 = xk + αk hk ,
(1.2)
kde αk ∈ R+ je tzv. délka k-tého kroku, hk je směr k-tého kroku. Jednotlivé numerické metody se liší způsobem výběru směru h k a délky αk k-tého 3
kroku. Přirozeným požadavkem, jehož splnění při konstrukci posloupnosti {xk } požadujeme, je lim f (xk ) = f ∗ = inf f (x). x∈X
k→∞
Libovolná posloupnost {xk }, xk ∈ X, mající tuto vlasnost se nazývá minimalizující posloupnost úlohy (1.1). Hlavními problémy, které studujeme v souvislosti s jednotlivými numerickými metodami jsou předpoklady na funkci f a množinu X, za kterých je posloupnost {xk } zadaná vztahem (1.2) při daném výběru směru h k a délky αk k-tého kroku vskutku minimalizující posloupností, vyšetřuje se konvergence této posloupnosti, popřípadě rychlost této konvergence. Poznamenejme ještě, že důležitým případem výběru délky kroku α k je tzv. jednorozměrná minimalizace, kdy α k se vybírá podle pravidla f (xk + αk hk ) = min f (xk + αhk ). α>0
Numerickým metodám jednorozměrné minimalizace je věnována V. kapitola.
4
Kapitola 2
Konvexní množiny V této kapitole jsou uvedeny základní vlastnosti konvexních množin, zhruba v rozsahu potřebném k výkladu teorie konvexního programování a zejména teorie duality v matematickém programování. Nejdůležitější částí kapitoly je odstavec o oddělování konvexních množin, neboť jeho výsledky tvoří základ konvexního programování. Naopak, výsledky odstavce týkajícího se kombinatorických a topologických vlastností konvexních množin nejsou v dalším textu bezprostředně využity, protože jsou však součásti většiny standardních textů věnovaných konvexní analýze, je zde uveden alespoň přehled nejdůležitějších výsledků z této oblasti.
2.1
Základní pojmy
Definice 2.1. Nechť X ⊆ Rn . Množina X se nazývá konvexní, jestliže pro všechna x1 , x2 ∈ X a pro každé λ ∈ [0, 1] je λx1 + (1 − λ)x2 ∈ X, tj. s libovolnými dvěma body x1 , x2 ∈ X leží v X celá úsečka spojující tyto dva body. Přímo z definice konvexní množiny plynou následující jednoduchá tvrzení. Věta 2.2. (i) Nechť I je libovolná indexová T množina a množiny X i jsou konvexní pro každé i ∈ I. Pak je množina i∈I Xi konvexní. (ii) Nechť X1 , . . . , Xm jsou konvexní množiny, α1 , . . . , αm ∈ R. Pak množina
n
α1 X1 + · · · + αm Xm := x ∈ R : x = je také konvexní.
m X i=1
αi xi , x i ∈ X i .
K vyšetřování vlastností konvexních množin zaveďme následující pojmy. 5
Definice 2.3. Množina X ⊆ Rn se nazývá: (i) kužel, jestliže pro každé x ∈ X a pro každé λ ∈ [0, ∞) je λx ∈ X, (ii) konvexní kužel, jestliže je současně konvexní množinou i kuželem. (iii) affinní, jestliže pro každé x1 , x2 ∈ X a pro každé λ ∈ R je λx1 + (1 − λ)x2 ∈ X, tj. X s libovolnými dvěma body obsahuje i celou přímku určenou těmito dvěma body. Dále budeme používat následující terminologii pro lineární kombinaci bodů z Rn . Definice 2.4. Nechť x1 , . . . , xm ∈ Rn . Lineární kombinace λ1 x1 +· · ·+λm xm se nazývá P (i) konvexní, je-li λi ≥ 0 a m k=1 λi = 1, (ii) nezáporná, je-li λi ≥ 0 pro všechna i = 1 . . . m, P (iii) afinní, je-li m k=1 λi = 1. Budeme rovněž používat pojem konvexního (kuželového, afinního) obalu množiny, což je nejmenší (vzhledem k inkluzi) konvexní (kuželová, afinní) množina obsahující danou množinu. Definice 2.5. Nechť X ⊆ Rn . (i) Průnik všech konvexních množin obsahujících množinu X se nazývá konvexní obal množiny X a značí se conv X. (ii) Průnik všech konvexních kuželů obsahujících X se nazývá kuželový (kónický) obal množiny X a značí se cone X. (iii) Průnik všech afinních množin obsahujících X se nazývá afinní obal množiny X a značí se aff X (iv) Zaměření afinního prostoru aff X nazýváme lineární obal množiny X a značíme Lin X, dim X označuje dimenzi prostoru Lin X. Všimněme si, že je-li X = {x1 , . . . , xm } ⊆ Rn , pak podle předchozí definice Lin X není množina všech lineárních kombinací prvků x 1 , . . . , xm , nýbrž lineárních kombinací prvků x 2 − x1 , . . . , xm − x1 . Tato definice lineárního obalu, lišící se od definice obvykle používané v lineární algebře, nám umožní jednodušší formulaci vlastností konvexních množin. Dále připomeňme, že je-li x0 ∈ aff X libovolný, je Lin X = {x = x ¯− x0 , x ¯ ∈ aff X}, a že každý afinní prostor můžeme popsat pomocí řešení jistého systému nehomogenních lineárních rovnic tvaru Ax = b, kde x ∈ R n , b ∈ Rm a A je matice typu m × n. Odtud zejména vidíme, že libovolná afinní množina je uzavřená. Věta 2.6. Nechť X ⊆ Rn . Je-li X konvexní množina (konvexní kužel, affinní prostor), pak libovolná konvexní (nezáporná, afinní) kombinace prvků z X je opět prvkem množiny X. 6
Důkaz. Dokážeme pouze tvrzení pro konvexní kombinace, důkaz zbývajících dvou tvrzení je analogický. Pro m = 2 je tvrzení totožné s definicí konvexní Pm+1 množiny. Pro m > 2 postupujeme indukcí. Nechť tedy x = i=1 λi xi je konvexní kombinace bodů x1 , . . . . , xm+1 ∈ X. Je-li λm+1 = 1, tj. λ1 = · · · = λm = 0, je tvrzení triviální a pro λm+1 < 1 platí x = (1 − λm+1 )
m X i=1
λi xi + λm+1 xm+1 . 1 − λm+1
Podle indukčního předpokladu je x ¯ := X.
Pm
λi i=1 1−λm+1 xi
∈ X a tedy i x ∈
Následující věta popisuje obaly množiny X pomocí lineárních kombinací bodů této množiny. Věta 2.7. Nechť X ⊆ Rn . Platí m m X X λi = 1 , λi xi : x1 , . . . , xm ∈ X, λ1 , . . . , λm ≥ 0, conv X = x = i=1
i=1
cone X = x =
aff X = x =
m X i=1
m X i=1
λi xi : x1 , . . . , xm ∈ X, λi ≥ 0 , λi xi : x1 , . . . , xm ∈ X,
m X i=1
λi = 1 ,
tj. conv X (cone X, aff X) je roven množině všech konvexních (nezáporných, afinních) kombinací prvků z X. Důkaz. Tvrzení opět dokážeme pouze pro konvexní obal, důkaz dalších dvou tvrzení je analogický. Označme Z množinu stojící na pravé straně dokazované množinové rovnosti. Dokážeme inkluze Z ⊆ conv X, Z ⊃ conv X. ⊆: Množina Z je konvexní. Vskutku, jsou-li z 1 , z2 ∈ Z, tj. z1 =
m X
z2 =
αi xi ,
Pm
i=1 αi
z = λz1 + (1 − λ)z2 =
βi yi ,
i=1
i=1
kde xi , yi ∈ X, αi , βi ≥ 0,
k X
=1=
m X
Pk
i=1
λαi xi +
i=1
βi a λ ∈ [0, 1], pak
k X i=1
(1 − λ)βi yi ∈ Z,
P Pk neboť λαi , (1−λ)βi ≥ 0 a λ m i=1 αi +(1−λ) i=1 βi = 1. Protože evidentně X ⊆ Z, platí conv X ⊆ conv Z = Z. 7
⊇: Nechť Y je libovolná konvexní množina, taková, že X ⊆ Y . Podle věty 2.6 je libovolná konvexní kombinace prvků z Y prvkem Y , což spolu s inkluzí X ⊆ Y implikuje Z ⊆ Y . Protože Y ⊇ X byla libovolná, \ conv X = Y ⊇ Z, Y ⊇X
tj. conv X ⊇ Z. V předchozí větě jsme popsali obaly množiny X ⊆ R n pomocí příslušných lineárních kombinací bodů této množin. Věta však neudává žádnou informaci o maximálním počtu bodů, jejichž lineární kombinace je třeba brát v úvahu. Upřesnění předchozí věty v tomto směru je obsahem následujících dvou tvrzení. Věta 2.8. Nechť X ⊆ Rn a x ∈ cone X je libovolné. Pak existují body x1 , . . . , xn ∈ X, λ1 , . . . , λn ≥ 0 taková, že x = λ1 x1 +· · ·+λn xn , tj. libovolný bod kónického obalu množiny X lze vyjádřit pomocí nezáporné kombinace nejvýše n bodů x1 , . . . , xn množiny X. Důkaz. Nechť x ∈ cone X. Pak podle Věty Pm2.7 existuje m ∈ N, x 1 , . . . , xm ∈ X a λ1 , . . . , λm ≥ 0 taková, že x = i=1 λi xi . Jsou-li body x1 , . . . , xm lineárně nezávislé, pak m ≤ n a tvrzení P věty platí. Jsou-li tyto body lineárně závislé, existují µ1 , . . . , µm ∈ R tak, že m i=1 µi xi = 0 a alespoň jedno z čísel µ je kladné. Nechť α ∈ R je libovolné, pak x=
m X i=1
λi xi − α
m X
µi xi =
i=1
m X i=1
(λi − αµi )xi .
Je-li α = minµi >0 µλii , pak je λi − αµi ≥ 0 pro každé i ∈ {1, . . . , m} a alespoň pro jeden index i je λi −αµi = 0, tj. x je nezáporná kombinace nejvýše m−1 bodů. Je-li m − 1 = n, je důkaz dokončen, jinak celou konstrukci opakujeme dokud nedostaneme x jako nezápornou kombinaci nejvýše n bodů. Věta 2.9. Nechť X ⊆ Rn , x ∈ conv XPje libovolné. Pak existují body x1 , . . . , xn+1 ∈ X a λ1 , . . . , λn+1 ∈ [0, 1], n+1 i=1 λi = 1 taková, že x = λ1 x1 + · · · + λn+1 xn+1 ,
tj. libovolný bod množiny conv X lze vyjádřit jako konvexní kombinaci nejvýše n + 1 bodů množiny X. Důkaz. Nechť A ⊆ Rn+1 je množina vektorů tvaru A = {[x, 1] : x ∈ X}. Není obtížné ověřit, že y = [x, 1] ∈ cone A, právě když x ∈ conv X. Nyní tvrzení plyne bezprostředně z Věty 2.8. 8
Příklad 2.10. (i) Dokažte následující tvrzení: Množina X je konvexní právě tehdy, když λX + µX = (λ + µ)X pro každé λ, µ ≥ 0. Řešení. Tvrzení je triviální, pokud λ = 0 = µ. Můžeme tedy předpokládat, že λ + µ > 0. Implikace ⇒: Nechť a ∈ λX + µX, tj. existují x 1 , x2 ∈ X taková, že λ µ a = λx1 + µx2 = (λ + µ) x1 + x2 = (λ + µ)x, λ+µ λ+µ µ λ x1 + λ+µ x2 ∈ X, neboť X je konvexní, tedy a ∈ (λ + µ)X. kde x = λ+µ Naopak, je-li a ∈ (λ + µ)X, tj. existuje x ∈ X takové, že a = (λ + µ)x = λx + µx, pak a ∈ λX + µX. Implikace ⇐: Nechť x1 , x2 ∈ X, λ ∈ [0, 1]. Pak
λx1 + (1 − λ)x2 ∈ λX + (1 − λ)X = (λ + 1 − λ)X = X, tedy X je konvexní.
N
(ii) Nechť A = {[x, y] : y ≥ 1 + x2 } ∪ {[0, 0]}. Určete conv A, cone A. Řešení. Přímým výpočtem lze ověřit, že přímky y = ±2x jsou tečnami k parabole y = 1 + x2 v bodech [±1, 2]. Protože množina A1 = {[x, y] : y ≥ 1 + x2 } je konvexní (intuitivně je to zřejmé, exaktně to plyne z konvexnosti funkce 1+x2 , viz [8, Věta 6.25 a Důsledek 6.27]). Body, které jsou v conv Ar A jsou vnitřní body úseček spojujících bod [0, 0] s body grafu [x, 1+x 2 ], |x| ≤ 1, odtud conv A = {[x, y], x ∈ [−1, 1], y ≥ 2|x|} ∪ {[x, y], |x| > 1, y ≥ 1 + x 2 } (nakreslete si obrázek). Podobně cone A = {[x, y], y ≥ 2|x|}.
N
Věta 2.11. Nechť X ⊆ Rn je kompaktní. Pak její konvexní obal conv X je také kompaktní. Důkaz. Definujme množinu n+1 X λi = 1 , Λ := λ = (λ1 , . . . , λn+1 ) ∈ Rn+1 : λi ≥ 0, i=1
2
Y := Λ×X n+1 ⊆ R(n+1) a dále definujme zobrazení F : Y → Rn předpisem F
(λ, x1 , . . . , xn+1 ) 7−→ (λ1 x1 + · · · + λn+1 xn+1 ). Protože zobrazení F je lineární, je spojité. Množina Y je kompaktní v R 2n+2 (je kartézským součinem kompaktních množin) a F (Y ) = conv X. Protože spojitý obraz kompaktní množiny je kompaktní množina, viz [7], je i conv X kompaktní. 9
Nyní se dostáváme k důležitému pojmu z konvexní analýzy, pojmu relativního vnitřku množiny v Rn . Jako ilustrační příklad uvažujme úsečku v R2 . Vnitřek této množiny (v obvyklé euklidovské metrice prostoru R 2 ) je prázdná množina, tj. žádný bod úsečky není jejím vnitřním bodem. Intuitivně je však zřejmé, že by bylo „rozumnéÿ považovat vnitřní body úsečky za vnitřní body množiny. Touto úvahou je motivována následující definice. Definice 2.12. Nechť X ⊆ Rn . Bod x ∈ X se nazývá relativně vnitřním bodem množiny X, jestliže existuje okolí O(x) bodu x tak, že O(x)∩aff X ⊆ X. Množina reletivně vnitřních bodů množiny X se nazývá relativní vnitřek množiny X a značí se ri X. Množina X rri X (kde X je uzávěr X) se nazývá relativní hranice množiny X a značí se r∂X. Následující věta obsahuje důležité tvrzení týkajících se konvexních množin (někdy bývá dokonce nazýváno „Základní věta teorie konvexních množinÿ) a je použito v důkazech řady dalších tvrzení v konvexní analýze. Věta 2.13. Je-li X ⊆ Rn neprázdná a konvexní, pak je ri X neprázdná. Důkaz. Bez újmy na obecnosti můžeme předpokládat, že 0 ∈ X, v opačném případě celý postup aplikujeme na množinu Y = {y = x − x0 ; x ∈ X} = X − x0 , kde x0 ∈ X libovolný, neboť pak platí 0 ∈ Y . Pak aff X = Lin X a nechť {x1 , . . . , xm } je maximální lineárně P nezávislý systém bodů množiny ˜ = {λ ∈ Rn : λi > 0, m λi < 1} a definujme zobrazení X. Označme Λ i=1 F : Rm → Rn následujícím předpisem F
λ = (λ1 , . . . , λm ) 7−→ λ1 x1 + · · · + λm xm . ˜ je libovolné, pak Nechť λ ∈ Λ F (λ) = λ1 x1 + · · · + λm xm + (1 −
m X i=1
λi ) · 0,
˜ ⊆ conv X = X a současně F (Λ) ˜ ⊆ Lin {x1 , . . . , xm } = aff X. tedy F (Λ) ˜ je otevřená Zobrazení F i F −1 jsou lineární a tedy i spojité. Poněvadž Λ n ˜ ˜ v R , je F (Λ) otevřená v aff X. Nechť y ∈ F (Λ) je libovolný, pak existuje ˜ tedy y ∈ ri X. okolí O(y) tak, že O(y) ∩ aff X ⊆ F (Λ), Při důkazech vlastností relativních vnitřků konvexních množin je užitečné následující tvrzení. Věta 2.14. Nechť X ⊆ Rn je konvexní, x ∈ ri X, y ∈ X. Pak pro každé λ ∈ (0, 1] je (1 − λ)y + λx ∈ ri X. 10
Důkaz. Označme z = λx+(1−λ)y. Podle definice z ∈ ri X právě tehdy, když pro každou posloupnost zk ∈ aff X, zk → z, platí zk ∈ X pro dostatečně velká k. Nechť tedy zk ∈ aff X je libovolná a zk → z. Protože y ∈ X, existuje posloupnost yk ∈ X tak, že yk → y. Nechť xk ∈ X jsou taková, že zk = λxk + (1 − λ)yk , tj. úsečka xk zk je bodem yk dělena v poměru λ. Lze ukázat, že (λ − 1)(yk − y) + zk − z xk = λx + . λ Pak xk ∈ aff X, xk → x. Odtud xk ∈ X pro dostatečně velká k (neboť x ∈ ri X) a tedy i zk = λxk + (1 − λ)yk ∈ X pro dostatečně velká k ∈ N . Jako přímý důsledek dostáváme toto tvrzení. Důsledek 2.15. Je-li X ⊆ Rn konvexní, pak i ri X je konvexní. Na závěr tohoto odstavce uveďme bez důkazu (ten je poměrně jednoduchou technickou záležitostí) následujcí tvrzení, které budeme často potřebovat. Věta 2.16. Nechť X ⊆ Rn je konvexní. Pak ri X = ri X a X = ri X. Množina X je také konvexní a aff X = aff X. Příklad 2.17. (i) Nechť A=
[
(αX + βY ),
(α,β)∈P
kde P ⊆ R2+ = {[x, y] : x, y > 0} je konvexní množina. Jsou-li X, Y konvexní, je A konvexní. Dokažte. Řešení. Nechť a1 , a2 ∈ A, λ ∈ [0, 1]. Pak existují (α1 , β1 ), (α2 , β2 ) ∈ P a x1 , x2 ∈ X, y1 , y2 ∈ Y taková, že a1 = α1 x1 + β1 y1 , a2 = α2 x2 + β2 y2 . Pak a =λa1 + (1 − λ)a2 = λ(α1 x1 + β1 y1 ) + (1 − λ)(α2 x2 + β2 y2 ) = =λα1 x1 + (1 − λ)α2 x2 + λβ1 y1 + (1 − λ)β2 y2 ,
tedy a ∈λα1 X + (1 − λ)X + λβ1 Y + (1 − λ)β2 Y =[λα1 + (1 − λ)α2 ]X + [λβ1 + (1 − λ)β2 ]Y
(předch. příklad)
=
(konvexnost P )
=
=αX + βY ⊆ X.
N (ii) Dokažte množinovou rovnost conv X + conv Y = conv (X + Y ). 11
Řešení. K důkazu množinové rovnosti dokážeme dvojici inkluzí: ⊇: X + Y ⊆ conv X + conv Z, odtud conv (X + Y ) ⊆ conv (conv X + conv Y ) = conv X + conv Y, nebot’ množina conv X + conv Y je podle Věty 2.2 konvexní. ⊆: Nechť a ∈ conv X + conv Y , tj. existují x ∈ conv X, z ∈ conv Z taková, že a = x + y. Odtud a=
n+1 X
λi xi +
i=1
i=1
µi yi =
i=1
Protože xi + yj ∈ X + Y , n+1 X
n+1 X
Pn+1 j=1
n+1 X i=1
λi
n+1 X
(xi + yj )µj .
j=1
µj (xi + yj ) =: wi ∈ conv (X + Y ), odtud
λi wi ∈ conv (conv (X + Y )) = conv (X + Y ). N
(iii) Dokažte implikaci: X ⊆ Rn je otevřená ⇒ conv X je otevřená. Řešení. Nechť x ¯ ∈ conv X, tj. podle Caratheodoryho věty existují Pn+1 Pn+1body x1 , . . . , xn+1 ∈ X a λ1 , . . . , λn+1 ≥ 0, i=1 λi = 1 taková, že x ¯ = i=1 λi xi . Protože X je otevřená, existuje ε > 0 takové, že O (x ) = {x : kx − xi k < ε i P ε} ⊆ X pro i = 1, . . . , n + 1. Položme O(¯ x) = n+1 λ O (x ). x) = i=1 i ε i Pak O(¯ {x : kx − x ¯k < ε} ( dokažte sami, např indukcí vzhledem k dimenzi n) je hledané okolí x ¯, které je celé obsaženo v conv X. N
2.2
Oddělování konvexních množin
Věty o oddělitelnosti konvexních množin jsou, jak uvidíme v kapitole 4, teoretickým základem konvexního programování. Definice 2.18. Množiny X1 , X2 ⊆ Rn se nazývají (i) oddělitelné , existuje-li 0 6= p ∈ R n a tak, že hp, x1 i ≥ hp, x2 i
pro každé x1 ∈ X1 , x2 ∈ X2 .
(2.1)
(ii) vlastně oddělitelné , pokud jsou oddělitelné a existují x ¯ 1 ∈ X1 , x ¯ 2 ∈ X2 a β ∈ R tak, že hp, x ¯1 i > hp, x¯2 i. (iii) silně oddělitelné , jestliže
inf hp, x1 i > β > sup hp, x2 i.
x1 ∈X1
x2 ∈X2
12
Nadrovina Hp,β := {x ∈ Rn : nadrovinou množin X1 , X2 .
hp, xi = β} se potom nazývá oddělující
Důležitým nástrojem při důkazu vět o oddělitelnosti konvexních množin je pojem projekce bodu na množinu. Kromě toho je tento pojem důležitý i při konstrukci numerických metod nepodmíněné minimalizace, viz. Kapitola VI. Definice 2.19. Nechť X ⊆ Rn , a ∈ Rn . Bod x∗ ∈ X nazveme projekcí bodu a na množinu X, značíme ΠX (a), jestliže kΠX (a) − ak ≤ kx − ak pro každé x ∈ X. Základní vlastnosti projekce bodu na množinu jsou shrnuty v následujícím tvrzení. Lemma 2.20. Nechť X ⊆ Rn je uzavřená a konvexní. Pak pro každé a 6∈ X existuje jediná projekce ΠX (a) ∈ X a pro každé x ∈ X platí hΠX (a) − a, x − ΠX (a)i ≥ 0,
hΠX (a) − a, x − ai ≥ kΠX (a) − ak2 ≥ 0.
(2.2) (2.3)
Důkaz. Projekce bodu x na množinu X je řešením úlohy f (x) = kx − ak → min, x ∈ X. Položme Y = X ∩ {x ∈ Rn : ||x − a|| ≤ R}, kde R je dostatečně velké reálné čislo. Pak Y je kompaktní a podle Weierstassovy věty (Věta 1.2) existuje minimum funkce f na Y a snadno se vidí, že je rovno minimu f na X, tedy projekce bodu na množinu existuje. Označme x∗ = ΠX (a), pak vzhledem ke konvexnosti množiny X pro libovolné x ∈ X, λ ∈ (0, 1] platí kx∗ − ak2 ≤ kλx + (1 − λ)x∗ − ak2 = kx∗ − a + λ(x − x∗ )k2 = = hx∗ − a + λ(x − x∗ ), x∗ − a + λ(x − x∗ )i =
= kx∗ − ak2 + 2λhx∗ − a, x − x∗ i + λ2 kx − x∗ k,
odtud vydělením λ ∈ (0, 1] dostaneme 0 ≤ 2hx∗ − a, x − x∗ i + λkx − x∗ k. Limitním přechodem pro λ → 0+ dostaneme hx ∗ − a, x − x∗ i ≥ 0, což je první z požadovaných tvrzení v (2.2). Druhá nerovnost v (2.3) plyne z (2.2) přidáním členů ±a v druhé složce skalárního součinu a následnou elementární úpravou. 13
Pomocí vlastností projekce bodu na konvexní množinu můžeme nyní snadno dokázat následující nutnou a postačující podmínku pro silnou oddělitelnost konvexních množin. Věta 2.21. Konvexní množiny X1 , X2 ⊆ Rn jsou silně oddělitelné právě tehdy, když vzdálenost množin ρ(X1 , X2 ) =
inf
x1 ∈X1 ,x2 ∈X2
||x1 − x2 || > 0.
Důkaz. Implikace ⇐: Nechť X1 , X2 jsou silně oddělitelné (nikoliv nutně konvexní), pak využitím Cauchyovy nerovnosti 0 < ε := ≤
inf hp, x1 i − sup hp, x2 i =
x1 ∈X1
inf
(x1 ,x2 )∈X1 ×X2
x2 ∈X2
inf
(x1 ,x2 )∈X1 ×X2
hp, x1 − x2 i ≤
kpkkx1 − x2 k = kpkρ(X1 , X2 ),
ε > 0. a tedy ρ(X1 , X2 ) ≥ kpk Implikace ⇒: Nechť X1 , X2 jsou konvexní, a ρ(X1 , X2 ) > 0. Označme X = X1 − X2 , snadno lze ověřit, že tato množina je konvexní a uzavřená (viz věty 2.2 a 2.16). Protože ρ(X1 , X2 ) > 0 a 0 6∈ X je p = ΠX (0) 6= 0. Ukážeme, že p je hledaný normálový vektor oddělující nadroviny. Z nerovnosti (2.3) v Lemmatu 2.20 plyne (volbou a = 0)) hp, xi ≥ kpk 2 > 0 pro každé x ∈ X. Odtud hp, x1 − x2 i = hp, x1 i − hp, x2 i ≥ kpk2 ,
a tedy
inf hp, x1 i − sup hp, x2 i ≥ kpk2 > 0.
x1 ∈X1
x2 ∈X2
Nyní lze vzít β ∈ (supx2 ∈X2 hp, x2 i, inf x1 ∈X1 hp, x1 i) libovolné a Hp,β je oddělující nadrovina množin X1 , X2 . Z teorie metrických prostorů je známo, že je-li (P, ρ) metrický prostor a A, B ⊆ P jsou uzavřené a disjunktní, X 2 je ohraničená (a tedy i kompaktní), pak je ρ(X1 , X2 ) > 0. Tato skutečnost a Věta 2.2.6. implokují následující tvrzení. Důsledek 2.22. Nechť X1 , X2 ⊆ Rn jsou konvexní a disjunktní, X1 uzavřená, X2 kompaktní. Pak jsou X1 , X2 silně oddělitelné. Jiným důležitým pojmem z teorie konvexních množin je pojem opěrné nadroviny. Definice 2.23. Nechť X ⊆ Rn , a ∈ ∂X = X − int X. Nadrovina Hp,β se nazývá (i) opěrná nadrovina množiny X v bodě a, jestliže hp, xi ≥ β = hp, ai pro každé x ∈ X. 14
(ii) vlastní opěrná nadrovina, je-li opěrná nadrovina a existuje x ¯ ∈ X takové, že hp, x¯i > β.
Věta 2.24. Nechť X ⊆ Rn je konvexní a a ∈ ∂X. Pak v tomto bodě existuje vlastní opěrná nadrovina této množiny. Je-li navíc a ∈ r∂X, existuje v a vlastní opěrná nadrovina množiny X. Důkaz. Důkaz provedeme pro existenci vlastní opěrné nadroviny v relativně hraniční bodě. Normálový vektor opěrné nadroviny sestrojíme takto. Zvolme a ∈ r∂X libovolný. Z vlastností množiny r∂X existuje a k ∈ aff X, ak 6∈ X, ak → a. Položme ΠX (ak ) − ak . pk = kΠX (ak ) − ak k Pak kpk k = 1, pk ∈ Lin X. Protože množina {x : kxk = 1} je kompaktní, můžeme z posloupnosti {pk } vybrat konvergentní podposloupnost. Bez újmy na obecnosti předpokládejme, že pk → p, kde kpk = 1 a p ∈ Lin X. Ukážeme, že p je hledaný normálový vektor vlastní opěrné nadroviny množiny X v bodě a. Z nerovnosti (2.3) v Lemmatu 2.20 plyne, že hp k , xi − hpk , ak i > 0 pro každé x ∈ X. Limitním přechodem pro k → ∞ dostáváme hp, xi ≥ hp, ai =: β, pro každé x ∈ X. Tím jsme ukázali, že H p,β je opěrná nadrovina. Ještě zbývá dokázat, že jde o vlastní opěrnou nadrovinu. Podle Věty 2.13 existuje x1 ∈ ri X. Položme x ¯ = x1 + p pro nějaké > 0 dostatečně malé. Protože p ∈ Lin X (neboť pk ∈ Lin X a Lin X je uzavřená množina), je x ¯ ∈ aff X. Z definice ri X je pro ε > 0 dostatečně malé také x ¯ ∈ X. Přímým 2 výpočtem pak hp, x ¯i = hp, x1 + εpi = hp, x1 i + εkpk > β. Nejdůležitějším výsledkem o oddělitelnosti konvexních množin je následující tvrzení. Věta 2.25. Konvexní množiny X1 , X2 ⊆ Rn jsou vlastně oddělitelné právě tehdy, když ri X1 ∩ ri X2 = ∅.
Důkaz. ⇐: Položme X := ri X1 − ri X2 . Pak X je konvexní a 0not ∈ X (ověřte sami!). Jsou možné dva případy: 0 6∈ X, nebo 0 ∈ X r X ⊆ r∂X. V prvním případě jsou podle Věty (2.21) množiny {0} a X silně oddělitelné a tato oddělující nadrovina odděluje i X 1 a X2 . V druhém případě z Věty 2.24 plyne existence vlastní opěrné nadroviny k X v bodě 0 a lze ukázat, že tato nadrovina vlastně odděluje X1 a X2 . ⇒: Předpokládejme sporem, že X1 , X2 jsou vlastně oddělitelné a existuje x ∈ ri X1 ∩ ri X2 . Z definice vlastní oddělitelné nadroviny existují x ¯1 ∈ X1 , x¯2 ∈ X2 takové, že hp, x ¯1 i > hp, x ¯2 i. Položme x ˜1 = x + α(¯ x1 − x) ∈ X1 , x ˜2 = x + α(¯ x2 − x) ∈ X2 . Pak x ˜1 ∈ aff X1 , x ˜2 ∈ aff X2 , a tedy x ˜ 1 ∈ X1 , x ˜2 ∈ X2 pro α > 0 dostatečně malé. Současně ale hp, x ˜1 i − hp, v˜2 i = hp, α(¯ x2 − x) − α(¯ x1 − x)i = = −αhp, x ¯1 − x ¯2 i < 0, 15
spor. Na závěr tohoto odstavce připomeňme, jak lze věty o oddělitelnosti konvexních množin využít ke studiu úloh lineárního programování. Věta 2.26. (Farkas - Minkonwski) Nechť A je m × n matice, b ∈ R m . Pak je právě jeden z následujících systémů rovnic a nerovnic řešitelný. Ax = b, x ≥ 0,
(2.4)
T
A y ≥ 0, hy, bi < 0. Důkaz. Předpokládejme, že x ∈ Rn a y ∈ Rm jsou současně řešení obou systémů, pak 0 > hy, bi = hy, Axi = hAT y, xi ≥ 0,
což je spor. Předpokládejme nyní, že systém (2.4) není řeitelný a označme a 1 , . . . , an sloupcové vektory tvořící matici A. Pak vektor b 6∈ cone {a 1 , . . . , an }. Protože cone {a1 , . . . , an } je uzavřená množina, jsou b a cone {a 1 , . . . , an } silně oddělitelné a nechť y je normálový vektor oddělující nadroviny, tj. hy, zi > hy, bi pro všechna z ∈ cone {a1 , . . . , an }, tedy pro všechna x ∈ Rn , x ≥ 0 je hy, Axi = hAT y, zi > hy, bi.
Dosadíme-li do poslední rovnosti x = 0, dostáváme 0 > hy, bi a nechámeli všechny složky vektoru x konvergovat do ∞, platí nerovnost pouze, je-li AT y ≥ 0. Jako důsledek Farkas-Minkovského věty dostáváme toto tvrzení. Věta 2.27. Nechť A je matice m × n a b ∈ R m . Pak existuje řešení právě jedné z následujících úloh Ax ≤ b, T
A y = 0,
x ∈ Rn ;
(2.5)
hy, bi < 0, y ≥ 0.
(2.6)
h˜ x, ˜bi < 0
(2.7)
Důkaz. Nechť A˜ = (A, b) je m × (n + 1) matice, ˜b = 01 ∈ Rn+1 (here 0 ∈ Rn ), x ˜ = xλ ∈ Rn+1 (with λ ∈ R) a uvažujme systémy ekvivalentní systémům z tvrzení věty: ˜x > 0, A˜ A˜T y = ˜b,
y ≥ 0.
(2.8)
Pak (2.5) je ekvivalnetní (2.8), (2.6) je ekvivalentní (2.7) a tvrzení o existenci právě jednoho z řešení systémů (2.5), (2.6) plyne z Věty 2.26. Nakonec jestě připomeňme jedno tvrzení z teorie lineárního programování, které lze snadno dokázat z předchozích vět. 16
Věta 2.28. Je-li v úloze lineárního programování hc, xi → min, x ∈ X, kde X = {x ∈ Rn , Ax ≥ b}, přičemž A je matice m × n, b ∈ R m , přípustná množina X neprázdná a f (x) = hc, xi je zdola ohraničená na X, pak je úloha řešitelná. Důkaz. Předpokládejme, že úloha není řešitelná a označme α = inf x∈X hc, xi (toto infimum existuje, protože minimalizovaná funkce f (x) = hc, xi je zdola ohraničená na X.) Pak neexistuje řešení úlohy Ax ≥ b, hc, xi ≤ α, která je ekvivalentní systému −A −b x≤ . T c α Podle předpokladu věty existují y ∈ R m , λ ∈ R tak, že λy je řešením systému −A
T
y c = 0, λ
který je ekvivalentní systému
AT y = λc,
T −b y < 0, α λ
hy, bi > λα,
y ≥ 0, λ
y, λ ≥ 0.
Tedy pro libovolné x ∈ X platí λhc, xi = hA T y, xi = hy, Axi ≥ hy, bi > λα, tj. λ > 0 a 1 inf hc, xi ≥ hy, bi > α, x∈X λ což je spor.
Cvičení 1. Nechť jsou dány množiny X = {[x, y] ∈ R 2 : y ≥ 1 + x2 }, Y = {[x, y] ∈ R2 : x ≥ αy 2 }. Určete pro jaké hodnoty parametru α jsou množiny X, Y oddělitelné. 2. Nechť X, Y jsou oddělitelné množiny, int X 1 6= ∅. Pak X, Y jsou vlastně oddělitelné. Dokažte. 3. Nechť X, Y ⊆ Rn . Množiny \ [ [ [ {λX + (1 − λ)Y } , {λX + (1 − λ)Y } y∈Y λ≥1
y∈Y λ≥1
se nazývají stín resp. polostín X na Y (zdůvodněte geometricky si tuto terminologii). Dokažte, že za předpokladu konvexnosti X a Y jsou tyto množiny konvexní. 17
2.3
Krajní body konvexních množin
Definice 2.29. Nechť X ⊆ Rn je konvexní množina. Bod x ∈ X nazveme krajním (jiný termín je extremální) bodem množiny X, jestliže jej nelze vyjádřit ve tvaru x = λx1 + (1 − λ)x2 ,
pro žádné
x1 , x2 ∈ X, λ ∈ (0, 1).
(2.9)
Množinu všech krajních bodů množiny X značíme E(X). Bod x ∈ X je tedy krajním bodem, jestliže neleží uvnitř žádné úsečky, jejíž krajní body jsou prvky množiny X. Např. krajními body konvexního mnohoúhelníka jsou jeho vrcholy, krajními body kruhu jsou body hraniční kružnice apod. Ke studiu množiny krajních bodů konvexní množiny budeme potřebovat následující dvě tvrzení. Zaveďme potřebné označení: Nechť x ∈ Rn , polopřímku prochá+ zející bodem x se směrovým vektorem h ∈ Rn budeme značit lx,h , tedy + lx,h = {y ∈ Rn : y = x + ht, t ≥ 0}. − + − Opačnou polopřímku budeme značit lx,h a lx,h = lx,h ∪lx,h je přímka určená bodem x a směrem h.
Věta 2.30. Nechť X je neohraničená uzavřená konvexní množina. Pak (i) Pro libovolný x0 ∈ X existuje 0 6= h ∈ Rn takový, že lx+0 ,h ⊆ X. + (ii) Jestliže lx+0 ,h ⊆ X pro nějaké x0 ∈ X a h ∈ Rn , pak lx,h ⊆ X pro každé x ∈ X. Důkaz. (i) Nechť x0 ∈ X je libovolné. Z neohraničenosti množiny X plyne existence posloupnosti xk ∈ X takové, že kxk k → ∞. Nechť α ≥ 0 je libovolné. Položme hk =
xk − x 0 , kxk − x0 k
λk =
α , kxk − x0 k
x¯k = λk xk + (1 − λk )x0 .
Protože khk k = 1, můžeme z posloupnosti {hk } vybrat konvergentní podposloupnost. Bez újmy na obecnosti můžeme předpokládat, že hk → h. Pro dostatečně velká k je λk ∈ [0, 1] (jelikož kxk k → ∞), a tedy vzhledem ke konvexnosti X je x ¯k ∈ X. Současně x ¯k = x0 + λk (xk − x0 ) = x0 + αhk a tedy x ¯k → x0 + αh ∈ X, neboť množina X je uzavřená. Protože α ≥ 0 bylo libovolné, je první část věty dokázána. (ii) Nechť lx+0 ,h ⊆ X a x ∈ X je libovolné. Pro α ≥ 0 a k ∈ N položme xk = x0 + (αk)h,
x ¯k =
1 1 xk + (1 − )x. k k
Pak xk ∈ lx+0 ,h ⊆ X a z konvexnosti X je i x¯k ∈ X. Současně x¯k = x + k1 (x0 − x) = ¯k → x+αh a vzhledem k uzavřenosti X máme x+αh ∈ X, x+αh+ k1 (x0 −x). Tedy x + tj. lx,h ⊆ X. Lemma 2.31. Nechť X ⊆ Rn je uzavřená a konvexní množina, x∗ ∈ r∂X je relativně hraniční bod množiny X, H = Hp,β je vlastní opěrná nadrovina množiny X v bodě x∗ , tj. hp, xi ≥ β = hp, x∗ i, pro každé x ∈ X, hp, x ¯i > β pro některé x ¯ ∈ X. Položme X ∗ = X ∩ Hp,β . Pak E(X ∗ ) ⊆ E(X) a dim X ∗ < dim X.
18
(2.10) (2.11)
Důkaz. Předpokládejme, že existuje x ∈ E(X ∗ ) a současně x 6∈ E(X), tj. x můžeme vyjádřit ve tvaru (2.9) Pak z (2.10) plyne β = hp, xi = λhp, x1 i + (1 − λ)hp, x2 i ≥ λβ + (1 − λ)β = β.
Odtud plyne hp, x1 i = hp, x2 i = β, tj. x1 , x2 ∈ X ∩ H = X ∗ . Tento vztah však spolu s (2.9) dává x 6∈ E(X ∗ ), což je spor. K důkazu druhé části tvrzení lemmatu označme M = aff X, M ∗ = aff X ∗ . Pak M ∗ ⊆ M , M ∗ ⊆ H a také X ∗ ⊆ X, X ∗ ⊆ H. Připusťme, že M ∗ = M . Pak X ⊆ M = M ∗ ⊆ H, to znamená, že hp, xi = β pro každé x ∈ X, což je spor s se skutečností, že H je vlastní opěrná nadrovina v bodě x∗ . Tedy M ∗ ⊂ M , což znamená, že i Lin X ∗ ⊂ Lin X a tedy dim Lin X ∗ < dim Lin X, což bylo třeba dokázat. Následující věta udává kriterium existence krajních bodů konvexní množiny. Věta 2.32. Nechť X ⊆ Rn je uzavřená konvexní množina. Pak E(X) 6= ∅ právě když X neobsahuje žádnou přímku, tj. pro každé x ∈ X a každé h ∈ Rn je lx,h 6⊆ X.
Důkaz. ⇒: Důkaz první implikace provedeme sporem. Nechť je tedy E(X) neprázdná, tj. existuje x ∈ E(X), a existuje x0 ∈ X a 0 6= h tak, že lx0 ,h ⊆ X. Pak + − podle Věty 2.30 lx,h ⊆ X a lx,h ⊆ X, speciálně x1 = x + h ∈ X, x2 = x − h ∈ X a 1 x = 2 (x1 + x2 ), tedy x 6∈ E(X). ⇐: Důkaz druhé implikace provedem indukcí vzhledem dim X. Je-li dim X = 0, je X = {x} jednoprvková a E(X) = {x} 6= ∅. Předpokádejme, že tvrzení je již dokázáno pro dim X < m. Protože X neobsahuje žádnou přímku, je r∂X 6= ∅ (ověřte sami) a nechť X ∗ je množina z Lemmatu 2.31. Protože dim X ∗ < m, vzhledem k indukčnímu předpokladu je E(X ∗ ) 6= ∅, inkluze E(X ∗ ) ⊆ E(X) nyní dává požadované tvrzení. Vztah mezi množinami X a E(X) v případě konvexní a kompkatní množiny popisuje následující věta. Věta 2.33. Nechť X ∈ Rn je konvexní a kompaktní. Pak X = conv E(X).
Důkaz. Vzhledem ke konvexnosti množiny X evidentně conv E(X) ⊆ X, stačí tedy dokázat opačnou inkluzi. Budeme opět postupovat indukcí vzhledem k dimenzi množiny X. Je-li dim X = 0, je tvrzení triviální. Předpokládejme, že tvrzení je již dokázáno pro dim X < m. Nechť x∗ ∈ r∂X je libovolné (r∂X 6= ∅ ze stejného důvodu jako v předchozí větě) a uvažujme množinu X ∗ z Lemmatu 2.31. Tato množina je kompaktní a konvexní, tedy podle indukčního předpokladu X ∗ = conv E(X ∗ ), specielně x∗ ∈ conv E(X ∗ ) ⊆ conv E(X) a protože x∗ bylo libovolné, je i r∂X ⊆ E(X). Vezměme nyní x∗ ∈ ri X libovolné a nechť h ∈ Lin X. Pak přímka lx,h leží v aff X a její průsečík s relativní hranicí množiny X je dvouprvková množina {x1 , x2 }. Tedy lx,h ∩ X = conv {x1 , x2 }. Odtud dostáváme x∗ ∈ conv {x1 , x2 } ⊆ conv (r∂X) ⊆ conv (conv E(X)) = conv E(X), tj. ri X ⊆ E(X) a celkem tedy X = r∂X ∪ ri X ⊆ conv E(X).
2.4
Kombinatorické a topologické vlastnosti konvexních množin
V tomto odstavci si uvedeme dvě tvrzení z teorie konvexních množin, která sice nemají bezprostřední souvislost s optimalizačními úvahami z dalších kapitol, jsou však z teoretického i historického hlediska důležitá.
19
Nejprve dokažme jedno pomocné tvrzení z lineární algebry. Připomeňme, že body x1 , . . . , xm ∈ Rn se nazývají afinně závislé existují λ1 , . . . ,λm ∈ R, Pm , jestliže P m ne všechna současně rovna nule taková, že i=1 λi = 0 a i=1 λi xi = 0.
Lemma 2.34. Body x1 , . . . , xm ∈ Rn jsou afinně závislé, právě když body x2 − x1 , . . . , xm − x1 jsou lineárně závislé. Důkaz. jsou body x1 , . . . , xm afinně závislé, tj. existují λ1 , . . . , λm tak, P ⇒: NechťP m že m i=1 λi = 0 a i=1 λi xi = 0, přičemž ne všechna λ1 , . . . , λm jsou nulová. Pak 0=
m X i=1
λ i xi − x 1
m X
λi =
i=1
m X i=1
λi (xi − x1 ),
tj. xi − x1 , i P = 2, . . . , m jsou lineárně závislé. m ⇐: Je-li ne všechna µP i jsou nulová, položme λ1 = i=2 µi (xi − x1 ) = 0 aP Pm m m − i=2 µi , λi = µi , i = 2, . . . , m. Pak i=1 λi = 0, i=1 λi xi = 0 a ne všechna λi jsou nulová, takže body x1 , · · · , xn jsou afinně závislé. Věta 2.35. (Hellyova věta) Nechť m ≥ n + 1, X1 , . . . , Xm ⊆ Rn jsou konvexní a každá (n + 1)-tice z těchto množin má neprázdný průnik. Pak ∩i∈I Xi 6= ∅. Důkaz. Důkaz provedeme indukcí vzhledem k m. Je-li m = n + 1, tvrzení zřejmě platí. Nechť tvrzení platí pro m a m + 1 > n + 1. Dále nechť y1 ∈ X2 ∩ · · · ∩ Xm+1 , y2 ∈ X1 ∩ X3 ∩ · · · ∩ Xm+1 , . . . , ym+1 ∈ X1 ∩ · · · ∩ Xm přičemž podle indukčního předpokladu jsou všechny tyto průniky neprázdné, tj. taková yi existují. Protože m > n, jsou P y1 , . . . , ym+1 afinně závislé, tedy existují c1 , . . . , cm+1 , taková, že P m+1 m+1 i=1 ci yi = 0 a i=1 ci = 0, kde alespoň jedno ci > 0. Položme P P ci y i ci >0 ci yi ∗ , x ¯ = Pci <0 . x = P ci >0 ci ci <0 ci Pak x∗ − x ¯ = 0, tj. x∗ = x ¯. Jestliže je ck ≤ 0 pro nějaké k ∈ {1, · · · }, pak je x∗ konvexní kombinací bodů y1 , . . . , yk−1 , yk+1 , . . . , ym , z nichž každý leží v množině Xk . Tedy i x∗ ∈ Xk . Je-li ck > 0, z téhož důvodu x¯ ∈ Xk , tj. i v tomto případě x∗ ∈ Xk . Protože k ∈ {1, . . . , m + 1} bylo libovolné, x∗ ∈ ∩m+1 i=1 Xi . Tím je tvrzení dokázáno.
Poznámka 2.36. (i) S Hellyovou větou se můžeme ve středoškolské matematice setkat v této elementární modifikaci (která však umožňuje formulaci řady velmi zajímavých příkladů, viz. [11, 3] ). Jsou-li K1 , . . . , Km , m ≥ 3, konvexní mnohoúhelníky v rovině, přičemž každá trojice těchto mnohoúhelníků má neprázdný průnik, pak existuje x0 ∈ ∩m i=1 Ki . (ii) Uvažujeme-li nekonečný systém konvexních množin, tvrzení Hellyovy věty obecně neplatí. Stačí uvažovat systém množin Ki = {(x, y) ∈ R2 | x ≥ i, y ∈ R} pro i ∈ N. Platí však toto modifikované tvrzení, viz. např. [21, str. 118].
20
Věta 2.37. Nechť K = {Ki , i ∈ I} je systém (obecně nekonečný) konvexních a kompaktních množin v Rn . Má-li libovolný (n + 1)-prvkový podsystém systému K neprázdný průnik, pak ∩i∈I Ki 6= ∅. Nyní uveďme základní topologické vlastnosti konvexních množin. Nechť X ⊆ R n je konvexní množina a předpokládejme, že v sobě obsahuje jednotkovou kouli se středem v počátku B n = {x ∈ Rn : ||x|| ≤ 1} a označme S n−1 jednotkovou sféru, tj. hranici B n . Definujme tzv. hraniční zobrazení b : ∂X → S n−1 předpisem b(x) =
x . ||x||
Připomeňme, že zobrazení mezi dvěma metrickými (topologickými) prostory nazveme homeomorfismem, jestliže toto zobrazení i zobrazení k němu inverzní (o němž se předpokládá, že existuje) jsou spojitá. Lemma 2.38. Hraniční zobrazení b je homeomorfismem mezi ∂X a S n−1 . Důkaz. Nejprve si všimněme, že b je navyájem jednoznačné zobrazení. Vskutku, je-li x ∈ S n−1 , nechť ω ∈ R je největší číslo, pro něž ωx ∈ X. Pak ωx je hraniční bod množiny X (v opačném případě se dostáváme do sporu s definicí čísla ω) a tento bod je jediným hraničním bodem X, který je skalárním násobkem x ∈ S n−1 . Protože kyk ≥ 1 pro každý hraniční bod X a euklidovská norma je spojité zobrazení, dostáváme spojitost zobrazení b. Spojitost zobrazení b−1 plyne z faktu, že inverzní zobrazení k zobrazení zobrazujícímu kompaktní množinu na kompaktní množinu je spojité. Věta 2.39. Nechť X ⊆ Rn je konvexní, kompaktní a dim X = n. Pak X je homeomorfní jednotkové kouli B n = {x ∈ Rn : ||x|| ≤ 1} v Rn . Důkaz. Protože dim X = n, je podle Věty 2.13 int X 6= ∅, tj. X obsahuje kouli v Rn o dostatečně malém poloměru. Vzhledem k tomu, že posunutí a skalární násobení nenulovou konstantou jsou homeomorfismy v Rn , bez újmy na obecnosti můžeme předpokládat, že X obsahuje jednotkovou kouli B n . Homeomorfismus f : B n → X nyní definujme pomocí hraničního zobrazení takto: −1 b (x/||x||) pro x 6= 0 f (x) = 0 pro x = 0. Ověření skutečnosti, že toto zobrazení je vskutku homeomorfismus přenecháme čtenáři jako cvičení.
Poznámka 2.40. Předchozí věty nám vlasně říkají, že libovolná konvexní množina obsahující ve svém vnitřku počátek definuje normu na Rn , která je ekvivalentní obvyklé euklidovské normě. Tuto normu lze definovat vztahem ||x||X = inf{α ∈ R+ : α−1 x ∈ X}. Na závěr tohoto odstavce uveďme jedno důležité tvrzení týkající se spojitých zobrazení konvexních a kompaktních množin. Uvedeme jej zde bez důkazu, protože ten vyžaduje zavedení řady nových pojmů (především z algebraické topologie), které přesahují rámec toho textu. Elemenární metodu důkazu (technicky však poměrně komplikovanou), založenou na tzv. Spernerově kombinatorickém lemmatu lze nalézt např. v [21].
21
Věta 2.41. (Brouwerova věta o pevném bodu). Nechť ∅ 6= X ⊆ Rn je konvexní a kompaktní množina f : X → X je spojité zobrazení. Pak má f alespoň jeden pevný bod, tj existuje x0 ∈ X, pro něž f (x0 ) = x0 .
Poznámka 2.42. V předchozích odstavcích jsou uvedeny pouze základní vlasnosti konvexních množin. Zcela stranou zůstaly například tzv. polární množiny ke konvexním množinám a některé další důležité pojmy z konvexní analýzy. Obsáhlé pojednání věnované dalším vlasnostem konvexních množin lze nalézt v [20].
2.5
Cvičení
1. Nechť A, B jsou konvexní. Rozhodněte, zda platí conv (A ∪ B) = ∪λ∈[0,1] (λA + (1 − λ)B). 2. Nechť A ⊆ Rn je konvexní. Rozhodněte, zda platí ri λX = λ ri X pro každé λ ∈ R. 3. Dokažte tuto modifikaci Caratheodoryho věty: PnNechť x ∈ ∂ conv X. (tj. o jedno Pak existují x1 , . . . , xn ∈ X a λ1 , . . . , λn ≥ 0, i=1 λi = 1P méně než v klasické Caratheodoryho větě) taková, že x = ni=1 λi xi . 4. Nechť X1 , . . . , xm ⊂ Rn jsou libovolné množiny. Dokažte následující identity ! ! m m m m X X X X conv Xi = conv Xi , aff Xi = aff Xi , i=1
ale
i=1
m X
i=1
i=1
cone Xi = cone (∪m i=1 Xi ) .
i=1
5. Nechť X1 , X2 ⊆ Rn jsou libovolné, přičemž sup hp, x1 i = inf hp, x2 i x2 ∈X2
x1 ∈X
pro každé p ∈ Rn . Pak conv X1 = conv X2 . Dokažte. 6. Nechť X, Y ⊆ Rn . Definujme X ⊕ Y = ∪λ∈[0,1] {λX + (1 − λ)Y }. Jsou-li X, Y konvexní, je i X ⊕ Y konvexní. Dokažte. 7. Nechť K1 , K2 jsou konvexní kužely. Pak K1 ⊕ K2 = K1 ∪ K2 . Dokažte. 8. Nechť X ⊆ Rn je konvexní. Pak platí aff (ri X) = aff X. Dokažte. 9. Nechť X ⊆ Rn . Množina X ∗ := {y ∈ Rn : hy, xi ≥ −1 pro každé x ∈ X}
se nazývá sdružená (někdy také duální, konjugovaná) k množině X. Dokažte tato tvrzení: 22
(i) Pro libovolnou X ⊆ Rn je X ∗ = conv (X ∪ {0}). (ii) Je-li X kužel v Rn , pak X ∗ := {y ∈ Rn : hy, xi = 0 pro každé x ∈ X} Q 10. Dokažte, že pro konvexní množinu XQ⊆ R n je projekce X tzv. neQ expanzivní zobrazení, tj. || X (x) − X (y)|| ≤ ||x − y|| pro všechna x, y ∈ Rn . 11. Dokažte, že pro konvexní množinu X ⊆ R n platí toto tvrzení: dim X = n právě když int X 6= ∅. 12. Nechť X ⊆ Rn je uzavřená. Dokažte toto tvrzení: X je konvexní právě když existuje λ ∈ (0, 1) takové, že λx+(1−λ)y ∈ X pro každé x, y ∈ X, tj. s každými dvěma body z X leží v X i bod, který dělí úsečku určenou body x, y v poměru λ.
23
24
Kapitola 3
Konvexní funkce Konvexní funkce hrají klíčovou roli v teorii optimalizace, neboť v praktických úlohách je většina minimalizovaných funkcí právě konvexní (resp. konkávní v případě maximalizace). Tato kapitola obsahuje souhrn základních vlastností konvexních funkcí v rozsahu prezentovaném ve standardních monografiích věnovaných matematickému programování.
3.1
Základní vlastnosti konvexních funkcí
Definice 3.1. Nechť X ⊂ Rn je konvexní množina, funkce f : X → R se nazývá (i) konvexní na X, je-li pro všechna x 1 , x2 ∈ X a každé λ ∈ [0, 1] f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 );
(3.1)
(ii) ostře konvexní na X, platí-li pro každé λ ∈ (0, 1) a x 1 6= x2 ve vztahu (3.1) ostrá nerovnost; (iii) silně konvexní na X s konstantou silné konvexnosti ϑ > 0, je-li f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ) −
(3.2)
2
−ϑλ(1 − λ)||x1 − x2 || .
Poznámka 3.2. (i) V některých monografiích věnovaných konvexní analýze, viz. např. [20, 21], se často vyšetřuje konvexnost funkcí, které mohou nabývat i nevlastních hodnot ±∞, tj. funkcí f : X → [−∞, ∞]. Definiční vztah pro toto obecnější pojetí konvexních funkcí je stejný jako (3.1), přičemž se používá obvyklé konvence pro počítání s nevlastními hodnotami (např. ∞ + a = ∞ pro a ∈ R, a · ∞ = ∞ pro a > 0, a · ∞ = −∞ pro a < 0, atd.). Tato zobecněná definice je výhodná při studiu některých speciálních vlastností konvexních funkcí, v tomto textu se však až na malé výjimky omezíme na funkce nabývající pouze konečných hodnot. (ii) Jako příklady konvexních funkcí uveďme např. funkce f (x) = hc, xi, f (x) = kxk4 = hx, xi2 , f (x) = kxk2 . Je zřejmé, že lineární funkce f (x) = 25
hc, xi je konvexní na Rn , není však ostře konvexní ani silně konvexní, neboť v definičním vztahu (3.1) platí vždy rovnost. Důkaz konvexnosti funkce f (x) = ||x||2 stejně jako rozdíl mezi silnou a ostrou konvexností uvedeme později. Rovněž ukážeme, že funkce f (x) = kxk 4 není silně konvexní na množinách obsahujících počátek, tj. bod x = 0. Základní vztah, který umožňuje řadu vlastností konvexních množin z předchozí kapitoly využít ke studiu konvexních funkcí uvádí následující věta. Věta 3.3. Nechť X ⊂ Rn je konvexní a f : X → R. Funkce f je konvexní na X právě tehdy, když její epigraf (nadgraf) epi f = {[x, β] ∈ Rn+1 : x ∈ X, β ≥ f (x)} je konvexní množina. Důkaz. ⇒: Nechť [x1 , β1 ], [x2 , β2 ] ∈ epi f , tj. β1 ≥ f (x1 ), β2 ≥ f (x2 ) a nechť λ ∈ [0, 1]. Pak λ[x1 , β1 ] + (1 − λ)[x2 , β2 ] = [λx1 + (1 − λ)x2 , λβ1 + (1 − λ)β2 ] a platí λβ1 + (1 − λ)β2 ≥ λf (x1 ) + (1 − λ)f (x2 ) ≥ f (λx1 + (1 − λ)x2 ), tj. λ[x1 , β1 ] + (1 − λ)[x2 , β2 ] ∈ epi f , což znamená, že epi f je konvexní množina. ⇐: Nechť x1 , x2 ∈ X, λ ∈ [0, 1], pak [x1 , f (x1 )], [x2 , f (x2 )] ∈ epi f což je konvexní množina, tedy λ[x1 , f (x1 )] + (1 − λ)[x2 , f (x2 )] = [λx1 + (1 − λ)x2 , λf (x1 ) + (1 − λ)f (x2 )], je prvkem epi f , tj. λf (x1 ) + (1 − λ)f (x2 ) ≥ f (λx1 + (1 − λ)x2 ), tedy f je konvexní. Dříve než začneme studovat základní vlastnosti konvexních funkcí, uvedeme tvrzení, která motivují vyšetřování konvexních funkcí z hlediska jejich extremálních vlastností. Věta 3.4. Nechť funkce f je konvexní na konvexní množině X ⊆ R n . Pak: (i) Libovolné lokální minimum funkce f na X je i globálním minimem. (ii) Množina bodů X, v nichž funkce f nabývá na X svého minima je konvexní. Je-li navíc funkce f na X ostře konvexní, je tato množina nejvýše jednoprvková. 26
(iii) je-li funkce f diferencovatelná na X a x ∗ ∈ X jej jejím stacionárním bodem, tj. f 0 (x∗ ) = 0, pak x∗ je bodem globálního minima f na X. Důkaz. (i) Nechť x∗ je lokálním minimem f na X, tj. existuje ε > 0 takové, že f (x) ≥ f (x∗ ) pro x spňující kx − x∗ k ≤ ε. Nechť nyní x ∈ X je libovolné. Je-li kx − x∗ k ≤ ε, není co dokazovat, předpokladejme tedy, že kx − x ∗ k > ε. Označme x ˆ bod, který je průsečíkem úsečky spojující x ∗ a x se sférou kx − x∗ k = ε, tj. pro λ = 1/kx − x∗ k platí x ˆ = λx + (1 − λ)x∗ . Pak ∗ kˆ x − x k = ε, a tedy f (x∗ ) ≤ f (ˆ x) = f (λx + (1 − λ)x∗ ) ≤ λf (x) + (1 − λ)f (x∗ ). Otud f (x) ≥ f (x∗ ), což znamená, že x∗ je bodem gobálního minima funkce f na X. (ii) Jestliže funkce f nenabývá svého minima na X, je tvrzení triviální, neboť prázdná množina je konvexní. jestliže existují x 1 , x2 ∈ X taková, že f (x1 ) = f (x2 ) = f ∗ − inf x∈X f (x), pak pro libovolné λ ∈ [0, 1] f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ) = f ∗ .
(3.3)
Z definice f ∗ je zřejmé, že v (3.3) musí platiti rovnost, což dokazuje tvrzení o konvexnosti množiny bodů, v nichž je nabyto minima. Je-li f navíc f ostře konvexní, rovnost v (3.3) nastane pro λ ∈ (0, 1) pouze je-li x 1 = x2 . (iii) Z definice diferencovatelnosti funkce f plyne, že pro x, x ∗ ∈ X a λ ∈ (0, 1] platí f (λx+(1−λ)x∗ ) = f (x∗ +λ(x−x∗ )) = hf 0 (x∗ ), λ(x−x∗ )iα(λkx−x∗ k), (3.4) kde funkce α splňuje limλ→0 α(λkx − x∗ k)/λ = 0. Současně, z konvexnosti f plyne f (λx + (1 − λ)x∗ ) ≤ λf (x) + (1 − λ)f (x∗ ). Kombinací tohoto vztahu s (3.4) (a využitím, že f 0 (x∗ ) = 0) dostáváme f (x) − f (x∗ ) ≥ = =
1 [f (x∗ + λ(x − x∗ )) − f (x∗ )] = λ 1 0 ∗ [hf (x ), λ(x − x∗ )i + α(λ(x − x∗ )] λ α(λ(x − x∗ )) . λ
Limitním přechodem λ → 0+ dostáváme požadované tvrzení. Následující dvě věty jsou uvedeny bez důkazu. První plyne téměř bezprostředně z definice konvexní funkce a druhou lze dokázat stejným způsobem jako Větu 2.6 z předchozí kapitole věnované konvexním množinám. Věta 3.5. Nechť X ⊂ Rn je konvexní, f1 , . . . , fm : X → R jsou konvexní na X a α1 , . . . , αm ≥ 0. Pak funkce α1 f1 + · · · + αm fm je konvexní na X. 27
Věta 3.6. (Jensenova nerovnost). Nechť množina X ⊆ R n je konvexní, f: P X → R je konvexní funkce, x1 , . . . , xm ∈ X, λ1 , . . . , λm ≥ 0 a m λ = 1. i=1 i Pak platí ! m m X X f λi xi ≤ λi f (xi ). (3.5) i=1
i=1
Je-li funkce f navíc ostře konvexní a λ i ∈ (0, 1), i = 1, . . . , m, pak rovnost v (3.5) nastane právě když x1 = · · · = xm . Důkaz. V důkazu tohoto tvrzení postupujeme podobně jako v případě Věty 2.6 matematickou indukcí, proto přeskočíme některé detaily. Jeli m = 2, je dokazovaná nerovnost nerovností z definice konvexní funkce. Předpokládejme, že tvrzení platí pro m > 2. Pak za předpokladu λ m+1 6= 1 (jinak je tvrzení triviální) f (λ1 x1 + . . . +λm xm + λm+1 ) = f (1 − λm+1 ) λm xm + λm+1 xm+1 ≤ 1 − λm+1 f ((1 − λm+1 )¯ x + λm+1 xm+1 ) ≤ +
≤
≤
≤
λ1 x1 + ··· + 1 − λm+1
(1 − λm+1 )f (¯ x) + λm+1 f (xm+1 )
λ1 f (x1 ) + . . . λm f (xm ) + λm+1 f (xm+1 ),
λ1 x1 λm xm kde x ¯ = 1−λ + · · · + 1−λ . m+1 m+1 Nyní dokážeme zbývající část tvrzení týkající se ostré konvexity a rovnosti v (3.5). Je-li x1 = · · · = xm =: x, pak evidentně
f (λ1 x1 + . . . λm xm ) = f x
m X i=1
=
m X
λi = f (x) = f (x)
λi f (x) =
i=1
m X i=1
m X
λi
!
=
λi f (xi )
i=1
Opačnou implikaci dokážeme opět indukcí. Pro m = 2 a λ i ∈ (0, 1), λ1 + λ2 = 1, rovnost f (λ1 x1 + λ2 x2 ) = λ1 f (x1 ) + λ2 f (x2 ) může nastat pouze, když x1 = x2 (viz definice ostré konvexity). Předpokládejme, že tvrzení platí pro m ∈ N a nechť f
m+1 X i=1
X m+1 λi f (xi ), λi xi = i=1
28
(3.6)
kde λ1 , . . . , λm+1 ∈ (0, 1). Označme x ˜= f (λ1 x1 + . . . λm xm + λm+1 xm+1 ) =
Pm
λ1 i=1 1−λm+1 xi .
Pak platí
= f ((1 − λm+1 )˜ x + λm+1 xm+1 ) ≤ λ1 λm ≤ (1−λm+1 )f x1 + · · · + xm +λm+1 f (xm+1 ) ≤ 1 − λm+1 1 − λm+1 ≤ λ1 f (x1 ) + · · · + λm f (xm ) + λm+1 f (xm+1 ), což vzhledem k (3.6) znamená, že obě nerovnosti v předchozím výpočtu se realizují jako rovnosti. První z nich implikuje x ˜ = x m+1 (definice ostré konvexity) a druhá implikuje x1 = · · · = xm (indukční předpoklad), což celkem dává x1 = · · · = xm = xm+1 . Jako důsledek předchozí věty dostáváme řadu „středoškolskýchÿ nerovností, viz [11], zejména nerovnost mezi algebraickým a geometrickým průměrem m-tic kladných čísel. Z diferenciálního počtu funkcí jedné proměnné je známo, že funkce − ln x je konvexní na (0, ∞) (neboť (− ln x) 00 = x12 > 0, vizP [8, str. 125]), tedy pro libovolná x 1 , . . . , xm > 0 a λ1 , . . . , λm ≥ 0 taková, že m i=1 λi = 1 platí ! ! m m m Y X X λi xi , λi ln xi = − ln λi xi ≤ − − ln odtud
i=1
i=1
i=1
m X i=1
λi xi ≥ xλ1 1 · · · xλnn
(3.7)
(v některé literatuře bývá termín Jensenova nerovnost používán právě pro tuto nerovnost). Zejména, je-li λi = 1/m, i = 1, . . . , m, dostáváme nerovnost √ x1 + · · · + x m ≥ m x1 . . . x m , m což je známá nerovnost mezi algebraickým a geometrickým průměrem (tzv. AG-nerovnost). Později ukážeme, že funkce − ln x je ostře konvexní a tento fakt implikuje, že v rovnost v poslední nerovnosti nastane právě když x 1 = · · · = xm . Věta 3.7. Nechť X ⊂ Rn je konvexní, I je libovolná indexová množina, fi : X → R jsou konvexní pro ∀i ∈ I a pro ∀x ∈ X je množina {f i (x), i ∈ I} shora ohraničená. Pak je funkce f (x) = sup fi (x) i∈I
konvexní na X. 29
Důkaz. Nechť x1 , x2 ∈ X, λ ∈ [0, 1]. Pak f (λx1 + (1 − λ)x2 ) = sup fi (λx1 + (1 − λ)x2 ) ≤ i∈I
≤ sup {λfi (x1 ) + (1 − λ)f (x2 )} ≤ i∈I
≤ λ sup fi (x1 ) + (1 − λ) sup fi (x2 ) = i∈I
i∈I
= λf (x1 ) + (1 − λ)f (x2 ).
Nyní si všimněme, jak se zachovává konvexnost při skládání funkcí. Věta 3.8. Nechť X ⊂ Rn je konvexní množina, g1 , . . . , gm jsou konvexní na X, funkce f : Rm → R je konvexní a neklesající (v tomto smyslu: je-li x = (x1 , . . . , xm ), y = (y1 , . . . , ym ), xi ≤ yi , i = 1, . . . , m, pak f (x) ≤ f (y)). Pak složená funkce F (x) := f (g1 (x), . . . , gm (x)) je konvexní na X. Důkaz. Nechť x1 , x2 ∈ X a λ ∈ [0, 1] jsou libovolná. Platí F (λx1 +(1 − λ)x2 ) = f (g1 (λx1 + (1 − λ)x2 ), . . . , gm (λx1 + (1 − λ)x2 ) ≤ ≤f (λ(g1 (x1 ), . . . , gm (x1 )) + (1 − λ)(g1 (x2 ), . . . , gm (x2 ))) ≤
≤λf (g1 (x1 ), . . . , gm (x1 )) + (1 − λ)(f (g1 (x2 ), . . . , gm (x2 ))) = =λF (x1 ) + (1 − λ)F (x2 ).
Tedy složená funkce F je konvexní. Poznámka 3.9. (i) Označme G = (g1 , . . . , gm ) : Rm → Rn . Je-li G afinní, tj. existuje matice A typu m × n, b ∈ Rm tak, že G(x) = Ax + b, pak není obtížné ukázat, že předpoklad monotonie funkce f v předchozí větě není nutný. (ii) Jsou-li f1 , . . . , fm konvexní na X, pak z předchozích dvou vět plyne, že pro q ≥ 1 je konvexní i funkce q f (x) = max {f1 (x), . . . , fm (x)} . 1≤i≤m
Tato skutečnost se často využívá v teorii tzv. penalizačních funkcí, o které se zmiňujeme v poslední kapitole. Příklad 3.10. Pomocí Jensenovy nerovnosti dokažte nerovnost r p r q p q p x1 + · · · + x n q x1 + · · · + x n ≥ n n pro kladná x1 , . . . , xn a p > q > 0. 30
Řešení. Uvažujme funkci f (z) = z p/q , která je pro z ≥ 0 konvexní, neboť q p p/q q > 1 a položme yi = xi . Aplikací Jensenovy nerovnosti (3.5) na funkci z s λ1 = · · · = λn = n1 dostáváme p/q
y1 + · · · + y n ≤ n
p/q
+ · · · + yn n
y1
!q/p
.
Umocněním této nerovnosti na q-tou a dosazením za y i dostáváme požadovanou nerovnost. N Příklad 3.11. Pomocí Jensenovy nerovnosti dokažte Hölderovu nerovnost n X i=1
|xi yi | ≤
n X i=1
!1
n X
p
|xi |
p
kde p, q jsou tzv. konjugovaná čísla, tj.
1 p
i=1
+
1 q
!1 q
|yi |
p
,
= 1, p, q > 1.
Řešení. Budeme vycházet z toho, že f (z) = z p , p > 1, je konvexní na (0, ∞) (neboť f 00 (z) = p(p − 1)z p−2 > 0 pro z ∈ (0, ∞)). Elementární úpravou dostáváme !p ! !p Pn n n 1−q q p X X x y y k k=1 Pn k q k = xk yk ykq . y k=1 k k=1
k=1
yq Pn k
Položme zk = xk yk1−q , λk = n X
k=1
ykq
xk yk1−q Pn
q k=1 yk
!p
k=1
n X
=
ykq
. Pak z Jensenovy nerovnosti
λk zk
k=1
!p
≤
n X
λk zkp =
k=1
n X k=1
A tedy
yq xpk ykp−pq Pn k
q. k=1 yk
!p n !p !p Pn n n X q X X ykq xk yk1−q ykq p p−pq q k=1 Pn Pn ≤ = yk yk xk yk q q k=1 yk k=1 yk k=1 k=1 k=1 !p−1 !p−1 n n n n X X X X p p+q−pq q p q xk yk yk xk yk = = k=1
protože ze vztahu n X k=1
xk yk ≤
1 p
+
1 q
n X k=1
k=1
k=1
k=1
= 1 plyne p + q − pq = 0. Odtud dostáváme
xpk
!1
p
n X k=1
ykq
! p−1
31
p
=
n X k=1
xpk
!1
p
n X
k=1
ykq
!1 q
. N
Příklad 3.12. Nechť f : R → R je konvexní, x 1 < x2 < x3 . Dokažte nerovnost f (x2 ) − f (x1 ) f (x3 ) − f (x1 ) ≥ . x3 − x 1 x2 − x 1 Řešení. Označme λ = (x2 − x1 )/(x3 − x1 ) ∈ (0, 1). Pak x2 =
x2 − x 1 x2 − x 1 x3 + 1 − x1 = λx3 + (1 − λ)x1 . x3 − x 1 x3 − x 1
Odtud f (x2 ) = f (λx3 + (1 − λ)x1 ) ≤ λf (x3 ) + (1 − λ)x1 = x3 − x 2 x2 − x 1 f (x3 ) + f (x1 ). = x3 − x 1 x3 − x 1 Vynásobíme tuto nerovnost jmenovatelem (x 3 − x1 ) a následným přičtením výrazu (x1 − x3 )f (x1 ) k oboum stranám nerovnosti dostáváme f (x2 )(x3 − x1 ) ≤ (x2 − x1 )f (x3 ) + (x3 − x2 )f (x1 )
(x3 − x1 )(f (x2 ) − f (x1 )) ≤ (x2 − x1 )(f (x3 ) − f (x1 )) a odtud již snadno dostáváme požadované tvrzení.
N
Příklad 3.13. Nechť f : R → R je konvexní. Dokažte nerovnost f (x + y) ≥ f (x) + f (y) − f (0) pro x, y > 0. Řešení. Nechť x, y > 0. Platí f (y) = f (0 ·
x x y x + (1 − )(x + y)) ≤ f (0) + f (x + y). x+y x+y x+y x+y
Podobně f (x) ≤
x y f (0) + f (x + y). x+y x+y
Sečtením obou nerovností dostáváme požadované tvrzení.
N
Příklad 3.14. Nechť ϕ : [a, b] → R je integrovatelná a f : R → R je konvexní. Dokažte Jensenovu nerovnost v integrálním tvaru ! Z b ∫ab ϕ(t) dt 1 f ≤ f (varphi(t)) dt. b−a b−a a 32
Řešení. Nechť t0 = a < t1 < · · · < tn = b je ekvidistantní dělení intervalu [a, b] a ξi , i = 1, . . . , n, je libovolný výběr reprezentantů příslušející tomuto dělení. Pak z integrovatelvosi ϕ plyne Z b n X ϕ(ξi )(ti − ti−1 ) = lim ϕ(t) dt n→∞
a z konvexnosti f a rovnosti Jensenovy nerovnosti (3.5) f
a
i=1
Pn
i=1 (ti
n X ϕ(ξi )(ti − ti−1 ) i=1
b−a
!
− ti−1 ) = b − a dostáváme aplikací ≤
n X i=1
f (ϕ(ξi ))
ti − ti−1 . b−a
Limitním přechodem pro n → ∞ dostáváme požadované tvrzení, R b neboť na pravé straně poslední nerovnosti je integrální součet integrálu a f (ϕ(t)). N
3.2
Kriteria konvexnosti diferencovatelných funkcí
Ze základního kursu matematické analýzy známo (viz např. [8, Odst. 6.3]), že funkce f jedné proměnné je konvexní na intervalu I ⊂ R, právě tehdy, když platí jedna z podmínek (i) Pro všechna x0 , x ∈ I je f (x) ≥ f (x0 ) + f 0 (x0 )(x − x0 ), tj., graf funkce f leží nad tečnou sestrojenou v libovolném bodě grafu; (ii) Funkce f 0 je neklesající na intervalu I, (iii) Jestliže existuje druhá derivace f 00 a pro každé x ∈ I platí f 00 (x) ≥ 0. Nyní si dokážeme analogická tvrzení pro funkce více proměnných. V těchto tvrzeních silná konvexnost s konstantou ϑ = 0 znamená obvyklou konvexnost. Věta 3.15. Nechť X ⊂ Rn je konvexní a funkce f je diferencovatelná na X. Pak f je silně konvexní na X s konstantou silné konvexity ϑ ≥ 0 právě tehdy, když pro každé x, x0 ∈ X platí f (x) ≥ f (x0 ) + hf 0 (x0 ), x − x0 )i + ϑkx − x0 k2 .
(3.8)
Důkaz. ⇒: Nechť f je silně konvexní s konstantou ϑ ≥ 0, tj. platí (3.2), odtud 1 [f (λx + (1 − λ)x0 ) − f (x0 )] = λ 1 o(λ) = [hf 0 (x0 ), λ(x − x0 )i + o(λ)] = hf 0 (x0 ), x − x0 i + , λ λ
f (x) − f (x0 ) − ϑ(1 − λ)kx − x0 k2 ≥
33
v poslední rovnosti jsme využili diferencovatelnosti funkce f , symbolem o(λ) rozumíme libovolnou funkci, pro níž lim λ→0 o(λ)/λ = 0. Limitním přechodem pro λ → 0 dostaneme nerovnost (3.8). ⇐: Nechť x1 , x2 ∈ X, λ ∈ [0, 1] jsou libovolná a označme x 0 = λx1 + (1 − λ)x2 . Podle (3.8) platí f (x1 ) ≥ f (x0 ) + hf 0 (x0 ), x1 − x0 i + ϑkx1 − x0 k2 ,
f (x2 ) ≥ f (x0 ) + hf 0 (x0 ), x2 − x0 i + ϑkx2 − x0 k2 .
Vynásobíme-li první nerovnost λ, druhou (1 − λ) a vzniklé nerovnosti sečteme, dostáváme λf (x1 ) + (1 − λ)f (x2 ) ≥ f (x0 ) + hf 0 (x0 ), λx1 + (1 − λ)x2 − x0 i + +ϑ(λkx1 − x0 k2 + (1 − λ)kx2 − x0 k2 ).
Odtud po úpravě f (x0 ) = f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ) − λ(1 − λ)ϑkx1 − x2 k2 , tedy f je silně konvexní s konstantou ϑ. Poznámka 3.16. (i) Je-li funkce f diferencovatelná v bodě x ∗ , pak tečná nadrovina ke grafu funce f v bodě [x∗ , f (x∗ )] má tvar z − f (x∗ ) = hf 0 (x∗ ), x − x∗ i, vztah (3.8) tedy znamená (pro ϑ = 0), že graf konvexní funkce leží nad tečnou nadrovinou sestrojenou v libovolném bodě grafu. (ii) Předpokládejme, že bod x∗ je stacionárním bodem funkce f , tj. 0 f (x∗ ) = 0. Pak vztah (3.8) říká, že graf funkce f leží uvnitř rotačního paraboloidu s vrcholem v bodě [x∗ , f (x∗ )], který je zadán rovnicí z = f (x∗ ) + ϑkx − x∗ k2 . Věta 3.17. Nechť X ⊂ Rn je konvexní, funkce f : X → R je silně konvexní na X s konstantou ϑ ≥ 0 právě tehdy, když hf 0 (x) − f 0 (x∗ ), x − x∗ i ≥ 2ϑkx − x∗ k2 pro každé x, x∗ ∈ X. Důkaz. ⇒: Podle předchozí věty platí f (x) − f (x∗ ) ≥ hf 0 (x∗ ), x − x∗ i + ϑkx − x∗ k2 , f (x∗ ) − f (x) ≥ hf 0 (x), x∗ − xi + ϑkx − x∗ k2
a sečtením těchto nerovností dostáváme nerovnost (3.9). 34
(3.9)
⇐: Nechť platí (3.9), pak f (x)−f (x∗ ) − hf 0 (x∗ ), x − x∗ i = Z 1 = hf 0 (x∗ ) + α(x − x∗ )), x − x∗ idα − hf 0 (x∗ ), x − x∗ i = 0 Z 1 1 0 ∗ hf (x + α(x − x∗ )) − f 0 (x∗ ), α(x − x∗ )idα ≥ = α 0 Z 1 Z 2ϑ 1 ∗ 2 ∗ 2 α dα = kα(x − x k dα = 2ϑkx − x k ≥ α 0 0 =2ϑkx − x∗ k2 , tedy je f silně konvexní podle Věty 3.15. Věta 3.18. Nechť X ⊂ Rn je konvexní, int X 6= ∅, f : X → R a matice druhých derivací f 00 je spojitá na X. Pak f je silně konvexní na X s konstantou ϑ ≥ 0 právě tehdy, když hf 00 (x)h, hi ≥ 2ϑkhk2
(3.10)
pro všechna x ∈ X a všechna h ∈ Rn . Důkaz. ⇒: Nechť x∗ ∈ int X je libovolné, tj. x = x∗ + αh ∈ X pro α > 0 dostatečně malá a h ∈ Rn je rovněž libovolné. Ze skutečnosti, že f má spojité druhé parciální derivace plyne, že f (x) = f (x∗ ) + αhf 0 (x∗ ), hi +
α2 00 ∗ hf (x )h, hi + o(α2 ), 2
odtud 1 1 00 ∗ hf (x )h, hi + o(α2 ) = 2 [f (x) − f (x∗ ) − hf 0 (x∗ ), αhi] ≥ θkhk2 , 2 α poslední nerovnost plyne z (3.8). Limitním přechodem pro α → 0 dostáváme (3.10). Je-li, x∗ ∈ X, x∗ 6∈ int X, pak existuje posloupnost xk ∈ int X, xk → x∗ . Podle předchozího hf 00 (xk )h, hi ≥ 2ϑkhk2 , pro každé h ∈ Rn a spojitost f 00 implikuje, že tato nerovnost platí i pro hraniční body x ∗ ∈ ∂X. ⇐: Nechť x, x∗ ∈ X jsou libovolné, h = x − x∗ , pak z Taylorova vzorce druhého stupně dostáváme 1 f (x) − f (x∗ ) = hf 0 (x∗ ), x − x∗ i + hf 00 (x∗ + α ¯ h)h, hi ≥ 2 ≥ hf 0 (x∗ ), x − x∗ i + ϑkx − x∗ k2 , tedy podle Věty 3.15. je f silně konvexní s konstantou ϑ ≥ 0. 35
Poznámka 3.19. (i) Na základě předchozí věty můžeme zdůvodnit výrok z části (ii) Poznámky 3.2. Funkce f (x) = kxk 4 = hx, xi2 není silně konvexní na Rn , neboť f 00 (x) = 12x · xT (zde x chápeme jako sloupcový vektor a xT je jeho transpozice), tj. f 00 (0) = 0. Naopak, funkce f (x) = kxk2 je silně konvexní s konstantou ϑ = 1, neboť f 00 (x) = 2I, kde I značí jednotkovou matici. (ii) Nechť A je symetrická matice, nejmenší vlastní číslo matice A označme λ1 (A). Pro toto vlastní číslo platí vyjádření λ1 (A) = min h6=0
hAh, hi , khk2
viz např. [6] Tedy podle předchozí věty je funkce f na množině X silně konvexní s konstantou ϑ ≥ 0, právě když pro nejmenší valstní hodnotu matice druhých derivací platí λ(f 00 (x)) ≥ 2ϑ pro každé x ∈ X. (iii) Každá z podmínek (3.8), (3.9), (3.10), ve které položíme θ = 0 a neostrou nerovnost nahradíme ostrou nerovností, je postačující pro ostrou konvexnost funkce f na X. Dokážeme platnost tohoto výroku například pro podnínku (3.8) (ve zbývajících dvou případech je důkaz analogický). Předpokládejme tedy, že f (x) − f (x0 ) > hf 0 (x0 ), (x − x0 )i
(3.11)
pro libovolná x, x0 ∈ X. Nechť x1 , x2 ∈ X, x1 6= x2 a λ ∈ (0, 1) jsou libovolná. Podobně jako v důkazu Věty 3.15 Položme x 0 = λx1 + (1 − λ)x2 Příklad 3.20. Rozhodněte o (ostré, silné) konvexnosti následujících funkcí: (i) f (x) = hAx, xi + hb, xi, x ∈ Rn , A je symetrická n × n matice, n (ii) f (x) = ||x||, p x∈R , 2 (iii) f (x) = 1 + ||x|| , a) x ∈ Rn , b) kxk≤ 1.
Řešení. (i) Přímým výpočtem dostáváme f 0 (x) = 2Ax + b,
f 00 (x) = 2A
(pro derivování skalárního resp. maticového součinu platí stejná pravidla jako pro derivování ”normálního” součinu). Tedy f je konvexní právě když A je pozitivně semidefinitní a je silně konvexní právě když je pozitivně definitní (hlavní minory jsou kladné). V tomto případě je (největší) konstantou silné konvexity ϑ = 21 λ1 (A), kde λ1 (A) je nejmenší vlastní hodnota matice A. (ii) Nechť x, y ∈ Rn jsou libovolná. Pak využitím Cauchyovy nerovnosti dostáváme ||x + y||2 = hx − y, x − yi = ||x||2 + 2hx, yi + ||y||2
≤ ||x||2 + 2||x|| ||y|| + ||y||2 = (kxk + kyk)2 , 36
přičemž je-li y = tx pro t ≥ 0, platí v předchozím vztahu rovnost. Odtud pro libovolné λ ∈ [0, 1] platí kλx + (1 − λ)yk ≤ kλx| + k(1 − λ)yk = λkxk + (1 − λ)ky| tedy norma je konvexní funkce na Rn . Tato funkce není ostře konvexní, neboť pro y = tx, t ≥ 0 dostáváme v předchozím vztahu rovnost. (iii) Dosadíme-li kxk2 = hx, xi a využijeme-li pravidel pro derivaci skalárního součinu, dostáváme (I zde značí jednotkovou matici) 1 f 0 (x) = p · x, 1 + hx, xi
a pro matici druhých derivací f 00 (x) =
1 1 I+ xxT . (1 + hx, xi) (1 + hx, xi)3/2
Označme A = hx, xiI − xxT . Pak pro každé h ∈ Rn (využitím Cauchyovy nerovnosti) hAh, hi = khk2 kxk2 − hh, xi2 ≥ khk2 kxk2 − khk2 kxk2 = 0, tedy matice A je pozitivně semidefinitní. To znamená, že matice I + A je pozitivně definitní a její nejmenší vlastní hodnota. Celkem tedy funkce f je konvexní v připadě a) i b). Pokud jde o silnou konvexnost, když kxk → ∞, pak 1 →0 λ1 [f 00 (x)] = (1 + kxk2 )3/2
a tedy funkce f není silně konvexní na R n . V případě b) pro každě x, pro 1 něž kxk ≤ 1, je (1 + kxk2 )−3/2 ≥ 2√ , a tedy f je na dané množině silně 2
1 konvexní s (maximální) konstantou silné konvexity θ = 4√ . λ1 (I + A) = 1. 2 Pokud nepotřebujeme určit konstantu silné konvexity explicitně, můžeme použít v případě b) (nebo obecněji, v případě jakékoliv kompaktní konvexní množiny) následuící úvahu: Protože matice druhých derivací f 00 (x) je pozitivně definitní, jej její nejmenší vlastní hodnota λ 1 [f 00 (x)] > 0 na X. Protože množina X je kompaktní, je i inf x∈X λ1 [f 00 (x)] > 0 a tedy f je silně konvexní na X. N
3.3
Spojitost a směrová derivace konvexních funkcí
V tomto odstavci si ukážeme, že konvexnost funkce implikuje řadu „pěknýchÿ vlastností. 37
Věta 3.21. Nechť X ⊆ Rn je konvexní, funkce f : X → R je konvexní na X. Pak f je spojitá v každém relativně vnitřním bodě množiny X. Důkaz. Nechť x∗ ∈ ri X je libovolné. Místo funkce f uvažme funkci F (x) = f (x∗ − x) − f (x∗ ), která je spojitá v bodě x = 0 právě tehdy, když f je spojitá v x = x∗ . Nejprve předpokládejme, že int X 6= ∅. Označme Kr = {x = (x1 , . . . , xn ∈ Rn : |xi − x0i | < r, kde x∗ = (x∗1 , . . . , x∗n )}, kde r > 0 je takové, že Kr ⊂ X a označme dále x1 , . . . , xm , m = 2n vrcholy krychle Kr . Položme α = max F (xi ). 1≤i≤m
Každý bod y ∈ Kr lze vyjádřit bodů x 1 , . . . , xm , P jako konvexní kombinaci Pm tj. existují λi ≥ 0 taková, že m λ = 1 a y = λ x i i i . Z konvexnosti i=1 i=1 funkce F plyne ! m m X X λi F (xi ) ≤ α. λi xi ≤ F (x) = F i=1
i=1
Pro libovolné ε > 0 označme Kε = εKr . Pro každé x ∈ Kε platí x ε x + (1 − ε) · 0 ≤ εF F (x) = F + (1 − ε)F (0) ≤ αε, ε ε
a odtud
0 = F (0) = F
1 ε x+ 1+ε 1+ε
−x ε
≤
ε 1 F (x) + α, 1+ε 1+ε
(3.12)
(3.13)
odtud F (x) ≥ −αε, což spolu s první nerovností dává |F (x) − F (0)| < αε, což znamená, že F je spojitá v bodě x = 0. Jestliže ri X 6= int X, uvažovali bychom v našem postupu místo krychle dimenze n krychli dimenze stejné, jako je dimenze množiny X. Poznámka 3.22. Všimněmě si, že tvrzení neplatí pro relativně hraniční body. Stačí totiž uvažovat množinu X = [−1, 1] a funkce definovanou předpisem ( 0 pro x ∈ (−1, 1), f (x) = 1 pro x = ±1.
Nyní připomeňme pojem směrové derivace. Nechť f : R n → R, x∗ ∈ Rn a h ∈ Rn . Pokud existuje limita f (x∗ + th) − f (x∗ ) , t→0+ t lim
tuto limitu nazýváme jednostrannou směrovou derivací funkce f v bodě x ∗ a směru h a značíme f 0 (x∗ , h). Následující věta říká, že konvexní funkce má v každém relativně vnitřním bodě směrovou derivaci. 38
Věta 3.23. Nechť X ⊆ Rn je konvexní, f : X → R je konvexní a x∗ ∈ ri X. Pak existuje f 0 (x∗ , h) a je konečná pro všechna h ∈ Lin X. Důkaz. Je-li x∗ ∈ ri X libovolný bod a h je libovolný bod lineárního obalu množiny X, je x∗ + th ∈ X, je-li |t| dostatečně malé. Označme nyní φ(t) = 1 ∗ ∗ t [f (x + th) − f (x )]. Ukážeme, že φ je neklesající a zdola ohraničená na (0, δ), kde δ > 0 je dostatečně malé. Nechť t 1 , t2 ∈ (0, δ) jsou libovolná. Platí t1 ∗ t1 ∗ ∗ f (x + t1 h) = f (1 − )x + (x + th) t2 t2 t1 t1 f (x∗ ) + f (x∗ + t2 h), ≤ 1− t2 t2 tedy
f (x∗ + t1 h) − f (x0 ) f (x∗ + t2 h) − f (x0 ) ≤ , t1 t2 tj. φ(t1 ) ≤ φ(t2 ). K důkazu ohraničenosti funkce φ vezměme t 0 ∈ (−δ, 0), takové, že x∗ + t0 h ∈ X. Pak pro t ∈ (0, δ) platí −t t (x∗ + t0 h) + (x∗ + th) ≤ f (x∗ ) = f t − t0 t − t0 t t ≤ f (x∗ + t0 h) − f (x∗ + th), t − t0 t − t0 odtud úpravou
f (x∗ + t0 h) − f (x∗ ) f (x∗ + th) − f (x∗ ) ≤ , t0 t tj. φ(t0 ) ≤ φ(t). Dokázali jsme, že funkce φ je na intervalu (0, δ) neklesající a zdola ohraničená, existuje tedy konečná lim t→0+ φ(t) = f 0 (x∗ , h). Poznámka 3.24. (i) Stejný příklad jako za Větou 3.21 ukazuje, že tvrzení obecně neplatí pro relativně hraniční body. (ii) Podobně jako v důkazu předchozí věty lze ukázat, že funkce ϕ je neklesající a shora ohraničená na intervalu (−δ, 0) a pro t > 0 dostatečně malá platí φ(−t) ≤ φ(t) a tedy i φ(0−) ≤ φ(0+). Ve Větě 3.21 jsme dokázali, že konvexní funkce je spojitá v každém relativně vnitřním bode množiny X. Následující tvrzení (uvádíme jej bez důkazu, ten lze nalezt např. v [21]) ukazuje další zajímavou vlastnost konvexních funkcí. Věta 3.25. Nechť X ⊆ Rn je konvexní a f : X → R je konvexní. Pak ke každé kompaktní podmnožině K ⊂ ri X existuje konstanta L K taková, že f je Lipschitzovská na K s konstantou L K , tj. platí |f (x) − f (y)| ≤ LK kx − yk ∀x, y ∈ K. 39
3.4
Další vlastnosti konvexních funkcí
V tomto odstavci si uvedeme některé další vlastnosti konvexních funkcí, které budeme potřebovat v pozdějším výkladu. První z nich je jednoduchým, ale z hlediska aplikací důležitým důsledkem věty o oddělování konvexních množin. Věta 3.26. Nechť X, Y ⊂ Rn jsou konvexní, ri X ∩ ri Y je neprázdná, f : X → R, g : X → R, f je konvexní, g je konkávní a f (x) ≥ g(x) pro všechna x ∈ ri X ∩ ri Y . Pak existuje afinní funkce l(x) = ha, xi + b taková, že pro každé x ∈ X a y ∈ Y f (x) ≥ l(x),
∀x ∈ X a
l(y) ≥ g(y)
∀y ∈ Y.
(3.14)
˜ = epi f, Y˜ = {(x, α), g(x) ≤ α, x ∈ X}, tj. Y˜ je podgraf g. Pak Důkaz. Nechť X ˜ Y˜ jsou konvexní a podle předpokladů vlastně oddělitelné. Existuje tedy (p, λ) ∈ X, Rn+1 tak, že ˜ (y, γ) ∈ Y˜ , h(x, β), (p, λ)i ≥ h(y, γ), (p, λ)i ∀(x, β) ∈ X, (3.15) ˜ (˜ přičemž existují (˜ x, β), y , γ˜ ) ∈ Rn+1 tak, že pro tyto body platí ostrá nerovnost v (3.15), tedy existuje δ tak, že hp, xi + λβ ≥ δ ≥ hp, yi + λγ.
(3.16)
Je-li λ = 0, X a Y jsou vlastně oddělitelné, což je spor, neboť ri X∩ri Y je neprázdný. Je-li λ < 0 pak pro β → ∞, resp. γ → −∞ dostáváme opět spor, tedy λ > 0. Vydělením nerovnosti (3.16) λ dostáváme hp/λ, xi+β ≥ δ/λ ≥ hp/λ, yi+γ. Položme a = −p/λ, b = δ/λ. Pak l(x) = ha, xi + b je hledanou afinní funkcí splňující obě nerovnosti v (3.14). Věta 3.27. Nechť X ⊆ Rn je konvexní, f je spojitá a silně konvexní na X s ϑ > 0. Pak pro každé α ∈ R je množina Xα = {x ∈ X : f (x) ≤ α} omezená. Důkaz. Nechť α ∈ R je takové, že Xα je neprázdná a nechť x∗ ∈ Xα je libovolné. Označme U = B1 (x∗ ) ∩ X, kde B1 (x∗ ) značí kouli se středem v bodě x∗ a poloměru 1. Označme m = inf x∈U f (x), které existuje, neboť f je spojitá na kompaktní množině U . Ukážeme, že pro každé x ∈ Xα platí kx − x∗ k ≤ 1 + α−m ϑ . Je-li x ∈ U , pak odhad platí. Nechť x ∈ Xα \ U . Označme λ = 1/kx − x∗ k, x ¯ = λx + (1 − λ)x∗ , pak x¯ ∈ B1 (x∗ ) a platí (dosazením za λ) m ≤ f (x) ≤ λf (x) + (1 − λ)f (x∗ ) − ϑλ(1 − λ)kx − x∗ k2 ≤ 1 ϑ 1− kx − x∗ k2 , ≤α− kx − x∗ k kx − x∗ k a tedy 1 +
α−m ϑ
≥ kx − x∗ k.
Předpoklad silné konvexnosti ve větě nelze nahradit slabším předpokladem ostré konvexnosti. Například volbou f (x) = ex , α > 0, pak Xα je neohraničená, neboť ex není silně konvexní. Platí však toto zobecnění Věty 3.27, jehož důkaz lze nalézt např v [22, str. 97]. Věta 3.28. Nechť X ⊂ Rn konvexní, f : X → R je spojitá a konvexní a předpokládejme, že existuje α ∈ R tak, že Xα je neprázdná a ohraničená. Pak Xα je ohraničená pro každé α ∈ R.
40
3.5
Subgradient a subdiferenciál
V tomto odstavci zavedeme pojmy subgradientu a subdiferenciálu funkce, které nalézají uplatnění především v tzv. nehladkých optimalizačních úlohách, tj. úlohách, kde minimalizovaná funkce není diferencovatelná. Definice 3.29. Nechť X ⊆ Rn je konvexní, f : X → R, x∗ ∈ X. Vektor a ∈ Rn se nazývá subgradient funkce f v bodě x∗ , jestliže f (x) − f (x∗ ) ≥ ha, x − x∗ i pro každé x ∈ X.
(3.17)
Množina všech subgradientů funkce f v bodě x∗ se nazývá subdiferenciál f v bodě x∗ a značí se ∂f (x∗ ). Poznámka 3.30. (i) Nechť f : X → R, x∗ ∈ ri X. Podle Věty 3.23 a Poznámky 0 0 0 0 3.24 existují f− (x∗ ) a f+ (x∗ ) a je-li f konvexní, je f− (x∗ ) ≤ f+ (x∗ ). Není obtížné ∗ 0 ∗ 0 ∗ ověřit, že v tomto případě ∂f (x ) = [f− (x ), f+ (x )]. (ii) Nadrovina Hp,α v Rn+1 , kde p = (a, 1) ∈ Rn+1 , α = f (x∗ ) − ha, x∗ i, je opěrná nadrovina k nadgrafu f v bodě (x∗ , f (x∗ )). Věta 3.31. Nechť X ⊆ Rn je konvexní, f : X → R. (i) Je-li f konvexní a x∗ ∈ riX. Pak ∂f (x∗ ) je neprázdná, uzavřená a konvexní množina. (ii) Je-li ∂f (x) neprázdná pro každé x ∈ X, pak f je konvexní na X. Důkaz. (i) Nechť x∗ ∈ ri X, Y = {x∗ }, g : Y → R, g(y) = f (x∗ ) (konstantní funkce). Pak ri X ∩ ri Y = {x∗ } a platí f (x) ≥ g(x) pro x ∈ ri X ∩ ri Y . Protože funkce f je konvexní na X, g je konkávní na Y , podle Věty 3.26 existuje afinní funkce l(x) = ha, xi + b tak, že f (x) ≥ l(x) pro všechna x ∈ X a l(y) ≥ g(y) pro všechna y ∈ Y . Tedy ha, x∗ i + b ≥ f (x∗ ). Sečtením poslední nerovnosti s nerovností f (x) ≤ l(x) dostáváme f (x) − f (x∗ ) ≥ ha, x − x∗ i, tedy a ∈ ∂f (x∗ ). (ii) Nechť x1 , x2 ∈ X, λ ∈ [0, 1], x¯ = λx1 + (1 − λ)x2 ∈ X. Podle předpokladu existuje a ∈ ∂f (¯ x), tj. f (x1 ) − f (¯ x) f (x2 ) − f (¯ x)
≥ ha, x1 − x ¯i, ≥ ha, x2 − x ¯i.
Vynásobením první rovnice λ, druhé 1 − λ a sečtením tako vzniklých nerovností dostáváme f (¯ x) ≤ λf (x1 ) + (1 − λ)f (x2 ),
a tedy f je konvexní.
Následující věta popisuje jistý extremální vztah mezi směrovou derivací konvexní funce a jejím subdiferenciálem. Toto tvrzení lze chápat jako zobecnění tvrzení z Poznámky 3.30 část (i). Věta 3.32. Nechť X ⊂ Rn je konvexní, f : X → R je konvexní a x0 ∈ ri X. Pak platí ∂f (x0 ) = {a ∈ Rn : ha, hi ≤ f 0 (x0 , h)∀h ∈ Lin X}, (3.18)
a
f 0 (x0 , h) = max{ha, hi. a ∈ ∂f (x0 )}
41
pro všechna h ∈ Lin X.
(3.19)
Důkaz. Máme dokázat množinovou rovnost, to znamená dokázat dvojici inkluzí. Označme A množinu stojící na pravé straně rovnosti (3.18). ⊆: Nechť a ∈ ∂f (x0 ). Protože x0 ∈ ri X, je x0 + th ∈ X pro každé h ∈ Lin X a t > 0 dostatečně malá, platí f (x0 + th) − f (x0 ) ≥ ha, thi. Po vydělení t a limitním přechodem pro t → 0 výjde f 0 (x0 , h) ≥ ha, hi, tj. a ∈ A. ⊇: Nechť a ∈ A a x ∈ X jsou libovolná. Označme h = x − x0 . Pak platí f (x) − f (x0 ) =
f (x0 + h) − f (x0 ) ≥ f 0 (x0 , h) ≥ ha, hi = ha, x − x0 i, 1
tedy a ∈ ∂f (x0 ). K důkazu rovnosti (3.19) stačí najít a ˜ ∈ ∂f (x0 ) tak, aby h˜ a, hi ≥ f 0 (x0 , h). Nechť h ∈ Lin X je libovolný, označme Y = {x ∈ Rn : x = x0 + th, t > 0}. Definujme g : Y → R takto g(x) = f (x0 ) +
kx − x0 k 0 f (x0 , h). khk
Pro x = x0 + th je g(x) = f (x0 ) + tf 0 (x0 , h) a g je afinní na Y , tedy i konkávní, navíc |x − x0 | 0 f (x) ≥ g(x) = f (x0 ) + f (x0 , h) |h| pro každé x ∈ ri X ∩ ri Y . Chceme, aby f (x0 + th) ≥ f (x0 ) + tf 0 (x0 , h), tj. f (x0 + th) − f (x0 ) ≥ f 0 (x0 , h). t Podle Věty 3.32 existuje lineární funkce l(x) = h˜ a, xi + b, taková, že a f (x) ≥ h˜ a, xi + b pro všechna x ∈ X a g(y) ≤ h˜ a, yi + b pro všechna y ∈ Y . Tedy f (x0 ) + tf 0 (x0 , h) ≤ h˜ a, x0 + thi + ba
f (x) − f (x0 ) − tf 0 (x0 , h) ≥ h˜ a, x − x0 i − th˜ a, hi, 0 f (x) − f (x0 ) − h˜ a, x − x0 i ≥ t(f (x0 , h) − h˜ a, hi). Tedy, je-li t = 0, pak a ˜ ∈ ∂f (x0 ). Pokud t → ∞, pak h˜ a, hi ≥ f 0 (x0 , h). Věta 3.33. Nechť X ⊆ Rn je konvexní, f : X → R je konvexní a x0 ∈ int X. (i) Je-li f diferencovatelná v x0 , pak je ∂f (x0 ) jednoprvková a ∂f (x0 ) = {f 0 (x0 )}. (ii) Je-li ∂f (x0 ) = {a} jednoprvková, pak je funkce f diferencovatelná v bodě x 0 a f 0 (x0 ) = a.
42
Důkaz. (i) Nejprve z x0 ∈ int X plyne, že Lin X = Rn . Podle Věty 3.15 je f 0 (x0 ) ∈ ∂f (x0 ). Nechť a ∈ ∂f (x0 ). Z diferencovatelnosti funkce f plyne, že f 0 (x0 , h) = hf 0 (x0 ), hi a podle 3.19 je ha, hi ≤ f 0 (x0 , h) = hf 0 (x0 ), hi. Pro každé h ∈ Lin X je hf 0 (x0 ) − a, hi ≥ 0 a dosazením h = a − f 0 (x0 ) dostáváme kf 0 (x0 ) − ak2 ≤ 0, tj. a = f 0 (x0 ). (ii) Nechť ∂f (x0 ) = {a}. Uvažme funkci φ(t, h) =
f (x0 + th) − f (x0 ) − ha, hi − ha, hi. t
Pak 0 ≤ φ(t, h) a limt→0 φ(t, h) = 0 lokálně stejnoměrně na Rn (vzhledem k h), 0 ≤ φ(t, h) ≤ ε. Je-li t > 0 dostatečně malé a khk dostatečně malé, pak 0≤
f (x0 + h) − f (x0 ) − ha, hi ≤ ε. khk
Příklad 3.34. (i) Určete ∂f (0, 0) pro funkci f (x1 , x2 ) = načrtněte v rovině.
p
x21 + 2x22 , tuto množinu
Řešení. Vektor a = (α, β) ∈ ∂f (0, 0) právě když q x21 + 2x22 ≥ αx1 + βx2 ∀[x1 , x2 ] ∈ R2 .
Vzhledem k tomu, že levás strana poslední nerovnosti se nezmění, jestliže nahradíme x1 , x2 opačnými čísly −x1 , −x2 , můžeme nerovnost umocnit a dostáváme x21 + x22 − α2 x21 − 2αβx1 x2 − β 2 x22 ≥ 0. Levá strana posledního výrazu je kvadratická forma s maticí 1 − α2 αβ αβ 2 − β2.
Minory této matice jsou ∆1 = 1 − α2 , ∆2 = 2 − 2α2 − β 2 . Tato forma je pozitivně 2 semidefinitní právě když ∆1 ≥ 0, ∆2 ≥ 0 a to nastane právě když |α| ≤ 1, α2 + β2 ≤ √ 1. Druhá nerovnost popisuje vnitřek a hranici elipsy s polosami 1 pro α a 2 pro β. Protože tato množina je obsažena v pásu |α| ≤ 1, je ∂f (0, 0) = {[α, β] ∈ R2 | α2 +
β2 ≤ 1}. 2 N
(ii) Pro x ∈ Rn a funkci f (x) = kxk =
p
hx, xi určete ∂f (0).
Řešení. Podle definice, a ∈ ∂f (0), právě když kxk ≥ ha, xi pro každé x ∈ Rn . Protože pravá strana nerovnosti nabývá největší hodnoty mezi jednotkovými vektory a pro x = kak (Cauchyova nerovnost se změní v rovnost pro skalární součin souhlasně
43
lineárně závislých vektorů), dostáváme nerovnost kak ≥ ha, ai = kak 2 (všimněte si, že stačí se omezit na jednotkové vektory, protože nerovnost zůstává zachována při záměně x 7−→ tx, kde t ≥ 0). Tato nerovnost je splněna právě když kak ≤ 1, tedy ∂f (0) = {a ∈ Rn | kak ≤ 1}. N Na závěr tohoto odstavce uveďme dvě tvrzení umožňující požítat subdiferenciál funkcí v konkrétních příkladech. Jejich důkaz, který je založen na vlastnostech víceznačných zobrazení je možno nalézt v [22]. Věta 3.35. Nechť f1 , . . . , fm : X → R jsou konvexní, X ⊂ Rn je konvexní a α1 , . . . , αm ≥ 0 a x ∈ int X. Pak ∂(α1 f1 (x) + · · · + αm f (xm ))(x) = α1 ∂f1 (x) + · · · + αm ∂fm (x). Věta 3.36. Nechť platí předpoklady Věty 3.35. Pak [ ∂ max fi (x) = conv ( ∂fi (x)), i=1,...,m
j∈I(x)
kde I(x) = {i ∈ {1, . . . , m} : fi (x) = maxi f( x)}.
3.6
Fenchelova transformace
V tomto odstavci popíšeme základní vlastnosti jisté transformace, která funkci f : Rn → R přiřadí (konvexní) funkci f ∗ : Rn → R, tzv. konjugovanou funkci (někdy se použivá pojem Fenchelova transformace nebo Legendreova transformace funkce f ). Tato transformace je velmi účinným nástrojem při studiu extremálních úloh, jak ukážeme v závěru následující kapitoly. Definice 3.37. Nechť f : Rn → R. Funkce f ∗ (y) = sup [hx, yi − f (x)] x∈Rn
(3.20)
se nazývá Fenchelovou transformací nebo také konjugovanou funkcí funkce f. Poznámka 3.38. (i) Je-li funkce f diferencovatelná a pro dané y je supremum v (3.20) menší než ∞, nutnou podmínkou pro extrém je ∂ [hx, yi − f (x)] = 0, ∂x tj. y = f 0 (x). Je-li stacionární bod x∗ funkce [hx, yi − f (x)] i bodem maxima této funkce (to nastane např. v případě, kdy f je konvexní), pak f ∗ (y) = hx∗ , yi−f (x∗ ), kde y = f 0 (x). V tomto tvaru je Fenchelova transformace známa pod názvem Legendreova transformace, viz. např. [2, kap. 10]. 44
Existuje-li navíc k funkci f 0 : Rn → Rn inverzní funkce (f 0 )−1 a funkce f je konvexní, pak platí f ∗ (y) = hy, (f 0 )−1 (y)i − f ((f 0 )−1 (y)). (ii) V definici konjugované funkce pomocí vztahu (3.20) předpokládáme, že funkce f je definována na celém Rn . V případě, že Dom f ⊂ Rn , dodefinujme f (x) = ∞ pro x ∈ Rn \Dom f . Ze vztahu (3.20) je pak zřejmé, že pro takto rozšířenou funkci f je f ∗ stejné jako když se v (3.20) supremum bere pouze přes množinu X. Příklad 3.39. (i) Nechť n = 1, f (x) = (f ∗ )∗ .
|x|p p ,
p > 1. Vypočtěte f ∗ a f ∗∗ =
p
Řešení. Protože funkce xy − |x|p je silně konkávní vzhledem k proměnné x, stačí najít stacionární bod této funkce. Je-li |x|p d xy − = y − |x|p−1 sgn x = 0, dx p 1
pak y = |x|p−1 sgn x a tedy x = |y| p−1 sgn y, tj. p
∗
f (y) = y · |y|
1 p−1
p |y| p−1 sgn y − = |y| p−1 p
kde q je konjugovaný exponent k p, tj. p1 + konjugovaná vzájemně, platí f ∗∗ (x) = f (x).
1 q
1 1− p
=
|y|q , q
= 1. Protože čísla p, q jsou N
(ii) Nechť f (x) = ex . Vypoctěte f ∗ a f ∗∗ . Řešení. Funkce xy − ex je konkávní, opět tedy stačí najít její stacionární bod. Přímým derovováním zjistíme, že stacionární bod existuje pouze pro y > 0 a snadnou úvahou dojdeme k výsledku y ln y pro y > 0, 0 pro y = 0, f ∗ (y) = sup(xy − ex ) = x∈R ∞ pro y < 0. Vypočtěme ještě f ∗∗ . Podle části (ii) předchozí poznámky je
f ∗∗ = sup [xy − f ∗ (y)] = xex − ex (x − 1) = ex , y∈(0,∞)
neboť
d dy [xy
− y(ln y − 1)] = x − ln y = 0 implikuje y = e x .
N
Všimněme si, že v obou předchozích příkladech platilo f = f ∗∗ . Nyní budeme směřovat k tvrzení, které ukazuje, že tento vztah není náhodný. Nejprve však dokažme některé vcelku jednoduché vlastnosti Fenchelovy transformace. Lemma 3.40. Platí následující tvrzení. 45
(i) Funkce f ∗ je konvexní na množině Y = {y ∈ Rn : f ∗ (y) < ∞}. (ii) Pro každé x, y ∈ Rn platí tzv. Fenchelova rovnost f ∗ (y) + f (x) ≥ hx, yi.
(3.21)
(iii) Je-li f (x) ≥ g(x) na Rn , pak f ∗ (y) ≤ g ∗ (y) pro y ∈ Dom f ∗ ∩ Dom g ∗ .
Důkaz. Tvrzení (i) plyne z Věty 3.7, neboť funkce hx, yi − f (x) je afinní a tedy i konvexní funkcí proměnné y (za indexovou množinu I z Věty 3.7 bereme X). Tvrzení (ii) a (iii) plynou přímo z definice. Lemma 3.41. Nechť f ∗ je konjugovaná k f . Pak platí (i) Pro každé 0 6= α ∈ R y (αf )∗ (y) = αf ∗ ( ); α (ii) Pro každé c ∈ R (f + c)∗ (y) = f ∗ (y) − c; (iii) Je-li g(x) = ha, xi, a ∈ Rn , pak
(f + g)∗ (y) = f ∗ (y − a).
Důkaz. Všechna tvrzení plynou jednoduchým výpočtem přímo z definice. Poznámka 3.42. Aplikujeme-li Fenchelovu nerovnost (3.23) na dvojici p q funkcí f (x) = |x|p , g(x) = |x|q , kde 1p + 1q = 1 dostáváme tzv. Youngovu nerovnost |x|p |x|q xy ≤ + . p q Lemma 3.43. Nechť g(x) = ha, xi−β, a ∈ R n , β ∈ R, X ⊂ Rn je konvexní, f : X → R. Pak f (x) ≥ g(x) pro každé x ∈ X, právě když (a, β) ∈ epi f ∗ . Důkaz. Platí následující řetězec ekvivalencí. (a, β) ∈ epi f ∗
⇐⇒
⇐⇒
β ≥ f ∗ (a) ⇐⇒ β ≥ ha, xi − f (x)
f (x) ≥ ha, xi − β
pro ∀x ∈ X
pro ∀x ∈ X
což dokazuje požadované tvrzení. Klíčovým tvrzením při důkazu Fenchelovy rovnosti f ∗∗ = f je následující věta (nakreslete si obrázek ilustrující její tvrzení). Věta 3.44. Nechť X ⊂ Rn je konvexní, f : X → R je konvexní a x∗ ∈ X. Je-li funkce f spojitá v bodě x∗ , platí f (x∗ ) = sup{ha, x∗ i − α : (a, α) ∈ Rn+1 , ha, xi − α ≤ f (x) pro ∀x ∈ X}, (3.22) tj. f (x) je v bodech spojitosti obálkou všech afinních funkcí, které jsou na X funkcí f majorizovány. 46
Důkaz. Označme A množinu stojící na pravé straně (3.22). Dosazením x = x∗ dostáváme ha, x∗ i ≤ f (x∗ ), tj. sup A ≤ f (x∗ ). K důkazu (3.22) tedy stačí ukázat, že ke každému ε > 0 existuje (a, α) ∈ R n+1 takové, že ha, xi − α ≤ f (x) na X a ha, x∗ i − α ≥ f (x∗ ) − ε. Protože funkce f je spojitá v bodě x∗ , ke každému ε > 0 existuje δ > 0 takové, že f (x) ≥ f (x ∗ ) − ε pro x ∈ (x∗ − δ, x∗ + δ). Nyní uvažujme množiny X = epi f,
Y = [x∗ − δ, x∗ + δ] × (−∞, f (x∗ ) − ε].
Tyto množiny jsou vlastně oddělitelné, tj. existuje (p, λ) ∈ R n+1 takové, že h(x, α), (p, λ)i ≥ γ ≥ h(y, β), (p, λ)i pro každé (x, α) ∈ X, (y, β) ∈ Y . Podobně jako ve Větě 3.26 lze ukázat, že λ > 0 a tedy γ h(p/λ), xi + α ≥ ≥ h(p/λ), yi + β. λ Označme a = −p/λ, α = −γ/λ. Protože [x ∗ , f (x∗ ) − ε] ∈ Y , [x, f (x)] ∈ X, znamená poslední nerovnost, že γ h−a, xi + f (x) ≥ ≥ h−a, xi + f (x∗ ) − ε, λ tj. f (x) ≥ ha, xi − p/λ pro každé x ∈ X a ha, x ∗ i − α > c. Protože ε > 0 bylo libovolné, dostáváme požadovanou nerovnost. Poznámka 3.45. Všimněme si, že předpoklad spojitosti funkce f v bodě x∗ lze nahradit slabším předpokladem, že funkce f je v bodě x ∗ zdola polospojitá, tj. lim inf f (x∗ ) ≥ f (x∗ ), ∗ x→x
což znamená, že ke každému ε > 0 existuje δ > 0 tak, že pro všechna x ∈ (x∗ − δ, x∗ + δ) je f (x) > f (x∗ ) − ε. Připomeňme také, že reálná funkce je zdola polospojitá v každém bodě uzavřeného intervalu [a, b], právě když její nadgraf na tomto intervalu je uzavřená množina. Věta 3.46. (Fenchelova věta). Nechť X ⊂ R n je konvexní, f : X → R je konvexní. Pak v každém bodě spojitosti f platí tzv. Fenchelova rovnost f ∗∗ (x) = f (x).
(3.23)
Důkaz. Podle předchozího tvrzení f (x∗ ) = sup{ha, x∗ i − α| (a, α) ∈ Rn+1 , f (x) ≥ ha, xi−α pro ∀x ∈ X} = = sup{ha, x∗ i − α| (a, α) ∈ epi f } =
= sup{ha, x∗ i − α| a ∈ D(f ∗ ), a ≥ f ∗ (a)} = =
sup {ha, x∗ i − f ∗ (a)} = f ∗∗ (x∗ ).
a∈D(f ∗ )
47
Nyní využijeme výše uvedených výsledků ke studiu tzv. konvexního obalu dané funkce. Definice 3.47. Nechť X ⊂ Rn je konvexní množina, f : X → R. Funkce g(x) = sup{h(x) : h konvexní a h ≤ f na X} se nazývá konvexní obal funkce f a značí se Cf . Konvexní obal funkce je tedy největší konvexní funkce, která je danou funkcí majorizována. Pojem konvexního obalu funkce a další příbuzné pojmy (tzv. polykonvexní, quasikonvexní a rank-1 konvexní obal hrají důležitou roli ve variačním počtu, viz [5]. Věta 3.48. Nechť X ⊂ Rn je konvexní, f : X → R. Pak Cf (x) = inf{α| [x, α] ∈ conv (epi f )} a tedy Cf (x) = inf
(n+1 X i=1
λi f (xi ), xi ∈ X,
n+1 X i=1
λi xi = x, λi ≥ 0,
n+1 X
)
λi = 1 .
i=1
(3.24)
Důkaz. Označme g(x) = inf{α| [x, α] ∈ conv (epi f )}. Pak g(x) ≥ f (x) a g je konvexní. Vskutku, množina epi g = {[x, β] : β ≥ g(x)} = {[x, β] : [x, β] ∈ conv (epi f )} je konvexní a podle Věty 3.3 je konvexní i funkce g. Platí tedy g(x) ≥ Cf (x). Z druhé strany, vezmeme-li v úvahu, že pro libovolnou funkci f : X → R je f (x) = inf{α : [x, α] ∈ epi f } a že nerovnost h ≤ f na X implikuje epi h ⊇ epi f , a tedy i pro konvexní obal conv (epi h) ⊇ conv (epi f ), pro libovolnou funkci h ≤ f , která je na X konvexní, platí h(x) = inf{α| [x, α] ∈ epi h = conv (epi h)} ≤ ≤ inf{α| [x, α] ∈ conv (epi f )} = g(x).
Protože h ≤ f byla libovolná konvexní funkce, platí pro každé x ∈ X sup{h(x) : h ≤ f, h konvexní } ≤ g(x) a tedy Cf (x) ≥ g(x). Vztah (3.24) plyne přímo z aplikace Caratheodoryho věty (Věta 2.9) a Věty 3.3 na epi f . Předchozí věta má sice velmi názorný geometrický význam (nakreslete si obrázek ilustrující její tvrzení), pro praktický výpočet konvexních obalů funkcí není příliš vhodná, neboť i v nejjednodušším případě funkce jedné 48
proměnné je (3.24) minimalizační úloha se čtyřmi proměnnými x 1 , x2 ∈ X, λ1 , λ2 ∈ [0, 1] a dvěmi vazebnými podmínkami λ1 x1 + λ2 x2 = x, λ1 + λ2 = 1. K praktickému výpočtu konvexního obalu Cf se většinou využívá následující tvrzení. Věta 3.49. Nechť X ⊂ Rn je konvexní, f : X → R. Pak pro každé x ∈ ri X Cf (x) = f ∗∗ (x).
(3.25)
Důkaz. Protože funkce f ∗∗ je konjugovaná k f ∗ , je podle Lemmatu 3.40 konvexní. Dále z (3.21) plyne f (x) ≥ hx, yi − f ∗ (y) pro x, y ∈ Rn (s konvencí z Poznámky 3.38 (ii), že f a f ∗ jsou rovny ∞ vně svých definičních oborů) a odtud f (x) ≥ sup {hx, yi − f ∗ (y)} = f ∗∗ (x), y∈Rn
tedy f ∗∗ (x) ≤ Cf (x). Opačnou nerovnost dokážeme takto. Funkce Cf je konvexní a tedy spojitá v každém relativně vnitřním bodě množiny X, tj. (Cf )∗∗ = Cf v těchto bodech podle Věty 3.21. Protože Cf ≤ f a dvojí konjugace zachová nerovnosti mezi funkcemi, tj. (Cf ) ∗∗ ≤ f ∗∗ , což spolu s rovností (Cf )∗∗ = Cf dává požadovanou nerovnost Cf (x) ≤ f ∗∗ (x) pro x ∈ ri X. Příklad 3.50. Nechť f : R2 → R je definována předpisem 1 + x2 + y 2 pro x2 + y 2 6= 0, f (x, y) = 0 pro x2 + y 2 = 0. Vypočtěte Cf .
Řešení. Protože f je radiálně symetrická, stačí najít C f˜ pro f˜ : R → R definovanou takto: 1 + x2 , x 6= 0, f (x) = 0 x = 0. Pro tuto funkci f˜ platí
˜ f˜∗ (y) = sup{xy − f(x)} = max{sup[xy − 1 − x2 ], 0} = x∈R
= max
y2 4
− 1, 0
=
(
x6=0
y2 4
− 1 pro |y| ≥ 2, 0 pro |y| < 2.
Odtud f˜∗∗ (x) = sup{xy − f˜∗ (y)} = y∈R
(
y2 +1 = max sup {xy}, sup xy − 4 |y|≤2 |y|≥2 49
)
= max{2|x|, g(x)},
kde g(x) =
2|x| 1 + x2
pro |x| ≤ 1, pro |x| ≥ 1,
jak zjistíme přímým výpočtem. Přeformulujeme-li tento výsledek pro funkce f , dostáváme p 2 x2 + y 2 pro x2 + y 2 ≤ 1, ∗∗ Cf (x, y) = f (x, y) = 1 + x2 + y 2 pro x2 + y 2 > 1.
N
3.7
Systémy konvexních a afinních nerovností
Následující věta a zejména její „regulárníÿ modifikace hrají důležitou roli v teorii konvexního programování. Věta 3.51. Nechť X ⊂ Rn je konvexní, funkce f1 , . . . , fk : X → R jsou konvexní a funkce fk+1 , . . . , fm jsou afinní (tj. fi (x) = hai , xi + βi , ai ∈ Rn , βi ∈ R). Jestliže systém nerovností fi (x) < 0, i = 1, . . . , k,
fj (x) = 0, j = k + 1, . . . , m
(3.26)
nemá řešení na X, pak existují konstanty y 1 ≥ 0, . . . , yk ≥ 0, yk+1 , . . . , ym ∈ R, ne všechny současně nulové tak, že m X i=1
yi fi (x) ≥ 0
pro všechna x ∈ X.
(3.27)
Důkaz. Definujme množiny A ={u ∈ Rm : ∃¯ x ∈ X : fi (¯ x) ≤ ui , i = 1, . . . , k, fj (¯ x) = uj , j = k + 1, . . . , m},
B ={u ∈ Rm : ui < 0, i = 1, . . . , k, uj = 0, j = k + 1, . . . , m}. Jsou-li u ¯, u ˜∈Aax ¯, x ˜ k nim příslušející prvky z X z definice množiny A, pak pro λ ∈ [0, 1] vzhledem k předpokladům na funkce f i platí fi (λ¯ x + (1 − λ)˜ x) ≤ λ¯ u + (1 − λ)˜ u, i = 1, . . . , k,
fj (λ¯ x + (1 − λ)˜ x) = λ¯ u + (1 − λ)˜ u, j = k + 1, . . . , m. Z konvexnosti množiny X plyne, že λ¯ u + (1 − λ)˜ u ∈ A, tj. A je konvexní. Konvexnost množiny B je zřejmá, a protože systém (3.26) nemá řešení na X, platí A ∩ B = ∅. To znamená, že množiny A, B jsou oddělitelné, tj. existuje y = (y1 , . . . , ym ), y 6= 0 tak, že hy, ui ≥ hy, vi pro všechna [u, v] ∈ A × B, tj. m X i=1
yi ui ≥ 50
k X i=1
yi vi .
Jestliže v1 , . . . , vk → −∞, vidíme, že předchozí nerovnost je splňena pouze když y1 , . . . , yk ≥ 0. Dosadíme-li do této nerovnosti u i = fi (¯ x), i = 1, . . . , m, a jestliže v1 , . . . , vk → 0−, dostáváme požadované tvrzení. V následujícím výkladu se zaměříme na modifikace Věty 3.51 které zaručují, že koeficient y0 v (3.27) je kladný. Vydělíme-li tento vztah číslem y0 můžeme tvrdit, že y0 = 1. Podmínky, které zajišťují platnost tohoto zesíleného tvrzení budeme nazývat podmínky regularity a příslušná tvrzení nazýváme regulární modifikace Věty 3.51. Věta 3.52. Nechť X ⊂ Rn je konvexní, f0 , f1 , . . . , fm : X → R jsou konvexní. Jestliže systém nerovností f0 (x) < 0, fi (x) < 0, i = 1, . . . , m
(3.28)
nemá řešení na X a systém (3.28) má řešení na X, pak existují y 1 , . . . , ym ≥ 0 taková, že m X f0 (x) + yi fi (x) ≥ 0 ∀x ∈ X. (3.29) i=1
Důkaz. Podle předchozí věty existují y 0 , y1 , . . . , ym ≥ 0 taková, že platí (3.26). Kdyby y0 = 0, alespoň jedno z ostatních yi musí být kladné a dosadíme-li řešení x ¯ systému (3.28) do (3.26), dostáváme spor. Vydělením nerovnosti kladným číslem y0 dostáváme požadované tvrzení. Důkaz následujcího tvrzení je založen na Farkas-Minkowského větě 2.26. Tvrzení ukazuje, že v případě afinních funkcí lze v (3.28) ostré nerovnosti nahradit neostrými. Věta 3.53. Předpokládejme, že systém nerovností f0 (x) := ha0 , xi + β0 < 0,
(3.30)
fi (x) := hai , xi + βi ≤ 0, i = 1, . . . , m,
(3.31)
nemá řešení na Rn a podsystém (3.31) má řešení. Pak existují y 1 , . . . , ym ≥ 0 taková, že platí f0 (x) +
m X i=1
tj. a0 −
m X
yi fi (x) ≥ 0
yi ai = 0,
β0 +
i=1
pro ∀x ∈ Rn , m X i=1
51
yi βi ≥ 0.
(3.32)
(3.33)
Důkaz. Nechť a ˜ 0 = [a0 , β0 ] ∈ Rn+1 , a ˜i = [ai , βi ] ∈ Rn+1 , i = 1, . . . , m, n+1 am+1 = [0, 1], x ˜ = [h, λ] ∈ R , kde h ∈ Rn , a uvažujme homogenní systém nerovností h˜ a0 , x ˜, i < 0,
(3.34)
h˜ ai , x ˜i ≤ 0, i = 1, . . . , m + 1.
Ukážeme-li, že tento systém nemá řešení na R n+1 , pak podle Věty 3.52 existují reálná čísla y1 , . . . , ym+1 ≥ 0 taková, že platí (3.32), a tedy (3.33). Nechť x ˜ = [h, λ] je řešením (3.34) Z nerovnosti h˜ a m+1 , x ˜i = −λ ≤ 0 plyne, že λ ≥ 0. Je-li λ > 0, vydělením nerovností (3.34) číslem λ > 0 vidíme, že x = h/λ je řešením (3.30), (3.31) – spor, tedy λ = 0, tj. ha 0 , hi < 0, hai , hi ≤ 0, i = 1, . . . , m. Nechť x ¯ je řešením systému (3.31). Položme x 0 = x ¯ + th, kde t > 0 je dostatečně velké. Pak ha0 , x0 i = ha0 , x ¯i + tha0 , hi < 0,
hai , x0 i = hai , x¯i + thai , hi ≤ 0, i = 1, . . . , m, tj. x0 je řešením (3.30), (3.31) a i v případě λ = 0 jsme dospěli ke sporu, tedy (3.34) nemá řešení a věta je dokázána. Z předchozí věty přímo plyne tato regulární modifikace Věty 3.51 Věta 3.54. Nechť X ⊂ Rn je polyedr a funkce f0 , f1 , . . . , fk , . . . , fm jsou afinní. Jestliže systém nerovností f0 (x) < 0, fi (x) ≤ 0, i = 1, . . . , k,
fj (x) = 0, j = k + 1, . . . , m nemá řešení na X a systém bez první nerovnosti má řešení na X. Pak existují y1 , . . . , yk ≥ 0, yk+1 , . . . , ym ∈ R taková, že f0 (x) +
m X i=1
yi fi (x) ≥ 0
pro ∀x ∈ X.
(3.35)
Důkaz. Protože množina X je polyedr, je zadána systémem afinních nerovností g1 (x) ≤ 0, . . . , gs (x) ≤ 0. Nyní uvažujme na Rn systém afinních nerovností f0 (x) < 0, fi (x) ≤ 0,
i = 1, . . . , k,
gl (x) ≤ 0,
l = 1, . . . , s,
fj (x) ≤ 0, −fj (x) ≤ 0, a aplikujme předchozí větu. 52
j = k + 1, . . . , m,
Následující obecné tvrzení kombinuje podmínky regularity z Vět 3.52 a 3.53 a lze jej dokázat podobně jako tyto věty. Důkaz zde neuvádíme, podrobnosti lze nalézt v [22]. Věta 3.55. Nechť X ⊂ Rn je konvexní, k, m ∈ N, k < m, l ∈ {0, . . . , k}, funkce f0 , f1 , . . . , fl jsou konvexní na X, fl+1 , . . . , fk , . . . , fm jsou afinní na X a uvažujme na X systém nerovností f0 (x) < 0, fi (x) < 0, i = 1, . . . , l, fi (x) ≤ 0, i = l + 1, . . . , k, fi (x) = 0, i = k + 1, . . . , m. Jestliže celý systém nerovností nemá řešení na X a systém bez první nerovnosti má řešení na X, pak existují y1 , . . . , yk ≥ 0, yk+1 , . . . , m ∈ R taková, že platí (3.55). Poznámka 3.56. (ii) V [22] a [19] lza najít další (obecnější a komplikovanější) regulární medifikace Věty 3.51, které lze využít, podobně jako ve Větě 4.11 v následující kapitole, k odvození podmínek regularity v úloze matematického programování. (ii) Všechny systémy nerovnic a rovnic uvažované v tomto odstavci jsou konečné. Podobné výsledky jako jsou tvrzení tohoto odstavce lze formulovat i pro nekonečné systémy rovnic a nerovnic. Formulace těchto výsledků by však vyžadovala zavedení některých dalších pojmů, které zde z důvodu rozsahu nenašly své místo. Více podrobností lze nalézt v [20].
3.8
Cvičení
1. Rozhodněte, zda daná funkce je konvexní (silně konvexní) na dané množině. 2
2
(i) f (x, y) = ex1 +x1 x2 +x2 a) konvexní na R2 , b) silně konvexní na R2 . (ii) f (x, y, z) = 2x2 + y 2 + z 2 + xy − 2xz na R3 . Určete (maximální) konstantu silné konvexity θ. (iii) f (x, y) = (1 + x2 + y 2 )2 na R2 , (iv) f (x, y) = (v) f (x) =
1 x+2y
1 ha,xi ,
na R2+ .
x ∈ Rn+ , a ∈ Rn+
p (vi) f (x) = 1 + hAx, xi, na x ∈ Rn , kde A je symetrická pozitivně definitní matrice.
2. Dokažte následující tvrzení: Je-li funkce f : R → R konvexní a shora ohraničená, pak f je konstantní funkce. 53
3. Nechť X ⊆ Rn je konvexní množina, f (x) := ρ(x, X) = inf kx − ak, a∈X
dokažte, že funkce f je konvexní. R 4. Nechť X ⊂ Rn je omezená konvexní množina, pro níž 0 ∈ X. Dokaže, že funkce p(x) = inf {x ∈ αX} α>0
je konvexní. 5. Nechť f : R → R je konvexní. Dokažte, že pro libovolná x 1 , x2 ∈ R a λ 6∈ [0, 1] platí nerovnost f (λx1 + (1 − λ)x2 ) ≥ λf (x1 ) + (1 − λ)f (x2 ). 6. Nechť X ⊆ Rn je konvexní množina, f : X → R je spojitá funkce. Dotažte tvrzení: Jestliže existuje µ(0, 1) takové, že f (µx1 + (1 − µ)x2 ) ≤ µf (x1 ) + (1 − µ)f (x2 ) pro libovolná x1 , x2 ∈ X, pak f je konvexní na X. 7. Nechť f : R → R a definujme funkci g : R 2 → R předpisem g(x, y) = yf (x/y) pro y > 0. Dokažte, že g je konvexní na R × (0, ∞). 8. Nechť f1 , f2 : Rn → R. Definujem funkci h předpisem h(y) = inf{f1 (x1 ) + f (x2 ) : x1 + x2 = y} = inf {f1 (x) + f2 (y − x)}. x
Funkci h nazýváme infimální konvolucí funkcí f 1 , f2 a značíme h = f1 f2 . (i) Nechť f1 , f2 : Rn → R jsou konvexní, h = f1 f2 , Y = {x ∈ Rn : h(x) > −∞}. Pak je h konvexní na Y . Dokažte.
(ii) Dokažte rovnost
(f1 f2 )(x) = inf{µ : [x, µ] ∈ (epi f1 + epi f2 ). 9. Nechť f (x1 , x2 ) = 1 + a2 x21 + b2 x22 . Určete h = (h1 , h2 ) ∈ R2 , pro něž směrová derivace f 0 ([0, 0]; h) nabývá maximální (minimální) hodnoty 10. Nechť A je symetrická matice, λ1 (A) ≤ λ2 (A) ≤ · · · ≤ λn (A) jsou vlastní hodnoty matice, u1 , . . . , un jsou příslušející (ortogonální) jednotkové vlastní vektory, a předpokládejme, že právě m ∈ {0, . . . , n} vlastních hodnot A je záporných. Určete, pro která h ∈ R n jsou směrové derivace funkce f (x) langleAx, xi záporné. 11. Vypočtěte konjugovanou funkci k dané funkci a prověřte rovnost f = f ∗∗ . 54
√ (i) f (x) = − 2x − x2 .
(ii) f (x) = x lg x.
ex +e−x . 2 n x∈R ,A
(iii) f (x) = cosh x = (iv) f (x) = hAx, xi,
je symetrická pozitivně definitní matice.
12. Nechť f : Rn → R, f ∗ je konjugovaná funkce k f , A je regulární n × n matice, g(x) := f (Ax). Pomocí f ∗ určete g ∗ . 13. Určete subdiferenciál funkce p 2x21 + x22 . Pro bod [x1 , x2 ] = [0, 0] tuto množinu (i) f (x1 , x2 ) = načrtněte v rovnině. (ii) f (x1 , x2 ) = max{x1 , x2 }. p (iii) f (x) = hAx, xi, kde A je symetrická pozitivně definitní matice. p (iv) f (x1 , x2 ) = p |x1 |p + |x2 |p , p > 1.
55
56
Kapitola 4
Nutné a dostatečné podmínky optimality V této kapitole se budeme zabývat úlohou matematického programování f (x) → min,
x ∈ X,
(4.1)
kde přípustná množina je zadána systémem rovností a nerovností X = {x ∈ P ⊆ Rn : gi (x) ≤ 0, i = 1, . . . , k,
(4.2)
gj (x) = 0, j = k + 1, . . . , m}.
Omezení x ∈ P se nazývá přímé a omezení g i (x) ≤ 0, i = 1, . . . , k, gj (x) = 0, j = k + 1, . . . , m, se nazývají funkcionální omezení. Odvodíme zde nutné i postačující podmínky, aby bod x ∗ ∈ X byl řešením úlohy (4.1), (4.2), a to jak v případě, kdy funkce f, g i , gj jsou diferencovatelné, tak i v případě, kdy tuto vlastnost nemají. Nejprve si všimneme obecných rysů optimalizace reálných funkcí na omezených podmnožinách v Rn , v následujícím odstavci formulujeme tzv. Lagrangeův princip a KuhnTuckerovy podmínky, které udávají nutné podmínky pro to, aby x ∗ ∈ X bylo lokálním řešením úlohy (4.1). Kromě toho jsou zde formulovány i předpoklady, za kterých jsou Kuhn-Tuckerovy podmínky z Lagrangeova principu i dostatečnými pro to, aby daný přípustný bod byl řešením (4.1), (4.2). Dále je zde úloha matematického programování (4.1), (4.2) vyšetřována prostřednictvím tzv. duální úlohy a v posledním odstavci je studována závislost hodnoty této úlohy na parametrech.
4.1
Extrémy konvexních funkcí
V tomto odstavci budeme požívat následující označení. Nechť X ⊆ Rn , f : X → R. Označme V (x∗ , X) = {h ∈ Lin X : ∃ α0 > 0 : x∗ + th ∈ X pro ∀ t ∈ (0, α0 )}. 57
Všimněme si, že V (x∗ , X) = Lin X, je-li x∗ ∈ ri X. Množina V (x∗ , h) je vlastně množina vektorů „mířícíchÿ z bodu x ∗ do množiny X. Dále označme U (x∗ , f ) = {h ∈ Lin X : ∃α0 > 0 : f (x∗ + th) < f (x∗ ) pro ∀t ∈ (0, α0 )}, tj. U (x∗ , f ) tvoří vektory s vlastností, že při pohybu v jejich směru z bodu x∗ funkce f klesá. Téměř triviální je následující nutná podmínka pro existenci lokálního řešení úlohy (4.1), (4.2). Věta 4.1. Jestliže x∗ ∈ X je lokálním řešením úlohy (4.1), (4.2), pak U (x∗ , f ) ∩ V (x∗ , X) = ∅. Důkaz. Je-li h ∈ U (x∗ , f ) ∩ V (x∗ ), X) 6= ∅, pak pro α > 0 dostatečně malá je současně x∗ + αh ∈ X i f (x∗ + αh) < f (x∗ ), tj. x∗ není lokálním řešením (4.1), (4.2). Definice 4.2. Nechť množina X je konvexní a funkce f je diferencovatelná na X. Řekneme, že bod x∗ ∈ X je stacionární bod úlohy (4.1), jestliže hf 0 (x∗ ), x − x∗ i ≥ 0
(4.3)
pro každé x ∈ X. Věta 4.3. Nechť funkce f je diferencovatelná na konvexní množině X ⊆ R n . Je-li x∗ lokálním minimem f na X, pak x∗ je stacionární bod f na X. Je-li f navíc konvexní na X, pak z (4.3) plyne, že x ∗ je řešením (4.1), tj. globálním minimem f na X. Důkaz. Je-li x∗ řešením (4.1) a neplatí (4.3), tj. existuje x ∈ X, pro něž hf 0 (x∗ ), x − x∗ i < 0, pak pro h = x − x∗ je h ∈ U (x∗ , f ) i h ∈ V (x∗ , f ), což je spor s Větou 4.1. Je-li funkce f navíc konvexní, z Věty 3.15 plyne, že pro každé x ∈ X f (x) − f (x∗ ) ≥ hf 0 (x∗ ), x − x∗ )i. Platí-li (4.3), pak f (x) ≥ f (x∗ ), tj. x∗ je řešením (4.1). Poznámka 4.4. Předchozí věta odhaluje typický jev, se kterým se v následujícím textu setkáme ještě několikrát. Některá podmínka (v předchozím důsledku je to “být stacionárním bodem”), která je za obecných předpokladů pouze podmínkou nutnou pro extrém, se po „vhodněÿ přidaném předpokladu konvexity stane i podmínkou postačující. 58
Nyní se budeme zabývat z aplikačního hlediska důležitým případem, kdy X = Rn+ = {x = (x1 , . . . , xn ) ∈ Rn : xi ≥ 0, i = 1, . . . , n}. Podmínku (4.3) zapíšeme ve tvaru n X ∂f ∗ (x )(xi − x∗i ) ≥ 0 ∂xi
pro všechna xi ≥ 0.
i=1
(4.4)
Všimněme si jednotlivých sčítanců v předchozím součtu. Každý z těchto sčítanců je nezáporný, právě když je splněna dvojice podmínek ∂f ∗ (x ) ≥ 0 ∂xi
a
x∗i
∂f ∗ (x ) = 0. ∂xi
(4.5)
Vskutku, je-li ∂f ∗ (x )(xi − x∗i ) ≥ 0 ∂xi
(4.6)
pro každé xi ≥ 0, pak v případě x∗i = 0 je vždy xi − x∗i ≥ 0 a musí platit první podmínka v (4.5). Je-li x∗i > 0, pak rozdíl xi −x∗i nabývá kladných i zá∂f (x∗ ) = 0. Podobnou úvahou dokážeme, porných hodnot a (4.6) implikuje ∂x i že (4.5) implikuje (4.6), a tedy obě podmínky jsou ekvivalentní. Protože v (4.4) můžeme každý sčítanec vyšetřovat samostatně, je podmínka (4.4) ekvivalentní podmínce (4.5). Předchozí úvahy jsou shrnuty v následujícím tvrzení. Důsledek 4.5. Nechť funkce f je konvexní a diferencovatelná na R n+ . Pak x∗ ∈ Rn+ je řešením úlohy f (x) → min, právě když
4.2
∂f ∗ (x ) ≥ 0, ∂xi
x∗i
x ∈ Rn+
∂f ∗ (x ) = 0, i = 1, . . . , n. ∂xi
Lagrangeův princip
Nejprve připomeneme dvě věty z kurzu matematické analýzy týkající se tzv. vázaných extrémů. Uvažujme m-tici funkcí g 1 , . . . , gm : Rn → R a množinu X = {x ∈ Rn : gi (x) = 0, i = 1, . . . , m}.
(4.7)
Budeme předpokládat, že funkce gi jsou diferencovatelné a že vektory derivací gi0 (x), i = 1, . . . , m, jsou lineárně nezávislé pro každé x ∈ X. Označme pro y = (y1 , . . . , ym ) L(x, y) = f (x) +
m X i=1
59
yi gi (x)
tzv. (regulární) Lagrangeovu funkci úlohy (4.1) s množinou X zadanou v (4.7). Následující věta udává nutnou podmínku pro lokální extrém této extremální úlohy. Věta 4.6. Jestliže x∗ ∈ X je bod lokálního extrému funkce f na X, pak ∗ ∈ R, taková, že existují y1∗ , . . . , ym 0
∗
f (x ) +
m X
yi∗ gi0 (x∗ ) = 0,
(4.8)
i=1
tj., pro Lagrangeovu funkci úlohy platí L 0x (x∗ , y ∗ ) = 0. Připomeňme, že bod x∗ splňující (4.8) se nazývá stacionární bod úlohy ∗ se nazývají příslušející Lagrangeovy (4.1) (s X zadanou (4.7)) a y1∗ , . . . , ym multiplikátory. Následující věta udává podmínku 2. řádu (obsahuje 2. derivace funkcí f a gi , i = 1, . . . , m) pro to, aby stacionární bod byl bodem lokálního extrému. ∗ jsou příslušející LagranVěta 4.7. Nechť x∗ je stacionární bod a y1∗ , . . . , ym geovy multiplikátory. Jestliže kvadratická forma hL 00xx (x∗ , y ∗ )h, hi je pozitivně (negativně) definitní pro každé h ∈ R m , pro něž hgi0 (x∗ ), hi = 0, i = 1, . . . , m, pak x∗ je bod lokálního minima (maxima) funkce f na X.
Při vyšetřování vázaných extrémů tedy hraje klíčovou roli Lagrangeova funkce úlohy. Tato funkce v sobě „zahrnujeÿ vazebné podmínky a jejím prostřednictvím je převedeno hledání vázaných extrémů na hledání extrémů na celém prostoru Rn , tj. bez jakýchkoliv omezení. V podstatě stejná myšlenka je základem Lagrangeova principu vyšetřování úlohy (4.1), (4.2). Funkcionální omezení vystupující v definici přípustné množiny jsou „zabudoványÿ do Lagrangeovy funkce L, jejíž vyšetření na množině P dává informace o lokálních (a za dodatečných předpokladech i o globálních) extrémech úlohy (4.1), (4.2). Lagrangovou funkcí úlohy (4.1), (4.2) nazýváme funkci L : P ×R×R m → R definovanou předpisem L(x, y0 , y) = y0 f (x) +
m X
yi gi (x).
(4.9)
i=1
Dále budeme používat toto označení (připomeňme, že k, m ∈ N jsou vzaty z (4.2)): Q = {y = (y1 , . . . , ym ) ∈ Rm : y1 , . . . , yk ≥ 0} a pro x∗ ∈ X
I(x∗ ) = {i ∈ {1, . . . , k}, gi (x∗ ) = 0}
značí tzv. množinu aktivních nerovností v bodě x ∗ , tj. indexy těch nerovností definujících množinu X, které se v bodě x ∗ realizují jako rovnosti. Číslo y0 a komponenty yi vektoru y se nazývají Lagrangeovy multiplikátory. 60
Následující věta udává nutnou a postačující podmínku pro lokální extrém úlohy (4.1), (4.2). Věta 4.8. (Lagrangeův princip). Nechť množina P ⊆ R n je konvexní, funkce f, gi , i = 1, . . . , k, jsou diferencovatelné v bodě x ∗ ∈ X a gj (x), j = k + 1, . . . , m, jsou spojitě diferencovatelné v nějakém okolí bodu x ∗ . Je-li bod x∗ lokálním extrémem úlohy (4.1), (4.2), pak existují Lagrangeovy mul∗ , . . . , y ∗ ∈ R tak, že ne všechna y ∗ , y ∗ = tiplikátory y0∗ , y1∗ , . . . , yk ≥ 0, yk+1 m 0 ∗ ∗ (y1 , . . . , ym ) jsou nulová a hL0x (x∗ , y0∗ , y ∗ ), x − x∗ i ≥ 0, yi∗ gi (x∗ )
= 0,
∀x ∈ P,
i = 1, . . . , m.
(4.10) (4.11)
Důkaz. Princip důkazu vysvětlíme za dodatečného zjednodušujícího předpokladu, že funkce gk+1 , . . . , gm jsou afinní. Není-li tento předpoklad splněn, postupujeme jako v důkazu Věty 9.1 v [6]. Uvažujme systém nerovností na relativním vnitřku ri P množiny P hf 0 (x∗ ), x − x∗ i < 0,
hgi0 (x∗ ), x − x∗ i < 0,
hgi0 (x∗ ), x
∗
− x i = 0,
i = 1, . . . , k i = k + 1, . . . , m.
Tento systém nemá na ri P řešení. Kdyby totiž existovalo řešení x ˜ ∈ ri P tohoto systému, označme h = x ˜ − x∗ . Pak hf 0 (x∗ ), hi < 0, tj. h ∈ U (x∗ , h) a protože gi (x) − gi (x∗ ) = hgi0 (x), hi + o(khk)
pro i = 1, . . . , m. Tedy h ∈ V (x∗ , X), což je spor s Větou 4.1 a systém nemá řešení na X. Pak podle Věty 3.51 existují y 1 , . . . , yk ≥ 0, yk+1 , . . . , ym ∈ R tak, že m X yi gi0 (x∗ ) = 0, tj. hL0x (x∗ , y ∗ , y) ≥ 0 y ∗ f 0 (x∗ ) + i=1
pro každé x ∈ P .
Poznámka 4.9. Podmínka (4.10) značí, že x ∗ je stacionárním bodem Lagreangeovy funkce na P (vzhledem k proměnné x při y = y ∗ a y0 = y0∗ ). Vztahy (4.11) se nazývají podmínky komplementarity a znamenají, že Lagrangeovy multiplikátory příslušející pasivním nerovnostem v bodě x ∗ jsou nulové. Podmínky (4.10), (4.11) se v literatuře obvykle nazývají Kuhn-Tuckerovy podmínky úlohy (4.1), (4.2). Následující věta ukazuje, že přidáním dodatečného předpokladu konvexnosti funkcí f, g1 , . . . , gk a afinity funkcí gk+1 , . . . , gm , se Kuhn-Tuckerovy podmínky (4.10), (4.11) stávají dostatečnými pro existenci globálního řešení (4.1), (4.2). Tato skutečnost je v souladu s Poznámkou 4.4. 61
Věta 4.10. Nechť množina P je konvexní, funkce f, g 1 , . . . , gk jsou konvexní a diferencovatelné na P , funkce gk+1 , . . . , gm jsou afinní a nechť platí (4.10) a (4.11) s y0∗ = 1. Pak x∗ je globálním řešením úlohy (4.1). Důkaz. Předpoklady věty na funkce f, g 1 , . . . , gm implikují, že pro dané y ∗ ∈ Q je funkce L(x, y ∗ ) konvexní na P . Podmínka (4.10) říká, že x ∗ je stacionárním bodem funkce L na P (viz Poznámka 4.9). Podle Věty 4.3 je stacionární bod konvexní funkce na konvexní množině bodem globálního minima, tj. L(x∗ , y) ≤ L(x, y) pro každé x ∈ P . Tedy, vezmeme-li v úvahu rovnost m X f (x∗ ) = f (x∗ ) + yi gi (x∗ ) = L(x∗ , y), i=1
která plyne z (4.11), pro každé x ∈ X platí ∗
∗
f (x ) = L(x , y) ≤ L(x, y) = f (x) +
m X i=1
yi gi (x) ≤ f (x),
a tedy x∗ je globálním minimem funkce f na X.
Věta 4.11. (Kuhna-Tuckera v diferenciálním tvaru) Nechť P je konvexní, funkce f, g1 , . . . , gk jsou konvexní a diferencovatelné, g k+1 , . . . , gm jsou afinní a nechť platí alespoň jedna z podmínek regularity: (i) Slaterova: Funkcionální omezení jsou pouze ve tvaru nerovnosti, tj. k = m a existuje x ¯ ∈ P : gi (¯ x) < 0, i = 1, . . . , k; (ii) Lineární: Množina P je polyedr, g 1 , . . . , gk jsou afinní. (iii) Modifikovaná Slaterova: Existuje l ∈ {0, . . . , k} takové, že funkce gl+1 , . . . , gk jsou lineární, ∃¯ x ∈ ri P tak, že gi (¯ x) < 0, i = 1, . . . , l. ∗ Pak je-li x lokální minimum v (4.1), (4.2), existuje y ∈ Q tak, že platí (4.10), (4.11) s y0∗ = 1. Důkaz. Důkaz provedeme za předpokladu Slaterovy podmínky (i), důkaz zbývajících dvou tvrzení je založen na Větách 3.54 a 3.55. Stačí dokázat nutnou podmínku, postačující podmínka je již obsažena v předchozí větě. Uvažme systém rovností a nerovností (předpokládáme, že k = m): hf 0 (x∗ ), x − x∗ i < 0, hgi0 (x∗ ), x
∗
− x i < 0, i = 1, . . . , m.
(4.12) (4.13)
Tento systém nemá řešení na P . Vskutku, kdyby x ∗ ∈ P bylo řešením (4.12), (4.13), pak z diferencovatelnosti funkcí g i plyne gi (x∗ + αh) = gi (x∗ ) + hgi0 (x∗ ), αhi + o(h), tedy g(x∗ + αh) < g(x∗ ) pro α > 0 dostatečně malá; tj. x∗ + αh ∈ X. Současně z nerovnosti (4.12) v systému plyne, že f 0 (x∗ , h) < 0, tj. f (x∗ + αh) < f (x∗ ) 62
pro α > 0 dostatečně malá. To je ale spor se skutečností, že x ∗ je lokální minimum. Protože systém bez první rovnice (4.13) má předpokládané řešení ∗ ), y ∗ > 0, i = 1, . . . m, takové, x ¯, z Věty 3.52 plyne existence y ∗ = (y1∗ , . . . ym i P ∗ g (x∗ ) ≥ 0, tj. platí tvrzení věty. že f 0 (x∗ ) + m y i i=1 i
Poznámka 4.12. Úloha (4.1), kde množina X je konvexní a funkce f je na této množině konvexní se nazývá úloha konvexního programování. Pro tuto úlohu stačí najít její stacionární body, protože podle Věty 4.3 jsou stacionární body této úlohy její globální minima. Je-li množina X zadána systémem rovností a nerovností (4.2), je tato množina konvexní pokud funkce g i , i = 1, . . . , k, konvexní a funkce gj , j = k + 1, . . . , m, jsou afinní. Věta 4.10 říká, že pro tuto úlohu s konvexní funkcí f jsou Kuhn-Tuckerovy podmínky (4.10), (4.11) s y0∗ = 1 postačujícími podmínkami pro (globální) řešení (4.1), (4.2). Je-li navíc splněna některá z podmínek regularity (v předchozí větě jsou uvedeny jen ty nejznámější, v literatuře lze nalézt řadu dalších) pak se tato úloha nazývá regulární úloha konvexního programování. Ve zbývající části tohoto odstavce se zaměříme postačující podmínky 2. řádu (obsahují parciální derivace 2. řádu funkcí f a gi , i = 1, . . . , m) pro lokální minimum (4.1), (4.2). Pro x∗ ∈ P budeme používat následující označení V (x∗ ) ={h ∈ Rn : h = λ(x − x∗ ), λ ∈ R+ , x ∈ P }
H(x∗ ) ={h ∈ Rn : hf 0 (x∗ ), hi ≤ 0, hgi0 (x∗ ), hi ≤ 0, i ∈ I(x∗ ), hgj0 (x∗ ), hi = 0, j = k + 1, . . . , m}. Věta 4.13. Nechť f, gi i = 1, . . . , m, jsou dvakrát spojitě diferencovatelné v bodě x∗ ∈ X, předpokládejme, že existuje y0∗ ≥ 0, y ∗ ∈ Q tak, že platí Kuhn-Tuckerovy podmínky (4.10), (4.11) a hL00xx (x∗ , y0∗ , y ∗ )h, hi > 0
pro ∀h ∈ V (x∗ ) ∩ H(x∗ ),
(4.14)
kde V (x∗ ) je uzávěr množiny V (x∗ ). Pak x∗ je ostré lokální minimum (4.1),(4.2). Důkaz. Sporem: Předpokládejme, že x∗ není ostrým lokálním minimem f na X, tj. existuje posloupnost xk ∈ X taková, že xk → x a f (xk ) ≤ f (x∗ ). Označme −x∗ hk = kxxkk −x ∗ k . Pak khk k = 1, lze tedy bez újmy na obecnosti předpokládat, že h k → h, khk = 1 (neboť z posloupnosti hk můžeme vybrat konvergentní podposloupnost.) Platí: 0 ≥ f (xk ) − f (x∗ ) = hf 0 (x∗ ), xk − x∗ i + o(kxk − x∗ k), tedy hf 0 (x∗ ), hk i ≤ 0 pro k → ∞. Podobně hgi0 (x∗ ), hk i ≤ 0,
hgj0 (x∗ ), hk i
= 0,
i ∈ I(x∗ ),
j = k + 1, . . . , m.
63
Tedy pro k → ∞ je h ∈ H(x∗ ), hk ∈ V (x∗ ), tj. h ∈ V (x∗ ). Dále L(xk , y0∗ , y ∗ ) = L(x∗ , y0∗ , y ∗ ) + hL0x (x∗ , y0∗ , y ∗ ), xk − x∗ i + 1 + hL00xx (x∗ , y0∗ , y ∗ )(xk − x∗ ), xk − x∗ i + o[(xk − x∗ )2 ], 2 a současně L(x∗ , y0∗ , y ∗ ) = y ∗ f (x∗ ) +
m X i=1
≥ y0∗ f (xk ) +
m X
yi∗ gi (x∗ ) = y ∗ f (x∗ ) ≥ y0∗ f (xk ) ≥ yi∗ gi (xk ) = L(xk , y0∗ , y ∗ ).
i=1
Odtud, s využitím (4.10), s označením αk = kxk − x∗ k, α2k 00 ∗ ∗ ∗ hLxx (x , y0 , y )h, hi + o(α2k ). 2
0 ≥ L(xk , y0∗ , y ∗ ) − L(x∗ , y0∗ , y ∗ ) ≥
Vydělením této nerovnosti α2k a limitním přechodem pro k → ∞ máme spor předpokladem (4.14). Důsledek 4.14. Nechť platí (4.14) pro všechna h ∈ Rn , pro něž hgi0 (x∗ ), hi, hgi0 (x∗ ), hi
yi∗ hgi0 (x∗ ), hi
≤ 0 i ∈ I(x∗ ), = 0, i = k + 1, . . . , m, i ∈ I(x∗ ).
= 0,
Je-li h ∈ V (x∗ ), pak x∗ je ostré lokální minimum (4.1). Důkaz. Předpokládejme, že x∗ není ostré lokální minimum, tj. existuje posloupnost xk ∈ X, xk → x∗ taková, že f (xk ) ≤ f (x∗ ). Nechť hk , h jsou stejná jako v důkazu Věty 4.13. Podle (4.10) je hL0x (x∗ , y0∗ , y ∗ ), hi ≥ 0, tj., y0∗ hf 0 (x∗ ), hi +
m X i=1
yi∗ hgi0 (x∗ ), hi ≥ 0,
a yi∗ hgi0 (x∗ ), hi = 0 pro i ∈ {1, . . . , m} ∩ I(x∗ ) a je splěna opačná nerovnost než (4.14), stejně jako v důkazu Věty 4.13, což je spor. Poznámka 4.15. Všimněme si, že pro k = 0 nám podmínky na vektor h v předchozím důsledku určují tečný prostor k množině X určené vztahem (4.7) a tvrzení Důsledku 4.14 je totožné s Větou 4.7.
4.3
Dualita v úlohách matematického programování
Uvažujeme opět extremální úlohu (4.1), (4.2) a připomeňme, že f ∗ = inf f (x). x∈X
64
nazýváme hodnotou úlohy matematického programování (4.1), (4.2). Dále připomeňme, že Q = {y = (y1 , . . . , ym ) ∈ Rm : y1 , . . . , yk ≥ 0}. V teorii duality hraje velmi důležitou roli následující pojem. Definice 4.16. Vektor y ∈ Q se nazývá vektor Kuhna-Tuckera úlohy (4.1), (4.2), jestliže ∗
f ≤ f (x) +
m X i=1
yi gi (x) pro všechna x ∈ P.
Následující věta udává postačující podmínku pro existenci vektoru Kuhna-Tuckera úlohy (4.1), (4.2). Věta 4.17. Nechť P je konvexní, f, g1 , . . . , gk jsou konvexní a gk+1 , . . . , gm jsou afinní a platí alespoň jedna z následujících podmínek regularity: (i) Slaterova: k = m a existuje x ¯ ∈ P tak, že g i (¯ x) < 0, i = 1, . . . , k (ii) Lineární: P je polyedr, funkce f, g 1 , . . . , gk jsou afinní. (iii) Modifikovaná Slaterova: Existuje index l ∈ {0, . . . , k} takový, že funkce f, g1 , , gl jsou konvexní na relativně otevřené množině U ⊃ P , funkce gl+1 , . . . , gk jsou lineární a existuje x ¯ ∈ ri P takové, že g i (¯ x) < 0, i = 1, . . . , l. Pak existuje vektor Kuhna-Tuckera úlohy (4.1), (4.2). Důkaz. Důkaz provedeme stejně jako u Věty 4.11 pouze za předpokladu Slaterovy podmínky (i). Uvažujme systém nerovností f (x) − f ∗ < 0 gi (x) < 0
i = 1, . . . , m.
Tento systém nemá na P řešení a nechť x ¯ je řešením tohoto systému bez první nerovnosti. Podle Slaterovy modifikace Věty 3.51 existují y 1 , . . . , ym ≥ 0 tak, že m X yi gi (x) ≥ 0 pro ∀x ∈ P. f (x) − f ∗ + i=1
Tedy y = (y1 , . . . , ym ) je vektor Kuhna-Tuckera (4.1), (4.2).
Připomeňme, že v teorii lineárního programování je důležitým pojmem pojem duální úlohy, a že původní a duální úloha mají za jistých dodatečných předpokladů stejnou hodnotu. V následující definici zavedeme tento pojem i pro úlohu matematického programování (4.1), (4.2). Definice 4.18. Nechť y ∈ Q. Definujme funkci " ϕ(y) = inf L(x, y) = inf x∈P
x∈P
65
f (x) +
m X i=1
yi gi (x)
#
a označme Y = {y ∈ Q : ϕ(y) > −∞}. Duální úlohou pak nazýváme úlohu ϕ(y) → max,
(4.15)
y ∈ Y,
a veličinu ϕ∗ = sup ϕ(y) y∈Y
nazýváme hodnota duální úlohy (4.15). Následující tvrzení ukazuje, že duální úloha je úlohou konvexního programování (hledání maxima funkce ϕ je totéž jako hledání minima funkce −ϕ), bez ohledu na to, zda primární úloha (4.1), (4.2) je nebo není konvexní. Věta 4.19. Množina Y je konvexní a funkce ϕ z duální úlohy je konkávní na Y . Důkaz. Nechť y1 , y2 ∈ Y, λ ∈ [0, 1] jsou libovolná. Pak ϕ(λy1 + (1 − λ)y2 ) = =
inf L(x, λy1 + (1 − λ)y1 ) =
x∈P
inf [λL(x, y1 ) + (1 − λ)L(x, y2 )] ≥
x∈P
≥ λ inf L(x, y1 ) + (1 − λ) inf L(x, y2 ) = x∈P
x∈P
= λϕ(y1 ) + (1 − λ)ϕ(y2 ) > −∞. Tento výpočet kromě konkávnosti funkce ϕ dokazuje i konvexnost množiny Y. Poznámka 4.20. Centrálním problémem teorie duality je dokázat, že primární a duální úloha mají stejnou hodnotu, tj. platí f ∗ = ϕ∗ . Jestliže tato rovnost nastane, je možno řešit primární úlohu (4.1), (4.2) pomocí duální úlohy (4.15). Duální úloha je „ jednoduššíÿ než primární úloha (je to úloha konvexního programování – pro tuto úlohu stačí najít stacionární body) a je-li ϕ∗ hodnota (4.15), stačí najít řešení rovnice f (x) = ϕ ∗ na množině X. Jinou motivací pro studium podmínek pro rovnost f ∗ = ϕ∗ můžeme uvést následujícím způsobem. Definujme funkci ψ na množině P zadané přímými omezeními takto: f (x) pro x ∈ X, ψ(x) = ∞ pro x ∈ P \X. Pak snadnou úvahou lze ověřit, že ψ(x) = sup L(x, y)
a
y∈Q
inf f (x) = inf ψ(x).
x∈X
x∈P
Pak platí f ∗ = inf ψ(x) = inf sup L(x, y) x∈P
x∈P y∈Q
66
a
ϕ∗ = sup inf L(x, y). y∈Q x∈P
Vidíme tedy, že hodnotu původní úlohy (4.1) a duální úlohy (4.15) dostaneme záměnou operací sup a inf v Lagrangeově funkci. Možnost záměny operací suprema a infima pro jisté funkce dvou proměnných (tzv. výplatní funkce) je centrálním problémem teorie her, viz např. [1]. Nejprve ukážeme, že hodnota primární úlohy je vždy větší nebo rovna hodnotě duální úlohy. Věta 4.21. Pro každé x ∈ X a každé y ∈ Q platí f (x) ≥ ϕ(y),
tj.
f ∗ ≥ ϕ∗ .
(4.16)
Důkaz. Pro každé x ∈ X a každé y ∈ Q je f (x) ≥ f (x) + ≥
m X i=1
yi gi (x) = L(x, y) ≥ inf L(x, y) ≥ x∈X
inf L(x, y) = ϕ(y),
x∈P
tj., jestliže vezmeme infimum levé strany nerovnosti a supremum pravé strany, dostáváme f ∗ ≥ ϕ∗ . V následujícím příkladě ukážeme, že v případě úlohy lineárního programování je duální úloha totožná s duální úlohou zavedenou v kurzu lineárního programování. Příklad 4.22. Uvažujme úlohu lineárního programování v obecném tvaru hc, xi → min,
x∈X
pro přípustnou množinu X danou podmínkami n X
j=1 n X
ai,j xj ≥ bi ,
i = 1, . . . , k,
ai,j xj = bi ,
i = k + 1, . . . , m,
j=1
xj ≥ 0, j = 1, . . . , s.
Určete duální úlohu k této úloze. Řešení. Označme A matici m × n, jejíž řádky jsou tvořeny vektory a i ∈ Rn , i = 1, . . . , m a nechť L(x, y) = hc, xi + hy, b − Axi. Omezení xj ≥ 0, j = 1, . . . s, bereme jako přímá omezení definující množinu P (toto je typický postup v řešení i obecnějších úloh matematického programování). Pak ϕ(y) = inf L(x, y). x1 ,...,xs ≥0
67
Platí L0x = c − AT y, a protože úloha lineárního programování je konvexní, stačí najít řešení systému hc − AT y, x − x∗ i ≥ 0 na P , tj. x∗i (c − AT y)i =0,
i = 1, . . . , s,
T
(c − A y)i =0,
i = s + 1, . . . , m,
po rozepsání do souřadnic. Tedy ϕ(y) = inf [hy, bi + hc − AT y, xi] = hy, bi, y∈Y
pokud (c − AT y)i ≥ 0, i = 1, . . . , s a (c − AT y)i = 0, i = s + 1, . . . , m a hodnota suprema v definice ϕ je rovna ∞, pokud je alespoň jedna z těchto podmínek porušena. To znamená, že přípustná množina Y duální úlohy je dána systémem nerovností a rovností m X i=1
m X
ai,j yi ≤ cj ,
j = 1, . . . , s,
ai,j yi = cj ,
j = s + 1, . . . , n,
i=1
yi ≥ 0,
i = 1, . . . , k.
Zjistili jsme, že duální úloha má tvar hy, bi → max, y ∈ Y , je to tedy opět úloha lineárního programování (a stejná, jako bylo odvozeno v kursu tohoto předmětu). N Následující tvrzení je nejdůležítějším výsledkem tohoto odstavce a udaává postačující podmínku pro tzv. vztah duality f ∗ = ϕ∗ . Věta 4.23. Nechť (4.1), (4.2) je regulární úloha konvexního programování, tj. P je konvexní, f, g1 , . . . , gk jsou konvexní, gk+1 , . . . , gm jsou afinní a platí alespoň jedna z podmínek regularity (i)–(iii) z Věty 4.17. Pokud f ∗ > −∞, pak platí tzv. vztah duality f ∗ = ϕ∗ , (4.17) přičemž množina řešení (4.15) je neprázdná a je rovna množině všech vektorů Kuhna-Tuckera úlohy (4.1), (4.2). Důkaz. Podle Věty 4.17 existuje vektor Kuhna-Tuckera úlohy (4.1), (4.2), označme jej y ∗ ∈ Q, tj. f ∗ ≤ f (x) +
m X
yi∗ gi (x)
i=1
∀x ∈ P,
tj. −∞ < f ∗ ≤ inf x∈P L(x, y ∗ ) = ϕ∗ . Tedy f ∗ ≤ ϕ(y ∗ ) ≤ ϕ∗ , což spolu s (4.16) dává f ∗ = ϕ∗ . 68
Nechť y ∗ je řešení (4.15). Tedy f ∗ = ϕ(y ∗ ) = inf L(x, y ∗ ) = f (x) + x∈P
m X
yi∗ gi (x),
i=1
∀x ∈ P,
což znamená, že y ∗ je vektor Kuhna-Tuckera (4.1), (4.2). Naopak, nechť y ∗ je Kuhn-Tuckerův vektor této úlohy. Tedy ∗
∗
ϕ = f ≤ f (x) +
m X
yi∗ gi (x) = L(x, y ∗ ),
i=1
tj. ϕ∗ ≤ inf x∈P L(x, y ∗ ) = ϕ(y ∗ ). Tedy ϕ∗ = ϕ(y ∗ ), což znamená, že y ∗ řešením (4.15). Jako přímý důsledek předchozí věta dostáváme následující tvrzení. Důsledek 4.24. Nechť (4.1), (4.2) je regulární úloha konvexního programování a Y přípustná množina (4.15). Pak platí: (i) Je-li množina Y neprázdná, pak je duální úloha řešitelná a f ∗ > −∞. (ii) Je-li Y = ∅, pak je f ∗ = −∞. Následující věta je v literatuře většinou citována jako Kuhn-Tuckerova věta v nediferenciálním tvaru. Všimněme si, že první z Kuhn-Tuckerových podmínek (4.10) (která říká, že x∗ je stacionární bod Lagrangeovy funkce na P ) spolu s předpokladem konvexnosti úlohy (4.1), (4.2) implikuje, že L(x∗ , y ∗ ) ≤ L(x, y ∗ ) pro všechna x ∈ P, tj. platí první z podmínek (ii) v následující větě. Věta 4.25. Nechť (4.1), (4.2) je regulární úloha konvexního programování. Pak x∗ ∈ X je řešení této úlohy právě tehdy, když platí alespoň jedna z následujících podmínek: (i) Existuje y ∗ ∈ Q takové, že ϕ(y ∗ ) = f (x∗ ); (ii) Existuje y ∗ ∈ Q takové, že L(x∗ , y ∗ ) = min L(x, y ∗ ), x∈P
yi∗ gi (x∗ ) = 0,
i = 1, . . . , k.
(4.18) (4.19)
Důkaz. Je-li x∗ řešení (4.1), (4.2), tj. f (x∗ ) = f ∗ , pak pro každý vektor Kuhna-Tuckera je podle Věty 4.23 ϕ∗ = ϕ(y ∗ ) a f ∗ = f (x∗ ). Celkem tedy f (x∗ ) = ϕ(y ∗ ), neboť f ∗ = ϕ∗ . Naopak, nechť f (x∗ ) = ϕ(y ∗ ) pro nějaké y ∗ ∈ Q. Pak f ∗ ≤ f (x∗ ) = ϕ(y ∗ ) ≤ ϕ∗ , tedy f ∗ = f (x∗ ) a x∗ je řešení (4.1), (4.2). 69
K důkazu tvrzení (ii), podle části (i), existuje y ∗ ∈ Q takové, že f (x∗ ) = ϕ(y ∗ ), tj. f (x∗ ) = inf L(x, y ∗ ) ≤ f (x) + x∈P
tedy
Pm
∗ i=1 yi gi (x)
Pak f (x∗ ) = f (x∗ ) +
m X i=1
tj.
yi∗ gi (x)
i=1
∀x ∈ P,
≥ 0, tj. yi∗ gi (x) = 0,
L(x∗ , y ∗ )
m X
i = 1, . . . , m.
yi∗ gi (x∗ ) ≤ L(x, y ∗ )
∀x ∈ P,
L(x, y ∗ ).
= minx∈P Nechť naopak platí podmínky (4.18), (4.19). Pak L(x∗ , y ∗ ) = min L(x, y ∗ ) = inf L(x, y ∗ ) = ϕ(y ∗ ). x∈P
x∈P
Současně však f (x∗ ) = L(x∗ , y ∗ ), tedy f (x∗ ) = ϕ(y ∗ ) a podle (i) je x∗ řešení (4.1), (4.2). Odstavec zakončíme definicí sedlového bodu Lagrangeovy funkce úlohy (4.1), (4.2) a vztahem tohoto pojmu k teorii duality. Definice 4.26. Bod [x∗ , y ∗ ] ∈ P ×Q se nazývá sedlovým bodem Lagrangeovy funkce L(x, y) na P × Q, jestliže platí L(x∗ , y) ≤ L(x∗ , y ∗ ) ≤ L(x, y ∗ )
pro ∀x ∈ P a ∀y ∈ Q.
V následující větě je využit pojem sedlového bodu Lagrangeovy funkce k formulaci nutné a postačující podmínky pro globální řešení úlohy (4.1), (4.2). Věta 4.27. Nechť P je konvexní množina, funkce f, g 1 , . . . , gk jsou konvexní na P, gk+1 , . . . , gm jsou afinní na P a platí některá z podmínek regularity (i)(iii) z Věty 4.17. Pak bod x∗ ∈ P je řešením (4.1), (4.2), právě když existuje y ∗ ∈ Q tak, že [x∗ , y ∗ ] je sedlovým bodem Lagrangeovy funkce L(x, y) na P × Q. Důkaz. Vzhledem k tvrzení Věty 4.25 stačí ukázat, že druhý vztah v tvrzení (ii) této věty je ekvivalentní nerovnosti L(x ∗ , y ∗ ) ≥ L(x∗ , y) pro každé y ∈ Q. Nechť tedy platí (ii) z Věty 4.25, pak L(x∗ , y ∗ ) = f (x∗ ) ≤ f (x∗ ) + 70
m X i=1
yi gi (x∗ ) = L(x∗ , y)
pro každé y ∈ Q. Naopak, je-li L(x∗ , y ∗ ) ≥ L(x∗ , y) pro každé y ∈ Q, tj. f (x∗ ) +
m X i=1
tj.
m X
yi∗ gi (x∗ ) ≥ f (x∗ ) +
yi∗ gi (x∗ )
i=1
≥
m X
m X
yi gi (x∗ ),
i=1
yi gj (x∗ ),
i=1
P ∗ ∗ pro každé y ∈ Q, tedy i pro y = 0. Odtud m i=1 yi gi (x ) ≥ 0 a ale současně ∗ yi gi (x ) ≤ 0 a odtud dostáváme požadované tvrzení. Poznámka 4.28. Zcela analogicky jako předchozí větu lze dokázat, že bod y ∗ ∈ Y je řešením duální úlohy (4.15), právě když existuje x ∗ ∈ P takové, že [x∗ , y ∗ ] je sedlovým bodem Lagrangeovy funkce L(x, y) na P ×Q. Všimněme si rovněž, že implikace: Bod [x∗ , y ∗ ] je sedlovým bodem L(x, y) na P × Q =⇒ x∗ je řešením (4.1), (4.2) platí i bez předpokladů regularity. Příklad 4.29. (i) Určete duální úlohu k úloze f (x) = e−x → min,
x≤1
a prověřte platnost vztahu duality f ∗ = ϕ∗ . Řešení. Podle definice ϕ(y) = =
inf L(x, y) = inf {f (x) + yg(x)} =
x∈R
x∈R
inf {e−x + y(x − 1)}.
x∈R
Pro y ≥ 0 je tato funkce konvexní, tedy její libovolný stacionární bod je bodem minima na R. V případě y = 0 je zřejmě inf x∈R e−x = 0 a pro y > 0 je stacionární bod x = ln y, tedy ϕ(y) = y + y(− ln y − 1) = −y ln y. Konečně, pro y < 0 je funkce L(x, y) = e −x + y(x − 1) zdola neohraničená na R (neboť limx→∞ L(x, y) = −∞. Celkem tedy −y lg y, ϕ(y) = 0, −∞,
y > 0, y = 0, y < 0.
Duální úloha je pak tvaru
ϕ(y) → max,
y ∈ Y = [0, ∞). 71
Protože limy→0+ −y ln y = 0, je minimalizovaná funkce spojitá na [0, ∞) (a je diferencovatelná na (0, ∞)), maximum najdeme jako její stacionární bod, neboť podle Věty 4.19 je tato funkce konkávní (o čemž se také snadno můžeme přesvědčit derivováním, ϕ00 (y) = − y1 < 0). Stacionární bod ϕ je y ∗ = e−1 a ϕ∗ = sup ϕ(y) = ϕ(e−1 ) = e−1 . y∈[0,∞)
Na závěr porovnejme hodnotu duální úlohy s hodnotou původní úlohy. Protože funkce e−x je klesající, nabývá svého minima v pravém krajním bodě intervalu, na němž hledáme minimum, tedy f ∗ = e−1 . Tento výsledek samozřejmě není překvapující, protože jsou splněny předpoklady Věty 4.23. N (ii) Určete duální úlohu k úloze f (x1 , x2 ) = x21 + x22 − x1 x2 → min,
x 1 + x2 ≥ 1
a prověřte platnost vztahu duality f ∗ = ϕ∗ . Řešení. Lagrangeova funkce úlohy je L(x1 , x2 , y) = x21 + x22 − x1 x2 + y(−x1 − x2 + 1). Všimněte si, že v zadání je omezující nerovnost ve tvaru „≥ÿ, avšak teorie vyžaduje nerovnosti ve tvaru „≤ÿ, proto bylo třeba nejprve omezující nerovnost vynásobit číslem −1. Lagrangeova funkce je konvexní funkcí proměnných x1 , x2 pro každé y ∈ R (je to kvadratická forma s pozitivně definitní maticí – přesvědčte se o tom), nabývá tedy svého minima ve stacionárním bodě, kterým dostaneme jako řešení systému rovnic L0x1 = 2x1 − x2 − y = 0,
L0x2 = −x1 + 2x2 − y = 0.
Odtud x1 = x2 = y a dosazením ϕ(y) =
inf
[x1 ,x2 ]∈R2
L(x1 , x2 , y) = 2y 2 − y 2 − y(2y − 1) = −y 2 + y.
Duální úloha je tedy úloha ϕ(y) = −y 2 + y → max,
y ≥ 0.
stacionární bod funkce ϕ y ∗ = 21 leží v přípustné množině duální úlohy, přičemž maximalizovaná funkce je konkávní, tedy 1 ϕ∗ = ϕ(y ∗ ) = . 4 Na závěr opět porovnáme hodnotu primární a duální úlohy (musí vyjít stejné, neboť jsou splněny předpoklady Věty 4.23). Stacionární bod funkce 72
f je [x1 , x2 ] = [0, 0], tento bod neleží v přípustné množině, minima je tedy nabyto na hraniční přímce x2 = 1 − x1 . Dosazením do funkce f a následným derivováním vyjde 1 1 1 = = ϕ∗ . f∗ = f , 2 2 4 N
4.4
Závislost řešení úlohy matematického programování na parametrech
Uvažujme úlohu matematického programování závisející na m-tici parametrů b = (b1 , . . . , bm ) ∈ Rm f (x) → min,
x ∈ X(b) := {x ∈ P ⊆ Rn | gi (x) ≤ bi , i = 1, . . . , m}. (4.20)
Pro jednoduchost budeme předpokládat, že v úloze se nevyskytují žádné ohraničující rovnosti. Budeme používal následující označení. g(x) = (g1 (x), . . . , gm (x)), m
B = {b ∈ R | X(b) 6= ∅},
X(b) = {x ∈ P | g(x) ≤ b}, F (b) = inf f (x), x∈X(b)
m
Y (b) = {y ∈ R | y ≥ 0, f (b) ≤ f (x) + hy, g(x) − bi, ∀x ∈ P }. V terminologii používané v předcházejícím textu je X(0) = X, F (0) = f ∗ a Y (b) je množina vektorů Kuhna-Tuckera úlohy (4.20). Následující věta shrnuje nejpodstatnější tvrzení týkající se závislosti řešení úlohy (4.20) na vektorovém parametru b. Věta 4.30. Nechť množina P je konvexní, funkce f, g 1 , . . . , gm jsou konvexní na P , F (0) > −∞ a Y (0) 6= ∅. Pak platí: (i) Množina B je konvexní. (ii) Funkce F (b) je konečná, konvexní a nerostoucí na B. (iii) Pro subdiferenciál funkce F platí ∂F (b) = −Y (b). Důkaz. (i) Nechť ˜b, ˆb ∈ B a λ ∈ [0, 1] jsou libovolná, tj. existují x ˜ ∈ X(˜b), x ˆ∈ ˆ X(b), položme x = λˆ x + (1 − λ)ˆ x. Platí g(x) = g(λ˜ x + (1 − λ)ˆ x) ≤ λg(˜ x) + (1 − λ)g(ˆ x) ≤ ˜b + (1 − λ)ˆb. Tedy x ∈ X(λ˜b + (1 − λ)ˆb), tj. λ˜b + (1 − λ)ˆb ∈ B. (ii) Nechť y ∗ ∈ y(0), tj. F (0) ≤ f (x) + hy ∗ , g(x)i pro všechna x ∈ P a tedy pro libovolné b ∈ B a x ∈ X(b) platí F (0) ≤ f (x) + hy ∗ , bi a tedy i F (0) ≤ F (b) + hy ∗ , bi, 73
(4.21)
protože F (0) > −∞, a tedy i F (b) > −∞. Nyní nechť ˜b, ˆb ∈ B, λ ∈ [0, 1] a b = λ˜b + (1 − λ)ˆb. Pro libovolná x ˜ ∈ X(˜b), x ˆ ∈ X(ˆb) položme x = λ˜ x + (1 − λ)ˆ x). Podle části (i) je x ∈ X(b), odtud F (b) ≤ f (x) ≤ λF (˜ x) + (1 − λ)F (ˆ x). Protože x ˜ ∈ X(˜b), x ˆ ∈ X(ˆb) byla libovolná, platí F (b) ≤ λF (˜b)+(1−λ)F (ˆb). Monotonie funkce F plyne z faktu, že pro ˆb ≤ ˜b je X(ˆb) ⊆ X(˜b). iii) Nechť b ∈ B je libovolné a y ∗ ∈ ∂F (b), tj. F (b0 )−F (b) ≥ hy ∗ , b0 −bi pro každé b0 ∈ B. Nechť x ∈ P je libovolné. Položme b 0 = g(x), pak F (b0 ) ≤ f (x) a f (x) − F (b) ≥ hy ∗ , g(x) − bi, tj. F (b) ≤ f (x) + hy ∗ , g(x) − bi, a protože x ∈ P bylo libovolné, −y ∗ ∈ Y (b∗ ), neboť z monotonie funkce F plyne, že y ∗ ≥ 0. Nechť naopak −y ∗ ∈ Y (b), tj. F (b) ≤ f (x) + h−y ∗ , g(x) − bi pro všechna x ∈ P . Pro libovolné b0 ∈ B a x ∈ X(b0 ) dostáváme F (b) ≤ f (x) + h−y ∗ , b0 − bi, a tedy i F (b) ≤ F (b0 ) + h−y ∗ , b0 − bi, tj. y ∗ ∈ ∂F (b). Příklad 4.31. (i) Určete závislost F (b) parametrické úlohy matematického programování na parametru b, určete duální úlohu a prověřte platnost rovnice ∂F (b) = −Y ∗ (b) pro úlohu f (x) = x2 + 2x + 2 → min,
x ≤ b.
Řešení. Nejprve určíme funkci F (b) = min x≤b f (x). Protože minimum funkce f na R je f (−1) = 1, platí ( 1 b ≥ −1, F (b) = 2 b + 2b + 2 b ≤ −1. Tato funkce je diferencovatelná a platí ( 0 F 0 (b) = 2b + 2
b ≥ −1, b ≤ −1.
Lagrangeove funkce úlohy je L(x, y) = x2 + 2x + 2 + y(x − b). 74
Tato funkce je konvexní na R vzhledem k x (pro každé y ∈ R), tedy minima nabývá v (jediném) stacionárním bodě x ∗ = − y+2 2 a tedy ϕ(y) = L(x∗ , y) = −
y2 − (b + 1)y + 1. 4
Duální úloha tedy je −
y2 − (b + 1)y + 1 → max, 4
y ≥ 0.
Stacionární bod funkce ϕ je y = −2(b + 1), který je v přípustné množině y ≥ 0 právě když b ≤ −1, v opačném případě je maxima nabyto pro y∗ = 0. Celkem tedy řešením duálním úlohy a současně Kuhn-Tuckerovým vekterem původní úlohy (viz Věta 4.23) je ( 0 b ≥ −1, y ∗ (b) = −2(b + 1) b ≤ −1. Tento výsledek je v souladu s výpočtem F 0 (b), protože podle teorie regulárních úloh konvexního programování F 0 (b) = −y ∗ (b). N (ii) Při stejném zadání jako v části (i) řešete úlohu |x| → min,
x ≤ b.
Řešení. Náčrtkem grafu funkce f (x) = |x| sandno zjistíme, že ( 0 b ≥ 0, F (b) = −b b ≤ 0. Lagrangeove funkce úlohy je L(x, y) = |x| + y(x − b). Tato funkce je konvexní na R vzhledem k x (pro každé y ∈ R), ale není na R diferencovatelná, proto při hledání funkce ϕ nemůžeme postupovat stejně jako v předchozím příkladě. Náčrtkem grafů funkcí |x| a y(x − b) po kratší úvaze dojdeme k závěru, že ( −yb |y| ≤ 1, ϕ(y) = inf {|x| + y(x − b)} = x∈R −∞ |y| > 1. Tedy duální úloha je tvaru −yb → max, 75
y ∈ [0, 1].
Protože lineární funkce nabývá vždy svého extrému na hranici množiny, v níž se hledá extrém (zde je to interval [0, 1]), extrému je dosaženo v bodě ( 0 b ≥ 0, y ∗ (b) = b b ≤ 0. Tento výsledek je opět v souladu s teorií, protože vyšlo F 0 (b) = −y ∗ (b).
N
(iii) Určete závislost hodnoty F (b 1 , b2 ) úlohy f (x1 , x2 ) = x21 + x22 → min,
x 1 + x2 ≤ b1 ,
x1 − x2 ≤ b2
na parametru b = (b1 , b2 ). Řešení. Lagrangeova funkce má tvar L(x1 , x2 , y1 , y2 ) = x21 + x22 + y1 (x1 + x2 − b1 ) + y2 (x1 − x2 − b2 ). Kuhn-Tuckerovy podmínky jsou (P1)
L0x1
= 2x1 + y1 + y2 = 0,
L0x2
= 2x1 + y1 − y2 = 0,
(P2)
y1 (x1 + x2 − b1 ) = 0,
y2 (x1 − x2 − b2 ) = 0,
Pro x1 , x2 platí x1 + x2 ≤ b1 , x1 − x2 ≤ b2 a y1 ≥ 0, y2 ≥ 0. Řešení se rozpadne na čtyři části: 1. Pro y1 = 0 a zároveň y2 = 0 řešíme systém rovnic 2x1 + y1 + y2 = 0, 2x2 + y1 − y2 = 0 a jeho řešení je x1 = 0, x2 = 0. Přičemž z podmínek (P1) a požadavku y1 , y2 ≥ 0 plyne, že musí být b1 ≥ 0 a b2 ≥ 0. 2. Pro y1 = 0 a zároveň x1 − x2 − b2 = 0 řešíme systém rovnic 2x1 + y1 + y2 = 0, 2x2 + y1 − y2 = 0, x1 − x 2 − b 2 = 0
a jeho řešení je x1 = b22 , x2 = − b22 . Přičemž ze stejných důvodů jako v předchozí části plyne, že b1 ≥ 0 a b2 < 0. 3. Pro y2 = 0 a zároveň x1 + x2 − b1 = 0 řešíme systém rovnic 2x1 + y1 + y2 = 0, 2x2 + y1 − y2 = 0, x1 + x 2 − b 1 = 0
a jeho řešení je x1 =
b1 2,
x2 =
b1 2.
76
Přičemž b1 < 0 a b2 ≥ 0.
4. Pro x1 + x2 − b1 = 0 a zároveň x1 − x2 − b2 = 0 řešíme systém rovnic 2x1 + y1 + y2 = 0, 2x2 + y1 − y2 = 0,
x1 + x2 − b1 = 0, x1 − x 2 − b 2 = 0
a jeho řešení je x1 =
b1 +b2 2 ,
b1 −b2 2 .
x2 =
Přičemž b1 < 0 a b2 < 0.
Pro řešení úlohy celkem dostáváme [0, 0] b1 ≥ 0, b2 ≥ 0, b2 , − b2 b1 ≥ 0, b2 < 0, b21 b1 2 [x∗1 , x∗2 ](b) = b1 < 0, b2 ≥ 0, 2, 2 b+1 +b2 , b1 −b2 b < 0, b < 0 1 2 2 2 a pro její hodnotu
F (b1 , b2 ) =
Nyní určíme funkci
0 1
ϕ(y1 , y2 ) =
2 2 b2 1 2 2 b1 1 2 2 (b1
b1 ≥ 0, b2 ≥ 0, b1 ≥ 0, b2 < 0,
+
b22 )
inf
[x1 ,x2 ]∈R2
b1 < 0, b2 ≥ 0, b1 < 0, b2 < 0.
L(x1 , x2 , y1 , y2 ).
Platí L0x1 = 2x1 + y1 + y2 = 0, L0x2 = 2x2 + y1 − y2 = 0, a tedy x1 =
−y1 + y2 −y1 − y2 , x2 = . 2 2
Po dosazení dostaneme ϕ(y1 , y2 ) = − 21 y12 − 12 y22 − b1 y1 − b2 y2 a určíme ϕ0y1 = −y1 − b1 = 0, ϕ0y2 = −y2 − b2 = 0. Odtud dostaneme stacionární bod y1 = −b1 , b1 + b 2 x1 = , 2
y2 = −b2 , b1 − b 2 x2 = . 2
Protože v duální úloze musí být y1 ≥ 0 [0, 0] [0, −b2 ] [y1∗ , y2∗ ](b) = [−b1 , 0] [−b1 , −b2 ]
y2 ≥ 0, dostáváme
77
b1 ≥ 0, b2 ≥ 0, b1 ≥ 0, b2 < 0,
b1 < 0, b2 ≥ 0,
b1 < 0, b2 < 0.
a tedy ϕ∗ (b1 , b2 ) =
0 1
2 2 b2 1 2 2 b1 1 2 2 (b1
b1 ≥ 0, b2 ≥ 0,
b1 ≥ 0, b2 < 0, b1 < 0, b2 ≥ 0,
+ b22 ) b1 < 0, b2 < 0.
Dostali jsme tedy rovnosti F (b1 , b2 ) = ϕ∗ (b1 , b2 ) a Fb0 (b1 , b2 ) = −y ∗ (b1 , b2 ), které dokazují platnosti vztahu duality a rovnost z části 3) Věty 4.1. N Využijeme-li předchozí věty výsledky z Kapitoly 3, bezprostředně dostáváme následující tvrzení. Důsledek 4.32. Nechť P je konvexní, f, g 1 , . . . , gm jsou konvexní na P , F (0) > −∞ a existuje x ¯ ∈ P takové, že g(¯ x) < 0. Pak (i) Funkce F (b) je spojitá v bodě b = 0. (ii) Pro libovolné h ∈ Rm existuje jednostranná derivace F 0 (0, h) = max h−y ∗ , hi. y ∗ ∈Y (0)
(iii) Funkce F je diferencovatelná v bodě b = 0 právě tehdy, když množina Y (0) = {y ∗ } je jednoprvková. Pak platí F 0 (0) = −y ∗ . Důkaz. Z existence x ¯ ∈ P , pro něž g(¯ x) < 0 plyne, že 0 ∈ int B. Tvrzení (i) až (iii) nyní plynou z vlastností konvexních funkcí v relativně vnitřním bodě jejich definičního oboru. Důsledek 4.33. Nechť jsou splněny předpoklady Věty 4.30 a nechť e i = (0, . . . , 0, 1, 0, . . . , 0) (jednička je na i-tém místě) i ∈ {1, . . . , m} (i) Jestliže yi∗ = 0 pro nějaký vektor y ∗ ∈ Y (0), pak F (αei ) = F (0) pro všechna α ≥ 0. (ii) Jestliže yi∗ > 0 pro každý vektor y ∗ ∈ Y (0), pak F (αei ) < F (0) pro všechna α > 0. Důkaz. i) V důkazu Věty 4.30 jsme ukázali, že pro každý vektor y ∗ ∈ Y (0) platí F (0) ≤ F (b) + hy ∗ , bi. Dosadíme-li za b = αei , dostáváme F (αei ) ≥ F (0). Protože F (b) je rostoucí, současně musí platit F (αe i ) ≤ F (0) a tedy F (αei ) = F (0). ii) Ze vztahu F 0 (0, ei ) = max h−y ∗ , ei i = max −y ∗ < 0, y ∗ ∈Y (0)
y ∗ ∈Y (0)
tedy F (αei ) < F (0) pro α > 0 dostatečně malá a z monotonie F plyne, že nerovnost platí pro všechna α > 0.
78
Nyní ukážeme, jak lze dokázat vztah duality f ∗ = ϕ∗ a některé další vztahy mezi úlohami (4.1) a (4.15) pomocí Fenchelovy transformace funkce F (b). Uvažujme úlohu f (x) → min, gi (x) + bi ≤ 0, i = 1, . . . , m, x ∈ P ⊆ Rn (zde na rozdíl od úlohy (4.20) uvažujeme z formálních důvodů omezení ve tvaru gi (x) + bi ≤ 0 místo gi (x) ≤ bi ) a nechť F (b) je hodnota této úlohy. Pak pro konjugovanou funkci této funkce F ∗ (y) = sup{hy, bi − F (b)} = sup {hy, bi − b∈Rn
b∈B
=
sup {−
b∈Rm
inf
x∈P,g(x)≤b
inf
x∈P,g(x)+b≤0
[f (x)−hy, bi]} = sup
f (x)} =
sup
b∈Rm x∈P,g(x)≤−b
{hy, bi−f (x)} =
= sup sup {hy, bi − f (x)} = x∈P b≤−g(x)
= =
supx∈P {−hy, g(x)i − f (x)} ∞
je-li y ≥ 0, jinak
− inf x∈P {f (x) + hy, g(x)i} je-li y ≥ 0 ∞ jinak.
Tedy F ∗ (y) = −ϕ(y) a duální úlohu (4.15) lze psát ve tvaru −F ∗ (y) → max,
y ≥ 0.
Dále platí F ∗∗ (0) = sup{h0, yi − F ∗ (y)} = sup{−F ∗ (y)} = sup ϕ(y) = ϕ∗ . y≥0
y≥0
y≥0
Je-li nyní funkce F spojitá v bodě 0, pak podle Věty 3.46 F (0) = F ∗∗ (0), tedy platí vztah duality f ∗ = ϕ∗ . Tedy každá podmínka, zajišťující spojitost funkce F v bodě 0 je dostatečnou podmínkou pro platnost vztahu duality. Například Slaterova podmínka regularity spolu s předpokladem F (0) > −∞ implikují, že 0 ∈ int B a tedy F je spojitá podle Věty 3.21. Tento alternativní přístup k teorii duality založený na Fenchelově transformaci (přístup presentovaný v tomto textu je založen na pojmu vektoru Kuhna-Tuckera) lze nalézt v řadě učebních textů věnovaných konvexní analýze a optimalizaci v prostorech konečné dimenze, viz např. [25]. Na závěr tohoto odstavce si ukážeme dvě z možných ekonomických interpretací vektorů Kuhna-Tuckera úlohy (4.20). K vysvětlení první z nich, předpokládejme, že nějaký výrobní proces je charakterizován n-rozměrným vektorem x ∈ Rn , který popisuje výsledek výrobního procesu. Nechť k realizaci tohoto procesu je třeba m zdrojů, jejichž spotřeba při výrobě charakterizované vektorem x je popsána m-ticí funkcí g(x) = (g 1 (x), . . . , gm (x)), g(x) ≥ 0. Dále nechť b = (b1 , . . . , bm ), b ≥ 0 je vektor zásob zdrojů a f (x) 79
je zisk při realizaci výrobků charakterizovaných vektorem x a P ⊆ R n je množina technologicky možných výrobních procesů. Budeme předpokládat, že funkce f je konkávní, množina P konvexní a funkce g je konvexní (tyto požadavky mají přirozenou ekonomickou interpretaci), 0 ∈ P a g(0) = 0 (podnik může nevyrábět a při nulové výrobě se nespotřebovává žádný ze zdrojů). Nyní vyšetřujme úlohu f (x) → max, g(x) ≤ b, x ∈ P
(4.22)
a označme Φ(b) hodnotu této úlohy. Není obtížné ověřit, že jsou splněny předpoklady Věty 4.30 (s funkcí −f místo f ). Nechť x ∗ = x∗ (b) je řešením (4.22), Φ(b) = f (x∗ (b)), tj. x∗ (b) je optimální výrobní proces při omezení zdrojů daném vektorem b. Předpokládejme dále pro jednoduchost, že úloha ekvivalentní k (4.22) −f (x) → min, g(x) ≤ b, x ∈ P má jediný Kuhn-Tuckerův vektor y ∗ (b). Jestliže při optimální skladbě výroby není i-tý zdroj zcela spotřebován, tj. gi (x∗ (b)) < bi , pak z podmínek komplementarity plyne y i∗ (b) = 0 a podle Důsledku 4.33 zvětšení zásob i-tého zdroje nevede ke zvýšení zisku (Φ(b + αei ) = Φ(b)). V tomto případě říkáme, že i-tý zdroj není deficitní. V opačném případě, je-li yi∗ (b) > 0, se i-tý zdroj nazývá deficitní a zvětšení jeho zásob vede ke zvýšení zisku (Φ(b+αe i ) > Φ(b)), přičemž Φ0 (b, h) = hy ∗ (b), hi, tj. Φ0 (b, ei ) = yi∗ (b) a odtud plyne, že největší „lokálníÿ nárůst risku zajistí zvětšení zásob toho zdroje, pro jehož index i platí y i∗ (b) ≥ yj (b), j = 1, . . . , m. Jestliže je možno zvyšovat zásoby všech zdrojů, je vhodné je zvy∗ (b)). šovat proporcionálně komponentám vektoru y ∗ (b) = (y1∗ (b), . . . , ym Jako poslední v této kapitole uvedem další možnou ekonomickou aplikaci vektoru Kuhna-Tuckera, která je založena na vztahu (4.21). Uvažujme opět extremální úlohu závislou na parametru (4.20). Budeme předpokládat, že stávající rozhodovací proces (přesněji, jeho omezení) je charakterizován vektorem b = 0, tj., minimum cílové funkce na přípustné množině X(0) je F (0). Stejně jako v předcházející části této kapitoly Y (b) značí množinu Kuhn-Tuckerových vektorů úlohy (4.20). Předpokládejme, že s optimálním výsledkem F (0) nejsme spokojeni a chceme dosáhnout vhodnou změnou rozhodovacích omezení (tj. vektoru b) lepšího výsledku F (b) < F (0) (hodnotu cílové funkce můžeme např. interpretovat jako ztráty). Dále předpokládejme, že náklady na jednotkovou změnu omezení b jsou charakterizovány vektorem y ∈ Rm , tedy změna omezujících omezení z b = 0 na hodnotu b “stojí” hy, bi. Protože hodnotu cílové funkce uvažujeme v termínech ztrát, bereme tuto hodnotu se záporným znaménkem. 80
Interpretace nerovnosti F (b) ≥ F (0) − hy ∗ , bi,
(4.23)
tj. nerovnosti (4.21) je následující. Ztráty na změnu omezujících omezení jsou −hy, bi. Jestliže vektor y charakterizující jednotkové náklady na změnu omezujících omezení (vektor b), pak nerovnost (4.23) znamená že ztráty vynaložené na změnu těchto omezení (např. náklady na vymáhání dluhů, které bychom chtěli investovat) jsou spolu spolu s novou hodnotou F (b) vyšší než při původních rozhodovacích omezeních. V tomto případě to znamená, že ztráty spojené se změnou rozhodovacích omezení jsou vyšší než efekt, kterého změnou rozhodovacích omezení dosáhneme. Tedy, jestliže vektor charakterizující náklady na změnu rozhodovacích omezení je Kuhn-Tuckerovým vektorem původní rozhodovací úloha, pak snaha o tuto změnu rozhodovacích omezení není účelná, neboť ztráty vynaložené na změnu rozhodovacích omezení jsou vyšší než snížení ztrát, kterého tímto dosáhneme! Více informací o uplatnění metod konvexní analýzy a matematického programování v ekonomii je možno nalézt např. v [].
4.5
Cvičení
1. Určete duální úlohu k dané úloze a prověřte platnost vztahu duality f ∗ = ϕ∗ . (i) f (x) = x2 + 2x + 2 → min, x ≤ 1,
(ii) f (x) = x log x → min, 0 < x ≤ e (nerovnost x > 0 uvažujte jako přímé omezení). (iii) f (x) = 12 hAx, xi + hd, xi → min, Ax ≤ b, kde C ∈ Rn×n je symetrická positivně definitní matice, d ∈ R n , A ∈ Rm×n , b ∈ Rm .
2. Určete závislost hodnoty dané úlohy F (b)na parametru b, určete duální úlohu k této úloze a prověřte platnost vztahů F (b) = Φ(b) a ∂F (b) = −Y (b). √ (i) f (x) = 1 + x2 , x ≤ b, x, b ∈ R. (ii) f (x) = e|x| , x ≤ b.
(iii) f (x1 , x2 ) = x21 + 2x1 x2 + 2x22 , x1 − x2 ≤ b. Q P (iv) f (x) = nj=1 xλi i , ni=1 xi ≤ b, xi , λi > 0, i = 1, . . . , n. P Pn √ (v) f (x) = − ni=1 αi xi , i=1 βi xi ≤ b, αi , βi > 0, xi ≥ 0, i = 1, . . . , n. P P (vi) f (x) = ni=1 αxii , ni=1 βi xi ≤ b, xi > 0, αi , βi > 0, i = 1, . . . , n. 81
82
Literatura
83
[1] R. J.Aumann, S. Hart (editors), Handbook of Game Theory with Economic Applications, North-Holland, Amserdam 1992. [2] M. Aoki, Introduction to Optimization Techniques. Fundamentals and Applications of Nonlinear Preogramming. Macmillan Series in Applied Computer Sciences. New York–London, 1971. [3] sc V. G. Boltanskij, I. M. Jaglom, Vypuklye figury, Moskva, 1961. [4] J. M. Borwein, A. S. Lewis, Convex Analysis and Nonlinear Optimization. Theory and Examples. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Springer-Verlag, New York, 2000. [5] B. Dacorogna, Direct Methods of the Calculus of Variations, Springer Verlag, Berlin, 1989. [6] Z. Došlá, O. Došlý, Diferenciální počet funkcí více proměnných, Skriptum MU, Brno, 2003. [7] Z. Došlá, O. Došlý, Metrické prostory - teorie a příklady, Skriptum MU, Brno 2000. [8] Z. Došlá, J. Kuben, Diferenciální počet funkcí jedné proměnné, Skriptum MU, Brno, 2003. [9] S. Fišnarov´ s, Metody kvadratického programování, Diplomová práce, MU Brno, 2001. [10] M. Hamala, Nelineárne programovanie, Vydavatelstvo technickej a ekonomickej literatúry, Bratislava, 1972. [11] J. Herman, R. Kučera, J. Šimša, Metody řešení matematických úloh I, SPN Praha, 1990. [12] V. Jarník, Diferenciální počet I, Academia, Praha 1974. [13] V. Jarník, Diferenciální počet II, Academia, Praha 1974. [14] L. G. Kachain, A polynomial algorithm in linear programming, Dokl. Akad. Nauk. SSSR, 244 (1979), 1093–1096 (v ruštině). [15] L. Kučera, Kombinatorocké algoritmy, SNTL, Praha, 1983. [16] H. P. Künzi, W. Krelle, Nichtlinear Programmierung, Springer Verlag, Berlin-Götingen-Heidelberg, 1962 (existuje český překlad). [17] K. Leichtweiss, Konvexe Mengen, VEB Deutsche Verlag der Wisseenschaften, Berlin, 1980. 84
[18] V. Novák, Diferenciální počet funkcí více proměnných, skriptum University J. E. Purkyně, Brno, 1983. [19] Alena Prágerová, Diferenční rovnice, Praha, SNTL, 1971. [20] R. T. Rockafeller, Convex Analysis, Princeton University Press, New Jersey, 1970. [21] J. Stoer, Ch. Witzgall, Convexity and optimization in finite dimensions. Die Grundlehren der mathematischen Wissenschaften, Band 163 Springer-Verlag, New York-Berlin 1970. [22] A. G. Sucharev, A. V. Timochov, V. V. Fedotov, Kurs metodov optimizacii, Nauka, Moskva, 1986. [23] F. P. Vasiljev, Metody rešenia extremálnych zadač, Nauka, Moskva, 1891. [24] H. P. Williams, Fourier’s method of linear programming and its dual. Amer. Math. Monthly 93 (1986), no. 9, 681–695. [25] M. Willem, Analyse Convexe et Opmization, 3 e edition, Editions Ciaco, Louvain la Neuve, 1989.
85
