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

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

Рассмотрим задачу min f(x) (1), (2), (3), где f(x), выпуклые функции. Вводя дополнительные переменную и ограничение, можно сделать функционал задачи линейным: min y (4), (5), (6), (7)

Поэтому без ограничения общности будем считать, что .Пусть, как и прежде, множество допустимых решений задачи (1)-(3), , и выполняется условие Слейтеда.

Ненулевой вектор p назовем возможным направлением для множества Q из точки x, если найдется такое, что для всех точка .

Ненулевой вектор p называется направлением спуска для множества Q из точки x, если p возможное направление из этой точки и .

Для фиксированной точки рассмотрим вспомогательную задачу линейного программирования (8), (9), для всех (10), , для всех . (11) Условие (11) называется условиями нормировки. Из условий (11) и (9) следует, что целевая функция (8) ограничена снизу на множестве допустимых решений. Тогда из критерия разрешимости для задачи линейного программирования следует, что найдется хотя бы одно оптимальное решение задачи (8)-(11). Нулевое решение является допустимым решением вспомогательной задачи и, значит, .

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

В случае общей задачи нелинейного программирования без дополнительных условий типа выпуклости равенство является лишь необходимым условием минимума. Для задачи выпуклого программирования (1), (3) при выполнении условия Слейтера последнее равенство является также достаточным условием оптимальности.