Главная › Услуги › Необходимые оптимальные условия куна таккера линейный случай. Теоремы куна-таккера. Смотреть что такое "Условия Каруша - Куна - Таккера" в других словарях

Необходимые оптимальные условия куна таккера линейный случай. Теоремы куна-таккера. Смотреть что такое "Условия Каруша - Куна - Таккера" в других словарях

Постановка задачи

Рассмотрим задачу нелинейной оптимизации. Пусть есть функции

При условиях .

Вильям Каруш в своей дипломной работе нашёл необходимые условия в общем случае, когда накладываемые условия могут содержать и уравнения, и неравенства. Независимо от него к тем же выводам пришли Гарольд Кун и Альберт Таккер.

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

Если при наложенных ограничениях - решение задачи, то найдётся ненулевой вектор множителей Лагранжа такой, что для функции Лагранжа выполняются условия:

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

Перечисленные необходимые условия минимума функции в общем случае не являются достаточными. Существует несколько вариантов дополнительных условий, которые делают их достаточными.

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

Если для допустимой точки выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также λ 1 > 0 , то .

Более слабые условия

Если для допустимой точки выполняются условия стационарности, дополняющей нежёсткости и неотрицательности, а также (условие Слейтера ), то .

Wikimedia Foundation . 2010 .

Смотреть что такое "Условия Каруша - Куна - Таккера" в других словарях:

В теории оптимизации условия Каруша Куна Таккера (англ. Karush Kuhn Tucker conditions, KKT) необходимые условия решения задачи нелинейного программирования. Чтобы решение было оптимальным, должны быть выполнены некоторые… … Википедия

Вильям Каруш William Karush Дата рождения: 1 марта 1917(1917 03 01) Место рождения: Чикаго, США Дата смерти … Википедия

У этого термина существуют и другие значения, см. Оптимизация. Оптимизация в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного … Википедия Википедия

Метод множителей Лагранжа, метод нахождения условного экстремума функции f(x), где, относительно m ограничений, i меняется от единицы до m. Содержание 1 Описание метода … Википедия

Теоремы Куна-Таккера - родовое название для утверждений, представляющих собой обобще-

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

следующего типа:

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

M, (?)

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 дифференцируемы (теоремы Ку-

на-Таккера в дифференциальной форме).

Напомним, что функция

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

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

Лагранжа.

Имеет место следующее утверждение.

Теорема 197 (Теорема Джона для дифференцируемых функций):

Пусть?x - решение задачи (?), такое что?x 2 intX и функции f( ), g1( ), . . . , gn( ) дифферен-

цируемы в точке?x.

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

выполнены следующие соотношения (условия Куна-Таккера):

0, i = 1, . . . , n

J = 0 (условия дополняющей

нежесткости).

Отметим, что условия дополняющей нежесткости можно записать в виде

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

Из этих условий следует, что если множитель Лагранжа положителен (_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, то условия Куна-Таккера характеризуют не решение рассматриваемой задачи, а

структуру множества ограничений в точке?x и теорема не имеет непосредственной связи с интересую-

щей нас задачей максимизации функции f( ), поскольку градиент самой функции f( ) .пропадает. из

условий Куна-Таккера.

Поэтому важно охарактеризовать условия, которые гарантируют, что _0 > 0.

Такие условия называются условиями регулярности.

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

так называемое условие Слейтера - имеет вид:

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

шее условие регулярности формулируется в терминах градиентов функций-ограничений и имеет вид:

градиенты активных ограничений в точке?x линейно независимы. (В число рассматриваемых ограни-

чений следует включать и ограничения на неотрицательность.)

Обозначим через A множество индексов тех ограничений, которые в точке оптимума?x активны

(в том числе, индексы всех ограничений в виде равенств), т. е.

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

Тогда если градиенты ограничений - векторы

линейно независимы2, то _0 > 0. Это условие называется условием регулярности Куна-Таккера.

Заметим, что если _0 > 0, то без потери общности можно считать _0 = 1, что обычно и делается.

Соответствующую теорему и называют собственно (прямой) теоремой Куна-Таккера. Теорема 198 (Прямая теорема Куна-Таккера, необходимое условие оптимальности):

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

X 2 intX и выполнено условие регулярности Куна-Таккера.

Тогда существуют множители Лагранжа _j > 0, j = 1, . . . ,m, такие что при _0 = 1 выполнены

следующие соотношения:

0, i = 1, . . . , n

Несложно переформулировать эту теорему для задач (??) и (???). Здесь требуются такие же мо-

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

0, i = 1, . . . , n

можно переписать в виде:

Это соотношение показывает, что в точке оптимума градиент целевой функции является линейной ком-

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

цательны. Рис. 17.1 иллюстрирует это свойство. Интуитивно, идея этого свойства состоит в том, что

если бы какой-нибудь коэффициент линейной комбинации был отрицательным, то можно было бы

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

f( ), {gk( )} выполнение этих условий в допустимом решении?x (т. е. точке, удовлетворяющей огра-

ничениям) при некоторых множителях Лагранжа, удовлетворяющих требованиям прямой теоремы,

гарантирует, что?x является решением задачи.

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

Пусть f( ) - дифференцируемая вогнутая функция, g1( ), . . . , gn( ) - дифференцируемые

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

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

0 = 1 выполнены следующие соотношения:

0, i = 1, . . . , n

Тогда?x - решение задачи (?).

Теорему можно очевидным образом переформулировать для задач (??) и (???). Для задачи (???)

ограничения в виде равенств могут быть только линейными (это связано с тем, что ограничение в виде

равенства, gj(x) = 0, следует представить с помощью двух ограничений в виде неравенств, gj(x) > 0

и?gj(x) > 0, каждое из которых задается квазивогнутой функцией; такое может быть только если

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

В еще одном варианте достаточного условия оптимальности предположение о вогнутости целевой

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

Теорема Куна-Таккера является обобщением методов решения оптимизационных задач в двух направлениях:

Линейного программирования на нелинейный случай, который получил по аналогии не очень удачное название «нелинейного программирования»;

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

Метод и условия Каруша-Куна-Таккера (Karush-Kuhn- Tucker conditions , KKT) формально являются необходимыми условиями оптимальности задачи нелинейного программирования. Кроме того, необходимые условия включают, так называемые условия регулярности стационарных точек – невырожденность множества градиентов ограничений. Метод является обобщением метода множителей Лагранжа на случай ограничений неравенств.

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

Основным методом в нелинейном программировании до сих пор остаётся применение функции Лагранжа, полученной переносом ограничений в целевую функцию. Условия Куна-Таккера также выведены из этого принципа.

Вильям Каруш в своей дипломной работе в 1931 году нашёл необходимые условия в общем случае ограничений равенств и неравенств. Независимо от него к тем же выводам позднее в 1941 году пришли Гарольд Кун и Альберт Таккер. Полученные ими результаты были более общими.

Если при наложенных ограничениях является решением задачи, то найдётся вектор множителей Лагранжа такой, что для функции Лагранжа выполняются условия:

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

- дополняющей нежёсткости : ;

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

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

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

Перейдём непосредственно к доказательству теоремы Куна-Таккера.

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

F(x)≤F(x опт)

F(x)-F(x опт)≤0.

Выберем два вида приращения x j вдоль j -й координаты

Δx j =x j -x jопт >0,

Δx j =x j -x jопт <0.

Переходя в этих соотношениях к пределу при Δx j →0, получаем:

Из этих соотношений следует, что

(3.6.1)

Аналогичное соотношение можно получить для случая минимума функции. Таким образом, доказана необходимость условий (3.6.1) для достижения в точке х опт максимума или минимума функции f(х) , т. е. если имеется экстремум, то условия (3.6.1) удовлетворяются. Но равенство нулю всех производных в точке х опт еще не обеспечивает существования в ней экстремума, т. е. условия (3.6.1) не являются достаточными. Геометрически это означает, что в случае нулевой производной от функции одной переменной может иметь место точка перегиба, а не максимум (или минимум), а в случае функции двух переменных - седловая точка, а не экстремум и т. д. Поэтому точки х опт , в которых выполняются соотношения (3.6.1), называются стационарными.

Заметим, что условие (3.6.1) удалось получить благодаря возможности придавать переменной х приращения двух знаков, откуда и возникли два неравенства при и при . Если допустимая область значений х ограничена неотрицательными значениями х ≥0, то внутри области, где х > 0, справедливость условия (3.6.1) сохраняется, так как там допустимы приращения обоих знаков. На границе области х ≥ 0, где х = 0, допускается только положительное приращение Δх >0, можно говорить только об односторонней производной, и из (3.6.1) следует следующее необходимое условие максимума:

Соответственно, необходимое условие минимума на границе области х j = 0 запишется в виде

б) Задача на условный экстремум

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

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) перепишутся как

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

где равенство нулю векторов понимается покомпонентно.

Рисунок 3.6.1 - Пояснение к задаче на условный экстремум

В случае n = 2 и m = 1 геометрическая задача об отыскании условного экстремума сводится (рис. 17-6) к отысканию точки касания А кривой φ = b к одной из кривых постоянного уровня f = const.

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

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

Составим функцию Лагранжа для данной задачи:

(4.2)

Если выполняется условие регулярности (существует по крайней мере одна точкаX, для которой g i (X )>0 для всех i ), то имеет место следующая теорема.

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

Точка (X (0) ,Λ (0)) называется седловой точкой для функции F (X ,Λ), а теорема называется теоремой о седловой точке. Докажем достаточность условий (4.3).

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

при .

Правое неравенство справедливо при любом , поэтому

Тогда из левого неравенства получим

Так как при этом

то f (X (0) )>f (X ).

Таким образом, точка X (0) удовлетворяет (4.1) и во всех других точках, удовлетворяющих (4.1), функция принимает значение меньшее, чем в X (0) .

Это утверждение приводит решение задачи НЛП к отысканию седловых точек функции Лагранжа F (X ,Λ).

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

Если f (X ) и g i (X )-дифференцируемые функции, то условия (4.3) эквивалентны следующим локальным условиям Куна-Таккера:

Выражение

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

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

Эти условия можно записать в векторной форме:

Пример. Найти maxZ =-x 1 2 -x 2 2 при ограничениях

Покажем, что существует Λ (0) 0, при котором в точке оптимума выполняются условия Куна-Таккера (4.4), (4.5) для функции F (X ,Λ):

F (X ,Λ)=-x 1 2 -x 2 2 +λ 1 (2x 1 +x 2 -2)+λ 2 (8-2x 1 -x 2)+λ 3 (6-x 1 -x 2).

Согласно условиям (4.5) λ 2 и λ 3 должны принимать нулевые значения, так как, подставляя x 1 =0.8 и x 2 =0.4 в выражения

имеем значения, большие нуля, а по условию

Согласно условию λ 1 может принимать ненулевое значение, так как

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

должна принимать нулевые значения, так как координаты вектора X (0) отличны от нуля. Находим λ 1 =0,8. Следовательно, в точке (X (0) ,Λ (0)) выполняются условия Куна-Таккера и она действительно является точкой экстремума.

Рассмотрим условия Куна-Такера в несколько другом виде.

Пусть имеем задачу оптимизации с ограничениями в виде равенств:

z = f (x 1 , x 2 , …, xn ) → min

при условиях:

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

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

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

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

При этом седловая точка должна обеспечивать минимум по своим переменным x i и максимум по переменным λj .

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

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

Для получения достаточного условия существования минимума необходимо добавить требование положительной определенности гессиана целевой функции.

Рассмотрим общую задачу математического программирования:

Z = f (X) → min,

при условиях:

Ограничения в виде неравенств могут быть преобразованы в ограничения в виде равенств добавлением к каждому из них ослабляющих переменных

Сформируем функцию Лагранжа:

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

Второе уравнение можно преобразовать, отбросив ослабляющие переменные и переходя к ограничениям-неравенствам. Получим ограничения исходной задачи. Третье уравнение можно умножить на ui /2 и заменить ослабляющие переменные, выразив их из второго уравнения системы.

Есть еще одно условие, которое должно выполняться в точке минимума. Это условие: λ i = 0, которое является следствием анализа физического смысла коэффициентов функции Лагранжа.

Можно показать, что

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

f * - оптимальное значение функции.

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

Окончательно получаем необходимые условия для условного минимума :

Выражения во второй строке гарантируют, что оптимальная точка будет допустимой.

Третья строка содержит следующую информацию: если ограничение активно (т.е. выражение в скобках равно нулю), то соответствующий коэффициент Лагранжа строго положителен. Положительность коэффициента Лагранжа означает активность соответствующего ограничения, т.е. то, что это ограничение является дефицитным, именно оно останавливает дальнейшее улучшение целевой функции. Если же ограничение не активно (т.е. выражение в скобках не равно нулю), то соответствующий коэффициент Лагранжа должен быть равен нулю, т.е. это ограничение не дефицитно, оно не оказывает влияния на дальнейшее улучшение целевой функции.

Для точки условного максимума коэффициенты Лагранжа меняют знак на противоположный (т.к. оптимальное значение целевой функции в точке условного максимума должно возрастать).

Приведенные условия эквивалентны теореме Куна-Такера и часто называются так же.

Достаточным условием для минимума (максимума) является выпуклость (вогнутость) целевой функции в стационарной точке. Это значит, что гессиан должен быть положительно (отрицательно) определен.

Конспективное представление материала этой главы можно посмотреть в двух презентациях:

файл «Нелинейное программирование»;

файл «Теорема Куна-Таккера».

На слайдах 10-14 презентации «Теорема Куна-Таккера» показан пример решения задачи Куна-Таккера.

4.5. Контрольные вопросы

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

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

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

Варианты ответов:

Вопрос 2. Дана действительная функция f (x ), определенная на отрезке действительных чисел S= . Пусть x 1 и x 2 - точки этого отрезка и 0 £ l £ 1.

Какое из нижеприведенных неравенств является условием строгой вогнутости функции?

Варианты ответов:

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

1) выпуклая;

2) строго выпуклая;

3) вогнутая;

4) строго вогнутая;

5) выпуклая и вогнутая.

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

3) вогнутая; 4) строго вогнутая;

5) выпуклая и вогнутая.

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

1) выпуклая; 2) ни выпуклая, ни вогнутая;

3) строго выпуклая; 4) вогнутая:

5) выпуклая и вогнутая.

Вопрос 6. Новая модель скоростного мотоцикла «Улитка» продается предприятием по цене (30 – 2x ) тыс. долл. за штуку, где х - количество проданных мотоциклов. Переменные производственные затраты составляют 6 тыс. долл. за штуку, фиксированные затраты - 30 тыс. долл. Максимизируйте прибыль предприятия за неделю.

Предположим, что в результате изменения ставки налога с продаж последний (налог) составил дополнительно 4 тыс. долл. на каждый проданный мотоцикл.

Как изменится оптимальный выпуск мотоциклов по сравнению с начальной ситуацией?

(Решить, используя функцию Лагранжа.)

Варианты ответов:

1) увеличитсяна 2 ; 2) уменьшится на 2 ;

3) не изменится; 4) увеличится на 1 ;

5) уменьшится на 1 .

Вопрос 7. Предположим, что у вас есть 2 недели (14 дней) отпуска, которые вы можете провести на Канарских островах и в Ницце. Пусть ваша функция полезности имеет вид 2KN – 3К 2 – 4N 2 , где К и N - количество дней, которое вы проводите на Канарских островах и в Ницце соответственно.

Сколько дней вы должны провести в Ницце, чтобы максимизировать свою функцию полезности?

(Для решения использовать функцию Лагранжа. Результат округлить до ближайшего целого. Проверить, выполняются ли условия оптимальности Куна - Таккера.)

Варианты ответов:

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,25x 1 (на продукт 1); р 2 = 14 – 0,5х 2 (на продукт 2), где x 1 и х 2 - объемы реализации продуктов. Предположим, что вся произведенная продукция реализуется. Максимальный суммарный объем сбыта - 57.

Каков оптимальный выпуск продукта 2?

Варианты ответов:

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

Вопрос 10. Владелец небольшого предприятия располагает на ближайший месяц 100 тыс. руб., которые он может потратить на увеличение основных фондов К (закупку оборудования) по цене 1 тыс. руб за единицу либо на покупку дополнительной рабочей силы L по цене 50 руб./ч. Увеличение готовой продукции, которая может быть продана по 10 тыс. руб. за единицу, определяется производственной функцией F(K, L)= L 2/7 К 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.