Метод дополнительного базиса в квадратичном программировании тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РГБ ОД

(САНКТ-ПЕТЕРБУРГСКИЙ

,!> ГОСТДАРСТВЕНШа УНИВЕРСИТЕТ

На правах рукописи УДК 519.853.32

ТДРИК 1Ю1АМЫВД САЛИХ

Метод дополнительного базиса в квадратичном программировании

Специальность 01.01.09. - Математическая кибернетика.

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени кандидата 5изико-математических наук

Санкт-Петербург 1994

Работа выполнена на кафедре исследования операции математике-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель -- кандидат физико-математических наук, доцент

ДАУГАВЕТ В.А.

Офщиальяые оппонента - доктор физико-математических наук, профессор ФОМИН В.Н.

кандидат физико-математических наук,

доцент

ШВНЫЙ А.Б.

Ведущая организация - Санкт-Петербургское отделение математического института им. Стеклова

Защита состоится " 1994 г.

в ^^ часов на заседании специализированного Совета К .063.57 Л9 по присуждения ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Старай Петергоф, Библиотечная площадь, 2, математико-механический факультет.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного университета по адресу: 199034, С.-Петербург, Университетская набережная, 7/9.

Автореферат разослан *1Ь* НИЛРлдлы г.

УЧЕНЫЙ СЕКРЕТАРЬ специализированного Совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Диссертация посвящена разработке и обоснованию нового конечного метода ВКП - метода дополнительного базиса, предложенного руководителем. Этот метод универсален, он не требует приведения ограничений задачи к какой-либо стандартной форме, меняющего размеры задачи, и применим к любой задаче ЕКП:

К(х) «« ^ <х.Оя> ♦ <с.*> » И1П , (1)

* «ей

где

А1П, .щххсю г

хШ1

N1 г Ь1И4Л

N3 -

* © )

АЩ^.М]**!« - ЬСМ^ . |2>

»см.) г

От матрицы и требуется лишь симметричность и неотрицательная определенность, остальные параметры а, о, с - проиавольны.

Цель работы. Разработка метода дополнительного базиса (ДБ) по следующим направлениям.

1: Проведение полного обоснования метода. 2. Создание программ на ЭВМ (на языке Паскаль), использующих метод ДБ для решения задач ВКП: - обсей задачи;

- некоторых типовых задач;

- задач большой размерности о сильно разразреженными исходными матрицами.

3. Использование предлагаемых программных разработок в нелинейной оптимизации и для некоторых вариационных задач.

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

Научная новизна. В диссертации получены следущие результаты.

1. Приведено полное обоснование метода.

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

3. Разработан мультипликативный вариант алгоритма ДБ для задач ЕКП большой размерности с сильно разрешенными исходными матрицами. Для этого варианта написана и отлажена процедура гвя и решена вариационная задача на определение зоны контакта двух параллельных балок со свободной границей при различных нагрузках.

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

Аттобация работа и публикации. По результатам диссертации сделаны доклады на семинаре кафедры исследования операций и на семинаре по нелинейным экстремальным задачам при С.-Петербургском университете.

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

Структура и объем работа. Диссертация состоит из введения, двух глав (II параграфов), списка литературы и приложения. Объем диссертации - 91 страница основного текста и 39 страниц приложения. Список литературы содержит 46 наименований. В диссертации имеется 7 рисунков и 2 таблицы.

СОДЕРХЛНИВ РАБОТУ

Во введении дан краткий исторический обзор и сформулирован» основное результата диссертации.

Первая г.чэва посвядена вопросам теории. Предлагаемый метод решения задачи <х>-<2>, метод дополнительного базиса (ДБ), основан на решении системы Куна-Таккерз, которую можно записать в Еиде

H[P,PJ:.zCPJ - ЕСР.РЭ*УСРЭ « dtPl , <3)

VtPXPjJ » о . <4>

i © , yCP,J ÍO , (3)

ztPíxyCPl - О . (А)

Здесь еср,нз - единичная матрица, матрица и имеет структуру

IDtN.Nl -ATtN,nj

I ,

»tH.Nl ОЩ.Щ J

ГДе N-(l,..,n), М - (n«t,.. ,n*mj. Р ■ N UH ■ (1,..,п«), P^'J к, , dTCPl » (-cT£NJ, ЬТСН31.

Неизвестными являются itPi и ytpj. Если г.ср], y.tPi -решение системы и>-(ь>, то x.cni 1« 2.ini - решение исходной задачи <i>- <а>. Система Куна-Такхера, вообще говоря, нелинейна из-за равенства ió>, поэтому еэ решение вызывает затруднения. Будем искать решение система Кунз-Таккера среда базисных решения линейной системы <з>. Базис системы <з>, т.е. р (р = |н|> линейно независимых столбцов матрицы

[ Н[Р,РЭ, -EtP.PJ ] ,

будем фиксировать с помощью индексного множества

Q - I и J ,

где i •= н состоит из номеров базисных столбцов матрицы hcp.pj , а а ср - из номеров базисных столбцов матриш (-eip.pj».

Множество а также будем называть базисом. Базисное решение системы (1) определяется по правилу: »срчи » усрчл • о, а остальные компоненты определяются из системы

•ЦР.цхжси - ЕСР.ЛЯУСЛ - асрз .

Центральным моментом метода ДВ является идея Вулфа об использовании только дополнительных Оазисов системы <31, т.е. таких. Оазисов а - 1 и о, у которых множества I и л не имеют общих элементов. Ясно, что базисное реиение <*срэ, усрз» на дополнительном базисе а удовлетворяет нелинейному условию <м. Назовем дополнительный базис и экстремальным, если его базисное решение <*ср1, усрэ> удовлетворяет условиям (4) и (5).

Известно, что исходная задача <х)-<2> разрешима тогда и только тогда, когда система <з> имеет экстремальный базис. Доказательство этого утверждения приведено в § 2 диссертации.

Метод ДБ заклинается в упорядоченном переборе дополнительных базисов системы <з> или несколько расширенной системы (добавляется еще один искусственный столбец), пока не будет найден экстремальный базис. В качестве начального дополнительного базиса используются все р столбцов единичной матрица Далее, как в симплекс-методе для задач

линейного программирования, метод ДБ строит последовательность базисов

.....

по правилу

так что каждый следующий базис отличается от предыдущего одним столбцом. Для описания метода ДБ нужно лишь указать правило определения индексов 1к и рк в формуле <7), Метод разделяется на два этапа, в кавдом из которых правило выбора индексов 1к и йк свое.

Отметим те моменты, на которых основан выбор этих индексов.

На первом этапе ищется дополнительный базис системы »з», базисное реиение на котором удовлетворяет лишь условию (4». Как уже говорилось, в качестве исходного дополнительного базиса используется все столбцы матрицы »-еср.рл, т.е. оа - 10и а0, где 1 -в , л «н. На каждом шаге первого этапа делается

попытка заманить в текущем базисе ок столбец (-еср.л» с номером i из множества р\р, на столбец нср.л с тем же номером <. Если это удается сделать, то переменная уел становится небазисяой, т.е. равной нули. Алгоритм устроен так, что далее вектор (-EtP.il) для J « р\р4 в базис не включается, поэтому уСЛ-о на всех дальнейших итерациях метода. Может оказаться, что произвести замену столбца (-еср.л» на нср.л не удается, так как нср.л является линейной комбинацией столбцов матрицы нср.рчр^ уже находящихся в базисе. В этом случае обращаем внимание на базисную переменную усл. Если усл-о, то оставляем столбец (-еср.л> в базисе и переходим к испытанию следущего столбца <-еср,*]) с номером I « р\н1. Если кв оказалось, что у1Л*о. то система см-еи несовместна (см. § 5 диссертации), значит исходная задача не имеет решения и процесс прерывается.

Первый этап завершается за конечное число итераций. Пусть аи - оптимальный базис первого этапа. Если в нем остались столбцы (-€[р,л> с номерами % из рчн , то соответствующие им компонента *р1л-о.

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

На втором этапе к рассмотрению подключаются условия о». Пусть и - множество индексов * « р,. для которых < о

или у^си < о, а - номер минимальной из этих компонент. Если и пусто, то ир - 1ри - требуемый экстремальный оазис, а моо1-2 (ы] - решение исходной задачи. Если с не пусто, то в систему (3) вводится еде один искусственный столбец тср,о1, переменная *юз при котором "забирает" в себя всю отрицательность векторов ¿гср11 и у^ср,! . Искусственный столбец определяется следующим образом. Строится вектор ма^«

Г-:

если 1 « с 11113 "1 о , если 1 в с

Формируется базисная матрица

ТСР.О^Э 1« ^НСР.!,.), -еср.и^

и полагается

tcp.oj »- tip .о,, j » hta^.3 .

Переходная итерация метода заключается в замене базисного столбца TtP.Pj,! искусственным столбцом, т.е.

а - о и (о>\(р >

v+t V

(вектор tip,oj строить не надо, так как для процесса замены столбцов нужен лишь вектор коэффициентов разложения rtp.oj по базису который очевидно совпадает с htuu]). Новый базис и^ является дополнительным базисом расширенной системы

Н[Р,Р]*ЦР1 - EtP,PJ*ylP3 ♦ TCP,OJ*»t[OJ » в[Р1

при этом г ifз и VntPJ удовлетворяют условию <5), а

Второй этап заключается в переборе дополнительных базисов ufc расширенной систем, базисные решения tk, vk на которых удовлетворяют условиям <t>> и условию ыкюз г v. Перебор заканчивается тогда, когда искусственная переменная wkioj станет достаточно малой. Правило выбора индексов t>> здесь очень просто. Заметим, что в дополнительном базисе ок расширенной системы отсутствует ровно один индекс из и (на t^+i) итерации таким является индекс pt,). Чтобы следующий базис был дополнительным, в базис ot можно ввести только тот индекс, которого нет в ofe. Поэтому, если на к-ой итерации иэ базиса исключается столбец Htp,pkj, то на следующей итерации в базис вводится вектор (-ctp,pki) и наоборот.

Описание метода приводится в § 3.

В § 4 приводятся формулы численной реализации метода ДБ с использованием обратной базисной матрицы.

Б § 5 доказано, что метод ДБ конечен для любой задачи ВКП, т.е. за конечное число итераций, если исключить случай зацикливания, будет подучен результат.

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

§ 7 посвящен строго выпуклым задачам квадратичного программирования. Известно, что если матрица о в целевой функции положительно определена, то задача ЕНП сводится к другой задаче ВКП, в которой ограничения очень просты: все или часть переменных ограничены лишь знаком. Для задач ВКП с такими

ограничениями написана и отлажена процедура mdbi.

Особое внимание в диссертации уделено разработке алгоритма ДБ для задач Сольной размерности с сильно разреженными матрицами dcn.n] hacm.nj. Этому вопросу посвящен 5 8. Разработанный алгоритм использует известное мультипликативное представление обратной базисной матрицы. На основе этого алгоритма написана процедура гим на языке Паскаль. Процедура опробована на ряде примеров.

Вторая глава диссертации посвящена использованию метода ДВ в алгоритмах нелинейной оптимизации.

Для решения нелинейных задач чебншевской аппроксимации с линейными ограничениями

Ф(х> I' мах lfv(xl I - ain (81

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

Методам линеаризации и разработке этого варианта посвящен § I главы i1. Составлена программа для решения задачи (в) методом линеаризации, с помощью которой решена тестовая радиотехническая задача. Программа пригодна для решения любой задачи вида tu) с дифференцируемыми функциями т. i х >.

В 5 2 главы и показано, как возникают задачи ВКП в вариационных задачах. В частности, рассмотрена контактная задача для двух параллельных балок со свободной границей. Показано, как эта задача сводится к задаче ВКП, причем задача ВКП имеет большую размерность, а матрицы d и а сильно разрежены. Для решения этой задачи использовалась процедура гая, описанная в §8 главы i..С помощью этой процедуры решена указанная задача при различных нагрузках на балку.

Задача ВКП появляется как вспомогательная в методе наискорейшего спуска для решения нелинейных минимаксных задач с линейными ограничениями. На каадой итерации метода приходится определять расстояние от конуса до многогранника, натянутых на конечное число векторов. § 3 главы и посвящен решению этой

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

Все разработанные программы написаны на языке Паскаль. Тексты программ находятся в приложении к диссертации и на дискетах. -

Основное содержание диссертации опубликовано в работе:

Даугавет В.А., Салих Т.М. "О методе дополнительного базиса для задач выпуклого квадратичного программирования"// X. Вычисл. матем. и матем. <Хиз. 1992, Т.32, * 12, с. 1981-1992.