Глава 14. АЛГОРИТМЫ ОТСЕЧЕНИЙ

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

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

14.1. ТЕОРИЯ АЛГОРИТМОВ ОТСЕЧЕНИЙ

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

Цель этих алгоритмов заключается в определении точки из некоторого множества где — или допустимая область, или некоторое другое множество, связанное с задачей нелинейного программирования. Но вследствие того, что обычно трудно оперировать с множеством в алгоритмах вместо непосредственного рассмотрения в начале процедуры берется более простое множество которое аппроксимирует . С помощью и специального отображения Г, которое рассматривается дальше, мы вычисляем такую тестовую точку

«что

Точка подвергается определенному тесту, называемому тестом решения, чтобы определить, входит ли она в Если эта точка проходит тест, то процедура завершает поиск, так как мы уже пришли к точке в

Если не проходит тест решения, то применяем второе отображение и определяем точку

С помощью строим полупространство Тогда Это полупространство обладает следующим свойством: Тогда из (14.3)

где символ означает, что содержится в но не совпадает с ним.

Множество аппроксимирует лучше, чем . С помощью определяется точка

Если проходит тест решения, то поиск завершается. В противном случае процедура продолжается аналогичным образом.

В общем случае по данному определяется тестовая точка Если проходит тест решения, то поиск завершается; если нет, то определяем точку и соответствующее множество Тогда Очевидно,

Обратите внимание также на то, что, хотя алгоритм вырабатывает Поэтому из (14.4) следует, что

В общем случае множества имеют вид

где — функции

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

Как действует метод отсечений. В каждом данном алгоритме будет задан тест решения для который построен так, что любое которое проходит тест, решает задачу НЛП.

Теперь допустим, что задана точка и мы хотим определить последующую точку

Сначала с помощью Г определим тестовую точку

Если проходит тест решения, то поиск завершается. В противном случае с помощью отображения находим

и определяем множество где

для функций Далее по соотношению формируем Чтобы можно было начать применение процедуры, задается множество

Короче говоря, по данному определяется Если то с помощью определяется множество и далее

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

Теперь может быть сформулирована теорема сходимости для методов отсечений. Мы рассмотрим лишь случай, когда вырабатывается бесконечная последовательность так как случай, когда поиск завершается через конечное число шагов, является тривиальным. Обозначения здесь такие же, как и раньше.

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

1) все точки входят в некоторое компактное множество и все точки также содержатся в некотором компактном множестве;

2) для любого из следует, что

3) для любого которое не проходит тест решения, отображение замкнуто. Кроме того, функции непрерывны;

4) если не проходит тест решения, то для любого

Если алгоритм удовлетворяет этим четырем условиям, то для некоторого где проходит тест решения.

Доказательство. Из условия 4 видно, что все существуют и непусты. Благодаря условию 1 должно существовать К, для которого

Используя условие 2, находим, что всех или в явной форме для всех

Тогда из выражения (14.9) имеем , привлекая условия 3 и (14.10), находим, что

или эквивалентно

Теперь допустим, что не проходит тест решения. Применяя условие 3 и учитывая, что А — замкнутое отображение, получаем Но для такого условие 4 гарантирует, что

Так как, выражения (14.12) и (14.13) противоречат друг другу, то должно пройти тест решений. Теорема доказана.

Замечания. Условие 1 обеспечивает наличие у последовательностей необходимых свойств. Условия 2 и 4 в совокупности дают то, что действительно «отсекает» достигая этим строгого улучшения и . В то же время благодаря второй части условия 4 полупространство не отсекает слишком много. Условие 3 содержит требования непрерывности и замкнутости, которые, как отмечалось ранее, способствуют сходимости.

Отображение Г является задачей линейного программирования. Изучение трех алгоритмов отсечений мы начнем с исследования отображения Г, которое одинаково для всех этих методов. В частности, для данного множества дает решение подзадачи

Более точно — решение задачи Для всех рассматриваемых методов максимизирующая точка будет существовать.

Во всех грех методах множество имеет вид Следовательно, задача определения представляет собой задачу ЛП. Более того, так как то из выражения (14.6) следует, что задача определения тоже является задачей

ЛП. Ясно, что задача определения также представляет собой задачу ЛП. Таким образом, эти три метода отсечений сводят решение задачи НЛП к решению некоторой последовательности задач