Необходими и достатъчни условия за kun tucker. Необходими условия за минимум на функция

Формулиране на проблема

Нека разгледаме проблем с нелинейна оптимизация. Нека има функции

При условия.

Уилям Каруш в своята теза откри необходимите условия в общия случай, когато наложените условия могат да съдържат както уравнения, така и неравенства. Независимо един от друг Харолд Кун и Албърт Тъкър стигат до същите заключения.

Необходими условия за минимум на функция

Ако при наложените ограничения има решение на задачата, тогава съществува ненулев вектор от множители на Лагранж, така че за функцията на Лагранж изпълнени са условията:

Достатъчни условия за минимум на функция

Изброените необходими условия за минимум на функция в общия случай не са достатъчни. Вариантите са няколко допълнителни условия, което ги прави достатъчни.

Проста формулировка

Ако за една допустима точка са изпълнени условията за стационарност, допълнителна нетвърдост и неотрицателност, както и λ 1 > 0, то .

По-слаби условия

Ако за допустима точка са изпълнени условията за стационарност, допълващи нетвърдостта и неотрицателността, както и ( Състоянието на Слейтър), Че .

Фондация Уикимедия. 2010 г.

Вижте какви са „условията на Каруш-Кун-Тъкър“ в други речници:

В теорията на оптимизацията условията на Karush Kuhn Tucker (KKT) са необходими условия за решаване на проблем с нелинейно програмиране. За да бъде решението оптимално, трябва да се направят определени неща... ... Wikipedia

В теорията на оптимизацията условията на Karush Kuhn Tucker (KKT) са необходими условия за решаване на проблем с нелинейно програмиране. За да бъде решението оптимално, трябва да бъдат изпълнени някои условия за редовност.... ... Wikipedia

Уилям Каруш Уилям Каруш Дата на раждане: 1 март 1917 г. (1917 03 01) Място на раждане: Чикаго, САЩ Дата на смърт ... Wikipedia

Този термин има и други значения, вижте Оптимизация. Оптимизация в математиката, компютърните науки и изследването на операциите, проблемът за намиране на екстремум (минимум или максимум) целева функцияв някаква област на крайномерен вектор ... Wikipedia Wikipedia

Метод на умножителя на Лагранж, метод за намиране условен екстремумфункции f(x), където, спрямо m ограничения, i варира от едно до m. Съдържание 1 Описание на метода ... Wikipedia

Теоремата на Kuhn-Tucker е обобщение на методите за решаване проблеми с оптимизациятав две посоки:

Линейно програмиранекъм нелинейния случай, който по аналогия получи не много сполучливото име „нелинейно програмиране”;

Нелинейни ограничения за равенство върху ограничения за неравенство.

Метод и условия на Каруш-Кун-Тъкър ( Условия на Каруш-Кун-Тъкър, KKT) са формално необходими условия за оптималността на проблем с нелинейно програмиране. В допълнение, необходимите условия включват така наречените условия за редовност за стационарни точки - неизродеността на набора от ограничителни градиенти. Методът е обобщение на метода на умножителя на Лагранж за случая на ограничения на неравенството.

Кун и Тъкър обобщиха метода на умножителя на Лагранж (за използване при конструиране на критерии за оптималност за проблеми с ограничения под формата на равенства) към случая обща задачанелинейно програмиране с ограничения, както под формата на равенства, така и неравенства.

Основният метод в нелинейното програмиране все още остава използването на функцията на Лагранж, получена чрез прехвърляне на ограничения към целевата функция. Условията на Kuhn-Tucker също са извлечени от този принцип.

Уилям Каруш в неговия дипломна работапрез 1931 г. той намира необходимите условия в общия случай на ограничения на равенствата и неравенствата. Независимо един от друг Харолд Кун и Албърт Тъкър стигат до същите заключения по-късно през 1941 г. Техните резултати бяха по-общи.

Ако при наложените ограничения е решение на задачата, тогава има вектор от множители на Лагранж, така че за функцията на Лагранж изпълнени са условията:

- стационарност: ;

- допълваща мекота: ;

- неотрицателност:.

Изброените необходими условия за минимум на функция в общия случай не са достатъчни. Има няколко опции за допълнителни условия, които ги правят достатъчни:

- просто състояние – 1) точката е стационарна, 2) условието за допълнителна нетвърдост е изпълнено, 3) множители на Лагранж;

- Състоянието на Слейтър (по-слаб) – 1) точката е неподвижна, 2) условието за допълнителна нетвърдост е изпълнено, 3) .

Нека преминем директно към доказателството на теоремата на Кун-Тъкър.

Ако непрекъсната функция от n променливи x = (x1,...,xn) F(x) има в точката х opt максимум, тогава съществува ε > 0 такова, че за всички хот ε-околността на точката хтърговия на едро

F(x)≤F(x opt)

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

Нека изберем два вида увеличение x jзаедно йти координати

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

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

Преминавайки в тези отношения до границата при Δ x j→0, получаваме:

От тези отношения следва, че

(3.6.1)

Подобна връзка може да се получи за случай на минимална функция. Следователно необходимостта от условия (3.6.1) за постигане в точката х на едромаксимална или минимална функция f(x), т.е. ако има екстремум, тогава условията (3.6.1) са изпълнени. Но равенството на нула на всички производни в точката х на едровсе още не гарантира наличието на екстремум в него, т.е. условията (3.6.1) не са достатъчни. Геометрично това означава, че в случай на нулева производна на функция на една променлива може да има инфлексна точка, а не максимум (или минимум), а в случай на функция на две променливи, седлова точка и не е екстремум и т.н. Следователно точките х на едро, при които са изпълнени съотношения (3.6.1), се наричат ​​стационарни.

Обърнете внимание, че условието (3.6.1) е получено благодарение на възможността за присвояване на променлива хувеличения на два знака, което е мястото, където двете неравенства възникнаха при и при . Ако валидният диапазон хограничени до неотрицателни стойности х≥0, след това вътре в региона, където х> 0, условието (3.6.1) остава в сила, тъй като там са разрешени увеличения на двата знака. На границата на обл х≥ 0, където х= 0, разрешено е само положително увеличение Δ х>0, можем да говорим само за едностранна производна, а от (3.6.1) следва следното необходимо условие за максимум:

Съответно необходимото условие за минимум на границата на района x j= 0 ще бъде записано като

б) Условен екстремумен проблем

При определяне на условния екстремум на функция, когато е необходимо да се определи максимумът (или минимумът) на функцията F(x)при ограничителни условия:

g i (x) = b i , i = 1, ..., m,

f(x)=max;

g i (x)=b i ;

Използва се и методът на множителите на Лагранж, който, както в случая на класическото вариационно смятане, се състои във въвеждането на функцията на Лагранж

(3.6.2)

където λ i са неопределените множители на Лагранж.

Ако приемем, че функцията е частен случай на функционала, получаваме, че необходимите условия за екстремума се намират чрез директно диференциране на връзка (3.6.2) и се записват във формата

Ако въведем вектори

отношения (17-8) и (17-9) ще бъдат пренаписани като

град Φ = град F - λ град φ = 0; (3.6.6)

където равенството на векторите на нула се разбира компонентно.

Фигура 3.6.1 - Обяснение на проблема с условния екстремум

Кога н= 2 и м = 1 геометрична задачаотносно намирането на условен екстремум се свежда (фиг. 17-6) до намиране на точката на допиране A на кривата φ = bкъм една от кривите на постоянно ниво f= конст.

Теорема 7.2.За проблема с изпъкнало програмиране (7.4)–(7.6), множеството допустими решениякойто има свойството редовност, планът е оптимален планако и само ако съществува вектор, такъв че
– седлова точка на функцията на Лагранж.

Ако приемем, че целта функция
и функции са непрекъснати и диференцируеми, тогава теоремата на Кун-Тъкър може да бъде допълнена с аналитични изрази, които определят необходимото и достатъчно условие за точката
беше седловата точка на функцията на Лагранж, т.е. беше решение на проблема с изпъкналото програмиране. Тези изрази имат следната форма:

Където И са стойностите на съответните частични производни на функцията на Лагранж, изчислени в седловата точка.

Теоремата на Кун-Тъкър заема централно място в теорията на нелинейното програмиране. Валидно е и за така наречените проблеми на квадратичното програмиране, т.е. къде е целевата функция
с ограничения:

.

В общия случай на решаване на проблеми с нелинейно програмиране за определяне на глобалния екстремум на проблема, няма ефективен изчислителен метод, ако не е известно, че всеки локален екстремум е също и глобален. По този начин, в проблем с изпъкнало и квадратично програмиране, множеството от възможни решения е изпъкнало, тогава ако целевата функция е вдлъбната, всеки локален максимум е също глобален.

Пример 7.3.Използвайки теоремата на Кун-Тъкър намираме
под ограничения

Решаваме графично (фиг. 7.2) и намираме:
;
;
(вижте решението по-долу за повече подробности). Нека покажем, че има вектор Y 0 0, при което условията на Kuhn-Tucker са изпълнени в оптималната точка. Нека съставим функцията на Лагранж:

Решение
намираме от системата:
. От второто уравнение
заместваме в първото уравнение на системата. Разграничете по :
. В изрази И заменете стойностите
И
. Имаме стойности на частични производни по-големи от нула и според условието те трябва да са равни на нула, тогава =0 И =0. От друга страна, може да приема ненулеви стойности, т.к
оттук
; всичко
тези. условията на Kuhn-Tucker са изпълнени, следователно тази точка е точка на екстремум.

Фиг.7.2. Графично решение на нелинейната задача

пример за програмиране 7.3

Необходимо условие за оптималностза проблем с нелинейно програмиране може да се формулира по следния начин. Позволявам
– оптимално решениезадачи (7.4)–(7.6) и функциите
,
,
диференцируеми в тази точка. Ако
е неособена точка от допустимото множество на задача (7.4)–(7.6), то тя е точка на Кун-Тъкър от тази задача.

По този начин, ако допустим набор
задача (7.4)-(7.6) няма особени точки и функциите Е(М),ж аз (М), (
) диференцируеми във всички точки
, тогава оптималното решение на този проблем трябва да се търси сред точките на Kuhn-Tucker.

Както е известно от математическия анализ, специална точкамножества от допустими решения на система от линейни уравнения и неравенства от вида

набор от възможни решения

ако в точката
градиентите на тези функции са линейно зависими
, които в него се превръщат в . Например,
– особена точка на множеството

Наистина ли,

Следователно това е линейно зависима система.

Градиентна функция
е вектор, чиито координати са съответно равни на стойностите на частните производни на функцията
в точката М 0 . Този вектор показва посоката на най-бързия растеж на функцията.

Необходимото условие за оптималност е малко полезно за решаването на повечето проблеми с нелинейното програмиране, тъй като Само в редки случаи е възможно да се намерят всички точки на Kuhn-Tucker на проблем с нелинейно програмиране.

Достатъчно условие за оптималностза проблем с нелинейно програмиране: ако
е седловата точка на функцията на Лагранж за задача (7.4)–(7.6), тогава
е оптималното решение на този проблем.

Това условие не е необходимо в общия случай: функцията на Лагранж може да няма едновременно седлови точки първоначален проблемнелинейното програмиране има оптимално решение.

Известни са различни методи, които позволяват приблизително да се намери оптималното решение на проблем с нелинейно програмиране. Въпреки това, тези методи осигуряват доста добро приближение само за проблема с изпъкнало програмиране, където всеки локален екстремум е също и глобален. Като цяло под градиентметодите разбират методи, при които движението към оптималната точка на функция съвпада с посоката на градиента на тази функция, т.е. започвайки от някаква точка
се извършва последователен преход към някои други точки, докато се идентифицира приемливо решение на първоначалния проблем. В този случай градиентните методи могат да бъдат разделени на 2 групи.

ДА СЕ първиТази група включва методи, при които изследваните точки не излизат извън обхвата на възможните решения на проблема. Най-често срещаният от тези методи е методът Франк-Волф (Вълк). Такива методи включват метода проектирани градиенти на Розен,метод валидни указания на Zeutendijk.

Co. второТази група включва методи, при които изследваните точки могат или не могат да принадлежат към областта на осъществимите решения. Въпреки това, в резултат на изпълнението на итеративния процес се намира точка в областта на възможните решения, която определя приемливо решение.

От тези методи най-често използваният метод е наказателни функцииили метод Arrow-Hurwitz.

При намиране на решения на проблеми с използване на градиентни методи, включително споменатите по-горе, итеративният процес се извършва до градиента на функцията
в следващата точка
няма да стане равно на нула или докато
, Където – сравнително малко положително число, характеризиращо точността на полученото решение.

Решаването на сложни проблеми с нелинейното програмиране с помощта на градиентни методи включва голямо количество изчисления и е препоръчително да се използва само компютър.

Използвайки пример, ще покажем общото значение на градиентните методи за решаване на проблеми с нелинейно програмиране.

Нека има функция на две променливи
. Нека първоначалните стойности на променливите са
, и стойността на функцията
. Ако
не е екстремум, тогава се определят такива нови стойности на променливите
И
така че следващата стойност на функцията
се оказа по-близо до оптимума от предишния.

Как се определя размерът на инкрементите? И ? За да направите това, в точки И Посоката на промяна на функцията към екстремума се определя с помощта на градиента. Колкото по-голяма е стойността на частната производна, толкова по-бързо функцията се променя към екстремума. Следователно увеличенията И се избират пропорционално на стойността на частните производни И по точки
И
. По този начин,
И
, Където – стойност, наречена стъпка, която определя мащаба на промяната И .

Пример 7.4.

Нека е необходимо да се увеличи максимално функцията

(максимум в точка (3;2))

.

В точката
,
при
ние имаме

;
,

Нека направим още една итерация. В точката
,
при
ние имаме

;
,

Фиг.7.3. Геометрична интерпретация на две стъпки

градиентен метод например 7.4

На фиг. 7.3 показва движението по наклона, което е извършено в в този пример. Поведение показва посоката на промяна на функцията към максимума. Ако вземем градиента със знак минус, тогава ще се придвижим към минимума.

Специфичен проблем с градиентните методи е изборът на размер на стъпката T. Ако правим малки стъпки, ще търсим оптимума много дълго време. Ако изберете неговата стойност твърде голяма, тогава оптимумът може да бъде „превишен“. Междинният проблем за избора на оптимален размер на стъпката се решава с помощта на подходящи методи. Ако стъпка Tсе определя приблизително, тогава те като правило попадат не в оптимума, а в неговата зона. Градиентните методи осигуряват определянето на локалните оптимуми. Когато се търси глобален оптимум с помощта на градиент, често има съмнение, че намереният оптимум е глобален. Това е недостатъкът на този метод при решаване на проблеми с неконвексно програмиране.

Въпроси за самопроверка

Постановка на проблема с нелинейното програмиране.

Процесът на намиране на решение на проблем с нелинейно програмиране, използвайки неговата геометрична интерпретация.

Алгоритъм на метода на Лагранж за решаване на задача от нелинейно програмиране.

Приложение на метода на Лагранж за решаване на задача на нелинейно програмиране в случай, че условията на връзка са неравенства.

Помощни определения и теореми, необходими за разглеждане на централната теорема на нелинейното програмиране - теоремата на Кун-Тъкър.

Теорема на Кун-Тъкър.

Необходимо и достатъчно условие за оптималност на задача от нелинейно програмиране.

Общото значение на градиентните методи за приближено решаване на задачи на нелинейното програмиране.

Групи градиентни методи за приближено решаване на задачи от нелинейното програмиране.

В предишния раздел бяха конструирани условията на Кун-Тъкър за задачи условна оптимизация. Използвайки метода на умножителя на Лагранж, беше получена интуитивна идея, че условията на Kuhn-Tanker са тясно свързани с необходимите условия за оптималност. IN този разделРазгледани са строги формулировки на необходими и достатъчни условия за оптималност на решаването на задача на нелинейно програмиране.

Теорема 1. Необходимост от условията на Кун-Тъкър

Нека разгледаме проблема с нелинейното програмиране (0) - (2). Нека са диференцируеми функции и x* е допустимо решение на тази задача. Нека го поставим. Освен това нека са линейно независими. Ако x* е оптималното решение на проблем с нелинейно програмиране, тогава има двойка вектори, която е решение на проблема на Kuhn-Tucker (3) - (7).

Условието, че те трябва да бъдат линейно независими, е известно като условие за линейна независимост и по същество е някакъв вид условие за редовност валидна площ, което почти винаги е удовлетворено за проблеми с оптимизацията, срещани в практиката. Като цяло обаче проверката на изпълнението на условието за линейна независимост е много трудна, тъй като се изисква предварително да се знае оптималното решение на проблема. В същото време условието за линейна независимост винаги е изпълнено за проблеми с нелинейно програмиране, които имат следните свойства.

• 1. Всички ограничения под формата на равенства и неравенства съдържат линейни функции.
• 2. Всички ограничения за неравенство съдържат вдлъбнати функции, всички ограничения за равенство съдържат линейни функции и също така има, според поне, една възможна точка x, която се намира във вътрешността на областта, определена от ограниченията на неравенството. С други думи, има точка x, такава че

Ако условието за линейна независимост в оптималната точка не е изпълнено, тогава проблемът Кун-Тъкър може да няма решение.

Минимизиране

под ограничения

На фиг. Фигура 1 показва областта на възможните решения на нелинейния проблем, формулиран по-горе. Ясно е, че има оптимално решение на този проблем. Нека покажем, че условието за линейна независимост не е изпълнено в оптималната точка.

Ориз.

Лесно се вижда, че векторите са линейно зависими, т.е. условието за линейна независимост в точката не е изпълнено.

Нека запишем условията на Kuhn-Tucker и проверим дали са изпълнени в точка (1, 0). Условия (3), (6) и (7) приемат следната форма;

От уравнение (11) следва, че докато уравнение (14) дава, Следователно, оптималната точка не е точка на Kuhn-Tucker.

Имайте предвид, че нарушаването на условието за линейна независимост не означава непременно, че точката на Kuhn-Tucker не съществува. За да потвърдим това, нека заменим целевата функция от този пример с функцията. В този случай оптимумът все още се постига в точка (1,0), в която условието за линейна независимост не е изпълнено. Условията на Kuhn-Tucker (12) - (16) остават непроменени и уравнение (11) приема формата

Лесно се проверява, че точката е точка на Кун-Тъкър, т.е. удовлетворява условията на Kuhn-Tucker.

Теоремата за необходимостта от условията на Kuhn-Tucker ни позволява да идентифицираме неоптимални точки. С други думи, теорема 1 може да се използва, за да се докаже, че дадена възможна точка, която удовлетворява условието за линейна независимост, не е оптимална, ако не удовлетворява условията на Kuhn-Tucker. От друга страна, ако в този момент условията на Kuhn-Tucker са изпълнени, тогава няма гаранция, че е намерено оптималното решение на нелинейния проблем. Като пример, разгледайте следния проблем с нелинейно програмиране.

Следващата теорема установява условията, при които точката на Kuhn-Tucker автоматично съответства на оптималното решение на проблем с нелинейно програмиране.

Теорема 2. Достатъчност на условията на Кун-Тъкър

Нека разгледаме проблема с нелинейното програмиране (0) - (2). Нека целевата функция е изпъкнала, всички ограничения за неравенство съдържат вдлъбнати функции, а ограниченията за равенство съдържат линейни функции. Тогава, ако има решение, което удовлетворява условията на Kuhn-Tucker (3) - (7), тогава x* е оптималното решение на проблема с нелинейното програмиране.

Ако условията на теорема 2 са изпълнени, тогава намирането на точката на Kuhn-Tucker осигурява оптимално решение на проблема с нелинейното програмиране.

Теорема 2 може да се използва и за доказване на оптималността това решениепроблеми с нелинейното програмиране. За илюстрация разгледайте отново примера:

Минимизиране

под ограничения

С помощта на теорема 2 доказваме, че решението е оптимално. Ние имаме

Тъй като матрицата е положително полуопределена за всички x, функцията се оказва изпъкнала. Първото ограничение на неравенството съдържа линейна функция, който е едновременно изпъкнал и вдлъбнат. За това

за да покажем, че функцията е вдлъбната, изчисляваме

Тъй като матрицата е отрицателно определена, функцията е вдлъбната. Функцията е включена в линейното ограничение в уравнението за равенство. Следователно, всички условия на теорема 2 са изпълнени; ако покажем, че това е точката на Kuhn-Tucker, ние наистина ще установим оптималността на решението. Условията на Kuhn-Tucker за пример 2 имат формата

Точката удовлетворява ограниченията (24) - (26) и следователно е допустима. Уравнения (22) и (23) приемат следната форма:

Поставяйки го, получаваме и. Така решението x*=(1, 5) удовлетворява условията на Kuhn-Tucker. Тъй като условията на теорема 2 са изпълнени, тогава оптималното решение на задачата от пример 3. Имайте предвид, че има и други стойности на и които удовлетворяват системата (22) - (29).

Бележки

• 1. За проблеми, срещани в практиката, условието за линейна независимост обикновено е изпълнено. Ако всички функции в проблема са диференцируеми, тогава точката на Кун-Тъкър трябва да се разглежда като възможна точкаоптимално. По този начин много от методите за нелинейно програмиране се събират в точката на Kuhn-Tucker. (Тук е уместно да се направи аналогия със случая безусловна оптимизация, когато съответните алгоритми позволяват да се определи неподвижна точка.)
• 2. Ако условията на теорема 2 са изпълнени, точката на Кун-Тъкър в същото време се оказва глобална минимална точка. За съжаление, проверката на достатъчни условия е много трудна и освен това приложните проблеми често нямат необходимите свойства. Трябва да се отбележи, че наличието на поне едно нелинейно ограничение под формата на равенство води до нарушаване на допусканията на теорема 2.
• 3. Достатъчните условия, установени от теорема 2, могат да бъдат обобщени в случай на проблеми с неизпъкнали функции, включени в ограничения под формата на неравенства, неизпъкнали целеви функции и нелинейни ограничения на равенства. В този случай се използват такива обобщения на изпъкнали функции като квази-изпъкнали и псевдо-изпъкнали функции.

Теоремите на Kuhn-Tucker са общо име за твърдения, които представляват обобщения

приложение на теоремата на Лагранж в случай на оптимизационни проблеми с ограничения под формата на неравенства, т.е. проблеми

следния тип:

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

М, (?)

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

Ето f: X 7! R - (в съответствие с установената терминология) целева функция, gr: X 7! R,

r = 1, . . . ,m, са ограничителни функции, X _ Rn е отворено множество.

Теорема 196 (теорема на Джон по отношение на седлова точка):

Нека функциите f( ), g1( ), . . . , gn( ) са вдлъбнати и?x е решение на задача (?), така че?x 2 intX.

След това има множители на Лагранж _j >

X е решение на проблема

Представяме тези твърдения за случая, когато функциите f, gr са диференцируеми (теореми на Ku-

on-Tucker в диференциална форма).

Припомнете си, че функцията

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

се нарича функция на Лагранж (лагранжиан) на тази задача, а коефициентите _j са множители

Лагранж.

В сила е следното твърдение.

Теорема 197 (теорема на Джон за диференцируеми функции):

Нека?x е решение на задача (?), така че?x 2 intX и функции f( ), g1( ), . . . , gn( ) диференциал

са количествено измерими в точка?x.

След това има множители на Лагранж _j > 0, j = 0, . . . ,м, не всички равно на нула, така че

изпълнени са следните отношения (условия на Kuhn-Tucker):

0, i = 1, . . . , н

J = 0 (условия на допълване

липса на твърдост).

Обърнете внимание, че условията за допълнителна отпуснатост могат да бъдат записани във формуляра

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

От тези условия следва, че ако множителят на Лагранж е положителен (_j > 0), тогава съответният

ограничението при решаването на проблема (при x = ?x) е изпълнено като равенство (т.е. gj(?x) = 0). други

с други думи, това ограничение е активно. От друга страна, в случай, когато gj(?x) > 0, тогава съответните

множителят на Лагранж _j е равен на нула.

Ако в проблема (?) някои от ограниченията имат формата на ограничения върху неотрицателността на някои xi,

тогава за тях не можете да въведете множители на Лагранж, като напишете отделно следните ограничения:

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

xi > 0, i 2 P _ (1, . . . , n). Във вътрешната точка (в смисъл, че1 ?x 2 intX) условията от първи ред за i 2 P са тогава

ще изглежда така:

За i /2 P тук, както в случая на представяне на проблема във формата (?), производната на функцията на Лагранж

за тази променлива ще изглежда като @L(?x,_)

В допълнение, условията за допълнителна нетвърдост също са изпълнени

От второто от тези условия следва, че за?xi > 0 (i 2 P)

От друга страна, ако @L(?x,_)/@xi Друга модификация на теоремата е свързана с наличието на ограничения под формата на равенства в задачата. Обозначаване

нека дефинираме множеството от съответните индекси чрез E. Задачата приема следния вид:

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

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

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

В същото време теоремата на Джон премахва условието, че всички множители на Лагранж са неотрицателни -

Множителите на Лагранж _j за j 2 E могат да имат произволен знак.

Теоремата на Джон не гарантира, че множителят на Лагранж на целевата функция, _0, е различен от нула.

Ако обаче _0 = 0, тогава условията на Kuhn-Tucker характеризират не решението на разглеждания проблем, а

структура на набора от ограничения в точка?x и теоремата няма пряка връзка с интереса

нашата текуща задача за максимизиране на функцията f(), тъй като градиентът на самата функция f() изчезва. от

Условия на Kuhn-Tucker.

Следователно е важно да се характеризират условията, които гарантират, че _0 > 0.

Такива условия се наричат ​​условия на редовност.

В случай, че разглежданият проблем е изпъкнал, едно от условията за редовност е

така нареченото условие на Слейтър има формата:

В случай, че целевата функция и ограниченията на проблема са диференцируеми, най-простият

Условието за редовност се формулира чрез градиенти на ограничителни функции и има формата:

градиентите на активните ограничения в точка?x са линейно независими. (Сред разглежданите ограничения са

трябва да бъдат включени и ограничения за неотрицателност.)

Нека означим с A набора от индекси на онези ограничения, които са активни в оптималната точка?x

(включително индекси на всички ограничения под формата на равенства), т.е.

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

Тогава, ако ограничителните градиенти са вектори

са линейно независими2, тогава _0 > 0. Това условие се нарича условие за редовност на Kuhn-Tucker.

Обърнете внимание, че ако _0 > 0, тогава без загуба на общност можем да приемем, че _0 = 1, което обикновено се прави.

Съответната теорема се нарича (директна) теорема на Кун-Тъкър. Теорема 198 (Директна теорема на Кун-Тъкър, необходимо условие за оптималност):

Нека функциите f( ), g1( ), . . . , gn( ) са диференцируеми и?x е решение на задача (?), така че

X 2 intX и условието за редовност на Kuhn-Tucker е изпълнено.

След това има множители на Лагранж _j > 0, j = 1, . . . ,m, така че когато _0 = 1 са изпълнени

следните съотношения:

0, i = 1, . . . , н

Лесно е да преформулирате тази теорема за задачи (??) и (???). Тук се изискват същите способности.

модификация на условията на Кун-Тъкър, както в теоремата на Джон.

0, i = 1, . . . , н

може да се пренапише като:

Тази връзка показва, че в оптималната точка градиентът на целевата функция е линейна ком-

комбинация от антиградиенти на ограничения и всички коефициенти на тази линейна комбинация са неотрицателни

ценен. Ориз. Фигура 17.1 илюстрира това свойство. Интуитивно идеята зад това свойство е следната

ако някой коефициент на линейна комбинация беше отрицателен, тогава това би било възможно

увеличете стойността на целевата функция чрез движение по това ограничение. Една от обратните версии на теоремата на Кун-Тъкър гласи, че когато функциите са вдлъбнати

f( ), (gk( )) изпълнение на тези условия в допустимо решение?x (т.е. точка, удовлетворяваща ограничението

стойности) за някои множители на Лагранж, които отговарят на изискванията на пряката теорема,

гарантира, че?x е решение на проблема.

Теорема 199 (Обратна теорема на Кун-Тъкър /достатъчно условие за оптималност/):

Нека f( ) е диференцируема вдлъбната функция, g1( ), . . . , gn( ) - диференцируеми

квазивдлъбнати функции, множеството X е изпъкнало и точката?x е допустима в задачата (?), и?x 2

Нека освен това съществуват множители на Лагранж _j > 0, j = 1, . . . ,m, така че когато

0 = 1 са изпълнени следните отношения:

0, i = 1, . . . , н

Тогава?x е решението на проблема (?).

Теоремата може да бъде преформулирана по очевиден начин за задачи (??) и (???). За задачата (???)

ограниченията под формата на равенства могат да бъдат само линейни (това се дължи на факта, че ограничението във формата

равенствата, gj(x) = 0, трябва да бъдат представени с помощта на две ограничения под формата на неравенства, gj(x) > 0

и?gj(x) > 0, всеки от които е даден от квазивдлъбната функция; това може да се случи само ако

ограничението е линейно).

В друга версия на условието за достатъчна оптималност, допускането, че целта е вдлъбната

функцията се заменя с предположението за квазивдлъбнатост с добавяне на условието rf(?x) 6= 0.