20. Метод Куна-Таккера.

Условия Куна-Таккера

В предыдущем разделе было установлено, что множители Лаг­ранжа можно использовать при построении критериев оптималь­ности для задач оптимизации с ограничениями в виде равенств. Кун и Таккер обобщили этот подход на случай общей задачи нели­нейного программирования с ограничениями, как в виде равенств, так и в виде неравенств.

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

минимизировать (0)

при ограничениях (1)

Определение:

Ограничение в виде неравенства называется активным, или связывающим, в точке, если, и неактивным, или несвязывающим, если

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

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

3.1. Условия Куна-Таккера и задача Куна-Таккера

Найти векторы ,удовлетворяющие следующим условиям

(3)

(4)

(5)

(7)

Прежде всего проиллюстрируем условия Куна - Таккера на примере.

Минимизировать

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

Записав данную задачу в виде задачи нелиней­ного программирования (0)-(2), получим

Уравнение (3), входящее в состав условий Куна-Таккера, принимает следующий вид:

Неравенства (4) и уравнения (5) задачи Куна - Таккера в данном случае записываются в виде

Уравнения (5.16), известные как условие дополняющей нежесткости, принимают вид

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

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

3.2. Интерпретация условий Куна - Таккера

Для того чтобы интерпретировать условия Куна - Таккера, рассмотрим задачу нелинейного программирования с ограничения­ми в виде равенств:

минимизировать

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

Запишем условия Куна-Таккера

(8)

Для этой функции условия оптимальности первого порядка запи­сываются в виде

Нетрудно видеть, что условия Куна-Таккера (8) и (9) совпадают с условиями оптимальности первого порядка для задачи Лагранжа.

Рассмотрим задачу нелинейного программирования с ограни­чениями в виде неравенств:

минимизировать

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

Запишем условия Куна-Таккера

Соответствующая функция Лагранжа имеет вид

Условия оптимальности первого порядка записываются как

Заметим, что - множитель Лагранжа, соответствующий ограни­чению. Раньше было показано, чтопредставляет неявную цену, ассоциированную с ограничением; другими словами, вели­чинаотражает изменение минимального значения целевой функ­ции, вызываемое единичным приращением правой части- го ог­раничения.

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

Для того чтобы определить знак (неявной цены, ассоциирован­ной с ограничением), следует увеличить правую часть ограничения от 0 до 1. Ясно, что при этом область допустимых решений сужается, поскольку любое решение, удовлетворяющее ограничению, автоматически удовлетворяет неравенству. Следовательно, размеры допустимой области уменьша­ются, и минимальное значениеулучшить невозможно (так как вообще оно может только возрастать). Другими словами, неявная цена, ассоциированная с-м ограничением, должна быть неотри­цательной, что соответствует условиям Куна-Таккера.

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

В предыдущем разделе построены условия Куна-Таккера для задач условной оптимизации. С помощью метода множителей Лагранжа получено интуитивное представление о том, что условия Куна - Танкера тесно связаны с необходимыми условиями опти­мальности. В данном разделе рассматриваются строгие формули­ровки необходимых и достаточных условий оптимальности решения задачи нелинейного программирования.

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

Рассмотрим задачу нелинейного программирования (0)-(2). Пусть - дифференцируемые функции, а х* - допус­тимое решение данной задачи. Положим. Далее пустьлинейно неза­висимы. Если х* - оптимальное решение задачи нелинейного про­граммирования, то существует такая пара векторов, чтоявляется решением задачи Куна-Таккера (3)-(7).

Условие, согласно которому должны быть линейно независимыми, известно как ус­ловие линейной независимости и по существу представляет собой некоторое условие регулярности допустимой области, которое поч­ти всегда выполняется для встречающихся на практике задач опти­мизации. Однако вообще проверка выполнения условия линейной независимости весьма затруднительна, так как требуется, чтобы оптимальное решение задачи было известно заранее. Вместе с тем условие линейной независимости всегда выполняется для задач нелинейного программирования, обладающих следующими свой­ствами.

1. Все ограничения в виде равенств и неравенств содержат линейные функции.

2. Все ограничения в виде неравенств содержат вогнутые функ­ции, все ограничения-равенства - линейные функции, а также существует, по крайней мере, одна допустимая точка х, которая рас­положена во внутренней части области, определяемой ограниче­ниями-неравенствами. Другими словами, существует такая точка х, что

Если условие линейной независимости в точке оптимума не вы­полняется, то задача Куна-Таккера может не иметь решения.

Минимизировать

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

На рис.1 изображена область допустимых ре­шений сформулированной выше нелинейной задачи. Ясно, что оптимальное решение этой задачи есть . Пока­жем, что условие линейной независимости не выполняется в точке оптимума.

Рис.1 Допустимая область в задаче 4

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

Запишем условия Куна-Таккера и проверим, выполняются ли они в точке (1, 0). Условия (3), (6) и (7) принимают сле­дующий вид;

(12)

(13)

При из уравнения (11) следует, что, тогда как уравнение (14) дает, Следовательно, точка оптимума не является точкой Куна - Таккера.

Заметим, что нарушение условия линейной независимости не обязательно означает, что точка Куна-Таккера не существует. Для того чтобы подтвердить это, заменим целевую функцию из этого примера функцией. При этом оптимум по-прежнему достигается в точке (1,0), в которой условие линейной независимости не выполняется. Условия Куна-Так­кера (12) - (16) остаются неизменными, а уравнение (11) принимает вид

Нетрудно проверить, что точка является точкой Куна-Таккера, т. е. удовлетворяет условиям Куна-Таккера.

Теорема о необходимости условий Куна-Таккера позволяет идентифицировать неоптимальные точки. Другими словами, тео­рему 1 можно использовать для доказательства того, что задан­ная допустимая точка, удовлетворяющая условию линейной неза­висимости, не является оптимальной, если она не удовлетворяет условиям Куна-Таккера. С другой стороны, если в этой точке условия Куна-Таккера выполняются, то нет гарантии, что най­дено оптимальное решение нелинейной задачи. В качестве примера рассмотрим следующую задачу нелинейного программирования.

Следующая теорема устанавливает условия, при выполнении которых точка Куна-Таккера автоматически соответствует оптимальному решению задачи нелинейного программирования.

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

Рассмотрим задачу нелинейного программирования (0) - (2). Пусть целевая функция выпуклая, все ограничения в виде неравенств содержат вогнутые функции, а ограничения в виде равенств содержат линейные функции. Тогда если существует решение, удовлет­воряющее условиям Куна-Таккера (3) - (7), то х* - оп­тимальное решение задачи нелинейного программирования.

Если условия теоремы 2 выполняются, то нахождение точки Куна-Таккера обеспечивает получение оптимального решения задачи нелинейного программирования.

Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример.

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

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

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

Метод и условия Каруша-Куна-Таккера (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.

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

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

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

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.

Запишем функцию Лагранжа: (4)
где λ i , i=1..m – неопределенные множители Лагранжа; z(X) и q i (X)– выпуклые вверх функции.

Теорема Куна-Таккера . Чтобы план X 0 был решением задачи (1) – (4) необходимо и достаточно, чтобы существовал вектор λ 0 ≥ 0 такой, что пара (X 0 ,λ 0) для всех X ≥ 0 и λ ≥ 0.
L(X, λ 0) ≤ L(X 0 ,λ 0) ≤ L(X 0 ,λ)

Назначение сервиса . Онлайн-калькулятор используется для нахождения экстремума функции через множители Лагранжа в онлайн режиме с проверкой решения в MS Excel . При этом решаются следующие задачи:

  1. составляется функция Лагранжа L(X) в виде линейной комбинации функции F(X) и ограничений g i (x);
  2. находятся частные производные функции Лагранжа, ∂L/∂x i , ∂L/∂λ i ;
  3. составляется система из (n+m) уравнений, ∂L/∂x i = 0.
  4. определяются переменные x i и множители Лагранжа α i .
Количество ограничений, g i (x) 1 2 3 4
Заданы ограничения x i ≥ 0.
.

Чтобы функция двух векторных переменных (4) имела седловую точку , необходимо и достаточно выполнения следующих условий Куна-Таккера :
(5)
(6)
(7)
(8)

Если решается задача минимизации , то имеет место седловая точка (X 0 , Y 0), если выполняются соотношения
L(X, λ 0) ≤ L(X 0 , Y 0) ≤ L(X 0 , Y)
Условия же Куна-Таккера существования седловой точки функции Лагранжа поменяют знак в (5) и (7) на противоположный.

Пример . Проверить выполнение условий Куна-Таккера. Найти точку оптимума задачи линейного программирования с ограничениями:
f(x) = x 1 2 -x 2 → min
g 1 (x) = x 1 - 1 ≥ 0
g 2 (x) = 26 - x 1 2 -x 2 2 ≥ 0
h 1 (x) = x 1 +x 2 - 6 = 0

Решение:
Функция Лагранжа: L(X, λ) = x 1 2 -x 2 - λ 1 (1-x 1) + λ 2 (26-(x 1 2 +x 2 2)) + λ 3 (6-(x 1 +x 2))
Необходимым условием экстремума функции Лагранжа является равенство нулю ее частных производных по переменным х i и неопределенным множителям λ.
Проверим выполнение условий Куна-Таккера. Вычислим матрицы вторых производных целевой функции и функций ограничений.

Матрица Гессе H f положительно полуопределена при всех значениях x, следовательно f(x) – выпуклая функция.
Ограничение g 1 (x) – линейная функция, которая одновременно является выпуклой и вогнутой.
Матрица Гессе для функции g 2 (x) имеет вид:

Δ 1 = -2, Δ 2 = 4.
Так как матрица H g 2 отрицательно определена, то g 2 (x) является вогнутой.
Функция h 1 (x) входит в линейное ограничение в виде равенства. Следовательно, условия (а), (б) и (в) Теоремы 1 выполнены. Найдем теперь точку оптимума x * .
Имеем:


Уравнение принимает следующий вид:

Для j=1 и j=2 соответственно можно получить следующие выражения:
j=1, 2x 1 -μ 1 + 2x 2 μ 2 + λ 1 = 0
j=2, -1 + 2x 2 μ 2 + λ 1 = 0
Таким образом, условия Куна-Таккера для нашего примера имеют следующий вид:
2x 1 -μ 1 + 2x 2 μ 2 + λ 1 = 0
-1 + 2x 2 μ 2 + λ 1 = 0
x 1 + x 2 – 6=0
μ 1 (x 1 -1) = 0
μ 2 (26 - x 1 2 – x 2 2) = 0
μ 1 , μ 2 ≥ 0

Из третьего уравнения находим: x 1 = 6-x 2 . Подставив значение x 1 в остальные уравнения, получим:
2(6-x 2) - μ 1 + 2μ 2 (6-x 2)
-1 + 2x 2 μ 2 + λ 1 = 0
μ 1 (6-x 2 -1) = 0 → x 2 = 5, x 1 = 1
μ 2 (26 – (6-x 2) 2 – x 2 2) = 0
Подставим x 2 = 5 в первое и второе уравнения:

Из второго уравнения выразим λ и подставим в первое уравнение:
3 - μ 1 - 8μ 2 = 0
Пусть μ 1 = 0,1 ≥ 0, тогда μ 2 = 2,2 ≥ 0. Таким образом, точка x * = является точкой минимума.

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

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

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

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

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

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

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

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

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

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

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

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


Wikimedia Foundation . 2010 .

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

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

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

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

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

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