Содержание
Введение 3
Выпуклая квадратичная задача.................................. 3
Невыпуклая квадратичная задача при выпуклых ограничениях б Невыпуклая квадратичная задача с невыпуклыми квадратичными ограничениями........................................ 12
Эллипсоидальная аппроксимация множеств ...................... 16
1 Решение выпуклой квадратичной задачи с квадратичными ограничениями методом эллипсоидов 19
1.1 Построение эллипсоида наименьшего объема, содержащего
пересечение двух эллипсоидов ......................... 21
1.2 Построение эллипсоида наименьшего объема, содержащего эллипсоидный слой.................................... 24
1.3 Оценка сокращения объема при построении эллипсоидальной аппроксимации пересечения двух эллипсоидов....... 26
1.3.1 Имеющийся результат............................. 27
1.3.2 Оценка 1......................................... 28
1.3.3 Оценка 2......................................... 30
1.3.4 Оценка 3........................................ 31
1.3.5 Численное сравнение.............................. 35
1.4 Приведение пары квадратичных форм к диагональному виду в методе эллипсоидов............................ 36
1.5 Алгоритм решения выпуклой квадратичной задачи .... 39
2 Метод ветвей и границ для решения задачи минимизации квадратичной функции при выпуклых квадратичных ограничениях 43
2.1 Оценивание снизу ..................................... 44
2.2 Оценивание сверху..................................... 49
2.3 Процедура деления..................................... 54
2.4 Обоснование сходимости................................ 55
2.5 Оценка скорости сходимости.............................. 58
2.6 Алгоритм.............................................. 5 8
•2.7 Результаты численного тестирования...................... 61
3 Метод ветвей и границ для решения общей задачи квадратичного программирования 63
1
3.1 Оценивание снизу........................................ 63
3.1.1 Существование ограниченной внешней аппроксимации .................................................... 65
3.1.2 Максимизация минимального собственного числа . 68
3.1.3 Выбор внешней аппроксимации....................... 69
3.2 Оценивание сверху ...................................... 72
3.3 Процедура деления....................................... 78
3.3.1 Аппроксимация эллипсоидом......................... 78
3.3.2 Аппроксимация, сводимая к двуполостному гиперболоиду ............................................... 79
3.3.3 Аппроксимация однополостным гиперболоидом ... 87
3.4 Обоснование сходимости.................................. 88
3.5 Алгоритм................................................ 90
3.6 Результаты численного тестирования...................... 94
4 Заключение 95
2
Введение
Квадратичное программирование представляет собой один из важнейших разделов математического программирования. Большое количеством прикладных (технических и экономических) постановок сводятся к квадратичным оптимизационным задачам разной сложности. Квадратичные задачи возникают также и как вспомогательные в рамках методов решения более общих задач.
Задача квадратичного программирования в общем виде записывается следующим образом:
тій/(ж), ж Є С, (1)
/ /(ж) = х1С}[)х + сЬх, (2)
С = {х Є Еп : хт(ЗіХ 4- с^ж < г*, г = 1, ...,га}. (3)
Здесь С}і, с,-, і = 0,1,..., га, - соответственно симметричные матрицы и заданные векторы в пространстве Еп, г і Є {—1.0,1}.
Среди ограничений (3) как частный случай могут присутствовать и линейные. Если матрица С (0,..., га}, неотрицательно определена, а г» = 1, і Є {1,га}, то соответствующая квадратичная функция выпукла. Если это справедливо для всех г = 1, задача (1)-(3) относится к классу задач выпуклого программирования и решается за полиномиальное время. Если же не накладывается никаких ограничений на определенность матриц хотя бы только в (2) или в (3) или на значение правой части в (3), задача переходит в класс труднорешаемых — ОТ-трудных, и к ней требуется применять аппарат глобальной оптимизации.
Невыпуклое квадратичное программирование как область математического программирования переживает в настоящее время период активного развития. Обнаружена полиномиальная разрешимость отдельных классов задач квадратичного программирования. Для других классов разрабатывают варианты методов глобальной оптимизации, стремясь ускорить сходимость за счет учета специфики задачи. Имеются отдельные попытки адаптировать методы глобальной оптимизации и к задаче квадратичного программирования в се самой общей постановке.
Выпуклая квадратичная задача
Ряд выпуклых квадратичных задач возникает в экономике [48]. Например, пусть известно, что проданное количество с некоторого товара за-
3
висит от его цены х: с = ах + /3. Тогда доход, который следует максимизировать, есть квадратичная функция г = хс = ах2 + /Зх. Задача рационального распределения некоторого ресурса, количество которого ограничено, записывается как дискретная задача о рюкзаке, а она. в свою очередь, формулируется в виде непрерывной так называемой квадратичной задачи о рюкзаке [62].
Другая постановка касается теории портфельного инвестирования [48]. Некоторая инвестиционная компания располагает капиталом а, который может быть вложен в определенные тг проектов. Требуется решить, какую часть денег инвестировать в каждый из проектов. Пусть j = 1, ...,п — прибыль, которая приходится в 1юд на каждую денежную единицу, вложенную в. проект j. Будем считать yj нормально распределенными случайными величинами с известными (из анализа предшествующих данных) математическими ожиданиями д7- и матрицей ковариаций
п
Q = Задача менеджера, состоящая в максимизации дохода £
j=1
п
при минимизации общей дисперсии £ VijXiXj формулируется в виде:
tj=1
mm{oi\xTQx — а2ЦТх)\
п
Е xj < а, j=i
где ц = (д 1,..., дп)Г, a а\, — некоторые веса, выбираемые менеджером.
Первые результаты в области квадратичного программирования получены для выпуклой квадратичной задачи (1), (2), в которой допустимое множество представляет собой многогранник:
С = {х € Еп : Ах < Ь}
при заданных m х n-матрице А и m-векторе Ь. Для этой задачи в [22] описан конечный метод, реализующий некоторый направленный перебор. В качестве вспомогательной выступает задача безусловной минимизации выпуклой квадратичной функции. Есть также множество приближенных алгоритмов, полиномиальность которых не доказана, но которые демонстрируют высокую эффективность на практических задачах. Ссылки на работы, в которых приводятся такие методы, можно найти в [65].
Один из основных классов методов решения выпуклых квадратичных задач с линейными или квадратичными ограничениями — методы отсечений. Именно этому классу принадлежит метод эллипсоидов
4
Н.З.Шора |28| — первый алгоритм решения таких задач, для которого была доказана полиномиальная сходимость. Именно этот метод использовал Л.Г.Хачиян для доказательства полиномиальной разрешимости задачи линейного программирования. В работе [10] приводится вариант этого метода для задачи выпуклого квадратичного программирования с линейными ограничениями. Е.Г.Анциферовым [38] предложена модификация метода эллипсоидов, более эффективно, чем оригинальный метод, решающая выпуклую квадратичную задачу с квадратичными ограничениями. Идея состоит в замене отсекающего полупространства отсекающим эллипсоидом. К сожалению, на практике скорость сходимости метода эллипсоидов соответствует худшему случаю, для которого и получена оценка.
Другой класс составляют алгоритмы внутренних точек. Среди них имеются и аффинно-масштабируюгцие алгоритмы, разработанные И.И.Дикиным, В.И.Зоркальцевым |6|, Ю.Г.Евтушенко, В.Т.Жадапом [7,
8], и методы центрального пути, предложенные М.Коджимой, С.Мизуно, А.Йошиз [51], а также Р.Монтейро, И.Адлером [54]. В последних на каждой итерации используется метод Ньютона решения задачи штрафа. Независимо от этих авторов, Й.Йе предлагает свой алгоритм центрального пути [65] , сходимость которого несколько лучше. Этот метод решает на каждом шаге в качестве вспомогательной задачу оптимизации выпуклой квадратичной функции на шаре. В настоящее время эти методы продолжают активно развиваться, ведется поиск путей ускорения их сходимости.
Первоначально разработанные для минимизации выпуклой квадратичной функции на многограннике, они легко переносятся на задачу вида (1)-(3), в которой допустимая область задана выпуклыми квадратичными ограничениями.
Специально для задачи минимизации выпуклой квадратичной функции при двух выпуклых квадратичных ограничениях (т = 2) Я.Юань разработал алгоритм [69], который решает двойственную к исходной задачу максимизации вогнутой функции по двум переменным на неотрицательном ортанте. При этом используется метод Ньютона, поскольку градиент и гессиан целевой функции легко вычисляются. Метод сходится, если допустимое множество состоит более чем из одной точки. В противном случае решение двойственной задачи может быть неограничено. Приводятся результаты численных экспериментов для размерности 4.
5
Невыгтуклая квадратичная задача при выпуклых ограничениях
К задаче минимизации невыпуклой квадратичной функции при выпуклых ограничениях сводятся многие практические постановки. Например, модель распределительной электрической сети представляет собой систему квадратичных уравнений, описывающую баланс мощностей. Такая система может быть сведена к задаче вогнутого программирования [3], состоящей в отыскании точек глобального максимума выпуклой квадратичной функции на множестве, образованном выпуклыми квадратичными неравенствами.
Многие задачи дискретной оптимизации имеют эквивалентные постановки в классе непрерывных квадратичных задач. Булевы переменные могут быть представлены как непрерывные следующим образом: условие # € {0,1} эквивалентно неравенству х2—х > 0 в сочетании с включением х € [0,1].
Задачу о назначениях можно представить как задачу вогнутого программирования [48]:
пип хтС}х\ х €
где С) — отрицательно определенная симметричная матрица, допустимое множество П образовано линейными ограничениями.
Задача об упаковке эквивалентна задаче вогнутого программирования с параллслепипедными ограничениями [60]:
шах<; t— || Х{ - X] ||2< 0, 1 < г < .? < я, х* 6 [0,1], г = 1,..., я.
К задаче минимизации невыпуклой квадратичной функции на параллелепипеде
'Р 'Р о
тахх С^х — 2с х] хг <1, г = 1, ...,я .
сводится задача о максимальном сечении графа [64].
Задача об отыскании максимальной клики графа имеет непрерывную постановку в виде
/р
тахх Лсх; х € о,
где Ад — матрица инциденций заданного графа С, имеющая и положительные, и отрицательные собственные числа, 5 задано линейными ограничениями [48].
В общем случае отыскание глобального минимимума невыпуклой квадратичной функции при невыпуклых квадратичных (как частный случай, линейных) ограничениях есть НР-трудная задача [62]. Более того,
6
в этих условиях даже задача поиска локального минимума также принадлежит классу труднорешаемых задач. Это означает, что проверка, доставляет ли стационарная точка локальный оптимум целевой функции, не осуществима за полиномиальное время. Этот факт доказан для задачи минимизации квадратичной функции уже при линейных ограничениях в [55], а также в [62]. В последней работе С.Вавасис приводит необходимое и достаточное условие локального минимума в задаче на многограннике: оно заключается в отсутствии допустимого направления спуска в допустимой точке. Однако в более общей задаче минимизации квадратичной функции при квадратичных ограничениях этот критерий не действует. Например, в задаче
2 2 . 2 / 1 mm у — х ; х + у <1
допустимая точка (0,-1) не является точкой локального оптимума, хотя в ней не существует допустимого направления спуска.
Тем не менее, можно указать задачи данного класса, в которых локальный оптимум достигается за полиномиальное время. А именно, в |62] приведены полиномиальные алгоритмы, определяющие точки локального минимума в вогнутой и неопределенной квадратичных задачах о рюкзаке:
1 Ф 'Г
min -х их + с х\
А
т
а1 х = 7,
к < я* <щ, г = 1,..., п.
Здесь D — диагональная матрица, отрицательно определенная (тогда задачу называют вогнутой) или неопределенная, а, у, к> Щ, i =
— соответственно заданные n-вектор и числа.
Задачи глобальной минимизации невыпуклой квадратичной функции на множестве, заданном выпуклыми квадратичными или линейными ограничениями, выделяются из класса задач невыпуклой квадратичной оптимизации, хотя в большинстве своем остаются труднорешаемыми. Так, в [58] показано, что задача минимизации на многограннике квадратичной функции, в матрице которой присутствует хотя бы одно отрицательное собственное число, принадлежит числу NP-трудных задач, а точнее, NP-полных, поскольку в [62] показана принадлежность общей задачи квадратичной минимизации на многограннике классу NP. Это означает, что такая задача полиномиально разрешима, если P=NP. Также для задачи минимизации квадратичной функции на многограннике
7
- Київ+380960830922