Доказательство. Покажем достаточность. Пусть - оптимальное решение задачи (1)-(3) и предположим, что

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

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

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

Из условия Слейтеда следует существование вектора , для которого Пусть . Если , то аналогично (12) имеем .Выберем . Тогда при достаточно малом справедливо и для . Отсюда непосредственно вытекает, что ч. т. д.

Если в решении задачи (8)-(11) величина мала по абсолютно величине, то это может привести к замедлению скорости сходимости метода возможных направлений. Чтобы избежать этих трудностей, следует изменить множество номеров в ограничении (10). Опишем один из таких подходов, в котором используется следующее множество номеров , где положительное число. Другими словами, это множество номеров ограничений задачи (1)-(3), которые в точке выполняются как равенства с точностью до .

Путь и некоторое начальное приближение. Допустим, что известно -е приближение и . Введем множество номеров , .

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

(13), (14), для всех (15), для всех (16). Обозначим эту задачу . Приведем описание одной итерации метода возможных направлений. Пусть оптимальное решение задачи . Рассмотрим три случая:

1) если то полагая .

2) если то полагая .

3) если то найдем решение задачи .

При вектор согласно критерию оптимальности является оптимальным решением задачи (1)-(3). Если же , то полагаем , .

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

Теорема 1. Пусть гладкие выпуклые функции, выполнено условие Слейтера и множество Q ограничено. Тогда

1) последовательность сходится к величине т.е. при ;

2) любая предельная точка последовательности есть точка минимума функции на множестве допустимых решений Q.

Доказательство. По построению последовательность не возрастающая и, в виду ограниченности множества Q, сущ. предел и при (1)

Величина на каждом шаге либо делится пополам, либо остается без изменений. Покажем, что . Предположим противное, т.е. . Тогда найдется такое, что и для всех . Другими словами, начиная с номера в алгоритме всегда реализуется первый случай . Выберем некоторую сходящуюся подпоследовательность . Такая подпоследовательность существует в виду ограниченности множества и условия нормировки (16) (п.9.1). Пусть . Тогда при некотором для всех справедливо для . Это означает, что для достаточно больших . Следовательно, , , для . Тогда из непрерывности функций следует для . С другой стороны, для . Отсюда вытекает существование такое, что для всех . С учетом непрерывности функций это означает, что для достаточно больших и всех . Таким образом, отсюда следует, что . Тогда , что противоречит (1). Следовательно, .

Покажем, что . Пусть номера тех итераций, когда происходит дробление величины . Из неравенства следует, что . Можно считать, что . Пусть . Тогда из критерия оптимальности следует, что существуют такие, что для . С другой стороны, найдется для всех . Из непрерывности дифференцируемости функций следует, что найдется номер такой, что для всех (2), для всех (3), , для всех . (4) Кроме того, из сходимости к 0 последовательности следует неравенство для достаточно больших . Из последнего неравенства и неравенства (4) имеем для всех больших некоторого . Отсюда, с учетом неравенств (2), (3) и выбора , получаем для всех для всех . Таким образом, , для любого , что противоречит сходимости последовательности к нулю. Следовательно, . Поскольку , то для любой предельной точки последовательности имеет место равенство . ч.т.д.