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 $\Sigma>0$ oraz $\ne\big(\mu _{1},\,\mu _{2},\,\dots,\,\mu _{k}\big)$ . To pociąga, że macierze $\Sigma _{{\text{IN}}}$ , a także $M_{{\text{IN}}}$ , są odwracalne dla wszystkich $\emptyset\ne\text{IN}\subset\{ 1,\, 2,\dots,\, 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ą $\overline{\text{Ł}}$ 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” $\overline{\text{Ł}}$ , jak wyraża się Markowitz, spośród setek tysięcy czy milionów ścian sympleksu, przez które à priori mogłaby przebiegać $\overline{\text{Ł}}$ . 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 $\overline{\text{Ł}}$ . W tym obecnym spojrzeniu może to nawet być jeden z wierzchołków sympleksu $\Delta^{k}$ , oczywiście taki, przez który przechodzi $\overline{\text{Ł}}$ . Tzn. $\#(\text{IN})=1$ jest możliwe.
Zakładamy, że algorytm już doszedł do boku $\overline{\text{Ł}}$ leżącego w IN i biegnie po nim (lub stoi, gdy $\#(\text{IN})=1)$ , zmniejszając przy tym wartość parametru $\lambda _{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

$x_{i}=\alpha _{i}+\beta _{i}\lambda _{E}>0\quad\text{dla}\, i\in\text{IN}$

oraz

$\eta _{j}=\gamma _{j}+\delta _{j}\lambda _{E}\ge 0\quad\text{dla}\ j\in\text{OUT}\,.$

Dodatniość, względnie nieujemność, może przy zmniejszaniu $\lambda _{E}$ popsuć się tylko w tych wyrażeniach, w których współczynniki przy $\lambda _{E}$ są dodatnie. Wynikają stąd naturalne dolne ograniczenia

$\lambda _{E}>-\frac{\alpha _{i}}{\beta _{i}}\quad\text{dla}\ i\in\text{IN},\:\beta _{i}>0$

oraz

$\lambda _{E}\ge-\frac{\gamma _{j}}{\delta _{j}}\quad\text{dla}\ j\in\text{OUT},\:\delta _{j}>0.$

Kresem dolnym optymalności portfeli na ścianie IN, wyrażonym w terminach parametru $\lambda _{E}$ , jest zatem

$\lambda^{{\text{IN}}}_{{\text{low}}}\overset{\text{def}}{\:=\:}\max _{{\substack{\beta _{i}>0\\ \delta _{j}>0}}}\left(-\frac{\alpha _{i}}{\beta _{i}},\,\,-\frac{\gamma _{j}}{\delta _{j}}\right),$

(15.1)

gdzie też oczywiście $i\in\text{IN}$ , $j\in\text{OUT}$ . Gdy $\#(\text{IN})=1$ , $\text{IN}=\{ i\}$ , wtedy nie ma aktywnej nierówności na temat $x_{i}$ , są tylko pewne nierówności na temat $\eta _{j}$ , $j\ne i$ , związane z optymalnością wierzchołka numer $i$ oraz związanymi z tym możliwymi wartościami parametru $\lambda _{E}$ .⁵⁶wtedy, jak wiadomo, rozwiązania warunków Karusha-Kuhna-Tuckera nie dają jednoznacznie wyznaczonych współczynników Lagrange'a $\lambda$ i $\lambda _{E}$

Algorytm będzie ,,wiedział”, gdzie skierować się dalej (gdzie leży następny bok łamanej $\overline{\text{Ł}}$ ) 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 $(\Sigma,\,\mu)$ , $\Sigma>0$ , $\ne\big(\mu _{1},\,\mu _{2},\dots,\,\mu _{k}\big)$ , mówimy, że ma
niezdegenerowane parametry gdy

$\ne\left(\ \frac{\alpha _{i}}{\beta _{i}},\:\frac{\gamma _{j}}{\delta _{j}}\,\,\Big|\:\, i\in\text{IN},\, j\in\text{OUT},\,\beta _{i}>0,\,\delta _{j}>0\right)\quad\quad\forall\,\emptyset\ne\text{IN}\subset\{ 1,\, 2,\dots,\, 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ą $\overline{\text{Ł}}$ 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 tyle⁵⁷sł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 $\text{IN}=\{ i\}$ , gdzie $\mu _{i}=\underset{1\le l\le k}{\max}\mu _{l}\:(=\, E_{{\max}})$ , tzn. od wierzchołka $e_{i}$ , w którym zaczyna się łamana wierzchołkowa $\overline{\text{Ł}}$ . Algorytm przez długi czas stoi na tym wierzchołku, podczas gdy parametr $\lambda _{E}$ maleje od $+\infty$ do wartości $\lambda^{{\{ i\}}}_{{\text{low}}}$ . Ta wartość progowa, na mocy niezdegenerowania parametrów modelu, jest równa $-\frac{\gamma _{j}}{\delta _{j}}$ dla jednego jedynego $j\ne i$ , $\delta _{j}>0$ . Stąd wiemy, że następnym etapem będzie $\text{IN}^{{\prime}}=\text{IN}\cup\{ j\}=\{ i,j\}$ , w którym parametr $\lambda _{E}$ będzie się zmniejszał poniżej wartości $\lambda^{{\text{IN}}}_{{\text{low}}}$ .

B. Załóżmy, że już trwa jakiś etap IN w algorytmie, zaś $\lambda _{E}$ zmniejsza się poniżej poznanej już poprzedniej wartości progowej. Afiniczne od $\lambda _{E}$ wzory na $x_{i}$ , $i\in\text{IN}$ , opisują bok $\overline{\text{Ł}}$ na ścianie IN, dla $\lambda _{E}$ poniżej poprzedniej wartości progowej aż do wartości $\lambda^{{\text{IN}}}_{{\text{low}}}$ danej wzorem (15.1). Na mocy niezdegenerowania parametrów modelu, w (15.1) jest jeden jedyny indeks $i\in\text{IN}$ lub $j\in\text{OUT}$ taki, że $\lambda^{{\text{IN}}}_{{\text{low}}}=-\frac{\alpha _{i}}{\beta _{i}}$ lub $\lambda^{{\text{IN}}}_{{\text{low}}}=-\frac{\gamma _{j}}{\delta _{j}}$ .

Następny etap algorytmu to $\text{IN}^{{\prime}}=\text{IN}\,\backslash\,\{ i\}$ w pierwszym przypadku, względnie $\text{IN}^{{\prime}}=\text{IN}\cup\{ j\}$ w drugim, przy czym parametr $\lambda _{E}$ zmniejsza się w nim poniżej $\lambda^{{\text{IN}}}_{{\text{low}}}$ (do jakiejś wartości lub do $-\infty$ ). W ten sposób rekurencyjnie podany jest już cały algorytm, opisujący bok po boku całą łamaną wierzchołkową $\overline{\text{Ł}}$ . Ostatni etap to, oczywiście, $\text{IN}=\{ i\}$ , $\mu _{i}=\underset{1\le l\le k}{\min}\mu _{l}\:(=\, E_{{\min}})$ , zaś $\lambda _{E}$ zmniejsza się w nim od poprzedniej wartości progowej do $-\infty$ (przyjmujemy, że maksimum pustego zbioru liczb wynosi $-\infty$ ).

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

Algorytm jest wydajny w $100\%$ – wędrujemy w nim dokładnie po tych ścianach $\Delta^{k}$ , przez które przebiega łamana $\overline{\text{Ł}}$ . Czasami zdarza się – o czym Markowitz w [22] wydaje się nie wiedzieć – że ten maksymalnie wydajny algorytm musi odwiedzić wszystkie $2^{k}-1$ niepuste ściany $\Delta^{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 $\overline{\text{Ł}}$ zaczynamy od $\text{IN}=\{ 3\}$ , bo $\mu _{3}=30=E_{{\max}}$ . $\lambda^{{\{ 3\}}}_{{\text{low}}}=\frac{155}{32}$ , wchodzi indeks 2, $\text{IN}^{{\prime}}=\{ 2,3\}$ . Kolejne $\lambda^{{\{ 2,3\}}}_{{\text{low}}}=\frac{167}{64}$ , wychodzi indeks $3$ , $\text{IN}^{{\prime\prime}}=\{ 2\}$ . Kolejne $\lambda^{{\{ 2\}}}_{{\text{low}}}=\frac{19}{8}$ , 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,3\}\to\{ 1,3,4\}\to\{ 1,2,3,4\}\to\{ 1,2,4\}\to\{ 2,4\}\to\{ 2,3,4\}\to\{ 3,4\}\to\{ 4\}\to\{ 1,4\}\to\{ 1\}$ .

Odpowiednie wartości progowe $\lambda _{{\text{low}}}$ są w środkowej kolumnie tamtej tabeli, też jadąc od dołu do góry: $\lambda^{{\{ 1,2\}}}_{{\text{low}}}=\frac{5341}{9392}$ , itd. Istotnie zatem, łamana $\overline{\text{Ł}}$ 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.⁵⁸Iwanicki 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!

$\Sigma\,\,=\begin{pmatrix}1.080810&3.498620&5.155060&-0.137649&4.392940\\ 3.498620&25.242400&49.611500&-1.707990&39.800400\\ 5.155060&49.611500&233.167000&-3.108180&95.732900\\ -0.137649&-1.707990&-3.108180&0.341958&-2.498140\\ 4.392940&39.800400&95.732900&-2.498140&67.339300\end{pmatrix},\quad\mu\,\,=\begin{pmatrix}1.572040\\ 4.211660\\ 6.351950\\ -0.365159\\ 5.352790\end{pmatrix}.$

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

	$\displaystyle\text{IN}=$	$\displaystyle\{ 3\}\to\{ 3,5\}\to\{ 5\}\ (\lambda _{{\text{hi}}}=28.417,\,\lambda _{{\text{low}}}=24.133)\to\{ 2,5\}\to\{ 2,3,5\}\to\{ 2,3\}\to$
		$\displaystyle\{ 2\}\ (\lambda _{{\text{hi}}}=11.386,\,\lambda _{{\text{low}}}=8.237)\to\{ 1,2\}\to\{ 1,2,3\}\to\{ 1,2,3,5\}\to\{ 1,2,5\}\to$
		$\displaystyle\{ 1,5\}\to\{ 1,3,5\}\to\{ 1,3\}\to\{ 1\}\ (\lambda _{{\text{hi}}}=0.852,\,\lambda _{{\text{low}}}=0.629)\to\{ 1,4\}\to\{ 1,3,4\}\to$
		$\displaystyle\{ 1,3,4,5\}\to\{ 1,4,5\}\to\{ 1,2,4,5\}\to\{ 1,2,3,4,5\}\to\{ 1,2,3,4\}\to\{ 1,2,4\}\to\{ 2,4\}\to$
		$\displaystyle\{ 2,3,4\}\to\{ 2,3,4,5\}\to\{ 2,4,5\}\to\{ 4,5\}\to\{ 3,4,5\}\to\{ 3,4\}\to\{ 4\}.$

Ćwiczenie 15.1

Policzyć do końca tę łamaną wierzchołkową, a następnie zobrazować ją na rzucie sympleksu $\Delta^{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 $\overline{\text{Ł}}$ , odkrywana stopniowo przez algorytm CLA, zmienia

(A) ścianę IN, $\#(\text{IN})\ge 2$ , na inną ścianę $\text{IN}^{{\prime}},\ \#(\text{IN}^{{\prime}})\ge 2$ , względnie

(B) ścianę IN, $\#(\text{IN})\ge 2$ na wierzchołek, np $\{ i\}$ , po którym z kolei łamana $\overline{\text{Ł}}$ wchodzi w ścianę $\text{IN}^{{\prime}},\ \#(\text{IN}^{{\prime}})\ge 2$ .

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 $E(\text{IN})$ , $\#(\text{IN})\ge 2$ , dają w sumie z węzłami wyróżnionymi cały przedział $[E_{{\min}},\, E_{{\max}}]$ . W sytuacji (A) domknięcia przedziałów $E(\text{IN}^{{\prime}})$ oraz $E(\text{IN})$ zahaczają się zatem jednym punktem $\inf\, E(\text{IN})=\sup\, E(\text{IN}^{{\prime}})$ . 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ę $\text{IN}^{{\prime}}$ nie przechodzi przez żaden wierzchołek sympleksu. Ten wspólny kres leży więc w dokładnie jednym z przedziałów $E(\text{IN})$ , $E(\text{IN}^{{\prime}})$ .
Natomiast sytuacja (B) to po prostu inne wypowiedzenie zdania ` $\mu _{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

$[E_{{\min}},\, E_{{\max}}]\ni E\longmapsto\sigma^{2}(x_{E})\,,$

(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\lambda _{E}(E)$ , gdzie $\lambda _{E}(\cdot)$ to funkcja związana z danym bokiem łamanej Ł leżącym na jakiejś ścianie $(\ge 1)$ -wymiarowej. (Przy rygorystycznym podejściu ta funkcja powinna być oznaczana symbolem $\lambda^{{\text{IN}}}_{{E}}(\cdot)$ . Na ścianach IN, $\#(\text{IN})\ge 2$ , współczynniki Lagrange'a $\lambda$ i $\lambda _{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 $\Lambda _{E}$ ,

$[E_{{\min}},\, E_{{\max}}]\ni E\xrightarrow{\Lambda _{E}}\lambda _{E}(E)$

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\xrightarrow{\Lambda _{E}}\lambda _{E}(E)$ jest liniowa, etykietujemy odpowiednimi zbiorami indeksów IN – nazwami ścian, których dotyczą. Węzły wyróżnione, w których jest skok funkcji $\Lambda _{E}$ , nazywamy pojedynczymi indeksami – numerami odpowiednich wierzchołków sympleksu. Przejście od parametru $E$ do $\lambda _{E}$ jest w takich węzłach rodzajem blow-upu: rozdmuchania punktu do odcinka [wartości parametru $\lambda _{E}$ ].

Niech dla IN : $\#(\text{IN})\ge 2$ , $E(\text{IN})$ będzie jak w dowodzie w Wykładzie XI (zbiór wartości oczekiwanych wszystkich portfeli wierzchołkowych $x_{E}$ leżących na ścianie IN).

Niech ponadto, tym razem dla wszystkich IN niepustych, $L\big(\text{IN}\big)$ oznacza zbiór wszystkich wartości współczynników Lagrange'a $\lambda _{E}$ w rozwiązaniach warunków K-kT dla portfeli wierzchołkowych leżących na ścianie IN.

Gdy $\#(\text{IN})\ge 2$ , jest to (wiemy to już!) przedział – obraz odpowiedniego przedziału $E(\text{IN})$ w globalnej funkcji $\Lambda _{E}$ :

$L(\text{IN})=\Lambda _{E}\big(E(\text{IN})\big)\,.$

Natomiast gdy $\text{IN}=\{ i\}$ ,

$L\bigl(\{ i\}\bigr)\quad\text{też jest przedziałem}\,,$

(15.4)

bo dla $\lambda _{E},\,\lambda^{{\prime}}_{E}\in L\big(\{ i\}\big)$ i $s,\, t>0$ , $s+t=1$ , nierówności wektorowe

$\left\{\begin{array}[]{ll}\Sigma e_{i}+\lambda e-\lambda _{E}\mu\ge 0,&\hbox{}\\ \Sigma e_{i}+\lambda^{{\prime}}e-\lambda^{{\prime}}_{E}\mu\ge 0,&\hbox{}\end{array}\right.$

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

$\Sigma e_{i}+(s\lambda+t\lambda^{{\prime}})e-(s\lambda _{E}+t\lambda^{{\prime}}_{E})\mu\ge 0,$

zaś warunki komplementarności

$e_{i}^{{\text{T}}}(\Sigma e_{i}+\lambda e-\lambda _{E}\mu)=0\,,\qquad e_{i}^{{\text{T}}}(\Sigma e_{i}+\lambda^{{\prime}}e-\lambda^{{\prime}}_{E}\mu)=0$

oczywiście pociągają warunek

$e_{i}^{{\text{T}}}\big(\Sigma e_{i}+(s\lambda+t\lambda^{{\prime}})e-(s\lambda _{E}+t\lambda^{{\prime}}_{E})\mu\big)=0\,.$

Istotnie zatem $s\lambda _{E}+t\lambda _{E}^{{\prime}}\in L(\{ i\})$ .

Uwaga 15.3

W języku używanym w tym Wykładzie XV, całkiem naturalnym dla algorytmu CLA, wierzchołek $e_{i}$ sympleksu $\Delta^{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ń.⁵⁹Symbolika $e_{i}$ 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.

$L(\{ i\})$ 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 $[E_{{\min}},\, E_{{\max}}]$ . 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 $\lambda _{E}$ , przedziały $L(\text{IN})$ oraz $L(\text{IN}^{{\prime}})$ 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: $L(\text{IN})$ lub $L(\text{IN}^{{\prime}})$ .

Punkt $\widetilde{E}$ leżący w części wspólnej domknięć $\overline{E(\text{IN})}$ i $\overline{E(\text{IN}^{{\prime}})}$ 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 $\widetilde{E}$ globalna funkcja $\Lambda _{E}$ nie ma skoku. Dla ustalenia uwagi niech np $\widetilde{E}\in E(\text{IN})$ , $\widetilde{E}\notin E(\text{IN}^{{\prime}})$ . Dla wartości $E$ trochę mniejszych od $\widetilde{E}$ bierzemy, jednoznacznie określone w etapie $\text{IN}^{{\prime}}$ dowodu z Wykładu XI, wielkości

$(x,\,\lambda,\,\lambda _{E})\,=\,\bigl(x_{E},\,\lambda(E),\,\lambda _{E}(E)\bigr)$

oraz ich granice

$x_{{\widetilde{E}}}\,=\lim _{{E\to\widetilde{E}-}}x_{E},\quad\widetilde{\lambda}\,=\lim _{{E\to\widetilde{E}-}}\lambda(E),\quad\widetilde{\lambda}_{E}\,=\lim _{{E\to\widetilde{E}-}}\lambda _{E}(E)\,,$

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

$\Sigma x_{E}+\lambda(E)e-\lambda _{E}(E)\mu\ge 0\,,\quad x^{{\text{T}}}_{E}\big(\Sigma x_{E}+\lambda(E)e-\lambda _{E}(E)\mu\big)=\, 0$

dla $E$ trochę mniejszych od $\widetilde{E}$ . Zatem również po przejściu granicznym $E\to\widetilde{E}-$ ,

$\Sigma x_{{\widetilde{E}}}+\widetilde{\lambda}e-\widetilde{\lambda}_{E}\mu\ge 0,\quad x^{{\text{T}}}_{{\widetilde{E}}}\big(\Sigma x_{{\widetilde{E}}}+\widetilde{\lambda}e-\widetilde{\lambda}_{E}\mu\big)=\, 0.$

Portfel $x_{{\widetilde{E}}}$ 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, $\widetilde{\lambda}_{E}=\lambda _{E}(\widetilde{E})$ liczone na boku leżącym na ścianie IN. Zatem to właśnie liczba $\widetilde{\lambda}_{E}$ okazuje się leżeć w części wspólnej domknięć przedziałów $L(\text{IN})$ i $L(\text{IN}^{{\prime}})$ . Dokładniej,

$\widetilde{\lambda}_{E}=\inf L(\text{IN})=\lambda^{{\text{IN}}}_{{\text{low}}}\,,$

(15.5)

przy czym $\widetilde{\lambda}_{E}\in L(\text{IN})$ . Równocześnie

$\widetilde{\lambda}_{E}=\sup L(\text{IN}^{{\prime}})$

(15.6)

oraz $\widetilde{\lambda}_{E}\notin L(\text{IN}^{{\prime}})$ , bo, przypominamy, $L(\text{IN})$ i $L(\text{IN}^{{\prime}})$ są rozłączne.

W sytuacji przeciwnej w (A): $\widetilde{E}\notin E(\text{IN})$ , lecz $\widetilde{E}\in E(\text{IN}^{{\prime}})$ byłoby, oczywiście, $L(\text{IN}^{{\prime}})\ni\sup L(\text{IN}^{{\prime}})$ oraz $\lambda^{{\text{IN}}}_{{\text{low}}}\notin L(\text{IN})$ , natomiast równości (15.5)–(15.6) oczywiście pozostawałyby w mocy.

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

$\sup L(\text{IN}^{{\prime}})=\lambda^{{\text{IN}}}_{{\text{low}}}\,.$

(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 $F_{{\min}}$ . Innymi słowy, sytuacja (A) daje tylko punkty gładkości granicy minimalnej. Albo też – patrz Uwaga 15.2 powyżej – punkty na $F_{{\min}}$ , 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 $e_{i}=x_{{\widetilde{E}}}$ , $\widetilde{E}=\mu _{i}$ , sąsiaduje z bokiem leżącym na ścianie IN, na którym wartości $E$ są większe od $\mu _{i}=\widetilde{E}$ , oraz z bokiem leżącym na ścianie $\text{IN}^{{\prime}}$ , na którym wartości $E$ są mniejsze od $\widetilde{E}$ . Wartość $\widetilde{E}$ jest węzłem wyróżnionym w terminologii z Wykładu X.

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

$\Sigma e_{i}+\widetilde{\lambda}e-\widetilde{\lambda}_{E}\mu\ge 0\,,\quad e^{{\text{T}}}_{i}\bigl(\Sigma e_{i}+\widetilde{\lambda}e-\widetilde{\lambda}_{E}\mu\bigr)=\, 0\,,$

(15.8)

gdzie $\widetilde{\lambda}_{E}=\sup L(\text{IN}^{{\prime}})$ . I oczywiście też przy $E\to\widetilde{E}+$ , dostając analogicznie

$\Sigma e_{i}+\widetilde{\widetilde{\lambda}}e-\widetilde{\widetilde{\lambda}}_{E}\mu\ge 0\,,\quad e^{{\text{T}}}_{i}\bigl(\Sigma e_{i}+\widetilde{\widetilde{\lambda}}e-\widetilde{\widetilde{\lambda}}_{E}\mu\bigr)=0\,,$

(15.9)

gdzie tym razem $\widetilde{\widetilde{\lambda}}_{E}=\inf L(\text{IN})=\lambda^{{\text{IN}}}_{{\text{low}}}$ . Związki (15.8)–(15.9) pokazują zatem, że $\sup L(\text{IN}^{{\prime}}),\,\lambda^{{\text{IN}}}_{{\text{low}}}\in L\big(\{ i\}\big)$ . Wobec własności (15.4),

$\bigl[\sup L(\text{IN}^{{\prime}}),\,\,\lambda^{{\text{IN}}}_{{\text{low}}}\bigr]\subset L\bigl(\{ i\}\bigr)\,.$

(15.10)

W istocie jest lepiej. Mianowicie

Stwierdzenie 15.1

$L\bigl(\{ i\}\bigr)=\bigl[\sup L(\text{IN}^{{\prime}}),\,\,\lambda^{{\text{IN}}}_{{\text{low}}}\bigr]$ .

Pokażemy, że dowolna liczba $\lambda _{E}\in L\bigl(\{ i\}\bigr)$ spełnia

$\sup L(\text{IN}^{{\prime}})\le\lambda _{E}\le\inf L(\text{IN})\ \Bigl(=\,\lambda^{{\text{IN}}}_{{\text{low}}}\Bigr),$

(15.11)

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

Zauważamy w tym celu, że $\#(\text{IN})=2=\#(\text{IN}^{{\prime}})$ , tzn ściany IN, $\text{IN}^{{\prime}}$ są po prostu krawędziami spotykającymi się w wierzchołku $e_{i}$ . Istotnie, warunki niezdegenerowania spełniane przez $(\Sigma,\,\mu)$ pociągają, że w algorytmie przy przejściu $\text{IN}\to\{ i\}$ wypada tylko jeden indeks, np $j$ , oraz przy przejściu $\{ i\}\to\text{IN}^{{\prime}}$ wchodzi też tylko jeden indeks, np $j^{{\prime}}$ . Tak więc $\text{IN}=\{ i,\, j\}$ , gdzie $\mu _{j}>\mu _{i}$ , oraz $\text{IN}^{{\prime}}=\{ i,\, j^{{\prime}}\}$ , gdzie $\mu _{{j^{{\prime}}}}<\mu _{i}$ .

Fakt, że $\lambda _{E}\in L\big(\{ i\}\big)$ oznacza, że dla $\lambda _{E}$ i jakiegoś rzeczywistego współczynnika $\lambda$ zachodzi

$\Sigma e_{i}+\lambda e-\lambda _{E}\mu\ge 0\,,\quad e_{i}^{{\text{T}}}\big(\Sigma e_{i}+\lambda e-\lambda _{E}\mu\big)=0\,,$

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

$\sigma _{{ii}}+\lambda-\lambda _{E}\mu _{i}=0,$

(15.12)

$\sigma _{{ji}}+\lambda-\lambda _{E}\mu _{j}\ge 0,$

(15.13)

$\sigma _{{j^{{\prime}}i}}+\lambda-\lambda _{E}\mu _{{j^{{\prime}}}}\ge 0.$

(15.14)

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

$\sigma _{{ji}}-\sigma _{{ii}}+\lambda _{E}(\mu _{i}-\mu _{j})\ge 0\,,$

(15.15)

$\sigma _{{j^{{\prime}}i}}-\sigma _{{ii}}+\lambda _{E}(\mu _{i}-\mu _{{j^{{\prime}}}})\ge 0\,.$

(15.16)

Pamiętając, że $\mu _{{j^{{\prime}}}}<\mu _{i}<\mu _{j}$ , nierówności (15.15)–(15.16) dają

$\frac{\sigma _{{ii}}-\sigma _{{j^{{\prime}}i}}}{\mu _{i}-\mu _{{j^{{\prime}}}}}\le\lambda _{E}\le\frac{\sigma _{{ii}}-\sigma _{{ji}}}{\mu _{i}-\mu _{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ść $\lambda _{E}(\mu _{i})$ w teorii Blacka, gdy zbiorem aktywnych indeksów jest $\{ i,\, l\}$ , $l\ne i$ (teoria Blacka w wymiarze 2). Wtedy portfele Blacka

$\begin{pmatrix}x_{i}\\ x_{l}\end{pmatrix}\,\,=\,\begin{pmatrix}\frac{E-\mu _{l}}{\mu _{i}-\mu _{l}}\\ \frac{\mu _{i}-E}{\mu _{i}-\mu _{l}}\end{pmatrix}$

mają wariancję

$\sigma^{2}(E)=\frac{1}{(\mu _{i}-\mu _{l})^{2}}\left(\sigma _{{ii}}(E-\mu _{l})^{2}+2\sigma _{{il}}(E-\mu _{l})(\mu _{i}-E)+\sigma _{{ll}}(\mu _{i}-E)^{2}\right),$

zaś $\lambda _{E}(\mu _{i})=\frac{1}{2}\Big(\sigma^{2}(E)\Big)^{{\prime}}\Big|_{{E=\mu _{i}}}$ (porównaj – kolejny raz! – Obserwacja 6.1 w Wykładzie VI). Liczymy zatem tę pochodną

$\lambda _{E}(\mu _{i})=\frac{1}{2(\mu _{i}-\mu _{l})^{2}}\Big(2\sigma _{{ii}}(\mu _{i}-\mu _{l})+2\sigma _{{il}}\big((\mu _{i}-\mu _{l})(-1)+0\big)+0\Big)=\frac{\sigma _{{ii}}-\sigma _{{il}}}{\mu _{i}-\mu _{l}}\,.$

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

$\frac{\sigma _{{ii}}-\sigma _{{ij}}}{\mu _{i}-\mu _{j}}=\lambda _{E}(\mu _{i})=\lim _{{E\to\mu _{i}+}}\Lambda(E)=\lambda^{{\text{IN}}}_{{\text{low}}}\,.$

Biorąc natomiast $l=j^{{\prime}}$ , mamy

$\frac{\sigma _{{ii}}-\sigma _{{ij^{{\prime}}}}}{\mu _{i}-\mu _{{j^{{\prime}}}}}=\lambda _{E}(\mu _{i})=\lim _{{E\to\mu _{i}-}}\Lambda(E)=\sup L(\text{IN}^{{\prime}})\,.$

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

$\big[\lambda^{{\{ i\}}}_{{\text{low}}},\,\,\sup L\big(\{ i\}\big)\big]=\big[\sup L(\text{IN}^{{\prime}}),\,\,\lambda _{{\text{low}}}^{{\text{IN}}}\big]\,.$

(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 $L(\text{IN})$ , obok liczb $\lambda _{\text{low}}^{\text{IN}}$ zdefiniowanych już jakiś czas temu wzorem (15.1), ważną – niejako dualną – rolę odgrywają też liczby $\sup L(\text{IN})$ . Naturalne jest w takiej sytuacji przyjąć następującą ogólną

Definicja 15.2

$\lambda^{{\text{IN}}}_{{\text{hi}}}\,\,\colon\!\!\!=\,\,\sup L(\text{IN})\,,$

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 $\lambda _{{\text{low}}}^{{\text{IN}}}$ i $\lambda _{{\text{hi}}}^{{\text{IN}}}$ 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ć

$\lambda _{{\text{hi}}}^{{\text{IN}^{{\prime}}}}=\lambda _{{\text{low}}}^{{\text{IN}}}\,.$

(15.19)

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

$\lambda _{{\text{hi}}}^{{\text{IN}^{{\prime}}}}=\lambda _{{\text{low}}}^{{\{ i\}}}$

(15.20)

oraz

$\lambda _{{\text{hi}}}^{{\{ i\}}}=\lambda _{{\text{low}}}^{{\text{IN}}}\,.$

(15.21)

Wniosek 15.2

W każdym węźle wyróżnionym $\widetilde{E}=\mu _{i}$ globalna funkcja $\Lambda _{E}$ ma skok w górę równy $\lambda _{{\text{hi}}}^{{\{ i\}}}-\lambda _{{\text{low}}}^{{\{ i\}}}>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 $\Lambda _{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ść $\lambda _{{\text{hi}}}^{{\text{IN}}}$ , analogiczna do formuły (15.1) definiującej $\lambda _{{\text{low}}}^{{\text{IN}}}$ . Skoro jest to kres górny wartości $\lambda _{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 $\lambda _{E}$ ,

$\lambda _{{\text{hi}}}^{{\text{IN}}}=\min\left\{-\frac{\alpha _{i}}{\beta _{i}},\,-\frac{\gamma _{j}}{\delta _{j}}\bigg|\ i\in\text{IN},\,\beta _{i}<0,\,\, j\in\text{OUT},\,\delta _{j}<0\right\}.$

(15.22)

(We wszystkich literach greckich w (15.22) dla lepszej czytelności opuszczony jest dolny indeks $`\text{IN}^{{\prime}}$ . Ponadto, gdy w momencie startu algorytmu $\text{IN}=\{ i_{0}\}$ i $\mu _{{i_{0}}}=E_{{\max}}$ , wtedy ten kres górny przyjmuje się równy $+\infty$ ).

Z przeprowadzonych dotąd rozważań wynika

Obserwacja. 15.1

$\bullet$ $\lambda^{{\text{IN}}}_{{\text{low}}}<\lambda^{{\text{IN}}}_{{\text{hi}}}$ dla każdego $\text{IN}\subset\{ 1,\, 2,\dots,\, k\}$ pojawiającego się w danej realizacji algorytmu CLA.

$\bullet\bullet$ Jeśli w realizacji algorytmu CLA po etapie IN bezpośrednio następuje etap $\text{IN}^{{\prime}}$ , to $\lambda^{{\text{IN}}}_{{\text{low}}}=\lambda^{{\text{IN}^{{\prime}}}}_{{\text{hi}}}$ .

Punkt $\bullet$ wynika z samego opisu etapów algorytmu CLA. Natomiast punkt $\bullet\bullet$ , 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 $\lambda^{{\text{IN}}}_{{\text{low}}}$ (patrz (15.1) ) i na $\lambda^{{\text{IN}^{{\prime}}}}_{{\text{hi}}}$ (patrz (15.22), gdzie oczywiście IN trzeba zastąpić przez $\text{IN}^{{\prime}}$ ) 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 $\bullet\bullet$ 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,

$\lambda _{{\text{low}}}^{{\{ 3,5\}}}=28.417=\lambda _{{\text{hi}}}^{{\{ 5\}}}\,,$

$\lambda _{{\text{low}}}^{{\{ 2,3\}}}=1.386=\lambda _{{\text{hi}}}^{{\{ 2\}}}\,,$

$\lambda _{{\text{low}}}^{{\{ 1,3\}}}=0.852=\lambda _{{\text{hi}}}^{{\{ 1\}}}\,.$

(15.23)

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

$\lambda _{{\text{hi}}}^{{\{ 1\}}}=0.8523696\,,\qquad\lambda _{{\text{low}}}^{{\{ 1\}}}=0.6289798\,.$

Z drugiej strony walory, których wartości oczekiwane sąsiadują z $\mu _{1}=1.57204$ to: walor drugi (sąsiadowanie z góry, $\mu _{2}=4.21166$ ) oraz walor czwarty (sąsiadowanie z dołu, $\mu _{4}=-0.365159$ ). Kuszące jest spróbować zastosować poznane wcześniej (jeszcze w dowodzie Stwierdzenia 15.1) wzory: $\frac{\sigma _{{11}}-\sigma _{{14}}}{\mu _{1}-\mu _{4}}$ na $\lambda _{{\text{low}}}^{{\{ 1\}}}$ , oraz $\frac{\sigma _{{11}}-\sigma _{{12}}}{\mu _{1}-\mu _{2}}$ na $\lambda _{{\text{hi}}}^{{\{ 1\}}}$ . W efekcie dostalibyśmy poprawnie

$\lambda _{{\text{low}}}^{{\{ 1\}}}=\frac{1.08081-(-0.137649)}{1.57204-(-0.365159)}=0.62898\,,$

lecz także

$\frac{\sigma _{{11}}-\sigma _{{12}}}{\mu _{1}-\mu _{2}}=\frac{1.08081-3.49862}{1.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

$\frac{\sigma _{{11}}-\sigma _{{13}}}{\mu _{1}-\mu _{3}}=\frac{1.08081-5.15506}{1.57204-6.35195}=0.85237=\lambda _{{\text{hi}}}^{{\{ 1\}}}$

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.

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

$\Sigma=\begin{pmatrix}9&3&1\\ 3&2&2\\ 1&2&4\end{pmatrix},\quad\mu=\begin{pmatrix}5\\ 4\\ 2\end{pmatrix},$

na ścianie $\{ 1,\, 3\}$ , przez którą nie przebiega łamana wierzchołkowa⁶⁰ w tym doskonale rozpoznanym przykładzie przebieg algorytmu CLA to $\{ 1\}\to\{ 1,\, 2\}\,\text{(cała)}\,\to\{ 2\}\to\{ 2,\, 3\}\,\text{(cała)}\,\to\{ 3\}$ wielkości $\lambda^{{\text{IN}}}_{{\text{low}}}$ i $\lambda^{{\text{IN}}}_{{\text{hi}}}$ nabierają zaskakujących znaczeń. Dokładniej, wzory z Wykładu XIV dają formalnie na tej ścianie

	$\displaystyle x_{1}$	$\displaystyle=\frac{3}{11}+\frac{3}{11}\lambda _{E}\,,$
	$\displaystyle\eta _{2}$	$\displaystyle=-\frac{10}{11}-\frac{10}{11}\lambda _{E}\,,$
	$\displaystyle x_{3}$	$\displaystyle=\frac{8}{11}-\frac{3}{11}\lambda _{E}\,.$

Zatem, liczone czysto formalnie, $\lambda _{{\text{low}}}^{{\{ 1,3\}}}=\max\Big(-\frac{3}{11}/\frac{3}{11}\Big)=-1$ ,

$\lambda _{{\text{hi}}}^{{\{ 1,3\}}}\,=\,\min\Big(-\big(-\frac{10}{11}\big)/\big(-\frac{10}{11}\big),\:-\frac{8}{11}/\big(-\frac{3}{11}\big)\Big)\,=\,\min\left(-1,\:\frac{8}{3}\right)\,=\,-1\,.$

Pouczające jest porównać to z pochodną funkcji $\sigma^{2}(E)$ na tym boku. Tutaj $\sigma^{2}(x)=9x_{1}^{{\, 2}}+2x_{1}x_{3}+4x_{3}^{{\, 2}}$ oraz $x_{1}=\frac{E-2}{3}$ , $x_{3}=\frac{5-E}{3}$ . Prowadzi to do

$\frac{1}{2}\frac{\,\, d\sigma^{{\, 2}}}{dE}\,=\,\frac{11}{9}E-\frac{31}{9}\,.$

To wyrażenie jest równe $-1$ tylko przy $E=2$ , a więc tylko w wierzchołku $e_{3}$ sympleksu $\Delta^{3}$ (leżącym w domknięciu ściany, której dotyczą tu obliczenia). Zatem wirtualne współczynniki $\lambda _{{\text{low}}}^{{\{ 1,3\}}}=\lambda _{{\text{hi}}}^{{\{ 1,3\}}}=-1$ wychwytują ten jeden jedyny portfel na boku $x_{2}=0$ , który a) jest wierzchołkowy (tj leży na łamanej Ł) i b) w obrazie którego styczna do obrazu boku $x_{2}=0$ jest tożsama ze styczną do granicy minimalnej. Na rysunku poniżej, na – uwaga – płaszczyźnie $\mathbb{R}^{2}(\sigma^{2},\, E)$ , ta wspólna styczna w punkcie $\widetilde{\mathcal{M}}(e_{3})$ jest niebieska, natomiast w punkcie $\widetilde{\mathcal{M}}(e_{1})$ : styczna do granicy minimalnej jest zielona, zaś styczna do obrazu boku $x_{2}=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$ ?

$\star\star$ 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

$\Sigma=\begin{pmatrix}6&6&2&6&4\\ 6&\frac{21}{2}&3&9&6\\ 2&3&2&3&2\\ 6&9&3&\frac{19}{2}&6\\ 4&6&2&6&4\end{pmatrix}\,,\qquad\mu=\begin{pmatrix}5\\ 4\\ 3\\ 2\\ 1\end{pmatrix}\,.$

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

	$\displaystyle\eta _{1}$	$\displaystyle=-\frac{27}{8}-\frac{5}{2}\lambda _{E}\,,$
	$\displaystyle x_{2}$	$\displaystyle=\frac{1}{4}+\lambda _{E}\,,$
	$\displaystyle\eta _{3}$	$\displaystyle=-\frac{51}{8}-\frac{1}{2}\lambda _{E}\,,$
	$\displaystyle x_{4}$	$\displaystyle=\frac{3}{4}-\lambda _{E}\,,$
	$\displaystyle\eta _{5}$	$\displaystyle=-\frac{27}{8}+\frac{3}{2}\lambda _{E}\,.$

A zatem, dalej czysto formalnie, byłoby $\lambda _{{\text{low}}}^{{\{ 2,4\}}}=\max\Big(-\frac{1}{4},\:\frac{27}{8}/\frac{3}{2}\Big)=\frac{9}{4}$ , oraz

$\lambda _{{\text{hi}}}^{{\{ 2,4\}}}\,\,=\,\,\min\Bigg(-\left(-\frac{27}{8}\right)/\left(-\frac{5}{2}\right),\:\,-\left(-\frac{51}{8}\right)/\left(-\frac{1}{2}\right),\:\,-\frac{3}{4}/\big(-1\big)\Bigg)\,=\,\min\Big(-\frac{27}{20},\:-\frac{51}{4}\Big)=-\frac{51}{4}\,.$

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 $\lambda _{{\text{low}}}^{{\{ 2,4\}}}>\lambda _{{\text{hi}}}^{{\{ 2,4\}}}$ .⁶¹Warto zwrócić uwagę, że ograniczenia na $\lambda _{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:

$-\frac{1}{4}\,=\,\frac{\frac{19}{2}-9}{2-4}\,=\,\frac{\sigma _{{44}}-\sigma _{{42}}}{\mu _{4}-\mu _{2}}\,\,<\,\,\lambda _{E}^{{\{ 2,4\}}}\,<\,\,\,\frac{\sigma _{{22}}-\sigma _{{24}}}{\mu _{2}-\mu _{4}}\,=\,\frac{\frac{21}{2}-9}{4-2}=\frac{3}{4}\,.$

Te ograniczenia są jednak przesłonięte mocniejszymi ograniczeniami pochodzącymi od hipotetycznej nieujemności składowych wektora $\eta$ – tej kwintesencji optymalności. I właśnie nieujemność $\eta$ jest nie do zrealizowania na boku $\overline{e_{2}\, e_{4}}$ .

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). $\text{IN}\longrightarrow\text{IN}^{{\prime}}$ , gdzie $\#(\text{IN}),\:\#(\text{IN}^{{\prime}})\ge 2$ .

Jak wiemy, zbiory IN oraz $\text{IN}^{{\prime}}$ różnią się wtedy tylko jednym elementem, zaś parametr $\lambda _{E}$ zmienia się płynnie przy przejściu łamanej wierzchołkowej $\overline{\text{Ł}}$ ze ściany IN na ścianę $\text{IN}^{{\prime}}$ . Dokładniej, $\lambda _{E}$ przechodzi przy takim przejściu przez wartość $\lambda^{{\text{IN}}}_{{\text{low}}}=\lambda^{{\text{IN}^{{\prime}}}}_{{\text{hi}}}$ (odpowiadający temu węzeł – wartość $E$ jest niewyróżniony, Wniosek 15.1 powyżej).

Po drugie

(B). $\text{IN}\longrightarrow\{ i\}\longrightarrow\text{IN}^{{\prime}}$

Wiemy, że wtedy oba zbiory IN oraz $\text{IN}^{{\prime}}$ 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 $e_{i}$ , zaś po chwili wybiega z niego po krawędzi $\text{IN}^{{\prime}}$ . Jeśli chodzi o parametr $\lambda _{E}$ , to na boku łamanej $\overline{\text{Ł}}$ 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 $\lambda^{{\text{IN}}}_{{\text{low}}}=\lambda^{{\{ i\}}}_{{\text{hi}}}$ — gdy punkt bieżący na tym boku dobiega do wierzchołka $e_{i}$ . Następnie parametr obniża się dalej, teraz parametryzując tylko nadstyczne położenia prostych podpierających granicę minimalną w obrazie wierzchołka $e_{i}$ , który jest, jak wiemy, punktem załamania tej granicy. (Odpowiadający temu węzeł – wartość $E=\mu _{i}$ jest wyróżniony, Wniosek 15.2 powyżej.)
Parametr $\lambda _{E}$ przebiega tak cały przedział $L(\{ i\})$ aż do jego lewego końca $\lambda^{{\{ i\}}}_{{\text{low}}}=\lambda^{{\text{IN}^{{\prime}}}}_{{\text{hi}}}$ . W tym momencie prosta podpierająca staje się znowu styczna – tym razem do obrazu krawędzi $\text{IN}^{{\prime}}$ . Dalsze zmniejszanie $\lambda _{E}$ to parametryzowanie boku łamanej $\overline{\text{Ł}}$ będącego częścią lub całą krawędzią $\text{IN}^{{\prime}}$ , znowu zgodnie z zależnością z Obserwacji 6.1 w Wykładzie VI.

Uwaga. Przypomnianego tu w (B) opisu zbioru $L(\{ i\})$ (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

$\ne\left(\ \frac{\alpha _{i}}{\beta _{i}},\:\frac{\gamma _{j}}{\delta _{j}}\,\,\Big|\:\, i\in\text{IN},\, j\in\text{OUT},\,\beta _{i}<0,\,\delta _{j}<0\right)\quad\quad\forall\,\emptyset\ne\text{IN}\subset\{ 1,\, 2,\dots,\, k\}\,,$

(15.24)

wtedy łamaną wierzchołkową $\overline{\text{Ł}}$ można odzyskiwać od końca do początku: od $E_{{\min}}$ (i $\lambda _{E}=-\infty$ ) do $E_{{\max}}$ (i $\lambda _{E}=+\infty$ ). W dyskusji jej przebiegu, w pełni analogicznej do tej przedstawionej w Wykładzie XV, akcentuje się wtedy tylko progowe wartości $\lambda^{{\text{IN}}}_{{\text{hi}}}$ , IN – ściany aktywne, goszczące łamaną $\overline{\text{Ł}}$ . Warunki (15.24) gwarantują wtedy z naddatkiem brak kolizji przy zmianach ścian. Zatem $\overline{\text{Ł}}$ 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.

Analiza Portfelowa i Rynki Kapitałowe 1

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

Definicja 15.1

Uwaga 15.1

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

Ćwiczenie 15.1

Uwaga 15.2

Uwaga 15.3

Wniosek 15.1

Stwierdzenie 15.1

Definicja 15.2

Wniosek 15.2

Uwaga 15.4

Ćwiczenie 15.2 (kontrolne)