Metoda redukcji Hamiltonowskej dla problemów PL na simpleksie.

Rozważmy ideę programowania dynamicznego na przykładzie rozwiązania problemów PL na simpleksie. Niech $M$ oznacza zwykły simpleks

$$M:=\{p \in \mathbb{R}^{N}: \, \sum_{j=1}^{n}p_{j}=1, \, p_{j} \in \mathbb{R}_{+}\}$$ (10.1)

i postawmy taki problem programowanie liniowego na $M$:

$$\max_{p \in \mathbb{R}^{n}}g_{c}(p)=g_{c}(\overline{p}) -?,$$ (10.2)

gdzie $g_{c}(p):=\frac{1}{2}<c,p>, \, c \in \mathbb{R}^{n}$, jest funkcją celu, $\overline{p} \in M$ jest punktem osią-gnięcia maksumum w () i $<\cdot,\cdot>$ jak zawsze, jest iloczynem skalarnym w $\mathbb{R}^{n}$.

Jest oczywistym, że problem () ma zawsze rozwiązanie $\overline{p} \in M$, ponieważ funkcja $g_{c}: \, \mathbb{R}^{n}_{+}\to \mathbb{R}$ jest ciągła, a $M$ jest zbiorem zwartym. Żeby podać najprostszą demonstrację metody redukcji (Hamiltonowskiej), wprowadźmy następne pomocnicze odwzorowanie sfery $\mathbb{S}^{n-1}$ na $M$, tj. takie $\Phi: \, \mathbb{R}^{n} \to \mathbb{R}^{n}_{+}$, $\Im$ $\Phi \big\vert _{\mathbb{S}^{n-1}}=M$, gdzie

$$\Phi(x)\big\vert _{\mathbb{S}^{n-1}}:= \{p_{j}:=x_{j}^{2} \in \mathbb{R}_{+}, \, j= \overline{1,n}: \, \sum_{j=1}^{n}x_{j}^{2}=1\}$$ (10.3)

Jest oczywistym z (), że $\Phi^{-1}(M)=\mathbb{S}^{n-1}$. Niech $\overline{x} \in \mathbb{S}^{n-1}$ jest punktem ekstremum dla problemu

$$G_{c}(x):=\frac{1}{2}<c,\Phi(x)> \rightarrow$$ (10.4)

$$\rightarrow \max_{x \in \mathbb{S}^{n-1}}\frac{1}{2}<c,\Phi(x)> \Rightarrow \frac{1}{2}<c,\Phi(\overline{x})>,$$

który przez wyrażenie $\overline{p}:=\Phi(\overline{x}) \in M$ rozwiązuje, oczywiście problem wyjściowy ().

Warunek ${\vert x\vert}^{2}=1, \, x \in \mathbb{S}^{n-1}$, może być rozważany jako odwzorowanie
$f: \, \mathbb{R}^{n} \to \mathbb{R}$ z ograniczeniem

$$f(x)=<x,x>\,-\,1\,=\,0, \quad x \in \mathbb{R}^{n}.$$ (10.5)

Rozważmy teraz funkcjonał celu $G_{c}: \, \mathbb{R}^{n} \to \mathbb{R}$ i skonstruujmy dla niego odpowiednie tzw. gradientowe pole wektorowe

$$K_{c}(x):=\nabla_{x}G_{c}(x)=D(x)c,$$ (10.6)

gdzie dla $x \in \mathbb{R}^{n}\quad D(x):= diag (x_{1},x_{2},x_{2}, \ldots x_{n})$ jest macierzą diagonalną. Pole wektorowe () definiuje na $\mathbb{R}^{n}$ układ dynamiczny

$$\frac{d x}{d t}= K_{c}(x),$$ (10.7)

dla którego funkcjonał $G_{c}: \, \mathbb{R}^{n} \to \mathbb{R}$ jest, jak to prosto sprawdzić, funkcją Lapunowa, tj:

$$\frac{d G_{c}(x)}{d t}=<D(x)c,D(x)c> \geq 0$$ (10.8)

dla wszystkich $x\in \mathbb{R}^{n}$ i $t \in \mathbb{R}$. Zakładając teraz, że $0 \neq x \in \overline{\Omega}$, gdzie
$\Omega \subset \Phi^{-1}(M)$ jest pewnym obszarem w $\mathbb{R}^{n}$, dość prosto zobaczyć z () że funkcjonał $(G_{c} \circ x):\mathbb{R}_{t}\mathbb{\times}{R}^{n}\to\mathbb{R}$ jest względem parametru $t \in \mathbb{R}$ rosnącym wzdłuż trajektorii pola wektorowego (), przyjmując swoje wartości maksymalne na zwartym zbiorze $\overline{\Omega} \subset \mathbb{R}^{n}$. Tę wartość maksymalną dość prosto obliczyć z takiego warunku:

$$\max_{x \in \overline{\Omega}}G_{c}(x)=\max_{x \in \partial{\Omega}}G_{c}(x)=$$ (10.9)

$$\max G_{c}\Big( x\big(T(x_{0}; \Omega), x_{0}\big)\Big),$$

gdzie z definicji, trajektoria $x: \, \mathbb{R}_{t} \times \Omega \to \mathbb{R}^{n}$ pola wektorowego () z warunkiem początkowym w punkcie $x_{0} \in \Omega \quad (x_{0} \not \in \partial \Omega !)$ koniecznie przecina brzeg $\partial \Omega$ obszaru $\Omega$ w momencie czasu $t =T(x_{0};\Omega) \in \mathbb{R}_{+}$, który prosto znaleźć w sposób analityczny z warunku $x(T(x_{0};\Omega);x_{0}) \in \partial \Omega$. Teraz biorąc do uwagi że funkcjonał $\overline{G}_{c}:\, \Omega \to \mathbb{R}$, gdzie

$$\overline{G_{c}}(x_{0}):= G_{c}(x(T(x_{0};\Omega),x_{0}))$$ (10.10)

jest zdefiniowany dla wszystkich punktów wewnętrznych $x_{0} \in \Omega$, prosto znajdujemy z () dość zręczny algorytm analityczny dla znalezienia ekstremum ()

$$\max_{x \in \overline{\Omega}}G_{c}(x)=\max_{x_{0} \in \Omega}\overline{G_{c}}(x_{0})=\overline{G_{c}}(\overline{x_{0}}),$$ (10.11)

gdzie punkt wewnętrzny $\overline{x_{0}} \in \Omega$ jest tutaj wyliczany z koniecznego warunku Fermat'a:

$$\nabla\overline{G_{c}}(\overline{x_{0}})=0$$ (10.12)

który na mocy () będzie i wystarczającym.

Ten algorytm znalezienia ekstremum () można także adaptować dla przypadku kiedy zwarty zbiór $\overline{\Omega}=\mathbb{S}^{n-1} \subset \mathbb{R}^{n}$ jest mniejszego wymiaru mając miarę Lebesgue'a zero w $\mathbb{R}^{n}$.

W tym celu wykorzystamy metodę rzutowania gradientowego pola wektorowego () na kostyczną przestrzeń $T(\mathbb{S}^{n-1})$ do sfery $\mathbb{S}^{n-1}$. Ponieważ przestrzeń styczna $T(\mathbb{S}^{n-1})$ jest definiowana jako przestrzeń liniowa, prostopadła do wektora $\nabla_{x}H(x) \in T_{x}(\mathbb{R}^{n})$ dla każdego punktu $x \in \mathbb{S}^{n-1}$, bo dość prosto znajdujemy że pole () zrzutowane na $T(\mathbb{S}^{n-1})$ ma postać

$$\overline{K_{c}}(x)=D(x)c -<D(x)c,x>x$$ (10.13)

dla każdego $x \in \mathbb{S}^{n-1} \subset \mathbb{R}^{n}$.

Teraz znajdujemy się w sytuacji podobnej do opisanej wyżej, tj. funkcjonał () pozostaje funkcją Lapunowa dla pola wektorowego (), stycznego do sfery $\mathbb{S}^{n-1}$:

$$\frac{d G_{c}(x)}{d t}=<\overline{K_{c}}(x),\overline{K_{c}}(x)>\, \geq 0$$ (10.14)

dla wszystkich $x \in \mathbb{S}^{n-1}$ i $t \in \mathbb{R}$, gdzie

$$\frac{d x}{d t}=\overline{K_{c}}(x).$$ (10.15)

Wyrażenie () ma sens dla wszystkich $x \in \mathbb{S}^{n-1}$, ponieważ sfera $\mathbb{S}^{n-1}$ jest oczywiście niezmienniczym zbiorem dla pola wektorowego () w $\mathbb{R}^{n}$. Biorąc pod uwagę, że funkcjonał $G_{c}: \, \mathbb{R}^{n} \to \mathbb{R}$ jest w rzeczywistości teraz określony na $\mathbb{S}^{n-1} \subset \mathbb{R}^{n}$ poprzez orbity pola wektorowego () na $\mathbb{S}^{n-1}$, to można skonstruować zredukowaną funkcję $\overline{G}_{c}: \, \mathbb{R}_{t}^{1} \times \mathbb{S}^{n-1} \to \mathbb{R}$ jako wyrażenie

$$\overline{G}_{c}(t;x_{0}):= G_{c}\big( x(t;x_{0})\big),$$ (10.16)

gdzie $t \in \mathbb{R}^{1}, \quad x_{0} \in \mathbb{S}^{n-1}$ oraz $x: \, \mathbb{R} \times \mathbb{S}^{n-1} \to \mathbb{S}^{n-1}$ jest odpowiednią orbitą pola wektorowego (). Ponieważ funkcja () jest ograniczona na $\mathbb{S}^{n-1}$ na mocy jej ciągłości dla wszystkich $t \in \mathbb{R}^{1}$, to istnieją jej ekstremalne wartości przy $t \to \pm\infty$ w pewnych punktach $\overline{x}_{\pm} \in \mathbb{S}^{n-1}$, gdzie względem (), pole wektorowe () zeruje się, tj.

$$\overline{K_{c}}(\overline{x}_{\pm})=0.$$ (10.17)

Ostatnie wyrażenie oznacza że punkty osobliwe $\overline{x}_{\pm} \in \mathbb{S}^{n-1}$ pola wektorowego () rozwiązują problem znalezienia ekstermum (), a tak więc i problemu programowania liniowego () na sympleksie $M \subset \mathbb{R}^{n}$. Przy tym oczywiście, $\overline{x}_{\pm}=\lim_{t \to \pm \infty}x(t;x_{0})$, dla dowolnego $x_{0} \in \mathbb{S}^{n-1}$, który oczywiście, nie powinien być punktem osobliwym. Tak więc wystarczy znaleźć granicę $\overline{x}_{\pm} \in \mathbb{S}^{n-1}$ przy pomocy metod analitycznych lub komputerowo-obliczeniowych, żeby przy pomocy odwzorowania () w postaci $\overline{p}_{\pm}=\Phi(\overline{x}_{\pm})\in M$ odzyskać rozwiązanie problemu PL ().

Przejdziemy teraz do wprowadzenia pojęcia redukcji Hamiltonowskiej problemów PL. Istota jej polega na znalezieniu pola wektorowego () w postaci równoważnej do odpowiedniej redukcji Hamiltonowskiej (typu Marsdena - Weinsteina) zastosowanej do specjalnego Hamiltonowego pola wektorowego na rozszerzonej przestrzeni fazowej $\mathbb{R}^{n} \times \mathbb{R}^{n} \ni (x,c)$.

Jako pierwszy krok tego schematu zadajmy na przestrzeni fazowej
$\mathbb{R}^{2n} =\mathbb{R}^{n} \times \mathbb{R}^{n}$ niekanoniczną strukturę Poissona, tj. ,,nawiasy Poissona''
w postaci

$$\{x_{i},x_{j}\}= \delta_{ij}x_{j}, \quad \{x_{i},x_{j}\}=0=\{e_{i},e_{j}\}, \quad i,j=\overline{1,n},$$ (10.18)

gdzie $(x,c) \in \mathbb{R}^{n} \times \mathbb{R}^{n}$. Strukturze Poissona () odpowiada tzw. struktura symlektyczna na $\mathbb{R}^{2n}$, którą zadaje się przez 2-formę symplektyczną $\omega^{(2)} \in \Lambda^{2}(\mathbb{R}^{2n})$, gdzie

$$\omega^{(2)}(x,c)=\sum_{j=1}^{n} d c_{j} \wedge \frac{d x_{j}}{x_{j}}$$ (10.19)

dla wszystkich $(x,c) \in \mathbb{R}^{2n} \backslash \{(0,c)\}$.

Struktura symplektyczna () (lub struktura ()) wybiera się wzglę-dem jednego warunku: gradientowe pole wektorowe () na $\mathbb{R}^{n}$ z dołączonym trywialnym polem wektorowym $\frac{d c}{d t}=0$ dla $t \in \mathbb{R}$ i $c \in \mathbb{R}^{n}$ jest równoważne Hamiltonowemu polu wektorowemu na $\mathbb{R}^{2n}$ wg. struktury symplektycznej () i z ustaloną funkcją Hamiltonową $H: \, \mathbb{R}^{2n} \to \mathbb{R}$, gdzie w naszym przypadku:

$$H(x,c):=\frac{1}{2}<c,c>$$ (10.20)

dla wszystkich $(x,c) \in \mathbb{R}^{2n}$. To znaczy wg. definicji, że pole wektorowe $K: \, \mathbb{R}^{2n} \to T(\mathbb{R}^{2n})$ znalezione wg. reguły

$$i_{K}\omega^{(2)} =-d H,$$ (10.21)

spełnia warunek

$$K(x,c)=(K_{c}(x),0).$$ (10.22)

dla wszystkich $(x,c) \in \mathbb{R}^{2n}$.

Formalnie to znaczy wobec struktury symplektycznej (), że jest ona jednym z rozwiązań równania Noether:

$$L_{K}\omega^{(2)}=0,$$ (10.23)

gdzie $L_{K}: \, \Lambda (\mathbb{R}^{2n}) \to \Lambda (\mathbb{R}^{2n})$ oznacza tzw. pochodną Liego wzdłuż pola wektorowego $K: \, \mathbb{R}^{2n} \to T(\mathbb{R}^{2n})$ zadanego w postaci (). Biorąc do uwagi wzór Cartan'a

$$L_{K}=i_{K}d+ d i_{K},$$ (10.24)

gdzie $i_{K}: \, \Lambda (\mathbb{R}^{2n}) \to \Lambda (\mathbb{R}^{2n})$ jest odpowiednio różniczkowaniem wewnętrznym algebry form różniczkowalnych $\Lambda (\mathbb{R}^{2n})$ wzdłuż pola wektorowego
$K: \, \mathbb{R}^{2n} \to T(\mathbb{R}^{2n})$, a $d : \, \Lambda(\mathbb{R}^{2n}) \to \Lambda (\mathbb{R}^{2n})$ jest różniczkowaniem zewnętrznym równania () może być przepisane też w postaci równoważnej jako

$$i_{K} d \omega^{(2)} + d i_{K} \omega^{(2)}=0,$$ (10.25)

które wg. warunku symplektyczności $d \omega^{(2)}=0$ powoduje równość (). Z innej strony, jeśli wprowadzić skośniesymetrzyczne odwzorowanie
$\vartheta: \, \mathbb{R}^{2n} \to \mathcal{S}p(\mathbb{R}^{2n})$, takie że

$$\omega^{(2)}(x,c):=<d c, \vartheta^{-1}d x>$$ (10.26)

gdzie macierz $\vartheta^{-1}: \, \mathbb{R}^{2n} \to \mathcal{S}p (\mathbb{R}^{2n})$, oczywiście istnieje dla p.w $(x,c) \in \mathbb{R}^{2n}$. Wtedy równania () lub () będzie liniowym równaniem na macierz $\vartheta: \, \mathbb{R}^{2n} \to \mathcal{S}p(\mathbb{R}^{2n})$ w takiej postaci:

$${\vartheta.}^{'} K - {\vartheta K'}^{*} - {K.}^{'} \vartheta =0,$$ (10.27)

gdzie ,, . '' oznacza zwykłą pochodną Freshet'a odpowiednich odwzorowań na $\mathbb{R}^{2n}$, a ,, * '' oznacza operację zwykłego sprzężenia wg. iloczynu skalarnego na $\mathbb{R}^{2n}$.

Po sprawdzenieu bezpośrednio że odwzorowanie $\vartheta: \, \mathbb{R}^{2n} \to \mathcal{S}p(R^{2n})$, gdzie

$$\vartheta(x,c)=D(x)$$ (10.28)

dla wszystkich $(x,c) \in \mathbb{R}^{2n}$, spełnia równanie () otrzymujemy przy $x \neq 0$ wyrażenie () dla struktury symplektycznej () na $\mathbb{R}^{2n}$. Wykorzystując dalej równość (), można znaleźć odpowiednią funkcję Hamiltonona () na $\mathbb{R}^{2n}$.

Teraz jesteśmy w stanie wykonać redukcję Hamiltonowską dla pola wektorowego () na $\mathbb{R}^{2n}$ względem komutującego wobec niego pola wektorowego $K_{\gamma}: \, \mathbb{R}^{2n} \to T(\mathbb{R}^{2n})$, zadanego poprzez funkcję Hamiltona
$\gamma: \, \mathbb{R}^{2n} \to \mathbb{R}$, gdzie

$$\gamma (x,c):=<e,c>$$ (10.29)

oraz $e:=(1,1,\cdots,1)^{T} \in \mathbb{R}^{n}, \quad (x,c) \in \mathbb{R}^{2n}$. Jest jasnym że $\{\gamma,H\}=0$, co powoduje $[K,K_{\gamma}]=0$ na $\mathbb{R}^{2n}$, gdzie

$$K_{\gamma}(x,c)=(D(x)e,0),$$ (10.30)

dla wszystkich $(x,c) \in \mathbb{R}^{2n}$. Redukcja przestrzeni fazowej $\mathbb{R}^{2n}$ wg. orbit pola wektorowego () oznacza prosto, że można skonstruować odwzorowanie równoważności takich punktów $(x,c)$ oraz $(y,c) \in \mathbb{R}^{2n}$, które mogą być połączone przez orbitę pola wektorowego (). Tak więc, opierając się na (), to odwzorowanie redukcji $r_{\gamma}: \, \mathbb{R}^{2n} \to \mathbb{S}^{n-1} \times \mathbb{R}^{n}$ może być zadane w postaci dokładnej

$$r_{\gamma}(x,c):=(\frac{x}{\Vert x\Vert},c)$$ (10.31)

która uwzględnia naszą więź $<x,x>=1$ ponieważ $\Phi(x) \in M$ dla wszystkich $x \in \mathbb{S}^{n-1}$. Rzeczywiście dla wszystkich $x\in \mathbb{R}^{n}$ wektor $\frac{x}{\Vert x\Vert} \in \mathbb{S}^{n-1}$ nie zależy od pola wektorowego (). Jest jasnym, że () rzutuje przestrzeń $\mathbb{R}^{2n}$ na $\mathbb{S}^{n-1} \times \mathbb{R}^{n}$, która jest podstawową dla nas względem odwzorowanie () i problemu PL () i (). Tak więc rzutowanie () rozważemy jako zadane. Wtedy powstaje problem znalezienia pola wektorowego () i funkcji Hamiltona (). Zróbmy to w taki sposób: niech punkt
$x=x(\tau,y) \in \mathbb{R}^{n}, \,\tau \in \mathbb{R}$, jest rzutowany poprzez () w stały punkt
$y \in \mathbb{S}^{n-1}: \, r_{\gamma}(x(t;y),c)=(y,c) \in \mathbb{S}^{n-1} \times \mathbb{R}^{n}$. To znaczy, że pole gradientowe $\frac{d x}{d \tau}= \frac{1}{2} \nabla (x^2 - 1)=D(x)e$ generuje orbitę $x(\tau;y)=y \Vert x(\tau;y)\Vert$ dla każdego $\tau \in \mathbb{R}$ i $y \in \mathbb{S}^{n-1}$. Stąd znajdujemy wprost że $\frac{d x}{d \tau}=x, \, \tau \in \mathbb{R}$. Wtedy, oczywi-ście, $\frac{d x}{ d \tau}= D(x)e$, co daje dokładnie (). Co jeszcze nie sprawdzono, lecz jest podstawowym, to komutatywność pól wektorowych ()
i $K_{\gamma}:=(D(x)e,0)$. Ostatnią własność sprawdzamy wprost. Tak więc, ponieważ jednocześnie zachodzi równość $L_{K_{\gamma}} \omega^{(2)}=0$, istnieje funkcja Hamiltona
$\gamma: \, \mathbb{R}^{2n} \to \mathbb{R}$, dokładnie taka jak (). Jako uwagę przytoczymy tylko wzmiankę o tym że takie pole wektorowe $K_{\gamma}: \, \mathbb{R}^{2n} \to T(\mathbb{R}^{2n})$, które komutuje z polem () i dokonuje redukcje $r_{\gamma}: \, \mathbb{R}^{2n} \to \mathbb{S}^{n-1} \times \mathbb{R}^{n}$, jest niejedyne i każde może być skonstruowane w podobny sposób jak wyżej, biorąc gradient funkcji ograniczenia $f(x):=\frac{1}{2} (x^{2}-1)k(x)$ gdzie $k:\, \mathbb{R}^{n} \to \mathbb{R}^{n}$ jest a priori p.w. dodatnia : $K_{\gamma}:=(\nabla f(x),0),\,x\in \mathbb{R}^{n}$. Na podstawie rzutowania () można teraz zrzutować pole wektorowe () na pole wektorowe $\overline{K}:\mathbb{S}^{n-1}\times \mathbb{R}^{n}\longrightarrow T(\mathbb{S}^{n-1} \times \mathbb{R}^{n})$ w taki sposób, że zachodzi równość:

$$\overline{K}(r_{\gamma}(x,c))= r_{\gamma*}K(x,c)$$ (10.32)

dla wszystkich $(x,c) \in \mathbb{R}^{2n}$, gdzie $r_{\gamma*}: \, T(\mathbb{R}^{2n}) \to T(\mathbb{S}^{n-1} \times \mathbb{R}^{n})$ jest odpowiednim do () odwzorowaniem stycznym. Jako wynik tej redukcji na $\mathbb{S}^{n-1} \times \mathbb{R}^{n}$ można sformułować taki lemat

10.1   Lemat Zredukowane pola wektorowe $\overline{K}: \, \mathbb{S}^{n-1} \times \mathbb{R}^{n} \to T(\mathbb{S}^{n-1} \times \mathbb{R}^{n})$ oraz $(\overline{K_{c}},0): \mathbb{S}^{n-1} \times \mathbb{R}^{n} \to T(\mathbb{S}^{n-1} \times \mathbb{R}^{n})$ są równe.

$\lhd$ Dowód lematu jest wprost wyliczając wyrażenie () $\rhd$
Ponieważ redukcja () jest niezmiennicza wg parametru $c \in \mathbb{R}^{n}$, można sformułować na podstawie równości $\overline{K}=(\overline{K_{c}},0)$ oraz własności () następu-jące twierdzenie.

10.2   Twierdzenie. Punkty krytyczne $(\overline{x}_{\pm}, c) \in \mathbb{S}^{n-1} \times \mathbb{R}^{n}$ pola wektorowego $\overline{K}: \, \mathbb{S}^{n-1} \times \mathbb{R}^{n} \to \mathbb{S}^{n-1}\times \mathbb{R}^{n}$ spełniają następne warunki graniczne:

$$\Phi(x)=p, \quad \inf_{p \in M}\frac{1}{2}<c,p>=\frac{1}{2}<c,\overline{p}_{-}>,$$ (10.33)

$$\lim_{t \to \pm \infty}x(t;x_{0})= \overline{x}_{\pm} \in \mathb... ...{n-1}, \quad \sup_{p \in M}\frac{1}{2}<c,p>=\frac{1}{2}<c,\overline{p}_{+}>,$$

dla każdego nie krytycznego punktu $x_{0} \in \mathbb{S}^{n-1}$ i dowolnego $c \in \mathbb{R}^{n}$.