Прямые методы условной оптимизации

Лемма 1 (Фаркаша о неразрешимости). Система ЛН (1) неразрешима тогда и только тогда, когда разрешима система



Теорема 1. (Куна-Таккера) будет использована в следующей форме
Пусть функции , имеют непрерывные частные производные на некотором открытом множестве Rⁿ, содержащем точку x*. Если x* является точкой минимума функции  при ограничениях , удовлетворяющих условию регулярности в виде линейной независимости векторов , то существуют такие неотрицательные множители Лагранжа , что
(4)
(5)
Определим функцию Лагранжа как обычно:
(6)
Тогда теорему Куна-Таккера можно записать в виде
= (__{}_m)^T, _i≥0,
(7)
(8)
(9)
Заметим, что множители Лагранжа _i в задаче НП с ограничениями-равенствами являются знако-неопределенными, тогда как в теореме Куна-Таккера они должны быть неотрицательными.

Методы возможных направлений

Этот класс методов решения задач НП основан на движении из одной допустимой точки к другой с лучшим значением целевой функции.

Типичная стратегия поиска в алгоритмах этого класса состоит в следующем. Возьмем текущую допустимую точку  и найдем направление S_k такое, что при достаточно малых _k выполняются следующие два условия: 1) точка  является допустимой; 2)
После нахождения допустимого направления  решается задача одномерной минимизации по параметру  для нахождения оптимальной длины шага в направлении S_k. Далее перемещаемся в точку  и процесс поиска повторяется.