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

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

Рассмотрим задачу 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) при выполнении условия Слейтера последнее равенство является также достаточным условием оптимальности.

Теорема 1(критерий оптимальности)

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

Доказательство

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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