Условна и безусловна оптимизация Теорема на Кун Тъкър. По-слаби условия

Централно място в теорията на нелинейното програмиране заема теоремата на Кун-Тъкър. Нека е даден проблем с нелинейно програмиране:

намирам максимална стойностфункции З=f(х 1, х 2, ..., x n) с ограничения

Нека съставим функцията на Лагранж за този проблем:

(4.2)

Ако условието за редовност е изпълнено (съществува според понеедна точка Х,за което g i(х)>0 за всички аз), тогава е валидна следната теорема.

Теорема.вектор х(0) тогава и само ако е оптимално решение на задача (4.1), когато съществува вектор Λ (0), такъв че когато за всички

точка ( X (0),Λ (0)) се нарича седлоточка за функция Е(х,Λ), а теоремата се нарича теоремата за седловата точка.Нека докажем достатъчността на условията (4.3).

Доказателство. Позволявам х(0) >0 и Λ (0) >0 - седлова точка на функцията Е(х,Λ). Ако в (4.3) вместо това Е(х,Λ) заместваме неговата стойност (4.2), получаваме

при .

Правилното неравенство е валидно за всяко , Следователно

Тогава от лявото неравенство получаваме

Тъй като в този случай

Че f(X (0))>f(х).

Така че точката X (0)удовлетворява (4.1) и във всички други точки, удовлетворяващи (4.1), функцията приема стойност, по-малка от X (0).

Това твърдение води решението на проблема с НЛП до намиране на седловините на функцията на Лагранж Е(х,Λ).

Доказателството за необходимостта от условия (4.3) не се разглежда поради неговата сложност.

Ако f(х) И g i(х)-диференцируеми функции, тогава условията (4.3) са еквивалентни на следните локални условия на Kuhn-Tucker:

Изразяване

означава, че стойността на частната производна на функцията на Лагранж се взема в точката ( X (0), Λ (0)), където

X (0)=(х 1 (0) , х 2 (0) , ..., x n(0)), Λ (0) =(λ 1 (0) , λ 2 (0) , ..., λ н (0)).

Тези условия могат да бъдат записани в векторна форма:

Пример.Намерете макс З=-х 1 2 -х 2 2 с ограничения

Нека покажем, че съществува Λ (0) 0, за което условията на Kuhn-Tucker (4.4), (4.5) за функцията са изпълнени в оптималната точка Е(х,Λ):

Е(х,Λ)=- х 1 2 -х 2 2 +λ 1 (2 х 1 +х 2 -2)+λ 2 (8-2 х 1 -х 2)+λ 3 (6- х 1 -х 2).

Съгласно условията (4.5) λ 2 и λ 3 трябва да вземат нулеви стойности, тъй като, замествайки х 1 =0,8 и х 2 =0,4 в израз

имаме стойности, по-големи от нула, и по условие

Съгласно условието λ 1 може да приеме ненулева стойност, тъй като

В съответствие с (2.16), производната

трябва да приема нулеви стойности, тъй като координатите на вектора X (0)са различни от нула. Намираме λ 1 =0,8. Следователно, в точката ( X (0),Λ (0)) условията на Kuhn-Tucker са изпълнени и това наистина е точка на екстремум.

Нека разгледаме условията на Kuhn-Tucker в малко по-различна форма.

Нека имаме оптимизационна задача с ограничения под формата на равенства:

z= f(х 1 , х 2 , …, xn) → мин

при условия:

g 1 ( х 1 , х 2 , ... , x n) = 0,

g 2 ( х 1 , х 2 , ... , x n) = 0,

ж н(х 1 , х 2 , . . . , x n) = 0.

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

В този случай седловата точка трябва да осигурява минимум в своите променливи x iи максимум по променливи λ й.

Необходими условия за стационарна точка са частните производни от първи ред по отношение на всички променливи да са равни на нула:

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

За получаване достатъчно условиесъществуването на минимум, е необходимо да се добави изискването Хесианът да бъде положително определен целева функция.

Нека помислим общзадача математическо програмиране:

Z= f(X) → min,

при условия:

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

Нека формираме функцията на Лагранж:

Тогава необходимите условияминимумът приема формата:

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

Има още едно условие, което трябва да бъде изпълнено при минималната точка. Това условие: λ аз= 0, което е следствие от анализа физически смисълкоефициенти на функцията на Лагранж.

Може да се покаже, че

Коефициент на Лагранж в минималната точка;

f* - оптимална стойностфункции.

Очевидно, когато b нараства аз валидна площсе разширява, което означава, че минимална стойностможе само да намалява, тоест производната трябва да е отрицателна (неположителна). Следователно при условната минимална точка

Най-накрая получаваме необходимите условия за условното минимум:

Изразите във втория ред гарантират, че оптималната точка е валидна.

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

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

Горните условия са еквивалентни Теорема на Кун-Тъкъри често се наричат ​​по същия начин.

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

Обобщение на материала в тази глава може да се види в две презентации:

файл “Нелинейно програмиране”;

файл "Теорема на Кун-Тъкър".

Слайдове 10-14 от презентацията „Теорема на Кун-Тъкър“ показват пример за решаване на проблема на Кун-Тъкър.

4.5. Контролни въпроси

(Разработено от Афанасиев М.Ю. и Суворов Б.П.)

Въпрос 1.При дадена реална функция f(х С= . Позволявам х 1 и х 2 - точки от този сегмент и 0 £ l £ 1.

Кое от следните неравенства е условие за изпъкналост на функция?

Възможни отговори:

Въпрос 2.При дадена реална функция f(х), определени върху сегмента от реални числа S=. Позволявам х 1 и х 2 са точките на тази отсечка и 0 £ l £ 1.

Кое от следните неравенства е условие една функция да бъде строго вдлъбната?

Възможни отговори:

Въпрос 3.функция

1) изпъкнал;

2) строго изпъкнали;

3) вдлъбнат;

4) строго вдлъбнати;

5) изпъкнали и вдлъбнати.

Въпрос 4.функция

3) вдлъбнат; 4) строго вдлъбнати;

5) изпъкнали и вдлъбнати.

Въпрос 5.функция

1) изпъкнал; 2) нито изпъкнал, нито вдлъбнат;

3) строго изпъкнали; 4) вдлъбнат:

5) изпъкнали и вдлъбнати.

Въпрос 6. Нов моделвисокоскоростен мотоциклет “Охлюв” се продава от фирмата на цена (30 – 2 х) хиляди долара за парче, където х- брой продадени мотоциклети. Променливите производствени разходи са $6 000 на единица, а постоянните разходи са $30 000. Увеличете максимално печалбата на вашия бизнес за седмицата.

Да кажем, че промяната в ставката на данъка върху продажбите е довела до допълнителни $4000 данък върху продажбите за всеки продаден мотоциклет.

Как ще се промени оптималното производство на мотоциклети в сравнение с първоначалната ситуация?

(Решете с помощта на функцията на Лагранж.)

Възможни отговори:

1) ще се увеличи с 2 ; 2) ще намалее с 2 ;

3) няма да се промени; 4) ще се увеличи с 1 ;

5) ще намалее с 1 .

Въпрос 7.Да приемем, че имате 2 седмици (14 дни) ваканция, която да прекарате на Канарските острови и Ница. Нека вашата функция на полезност е във формата 2 KN – 3К 2 – 4N 2,Където ДА СЕИ Н-броя дни, които прекарвате съответно на Канарските острови и Ница.

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

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

Възможни отговори:

1) 3 ; 2) 4 ; 3) 5 ; 4) 6 ; 5) 7 .

Въпрос 8.За задачата във въпрос 7 намерете стойността на двойната оценка на ограничението.

(Закръглете резултата до най-близкото цяло число.)

Възможни отговори:

1) 41 ; 2) 34; 3) 29 ; 4) 39 ; 5) 44 .

Въпрос 9.Монополистът планира производствена и пласментна програма за следващия период. Цени: Р 1 = 14 – 0,25х 1 (на продукт 1); Р 2 = 14 – 0,5х 2 (за продукт 2), където х 1 и х 2 - обеми на продажби на продукти. Да приемем, че всички произведени продукти са продадени. Максималният общ обем на продажбите е 57.

Какво е оптималното освобождаване на продукт 2?

Възможни отговори:

1) 36,4 ; 2) 30,7 ; 3) 26,3 ; 4) 20,6 ; 5) 41,8 .

Въпрос 10.Собственикът на малко предприятие има 100 хиляди рубли за следващия месец, които може да похарчи за увеличаване на дълготрайните активи ДА СЕ(закупуване на оборудване) на цена от 1 хил. Рубли на единица или за закупуване на допълнителен труд Лна цена от 50 рубли / час. Увеличение на готовите продукти, които могат да бъдат продадени за 10 хиляди рубли. за единица, определена от производствената функция F(K, L)= L 2/7 K 2/5.

Колко пари трябва да се изразходват за увеличаване на дълготрайните активи?

Възможни отговори:

1) 74,36 хилядитъркайте.; 2) 58,33 хиляди рубли.; 3) 63,44 хиляди рубли.;

4) 45,66 хиляди рубли.; 5) 39,77 хиляди рубли.

Отговори на въпроси:

1 -4,2 - 1,3 -4,4 - 5,

5 -2, 6 -5,7- 4,8- 2,9- 4,10- 2.

Теорема 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-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.

Теоремата на 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= конст.

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

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

При условия.

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

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

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

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

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

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

Ако за една допустима точка са изпълнени условията за стационарност, допълнителна нетвърдост и неотрицателност, както и λ 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