Zagadnienia

6. Warunki regularności i przykłady

W tym rozdziale podamy warunki dostateczne równości stożka kierunków stycznych T({\bar{\mathbf{x}}}) i stożka kierunków stycznych dla ograniczeń zlinearyzowanych T_{{lin}}({\bar{\mathbf{x}}}). Przypomnijmy, że jest to główne założenie twierdzenia Kuhna-Tuckera, tw. 5.2, opisującego warunek konieczny pierwszego rzędu dla lokalnego rozwiązania problemu optymalizacyjnego z ograniczeniami nierównościowymi (5.3).

6.1. Warunki regularności

Sformułujemy teraz trzy warunki dostateczne równości T({\bar{\mathbf{x}}})=T_{{lin}}({\bar{\mathbf{x}}}), zwane warunkami regularności. Dowody dostateczności podamy w kolejnych twierdzeniach.

Definicja 6.1

W punkcie {\bar{\mathbf{x}}}\in W spełniony jest:

  • warunek liniowej niezależności, jeśli funkcje g_{i}, i\notin I({\bar{\mathbf{x}}}), są ciągłe w {\bar{\mathbf{x}}} oraz wektory Dg_{i}({\bar{\mathbf{x}}}), dla i\in I({\bar{\mathbf{x}}}), są liniowo niezależne,

  • warunek afiniczności, jeśli funkcje g_{i}, i\in I({\bar{\mathbf{x}}}), są afiniczne oraz funkcje g_{i}, i\notin I({\bar{\mathbf{x}}}), są ciągłe w {\bar{\mathbf{x}}},

  • warunek Slatera, jeśli funkcje g_{i}, i\in I({\bar{\mathbf{x}}}) są pseudowypukłe w {\bar{\mathbf{x}}}, funkcje g_{i}, i\notin I({\bar{\mathbf{x}}}), są ciągłe w {\bar{\mathbf{x}}} oraz istnieje \mathbf{x}\in\mathbb{X}, dla którego g_{i}(\mathbf{x})<0 dla i\in I({\bar{\mathbf{x}}}).

Zauważmy, że w warunku Slatera nie wymagamy, aby punkt \mathbf{x} spełniał warunki ograniczeń nieaktywnych, tzn. \mathbf{x} nie musi być w zbiorze W.

Twierdzenie 6.1

Jeśli w punkcie {\bar{\mathbf{x}}}\in W spełniony jest warunek afiniczności, to T({\bar{\mathbf{x}}})=T_{{lin}}({\bar{\mathbf{x}}}).

Dowód

Zawieranie T({\bar{\mathbf{x}}})\subset T_{{lin}}({\bar{\mathbf{x}}}) wynika z lematu 5.2. Wystarczy zatem wykazać zawieranie w drugą stronę.

Niech \mathbf{d}\in T_{{lin}}({\bar{\mathbf{x}}}). Udowodnimy, że istnieje \lambda^{*}>0, taka że cały odcinek {\bar{\mathbf{x}}}+\lambda\mathbf{d}, \lambda\in[0,\lambda^{*}], zawarty jest w W:

\big\{{\bar{\mathbf{x}}}+\lambda\mathbf{d}:\lambda\in[0,\lambda^{*})\big\}\subset W. (6.1)

Zauważmy, że g_{i}({\bar{\mathbf{x}}})<0 dla i\notin I({\bar{\mathbf{x}}}). Z ciągłości tych funkcji w {\bar{\mathbf{x}}} wynika, że istnieje \lambda^{*}>0, dla której g_{i}({\bar{\mathbf{x}}}+\lambda\mathbf{d})\le 0, i\notin I({\bar{\mathbf{x}}}), \lambda\in[0,\lambda^{*}]. Pozostaje jeszcze wykazać, że nierówność taka zachodzi dla ograniczeń aktywnych. Ustalmy i\in I({\bar{\mathbf{x}}}). Z definicji \mathbf{d} wiemy, że Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}\le 0. Ograniczenie g_{i} jest afiniczne, czyli postaci g_{i}(\mathbf{x})=\mathbf{a}_{i}^{T}\mathbf{x}+b_{i}, gdzie \mathbf{a}_{i}\in\mathbb{R}^{n}, b_{i}\in\mathbb{R}. Zatem Dg_{i}({\bar{\mathbf{x}}})d=\mathbf{a}_{i}^{T}\mathbf{d}. Z faktu, że g_{i} jest aktywne w {\bar{\mathbf{x}}} dostajemy również 0=g_{i}({\bar{\mathbf{x}}})=\mathbf{a}_{i}^{T}{\bar{\mathbf{x}}}+b_{i}. Stąd dla dowolnego \lambda\ge 0 mamy

0\ge\lambda\mathbf{a}_{i}^{T}\mathbf{d}=\lambda\mathbf{a}_{i}^{T}\mathbf{d}+\underset{0}{\underbrace{\mathbf{a}_{i}^{T}{\bar{\mathbf{x}}}+b_{i}}}=\mathbf{a}_{i}^{T}({\bar{\mathbf{x}}}+\lambda\mathbf{d})+b_{i}=g_{i}({\bar{\mathbf{x}}}+\lambda\mathbf{d}).

Dowodzi to (6.1).

Pozostaje już tylko skonstruować ciąg (\mathbf{x}_{k})\subset W, \mathbf{x}_{k}\to{\bar{\mathbf{x}}} i (\lambda _{k})\subset(0,\infty). Kładziemy

\mathbf{x}_{k}={\bar{\mathbf{x}}}+\frac{\lambda^{*}}{k}\mathbf{d},\qquad\lambda _{k}=\frac{k}{\lambda^{*}}.

Wówczas \mathbf{x}_{k}\in W, \mathbf{x}_{k}\to\mathbf{x} oraz \lambda _{k}(\mathbf{x}_{k}-\mathbf{x})=\mathbf{d}, czyli trywialnie

\lim _{{k\to\infty}}\lambda _{k}(\mathbf{x}_{k}-{\bar{\mathbf{x}}})=\mathbf{d},

a zatem \mathbf{d}\in T({\bar{\mathbf{x}}}).

Przed przystąpieniem do dowodu analogicznych twierdzeń dla pozostałych warunków regularności sformułujemy pomocniczy lemat. Wprowadźmy zbiór

T_{{int}}({\bar{\mathbf{x}}})=\big\{\mathbf{d}\in\mathbb{R}^{n}:\ \forall\  i\in I({\bar{\mathbf{x}}})\quad Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}<0\big\}.
Uwaga 6.1

Zauważmy, że jeśli w punkcie {\bar{\mathbf{x}}}\in W funkcje g_{i}, i\in I({\bar{\mathbf{x}}}), są różniczkowalne w {\bar{\mathbf{x}}}, zaś funkcje g_{i}, i\notin I({\bar{\mathbf{x}}}) są ciągłe w {\bar{\mathbf{x}}}, to \mathbf{d}\in T_{{int}}({\bar{\mathbf{x}}}) oznacza, że {\bar{\mathbf{x}}}+\lambda\mathbf{d}\in\mathop{\rm int}W dla dostatecznie małych \lambda>0.

Lemat 6.1

Niech {\bar{\mathbf{x}}}\in W oraz funkcje g_{i}, i\in I({\bar{\mathbf{x}}}), są różniczkowalne w {\bar{\mathbf{x}}}, zaś funkcje g_{i}, i\notin I({\bar{\mathbf{x}}}) są ciągłe w {\bar{\mathbf{x}}}. Wówczas

  • I) T_{{int}}({\bar{\mathbf{x}}})\subset T({\bar{\mathbf{x}}}),

  • II) Jeśli T_{{int}}({\bar{\mathbf{x}}})\ne\emptyset, to \mathop{\rm cl}(T_{{int}}({\bar{\mathbf{x}}}))=T_{{lin}}({\bar{\mathbf{x}}}).

Dowód

Dowód (I) zostawiamy jako ćwiczenie. Do dowodu (II) zauważmy, że T_{{int}}({\bar{\mathbf{x}}}) jest wnętrzem zbioru T_{{lin}}({\bar{\mathbf{x}}}). Ponadto T_{{lin}}({\bar{\mathbf{x}}}) jest zbiorem wielościennym, a zatem wypukłym (patrz lemat 4.5). Zastosowanie lematu 3.2 kończy dowód.

Twierdzenie 6.2

Jeśli w punkcie {\bar{\mathbf{x}}}\in W spełniony jest warunek Slatera, to T({\bar{\mathbf{x}}})=T_{{lin}}({\bar{\mathbf{x}}}).

Dowód

Pokażemy najpierw, że T_{{int}}({\bar{\mathbf{x}}})\ne\emptyset. Niech \mathbf{x}\in\mathbb{X} taki że g_{i}(\mathbf{x})<0 dla i\in I({\bar{\mathbf{x}}}). Z pseudowypukłości g_{i} w punkcie {\bar{\mathbf{x}}} dostajemy Dg_{i}({\bar{\mathbf{x}}})(\mathbf{x}-{\bar{\mathbf{x}}})<0 dla i\in I({\bar{\mathbf{x}}}), czyli (\mathbf{x}-{\bar{\mathbf{x}}})\in T_{{int}}({\bar{\mathbf{x}}}).

Na mocy lematu 6.1 mamy T_{{lin}}({\bar{\mathbf{x}}})=\mathop{\rm cl}(T_{{int}}({\bar{\mathbf{x}}})). Udowodniliśmy także, że T_{{int}}({\bar{\mathbf{x}}})\subset T({\bar{\mathbf{x}}})\subset T_{{lin}}({\bar{\mathbf{x}}}) oraz, że T({\bar{\mathbf{x}}}) jest domknięty. A zatem T_{{lin}}({\bar{\mathbf{x}}})=T({\bar{\mathbf{x}}}).

Dowód analogicznego twierdzenia dla warunku liniowej niezależności wymaga pomocniczego lematu w stylu lematu Farkasa. Wynik ten jest jednak wcześniejszy i został uzyskany przez Paul'a Gordana w 1873 roku.

Lemat 6.2 (Gordan, 1873)

Niech A będzie macierzą m\times n. Wówczas dokładnie jeden z układów ma rozwiązanie:

\text{(1)}\ \begin{cases}A\mathbf{x}<\mathbf{0},&\\
\mathbf{x}\in\mathbb{R}^{n},&\end{cases}\qquad\text{(2)}\ \begin{cases}A^{T}\mathbf{y}=\mathbf{0},&\\
\mathbf{y}\ge\mathbf{0},\ \mathbf{y}\ne\mathbf{0}&\\
\mathbf{y}\in\mathbb{R}^{m}.&\end{cases}
Dowód

Dowód rozpoczniemy od uzasadnienia, że oba te układy nie mogą mieć rozwiązania jednocześnie. Załóżmy więc przez sprzeczność, że istnieją \mathbf{x},\mathbf{y} spełniające (1)-(2). Z faktu, że \mathbf{y} rozwiązuje (2), dostajemy, że y^{T}A\mathbf{x}=0. Z drugiej strony \mathbf{x} rozwiązuje (1), czyli (Ax)_{i}<0 dla każdego i=1,\ldots,n. Pamiętając, że y_{j}\ge 0, j=1,\ldots,m, i \mathbf{y}\ne\mathbf{0} mamy \mathbf{y}^{T}A\mathbf{x}<0. Dostaliśmy więc sprzeczność, co dowodzi, że nie może istnieć jednocześnie rozwiązanie (1) i (2).

Następnym krokiem dowodu będzie wykazanie, że zawsze któryś z układów ma rozwiązanie. W tym celu udowodnimy, że jeśli układ (1) nie ma rozwiązania, to układ (2) ma rozwiązanie. W tym celu zdefiniujmy następujące zbiory wypukłe:

U=(-\infty,0)^{m},\qquad V=\{\mathbf{z}\in\mathbb{R}^{m}:\ \mathbf{z}=A\mathbf{x}\text{ dla pewnego $\mathbf{x}\in\mathbb{R}^{n}$}\}.

Z faktu, że układ (1) nie ma rozwiązania, wynika, iż zbiory te są rozłączne. Słabe twierdzenie o oddzielaniu implikuje istnienie wektora \mathbf{a}\in\mathbb{R}^{m}, \mathbf{a}\ne\mathbf{0}, takiego że

\sup _{{\mathbf{z}\in U}}\mathbf{a}^{T}\mathbf{z}\le\inf _{{\mathbf{z}\in V}}\mathbf{a}^{T}\mathbf{z}.

Wykażemy, że \mathbf{a}\ge\mathbf{0}. Przypuśćmy przeciwnie, że istnieje współrzędna a_{i}<0. Rozważmy ciąg \mathbf{z}_{n}=[-\frac{1}{n},-\frac{1}{n},\ldots,-n,\ldots,-\frac{1}{n}]^{T}, gdzie (-n) jest na i-tej pozycji. Wówczas \mathbf{z}_{n}\in U oraz \lim _{{n\to\infty}}\mathbf{a}^{T}\mathbf{z}_{n}=\infty, a zatem dostaliśmy sprzeczność, gdyż \sup _{{\mathbf{z}\in U}}\mathbf{a}^{T}\mathbf{z} jest skończone.

Wiemy zatem, że wektor \mathbf{a} ma wszystkie współrzędne nieujemne. Pociąga to \sup _{{\mathbf{z}\in U}}\mathbf{a}^{T}\mathbf{z}=0. Weźmy \mathbf{z}=A(-A^{T}\mathbf{a}). Wówczas \mathbf{z}\in V, czyli \mathbf{a}^{T}\mathbf{z}\ge 0. A zatem

0\le\mathbf{a}^{T}\mathbf{z}=\mathbf{a}^{T}A(-A^{T}\mathbf{a})=-\| A^{T}\mathbf{a}\|^{2},

co implikuje, że \| A^{T}\mathbf{a}\|=0, czyli A^{T}\mathbf{a}=\mathbf{0}. Rozwiązaniem układu (2) jest zatem \mathbf{y}=\mathbf{a}.

Twierdzenie 6.3

Jeśli w punkcie {\bar{\mathbf{x}}}\in W spełniony jest warunek liniowej niezależności, to T({\bar{\mathbf{x}}})=T_{{lin}}({\bar{\mathbf{x}}}).

Dowód

Identycznie jak w dowodzie tw. 6.2 wystarczy pokazać, że T_{{int}}({\bar{\mathbf{x}}})\ne\emptyset. Niech A będzie macierzą składającą się z gradientów Dg_{i}({\bar{\mathbf{x}}}) ograniczeń aktywnych (jako rzędów). Na mocy liniowej niezależności nie istnieje wektor \mu\in\mathbb{R}^{{|I({\bar{\mathbf{x}}})|}}, \mu\ne\mathbf{0}, o tej własności, że A^{T}\mu=\mathbf{0}. Nie istnieje więc rozwiązanie układu (2) w lemacie 6.2. A zatem ma rozwiązanie układ (1), czyli istnieje \mathbf{d}\in\mathbb{R}^{n}, takie że A\mathbf{d}<\mathbf{0}:

Dg_{i}({\bar{\mathbf{x}}})\mathbf{d}<0,\qquad\forall\  i\in I({\bar{\mathbf{x}}}).

Stąd \mathbf{d}\in T_{{int}}({\bar{\mathbf{x}}}).

6.2. Przykłady

Przykład 6.1

Rozważmy problem optymalizacji na zbiorze:

W=\big\{\mathbf{x}\in\mathbb{R}^{2}:\  x_{1}^{2}+x_{2}^{2}\le 1,\quad x_{1}+2x_{2}\le 1,\quad x_{1}-3x_{2}\le 1\big\}.

Zbiór \mathbb{X}=\mathbb{R}^{2}. Ograniczenia są opisane przez trójkę funkcji

g_{1}(x_{1},x_{2})=x_{1}^{2}+x_{2}^{2}-1,\qquad g_{2}(x_{1},x_{2})=x_{1}+2x_{2}-1,\qquad g_{3}(x_{1},x_{2})=x_{1}-3x_{2}-1.

W punkcie {\bar{\mathbf{x}}}=[1,0]^{T} wszystkie ograniczenia są aktywne i mamy

Dg_{1}({\bar{\mathbf{x}}})=[2,0],\qquad Dg_{2}({\bar{\mathbf{x}}})=[1,2],\qquad Dg_{3}({\bar{\mathbf{x}}})=[1,-3].

Warunek liniowej niezależności ograniczeń nie jest spełniony w {\bar{\mathbf{x}}}. Ograniczenia aktywne nie są również afiniczne. Pozostaje zatem sprawdzić warunek Slatera. Wszystkie funkcje ograniczeń są wypukłe, a więc także pseudowypukłe. W punkcie \mathbf{x}=[0,0]^{T} mamy g_{i}(\mathbf{x})=-1<0 dla i=1,2,3. Zachodzi więc warunek Slatera.

Przykład 6.2 (Kuhn, Tucker (1951))

Rozważmy zadanie optymalizacyjne:

\begin{cases}x_{1}\to\min,&\\
x_{2}\le x_{1}^{3},&\\
x_{2}\ge 0,&\end{cases}
Rys. 6.1. Zbiór punktów dopuszczalnych dla przykładu Kuhna-Tuckera.

Zbiór punktów dopuszczalnych W naszkicowany jest na rysunku 6.1. Zapiszmy funkcje opisujące ograniczenia:

g_{1}(x_{1},x_{2})=-x_{1}^{3}+x_{2},\qquad g_{2}(x_{1},x_{2})=-x_{2}.

Zauważmy, że w każdym punkcie dopuszczalnym, poza [0,0]^{T}, spełniony jest warunek liniowej niezależności. Widać jednak, że rozwiązaniem powyższego problemu optymalizacyjnego jest {\bar{\mathbf{x}}}=[0,0]^{T}. Niestety w tym punkcie T({\bar{\mathbf{x}}})\ne T_{{lin}}({\bar{\mathbf{x}}}):

T({\bar{\mathbf{x}}})=\big\{\mathbf{d}\in\mathbb{R}^{2}:\  d_{1}\ge 0,\quad d_{2}=0\big\},\qquad T_{{lin}}({\bar{\mathbf{x}}})=\big\{\mathbf{d}\in\mathbb{R}^{2}:\  d_{2}=0\big\}.
Przykład 6.3

Niech A będzie macierzą symetryczną n\times n. Rozważmy zadanie optymalizacyjne:

\begin{cases}\mathbf{x}^{T}A\mathbf{x}\to\max,&\\
\|\mathbf{x}\|\le 1,&\\
\mathbf{x}\in\mathbb{R}^{n}.&\end{cases}

Zapiszmy najpierw problem optymalizacyjny w kanonicznej formie. Zauważmy przy tym, że warunek \|\mathbf{x}\|\le 1 jest równoważny \|\mathbf{x}\|^{2}=\mathbf{x}^{T}\mathbf{x}\le 1.

\begin{cases}-\mathbf{x}^{T}A\mathbf{x}\to\min,&\\
\mathbf{x}^{T}\mathbf{x}-1\le 0,&\\
\mathbf{x}\in\mathbb{R}^{n}.&\end{cases}

Oznaczmy przez W zbiór punktów dopuszczalnych. Zauważmy, że w każdym punkcie dopuszczalnym spełnione są warunki liniowej niezależności i Slatera. Wynika stąd, że rozwiązanie powyższego zadania spełnia warunki konieczne pierwszego rzędu (warunki Kuhna-Tuckera (5.5)). Znajdziemy teraz wszystkie punkty ,,podejrzane”.

Warunki Kuhna-Tuckera mają następującą postać:

\begin{cases}-2\mathbf{x}^{T}A+2\mu\mathbf{x}^{T}=\mathbf{0}^{T},&\\
\mu(\mathbf{x}^{T}\mathbf{x}-1)=0,&\\
\mu\ge 0,\quad x\in\mathbb{R}^{n}.&\end{cases}

Przypadek \mathbf{x}^{T}\mathbf{x}-1<0. Wówczas \mu=0 (z powodu drugiego równania) i pierwsze równanie przyjmuje postać \mathbf{x}^{T}A=\mathbf{0}^{T}, którą poprzez transponowanie obu stron sprowadzamy do

A\mathbf{x}=\mathbf{0}.

Równanie to spełnione jest przez wszystkie \mathbf{x}\in\ker A, \| x\|<1. W szczególności ma ono co najmniej jedno rozwiązanie (\mathbf{x}=\mathbf{0}).

Przypadek \mathbf{x}^{T}\mathbf{x}-1=0. Teraz nic nie możemy powiedzieć o \mu. Może być zerowe lub dodatnie. Pierwsze równanie przyjmuje jednak postać \mu\mathbf{x}^{T}=\mathbf{x}^{T}A, które po stransponowaniu wygląda następująco:

\mu\mathbf{x}=A\mathbf{x}.

Rozwiązaniami są zatem wektory własne (\mathbf{x}) odpowiadające nieujemnym wartościom własnym (\mu). Zbiór rozwiązań może być pusty, jeśli wszystkie wartości własne są ujemne.

Podsumowując, zbiór punktów podejrzanych, czyli punktów, w których spełniony jest warunek konieczny pierwszego rzędu, ma postać:

\big\{\mathbf{x}\in\ker A:\ \| x\|<1\big\}\\
\cup\big\{\mathbf{x}\in\mathbb{R}^{2}:\ \text{$\| x\|=1$ oraz $\mathbf{x}$ jest wektorem własnym $A$ dla nieujemnej wartości własnej}\big\}.

Na obecnym etapie nie mamy żadnej techniki pozwalającej na znalezienie rozwiązania. Możemy tylko posłużyć się zdrowym rozsądkiem. Otóż, jeśli \mathbf{x}\in\ker A, to wartość funkcji celu \mathbf{x}^{T}A\mathbf{x} jest zerowa. Dla dowolnego elementu drugiego zbioru, wartość funkcji celu jest równa wartości własnej. Możemy zatem wyciągnąć następujący wniosek: jeśli maksymalna wartość własna jest dodatnia, to każdy wektor jej odpowiadający jest rozwiązaniem globalnym. Jeśli macierz A nie ma wartości własnych większych od zera, to rozwiązaniem jest dowolny punkt z jądra A o normie nie większej niż 1.

6.3. Zadania

Ćwiczenie 6.1

Uzasadnij prawdziwość stwierdzenia umieszczonego w uwadze 6.1, by później udowodnić, że T_{{int}}({\bar{\mathbf{x}}})\subset T({\bar{\mathbf{x}}}), gdzie T_{{int}}({\bar{\mathbf{x}}}) zdefiniowane jest w lemacie 6.1.

Ćwiczenie 6.2

Przez ”punkty podejrzane” problemu optymalizacyjnego rozumiemy takie punkty dopuszczalne, w których nie są spełnione warunki regularności albo spełnione są warunki konieczne pierwszego rzędu. Znajdź wszystkie punkty podejrzane dla następującego problemu optymalizacyjnego:

\begin{cases}x^{2}-6x+y^{2}+2y\to\min,&\\
x+2y-10=0,&\\
25-x^{2}-y^{2}\ge 0.&\end{cases}

Czy w którymś z nich jest rozwiązanie? Jeśli tak, to w którym? Odpowiedź uzasadnij.

Ćwiczenie 6.3

Znajdź zbiór rozwiązań problemu optymalizacyjnego

\begin{cases}\sum _{{i=1}}^{n}c_{i}x_{i}^{2}\to\min,&\\
\sum _{{i=1}}^{n}x_{i}=b,&\end{cases}

gdzie b,(c_{i})>0. Uzasadnij, że są to wszystkie rozwiązania.

Ćwiczenie 6.4

Znajdź rozwiązania globalne problemu optymalizacyjnego

\begin{cases}x_{1}^{2}+3x_{2}^{2}-x_{1}\to\min,&\\
x_{1}^{2}-x_{2}\le 1,&\\
x_{1}+x_{2}\ge 1.\end{cases}
Ćwiczenie 6.5

Znajdź minima i maksima globalne funkcji

f(x_{1},x_{2})=4x_{1}^{2}+2x_{2}^{2}-6x_{1}x_{2}+x_{1}

na zbiorze

W=\big\{(x_{1},x_{2})\in\mathbb{R}^{2}:\ -2x_{1}+2x_{2}\ge 1,\  2x_{1}-x_{2}\le 0,\  x_{1}\le 0,\  x_{2}\ge 0\big\}.

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.