Глава 9. МЕТОДЫ УСКОРЕНИЯ СХОДИМОСТИ И ЗАДАЧА КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ

В предыдущей главе были представлены выпуклый симплексный метод и метод субоптимизации на многообразиях для задачи (8.1), задачи нелинейного

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

В выпуклом симплексном методе будут использованы сопряженные направления. Соответствующий метод будем называть алгоритмом «выпуклый симплексный метод — сопряженные направления» (ВСМ-СН). Этот алгоритм не только решает задачу (9.1) за конечное число шагов, но, кроме того, имеет большое значение для целевых функций общего вида, так как в этом случае использование сопряженных направлений способствует ускорению сходимости.

Метод субоптимизации на многообразиях для задачи (9.1) сводится к алгоритму, в котором с помощью направляющего элемента преобразуются соответствующие таблицы. В отличие от метода ВСМ-СН этот алгоритм не может быть использован для функции общего вида. Несмотря на это, он весьма эффективен для задачи КП с отрицательно определенной матрицей

9.1. СХОДИМОСТЬ ВЫПУКЛОГО СИМПЛЕКСНОГО МЕТОДА ДЛЯ ЗАДАЧИ КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ

Покажем, как можно комбинировать выпуклый симплексный метод и метод сопряженных направлений, чтобы получить метод ВСМ-СН. Сопряженные направления придадут выпуклому симплексному методу свойство; в случае квадратичной функции цели общего вида метод сходится за конечное число шагов к точке, в которой выполняются условия Куна — Таккера. Не будем требовать специальной формы матрицы Более того, при неквадратичных целевых функциях сопряженные направления, можно надеяться, помогут ускорить сходимость, используя квадратичную аппроксимацию. Метод сопряженных направлений, который будет использован, представляет собой процедуру 2 максимизации квадратичной функции (процедуру 2 гл. 6). Вместо расширяющего шага процедуры 2 мы используем шаг выпуклого симплексного метода. Тогда, поскольку в качестве основного алгоритма будет использован выпуклый симплексный метод, теорема сходимости В обеспечивает

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

Отображение Перед тем как перейти к изложению метода ВСМ-СН, следует ввести отображение Напомним, что обозначает допустимую область. Отображение по заданному и направлению определяет

При этом используется соотношение

где — интервал,

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

Соотношение между Пусть тогда максимизирует на отрезке прямой, проходящей через х в направлении заключенном в допустимой области. Например, рассмотрим задачу (8.1) с допустимой точкой х. Пусть — наименьшее, а — наибольшее при котором точка допустима. Вообще говоря, Тогда вследствие линейности ограничений для всех

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

Конечно, при

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

обладает следующим свойством:

В процедуре, которая будет проводиться важно знать, когда из условия (9.4) следует другое (9.5). Тогда у максимизирует как «а всей прямой, так и на ее допустимом участке.

Построение процедуры ВСМ-СН. Процедура основана на модификации процедуры 2 минимизации квадратичной функции. В качестве расширяющего шага (шага (а) процедуры 2) мы применяем шаг выпуклого симплексного метода. Обозначения означают точки и направления в соответствии

Метод ВСМ-СН следует процедуре 2 до тех пор, пока она может вырабатывать допустимые точки. Всякий раз, когда процедура 2 не может дать допустимую точку, мы перестаем пользоваться ею и вместо этого применяем отображение чтобы обеспечить допустимость. Далее из допустимой точки, полученной с помощью метод ВСМ-СН после подготовительного шага включает в работу процедуру 2. Здесь всюду, где можно, для построения сопряженных направлений используется процедура 2. Как только эта процедура дает недопустимую точку, то мы подставляем вместо этой точки допустимую и возобновляем применение процедуры 2.

Вместо того чтобы использовать отображение как в процедуре 2, в методе ВСМ-СН применяется при Эта модификация обеспечивает допустимость всех точек. Если точки, полученные по входят также в то шаги 0 и 1 метода ВСМ-СН в точности совпадают с процедурой 2. Значил, если окажется квадратичной функцией, то будут вырабатываться сопряженные направления и процедура сойдется за конечное число итераций. Всякий раз, когда точка из не входит в это означает, что процедура 2 не могла бы дать допустимую точку, и мы после вспомогательного шага начинаем заново с шага О, но уже по лученной точкой. Каждый раз, когда мы возвращаемся к шагу 0, мы фактически возобновляем процедуру 2 и опять начинаем наши усилия по построению сопряженных направлений.

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

Чтобы начать применение метода ВСМ-СН, должна быть задана некоторая допустимая точка . В шаге 0 метода ВСМ-СН используются направления качестве в точке будет использовано направление, которое определит выпуклый симплексный метод. Тогда первая точка Следует обратить внимание на то, что такая же, как если бы в точке был применен выпуклый симплексный метод. Если при то, пока это имеет место, наша процедура ВСМ-СН будет вести себя аналогично процедуре 2. Если то точка, полученная по процедуре 2, не будет допустимой. В этом случае мы повторяем шаг О после вспомогательного шага и возобновляем наши усилия по построению сопряженных направлений.

Шаг 2 метода служит в качестве вспомогательного. В этом шаге вычисляется для всех Здесь является компонентой вектора оценок компонентой Если то мы уменьшаем меняя только базисные переменные до тех пор, когда либо перестает возрастать, либо некоторое переменное становится нулем (в зависимости от того, что наступит первым). Таким образом, изменение в точности совпадает со случаем в выпуклом симплексном методе, где играет роль

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

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

Алгоритм ВСМ-СН. В настоящей процедуре как для так и для Исходная базисная

допустимая точка и соответствующая таблица считаются заданными. Определим . Положим и перейдем к шагу 0.

Шаг 0. Замена на задана. Полагаем Пусть — точка, — направление, определенные выпуклым симплексным методом в точке Преобразовываем базис, включая в число базисных наибольшее количество наибольших переменных. Если то происходит переход к шагу 1. В противном случае полагаем и происходит переход к шагу 2.

Шаг 1. Точка и направления заданы.

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

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

в. Полагаем Вычисляется Если то происходит переход к в противном случае — переход к шагу 2 с и замена на

г. Полагаем Замена на и переход к шагу 1.

Шаг 2. Задано Преобразовываем базис, включая в число базисных наибольшее количество наибольших по величине переменных. Полагаем .

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

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

Если то замена I на и переход к

Замечания. Шаг 0 подобен исходному шагу процедуры 2. Для после расчета надо проверить, имеет место Если да, то надо вычислить и продолжить процесс таким же образом для Если то переход к шагу и замена на (см. также упр. 2).

Для шага О точка вычисляемая выпуклым симплексным методом может быть записана также в виде

Если на шаге 0, шагах 16 и в все х вычисленные входят также в то, как было указано раньше, шаги 0 и 1 превращаются в процедуру 2 В этом случае, если целевая функция квадратична, то будет иметь место сходимость за конечное число шагов

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

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

и ясно, что

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

Таким образом, если выпуклый симплексный метод перестает менять то после того, как шаг 0 наступит в следующий раз, И уже более не будет меняться в шагах 0 и 1.

Сходимость за конечное число шагов в задаче квадратичного программирования. Теперь рассмотрим задачу КП. Предположим, что имеют место предположения, которые обеспечивают сходимость выпуклого симплексного метода, используемого в чистом виде, к точке, которая удовлетворяет условиям Куна — Таккера. Согласно теореме сходимости В метод ВСМ-СН также будет сходиться к этой точке, так как в шагах 0 и 1 используется выпуклый симплексный метод. Однако сходимость могла бы быть лишь в предельном смысле. Следующая теорема убеждает в том, что сходимость будет конечной. Подходящая точка определяется как точка, в которой выполняются условия Куна — Таккера.

Чтобы упростить доказательство, сначала сделаем два предположения:

Предпол ожение I. Метод ВСМ-СН сходится к единственной подходящей точке. Так как мы знаем, что любая сходящаяся подпоследовательность должна сходиться к решению, предположение I обеспечивает сходимость всей последовательности к единственной точке х.

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

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

Теорема 9.1. Пусть — произвольная квадратичная функция для задачи (9.1). Допустим, что выполняются предположения I и II и предполооюения выпуклого симплексного метода. Тогда метод ВСМ-СН сходится за конечное число шагов.

Пр имечание. В теореме означает выработанную точку, его не следует смешивать с обозначением используемым при изложении алгоритма ВСМ-СН. Доказательство. Допустим, процедура не находит подходящую точку за конечное число итераций и вырабатывает бесконечную последовательность. Как было отмечено выше, благодаря предположению I вся последовательность должна сходиться к х

Пусть - число положительных компонент х. Обозначая компоненту х через полагаем

и

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

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

Обращаясь к предположению II, приходим к тому, что

и из непрерывности с

для всех х, лежащих в окрестности х. Значит, для достаточно больших скажем для из (9.6) имеем

Покажем, что существует целое такое, что для всех

Выберем на котором наступает шаг 2, и предположим, что при некотором

Тогда согласно и (9.9) шаг 2 должен уменьшать Кроме того, для достаточно больших согласно (9.6) и (9.7) базисные переменные будут существенно большими по сравнению с Таким образом, при достаточно больших когда уменьшается, можно будет уменьшить до нуля, не заставляя при этом какое-либо базисное переменное также уменьшаться до нуля (следовательно, не выходя за пределы допустимой области). Более того, как бы то ни было должно быть уменьшено до нуля, так как согласно (9.8) только при этом целевая функция достигает своего наибольшего значения. Следовательно, на некоторой итерации где к достаточно большое, например если то шаг 2 уменьшит до нуля.

Для всех последующих итераций останется нулем. Действительно, шаг 2 не может увеличить Далее согласно (9.9) выпуклый симплексный метод также не увеличит Аналогично, как было отмечено при изложении алгоритма, шаги .0 и 1 вследствие того, что они основаны на выпуклом симплексном методе, никогда не будут увеличивать Повторяя эту аргументацию для всех мы найдем, что должно существовать такое при котором выполняется (9.10).

Итак, для все компоненты строго положительны и

Таким образом, меняются только переменные у и ни одна из них в нуль не обращается. Значит, максимум в отображении должен наступить до достижения границы и дает точки, которые находятся в Тогда шаги 0 и 1 процедуры ВСМ-СН ведут себя как процедура 2 и при этом вырабатываются сопряженные направления.

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