Условия Каруша — Куна — Таккера. Теоремы куна-таккера
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 . При этом решаются следующие задачи:
- составляется функция Лагранжа L(X) в виде линейной комбинации функции F(X) и ограничений g i (x);
- находятся частные производные функции Лагранжа, ∂L/∂x i , ∂L/∂λ i ;
- составляется система из (n+m) уравнений, ∂L/∂x i = 0.
- определяются переменные x i и множители Лагранжа α i .
Чтобы функция двух векторных переменных (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 Описание метода … Википедия