14.4. ДВОЙСТВЕННЫЙ МЕТОД ОТСЕЧЕНИЙ

При решении задачи (14.15) или ее модификаций с помощью рассмотренных до сих пор методов отсечений пытаются аппроксимировать допустимую область F. В двойственном алгоритме отсечений вместо этого используется функция Лагранжа и двойственная задача.

Некоторые результаты, вытекающие из анализа функций Лагранжа. Напомним некоторые функции, введенные в гл. 2: функция Лагранжа имеет вид

где

Прямая функция —

двойственная функция —

В гл. 2 было доказано, что

Прямая задача определения эквивалентна задаче

Двойственная задача определения может быть также записана в виде

при

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

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

Множество X также предполагается выпуклым и компактным в .

Множества являются множествами из вида

где а точки фиксированы.

Исходное множество определяется соотношением

где — точка из (14.29).

Алгоритмическое отображение. Алгоритмическое отображение заключается в следующем. Процедура начинается с множества из (14.31).

В общем случае пусть для заданного точка будет оптимальным решением подзадачи ЛП

или в явной форме

В обозначениях, использованных ранее, соотношение означает, что является решением задачи (14.32); таким образом,

Далее определяется точка которая максимизирует функцию Лагранжа на X, т. е. определяется

Благодаря компактности X и непрерывности и точка существует.

Тест решения заключается в проверке равенства

Если не проходит тест решения, то согласно (14.32) и (14.33)

Вычисленное кроме того, определяет отображение Другими словами, максимизирует на X). Согласно гл. 7 из компактности X следует замкнутость А.

Наконец, определим множество для соотношением

Короче говоря, при заданном решением подзадачи (14.32) определяется Тогда, применяя (14-33), определяем Если то необходим останов, в противном случае полагаем

Теперь докажем сходимость.

Условие 1. Так как то достаточно показать, что и компоненты ограничены.

Сначала определим точку х следующим соотношением:

где х существует благодаря компактности X.

Очевидно, Кроме того, полагая находим, что Поэтому ограничены.

Из выражения (14.29), определения и неотрицательности следует, что

Поэтому

и, так как Овсе ограничены. Следовательно, компактно.

Заметим также, что все входят в компактное множество X.

Условие 2. Это условие тривиально.

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

Условие 4. Если не проходит тест решения, то

Но в этом случае

Кроме того, точка где определяется из (14.34), удовлетворяет соотношению Таким образом, процедура сходится.

Интерпретация сходимости. Докажем теперь, что если проходит тест решения, т. е. если

то решение задачи (14.27) определено.

Перепишем подзадачу (14.32):

Двойственной к задаче ЛП (14.36) является задача

где

а — переменные. Из теории двойственности ЛП известно, что оптимальное значение целевой функции (14.37) равно

Рассматривая выражение (14.37), учитывая вогнутость целевой функции и ограничений и свойство из п. 2.3.1 (гл. 2), видим, что точка

удовлетворяет неравенству

Выбирая оптимальными для задачи (14.37), видим, что не меньше, чем оптимальное значение целевой функции в (14.37), т. е.

При этом — допустимая точка прямой задачи (14.27). Это следует из того, что аналогично выражению (14.39)

Кроме того, X выпукло, и используя свойство (е) п. 2.3.1 гл. 2, получаем

Эти рассмотрения приводят к важному результату. Полагая, что решение задачи (14.27), и учитывая, что допустимая точка, из (14.40) получаем

Теперь вычисляются точки для которые максимизируют

по Точка допустима для двойственной задачи, т. е.

Из соотношений (14.26), (14.42) и (14.43) получаем, что

Отсюда сразу следует, что если удовлетворяет тесту решения, то

Поведение переменных. Теперь рассмотрим точку Из выражений (14.39) и (14.40)

Следовательно, предел любой сходящейся подпоследовательности

должен быть оптимальной точкой задачи (14.27) (упр. 8).

Интерпретация двойственности. Используя задачу (14.36), покажем, что алгоритм аппроксимирует двойственную задачу.

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

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

Пусть , тогда

Теперь задача (14.46) может быть переписана в виде

Но задача (14.47) совпадает с задачей (14.36).

Упражнения

(см. скан)

(см. скан)

Примечания и ссылки

§ 14,1. Построение методов отсечений этим подходом является новым.

§ 14.2. Алгоритм был предложен Келли и в работе Ченея и Гольдштейна, см. также Вольф (1961). Доказательство с помощью теоремы сходимости для методов отсечений является новым.

§ 14.3. Этот алгоритм основан на статье Вейногта (1967), но доказательство является новым.

§ 14.4. Алгоритм этого раздела является двойственным к алгоритму, разработанному Данцигом и Вольфом (см. Данциг (1963),

гл. 24). Представление, приведенное в этой работе, является принципиально другим, основанным на построении новых столбцов, а не на отсечениях.