Warunki konieczne i wystarczające dla kun tuckera. Warunki konieczne minimum funkcji

Sformułowanie problemu

Rozważmy nieliniowy problem optymalizacji. Niech będą funkcje

Na warunkach .

William Karush w swojej pracy znalazł warunki konieczne w ogólnym przypadku, gdy narzucone warunki mogą zawierać zarówno równania, jak i nierówności. Niezależnie od siebie Harold Kuhn i Albert Tucker doszli do tych samych wniosków.

Warunki konieczne minimum funkcji

Jeżeli przy nałożonych ograniczeniach istnieje rozwiązanie problemu, to istnieje niezerowy wektor mnożników Lagrange'a taki, że dla funkcji Lagrange'a spełnione są warunki:

Warunki wystarczające na minimum funkcji

Wymienione warunki konieczne dla minimum funkcji nie są w ogólnym przypadku wystarczające. Istnieje kilka opcji dodatkowe warunki co czyni je wystarczającymi.

Proste sformułowanie

Jeżeli dla punktu dopuszczalnego spełnione są warunki stacjonarności, dopełniającej niesztywności i nieujemności oraz λ 1 > 0, to .

Słabsze warunki

Jeżeli dla punktu dopuszczalnego spełnione są warunki stacjonarności, uzupełniające niesztywność i nieujemność, a także ( Stan Slatera), To .

Fundacja Wikimedia. 2010.

Zobacz, jakie są „warunki Karusha-Kuhna-Tuckera” w innych słownikach:

W teorii optymalizacji warunki Karusha Kuhna Tuckera (KKT) są warunkami niezbędnymi do rozwiązania problemu programowania nieliniowego. Aby rozwiązanie było optymalne należy zrobić pewne rzeczy... ...Wikipedię

W teorii optymalizacji warunki Karusha Kuhna Tuckera (KKT) są warunkami niezbędnymi do rozwiązania problemu programowania nieliniowego. Aby rozwiązanie było optymalne, muszą być spełnione pewne warunki prawidłowości.... ...Wikipedia

William Karush William Karush Data urodzenia: 1 marca 1917 (1917 03 01) Miejsce urodzenia: Chicago, USA Data śmierci… Wikipedia

Termin ten ma inne znaczenia, patrz Optymalizacja. Optymalizacja w matematyce, informatyce i badaniach operacyjnych, problem znalezienia ekstremum (minimum lub maksimum) funkcja celu w jakiejś dziedzinie wektora skończenie wymiarowego... Wikipedia Wikipedia

Metoda mnożnika Lagrange'a, metoda znajdowania ekstremum warunkowe funkcje f(x), gdzie w odniesieniu do m ograniczeń i zmienia się od jednego do m. Spis treści 1 Opis metody... Wikipedia

Twierdzenie Kuhna-Tuckera jest uogólnieniem metod rozwiązywania problemy optymalizacyjne w dwie strony:

Programowanie liniowe do przypadku nieliniowego, który przez analogię otrzymał niezbyt udaną nazwę „programowanie nieliniowe”;

Nieliniowe ograniczenia równościowe na ograniczeniach nierówności.

Metoda i warunki Karusha-Kuhna-Tuckera ( Warunki Karusha-Kuhna-Tuckera, KKT) są formalnie niezbędnymi warunkami optymalności problemu programowania nieliniowego. Dodatkowo do warunków niezbędnych zaliczają się tzw. warunki regularności dla punktów stacjonarnych – brak degeneracji zbioru gradientów więzów. Metoda ta jest uogólnieniem metody mnożnika Lagrange’a na przypadek ograniczeń nierównościowych.

Kuhn i Tucker uogólnili metodę mnożnika Lagrange'a (do zastosowania przy konstruowaniu kryteriów optymalności dla problemów z ograniczeniami w postaci równości) na przypadek wspólne zadanie programowanie nieliniowe z ograniczeniami, zarówno w postaci równości, jak i nierówności.

Główną metodą programowania nieliniowego pozostaje nadal wykorzystanie funkcji Lagrange'a uzyskanej poprzez przeniesienie ograniczeń na funkcję celu. Z zasady tej wywodzą się także warunki Kuhna-Tuckera.

William Karush w swoim Praca dyplomowa w 1931 r. znalazł warunki konieczne w ogólnym przypadku ograniczeń równości i nierówności. Niezależnie od tego Harold Kuhn i Albert Tucker doszli do tych samych wniosków później, w 1941 roku. Ich wyniki były bardziej ogólne.

Jeżeli przy nałożonych ograniczeniach istnieje rozwiązanie problemu, to istnieje wektor mnożników Lagrange'a taki, że dla funkcji Lagrange'a spełnione są warunki:

- stacjonarność: ;

- uzupełniająca miękkość: ;

- nienegatywność:.

Wymienione warunki konieczne dla minimum funkcji nie są w ogólnym przypadku wystarczające. Istnieje kilka opcji dodatkowych warunków, które czynią je wystarczającymi:

- prosty warunek – 1) punkt jest nieruchomy, 2) spełniony jest warunek dopełniającej niesztywności, 3) mnożniki Lagrange’a;

- Stan Slatera (słabszy) – 1) punkt jest nieruchomy, 2) spełniony jest warunek dopełniającej niesztywności, 3) .

Przejdźmy bezpośrednio do dowodu twierdzenia Kuhna-Tuckera.

Jeżeli funkcja ciągła n zmiennych x = (x1,...,xn) F(x) ma w punkcie X opt maksimum, to istnieje ε > 0 takie, że dla wszystkich X z ε-sąsiedztwa punktu X Hurt

F(x)≤F(x opcja)

F(x)-F(x opcja)≤0.

Wybierzmy dwa rodzaje przyrostów x j przed siebie J współrzędne

Δx j =x j -x jopt >0,

Δx j =x j -x jopt<0.

Przejście w tych zależnościach do granicy w Δ x j→0, otrzymujemy:

Z tych relacji wynika, że

(3.6.1)

Podobną zależność można otrzymać dla przypadku funkcji minimalnej. Zatem konieczność spełnienia warunków (3.6.1) w punkcie x hurtowo funkcja maksymalna lub minimalna k(x), czyli jeśli istnieje ekstremum, to warunki (3.6.1) są spełnione. Ale równość do zera wszystkich pochodnych w tym punkcie x hurtowo nie zapewnia jeszcze istnienia w nim ekstremum, tj. warunki (3.6.1) nie są wystarczające. Geometrycznie oznacza to, że w przypadku zerowej pochodnej funkcji jednej zmiennej może istnieć punkt przegięcia, a nie maksimum (lub minimum), a w przypadku funkcji dwóch zmiennych punkt siodłowy, a nie ekstremum itp. Zatem punkty x hurtowo, w których spełnione są zależności (3.6.1), nazywane są stacjonarnymi.

Należy zauważyć, że warunek (3.6.1) uzyskano dzięki możliwości przypisania zmiennej X przyrosty dwóch znaków, czyli miejsce, w którym powstały dwie nierówności w i w . Jeśli prawidłowy zakres X ograniczone do wartości nieujemnych X≥0, następnie wewnątrz obszaru, w którym X> 0, warunek (3.6.1) pozostaje ważny, ponieważ dozwolone są tam przyrosty obu znaków. Na granicy regionu X≥ 0, gdzie X= 0, dozwolony jest tylko przyrost dodatni Δ X>0, możemy mówić tylko o pochodnej jednostronnej i z (3.6.1) wynika warunek konieczny dla maksimum:

W związku z tym warunek konieczny minimum na granicy regionu x j= 0 zostanie zapisane jako

b) Problem ekstremum warunkowego

Przy określaniu ekstremum warunkowego funkcji, gdy konieczne jest określenie maksimum (lub minimum) funkcji F(x) w warunkach ograniczających:

sol ja (x) = b ja , ja = 1, ..., m,

f(x)=maks.;

sol ja (x)=b ja ;

Stosowana jest także metoda mnożników Lagrange’a, która podobnie jak w przypadku klasycznego rachunku wariacyjnego polega na wprowadzeniu funkcji Lagrange’a

(3.6.2)

gdzie λ i są nieokreślonymi mnożnikami Lagrange'a.

Zakładając, że funkcja jest szczególnym przypadkiem funkcjonału, otrzymujemy, że warunki konieczne dla ekstremum znajdują się przez bezpośrednie różniczkowanie relacji (3.6.2) i są zapisane w postaci

Jeśli wprowadzimy wektory

relacje (17-8) i (17-9) zostaną przepisane jako

grad Φ = grad F - λ grad φ = 0; (3.6.6)

gdzie równość wektorów do zera rozumiana jest składowo.

Rysunek 3.6.1 – Wyjaśnienie problemu ekstremum warunkowego

Gdy N= 2 i M = 1 problem geometryczny znalezienie ekstremum warunkowego sprowadza się (Rys. 17-6) do znalezienia punktu styczności A krzywej φ = B do jednej z krzywych stałego poziomu F= stała

Twierdzenie 7.2. Dla problemu programowania wypukłego (7.4)–(7.6) zbiór dopuszczalne rozwiązania plan, który ma właściwość regularności, jest planem optymalnego planu wtedy i tylko wtedy, gdy istnieje wektor taki, że
– punkt siodłowy funkcji Lagrange’a.

Zakładając, że funkcja celu
i funkcje są ciągłe i różniczkowalne, to twierdzenie Kuhna-Tuckera można uzupełnić wyrażeniami analitycznymi, które określają warunek konieczny i wystarczający dla punktu
był punktem siodłowym funkcji Lagrange’a, tj. było rozwiązaniem problemu programowania wypukłego. Wyrażenia te mają następującą postać:

Gdzie I są wartościami odpowiednich pochodnych cząstkowych funkcji Lagrange'a obliczonych w punkcie siodłowym.

Twierdzenie Kuhna-Tuckera zajmuje centralne miejsce w teorii programowania nieliniowego. Dotyczy to również tak zwanych problemów programowania kwadratowego, tj. gdzie jest funkcją celu
z ograniczeniami:

W ogólnym przypadku rozwiązywania problemów programowania nieliniowego w celu określenia globalnego ekstremum problemu nie ma skutecznej metody obliczeniowej, jeśli nie wiadomo, że którekolwiek ekstremum lokalne jest również globalne. Zatem w zadaniu programowania wypukłego i kwadratowego zbiór możliwych rozwiązań jest wypukły, to jeśli funkcja celu jest wklęsła, każde maksimum lokalne jest również globalne.

Przykład 7.3. Korzystając z twierdzenia Kuhna-Tuckera znajdujemy
pod ograniczeniami

Rozwiązujemy graficznie (ryc. 7.2) i znajdujemy:
;
;
(więcej szczegółów znajdziesz w rozwiązaniu poniżej). Pokażmy, że istnieje wektor Y 0 0, przy którym warunki Kuhna-Tuckera są spełnione w punkcie optymalnym. Utwórzmy funkcję Lagrange'a:

Rozwiązanie
z układu dowiadujemy się:
. Z drugiego równania
podstaw do pierwszego równania układu. Rozróżnij według :
. W wyrażeniach I zastąpić wartości
I
. Mamy wartości pochodnych cząstkowych większe od zera i zgodnie z warunkiem muszą one być zatem równe zeru =0 I =0. Z drugiej strony, może przyjmować wartości niezerowe, ponieważ
stąd
; Wszystko
te. spełnione są warunki Kuhna-Tuckera, zatem punkt ten jest punktem ekstremalnym.

Ryc.7.2. Graficzne rozwiązanie problemu nieliniowego

przykład programowania 7.3

Warunek konieczny optymalności dla problemu programowania nieliniowego można sformułować w następujący sposób. Pozwalać
– optymalne rozwiązanie problemy (7.4)–(7.6) i funkcje
,
,
różniczkowalne w tym momencie. Jeśli
jest nieosobliwym punktem dopuszczalnego zbioru problemów (7.4)–(7.6), to jest punktem Kuhna-Tuckera tego problemu.

Zatem jeśli zbiór dopuszczalny
problem (7.4)-(7.6) nie ma punktów osobliwych oraz funkcje F(M),G I (M), (
) różniczkowalna we wszystkich punktach
, to optymalnego rozwiązania tego problemu należy szukać wśród punktów Kuhna-Tuckera.

Jak wiadomo z analizy matematycznej, specjalny punkt zbiory dopuszczalnych rozwiązań układu równań liniowych i nierówności o postaci

tj. zbiory wykonalnych rozwiązań

jeśli w tym momencie
gradienty tych funkcji są liniowo zależne
, które w nim zamieniają się w . Na przykład,
– punkt osobliwy zbioru

Naprawdę,

Jest to zatem układ liniowo zależny.

Funkcja gradientu
jest wektorem, którego współrzędne są odpowiednio równe wartościom pochodnych cząstkowych funkcji
w tym punkcie M 0. Wektor ten pokazuje kierunek najszybszego wzrostu funkcji.

Niezbędny warunek optymalności jest mało przydatny do rozwiązywania większości problemów programowania nieliniowego, ponieważ Tylko w rzadkich przypadkach możliwe jest znalezienie wszystkich punktów Kuhna-Tuckera problemu programowania nieliniowego.

Warunek wystarczający optymalności dla problemu programowania nieliniowego: if
jest zatem punktem siodłowym funkcji Lagrange'a dla problemu (7.4)–(7.6).
jest optymalnym rozwiązaniem tego problemu.

Warunek ten nie jest konieczny w ogólnym przypadku: funkcja Lagrange'a nie może mieć jednocześnie punktów siodłowych oryginalny problem programowanie nieliniowe ma rozwiązanie optymalne.

Znane są różne metody, które pozwalają w przybliżeniu znaleźć optymalne rozwiązanie problemu programowania nieliniowego. Jednak metody te zapewniają dość dobre przybliżenie tylko dla problemu programowania wypukłego, gdzie każde ekstremum lokalne jest również globalne. Ogólnie rzecz biorąc, pod gradient metody rozumieją metody, w których ruch do punktu optymalnego funkcji pokrywa się z kierunkiem gradientu tej funkcji, tj. zaczynając od jakiegoś punktu
przeprowadza się sekwencyjne przejście do innych punktów, aż do znalezienia akceptowalnego rozwiązania pierwotnego problemu. W tym przypadku metody gradientowe można podzielić na 2 grupy.

DO Pierwszy Do tej grupy zaliczają się metody, w których badane punkty nie wykraczają poza zakres możliwych rozwiązań problemu. Najbardziej popularną z tych metod jest metoda Frank-Wilk (Wilk). Do takich metod zalicza się metodę rzutowane gradienty Rosena, metoda aktualne wskazówki Zeutendijk.

Współ. drugi Do tej grupy zaliczają się metody, w których badane punkty mogą, ale nie muszą, należeć do obszaru możliwych rozwiązań. Jednakże w wyniku realizacji procesu iteracyjnego zostaje znaleziony punkt w obszarze rozwiązań dopuszczalnych, który wyznacza rozwiązanie akceptowalne.

Spośród tych metod najczęściej stosowaną metodą jest funkcje kary lub metoda Arrow-Hurwitz.

Przy poszukiwaniu rozwiązań problemów metodami gradientowymi, w tym wspomnianymi powyżej, proces iteracyjny prowadzi się aż do uzyskania gradientu funkcji
w następnym punkcie
nie stanie się równa zero lub do
, Gdzie – dość mała liczba dodatnia charakteryzująca dokładność otrzymanego rozwiązania.

Rozwiązywanie złożonych problemów związanych z programowaniem nieliniowym przy użyciu metod gradientowych wymaga dużej liczby obliczeń i zaleca się jedynie przy użyciu komputera.

Na przykładzie pokażemy ogólne znaczenie metod gradientowych w rozwiązywaniu problemów programowania nieliniowego.

Niech będzie funkcja dwóch zmiennych
. Niech będą początkowe wartości zmiennych
i wartość funkcji
. Jeśli
nie jest ekstremum, wówczas wyznacza się takie nowe wartości zmiennych
I
tak aby następna wartość funkcji
okazała się bliższa ideału niż poprzednia.

Jak określa się wielkość przyrostów? I ? Aby to zrobić, w punktach I Kierunek zmiany funkcji w kierunku ekstremum wyznacza się za pomocą gradientu. Im większa wartość pochodnej cząstkowej, tym szybciej funkcja zmierza w stronę ekstremum. Dlatego podwyżki I dobiera się proporcjonalnie do wartości pochodnych cząstkowych I w punktach
I
. Zatem,
I
, Gdzie – wartość zwana krokiem, która określa skalę zmiany I .

Przykład 7.4.

Niech będzie konieczna maksymalizacja funkcji

(maksymalnie w punkcie (3;2))

W punkcie
,
Na
mamy

;
,

Zróbmy jeszcze jedną iterację. W punkcie
,
Na
mamy

;
,

Ryc.7.3. Interpretacja geometryczna dwóch kroków

metoda gradientowa na przykład 7.4

Na ryc. 7.3 pokazuje ruch wzdłuż nachylenia, który został przeprowadzony w w tym przykładzie. Postawa wskazuje kierunek zmiany funkcji w kierunku maksimum. Jeśli przyjmiemy gradient ze znakiem minus, będziemy przesuwać się w stronę minimum.

Specyficznym problemem metod gradientowych jest wybór wielkości kroku T. Jeśli będziemy stawiać małe kroki, optymalności będziemy szukać bardzo długo. Jeżeli wybierzemy jego wartość zbyt dużą, wówczas optymalne może zostać „przekroczone”. Pośredni problem wyboru optymalnej wielkości stopnia rozwiązuje się za pomocą odpowiednich metod. Jeśli krok T jest określony w przybliżeniu, wówczas z reguły nie mieszczą się one w optymalnym, ale w jego strefie. Metody gradientowe pozwalają na wyznaczenie optimów lokalnych. Szukając optymalnego globalnego za pomocą gradientu, często pojawia się wątpliwość, czy znalezione optymalne jest globalne. Jest to wada tej metody przy rozwiązywaniu problemów programowania niewypukłego.

Pytania autotestowe

Sformułowanie problemu programowania nieliniowego.

Proces znajdowania rozwiązania problemu programowania nieliniowego z wykorzystaniem jego interpretacji geometrycznej.

Algorytm metody Lagrange'a do rozwiązywania problemu programowania nieliniowego.

Zastosowanie metody Lagrange'a do rozwiązywania problemu programowania nieliniowego w przypadku, gdy warunki połączenia są nierównościami.

Definicje i twierdzenia pomocnicze niezbędne do rozważenia centralnego twierdzenia programowania nieliniowego - twierdzenia Kuhna-Tuckera.

Twierdzenie Kuhna-Tuckera.

Warunek optymalności konieczny i wystarczający dla problemu programowania nieliniowego.

Ogólne znaczenie metod gradientowych dla przybliżonego rozwiązywania problemów programowania nieliniowego.

Grupy metod gradientowych przybliżonego rozwiązywania problemów programowania nieliniowego.

W poprzedniej sekcji skonstruowano warunki Kuhna-Tucker do zadań optymalizacja warunkowa. Stosując metodę mnożnika Lagrange'a uzyskano intuicyjny pogląd, że warunki Kuhna-Tankera są ściśle powiązane z niezbędnymi warunkami optymalności. W ta sekcja Rozważane jest rygorystyczne sformułowanie warunków koniecznych i wystarczających dla optymalności rozwiązania problemu programowania nieliniowego.

Twierdzenie 1. Konieczność warunków Kuhna-Tuckera

Rozważmy problem programowania nieliniowego (0) - (2). Niech będą funkcjami różniczkowalnymi, a x* będzie dopuszczalnym rozwiązaniem tego problemu. Połóżmy to. Co więcej, niech będą liniowo niezależne. Jeśli x* jest optymalnym rozwiązaniem problemu programowania nieliniowego, to istnieje para wektorów, która jest rozwiązaniem problemu Kuhna-Tuckera (3) - (7).

Warunek, że muszą one być liniowo niezależne, jest znany jako warunek liniowej niezależności i jest zasadniczo pewnego rodzaju warunkiem regularności ważny obszar, co prawie zawsze jest spełnione w przypadku problemów optymalizacyjnych napotykanych w praktyce. Generalnie jednak sprawdzenie spełnienia warunku liniowej niezależności jest bardzo trudne, gdyż wymagane jest wcześniejsze poznanie optymalnego rozwiązania problemu. Jednocześnie warunek liniowej niezależności jest zawsze spełniony w przypadku problemów programowania nieliniowego, które mają następujące właściwości.

1. Wszelkie ograniczenia w postaci równości i nierówności zawierają funkcje liniowe.
2. Wszystkie ograniczenia nierówności zawierają funkcje wklęsłe, wszystkie ograniczenia równości zawierają funkcje liniowe, istnieje też, według co najmniej, jeden dopuszczalny punkt x, który znajduje się we wnętrzu obszaru określonego przez ograniczenia nierówności. Innymi słowy, istnieje punkt x taki, że

Jeżeli warunek liniowej niezależności w optymalnym punkcie nie jest spełniony, wówczas problem Kuhna-Tuckera może nie mieć rozwiązania.

Zminimalizować

pod ograniczeniami

Na ryc. Rysunek 1 przedstawia obszar dopuszczalnych rozwiązań sformułowanego powyżej problemu nieliniowego. Oczywiste jest, że istnieje optymalne rozwiązanie tego problemu. Pokażmy, że w optymalnym punkcie warunek liniowej niezależności nie jest spełniony.

Ryż.

Łatwo zauważyć, że wektory są liniowo zależne, tj. warunek liniowej niezależności w punkcie nie jest spełniony.

Zapiszmy warunki Kuhna-Tuckera i sprawdźmy, czy są spełnione w punkcie (1, 0). Warunki (3), (6) i (7) przyjmują następującą postać;

W, z równania (11) wynika, że o ile równanie (14) daje, Zatem punktem optymalnym nie jest punkt Kuhna-Tuckera.

Należy zauważyć, że naruszenie warunku liniowej niezależności nie musi oznaczać, że punkt Kuhna-Tuckera nie istnieje. Aby to potwierdzić, zamieńmy funkcję celu z tego przykładu na funkcję. W tym przypadku optymalne jest nadal osiągane w punkcie (1,0), w którym warunek liniowej niezależności nie jest spełniony. Warunki Kuhna-Tuckera (12) - (16) pozostają niezmienione, a równanie (11) przyjmuje postać

Łatwo sprawdzić, że punkt jest punktem Kuhna-Tuckera, tj. spełnia warunki Kuhna-Tuckera.

Twierdzenie o konieczności warunków Kuhna-Tuckera pozwala nam zidentyfikować punkty nieoptymalne. Innymi słowy, Twierdzenie 1 można wykorzystać do udowodnienia, że dany punkt wykonalny spełniający warunek liniowej niezależności nie jest optymalny, jeśli nie spełnia warunków Kuhna-Tuckera. Z drugiej strony, jeśli w tym momencie spełnione są warunki Kuhna-Tuckera, to nie ma gwarancji, że znaleziono optymalne rozwiązanie problemu nieliniowego. Jako przykład rozważmy następujący problem programowania nieliniowego.

Poniższe twierdzenie ustala warunki, w których punkt Kuhna-Tuckera automatycznie odpowiada optymalnemu rozwiązaniu problemu programowania nieliniowego.

Twierdzenie 2. Wystarczalność warunków Kuhna-Tuckera

Rozważmy problem programowania nieliniowego (0) - (2). Niech funkcja celu będzie wypukła, wszystkie ograniczenia nierówności zawierają funkcje wklęsłe, a ograniczenia równości zawierają funkcje liniowe. Wtedy jeśli istnieje rozwiązanie spełniające warunki Kuhna-Tuckera (3) - (7), to x* jest optymalnym rozwiązaniem problemu programowania nieliniowego.

Jeżeli spełnione są warunki Twierdzenia 2, to znalezienie punktu Kuhna-Tuckera zapewnia optymalne rozwiązanie problemu programowania nieliniowego.

Twierdzenie 2 można również zastosować do udowodnienia optymalności ta decyzja problemy programowania nieliniowego. Aby to zilustrować, rozważmy ponownie przykład:

Zminimalizować

pod ograniczeniami

Korzystając z Twierdzenia 2 udowadniamy, że rozwiązanie jest optymalne. Mamy

Ponieważ macierz jest dodatnio półokreślona dla wszystkich x, funkcja okazuje się wypukła. Pierwsze ograniczenie nierówności zawiera funkcja liniowa, który jest jednocześnie wypukły i wklęsły. Za to

aby pokazać, że funkcja jest wklęsła, obliczamy

Ponieważ macierz jest ujemnie określona, funkcja jest wklęsła. Funkcja jest zawarta w więzach liniowych w równaniu równości. W konsekwencji wszystkie warunki Twierdzenia 2 są spełnione; jeśli pokażemy, że jest to punkt Kuhna-Tuckera, rzeczywiście ustalimy optymalność rozwiązania. Warunki Kuhna-Tuckera na przykład 2 mają postać

Punkt spełnia ograniczenia (24) - (26) i dlatego jest dopuszczalny. Równania (22) i (23) przyjmują następującą postać:

Ujmując to, otrzymujemy i. Zatem rozwiązanie x*=(1, 5) spełnia warunki Kuhna-Tuckera. Ponieważ warunki Twierdzenia 2 są spełnione, wówczas optymalne rozwiązanie problemu z Przykładu 3. Należy zauważyć, że istnieją również inne wartości i które spełniają układ (22) - (29).

Notatki

1. Dla problemów napotykanych w praktyce warunek liniowej niezależności jest zwykle spełniony. Jeżeli wszystkie funkcje w zadaniu są różniczkowalne, wówczas należy rozważyć punkt Kuhna-Tuckera możliwy punkt optymalny. Zatem wiele metod programowania nieliniowego zbiega się do punktu Kuhna-Tuckera. (W tym miejscu wypada dokonać analogii do przypadku bezwarunkowa optymalizacja, gdy odpowiednie algorytmy pozwalają wyznaczyć punkt stacjonarny.)
2. Jeżeli spełnione są warunki Twierdzenia 2, punkt Kuhna-Tuckera okazuje się jednocześnie punktem minimum globalnego. Niestety sprawdzenie wystarczających warunków jest bardzo trudne, a w dodatku stosowane problemy często nie mają wymaganych właściwości. Należy zauważyć, że obecność co najmniej jednego ograniczenia nieliniowego w postaci równości prowadzi do naruszenia założeń Twierdzenia 2.
3. Warunki wystarczające ustalone Twierdzeniem 2 można uogólnić na przypadek problemów z funkcjami niewypukłymi zawartymi w ograniczeniach w postaci nierówności, niewypukłych funkcji celu i nieliniowych więzów równościowych. W tym przypadku stosuje się takie uogólnienia funkcji wypukłych, jak funkcje quasi-wypukłe i pseudowypukłe.

Twierdzenia Kuhna-Tuckera to ogólna nazwa stwierdzeń reprezentujących uogólnienia

zastosowanie twierdzenia Lagrange’a do przypadku problemów optymalizacyjnych z ograniczeniami w postaci nierówności, tj. problemów

następujący typ:

gj(x) > 0, j = 1, .

M, (?)

x = (x1, . . , xn) 2 X.

Tutaj f: X 7! R - (zgodnie z przyjętą terminologią) funkcja celu, gr: X 7! R,

r = 1, . . . ,m, są funkcjami ograniczeń, X _ Rn jest zbiorem otwartym.

Twierdzenie 196 (twierdzenie Johna w odniesieniu do punktu siodłowego):

Niech funkcje f( ), g1( ), . . . , gn( ) są wklęsłe, a?x jest rozwiązaniem problemu (?), takim, że?x 2 intX.

Następnie istnieją mnożniki Lagrange'a _j >

X jest rozwiązaniem problemu

Stwierdzenia te prezentujemy dla przypadku, gdy funkcje f, gr są różniczkowalne (twierdzenia Ku-

on-Tucker w formie różniczkowej).

Przypomnijmy, że funkcja

L(x,_) = _0f(x) +

nazywa się funkcją Lagrange'a (Lagrangianu) tego problemu, a współczynniki _j są mnożnikami

Lagrange'a.

Poniższe stwierdzenie jest aktualne.

Twierdzenie 197 (Twierdzenie Johna o funkcjach różniczkowalnych):

Niech?x będzie rozwiązaniem problemu (?), takim, że?x 2 intX i funkcje f( ), g1( ), . . . , gn( ) różnica

są wymierne w punkcie?x.

Następnie istnieją mnożniki Lagrange'a _j > 0, j = 0, . . . ,m, nie wszystkie równy zeru, takie że

spełnione są następujące zależności (warunki Kuhna-Tuckera):

0, ja = 1, . . . , N

J = 0 (warunki komplementarności

brak sztywności).

Należy zauważyć, że warunki luzu dopełniającego można zapisać w postaci

gj(?x)_j = 0, j = 1, . . . , M.

Z tych warunków wynika, że jeśli mnożnik Lagrange'a jest dodatni (_j > 0), to odpowiada mu

ograniczenie rozwiązania problemu (przy x = ?x) jest spełnione jako równość (tj. gj(?x) = 0). Inni

innymi słowy, to ograniczenie jest aktywne. Natomiast w przypadku, gdy gj(?x) > 0, wówczas odpowiada

mnożnik Lagrange'a _j jest równy zero.

Jeśli w zadaniu (?) niektóre ograniczenia mają postać ograniczeń na nieujemność jakiegoś xi,

to dla nich nie można wprowadzić mnożników Lagrange’a wpisując osobno następujące ograniczenia:

gj(x) > 0, j = 1, . . . , M, (??)

xi > 0, i 2 P _ (1, .. , n). W punkcie wewnętrznym (w tym sensie, że1 × 2 intX) są wówczas warunki pierwszego rzędu dla i 2 P

będzie wyglądać tak:

Dla i /2 P tutaj, podobnie jak w przypadku przedstawienia problemu w postaci (?), pochodna funkcji Lagrange'a

dla tej zmiennej będzie wyglądać jak @L(?x,_)

Ponadto spełnione są również warunki uzupełniającej niesztywności

Z drugiego z tych warunków wynika, że for xi > 0 (i 2 P)

Natomiast jeśli @L(?x,_)/@xi Kolejna modyfikacja twierdzenia wiąże się z występowaniem w zadaniu ograniczeń w postaci równości. Przeznaczenie

zdefiniujmy zbiór odpowiednich indeksów poprzez E. Problem ma następującą postać:

gj(x) > 0, j 2 (1, . . . , m)\E,

gj(x) = 0, j 2 E, (???)

xi > 0, i 2 P _ (1, .. , n).

Jednocześnie twierdzenie Johna usuwa warunek, że wszystkie mnożniki Lagrange'a są nieujemne -

Mnożniki Lagrange'a _j dla j 2 E mogą mieć dowolny znak.

Twierdzenie Johna nie gwarantuje, że mnożnik Lagrange'a funkcji celu _0 jest różny od zera.

Jeśli jednak _0 = 0, to warunki Kuhna-Tuckera charakteryzują nie rozwiązanie rozważanego problemu, ale

Struktura zbioru ograniczeń w punkcie?x i twierdzenie nie ma bezpośredniego związku z interesem

nasze obecne zadanie maksymalizacji funkcji f( ), ponieważ gradient samej funkcji f( ) znika. z

Warunki Kuhna-Tuckera.

Dlatego ważne jest scharakteryzowanie warunków gwarantujących, że _0 > 0.

Takie warunki nazywane są warunkami regularności.

W przypadku, gdy rozpatrywany problem jest wypukły, jednym z warunków regularności jest

tzw. warunek Slatera ma postać:

W przypadku, gdy funkcja celu i ograniczenia problemu są różniczkowalne, najprościej

Warunek regularności sformułowany jest w postaci gradientów funkcji więzów i ma postać:

gradienty aktywnych więzów w punkcie x są liniowo niezależne. (Wśród rozważanych ograniczeń znajdują się

należy również uwzględnić ograniczenia dotyczące nienegatywności.)

Oznaczmy przez A zbiór wskaźników tych więzów, które działają w optymalnym punkcie?x

(uwzględniając wskaźniki wszystkich ograniczeń w postaci równości), tj.

gj(?x) = 0, j 2 A.

Następnie, jeśli gradienty więzów są wektorami

są liniowo niezależne2, wówczas _0 > 0. Warunek ten nazywany jest warunkiem regularności Kuhna-Tuckera.

Należy zauważyć, że jeśli _0 > 0, to bez utraty ogólności możemy założyć, że _0 = 1, co zwykle się dzieje.

Odpowiednie twierdzenie nazywa się (bezpośrednim) twierdzeniem Kuhna-Tuckera. Twierdzenie 198 (Bezpośrednie twierdzenie Kuhna-Tuckera, warunek konieczny optymalności):

Niech funkcje f( ), g1( ), . . . , gn( ) są różniczkowalne, a?x jest rozwiązaniem problemu (?), tak że

X 2 intX i warunek regularności Kuhna-Tuckera jest spełniony.

Następnie istnieją mnożniki Lagrange'a _j > 0, j = 1, . . . ,m, tak że gdy _0 = 1 są spełnione

następujące współczynniki:

0, ja = 1, . . . , N

Łatwo jest przeformułować to twierdzenie na problemy (???) i (???). Tutaj wymagane są te same możliwości.

modyfikacja warunków Kuhna-Tuckera, jak w twierdzeniu Johna.

0, ja = 1, . . . , N

można przepisać jako:

Zależność ta pokazuje, że w optymalnym punkcie gradient funkcji celu jest funkcją liniową

kombinacja antygradientów ograniczeń, a wszystkie współczynniki tej kombinacji liniowej są nieujemne

cenny. Ryż. Rysunek 17.1 ilustruje tę właściwość. Intuicyjnie, idea stojąca za tą właściwością jest taka

gdyby jakikolwiek współczynnik kombinacji liniowej był ujemny, byłoby to możliwe

zwiększyć wartość funkcji celu, przesuwając się wzdłuż tego ograniczenia. Jedna z odwrotnych wersji twierdzenia Kuhna-Tuckera stwierdza, że gdy funkcje są wklęsłe

f( ), (gk( )) spełnienie tych warunków w rozwiązaniu dopuszczalnym?x (czyli punkcie spełniającym ograniczenie

wartości) dla niektórych mnożników Lagrange’a spełniających wymagania twierdzenia bezpośredniego,

gwarantuje, że?x jest rozwiązaniem problemu.

Twierdzenie 199 (Odwrotne twierdzenie Kuhna-Tuckera /warunek wystarczający na optymalność/):

Niech f( ) będzie różniczkowalną funkcją wklęsłą, g1( ), . . . , gn( ) - różniczkowalna

funkcje quasi-wklęsłe, zbiór X jest wypukły, a punkt ?x jest dopuszczalny w zadaniu (?), oraz?x 2

Niech dodatkowo istnieją mnożniki Lagrange'a _j > 0, j = 1, . . . ,m, tak, że kiedy

0 = 1 spełnione są następujące zależności:

0, ja = 1, . . . , N

Zatem?x jest rozwiązaniem problemu (?).

Twierdzenie można w oczywisty sposób przeformułować na problemy (???) i (???). Za zadanie (???)

więzy w postaci równości mogą mieć jedynie charakter liniowy (wynika to z faktu, że więzy w postaci

równości, gj(x) = 0, należy przedstawić za pomocą dwóch ograniczeń w postaci nierówności, gj(x) > 0

and?gj(x) > 0, z których każde jest dane funkcją quasi-wklęsłą; może się to zdarzyć tylko wtedy, gdy

ograniczenie jest liniowe).

W innej wersji warunku wystarczającej optymalności założenie, że celem jest wklęsłość

funkcję zastępuje się założeniem quasi-wklęsłości z dodaniem warunku rf(?x) 6= 0.