Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Optymalizacja II – 9. Warunki drugiego rzędu – MIM UW

Zagadnienia

9. Warunki drugiego rzędu

W tym rozdziale przedstawimy warunki konieczne i dostateczne drugiego rzędu, tzn. warunki sformułowane w języku drugich pochodnych oraz podsumujemy dotychczasową wiedzę dotyczącą rozwiązywania problemów optymalizacyjnych z ograniczeniami mieszanymi.

9.1. Warunki drugiego rzędu

Rozważmy problem optymalizacyjny z ograniczeniami mieszanymi (8.1). Załóżmy, że pewnym punkcie {\bar{\mathbf{x}}}\in W spełniony jest warunek pierwszego rzędu, tzn. istnieją wektory \mu\in[0,\infty)^{m} i \lambda\in\mathbb{R}^{l}, takie że

\begin{cases}Df({\bar{\mathbf{x}}})+\sum _{{i\in I({\bar{\mathbf{x}}})}}\mu _{i}Dg_{i}({\bar{\mathbf{x}}})+\sum _{{j=1}}^{l}\lambda _{j}Dh_{j}({\bar{\mathbf{x}}})=\mathbf{0}^{T},&\\
\mu _{i}g_{i}({\bar{\mathbf{x}}})=0,\quad i=1,2,\ldots,m.&\end{cases}
Definicja 9.1

Funkcją Lagrange'a nazywamy funkcję

L(\mathbf{x},\mu,\lambda)=f(\mathbf{x})+\sum _{{i=1}}^{m}\mu _{i}g_{i}(\mathbf{x})+\sum _{{j=1}}^{l}\lambda _{j}h_{j}(\mathbf{x}).

Możemy teraz zapisać warunek pierwszego rzędu w skróconej formie:

D_{x}L({\bar{\mathbf{x}}},\mu,\lambda)=\mathbf{0}^{T},\qquad\text{oraz}\qquad\mu _{i}g_{i}({\bar{\mathbf{x}}})=0,\quad i=1,2,\ldots,m,

gdzie D_{x} oznacza różniczkowanie względem zmiennej \mathbf{x}\in\mathbb{R}^{n}.

Definicja 9.2

Zbiór

I^{*}({\bar{\mathbf{x}}})=\big\{ i\in I({\bar{\mathbf{x}}}):\ \mu _{i}>0\big\}

nazywamy zbiorem ograniczeń nierównościowych mocno aktywnych.

Zbiór

I^{0}({\bar{\mathbf{x}}})=I({\bar{\mathbf{x}}})\setminus I^{*}({\bar{\mathbf{x}}})

nazywamy zbiorem ograniczeń nierównościowych słabo aktywnych.

Twierdzenie 9.1 (Warunek konieczny drugiego rzędu)

Załóżmy, że punkt {\bar{\mathbf{x}}} jest lokalnym rozwiązaniem problemu z ograniczeniami mieszanymi i spełniony jest w nim warunek liniowej niezależności. Niech \mu, \lambda będą mnożnikami Lagrange'a z warunku pierwszego rzędu. Jeśli f, g_{i}, i\in I({\bar{\mathbf{x}}}) oraz h_{j}, j=1,\ldots,l, są klasy C^{2} w otoczeniu {\bar{\mathbf{x}}}, to

\mathbf{d}^{T}D^{2}_{x}L({\bar{\mathbf{x}}},\mu,\lambda)\mathbf{d}\ge 0

dla każdego \mathbf{d}\in\mathbb{R}^{n} spełniającego

\displaystyle Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}=0,\quad i\in I({\bar{\mathbf{x}}}),
\displaystyle Dh_{j}({\bar{\mathbf{x}}})\mathbf{d}=0,\quad j=1,\ldots,l.
Dowód

Ustalmy \mathbf{d}\in\mathbb{R}^{n} jak w warunkach twierdzenia. Na mocy twierdzenia 8.5 istnieje \varepsilon>0 i krzywa \mathbf{y}:(-\varepsilon,\varepsilon)\to\mathbb{R}^{n} klasy C^{2} o następujących własnościach: \mathbf{y}(0)={\bar{\mathbf{x}}}, y^{{\prime}}(0)=\mathbf{d}, oraz dla t\in(-\varepsilon,\varepsilon) mamy h_{j}(y(t))=0, j=1,\ldots,l, i g_{i}(y(t))=0, i\in I({\bar{\mathbf{x}}}). Wynika stąd, że funkcja F(t):=L(y(t),\mu,\lambda) równa jest f(y(t)) dla t w otoczeniu 0. Z ciągłości ograniczeń nieaktywnych wnioskujemy, że y(t)\in W dla t w otoczeniu 0. Zatem F ma minimum lokalne w 0, gdyż y(0) jest minimum lokalnym f na W. Na mocy założeń, F jest klasy C^{2}. Istnienie minimum w zerze implikuje, że F^{{\prime\prime}}(0)\ge 0, a więc

0\le\mathbf{d}^{T}D^{2}_{x}L({\bar{\mathbf{x}}},\mu,\lambda)\mathbf{d}+D_{x}L({\bar{\mathbf{x}}},\mu,\lambda)y^{{\prime\prime}}(0).

To kończy dowód, gdyż w punkcie {\bar{\mathbf{x}}} spełnione są warunki pierwszego rzędu: D_{x}L({\bar{\mathbf{x}}},\mu,\lambda)=\mathbf{0}^{T}.

Bez dowodu pozostawiamy następujące uogólnienie powyższego twierdzenia:

Twierdzenie 9.2

Przy założeniach tw. 9.1 następująca nierówność

\mathbf{d}^{T}D^{2}_{x}L({\bar{\mathbf{x}}},\mu,\lambda)\mathbf{d}\ge 0

zachodzi dla każdego \mathbf{d}\in\mathbb{R}^{n} spełniającego

\displaystyle Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}=0,\quad i\in I^{*}({\bar{\mathbf{x}}}),
\displaystyle Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}\le 0,\quad i\in I^{0}({\bar{\mathbf{x}}}),
\displaystyle Dh_{j}({\bar{\mathbf{x}}})\mathbf{d}=0,\quad j=1,\ldots,l.

Podamy teraz warunek dostateczny istnienia rozwiązania lokalnego. Zwróćmy uwagę na to, że warunek ten implikuje, iż rozwiązanie jest ścisłe. Pozostaje więc szara strefa, gdzie jest spełniony warunek konieczny drugiego rzędu, lecz nie zachodzi warunek dostateczny drugiego rzędu. Podobnie jak w przypadku optymalizacji bez ograniczeń, na to nie ma niestety rady.

Twierdzenie 9.3 (Warunek dostateczny drugiego rzędu)

Załóżmy, że w punkcie {\bar{\mathbf{x}}}\in W spełniony jest warunek pierwszego rzędu, tzn. istnieją wektory \mu\in[0,\infty)^{m} i \lambda\in\mathbb{R}^{l}, takie że

\begin{cases}Df({\bar{\mathbf{x}}})+\sum _{{i\in I({\bar{\mathbf{x}}})}}\mu _{i}Dg_{i}({\bar{\mathbf{x}}})+\sum _{{j=1}}^{l}\lambda _{j}Dh_{j}({\bar{\mathbf{x}}})=\mathbf{0}^{T},&\\
\mu _{i}g_{i}({\bar{\mathbf{x}}})=0,\quad i=1,2,\ldots,m.&\end{cases} (9.1)

Załóżmy ponadto, że funkcje g_{i}, i\in I^{*}({\bar{\mathbf{x}}}), oraz h_{j}, j=1,\ldots,l, są dwukrotnie różniczkowalne w {\bar{\mathbf{x}}}. Jeśli

\mathbf{d}^{T}D^{2}_{x}L({\bar{\mathbf{x}}},\mu,\lambda)\mathbf{d}>0

dla każdego \mathbf{d}\in\mathbb{R}^{n}\setminus\mathbf{0} spełniającego

\begin{aligned}\displaystyle&\displaystyle Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}=0,\quad i\in I^{*}({\bar{\mathbf{x}}}),\\
\displaystyle&\displaystyle Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}\le 0,\quad i\in I^{0}({\bar{\mathbf{x}}}),\\
\displaystyle&\displaystyle Dh_{j}({\bar{\mathbf{x}}})\mathbf{d}=0,\quad j=1,\ldots,l,\end{aligned} (9.2)

to {\bar{\mathbf{x}}} jest ścisłym rozwiązaniem lokalnym.

Zanim przejdziemy do dowodu podkreślmy, iż w powyższym twierdzeniu nie zakłada się regularności punktu ograniczeń.

Dowód twierdzenia 9.3

Przeprowadzimy dowód przez zaprzeczenie. Załóżmy mianowicie, że {\bar{\mathbf{x}}} nie jest ścisłym rozwiązaniem lokalnym. Istnieje zatem ciąg punktów dopuszczalnych \mathbf{x}_{k}\in W, takich że \mathbf{x}_{k}\ne{\bar{\mathbf{x}}} oraz f(\mathbf{x}_{k})\le f({\bar{\mathbf{x}}}). Zdefiniujmy

\mathbf{d}_{k}=\frac{\mathbf{x}_{k}-{\bar{\mathbf{x}}}}{\|\mathbf{x}_{k}-{\bar{\mathbf{x}}}\|},\qquad\text{oraz}\qquad\lambda _{k}=\|\mathbf{x}_{k}-{\bar{\mathbf{x}}}\|.

Wówczas \mathbf{x}_{k}={\bar{\mathbf{x}}}+\lambda _{k}\mathbf{d}_{k}. Zauważmy, że \lim _{{k\to\infty}}\lambda _{k}=0. Z faktu \|\mathbf{d}_{k}\|=1 wynika, że istnieje podciąg \mathbf{d}_{{k_{n}}} zbieżny do pewnego \mathbf{d} o normie jednostkowej. Aby uprościć notację zakładamy, że od początku \mathbf{d}_{k} był zbieżny do \mathbf{d}. Oczywiście z definicji \lambda _{k} wynika, że \lim _{{k\to\infty}}\lambda _{k}=0.

W dalszej części dowodu wykażemy dwie własności \mathbf{d}: (a) \mathbf{d}^{T}D^{2}_{x}L({\bar{\mathbf{x}}},\mu,\lambda)\mathbf{d}\le 0 oraz (b) \mathbf{d} spełnia warunki (9.2). A to przeczy założeniom twierdzenia.

Rozpocznijmy od dowodu własności (a). Z definicji drugiej pochodnej:

L(\mathbf{x},\mu,\lambda)=L({\bar{\mathbf{x}}},\mu,\lambda)+D_{x}L({\bar{\mathbf{x}}},\mu,\lambda)(\mathbf{x}-{\bar{\mathbf{x}}})+\frac{1}{2}(\mathbf{x}-{\bar{\mathbf{x}}})^{T}D^{2}_{x}L({\bar{\mathbf{x}}},\mu,\lambda)(\mathbf{x}-{\bar{\mathbf{x}}})+o(\|\mathbf{x}-{\bar{\mathbf{x}}}\|^{2}).

Przypomnijmy, że L(\mathbf{x}_{k},\mu,\lambda)\le L({\bar{\mathbf{x}}},\mu,\lambda), bo f(\mathbf{x}_{k})\le f({\bar{\mathbf{x}}}) oraz g_{i}(\mathbf{x}_{k})\le g_{i}({\bar{\mathbf{x}}}) dla i\in I({\bar{\mathbf{x}}}). Z warunku pierwszego rzędu (9.1) wynika również, że D_{x}L({\bar{\mathbf{x}}},\mu,\lambda)=\mathbf{0}^{T}. Zatem

(\mathbf{x}_{k}-{\bar{\mathbf{x}}})^{T}D^{2}_{x}L({\bar{\mathbf{x}}},\mu,\lambda)(\mathbf{x}_{k}-{\bar{\mathbf{x}}})+o(\|\mathbf{x}_{k}-{\bar{\mathbf{x}}}\|^{2})\le 0.

Przypomnijmy, że \mathbf{x}_{k}={\bar{\mathbf{x}}}+\lambda _{k}\mathbf{d}_{k}. Wstawiając tą reprezentację do powyższego wzoru dostajemy:

\lambda _{k}^{2}\mathbf{d}_{k}^{T}D^{2}_{x}L({\bar{\mathbf{x}}},\mu,\lambda)\mathbf{d}_{k}+o(\lambda _{k}^{2}\|\mathbf{d}_{k}\|^{2})\le 0.

Dzielimy obie strony przez \lambda _{k}^{2}:

\mathbf{d}_{k}^{T}D^{2}_{x}L({\bar{\mathbf{x}}},\mu,\lambda)\mathbf{d}_{k}+\frac{o(\lambda _{k}^{2}\|\mathbf{d}_{k}\|^{2})}{\lambda _{k}^{2}}\le 0.

Przypomnijmy, że \|\mathbf{d}_{k}\|=1. A zatem w granicy, gdy k\to\infty, drugi składnik powyższej sumy dąży do 0. Korzystając z faktu, że \lim _{{k\to\infty}}\mathbf{d}_{k}=\mathbf{d} dostajemy

\mathbf{d}^{T}D^{2}_{x}L({\bar{\mathbf{x}}},\mu,\lambda)\mathbf{d}\le 0,

co kończy dowód faktu (a).

W dowodzie własności (b) zastosujemy podobne podejście jak powyżej. Z różniczkowalności funkcji f w punkcie {\bar{\mathbf{x}}} mamy

f(\mathbf{x}_{k})=f({\bar{\mathbf{x}}})+Df({\bar{\mathbf{x}}})(\mathbf{x}_{k}-{\bar{\mathbf{x}}})+o(\|\mathbf{x}_{k}-{\bar{\mathbf{x}}}\|).

Przypomnijmy, że f(\mathbf{x}_{k})\le f({\bar{\mathbf{x}}}), co implikuje

Df({\bar{\mathbf{x}}})(\mathbf{x}_{k}-{\bar{\mathbf{x}}})+o(\|\mathbf{x}_{k}-{\bar{\mathbf{x}}}\|)\le 0.

Korzystając znów z reprezentacji \mathbf{x}_{k}={\bar{\mathbf{x}}}+\lambda _{k}\mathbf{d}_{k} dostajemy

Df({\bar{\mathbf{x}}})\mathbf{d}_{k}+\frac{o(\lambda _{k}\|\mathbf{d}_{k}\|)}{\lambda _{k}}\le 0.

Zatem w granicy, przy k\to\infty, otrzymujemy Df({\bar{\mathbf{x}}})\mathbf{d}\le 0. Zauważając, że g_{i}(\mathbf{x}_{k})\le g_{i}({\bar{\mathbf{x}}})=0 dla i\in I({\bar{\mathbf{x}}}) i postępując podobnie jak powyżej dostajemy Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}\le 0, i\in I({\bar{\mathbf{x}}}). Analogicznie również dowodzimy, że Dh_{j}({\bar{\mathbf{x}}})\mathbf{d}=0 dla j=1,\ldots,l.

Pomnóżmy obie strony pierwszej równości w (9.1) przez \mathbf{d}:

Df({\bar{\mathbf{x}}})\mathbf{d}+\sum _{{i\in I({\bar{\mathbf{x}}})}}\mu _{i}Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}+\sum _{{j=1}}^{l}\lambda _{j}Dh_{j}({\bar{\mathbf{x}}})\mathbf{d}=0.

Suma ta składa się z wyrazów nieujemnych. Ponieważ sumują się one do zera, to wszystkie muszą być zerowe. W szczególności

Df({\bar{\mathbf{x}}})\mathbf{d}=0,\qquad\text{oraz}\qquad Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}=0,\quad i\in I^{*}({\bar{\mathbf{x}}}).

Dowiedliśmy zatem, że \mathbf{d} spełnia warunki (9.2).

9.2. Podsumowanie

Opiszemy teraz ogólny algorytm postępowania w przypadku rozwiązywania problemów optymalizacyjnych z ograniczeniami mieszanymi.

Krok 1. Szukamy punktów podejrzanych:

\displaystyle A_{1}=\{\mathbf{x}\in X: \displaystyle\text{w punkcie $\mathbf{x}$ \textbf{nie} zachodzi warunek regularności}\},
\displaystyle A_{2}=\{\mathbf{x}\in X: w punkcie \mathbf{x} zachodzi warunek regularności
\displaystyle\text{i spełnione są warunki pierwszego rzędu}\}.

Krok 2. Sprawdzamy, czy w punktach ze zbiorów A_{1},A_{2} spełnione są założenia tw. 7.6, tzw. warunki dostateczne pierwszego rzędu. Jeśli tak, to w punktach tych są rozwiązania globalne. Pozostałe kroki podejmujemy, jeśli

  • nie znaleźliśmy żadnego rozwiązania globalnego, lub

  • chcemy znaleźć wszystkie rozwiązania globalne, lub

  • chcemy znaleźć wszystkie rozwiązania lokalne.

Usuwamy ze zbiorów A_{1},A_{2} punkty, które są rozwiązaniami globalnymi. Oznaczmy nowe zbiory A^{{\prime}}_{1},A^{{\prime}}_{2}.

Krok 3. Eliminujemy ze zbioru A^{{\prime}}_{2} te punkty, gdzie nie zachodzi warunek konieczny drugiego rzędu. Pozostałe punkty oznaczamy A^{{\prime\prime}}_{2}.

Krok 4. W każdym punkcie ze zbioru A^{{\prime}}_{1}\cap A^{{\prime\prime}}_{2} sprawdzamy warunek dostateczny drugiego rzędu. Punkty, w których jest spełniony, są rozwiązaniami lokalnymi.

Krok 5. Optymalność punktów ze zbioru A^{{\prime}}_{1}\cap A^{{\prime\prime}}_{2}, w których nie jest spełniony warunek dostateczny drugiego rzędu sprawdzamy innymi metodami.

9.3. Przykład

W tym podrozdziale opiszemy bardzo dokładnie rozwiązanie następującego problemu optymalizacyjnego:

\begin{cases}(x_{1}-1)^{2}+x_{2}^{2}\to\min,&\\
2kx_{1}-x_{2}^{2}\le 0,&\\
\mathbf{x}=(x_{1},x_{2})\in\mathbb{R}^{2},&\end{cases}

gdzie k>0 jest parametrem.

Zauważmy, że w każdym punkcie, gdzie aktywne jest ograniczenie, spełniony jest warunek liniowej niezależności ograniczeń: pierwsza pochodna ograniczenia wynosi [2k,-2x_{2}]\ne\mathbf{0}^{T}. Wynika stąd, że A_{1}=\emptyset.

Funkcja Lagrange'a dla powyższego problemu ma postać:

L(x_{1},x_{2};\mu)=(x_{1}-1)^{2}+x_{2}^{2}+\mu(2kx_{1}-x_{2}^{2}).

Zapiszmy warunek pierwszego rzędu:

\displaystyle[2(x_{1}-1),2x_{2}]+\mu[2k,-2x_{2}]=\mathbf{0}^{T}, (9.3)
\displaystyle\mu(2kx_{1}-x_{2}^{2})=0, (9.4)
\displaystyle\mu\ge 0.

Sprawdźmy, czy możliwe jest \mu=0. Wówczas z równania (9.3) dostajemy

2(x_{1}-1)=0,\qquad 2x_{2}=0,

co pociąga x_{1}=1, x_{2}=0. Punkt ten nie jest dopuszczalny: nie spełnia warunku nierównościowego dla żadnego k>0. Wnioskujemy zatem, że \mu>0 i warunek konieczny pierwszego rzędu może być spełniony tylko w punktach, w których ograniczenie nierównościowe jest aktywne:

2kx_{1}-x_{2}^{2}=0. (9.5)

Rozpiszmy równanie (9.3):

\begin{cases}x_{1}-1+\mu k=0,&\\
x_{2}-\mu x_{2}=0.&\end{cases}

Z drugiego równania wynika, że albo \mu=1 albo x_{2}=0. Jeśli x_{2}=0, to z (9.5) dostajemy x_{1}=0. Punkt (0,0) wraz z mnożnikiem Lagrange'a \mu=1/k spełnia warunek pierwszego rzędu.

Rozważmy teraz przypadek \mu=1. Wówczas z równania x_{1}-1+\mu k=0 dostajemy x_{1}=1-k. Jeśli k>1, to x_{1}<0 i równanie (9.5) nie ma rozwiązania. Dla k=1 dostajemy punkt (0,0), zaś dla k\in(0,1) dwa punkty

x_{1}=1-k,\qquad x_{2}=\pm\sqrt{2k(1-k)}.

Podsumowując: A_{1}=\emptyset oraz

\displaystyle A_{2}=\{(0,0)\}\qquad\text{dla}\quad k\ge 1,
\displaystyle A_{2}=\big\{(0,0),\big(1-k,\sqrt{2k(1-k)}\big),\big(1-k,-\sqrt{2k(1-k)}\big)\big\}\qquad\text{dla}\quad 0<k<1.

Funkcja g_{1}(x_{1},x_{2})=2kx_{1}-x_{2}^{2} nie jest quasi-wypukła, wiec nie możemy skorzystać z twierdzenia 7.6 stwierdzającego dostateczność warunku pierwszego rzędu. Zatem A^{{\prime}}_{2}=A_{2}.

Przechodzimy do kroku 3 i sprawdzamy warunek konieczny drugiego rzędu dla punktów z A^{{\prime}}_{2}. Rozważmy najpierw punkt (0,0). Odpowiada mu mnożnik Lagrange'a \mu=1/k. Pierwsza pochodna funkcji Lagrange'a ma postać:

D_{x}L(x_{1},x_{2},1/k)=[(2(x_{1}-1)+2,2x_{2}(1-\frac{1}{k})].

Macierz drugich pochodnych to;

D^{2}_{x}L(x_{1},x_{2},1/k)=\begin{bmatrix}2,&0\\
0,&2(1-\frac{1}{k})\end{bmatrix}.

Na mocy twierdzenia wystarczy sprawdzić, że

\mathbf{d}^{T}\begin{bmatrix}2,&0\\
0,&2(1-\frac{1}{k})\end{bmatrix}\mathbf{d}\ge 0

dla wektorów \mathbf{d}\in\mathbb{R}^{2}\setminus\mathbf{0} spełniających Dg_{1}(0,0)\mathbf{d}=[2k,0]\mathbf{d}=0, czyli takich że d_{1}=0. Wstawiając do powyższej nierówności dostajemy (1-\frac{1}{k})d_{2}^{2}\ge 0. Nierówność ta zachodzi dla k\ge 1: w punkcie (0,0) może być rozwiązanie lokalne. Dla k<1 nierówność nie zachodzi, więc w (0,0) nie ma rozwiązania lokalnego.

Załóżmy teraz 0<k<1 i rozważmy dwa pozostałe punkty. W obu przypadkach mnożnik Lagrange'a \mu=1. Mamy zatem

\displaystyle D_{x}L(x_{1},x_{2},1)=[(2(x_{1}-1)+2k,0],
\displaystyle D^{2}_{x}L(x_{1},x_{2},1)=\begin{bmatrix}2,&0\\
0,&0\end{bmatrix}.

Macierz drugich pochodnych jest nieujemnie określona, więc warunek konieczny drugiego rzędu jest spełniony w obu punktach. Podsumowując:

\displaystyle A^{{\prime\prime}}_{2}=\{(0,0)\}\qquad\text{dla}\quad k\ge 1,
\displaystyle A^{{\prime\prime}}_{2}=\big\{\big(1-k,\sqrt{2k(1-k)}\big),\big(1-k,-\sqrt{2k(1-k)}\big)\big\}\qquad\text{dla}\quad 0<k<1.

Przechodzimy do sprawdzenia warunku dostatecznego drugiego rzędu. W przypadku k>1 macierz drugich pochodnych funkcji Lagrange'a jest dodatnio określona, więc na mocy tw. 9.3 w punkcie (0,0) jest ścisłe rozwiązanie lokalne. Niestety nie możemy nic powiedzieć o punkcie (0,0), gdy k=1.

Rozważmy przypadek 0<k<1. Zajmijmy się punktem {\bar{\mathbf{x}}}=\big(1-k,\sqrt{2k(1-k)}\big). Musimy sprawdzić warunki tw. 9.3:

\mathbf{d}^{T}\begin{bmatrix}2,&0\\
0,&0\end{bmatrix}\mathbf{d}=2d_{1}^{2}>0

dla \mathbf{d}\in\mathbb{R}^{2}\setminus\mathbf{0} spełniającego [2k,-2\sqrt{2k(1-k)}]\mathbf{d}=0, czyli d_{1}=\frac{1}{k}\sqrt{2k(1-k)}d_{2}. A zatem jeśli \mathbf{d}\ne\mathbf{0}, to d_{1}\ne 0 i w punkcie {\bar{\mathbf{x}}} spełniony jest warunek dostateczny drugiego rzędu: {\bar{\mathbf{x}}} jest ścisłym rozwiązaniem lokalnym. Analogicznie dowodzimy, że punkt \big(1-k,-\sqrt{2k(1-k)}\big) jest również ścisłym rozwiązaniem lokalnym.

Pozostaje jeszcze przypadek k=1. Choć (0,0) jest rozwiązaniem globalnym, to nie udało nam się tego pokazać korzystając z teorii Kuhna-Tuckera. Łatwo można to jednak udowodnić bezpośrednio.

9.4. Zadania

Ćwiczenie 9.1

Rozwiąż geometrycznie i analitycznie zadanie minimalizacji x_{2} na zbiorze W=\{(x_{1},x_{2}):\  x_{1}+x_{2}\ge 2,\  x_{1}^{2}+x_{2}^{2}\le 2\}.

Ćwiczenie 9.2

Niech A będzie macierzą m\times n o pełnym rzędzie (tzn. o rzędzie równym \min(m,n)). Udowodnij, że rzut na jądro \ker A jest przekształceniem liniowym zadanym wzorem

I-A^{T}(AA^{T})^{{-1}}A.

W dowodzie wykorzystaj fakt, że rzeczony rzut, to taki punkt zbioru \ker A, który jest najmniej oddalony od rzutowanego punktu.

Ćwiczenie 9.3
Rysunek pomocniczy do zadania \ref{exe:ch9:statek}
Rys. 9.1. Położenie punktów pomiarowych.

Na brzegu będącym prostym odcinkiem co 500 metrów stoją trzy stacje pomiarowe, patrz rys. 9.1. Każda z nich mierzy kąt między prostą prostopadłą do brzegu a prostą przechodzącą przez punkt pomiarowy i statek. Wyniki obserwacji są następujące:

\tilde{\alpha}_{1}=0.083,\qquad\tilde{\alpha}_{2}=0.024,\qquad\tilde{\alpha}_{3}=-0.017.

Pomiary te są obarczone małymi błędami. Skoryguj je tak, aby były zgodne tzn. wskazywały na ten sam punkt na płaszczyźnie i korekta była jak najmniejsza w sensie średniokwadratowym (suma kwadratów różnic pomiędzy zmierzonymi kątami i skorygowanymi kątami). Znajdź położenie statku względem punktów pomiarowych. W obliczeniach przyjmij, że tg(\alpha)\approx\alpha dla małych kątów \alpha.

Ćwiczenie 9.4

Metalowa belka ma przekrój trapezoidalny. Pole tego przekroju ze względów wytrzymałościowych musi wynosić S. Górna i boczna powierzchnia musi zostać zabezpieczona antykorozyjnie. Ustal tak kształt przekroju, aby powierzchnia do zabezpieczenia antykorozyjnego była jak najmniejsza.

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.