14.2. ВОГНУТЫЙ АЛГОРИТМ ОТСЕЧЕНИЙ

Вогнутый метод отсечений относится к задаче которой и все вогнуты.

Преобразование задачи. Рассмотрим задачу

Вводя скалярную величину легко видеть, что задача (14.15) эквивалентна задаче

По существу, добавлением одного ограничения и одной переменной мы заменили задачу (14.15) задачей с линейной целевой функцией.

Пусть

Тогда задача (14.16) эквивалентна задаче

Следовательно, мы свели задачу (14.15) к задаче с одним ограничением и линейной целевой функцией. Кроме того, согласно свойству гл. 2 функция вогнута.

Меняя обозначения, видим, что достаточно рассмотреть задачу

где — единственная вогнутая функция. Ясно, что задача (14.17) эквивалентна задаче (14.15). Вогнутый метод отсечений построен для решения задачи (14.17).

Предположения. Вогнутый алгоритм отсечений для задачи (14.17) предполагает, что допустимое множество задачи (14.17) содержится в компактном множестве где

Мы тйкже предполагаем, что функция ограничения непрерывна. Наконец, предполагается, что для данного существует вектор равномерно ограниченный на У и такой, что

Равномерная ограниченность означает, что существует положительное число М, такое, что для всех

Теперь мы полностью определим отображения, которые составляют вогнутый метод отсечений.

Детализация алгоритма. При заданном множестве составляем подзадачу

Тогда отображение Г имеет следующий вид:

Для заданной точки тест решения заключается в проверке того, имеет ли место соотношение

где — допустимое множество для задачи (14.17).

Отображение определяется с помощью и входящих в соотношение (14.19):

Воспользовавшись введенными обозначениями, получаем: если то Наконец, для

Для того чтобы начать поиск, положим, что Таким образом, алгоритм определен полностью.

Процедура формирования по осуществляется следующим образом. Пусть при заданном точка решает задачу (14.20). Если окажется, что то поиск завершен, в противном случае после определения (см. (14.19)) составляется

и множество

Как было отмечено в § 14.1, все подзадачи — задачи ЛП.

Построение метода выборл для задачи (14.17) так, чтобы А было замкнутым для всех оставляется в качестве упр. 1. Кроме того, упражнение показывает также, что точки входят в компактное множество.

Прежде чем установить сходимость алгоритма, докажем следующую лемму.

Лемма 14.1. Для всех

Доказательство. Пусть тогда Из выражения (14.19) следует:

Следовательно, для всех так что для всех k.

Но так как

и по предположению то для всех к. Лемма доказана.

Теперь сходимость будет установлена с помощью теоремы сходимости для метода отсечений.

Условие I. Для всех к Множество по предположению компактно. Кроме того, согласно упр. 2 все содержатся в компактном множестве.

Условие 2. Очевидно из определения Г.

Условие 3. Отображение А замкнуто согласно упр. 2. Ясно, что непрерывны, так как непрерывно и

Условие 4. Если не проходит тест решения, то так что Но тогда

Кроме того, согласно лемме 14.1

Алгоритм сходится.

Интерпретация сходимости. Пусть х — решение задачи (14.17). Тогда из леммы 14.1 и вида задачи (14.20) следует, что

Значит, если то должно быть решением задачи (14.17). Поэтому вогнутый метод отсечений вырабатывает точку, оптимальную для задачи (14.17).

14.2.1. Действие вогнутого метода отсечений

Пусть будут такими, как представлены на рис. 14.1, и предположим, что Допустимая область имеет вид Так как то первая подзадача заключается в следующем:

и имеет решение

На рис. 14.2 показано Обратите внимание на то, что так как то Вторая задача принимает вид

и имеет решение

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

С геометрической точки зрения гиперплоскости

используются для отсечения части множества. Отсюда и происходит название алгоритма отсечений.

Вогнутый метод отсечений существенно зависит от вогнутости (упр. 3). Действительно, алгоритм может не работать даже в том случае, если допустимая область выпукла, но ограничения выражены не вогнутыми функциями. Но следующий алгоритм преодолевает эту ограниченность.

Рис. 14.1. Исходные данные.

Рис. 14.2. Первая итерация.