Двойственный метод приведенного градиента в выпуклом программировании и порожденное им семейство алгоритмов

• Автор: Бакман, Ефим Гедалевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Луцк
• Количество страниц: 103 c. : ил

Глава I. Задача выпуклого программирования с линейными ограничениями

§1. Описание метода

§2. Обоснование метода

§3. Устойчивость метода .

§4. Вычислительные особенности

§5. Связь с другими методами

Глава II. Декомпозиция

§1. Декомпозиция задачи выпуклого программирования с блочной структурой ограничений

§2. Обобщённые верхние границы

§3. Метод подвижного базиса ц

Глава III. Задача квадратичного программирования . . . 5"5" §1. Применение прямых итеративных методов
для решения Р-задачи
§2. Применение прямых конечных методов для решения Р-задачи
§3. Применение двойственных итеративных методов
для решения Р-задачи
§4. Применение двойственного метода для решения
Р-задачи без обращения С
§5. Обсуждение
Глава IV. Численный эксперимент
§1. Описание эксперимента
§2. Обсуждение результатов эксперимента
Приложения
Литература

В последнее время методы решения прикладных задач развиваются особенно быстрыми темпами. И это неудивительно, так как применение математических методов в экономике часто приводит к большой экономии средств при незначительных дополнительных затратах. Так за последние 20 лет были разработаны эффективные методы решения оптимизационных задач /см. работы [у?35-31с_)52>5'3'3/. Полученные результаты используются при анализе, проектировании и планировании работы сложных систем
В настоящей диссертации предложен двойственный метод решения задач выпуклого программирования с линейными ограничениями, рассмотрены различные декомпозиционные подходы с использованием указанного метода. Метод детализируется для решения важной с точки зрения практического применения задачи квадратичного программирования. Потребность в эффективных методах подобного рода диктуется тем, что при использовании ряда методов выпуклого программирования на каждом шаге приходится решать задачу минимизации выпуклой функции при линейных ограничениях. Это прежде всего различные варианты методов возможных направлений, отсечения |^3 9 проекций градиента [ 46' ] . Процедура решения задач квадратичного программирования используется как подзадача во многих приложениях и поэтому должна решаться большое число раз Мц . В связи с этим эффективность метода имеет особую ценность [54,4-43^)
С самого начала мы хотели бы уточнить, что в настоящей работе будет пониматься под термином "двойственный ме-

тод". Этим термином мы обозначаем метод, допускающий отрицательность группы переменных задачи /называемых базисными переменными/. Процесс решения задачи заключается в продвижении от одного двойственно допустимого решения к друтому. Под двойственно допустимым решением понимается такое решение, для которого выполнены все условия оптимальности Куна-Танкера за исключением условия неотрицательности базисных переменных.
Впервые термин "двойственный метод" был введён Лемке [_■1CZ 3 для обозначения метода решения задач линейного программирования. йтот метод получил дальнейшее развитие в работах Вагнера для ограниченных сверху переменных и
Розена £ ]| для случая блочно-диагональной матрицы ограничений. Оригинальный подход для декомпозиции задачи линейного программирования предложил Озе ^/05" . Имеется много
различных модификаций перечисленных методов, их полное перечисление заняло бы слишком много места. Мы ограничились перечислением лишь тех работ, в которых двойственный метод был использован для решения задач линейного программирования со своей спецификой ограничений. К их числу относится таете работа £ 5" }, в которой двойственный метод применялся для решения задачи линейного программирования с обобщёнными верхними границами.
В противоположность задаче линейного программирования число работ, обобщающих двойственный метод на случай нелинейных целевых функций, совсем невелико. Первое описание обобщения двойственного метода линейного программирования на случай квадратичной целевой функции было опубликовано

Если 2. содержит отличное от нуля число у -переменных, то столько же х. -переменных стали базисными. Обозначим их число через ^ . ос -вектор базисных переменных
будем обозначать ХБ .Он образует подвижный, или П-ба-зис. Пусть зависимость от 2. выражена с помощью
соотношения
Зсє = с( - Р 2., /2>7
где ЛГр и с/ - -векторы, 2. - Л- -вектор переменных Р-задачи, Р -матрица м^х. ус.
Поиск отрицательной базисной переменной производится следующим образом: решив Р-задачу, её решение 2. подставляем сначала в /2.7/, находим ссБ- с{- РШ. Если существует ос.^ х О , то П-базис покинет ос -переменная. В противном случае переходим к Н-базису. Так как значения всех компонент вектора эс нам известны, можно вычислить у
= Ах., и, если существует < о , то базис покинет у -переменная. Если же отрицательных переменных нет ни в П- , ни в Н-базисе, то задача решена.
Таким образом, возможны следующие варианты смены базиса: если базис покидает х. -переменная, то сразу выполняем один шаг модифицированного жорданова исключения. При этом либо базисной становится ос -переменная, либо у -переменная.
Во втором случае образующаяся после жорданова исключения у -строка отбрасывается, так как П-базис не должен содержать у-переменных. Если базис покидает у-переменная, то формируется зависимость от 2 , что выполняется следующим образом: переменные сс^ просматриваются по очереди. Если очередная эс -переменная принадлежит П-базису, то из