9.2. МЕТОД СУБОПТИМИЗАЦИИ НА МНОГООБРАЗИЯХ ДЛЯ КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ

Теперь применим метод субоптимизации на многообразиях гл. 8 к задаче КП:

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

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

Процедура преобразования таблиц. Пусть исходная таблица имеет вид

Обратите внимание на то, что если мы определим точку которая удовлетворяет условию (9.14) и для которой

то условия Куна — Таккера для задача (9.13) удовлетворяются.

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

Дополняемость и полудополняемость. Прежде чем сформулировать алгоритм, нужно дать некоторые определения. Точка будет называться дополняющей, если она удовлетворяет условиям (9.14), (9.15) и Точка будет называться полудополняющей, если она удовлетворяет условиям (9.14), (9.15) и, кроме того, для некоторого

для некоторого

а для всех остальных из следует, что и из следует, что Следует обратить внимание на

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

Теперь мы можем дать строгую формулировку алгоритма.

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

Шаг а. Точкя — дополняющая. Определим

Если то алгоритм завершает поиск: условия Куна—Таккера удовлетворяются, — оптимальная точка.

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

Шаг Точка полудополняющая

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

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

Каждая точка имеет ненулевых базисных компонент, которым соответствует базисная таблица. Таким образом, как и в симплексном методе, вместо непосредственного физического изменения переменных мы можем, преобразовывая данную таблицу, перейти к следующей таблице (упр. 9.5).

Связь алгоритма преобразования таблиц с процедурой субоптимизации на многообразиях. Теперь покажем, что алгоритм преобразования таблиц является частным случаем процедуры субоптимизации на многообразиях. По заданной точке оба метода получают одну и ту же точку Здесь необходимы предположения о том, что квадратичная целевая функция вогнута, существуют решения подзадач, они единственны и обладают свойством единственности, введенным в гл. 8. Эти требования обеспечивают сходимость метода многообразия. Как было упомянуто выше, также требуется, чтобы все базисы (9.14) были невырожденными.

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

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

В обоих методах, если все поиск завершается.

Допустим . В методе многообразий образуется и решением соответствующей подзадачи

определяется оптимальная точка

В методе преобразования таблиц задача (9.18) может быть решена увеличением небазисной переменной

если при этом обращается в нуль базисная переменная Когда соответствующее х в точности совпадает с точкой метода многообразий.

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

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

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

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

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

построить из увеличивая до обращения в нуль

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

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

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

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

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

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

Упражнения

(см. скан)

(кликните для просмотра скана)

(см. скан)

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

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

§ 9.2. Алгоритм преобразования таблиц был предложен в статьях Данцига (Данциг (1963)) и ван де Панна и Уинстона. В этих статьях сходимость доказана исследованием алгебраических преобразований таблицы. Аргументация, представленная в этом параграфе, является геометрической содержанию и связывает алгоритм преобразования таблиц с более общим подходом метода многообразий.

Дополнительные замечания

Квадратичное программирование Исследовано подробно. Обычней оно рассматривается как расширение ЛП; здесь, однако, оно рассматривается как частный случай НЛП. Подход через НЛП позволяет, например, использовать метод ВСМ - СН, применимый к функциям общего вида так же, как и к квадратичным функциям. Другие работы по КП см. у Била (1959); Баранкина и Дорфмана; Бута (1964); Хильдрета (1957); Хоутеккера; Лемке (1962); Марковица (1956); Тейла и ван де Панна; у Вольфа (1959). Задача нахождения глобального оптимума в КП рассмотрена в статьях Риттера (1965 и 1966). Влияние параметров и вопросы чувствительности исследованы Бутом (1963).

При несколько отличном подходе к КП, предложенном Лемке, условия Куна — Таккера непосредственно разрешаются с помощью алгоритма преобразования таблиц. Этот подход имеет интересное применение к играм; ом. Лемке; Лемке и Хоусои; и Коггл и Данциг.