Rozdział II. Programowanie wypukłe. Programowanie wypukłe Programowanie wypukłe warunki konieczne i wystarczające

Jeśli w zadaniu z zakresu programowania matematycznego musisz znaleźć ekstremum funkcji, na przykład:

na zestawie wykonalnych rozwiązań podanych przez ograniczenia

1) funkcja celu jest różniczkowalna i wklęsła, tj. warunek jest do tego spełniony:

Dla każdego,

2) i po lewej stronie wszystkich ograniczeń - funkcje różniczkowalne i wypukłe, tj. dla nich spełnione są następujące warunki:

Dla każdego,

Wtedy problem (4.7) - (4.8) nazywamy problemem programowanie wypukłe.

Każda funkcja liniowa spełnia jednocześnie warunki wypukłości i wklęsłości; te. można go uznać za wypukły i wklęsły. To pozwala nam rozpatrywać problemy liniowe jako szczególny przypadek wypukłych problemów programowania.

Jeśli dla problemów programowania matematycznego w ogólnym przypadku nadal nie ma spójnej teorii istnienia i stabilności rozwiązania, to dla problemów programowania wypukłego taka teoria istnieje.

Przedstawmy trzy definicje:

1). Funkcja Lagrange'a wypukłego problemu programowania (4.7) - (4.8) jest funkcją:

,

, (4.9)

2). Mówi się, że problem wypukłego programowania (4.7) - (4.8) spełnia warunek prawidłowościjeśli istnieje przynajmniej jeden punkt wewnętrzny zbioru wykonalnych rozwiązań określonych przez ścisłe nierówności uzyskane z (4.8) (tj. ).

3). Chodzi o to siodło punkt funkcji, jeśli dla wszystkich wykonano:

Jeśli funkcja celu (usuń)

W teorii programowania nieliniowego centralne miejsce zajmuje twierdzenie Kuhna-Tuckera, które uogólnia klasyczną metodę mnożników Lagrange'a na przypadek, gdy ograniczenia problemu nieliniowego wraz z ograniczeniami w postaci równości zawierają również ograniczenia w postaci nierówności.

Twierdzenie Kuhna-Tuckera. Jeśli wypukły problem programowania (4.7) - (4.8) spełnia warunek regularności, to punkt jest optymalnym rozwiązaniem tego problemu wtedy i tylko wtedy, gdy istnieje punkt o współrzędnych nieujemnych, który jest punktem siodłowym funkcji Lagrange'a tego problemu.

Warunki Karush - Kuna - Tucker w postaci różnicowej:

Jeżeli funkcja Lagrange'a jest wypukła w stosunku do, wklęsła względem i różniczkowalna w sposób ciągły względem wszystkich, a następnie aby para była punktem siodłowym funkcji Lagrange'a, konieczne i wystarczające jest spełnienie następujących warunków:

,

,

,

PrzykładTwierdzenie Kuhna-Tuckera uzasadnia redukcję zagadnienia programowania wypukłego do problemu znalezienia punktu siodłowego funkcji Lagrange'a. Aby taka redukcja miała praktyczne znaczenie, konieczne jest, aby wynikający z niej problem był nieco prostszy niż pierwotny. Nie zawsze tak się dzieje, dlatego opracowano szereg bezpośrednich metod rozwiązywania problemu nieliniowego (4.5), (4.6). Rozważmy niektóre z nich.

PROGRAMOWANIE CONVEX, sekcja programowania matematycznego, w której problem maksymalizacji wklęsłej funkcji celu f (x) argumentu wektorowego x \u003d (x 1, ..., x n) spełniającego ograniczenia gi (x) ≥ 0, x Є X, i \u003d 1, ..., m, gdzie gi to funkcje wklęsłe, X to zbiór wypukły. Punkt x, który spełnia te ograniczenia, nazywany jest dopuszczalnym. Głównym rezultatem teorii programowania wypukłego jest twierdzenie o punkcie siodłowym: aby dopuszczalny punkt x * wypukłego problemu programowania był optymalny, konieczne jest (w dość szerokich warunkach) i wystarczające istnienie wektora y * \u003d (y * 1, ..., ym *) ze składnikami nieujemnymi y * takimi, że punkt (x *, y *) jest punktem siodłowym dla funkcji Lagrange'a

wypukłe problemy programistyczne, czyli dla dowolnych x Є X i y z nieujemnymi składowymi, nierówności

Szereg metod programowania wypukłego opiera się na twierdzeniu o punkcie siodła, w którym albo funkcja φ (y 1, ..., y m) \u003d max x Є XL (x, y) jest zminimalizowana dla y i ≥ 0, i \u003d 1, .. ., m lub punkt siodłowy znajduje się bezpośrednio, a niektóre z jego modyfikacji są czasami używane zamiast funkcji Lagrange'a. Inne podejście do rozwiązania problemu programowania wypukłego wiąże się z poszukiwaniem możliwych kierunków ruchu punktu wykonalnego x, które nie są wyprowadzone ze zbioru punktów wykonalnych oraz podczas poruszania się, wzdłuż którego rośnie funkcja celu. To podejście jest implementowane przy użyciu sekwencji iteracji. W każdej iteracji obliczany jest możliwy kierunek wychodzący z następnego punktu, po czym następuje przesunięcie w tym kierunku o pewną odległość do następnego punktu. Istnieją metody rozwiązywania problemów programowania wypukłego, specjalnie przystosowane do przypadku, gdy funkcja celu jest nieliniowa, a ograniczenia są liniowe. Zwykle metody programowania wypukłego wymagają nieskończonej liczby iteracji, aby dokładnie określić optymalny punkt. Wyjątkami są problemy programowania kwadratowego (funkcja celu jest sumą wklęsłych funkcji kwadratowych i liniowych, ograniczenia są liniowe) oraz programowanie liniowe (funkcja celu i ograniczenia są liniowe), do których stosuje się głównie metody skończone. Wiele metod obliczeniowych programowania wypukłego jest realizowanych w postaci programów komputerowych; istnieją również pakiety oprogramowania obejmujące programowanie liniowe i problemy z programowaniem wypukłym. Zobacz także Badania operacyjne.

Lit.: Golshtein E.G. Programowanie wypukłe. Elementy teorii. M., 1970; Programowanie nieliniowe Zangwill W.I. Jedno podejście. M., 1973.

Niech układ nierówności formy

(4.3) i funkcję

Z \u003d f (x 1, x 2, ..., x n), (4.4)

ponadto wszystkie funkcje są wypukłe na pewnym wypukłym zbiorze M, a funkcja Z jest albo wypukła na zbiorze M, albo wklęsła.

Problem programowania wypukłego polega na znalezieniu rozwiązania dla układu więzów (4.3), w którym funkcja celu Z osiągnie swoją wartość minimalną lub funkcja wklęsła Z osiągnie wartość maksymalną. (Warunki nieujemności zmiennych można uznać za uwzględnione w systemie (4.3)).

Ze względu na właściwość 3 0, każdy problem programowania liniowego jest szczególnym przypadkiem problemu wypukłego. W ogólnym przypadku problemy z programowaniem wypukłym są nieliniowymi problemami programistycznymi. Przydzielanie wypukłych problemów programistycznych do specjalnej klasy jest wyjaśnione przez ekstremalne własności funkcji wypukłych: każde lokalne minimum funkcji wypukłej (lokalne maksimum funkcji wklęsłej) jest jednocześnie globalne; ponadto, biorąc pod uwagę właściwość 2 0, funkcja wypukła (wklęsła) zdefiniowana na zamkniętym zbiorze ograniczonym osiąga globalne maksimum i globalne minimum w tym zbiorze. Stąd wynika, że jeśli funkcja celu Z jest ściśle wypukła (ściśle wklęsła) i jeśli domena rozwiązania systemu ograniczeń nie jest pusta i ograniczona, to wypukły problem programowania zawsze ma unikalne rozwiązanie.

Wywoływana jest funkcja F (X) \u003d F (x 1, x 2, ..., x n) rozdzielny, jeśli można ją przedstawić jako sumę funkcji, z których każda zależy tylko od jednej zmiennej, tj. Jeśli

(możliwe, że F i (x i) \u003d 0 dla niektórych i).

Niech system ograniczeń (4.3) i funkcja celu (4.4) zostaną podane w wypukłym problemie programowania, a funkcja celu Z i wszystkie ograniczenia są rozłączne. Wtedy problem wygląda następująco:

Znajdź minimum funkcji wypukłej (maksimum - wklęsłej)

z ograniczeniami

Idea odcinkowej metody przybliżenia liniowego polega na tym, że wszystkie fi i wszystkie są zastępowane liniami przerywanymi składającymi się z odcinków prostych. W tym przypadku pierwotny problem z programowaniem wypukłym zostaje zastąpiony nowym, przybliżonym problemem, który jest problemem programowania liniowego. Ten problem jest zwykle rozwiązywany metodą simplex, a jego rozwiązanie jest przybliżonym rozwiązaniem pierwotnego problemu programowania wypukłego.

Rysunek 12. Rozwiązanie problemu wypukłego programowania przez odcinkową aproksymację liniową

Aby skonstruować przybliżony problem, rozważ fragmentaryczne liniowe przybliżenie funkcji jednej zmiennej h (x) podanej w przedziale. Dzielimy ten segment na r części przez punkty x 0

Równanie odcinka łamanej między punktami (x k; h k) i (x k + 1; h k + 1) ma postać (równanie prostej wzdłuż dwóch punktów). Jeśli każda z relacji w tej równości jest oznaczona przez, otrzymujemy:

Zauważ, że dla każdego istnieje unikalna wartość spełniająca warunki (4.7). Oznaczanie można przepisać (4.7) w postaci:

[Równania (4.8) nazywamy równaniami parametrycznymi segmentu.

Jeśli h (x) \u003d 0, to drugie z tych równań zamienia się w tożsamość 0 \u003d 0, a pierwsze przyjmuje postać (4.1) - równanie odcinka leżącego na osi odciętych].

Zatem dla dowolnego równania linii przerywanej można zapisać w postaci:

i tylko dwie wartości są zawsze niezerowe (jeśli x jest wewnętrznym punktem k-tego segmentu przegrody) lub jedną (jeśli x pokrywa się z końcem segmentu).

Wracając do wypukłego problemu programowania z funkcjami rozłącznymi, zauważamy, że przede wszystkim (w zależności od układu ograniczeń) należy wyznaczyć przedział zmienności każdej zmiennej x j. Następnie każdy z tego przedziału jest dzielony na części za pomocą punktów x jk i za pomocą wzorów (4.9) wyznacza się odcinkowo liniowe przybliżenie funkcji f j i konstruuje się. Następnie dla pierwotnego problemu (4.6) możemy zapisać przybliżony problem:

Znajdź maksimum funkcji

podlega ograniczeniom (4.10)

Ponieważ przybliżony problem (4.10) jest problemem programowania liniowego, który zwykle rozwiązuje się metodą simplex, warunki nieujemności zmiennych są zapisywane oddzielnie od pozostałych ograniczeń.

Różnica między otrzymanym problemem (4.10) a zwykłym problemem programowania liniowego polega na tym, że dla każdego x j są nie więcej niż dwie sąsiednie niezerowe wartości, dlatego nie można przyjąć za główne zmienne dwóch o tym samym j i nieprzylegających k. Należy również zauważyć, że oczywiście nie jest konieczne przeprowadzanie odcinkowego przybliżenia liniowego dla warunków nieujemności składników zmiennych f j (x j) i (jeśli takie istnieją).

W tym rozdziale dokonaliśmy przeglądu zaledwie kilku technik optymalizacji stosowanych przez menedżerów do podejmowania skutecznych decyzji w przedsiębiorstwach. Jednak opisane techniki pozwalają zrozumieć podstawową zasadę stosowania aparatu matematycznego w ekonomii, która pozwala na wybór spośród wielu alternatywnych opcji optymalnych dla danego przypadku lub sytuacji.

Funkcja nazywa się wypukły

Funkcja nazywa się wklęsły na wypukłym zbiorze, jeśli dla jakichkolwiek punktów i dowolna liczba zachodzi następująca nierówność:

Czasami funkcja wypukła jest nazywana wypukłą w dół w przeciwieństwie do funkcji wklęsłej, która jest czasami nazywana wypukłą w górę. Znaczenie tych nazw jasno wynika z geometrycznego obrazu typowej funkcji wypukłej (ryc. 3.3) i wklęsłej (ryc. 3.4).

Figa. 3.3. Funkcja wypukła

Figa. 3.4. Funkcja wklęsła

Podkreślamy, że definicje funkcji wypukłych i wklęsłych mają sens tylko dla zbioru wypukłego X, bo tylko w tym przypadku chodzi koniecznie należy X.

Problem programowania wypukłego jest szczególnym przypadkiem ogólnego problemu programowania matematycznego (3.7), (3.8), gdy funkcja celu i funkcje ograniczeń są wklęsłe na zbiorze wypukłym R.

Ponieważ problem maksymalizacji funkcji jest równoważny problemowi minimalizacji tej funkcji ze znakiem minus, ograniczenie jest równoważne nierówności, a wypukłość wynika z wklęsłości i odwrotnie. Stąd

problem programowania wypukłego nazywany jest również problemem minimalizacji funkcji wypukłej pod ograniczeniami:

, ,

gdzie są funkcje wypukłe; R Jest zestawem wypukłym. To tylko inna forma problemu.

Należy zauważyć, że jeśli wypukły problem programistyczny jest sformułowany jako problem maksimum, to funkcja celu jest z konieczności wklęsła, a jeśli jest sformułowana jako problem minimalny, to jest wypukła. funkcje ograniczeń są wypukłe. To połączenie jest spowodowane obecnością pewnych właściwości w wypukłym problemie programistycznym, które mogą być nieobecne, jeśli takie połączenie zostanie naruszone. W poniższym lemacie przedstawiono dwie główne takie właściwości.

Lemat 1

Zbiór dopuszczalnych planów dla wypukłych problemów programistycznych

jest wypukły. Dowolne lokalne maksimum funkcji wklęsłej włączone X jest globalna.

Jeśli funkcje ograniczeń były wypukłe, to dla zbioru X (3.14) wypukłość już nie występowała. W takim przypadku wypukłość zbioru można udowodnić:

Gdyby funkcja celu była wypukła, to stwierdzenie lematu dotyczące jego maksimów stałoby się niepoprawne, ale podobne stwierdzenie można by udowodnić dla minimów.

Funkcja nazywa się rygorystycznie wypukły na wypukłym zbiorze, jeśli dla jakichkolwiek punktów i dowolną liczbę, którą zachodzi nierówność.

Funkcja nazywa się rygorystycznie wklęsły na wypukłym zbiorze, jeśli dla jakichkolwiek punktów i dowolną liczbę zachodzi następująca nierówność:

Lemat 2

Suma funkcji wypukłych (wklęsłych) jest wypukła (wklęsła). Iloczyn funkcji wypukłej (wklęsłej) i liczby dodatniej jest wypukły (wklęsły). Suma funkcji wypukłych (wklęsłych) i ściśle wypukłych (ściśle wklęsłych) jest ściśle wypukła (ściśle wklęsła).

Twierdzenie 1

Jeśli funkcja jest ściśle wklęsła (ściśle wypukła) na zbiorze wypukłym X, to może mieć tylko jeden maksymalny (minimalny) punkt.

Dowód

Załóżmy, że jest odwrotnie, tj. że są dwie kwestie ,, które są maksymalnymi punktami ściśle wklęsłej funkcji na X... Oznaczając, mamy ... Wtedy jest to prawda:

te. doszło do sprzeczności. Dowód jest podobny dla minimum funkcji ściśle wypukłej.

Funkcja liniowa jest jedynym przykładem funkcji wypukłej i wklęsłej, co oznacza, że \u200b\u200bnie jest ona ściśle wypukła (ściśle wklęsła). Funkcja kwadratowa nie może być wypukły (wklęsły), ale może być ściśle wypukły (ściśle wklęsły); wszystko to jest określone przez macierz re... Elementy macierzy re reprezentują drugą pochodną cząstkową funkcji kwadratowej, tj.

.

Oznaczmy macierz drugiej pochodnej cząstkowej przez.

Lemat 3

Dla funkcji kwadratowej była wypukła (wklęsła) w całej przestrzeni, konieczne i wystarczające jest, aby matryca re została zdefiniowana pozytywnie (negatywnie). Jeśli re pozytywnie (negatywnie) zdefiniowane, tj.

wtedy jest ściśle wypukła (ściśle wklęsła).

Problem maksymalizacji (minimalizacji) funkcji kwadratowej przy ograniczeniach liniowych, gdzie re Jest ujemną (dodatnią) określoną macierzą i D T= rejest nazywany problem programowania kwadratowego .

Z lematu wynika, że \u200b\u200bproblem programowania liniowego rozpatrywany w Rozdziale 2, podobnie jak problem programowania kwadratowego, jest szczególnym przypadkiem problemu wypukłego programowania.

Istnieją funkcje wypukłe w jednej grupie zmiennych i wklęsłe w innej. Takie funkcje stanowią jedną z głównych klas funkcji, dla których z pewnością istnieje punkt siodłowy.

Twierdzenie 2

(O istnieniu punktu siodłowego dla funkcji wklęsło-wypukłej). Zostawiać X i Y są wypukłymi, zamkniętymi, ograniczonymi podzbiorami skończonych wymiarowych przestrzeni euklidesowych, a funkcja jest ciągła w i, wklęsła i wypukła, a następnie ma punkt siodłowy.

Rozważmy funkcję Lagrange'a dla wypukłego problemu programistycznego:

(3.15)

zdefiniowane na produkcie bezpośrednim, gdzie. Dzięki swojej wklęsłości funkcja ta jest wklęsła i liniowa, a zatem wypukła do wewnątrz.

Jednak na podstawie Twierdzenia 1 nie można argumentować, że ma punkt siodłowy, ponieważ zbiór R niekoniecznie jest zamknięty i ograniczony, ale Y oczywiście nieograniczone. Niemniej jednak można się spodziewać, że w pewnych warunkach punkt siodłowy będzie nadal istniał.

Najbardziej znanym twierdzeniem związanym z tym zagadnieniem jest twierdzenie Kuhna-Tuckera, które ustanawia związek między istnieniem rozwiązania problemu wypukłego programowania a punktem siodłowym dla funkcji Lagrange'a, gdy warunki Slatera : wypukły problem programistyczny spełnia warunek Slater, jeśli istnieje taki punkt, w którym warunek jest spełniony: .

Twierdzenie Kuhna-Tuckera

Jeśli wypukły problem programistyczny spełnia warunek Slatera, to warunkiem koniecznym i wystarczającym dla optymalności projektu jest istnienie takiego, że para jest punktem siodłowym funkcji Lagrange'a (3.15).

Poniższy przykład ilustruje stan Slatera.

Przykład 1

Biorąc pod uwagę wypukły problem programistyczny:

Tutaj jest to oczywiste x = 0 ma rozwiązanie problemu, ale funkcja Lagrange'a nie ma punktu siodłowego, ponieważ zewnętrzne ograniczenie w problemie minimaksu nie jest osiągane:

Podział ograniczeń w wypukłym problemie programistycznym na i , jak już wspomniano, jest warunkowe. Dlatego zwykle pod R rozumie się zbiór prostej formy, to jest albo cała przestrzeń E n, lub nieujemną ortantę lub równoległościan. O złożoności wypukłego problemu programowania decyduje system ograniczeń:

.

Ponieważ punktu siodłowego funkcji Lagrange'a poszukuje się na iloczynie zbiorów, gdzie Y jest również zbiorem postaci prostej (ortant nieujemny), wówczas znaczenie twierdzenia Kuhna-Tuckera polega na sprowadzeniu problemu znalezienia ekstremum funkcji ze złożonymi ograniczeniami na zmiennych do problemu znalezienia ekstremum nowej funkcji z prostymi ograniczeniami.

Jeśli zestaw R zbiega się z E n, to warunki ekstremalne, jak wiadomo, mają postać:

Co więcej, te warunki są nie tylko konieczne, aby funkcja osiągnęła maksimum, ale także wystarczające. Jest to ważna właściwość funkcji wklęsłych, aw przypadku wypukłego problemu programowania jest wklęsła.

Twierdzenie 3

Aby stale różniczkowalna funkcja wklęsła miała maksimum w jednym punkcie E nkonieczne i wystarczające jest, aby gradient funkcji w punkcie był równy zeru, tj. ...

Przypomnij sobie, że gradient funkcji to:

.

Zatem, aby znaleźć punkt siodłowy funkcji Lagrange'a na produkcie, a tym samym znaleźć rozwiązanie problemu wypukłego programowania dla R= E n konieczne jest rozwiązanie układu równań (3.16). Ale w tym systemie n równania i niewiadome n+ mponieważ poza tym n-wymiarowy wektor jest nam nieznany i m-wymiarowy wektor mnożników Lagrange'a. Jednak dla punktu siodłowego funkcji Lagrange'a zachodzi bardzo ważna własność:

. (3.17)

Z równania (3.17) wynika, że \u200b\u200bjedno lub drugie jednocześnie. Ta własność jest podobna do drugiego twierdzenia o dualności (rozdz. 2.5) programowania liniowego. Nazywane są ograniczeniami, które są spełnione w pewnym momencie jako równości aktywny .

Zatem tylko te mnożniki Lagrange'a mogą być niezerowe, co odpowiada ograniczeniom aktywnym w punkcie. Biorąc pod uwagę tę właściwość, aby znaleźć rozwiązanie problemu wypukłego programowania, rozważ następującą metodę.

Wykład 11.Programowanie wypukłe

Definicja 1. Z przez programowanie wypukłe nazywany nieliniowym problemem programowania, w którym wszystkie funkcje są wypukłe.

Zatem problem z programowaniem wypukłym jest problemem minimalizacji warunkowej, w którym funkcja celu jest wypukła, a dziedziną wykonalną jest zbiór wypukły utworzony przez układ wypukłych nierówności. Dlatego twierdzenia uzyskane wcześniej w sekcji 6 są ważne dla problemu programowania wypukłego. W tej sekcji konkretyzujemy te ogólne wyniki i wprowadzamy je w formę, która jest wygodniejsza do studiowania i rozwiązywania następującego problemu z programowaniem wypukłym:

(1)

, (2)

. (3)

Będziemy potrzebować kilku konstrukcji pomocniczych w kosmosie
wektory
... Wektor od pierwszego
komponent punktowy będzie oznaczony przez ... Więc,
.

Dla problemu (1) - (3) zdefiniuj zbiór

gdzie
.

Lemat . Dla wypukłego problemu programowania (1) - (3) pęczek wypukły.

Dowód. Wybierz dowolne wektory
tłumu i liczbę
... Następnie są punkty i z takie jak i. Mnożymy te nierówności przez i
odpowiednio i dodaj je. Ponieważ wszystkie funkcje są wypukłe, otrzymujemy

Uzyskane nierówności i implikują wypukłość zbioru .

Twierdzenie 1. (Twierdzenie Kuhna-Tuckera w postaci punktu siodłowego funkcji Lagrange'a wypukłego problemu programowania ) Niech w wypukłym problemie programowania (1) - (3) system (2) spełni warunek Slatera w odniesieniu do było rozwiązaniem problemu (1) - (3), konieczne i wystarczające jest, aby istniał wektor nieujemny takie że
Jest punktem siodła funkcji Lagrange'a.

Dowód. Ponieważ wystarczalność tego warunku została już udowodniona dla dowolnego nieliniowego problemu programowania (patrz Twierdzenie 2.6 Wstępu), pozostaje tylko udowodnić konieczność.

Konieczność. Zostawiać - rozwiązanie problemu (1) - (3). Kładziemy
... To oczywiste
, tak jak
,
i
.

Upewnijmy się, że
... Załóżmy, że jest odwrotnie. Oznacza to, że jest sens
takie że
... W związku z tym, - taki dopuszczalny punkt, w którym wartość funkcji celu jest mniejsza od minimum. Mamy z tym sprzeczność - rozwiązanie problemu wypukłego programowania.

Więc,
... Zgodnie z lematem zestaw wypukły. Stąd wszystkie wymagania Twierdzenia 8.2 są spełnione. Dlatego istnieje wartość różna od zera

wektor
punkt obrotu do mnóstwa :

Sprawdźmy dalej, czy wszystkie współrzędne wektora nie są pozytywne. Załóżmy, że jest odwrotnie. Niech będzie współrzędna
... Naprawmy wektor wszystkie komponenty z wyjątkiem -O. Następnie, biorąc pod uwagę, że produkt
może przyjmować dowolnie duże wartości (ponieważ współrzędne ) uzyskujemy sprzeczność z nierównością (4).

Łatwo to zauważyć dla każdego
wektory
zawarte w wielu ... Następnie z (4) mamy:

Pokażmy to
... Niech tak nie będzie. Następnie
... W związku z tym,
... Według warunku Slatera istnieje wektor
takie że
... w związku z tym
... Wynikająca z tego sprzeczność oznacza, że
.

Oznaczamy
... Pokażmy, że skonstruowany wektor jest wymaganym wektorem mnożników Lagrange'a. To oczywiste
az (5) otrzymujemy

Stąd w
powinien

. (7)

Z drugiej strony, ponieważ
(o ile
) i
otrzymujemy nierówność

... Z tego i (7) wynika, że \u200b\u200bw punkcie
spełniony jest warunek luźności uzupełniającej:

. (8)

Z (6) i (8) mamy

lub, co jest tym samym,

Dalej, niech
... Następnie
... Z tego i (8) otrzymujemy nierówność

Nierówności (9), (10) i to znaczą
Jest punktem siodłowym funkcji Lagrange'a problemu wypukłego

logo programowania. Co było wymagane.

Przed zapoznaniem się z inną wersją twierdzenia Kuhna-Tuckera przedstawiamy następujące twierdzenie, które jest warunkowym kryterium minimum w zakresie stożków wektorów nośnych.

Twierdzenie 2. Zostawiać - wypukłe i zróżnicowane na
funkcja, zestaw
wypukły. Następnie, aby wskazać
było warunkowym minimum funkcji na planie
, jest to konieczne i wystarczające do włączenia

. (11)

Dowód wynika bezpośrednio z Twierdzenia 6.5 i definicji stożka
wektory wspierające w punkcie do mnóstwa
.

Twierdzenie 3. (Twierdzenie Kuhna-Tuckera w postaci różniczkowej dla wypukłego problemu programowania ) Niech wypukły problem programistyczny zostanie podany w postaci (1), (2), gdzie wszystkie funkcje
są ciągle różniczkowalne, system (2) spełnia warunek Slatera. Następnie, aby uzyskać wektor
było rozwiązaniem problemu (1), (2), konieczne i wystarczające jest, aby istniał nieujemny wektor takie, że warunki

, (12)

.

Dowód. Pokażmy, że warunki (12) i (13) są równoważne włączeniu (11). Przejdźmy do sedna
jest taki, że
... Następnie
i
.

Pozwól teraz
... Następnie z Twierdzeń 2 i 10.5 wynika, że \u200b\u200bwarunkiem koniecznym i wystarczającym dla ekstremum jest istnienie takich czynników
,
dla którego
... Kładziemy
dla wszystkich
i otrzymujemy z ostatnich warunków równości (12) i (13). Co było wymagane.

Na zakończenie tej sekcji przedstawiamy sformułowania dwóch twierdzeń Kuhna-Tuckera dla problemu

programowanie wypukłe z ograniczeniami liniowymi.

Twierdzenie 4. Niech układ ograniczeń (2) w wypukłym problemie programowania (1) - (3) będzie miał postać

, b - wektor wymiaru
... Następnie, aby uzyskać nieujemny wektor było rozwiązaniem problemu, jest to konieczne i wystarczające

był wektor nieujemny takie że
Jest punktem węzłowym funkcji Lagrange'a danego problemu.

Zauważ, że w tym przypadku funkcja Lagrange'a ma postać.

Twierdzenie 5. Uwzględnijmy wypukły problem programowania (1), (2) funkcję celu jest różniczkowalna w sposób ciągły, układ ograniczeń (2) ma postać
, gdzie A jest macierzą wymiaru
, b - wektor wymiaru
. Następnie, aby uzyskać wektor
było rozwiązaniem problemu, konieczne i wystarczające jest, aby istniał wektor nieujemny takie, że warunki
,
.

Zauważ, że Twierdzenia 4 i 5 nie wymagają spełnienia warunku Slatera, dlatego nie są specjalnymi przypadkami Twierdzeń 1 i 3 i wymagają niezależnego dowodu.