15. Wykład XV, 22.I.2010

Przystępujemy do opisu działania CLA; komentarze objaśniające będą podane później, by nie zaciemniać głównej, pięknej pętli algorytmu.

Zakładamy już do końca, że Σ>0 oraz μ1,μ2,,μk. To pociąga, że macierze ΣIN, a także MIN, są odwracalne dla wszystkich IN1, 2,,k – patrz Twierdzenie w Wykładzie XIV. Algorytm CLA odnajduje, na nowo i niezależnie od metody prób opartej na twierdzeniu Karusha-Kuhna-Tuckera (patrz Wykład X), łamaną wierzchołkową Ł¯ zbudowaną z portfeli relatywnie minimalnego ryzyka. Względnie– w oryginalnej prezentacji Markowitza w [22] – tylko łamaną efektywną, co jest różnicą mało istotną z punktu widzenia metodologii CLA. Najczęściej sprawnie i bezbłędnie odnajduje on tych ,,kilkaset boków” Ł¯, jak wyraża się Markowitz, spośród setek tysięcy czy milionów ścian sympleksu, przez które à priori mogłaby przebiegać Ł¯. Redukuje problem o potencjalnej złożoności wykładniczej od k do problemu w praktyce wielomianowego od k, i to wielomianowego – wydaje się, jest to otwarte pole do badań – bardzo niskiego stopnia.

Skoncentrujmy uwagę na jednej ustalonej ścianie IN, w której leży jeden z boków Ł¯. W tym obecnym spojrzeniu może to nawet być jeden z wierzchołków sympleksu Δk, oczywiście taki, przez który przechodzi Ł¯. Tzn. #IN=1 jest możliwe.
Zakładamy, że algorytm już doszedł do boku Ł¯ leżącego w IN i biegnie po nim (lub stoi, gdy #(IN)=1), zmniejszając przy tym wartość parametru λE.
Jak długo to się dzieje, tzn. jak długo utrzymuje się relatywna optymalność portfeli – punktów na tym boku? Oczywiście, z twierdzenia K-KT, dopóki

xi=αi+βiλE>0dlaiIN

oraz

ηj=γj+δjλE0dlajOUT.

Dodatniość, względnie nieujemność, może przy zmniejszaniu λE popsuć się tylko w tych wyrażeniach, w których współczynniki przy λEdodatnie. Wynikają stąd naturalne dolne ograniczenia

λE>-αiβidlaiIN,βi>0

oraz

λE-γjδjdlajOUT,δj>0.

Kresem dolnym optymalności portfeli na ścianie IN, wyrażonym w terminach parametru λE, jest zatem

λlowIN=defmaxβi>0δj>0-αiβi,-γjδj, (15.1)

gdzie też oczywiście iIN, jOUT. Gdy #IN=1, IN=i, wtedy nie ma aktywnej nierówności na temat xi, są tylko pewne nierówności na temat ηj, ji, związane z optymalnością wierzchołka numer i oraz związanymi z tym możliwymi wartościami parametru λE.56wtedy, jak wiadomo, rozwiązania warunków Karusha-Kuhna-Tuckera nie dają jednoznacznie wyznaczonych współczynników Lagrange'a λ i λE

Algorytm będzie ,,wiedział”, gdzie skierować się dalej (gdzie leży następny bok łamanej Ł¯) gdy zawsze tylko jedna liczba z tych wymienionych po prawej stronie równości (15.1) realizuje dane maksimum. W celu zapewnienia skuteczności algorytmu CLA będziemy to zakładali do końca wykładu. Dokładniej,

Definicja 15.1

O modelu Markowitza Σ,μ, Σ>0, μ1,μ2,,μk, mówimy, że ma
niezdegenerowane parametry gdy

(αiβi,γjδj|iIN,jOUT,βi>0,δj>0)IN{1, 2,,k}. (15.2)

Komentarz po definicji: zakładając w dalszym ciągu niezdegenerowanie parametrów modelu, zakładamy w tym wykładzie więcej, niż jest potrzebne do sprawnego przebiegu algorytmu (choć i tak mniej, niż u Markowitza w [22]). Bo przecież nie wszystkie ściany IN muszą być odwiedzone przez konkretną łamaną Ł¯ oraz, dla jakiegokolwiek danego  IN, który występuje w konkretnym przebiegu algorytmu, nie wszystkie ułamki wymienione w (15.2) muszą być różne! Tylko największy  z nich musi być różny od wszystkich pozostałych.

Uwaga 15.1

Gdy patrzymy na formułę (15.1), czy też na dualną formułę (15.22), która pojawi się [dopiero] pod koniec tego wykładu, nie sposób nie zauważyć ich dużego podobieństwa z formułami, jakie występują w programowaniu liniowym. Można przykładowo spojrzeć na wzory na stronie 126 w klasycznej książce [7] poświęconej programowaniu liniowemu, czy też na towarzyszącą im dyskusję na stronach sąsiednich tamże.
W istocie to, czym od strony technicznej zajmuje się analiza portfelowa, to programowanie kwadratowe, oczywiście ze specyficznymi ograniczeniami ,,portfelowymi”. Ekstremalizacja funkcji wypukłej bądź wklęsłej (bądź też, jak w Wykładzie XIV, pseudo-wklęsłej), a więc zasadniczo twierdzenie K-KT, nierówności opisujące wypukłą dziedzinę takiej funkcji i równocześnie pochodne nierówności typu K-KT wiążące się z ekstremalizacją tej funkcji – stąd biorą się dwie rodziny ułamków, w których teraz łącznie szukamy liczby najmniejszej bądź największej. O tyle57słynna Passentowska mała różnica, którą chciałoby się umieć zagrać – na jakim instrumencie? programowanie kwadratowe jest bogatsze od liniowego. Przypominamy jeszcze raz tytuł przełomowej pracy [14]: nonlinear programming. Warto też jeszcze rzucić okiem na sam tytuł książki [17], albo też przewertować ją dokładniej.
W książce Gassa jedna rodzina ułamków jest poddawana ekstremalizacji w każdym kroku algorytmu sympleks, zaś teraz są temu poddawane równocześnie dwie rodziny różnego pochodzenia.

Opis algorytmu CLA dla modeli z niezdegenerowanymi parametrami

A. Zaczynamy od IN=i, gdzie μi=max1lkμl=Emax, tzn. od wierzchołka ei, w którym zaczyna się łamana wierzchołkowa Ł¯. Algorytm przez długi czas stoi na tym wierzchołku, podczas gdy parametr λE maleje od + do wartości λlowi. Ta wartość progowa, na mocy niezdegenerowania parametrów modelu, jest równa -γjδj dla jednego jedynego ji, δj>0. Stąd wiemy, że następnym etapem będzie IN=INj=i,j, w którym parametr λE będzie się zmniejszał poniżej wartości λlowIN.

B. Załóżmy, że już trwa jakiś etap IN w algorytmie, zaś λE zmniejsza się poniżej poznanej już poprzedniej wartości progowej. Afiniczne od λE wzory na xi, iIN, opisują bok Ł¯ na ścianie IN, dla λE poniżej poprzedniej wartości progowej aż do wartości λlowIN danej wzorem (15.1). Na mocy niezdegenerowania parametrów modelu, w (15.1) jest jeden jedyny indeks iIN lub jOUT taki, że λlowIN=-αiβi lub λlowIN=-γjδj.

Następny etap algorytmu to IN=IN\i w pierwszym przypadku, względnie IN=INj w drugim, przy czym parametr λE zmniejsza się w nim poniżej λlowIN (do jakiejś wartości lub do -). W ten sposób rekurencyjnie podany jest już cały algorytm, opisujący bok po boku całą łamaną wierzchołkową Ł¯. Ostatni etap to, oczywiście, IN=i, μi=min1lkμl=Emin, zaś λE zmniejsza się w nim od poprzedniej wartości progowej do - (przyjmujemy, że maksimum pustego zbioru liczb wynosi -).

Komentarz po opisie algorytmu. Stosując algorytm CLA, rekurencyjnie wędrujemy po niektórych ścianach sympleksu Δk, włączając w to niektóre wierzchołki, cały czas ściśle kontrolując malejącą ewolucję wiodącego parametru λE. Po drodze uzyskujemy parametryczne opisy boków łamanej wierzchołkowej Ł¯ wraz z progowymi wartościami parametru λE odpowiadającymi wierzchołkom spójnej łamanej Ł¯.

Algorytm jest wydajny w 100% – wędrujemy w nim dokładnie po tych ścianach Δk, przez które przebiega łamana Ł¯. Czasami zdarza się – o czym Markowitz w [22] wydaje się nie wiedzieć – że ten maksymalnie wydajny algorytm musi odwiedzić wszystkie 2k-1 niepuste ściany Δk. Tak właśnie dzieje się w przykładzie Więcha omówionym w Wykładzie X, i też w przykładzie Iwanickiego w wymiarze 5 omawianym tutaj poniżej (czy też w, tylko wzmiankowanym pod koniec Wykładu VII, nie–praw–do–po–dob–nym przykładzie Iwanickiego w wymiarze 6).

Przykład 15.1 (Więch [29], kontynuacja)

Odnajdywanie łamanej Ł¯ zaczynamy od IN=3, bo μ3=30=Emax. λlow3=15532, wchodzi indeks 2, IN=2,3. Kolejne λlow2,3=16764, wychodzi indeks 3, IN′′=2. Kolejne λlow2=198, wchodzi indeks 1, itd. Z tabeli w Wykładzie X odczytujemy, jadąc od dołu do góry, kolejne etapy. Po 1, 2 etap 1, 2, 3, następnie 1,31,3,41,2,3,41,2,42,42,3,43,441,41.

Odpowiednie wartości progowe λlow są w środkowej kolumnie tamtej tabeli, też jadąc od dołu do góry: λlow1,2=53419392, itd. Istotnie zatem, łamana Ł¯ w przykładzie Więcha odwiedza wszystkie podzbiory zbioru 1, 2, 3, 4 poza pustym. Ten przykład w chwili pojawienia się jesienią 2001 stanowił prawdziwą sensację.

A oto jak łamana wierzchołkowa w przykładzie Więcha wygląda w rzucie na płaszczyznę ekranu bądź rysunku, przy odpowiednim wyborze kierunku rzutowania:

[w wersji pdf Rysunek 15.1 jest na następnej stronie]

\par
Rys. 15.1. Reprodukcja rysunku Czuby z roku 2007.

Jeszcze bardziej intrygujący przykład podał w roku 2007 w swojej pracy licencjackiej [9] student A. Iwanicki; anonsowaliśmy to odkrycie już w Wykładzie VII.58Iwanicki wyszedł od programu dla Critical Line Algorithm (w Visual Basicu) autorstwa G. P. Todda, podanego w [22], lecz udoskonalił go przez wprowadzenie pomysłowych shortcutów i dodanie własnej części probabilistycznej – losowanie próbek danych. Jego program wykonywał przez jedną noc najpierw dziesiątki, a potem nawet setki tysięcy przebiegów algorytmu CLA na próbnych danych! Przykład podany w tekście wykładu został znaleziony po około 8 dobach poszukiwań netto. Bez algorytmu CLA, i bez książki [22] jako wstępnego inputu, nie byłoby to możliwe.  Jest to najbogatszy możliwy przykład w wymiarze 5. Ma on granicę minimalną składającą się z 26 kawałków różnych hiperbol, zaś granica efektywna składa się w nim z (aż) 19 kawałków różnych hiperbol!

Σ=1.0808103.4986205.155060-0.1376494.3929403.49862025.24240049.611500-1.70799039.8004005.15506049.611500233.167000-3.10818095.732900-0.137649-1.707990-3.1081800.341958-2.4981404.39294039.80040095.732900-2.49814067.339300,μ=1.5720404.2116606.351950-0.3651595.352790.

Zgodnie z tym, co wyżej zaanonsowane, łamana wierzchołkowa okazuje się mieć tu aż 25-5-1=26 boków, natomiast algorytm CLA odnajduje ją w 31=25-1 krokach IN,  1#IN5. Kolejne kroki są następujące. (Przy wierzchołkach dających punkty załamania granicy minimalnej podajemy w nawiasach przedziały dla ,,nadstycznego” parametru λE; dyskusja nt tych przedziałów – patrz Stwierdzenie 15.1 niżej. Wielkości λhi są tożsame z wielkościami λlow w etapach bezpośrednio poprzedzających, porównaj Obserwacja 15.1, część A, poniżej.)

IN=33,55λhi=28.417,λlow=24.1332,52,3,52,3
2λhi=11.386,λlow=8.2371,21,2,31,2,3,51,2,5
1,51,3,51,31λhi=0.852,λlow=0.6291,41,3,4
1,3,4,51,4,51,2,4,51,2,3,4,51,2,3,41,2,42,4
2,3,42,3,4,52,4,54,53,4,53,44.
Ćwiczenie 15.1

Policzyć do końca tę łamaną wierzchołkową, a następnie zobrazować ją na rzucie sympleksu Δ5 na płaszczyznę (możliwym, tak jak możliwy jest rzut hipersześcianu na płaszczyznę, itd.).

Uzasadnienie poprawności algorytmu CLA wraz z dodatkowymi informacjami na jego temat.

Chcemy dokładniej przyjrzeć się, co się dzieje, gdy łamana wierzchołkowa Ł¯, odkrywana stopniowo przez algorytm CLA, zmienia

(A) ścianę IN, #IN2, na inną ścianę IN,#IN2, względnie

(B) ścianę IN, #IN2 na wierzchołek, np i, po którym z kolei łamana Ł¯ wchodzi w ścianę IN,#IN2.

Uwaga 15.2

Sytuacje (A) i (B) można też scharakteryzować/rozróżnić inaczej. Mianowicie, pamiętamy jeszcze z dowodu Twierdzenia 10.1, że parami rozłączne przedziały EIN, #IN2, dają w sumie z węzłami wyróżnionymi cały przedział Emin,Emax. W sytuacji (A) domknięcia przedziałów EIN oraz EIN zahaczają się zatem jednym punktem infEIN=supEIN. Jest to jeden z węzłów w Twierdzeniu 10.1, przy czym węzeł niewyróżniony: łamana przechodząc ze ściany IN na ścianę IN nie przechodzi przez żaden wierzchołek sympleksu. Ten wspólny kres leży więc w dokładnie jednym z przedziałów EIN, EIN.
Natomiast sytuacja (B) to po prostu inne wypowiedzenie zdania `μi jest węzłem wyróżnionym' – porównaj definicję węzłów wyróżnionych w dowodzie Twierdzenia 10.1 na początku Wykładu XI.

Tak więc, w telegraficznym skrócie, sytuacja (A) – węzły niewyróżnione, sytuacja (B) – węzły wyróżnione.

W naszych rozważaniach pomocna będzie funkcja wypukła

Emin,EmaxEσ2xE, (15.3)

której dotyczył już Wniosek 11.1 w Wykładzie XI.

Jako funkcja wypukła, ma ona wszędzie skończone pochodne jednostronne, zaś w punktach różniczkowalności ma pochodną o wartości 2λEE, gdzie λE() to funkcja związana z danym bokiem łamanej Ł leżącym na jakiejś ścianie 1-wymiarowej. (Przy rygorystycznym podejściu ta funkcja powinna być oznaczana symbolem λINE(). Na ścianach IN, #IN2, współczynniki Lagrange'a λ i λE są wyznaczone jednoznacznie jako funkcje portfela wierzchołkowego, a więc też jako funkcje E.) Wynika to wprost z Obserwacji 6.1 w Wykładzie VI; wspominaliśmy nie raz, że tamta obserwacja jest technicznie bardzo użyteczna.

W związku z tym globalna funkcja ΛE,

Emin,EmaxEΛEλEE

jest ściśle rosnąca i kawałkami liniowa, z możliwymi skokami w górę:

— w węzłach wyróżnionych, jak np w przykładzie Więcha na rysunku powyżej,

\par
Rys. 15.2. Reprodukcja rysunku Teklińskiego z roku 2009.

— co widzieliśmy przy okazji rozwiązywania zadania sprawdzającego z Wykładu X,

— oraz być może  w jakichś węzłach niewyróżnionych – tego jeszcze w tym momencie nie wiemy; w przykładzie Więcha – bez takich skoków w węzłach niewyróżnionych.

Odcinki, na których funkcja EΛEλEE jest liniowa, etykietujemy odpowiednimi zbiorami indeksów IN – nazwami ścian, których dotyczą. Węzły wyróżnione, w których jest skok funkcji ΛE, nazywamy pojedynczymi indeksami – numerami odpowiednich wierzchołków sympleksu. Przejście od parametru E do λE jest w takich węzłach rodzajem blow-upu: rozdmuchania punktu do odcinka [wartości parametru λE].

Niech dla IN : #IN2, EIN będzie jak w dowodzie w Wykładzie XI (zbiór wartości oczekiwanych wszystkich portfeli wierzchołkowych xE leżących na ścianie IN).

Niech ponadto, tym razem dla wszystkich IN niepustych, LIN oznacza zbiór wszystkich wartości współczynników Lagrange'a λE w rozwiązaniach warunków K-kT dla portfeli wierzchołkowych leżących na ścianie IN.

Gdy #IN2, jest to (wiemy to już!) przedział – obraz odpowiedniego przedziału EIN w globalnej funkcji ΛE:

LIN=ΛEEIN.

Natomiast gdy IN=i,

Liteż jest przedziałem, (15.4)

bo dla λE,λELi i s,t>0, s+t=1, nierówności wektorowe

Σei+λe-λEμ0,Σei+λe-λEμ0,

pociągają (też wektorową) nierówność

Σei+sλ+tλe-sλE+tλEμ0,

zaś warunki komplementarności

eiTΣei+λe-λEμ=0,eiTΣei+λe-λEμ=0

oczywiście pociągają warunek

eiTΣei+sλ+tλe-sλE+tλEμ=0 .

Istotnie zatem sλE+tλELi.

Uwaga 15.3

W języku używanym w tym Wykładzie XV, całkiem naturalnym dla algorytmu CLA, wierzchołek ei sympleksu Δk występuje po prostu jako singleton i – pewien jednoelementowy podzbiór zbioru numerów wszystkich wierzchołków sympleksu. Jest to na tyle naturalne, że nie powinno powodować nieporozumień.59Symbolika ei pozostaje w użyciu gdy opuszczamy język CLA, np tu powyżej w samym uzasadnieniu faktu (15.4), lub gdy dyskutujemy zachowanie konkretnych odwzorowań Markowitza w punktach ekstremalnych sympleksu.

Li jest zatem przedziałem, ok, lecz jakim konkretnie? To pytanie jest technicznie najtrudniejsze w całej dyskusji algorytmu CLA. Zajmiemy się nim za chwilę przy omawianiu sytuacji (B).

Wracamy teraz do alternatywy (A) versus (B) sformułowanej na początku dyskusji poprawności algorytmu CLA. (Rzecz dotyczy węzłów leżących w przedziale Emin,Emax. Po Uwadze 15.2 wiemy już, że to jest po prostu alternatywa węzły niewyróżnione versus wyróżnione.)

Ad (A) Wobec ścisłej wypukłości funkcji (15.3) i geometrycznej interpretacji współczynnika λE, przedziały LIN oraz LIN są rozłączne. Chcemy uzasadnić, że ich domknięcia przecinają się w jednym punkcie, który zresztą okaże się leżeć w jednym z tych przedziałów: LIN lub LIN.

Punkt E~ leżący w części wspólnej domknięć EIN¯ i EIN¯ jest w sytuacji (A) węzłem niewyróżnionym – wiemy to z dowodu (podanego w Wykładzie XI) Twierdzenia 10.1 o łamanej wierzchołkowej z Wykładu X.
Pokażemy, że w węźle niewyróżnionym E~ globalna funkcja ΛE nie  ma skoku. Dla ustalenia uwagi niech np E~EIN, E~EIN. Dla wartości E trochę mniejszych od E~ bierzemy, jednoznacznie określone w etapie IN dowodu z Wykładu XI, wielkości

x,λ,λE=xE,λE,λEE

oraz ich granice

xE~=limEE~-xE,λ~=limEE~-λE,λ~E=limEE~-λEE,

tak jak w tamtym dowodzie w Wykładzie XI. Z warunków dawanych przez twierdzenie K-KT mamy

ΣxE+λEe-λEEμ0,xETΣxE+λEe-λEEμ= 0

dla E trochę mniejszych od E~. Zatem również po przejściu granicznym EE~-,

ΣxE~+λ~e-λ~Eμ0,xE~TΣxE~+λ~e-λ~Eμ= 0.

Portfel xE~ leży na ścianie IN, zaś współczynniki Lagrange'a dla portfeli wierzchołkowych leżących na ścianie IN są wyznaczone jednoznacznie. A więc, w szczególności, λ~E=λEE~ liczone na boku leżącym na ścianie IN. Zatem to właśnie liczba λ~E okazuje się leżeć w części wspólnej domknięć przedziałów LIN i LIN. Dokładniej,

λ~E=infLIN=λlowIN, (15.5)

przy czym  λ~ELIN. Równocześnie

λ~E=supLIN (15.6)

oraz λ~ELIN, bo, przypominamy, LIN i LIN są rozłączne.

W sytuacji przeciwnej w (A): E~EIN, lecz E~EIN byłoby, oczywiście, LINsupLIN oraz λlowINLIN, natomiast równości (15.5)–(15.6) oczywiście pozostawałyby w mocy.

Wnioskiem z (15.5) i (15.6) jest równość

supLIN=λlowIN. (15.7)
Wniosek 15.1

Obraz [w odwzorowaniu Markowitza] każdego wierzchołka łamanej Ł, który nie jest wyróżniony (patrz Twierdzenie 10.1 w Wykładzie X), jest punktem gładkości granicy minimalnej Fmin. Innymi słowy, sytuacja (A) daje tylko punkty gładkości granicy minimalnej. Albo też – patrz Uwaga 15.2 powyżej – punkty na Fmin, których rzędne są węzłami niewyróżnionymi, są punktami gładkości granicy minimalnej.

Co natomiast skrywa się za sytuacją (B) mogącą wystąpić w przebiegu algorytmu, czyli – znowu Uwaga 15.2 – co się skrywa za węzłami wyróżnionymi? By odpowiedzieć, zajmijmy się tą sytuacją szczegółowo.

Ad (B) Teraz w łamanej Ł wierzchołek ei=xE~, E~=μi, sąsiaduje z bokiem leżącym na ścianie IN, na którym wartości E są większe od μi=E~, oraz z bokiem leżącym na ścianie IN, na którym wartości E są mniejsze od E~. Wartość E~ jest węzłem wyróżnionym w terminologii z Wykładu X.

Dla tego portfela wierzchołkowego ei nie ma  jednoznaczności współczynników Lagrange'a λ i λE – teoria Blacka się nie stosuje. Jednak oczywiście można robić przejścia graniczne przy EE~- analogicznie, jak w sytuacji (A), dostając, w oznaczeniach z tamtej sytuacji,

Σei+λ~e-λ~Eμ0,eiTΣei+λ~e-λ~Eμ= 0, (15.8)

gdzie λ~E=supLIN. I oczywiście też przy EE~+, dostając analogicznie

Σei+λ~~e-λ~~Eμ0,eiTΣei+λ~~e-λ~~Eμ=0, (15.9)

gdzie tym razem λ~~E=infLIN=λlowIN. Związki (15.8)–(15.9) pokazują zatem, że supLIN,λlowINLi. Wobec własności (15.4),

supLIN,λlowINLi. (15.10)

W istocie jest lepiej. Mianowicie

Stwierdzenie 15.1

Li=supLIN,λlowIN.

Pokażemy, że dowolna liczba λELi spełnia

supLINλEinfLIN=λlowIN, (15.11)

co łącznie z inkluzją (15.10) zakończy dowód.

Zauważamy w tym celu, że #IN=2=#IN, tzn ściany IN, IN są po prostu krawędziami  spotykającymi się w wierzchołku ei. Istotnie, warunki niezdegenerowania spełniane przez Σ,μ pociągają, że w algorytmie przy przejściu INi wypada tylko jeden indeks, np j, oraz przy przejściu iIN wchodzi też tylko jeden indeks, np j. Tak więc IN=i,j, gdzie μj>μi, oraz IN=i,j, gdzie μj<μi.

Fakt, że λELi oznacza, że dla λE i jakiegoś rzeczywistego współczynnika λ zachodzi

Σei+λe-λEμ0,eiTΣei+λe-λEμ=0,

a więc równość na składowej numer i oraz nieostre nierówności 0 na wszystkich pozostałych składowych, w szczególności na składowych nr j i j:

σii+λ-λEμi=0, (15.12)
σji+λ-λEμj0, (15.13)
σji+λ-λEμj0. (15.14)

Z (15.12) wyznaczamy λ i podstawiamy do nierówności (15.13)–(15.14), dostając odpowiednio

σji-σii+λEμi-μj0, (15.15)
σji-σii+λEμi-μj0 . (15.16)

Pamiętając, że μj<μi<μj, nierówności (15.15)–(15.16) dają

σii-σjiμi-μjλEσii-σjiμi-μj. (15.17)

Za chwilę okaże się, że nierówności (15.17) są dokładnie nierównościami (15.11). Policzymy w tym celu wielkość λEμi w teorii Blacka, gdy zbiorem aktywnych indeksów jest i,l, li (teoria Blacka w wymiarze 2). Wtedy portfele Blacka

xixl=E-μlμi-μlμi-Eμi-μl

mają wariancję

σ2E=1μi-μl2σiiE-μl2+2σilE-μlμi-E+σllμi-E2,

zaś λEμi=12σ2EE=μi (porównaj – kolejny raz! – Obserwacja 6.1 w Wykładzie VI). Liczymy zatem tę pochodną

λEμi=12μi-μl22σiiμi-μl+2σilμi-μl-1+0+0=σii-σilμi-μl.

Następnie, biorąc l=j, mamy

σii-σijμi-μj=λEμi=limEμi+ΛE=λlowIN.

Biorąc natomiast l=j, mamy

σii-σijμi-μj=λEμi=limEμi-ΛE=supLIN.

Istotnie więc, (15.17) są tożsame z (15.11). Dowód stwierdzenia jest zakończony.

Zauważmy, że ze Stwierdzenia 15.1 wynika

λlowi,supLi=supLIN,λlowIN. (15.18)

Jedną szczegółową ilustrację rachunków w tym ostatnim dowodzie (w ramach przykładu Iwanickiego w wymiarze 5 podanego już wcześniej w tym Wykładzie XV) podamy jeszcze później, po pewnym ogólniejszym podsumowaniu.

Pora na rekapitulację.  Przeprowadzona powyżej dyskusja algorytmu CLA pokazała, że w każdej z sytuacji (A) i (B), w opisie wzajemnych położeń zbiorów LIN, obok liczb λlowIN zdefiniowanych już jakiś czas temu wzorem (15.1), ważną – niejako dualną – rolę odgrywają też liczby supLIN. Naturalne jest w takiej sytuacji przyjąć następującą ogólną

Definicja 15.2
λhiIN:=supLIN,

gdzie IN to dowolny z etapów występujących  w danej realizacji algorytmu CLA.

(Podkreślamy, że w książce Markowitza [22] wielkości λlowIN i λhiIN definiowane są równocześnie. W tych wykładach – nie. Wiąże się to ze zbyt mocnymi warunkami niezdegenerowania zakładanymi u Markowitza. Nasze ,,niezdegenerowane parametry” są scharakteryzowane słabszymi warunkami; niżej piszemy o tym szerzej.)

Po przyjęciu takiego oznaczenia, w sytuacji (A) wzór (15.7) przybiera przejrzystą postać

λhiIN=λlowIN. (15.19)

Natomiast w sytuacji (B), równość (15.18) po wprowadzeniu tego nowego symbolu, oznacza

λhiIN=λlowi (15.20)

oraz

λhii=λlowIN. (15.21)
Wniosek 15.2

W każdym węźle wyróżnionym E~=μi globalna funkcja ΛE ma skok w górę równy λhii-λlowi>0. Innymi słowy, w sytuacji (B) w opisie przebiegu algorytmu CLA mamy zawsze punkt załamania granicy minimalnej w aspekcie M.

Zestawiając ten wniosek z poprzednim Wnioskiem 15.1, widzimy, że to dokładnie węzły wyróżnione okazują się być rzędnymi punktów załamania granicy minimalnej, zaś dany skok funkcji ΛE mierzy (co prawda na mniej kanonicznej płaszczyźnie wariancja – wartość oczekiwana i tylko z dokładnością do czynnika 2) wielkość takiego załamania.
Zapamiętajmy ten fakt; to jeden z kilku kluczowych momentów całego wykładu APRK1.

Uwaga 15.4

Dla każdego zbioru IN pojawiającego się w danej realizacji algorytmu CLA istnieje poręczna formuła na wielkość λhiIN, analogiczna do formuły (15.1) definiującej  λlowIN. Skoro jest to kres górny wartości λE, przy których na ścianie IN zachodzą warunki K-KT charakteryzujące portfele wierzchołkowe, zatem, rozwiązując wiadomy układ liniowych nierówności dających ograniczenia z góry  na λE,

λhiIN=min-αiβi,-γjδj|iIN,βi<0,jOUT,δj<0. (15.22)

(We wszystkich literach greckich w (15.22) dla lepszej czytelności opuszczony jest dolny indeks `IN. Ponadto, gdy w momencie startu algorytmu IN=i0  i  μi0=Emax, wtedy ten kres górny przyjmuje się równy +).

Z przeprowadzonych dotąd rozważań wynika

Obserwacja. 15.1

λlowIN<λhiIN dla każdego IN1, 2,,k pojawiającego się w danej realizacji algorytmu CLA.

A Jeśli w realizacji algorytmu CLA po etapie IN bezpośrednio następuje etap IN, to λlowIN=λhiIN.

Punkt wynika z samego opisu etapów algorytmu CLA. Natomiast punkt A, ogniskujący jak w soczewce całe piękno algorytmu CLA, wynika z równości (15.19), (15.20) i (15.21). Wzory na λlowIN (patrz (15.1) ) i na λhiIN (patrz (15.22), gdzie oczywiście IN trzeba zastąpić przez IN) nie mają na pierwszy rzut oka nic wspólnego. A jednak zawsze wyrażają te same wielkości!

Jest bardzo pouczające przeanalizować ten punkt A Obserwacji 15.1 powyżej na wybranych fragmentach przebiegu algorytmu CLA w przykładzie Iwanickiego (już wcześniej przytoczonym).

Kolejność następowania etapów w tamtym przykładzie jest znana, bo też już była podana wcześniej. I otóż, z przybliżeniem do trzech miejsc dziesiętnych po przecinku,

λlow3,5=28.417=λhi5,
λlow2,3=1.386=λhi2,
λlow1,3=0.852=λhi1. (15.23)

Ta ostatnia równość (15.23) jest szczególnie godna uwagi. Z jednej strony można obliczyć nawet dokładniej, że

λhi1=0.8523696,λlow1=0.6289798 .

Z drugiej strony walory, których wartości oczekiwane sąsiadują z μ1=1.57204 to: walor drugi (sąsiadowanie z góry, μ2=4.21166) oraz walor czwarty (sąsiadowanie z dołu, μ4=-0.365159). Kuszące jest spróbować zastosować poznane wcześniej (jeszcze w dowodzie Stwierdzenia 15.1) wzory: σ11-σ14μ1-μ4 na λlow1,  oraz  σ11-σ12μ1-μ2 na λhi1. W efekcie dostalibyśmy poprawnie

λlow1=1.08081--0.1376491.57204--0.365159=0.62898,

lecz także

σ11-σ12μ1-μ2=1.08081-3.498621.57204-4.21166=0.91597,

co już nie jest wartością występującą w (15.23). Czyżby rozwinięta wcześniej teoria przestawała pracować? Nic podobnego. Zapomnieliśmy tylko, że w aktualnym przebiegu CLA w przykładzie Iwanickiego, przed dojściem do wierzchołka 1 nie jesteśmy na krawędzi łączącej go z wierzchołkiem najbliższym w sensie wartości oczekiwanej (tj na krawędzi 1,2), tylko na krawędzi łączącej 1 z dalszym w sensie wartości oczekiwanej wierzchołkiem 3 (por. też (15.23) ).  Po uwzględnieniu tego przeoczenia

σ11-σ13μ1-μ3=1.08081-5.155061.57204-6.35195=0.85237=λhi1

już jak trzeba.

W charakterze komentarza do Obserwacji 15.1 powyżej należy stwierdzić, że słowa ,,pojawiającego się w danej realizacji algorytmu” są w tej obserwacji kluczowe.

Np w znanym nam przykładzie Mordona [przytaczanym tu od nowa dla wygody czytelnika]

Σ=931322124,μ=542,

na ścianie 1, 3, przez którą nie  przebiega łamana wierzchołkowa60  w tym doskonale rozpoznanym przykładzie przebieg algorytmu CLA to  11, 2(cała)22, 3(cała)3  wielkości λlowIN i λhiIN nabierają zaskakujących znaczeń. Dokładniej, wzory z Wykładu XIV dają formalnie na tej ścianie

x1=311+311λE,
η2=-1011-1011λE,
x3=811-311λE.

Zatem, liczone czysto formalnie, λlow1,3=max-311/311=-1,

λhi1,3=min--1011/-1011,-811/-311=min-1,83=-1 .

Pouczające jest porównać to z pochodną funkcji σ2E na tym boku. Tutaj σ2x=9x1 2+2x1x3+4x3 2 oraz x1=E-23, x3=5-E3. Prowadzi to do

12dσ 2dE=119E-319.

To wyrażenie jest równe -1 tylko przy E=2, a więc tylko w wierzchołku e3 sympleksu Δ3 (leżącym w domknięciu  ściany, której dotyczą tu obliczenia). Zatem wirtualne współczynniki λlow1,3=λhi1,3=-1 wychwytują ten jeden jedyny portfel na boku x2=0, który a) jest wierzchołkowy (tj leży na łamanej Ł) i b) w obrazie którego styczna do obrazu boku x2=0 jest tożsama  ze styczną do granicy minimalnej. Na rysunku poniżej, na – uwaga – płaszczyźnie R2σ2,E, ta wspólna styczna w punkcie M~e3 jest niebieska, natomiast w punkcie M~e1 :  styczna do granicy minimalnej jest zielona, zaś styczna do obrazu boku x2=0 jest czerwona. [W wersji pdf rysunek trafia na następną stronę.]

\par
Rys. 15.3. Styczne w skrajnych punktach przykładu Mordona.
Ćwiczenie 15.2 (kontrolne)

Czy czytelnik umie policzyć, na jakich dokładnie wysokościach narysowane tu styczne przecinają pionową oś zmiennej E ?

A Jeszcze ciekawszy efekt może wystąpić na ścianie, której podprzestrzeń afiniczną (rozpinaną przez tę ścianę) łamana Ł w ogóle omija. Dzieje się tak np w wymiarze 5 ze ścianą 2, 4 w modelu z parametrami

Σ=66264621239623232693192646264,μ=54321.

Czysto formalnie, wzory z Wykładu XIV dawałyby na tej ścianie

η1=-278-52λE,
x2=14+λE,
η3=-518-12λE,
x4=34-λE,
η5=-278+32λE.

A zatem, dalej czysto formalnie, byłoby λlow2,4=max-14,278/32=94, oraz

λhi2,4=min--278/-52,--518/-12,-34/-1=min-2720,-514=-514.

W tym przykładzie ściana 2, 4 okazuje się bardzo nieoptymalna z punktu widzenia relatywnego minimalizowania ryzyka w modelu i dla wirtualnych wielkości z algorytmu z nią związanych mamy λlow2,4>λhi2,4.61Warto zwrócić uwagę, że ograniczenia na λE pochodzące od dodatniości współrzędnych x-owych podlegają teorii użytej w dowodzie Stwierdzenia 15.1, i monotoniczność ograniczeń pochodzących od tych współrzędnych jest  zachowywana:

-14=192-92-4=σ44-σ42μ4-μ2<λE2,4<σ22-σ24μ2-μ4=212-94-2=34.
Te ograniczenia są jednak przesłonięte  mocniejszymi ograniczeniami pochodzącymi od hipotetycznej nieujemności składowych wektora η – tej kwintesencji optymalności. I właśnie nieujemność η jest nie do zrealizowania na boku e2e4¯.

Podsumowanie algorytmu CLA.

Podczas dyskusji algorytmu CLA wydzieliśmy dwie sytuacje – dwa możliwe rodzaje przejść między kolejnymi etapami algorytmu, przy przyjętych przez nas założeniach niezdegenerowania (15.2).

Po pierwsze

(A).  ININ,  gdzie  #IN,#IN2.

Jak wiemy, zbiory IN oraz IN różnią się wtedy tylko jednym elementem, zaś parametr λE zmienia się płynnie przy przejściu łamanej wierzchołkowej Ł¯ ze ściany IN na ścianę IN. Dokładniej, λE przechodzi przy takim przejściu przez wartość λlowIN=λhiIN (odpowiadający temu węzeł – wartość E jest niewyróżniony, Wniosek 15.1 powyżej).

Po drugie

(B).  INiIN

Wiemy, że wtedy oba zbiory IN oraz IN są dwuelementowe i oba są – różnymi! – nadzbiorami singletonu i. W tej fazie algorytmu łamana wierzchołkowa biegnie po krawędzi IN, wpada w wierzchołek ei, zaś po chwili wybiega z niego po krawędzi IN. Jeśli chodzi o parametr λE, to na boku łamanej Ł¯ będącym częścią lub całą krawędzią IN, zmniejsza się on (będąc cały czas związany zależnością z Obserwacji 6.1 ze stycznymi do obrazów punktów na boku IN) do swego kresu dolnego λlowIN=λhii — gdy punkt bieżący na tym boku dobiega do wierzchołka ei. Następnie parametr obniża się dalej, teraz parametryzując tylko nadstyczne  położenia prostych podpierających granicę minimalną w obrazie wierzchołka ei, który jest, jak wiemy, punktem załamania tej granicy. (Odpowiadający temu węzeł – wartość E=μi jest wyróżniony, Wniosek 15.2 powyżej.)
Parametr λE przebiega tak cały przedział Li aż do jego lewego końca λlowi=λhiIN. W tym momencie prosta podpierająca staje się znowu styczna – tym razem do obrazu krawędzi IN. Dalsze zmniejszanie λE to parametryzowanie boku łamanej Ł¯ będącego częścią lub całą krawędzią IN, znowu zgodnie z zależnością z Obserwacji 6.1 w Wykładzie VI.

Uwaga. Przypomnianego tu w (B) opisu zbioru Li (patrz Stwierdzenie 15.1 powyżej) wykładowca nie znalazł w dostępnej literaturze. Został on włączony do wykładów dopiero w roku akademickim 2009/10.

Podany opis przebiegu algorytmu CLA obowiązuje, powtarzamy to, przy założeniu warunków niezdegenerowania (15.2). Zauważmy jednak na koniec, że można podać równoległy zestaw innych  warunków, też pociągający ten sam przebieg algorytmu, tzn występowanie w jego realizacji tylko sytuacji typu (A) oraz (B), co prawda przebieganych w przeciwnym porządku i kierunkach, niż poprzednio. Mianowicie, jeśli zakładać tylko, że

(αiβi,γjδj|iIN,jOUT,βi<0,δj<0)IN{1, 2,,k}, (15.24)

wtedy łamaną wierzchołkową Ł¯ można odzyskiwać od końca do początku: od Emin (i λE=-) do Emax (i λE=+). W dyskusji jej przebiegu, w pełni analogicznej do tej przedstawionej w Wykładzie XV, akcentuje się wtedy tylko progowe wartości λhiIN, IN – ściany aktywne, goszczące łamaną Ł¯. Warunki (15.24) gwarantują wtedy z naddatkiem brak kolizji przy zmianach ścian. Zatem Ł¯ wygląda wtedy tak samo jak przy obowiązywaniu warunków (15.2): doznaje tylko ewolucji typu (A) i/lub (B). Podkreślamy jeszcze raz, że każdy z zestawów warunków (15.2) i (15.24) sam w sobie jest słabszy niż ten, który podany jest na stronie 161 w [22].

Można zauważyć na koniec, że tak właśnie, na samym początku, w [19] Markowitz planował znajdować wszystkie portfele efektywne: zaczynać od portfela mającego minimum wariancji, natomiast kończyć na portfelu mającym maksimum wartości oczekiwanej. Można to dokładnie prześledzić w tekście na Rysunku 14.2 (reprodukcja strony 87 z [19]) w Wykładzie XIV.

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

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.