Решение задач квадратичного программирования с помощью эллипсоидальных аппроксимаций допустимого множества тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Нечаева, Мария Станиславовна

• Нечаева, Мария Станиславовна
• кандидат физико-математических наук
• 2001

Оглавление диссертации кандидат физико-математических наук Нечаева, Мария Станиславовна

Введение

Выпуклая квадратичная задача.

Невыпуклая квадратичная задача при выпуклых ограничениях 6 Невыпуклая квадратичная задача с невыпуклыми квадратичными ограничениями.

Эллипсоидальная аппроксимация множеств

1 Решение выпуклой квадратичной задачи с квадратичными ограничениями методом эллипсоидов

1.1 Построение эллипсоида наименьшего объема, содержащего пересечение двух эллипсоидов

1.2 Построение эллипсоида наименьшего объема, содержащего эллипсоидный слой.

1.3 Оценка сокращения объема при построении эллипсоидальной аппроксимации пересечения двух эллипсоидов.

1.3.1 Имеющийся результат.

1.3.2 Оценка 1.

1.3.3 Оценка 2.

1.3.4 Оценка 3.

1.3.5 Численное сравнение.

1.4 Приведение пары квадратичных форм к диагональному виду в методе эллипсоидов.

1.5 Алгоритм решения выпуклой квадратичной задачи

2 Метод ветвей и границ для решения задачи минимизации квадратичной функции при выпуклых квадратичных ограничениях

2.1 Оценивание снизу

2.2 Оценивание сверху

2.3 Процедура деления.

2.4 Обоснование сходимости.

2.5 Оценка скорости сходимости.

2.6 Алгоритм.

•2.7 Результаты численного тестирования.

3 Метод ветвей и границ для решения общей задачи квадратичного программирования

3.1 Оценивание снизу

3.1.1 Существование ограниченной внешней аппроксимации

3.1.2 Максимизация минимального собственного числа

3.1.3 Выбор внешней аппроксимации.

3.2 Оценивание сверху

3.3 Процедура деления.

3.3.1 Аппроксимация эллипсоидом.

3.3.2 Аппроксимация, сводимая к двуполостному гиперболоиду

3.3.3 Аппроксимация однополостным гиперболоидом

3.4 Обоснование сходимости.

3.5 Алгоритм.

3.6 Результаты численного тестирования.

Введение диссертации (часть автореферата) на тему «Решение задач квадратичного программирования с помощью эллипсоидальных аппроксимаций допустимого множества»

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

Задача квадратичного программирования в общем виде записывается следующим образом: тт/(ж), х £ С, (1) ж) = хтд{)х -г с<5 ж, (2)

С = {хеЕп:хтС}{х + с[х'<Гг, г = 1 ,.,т}. (3)

Здесь Сг, г = 0,1,-- соответственно симметричные матрицы и заданные векторы в пространстве Еп, Г{ £ {—1, 0,1}.

Среди ограничений (3) как частный случай могут присутствовать и линейные. Если матрица £ {0,., т}, неотрицательно определена, а Гг = 1, г € {1,., т}, то соответствующая квадратичная функция выпукла. Если это справедливо для всех г = 1,., п, задача (1)-(3) относится к классу задач выпуклого программирования и решается за полиномиальное время. Если же не накладывается никаких ограничений на определенность матриц хотя бы только в (2) или в (3) или на значение правой части в (3), задача переходит в класс труднорешаемых — КР-трудных, и к ней требуется применять аппарат глобальной оптимизации.

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

Выпуклая квадратичная задача

Ряд выпуклых квадратичных задач возникает в экономике [48]. Например, пусть известно, что проданное количество с некоторого товара зависит от его цены х: с = ах + /3. Тогда доход, который следует максимизировать, есть квадратичная функция г -—— «Г С '— + (Зх. Задача рационального распределения некоторого ресурса, количество которого ограничено, записывается как дискретная задача о рюкзаке, а она, в свою очередь, формулируется в виде непрерывной так называемой квадратичной задачи о рюкзаке [62].

Другая постановка касается теории портфельного инвестирования [48]. Некоторая инвестиционная компания располагает капиталом а, который может быть вложен в определенные п проектов. Требуется решить, какую часть денег инвестировать в каждый из проектов. Пусть yj, j = 1, .,n — прибыль, которая приходится в год на каждую денежную единицу, вложенную в. проект j. Будем считать jjj нормально распределенными случайными величинами с известными (из анализа предшествующих данных) математическими ожиданиями щ и матрицей ковариаций п

Q = (сгу). Задача менеджера, состоящая в максимизации дохода Е f-ijXj э=1 п при минимизации общей дисперсии Е crijXiXj формулируется в виде: 1 mm(aixT Qx — a>2iiT х)] п

Е х3 < аэ 3=1 где fi= (/ii,., fin)T, a ai, «2 — некоторые веса, выбираемые менеджером.

Первые результаты в области квадратичного программирования получены для выпуклой квадратичной задачи (1), (2), в которой допустимое множество представляет собой многогранник:

С — {х £ Еп : Ах < 6} при заданных m х n-матрице А и m-векторе Ь. Для этой задачи в [22] описан конечный метод, реализующий некоторый направленный перебор. В качестве вспомогательной выступает задача безусловной минимизации выпуклой квадратичной функции. Есть также множество приближенных алгоритмов, полиномиальность которых не доказана, но которые демонстрируют высокую эффективность на практических задачах. Ссылки на работы, в которых приводятся такие методы, можно найти в [65].

Один из основных классов методов решения выпуклых квадратичных задач с линейными или квадратичными ограничениями — методы отсечений. Именно этому классу принадлежит метод эллипсоидов

Н.З.Шора [28] — первый алгоритм решения таких задач, для которого была доказана полиномиальная сходимость. Именно этот метод использовал Л.Г.Хачиян для доказательства полиномиальной разрешимости задачи линейного программирования. В работе [10] приводится вариант этого метода для задачи выпуклого квадратичного программирования с линейными ограничениями. Е.Г.Анциферовым [38] предложена модификация метода эллипсоидов, более эффективно, чем оригинальный метод, решающая выпуклую квадратичную задачу с квадратичными ограничениями. Идея состоит в замене отсекающего полупространства отсекающим эллипсоидом. К сожалению, на практике скорость сходимости метода эллипсоидов соответствует худшему случаю, для которого и получена оценка.

Другой класс составляют алгоритмы внутренних точек. Среди них имеются и аффинно-масштабирующие алгоритмы, разработанные И.И.Дикиным, В.И.Зоркальцевым [6], Ю.Г.Евтушенко, В.Т.Жаданом [7, 8], и методы центрального пути, предложенные М.Коджимой, С.Мизуно, А.Йошиз [51], а также Р.Монтейро, И.Адлером [54]. В последних на каждой итерации используется метод Ньютона решения задачи штрафа. Независимо от этих авторов, Й.Йе предлагает свой алгоритм центрального пути [65] , сходимость которого несколько лучше. Этот метод решает на каждом шаге в качестве вспомогательной задачу оптимизации выпуклой квадратичной функции на шаре. В настоящее время эти методы продолжают активно развиваться, ведется поиск путей ускорения их сходимости.

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

Специально для задачи минимизации выпуклой квадратичной функции при двух выпуклых квадратичных ограничениях (т = 2) Я.Юань разработал алгоритм [69], который решает двойственную к исходной задачу максимизации вогнутой функции по двум переменным на неотрицательном ортанте. При этом используется метод Ньютона, поскольку градиент и гессиан целевой функции легко вычисляются. Метод сходится, если допустимое множество состоит более чем из одной точки. В противном случае решение двойственной задачи может быть неограничено. Приводятся результаты численных экспериментов для размерности 4.

Невыпуклая квадратичная задача при выпуклых ограничениях

К задаче минимизации невыпуклой квадратичной функции при выпуклых ограничениях сводятся многие практические постановки. Например, модель распределительной электрической сети представляет собой систему квадратичных уравнений, описывающую баланс мощностей. Такая система может быть сведена к задаче вогнутого программирования [3], состоящей в отыскании точек глобального максимума выпуклой квадратичной функции на множестве, образованном выпуклыми квадратичными неравенствами.

Многие задачи дискретной оптимизации имеют эквивалентные постановки в классе непрерывных квадратичных задач. Булевы переменные могут быть представлены как непрерывные следующим образом: условие х £ {0,1} эквивалентно неравенству х2—х > 0 в сочетании с включением ж £ [0,1].

Задачу о назначениях можно представить как задачу вогнутого программирования [48]: пгл min ж Qx; х G О, где Q — отрицательно определенная симметричная матрица, допустимое множество Г2 образовано линейными ограничениями.

Задача об упаковке эквивалентна задаче вогнутого программирования с параллелепипедными ограничениями [60]: maxi; t— || Х{ — Xj ||2< 0, 1 < i < j < n, Xi G [0,1], i= 1,., n.

К задаче минимизации невыпуклой квадратичной функции на параллелепипеде гр гр . л тахх Qx— 2с х\ xi < 1, г — 1., п сводится задача о максимальном сечении графа [64].

Задача об отыскании максимальной клики графа имеет непрерывную постановку в виде m maxcc Aqx\ х G S, где Aq — матрица инциденций заданного графа G, имеющая и положительные, и отрицательные собственные числа, S задано линейными ограничениями [48].

В общем случае отыскание глобального минимимума невыпуклой квадратичной функции при невыпуклых квадратичных (как частный случай, линейных) ограничениях есть NP-трудная задача [62]. Более того, в этих условиях даже задача поиска локального минимума также принадлежит классу труднорешаемых задач. Это означает, что проверка, доставляет ли стационарная точка локальный оптимум целевой функции, не осуществима за полиномиальное время. Этот факт доказан для задачи минимизации квадратичной функции уже при линейных ограничениях в [55], а также в [62]. В последней работе С.Вавасис приводит необходимое и достаточное условие локального минимума в задаче на многограннике: оно заключается в отсутствии допустимого направления спуска в допустимой точке. Однако в более общей задаче минимизации квадратичной функции при квадратичных ограничениях этот критерий не действует. Например, в задаче min у — х2] х2 + у2 < 1 допустимая точка (0, —1) не является точкой локального оптимума, хотя в ней не существует допустимого направления спуска.

Тем не менее, можно указать задачи данного класса, в которых локальный оптимум достигается за полиномиальное время. А именно, в [62] приведены полиномиальные алгоритмы, определяющие точки локального минимума в вогнутой и неопределенной квадратичных задачах о рюкзаке: 1 Ф гр mm -х Dx + с х\ li т ах = 7, ъ ^^ j ^ — 1'э * * *)

Здесь D — диагональная матрица, отрицательно определенная (тогда задачу называют вогнутой) или неопределенная, а, 7, k, щ, i = 1,.,п, — соответственно заданные n-вектор и числа.

Задачи глобальной минимизации невыпуклой квадратичной функции на множестве, заданном выпуклыми квадратичными или линейными ограничениями, выделяются из класса задач невыпуклой квадратичной оптимизации, хотя в большинстве своем остаются труднорешаемыми. Так, в [58] показано, что задача минимизации на многограннике квадратичной функции, в матрице которой присутствует хотя бы одно отрицательное собственное число, принадлежит числу NP-трудных задач, а точнее, NP-полных, поскольку в [62] показана принадлежность общей задачи квадратичной минимизации на многограннике классу NP. Это означает, что такая задача полиномиально разрешима, если P=NP. Также для задачи минимизации квадратичной функции на многограннике показано [67]: существует константа е < 1/3 такая, что если только класс Р не совпадает с ИР, не существует полиномиального алгоритма, дающего решение х с оценкой

М < (1+ £)/*•

КР-полны также такие частные случаи, как минимизация на симплексе и при параллелепипедных ограничениях [62].

Поскольку задача оптимизации на многограннике представляет собой частный случай задачи оптимизации на множестве, заданном выпуклыми квадратичными ограничениями, последняя относится к классу трудных задач. Тем не менее, среди таких задач имеется по крайней мере одна, разрешимая за полиномиальное время — это задача минимизации невыпуклой квадратичной функции на шаре (при одном выпуклом квадратичном ограничении, т = 1). Другое свойство этой задачи состоит в том, что не более одного ее локального оптимума не является глобальным [47]. Предлагаемый в работе Йе [66] алгоритм находит точку глобального минимума, используя минимизацию по двойственной переменной.

Как мы увидим далее, рассматривая результаты, касающиеся общей задачи квадратичного программирования, задача с двумя выпуклыми квадратичными ограничениями [64] также полиномиально разрешима. Ее свойства и возможности алгоритмического решения исследовались Юанем в [68].

Задача оптимизации на шаре фигурирует в качестве вспомогательной в алгоритме, предложенном Йе для минимизации невыиуклой квадратичной функции при линейных ограничениях [66]. Метод принадлежит классу аффинно-масштабирующих методов внутренних точек.

Для задачи того же типа Бест и Динг [40] разработали метод декомпозиции, который заменяет исходную задачу несколькими меньшей размерности. Число подзадач в общем случае равно числу ограничений в исходной. Повторяя процедуру последовательно, размерность доводят до единицы, и каждая подзадача решается аналитически. В статье приводится также способ сокращения количества подзадач и численные примеры для размерности 3.

В [48]разрабатывается подход к квадратичной минимизации на многограннике, основанный на представлении целевой функции в виде разности двух выпуклых квадратичных функций и последующей кусочно-линейной аппроксимации вогнутой части.

Многими авторами рассматривалась невыпуклая квадратичная задача (1), (2) с параллелепипедными ограничениями:

С = {х е Еп : li < Xi < = 1, .,n} для некоторых чисел k, щ, г = 1 ,.,п. NP-трудность этой задачи была показана в [55]. Данг и Ксю [43] предложили для этой задачи метод внутренних точек, решающий на каждой итерации задачу на минимум барьерной функции. Начальное значение барьерного параметра выбирается достаточно большим, чтобы барьерная функция была выпукла. При уменьшении параметра барьерная функция приближается к целевой в исходной задаче, и на этом пути существуют значения барьерного параметра, при которых каждая точка локального минимума барьерной функции близка к точке глобального оптимума в исходной задаче. Доказана сходимость метода к стационарной точке исходной задачи. Сходимость к точке глобального оптимума теоретически обосновать не удалось, хотя в численных экспериментах всегда наблюдалась именно такая тенденция, если барьерный параметр уменьшался достаточно медленно.

Для невыпуклой квадратичной задачи с параллелепипедными ограи ничениями Ие разработал алгоритм, основанный на технике полуопределенного программирования, причем уже за полиномиальное время он дает приближенное решение х, обладающее свойством: ~ № 4

-/* -Г

Целая серия подходов к задаче с параллелепипедными ограничениями описана в статье [36]. Здесь авторы сначала приводят обзор некоторых свойств стационарных точек и различных критериев глобального оптимума. Далее описаны идеи следующих методов решения рассматриваемой задачи. Метод И.Бомзе и Г.Даннингер основан на условии глобальной оптимальности, которое состоит в проверке матрицы на копо-зитивность (матрица копозитивна на множестве, если образует на нем неотрицательную квадратичную форму). Поскольку такая проверка NP-полна, для задач не самой маленькой размерности более полезна эвристика, основанная на условии копозитивности и позволяющая выходить из точки локального оптимума в точку с лучшим значением целевой функции. Метод внутренних точек Хана, Пардалоса и Йе решает на каждом шаге задачу минимизации невыпуклой квадратичной функции на эллипсоиде, вписанном в допустимую область, и таким образом строит последовательность допустимых решений. Доказана только локальная сходимость метода, но с его помощью можно получить хорошую стартовую точку для других методов. Другие методы состоят в решении серии линейных или выпуклых задач, последовательно аппроксимирующих исходную, или в решении последовательности задач безусловной минимизации штрафной функции.

Популярный подход к решению задач глобальной минимизации, реализующий направленный перебор, представляют так называемые методы "ветвей и границ", идея которых состоит в последовательном разбиении допустимой области на подмножества и отборе из них перспективных по критерию наилучшей оценки снизу оптимального значения целевой функции. В [36] описаны алгоритмы ветвей и границ, предложенные П.Пардалосом и П.Хансеном для задачи с параллелепипедными ограничениями. Первый основан на представлении произвольной квадратичной функции в виде разницы двух выпуклых квадратичных функций; в другом разбиение и ветвление осуществляются с помощью критерия локальной оптимальности, и определяющими факторами служат знаки первой и второй производных целевой функции.

Подход, связанный с полуопределенным программированием, широко распространен при решении невыпуклых квадратичных задач. Задачей полуопределенного программирования называют задачу минимизации линейной функции от матричной переменной при условии ее неотрицательной определенности. Такая задача разрешима за полиномиальное время, например, прямо-двойственным методом внутренних точек [56]. Разработаны также методы, в частности, основанные на идее отсечений, использующие разреженность или другие особенности матрицы, фигурирующей в постановке [45]. Между тем, Н.З.Шор и соавторы [33] считают более целесообразным решать задачи полуопредленного программирования методами негладкой оптимизации.

Оказывается, двойственная к задаче квадратичного программирования эквивалентна некоторой задаче полуопределенного программирования. Если в исходной задаче имеется разрыв двойственности, решение задачи полуопределенного программирования дает оценку снизу оптимального значения целевой функции, а при отсутствии разрыва двойственности невыпуклая квадратичная задача решается за полиномиальное время, и такое свойство называют скрытой выпуклостью. В связи с этим, важно определить классы задач квадратичного программирования, в которых разрыв двойственности равен нулю. Признаком отсутствия разрыва двойственности в задаче полуопределенного програмжирования является, например, существование точки Слейтера в ее допустимой области. Критерии существования точки Слейтера в задачах полуопределенного программирования исследованы Л.Тунселом в [61].

В [67] для задачи оптимизации невыпуклой квадратичной функции при выпуклых квадратичных ограничениях Йе предлагает полиномиальный алгоритм, основанный на теории полуопределенного программирования. Результатом работы является случайная точка, допустимая с вероятностью 1, для которой известна оценка близости математического ожидания значения целевой функции к оптимальному значению в задаче, и такая оценка является наилучшей среди известных оценок, получаемых за полиномиальное время.

Шор предлагает для задачи того же типа метод ветвей и границ [25], [29]. Для получения нижней оценки оптимального значения целевой функции автор использует теорию двойственности, причем показано, при каких условиях оценка совпадает с искомым оптимумом.

И.Новак в работе [57] продолжает исследовать возможности применения к задачам того же типа метода ветвей и границ глобальной оптимизации. Нижняя оценка оптимального значения целевой функции представляет собой двойственную оценку, полученную в результате решения задачи полуопределенного программирования. Оценка может быть улучшена путем добавления во вспомогательную задачу избыточных линейных ограничений. Для достаточно малых элементов разбиения указывается, добавление каких именно избыточных ограничений вообще уничтожает разрыв двойственности. Автор также предлагает эвристику, которая с помощью процедуры локального спуска для каждого элемента разбиения допустимой области строит отсечение, обеспечивающее сходимость за конечное число шагов. Отдельно рассматривается применение этого метода к квадратичным задачам на симплексе и на параллелепипеде.

Задачу оптимизации квадратичной функции на симплексе называют стандартной задачей квадратичного программирования, и она также ИР-трудна. Для нее в [41] авторы предлагают подход, связанный с копозитивным программированием вместо полуопределенного. Подход состоит в замене исходной задачи задачей оптимизации на конусе ко-позитивных на положительном ортанте матриц. Такая задача решается прямо-двойственным методом внутренних точек. Кроме того, метод комбинируется с алгоритмом, обеспечивающим спуск в точку локального минимума, а также с аффинно-масштабирующей процедурой выхода из точки локального, но не глобального минимума в допустимую точку с лучшим значением целевой функции.

Невыпуклая квадратичная задача с невыпуклыми квадратичными ограничениями

Для задачи минимизации квадратичной функции при произвольных квадратичных ограничениях при помощи лагранжевой релаксации также может быть получена нижняя оценка оптимального значения целевой функции. Для решения соответствующей задачи полуопределенного программирования может быть использован метод внутренних точек, как предлагает Г.Волкович [64]. С другой стороны, в работах [30]—[33] исследуются алгоритмы построения двойственных оценок, основанные на методах негладкой оптимизации. Показано, что добавление в формулировку задачи избыточных ограничений приводит к улучшению оценки, вплоть до совпадения ее с оптимальным значением задачи. Рассмотрен ряд булевых комбинаторных задач, которые могут быть переформулированы как задачи непрерывного квадратичного программирования. Среди них задача о максимальном взвешенном независимом множестве вершин графа, о максимальном разрезе графа, об оптимальной бисекции графа. Приводятся алгоритмы получения эффективных нижних оценок в этих задачах. Введением новых переменных и подходящих ограничений можно понизить степень любого полинома до квадрата, поэтому предложенная техника дает возможность оценивать снизу глобальный минимум полиномиальной функции.

Ириарт-Уррути в [47] формулирует необходимые и достаточные условия глобального минимума в задаче минимизации невыпуклой квадратичной функции при одном и двух невыпуклых квадратичных ограничениях при соблюдении условий регулярности. Сначала рассматривается задача при одном квадратичном ограничении-равенстве: (1), (2) при

С = {х в Еп:{х- х1)т<31{х - х1) = п}.

В этой задаче допустимая точка х доставляет глобальный оптимум в том и только том случае, если существует число Л такое, что а) - х°) + ЛфДж - ж1) = 0;

Ь) (¿о + Лфхнеотрицательно определена.

Таким образом, к обычному условию Лагранжа добавляется требование Н

Например, рассмотрим задачу: найти наименее удаленную от точки а = (1,0) точку, удовлетворяющую условию х2 — у2 = 4. Задача записывается в виде: тт(х - I)2 + у2- х2 -у2 = 4, пои имеет две точки, для которых выполняется условие Лагранжа (а):

2,0) с множителем — 1/2; (—2,0) с множителем — 3/2.

Г 1/2 0

Условие (Ь) справедливо только для точки (2,0): матрица ^ ^ ложительно определена; эта точка и есть решение задачи. Для задачи (1), (2) с одним ограничением-неравенством:

С = {х £ Еп : (х - х1)Тдг{х - х1) < п}, имеется следующий результат. Допустимая точка х доставляет глобальный оптимум в том и только том случае, если существует число Д такое, что а/ Яо(х - х°) + ^г(х - х1) = 0; а)" Д((® - х^Я^х - ж1) - п) = 0;

Ъ)' Яо + Афзнеотрицательно определена.

В качестве примера рассматривается задача: найти наименее удаленную от точки а = (1,0) точку множества {(х,у) : ж2+ 4у2 > 4}. В задаче имеется четыре точки Куна-Таккера:

2,0) с множителем 1/2;

2,0) с множителемЗ/2; с множителем 1. о о

В первых двух точках условие (Ь)' не выполняется, зато оно справедливо для двух последних точек, которые и дают решение задачи.

Для задачи с двумя квадратичными ограничениями-неравенствами

4,(2),

С = {х е Еп : дг{х) = (х - хУЯ^х - х1) - п < 0,

92 (®) = (х - х2)т02(х - х2) - г2 < 0} необходимое и достаточное условия глобального оптимума выглядят так.

Если х - глобальный оптимум задачи, причем оба ограничения активны в этой точке, а градиенты Уд^ж) и У<?2(ж) линейно независимы, то существуют числа Д 1 > 0, Д2 > 0 такие, что

Я о (ж - ж0) + ¡¿{Уд^х) 4- р2^92{х) = 0; имеет не более одного отрицательного собственного числа.

Если только одно, например первое, ограничение активно в х, то из необходимого условия локального оптимума второго порядка получаем: существует число Дх > 0 такое, что

Яо{х - х°) + ¡Х1^д1(х) = 0;

Я о + Ц1Я1 имеет не более одного отрицательного собственного числа.

Если для допустимой точки х существуют числа Дх > 0, Д2 > 0 такие, что

Яо{х - х°) 4- ЦгУд^х) + Д2У#2Й = 0;

Дтй = Р>292{х) = 0;

Яо + ДА + Д2^2 положительно определена, то х — точка глобального оптимума.

В состав необходимых и достаточных условий глобального оптимума входят разные свойства гессиана функции Лагранжа. Например, рассмотрим задачу пип(ж — I)2 4-у2 — 6х — Юг2; х2 + у2 + < 2, (х - 2)2 4- у2 + г2 < 2.

Здесь точка (1,1,0) удовлетворяет необходимым условиям глобального оптимума с множителями Д1 = Д2 •= 1, гессиан функции Лагранжа равен 6 — 16} и имеет одно отрицательное собственное число. Однако точка не доставляет даже локального минимума, так как в ней существует направление, вдоль которого функция убывает: < 0 при е = 0, х£ — (1,1 — е, \]е(2 — е)).

Задача минимизации квадратичной функции при одном квадратичном ограничении вообще является наиболее исследованной в классе. Она обнаруживает отсутствие разрыва двойственности, и поэтому решается за полиномиальное время. Другая квадратичная задача с тем же свойством возникает при необходимости учесть в задаче минимизации квадратичной функции только условие ортогональности векторов переменных: ХТХ = I [37]. В этой же работе показаны возможности применения этой легкорешаемой задачи в качестве вспомогательной при решении других классов невыпуклых квадратичных задач.

Согласно результату, приведенному Б.Т.Поляком в [59], разрыв двойственности отсутствует и в задаче минимизации квадратичной функции при двух квадратичных ограничениях, если существует положительно определенная линейная комбинация матриц, задающих ограничения. Как мы увидим в разделе 3.1, последнее требование выполняется, если допустимое множество в такой задаче ограничено. Для решения задачи с двумя ограничениями, когда разрыв двойственности отсутствует, или же для нахождения оценки снизу оптимального значения в [59] предлагается решать двойственную задачу, которая представляет собой задачу линейного программирования с матричными ограничениями-неравенствами.

В [52] рассматривается задача аппроксимации невыпуклого множества, заданного конечным или бесконечным числом квадратичных ограничений, множеством, определенным при помощи выпуклых квадратичных ограничений. При этом используются методы полуопределенного программирования применительно к общей невыпуклой задаче квадратичного программирования с бесконечным числом линейных ограничений. Аппроксимация достигается последовательными приближениями, монотонно сходящимися по включению к выпуклой оболочке исходного множества.

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

Варианты метода ветвей и границ предлагались, например, в работах [34], [60]. В первой из них используется разбиение допустимой области на параллелепипеды, а метод, изложенный У.Рабером во второй, использует разбиение на симплексы и для построения оценок заменяет квадратичную задачу задачей линейного программирования. Сравнение этих двух близких методов на тестовых примерах размерности п до 8 и с числом квадратичных ограничений до 2п показало, что если число ограничений мало по сравнению с размерностью, то метод, основанный на паралле-лепипедных разбиениях, в большинстве случаев находит приближенное решение быстрее, чем использующий деление на симплексы. И наоборот, при сравнительно большом числе ограничений метод Рабера работает быстрее на подавляющем большинстве задач.

Невыпуклая квадратичная задача находит свое применение и в методах двухуровневого программирования. Классический прием решения двухуровневой задачи оптимизации — замена задачи второго уровня ее равенствами Куна-Таккера, если только они оказываются необходимыми и достаточными условиями оптимума. В полученной задачи усложняющим элементом является условие дополняющей нежесткости, которое можно заменить невыпуклыми квадратичными ограничениями и таким образом получить задачу минимизации квадратичной функции на множестве, заданном невыпуклыми квадратичными ограничениями [35]. В экономических иерархических постановках распространенным случаем является задача с вогнутой целевой функцией верхнего уровня, которая сводится к задаче минимизации вогнутой функции при невыпуклых квадратичных ограничениях. Эта же формулировка соответствует и прикладным проблемам размещения, планирования производства и минимизации рисков. Для решения этой задачи в [35] предложен алгоритм ветвей и границ, использующий разбиение на симплексы, а в качестве нижней оценки — минимум вогнутой функции на множестве вершин симплекса. Оценка может быть улучшена за счет линеаризации квадратичных ограничений, фигурирующих в задаче.

Эллипсоидальная аппроксимация множеств

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

Задачи внутренней аппроксимации различных выпуклых областей множествами простой структуры не только используются в качестве вспомогательных в методах математического программирования. Они имеют самостоятельное значение в приложениях, когда требуется найти не один, а множество планов, близких к оптимальному, причем это множество должно быть просто с точки зрения технологического контроля. В сообщении [4] приводится общий подход к представлению геометрической задачи о внутренней аппроксимации шаром в произвольной норме в виде задачи математического программирования. Именно, рассмотрим непрерывное отображение д : Rn —Rm и множество G = {х G К1 : д(х) < 0}. Фиксировав в Rn некоторую норму, обозначим В (у,г) = {х е Rn : \\х — у || < г}. Для каждого i — 1, .,п положим

Ni= sup {gi(x) - gi(y)), i = 1, .,ra, xeB(y,r)

N(y,r) = (N1(y,r),.,Nm(y,r)f. Если в решении у*, г* задачи математического программирования шах г; д(у) + N(y, г) < 0, г > 0 г* > 0, то шар В(у*,г*) является в данной норме максимальным шаром, вписанным в G. Задача внутренней аппроксимации многогранного множества не просто шаром в евклидовой норме, а эллипсоидом максимального объема рассматривалась, например, в [27], [50].

О задаче внешней аппроксимации множеством простой структуры можно сказать то же самое: она встречается и в приложениях, и как вспомогательная в итерационных методах. Такой прием рассматривается в контексте выпуклого квадратичного программирования: в классе методов отсечений [28] фигурирует задача внешней аппроксимации многомерным эллипсоидом области, представляющей собой пересечение двух эллипсоидов. Критерием качества аппроксимации служит величина объема аппроксимирующего эллипсоида.

Задача построения эллипсоида минимального объема, содержащего пересечение двух заданных эллипсоидов, имеет единственное решение [9]. Соответствующие численные методы исследовались многими авторами, в частности, в связи с аппроксимацией множеств достижимости и областей неопределенности эллипсоидальными областями [24], [18].

Оптимальный эллипсоид может быть найден методом покоординатного спуска, предлагаемым в [18]. В [63] задача определения эллипсоида наименьшего объема, содержащего выпуклое множество, сводится к выпуклой задаче полуопределенного программирования, решаемой за полиномиальное время методами внутренних точек.

С целью уменьшения трудоемкости можно ограничиться квазиоптимальными методами. Так, Ф.Л.Черноусько [24] предлагает аппроксимировать один из эллипсоидов, участвующих в пересечении, полупространством и воспользоваться известной схемой [28] погружения полуэллипсоида в эллипсоид минимального объема, которая используется в методе эллипсоидов решения выпуклых задач математического программирования. В работе [20] приводится точное решение задачи о построении эллипсоида наименьшего объема, содержащего пересечение двух заданных эллипсоидов, связанных подобием, и исследуемая задача сводится к погружению в эллипсоид минимального объема пересечения двух подобных эллипсоидов. Доказывается и демонстрируется на примере преимущество такого способа аппроксимации перед предложенным в [18].

Особый интерес представляет другой квазиоптимальный способ, который состоит в использовании линейной комбинации (иначе говоря, смеси) исходных эллипсоидов с некоторыми неотрицательными коэффициентами. В работе [24] Черноусько строит линейную смесь эллипсоидов с фиксированными весами, а в [18] авторы идут дальше, указывая на возможность подбора оптимальных в смысле объема коэффициентов смеси, не предлагая, впрочем, эффективного алгоритма решения этой задачи. Эллипсоид, полученный смешиванием, в общем случае не является оптимальным по объему. В [18] указаны немногие частные случаи, когда эллипсоид минимального объема, содержащий пересечение двух эллипсоидов, оказывается смесью, однако эти результаты, к сожалению, не могут иметь отношения к той специфической задаче, которая фигурирует в методах отсечений. Тем не менее, имеются еще возможности, оставаясь в рамках описанного в [24] подхода, улучшить погружение. Так, Е.Г.Анциферов в [1], [38] предлагает строить требуемый эллипсоид в виде линейной комбинации исходных эллипсоидов и некоторой полосы, содержащей их пересечение. Включение в смесь нового объекта — полосы — в большинстве случаев оказывается существенным для улучшения аппроксимации.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Нечаева, Мария Станиславовна

Основные результаты диссертации состоят в следующем.

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

2. Исследованы геометрические свойства множеств в п-мерном пространстве, каждое из которых образовано одним квадратичным ограничением определенного вида.

3. Выполнено обобщение способа построения внешней эллипсоидальной аппроксимации пересечения двух эллипсоидов путем линейного комбинирования неравенств. В результате получены: а) метод погружения неограниченного множества, определенного любыми квадратичными неравенствами, в эллипсоид наименьшего объема или, если последнее невозможно, неограниченную область, заданную одним квадратичным ограничением с наибольшим минимальным собственным числом в матрице; b) метод внутренней аппроксимации пересечения конечного числа эллипсоидов эллипсоидом возможно большего объема; c) для некоторых случаев метод внутренней аппроксимации неограниченной области, определенной квадратичными неравенствами, множеством, заданным одним квадратичными ограничением.

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

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

4 Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Нечаева, Мария Станиславовна, 2001 год

1. Анциферов Е.Г. К методу эллипсоидов в выпуклом программировании // Численные методы анализа и их приложения. Иркутск: Сибирский энергетический ин-т СО АН СССР, 1987.

2. Анциферов Е.Г., Ащепков Л.Т., Булатов В.П. Методы оптимизации и их приложения. 4.1. Математическое программирование. Новосибирск: Наука, 1990.

3. Анциферов Е.Г., Тарасов В.И. К решению систем квадратичных уравнений, моделирующих распределение нагрузок в электрических сетях // Известия вузов. Математика, 1994, N0 12, с.8-19.

4. Ащепков Л.Т. О построении максимального куба, вписанного в заданную область // Журнал вычислительной математики и математической физики, 1980, т.20, N0 2, с.510-512.

5. Беллман Р. Введение в теорию матриц. М.: Наука, 1969.

6. Дикин И.И., Зоркальцев В.И. Итеративное решение задач математического программирования: алгоритмы метода внутренних точек. Новосибирск: Наука. Сиб. отд-ние, 1980.

7. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982.

8. Евтушенко Ю.Г., Жадан В.Г. Двойственные барьерно-проективные и барьерно-ньютоновские методы для задач линейного программирования // Журнал вычислительной математики и математической физики, 1996, т.36, N0 7, с.30-45.

9. Загускин В.Л. Об описанных и вписанных эллипсоидах экстремального объема // Успехи математических наук, 1958, т. 13, N0 6(84), с.89-93.

10. Козлов М.К., Тарасов С.П., Хачиян Л.Г. Полиномиальная разрешимость задач выпуклого квадратичного программирования // Доклады АН СССР, 1979, N0 5, с.1051-1053.

11. И. Маркус М., Минк X. Обзор по теории матриц и матричных неравенствам.: Наука, 1972.

12. Нечаева М.С. Оценка эффективности одной модификации метода эллипсоидов решения выпуклой полно-квадратичной задачи / Материалы XXVI конференции научной молодежи СЭИ СО РАН. Иркутск, 24 апреля 1996, с. 78-92. Деп. в ВИНИТИ 8.07.96, N 2194-В96.

13. Нечаева М.С. К оценке сокращения объемов при построении наилучшей эллипсоидальной аппроксимации пересечения двух эллипсоидов // Известия РАЕН, серия МММИУ, 1997, т.1, No 4, с.138-144.

14. Нечаева М.С. Решение выпуклой полной квадратичной задачи методом эллипсоидов. — Препринт, Иркутск: ИСЭМ СО РАН, 1998, 26 с.

15. Нечаева М.С., Хамисов О.В. Алгоритм решения невыпуклой квадратичной задачи, использующий полиномиальную оптимизацию на эллипсоиде // Дискретный анализ и исследование операций, серия 2, 2000, т. 7, No 2, с. 74-88.

16. Нечаева М.С. Метод ветвей и границ для решения общей задачи квадратичного программирования / Труды Байкальской международной конференции Методы оптимизации и их приложения, т.1, Иркутск: ИСЭМ СО РАН, 2001, с.276-281.

17. Овсеевич А.И., Решетняк Ю.Н. Аппроксимация пересечения эллипсоидов в задачах гарантированного оценивания / / Техническая кибернетика, 1988, No 4.

18. Парлетт Б. Симметричная проблема собственных значений. Численные методы. М.: Мир, 1983.

19. Покотило В.Г. К проблеме аппроксимации пересечения эллипсоидов // Техническая кибернетика, 1990, No 3.

20. Поляк Б.Т. Введение в оптимизацию. — М.: Наука, 1983.

21. Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

22. Уилкинсон Дж.Х. Алгебраическая проблема собственных значений. М.: Наука, 1970.

23. Черноусько Ф.Л, Оптимальные гарантированные оценки неопределенностей с помощью эллипсоидов. Часть II // Техническая кибернетика, 1980, N4.

24. Шор Н.З. Об одном подходе к получению глобальных экстремумов в полиномиальных задачах математического программирования // Кибернетика, 1987, No 5, с. 102-106.

25. Шор Н.З. Квадратичные оптимизационные задачи // Техническая кибернетика, 1987, No 1, с. 128-139.

26. Шор Н.З., Березовский O.A. Использование алгоритма субградиентного типа с растяжением пространства для построения эллипсоида максимального объема, вписанного в многогранник // Кибернетика 1989, No 6, с.119-120.

27. Шор Н.З., Гершович В.И. Об одном семействе алгоритмов для решения задач выпуклого программирования // Кибернетика, 1979, No 4.

28. Шор Н.З., Стеценко С.И. Квадратичные экстремальные задачи и недифференцируемая оптимизация. Киев: Наукова Думка, 1989.

29. Шор Н.З. Роль избыточных ограничений в улучшении двойственных оценок для полиномиальных оптимизационных задач // Кибернетика и системный анализ, 1998, No 4, с.106-121.

30. Шор Н.З., Стецюк П.И. Использование модификации г-алгоритма для нахождения глобального минимума полиномиальных функций // Кибернетика и системный анализ, 1987, No 4, с.28-49.

31. Шор Н.З., Стецюк П.И. Использование r-алгоритма в задачах полуопределенного программирования / Труды международной конференции "Питания оптим1зацш обчислень", Киев, 1997, с.330-335.

32. Шор Н.З., Стецюк П.И,, Крылов C.B. Нахождение глобальных минимумов полиномиальных функций с использованием двойственных квадратичных оценок // Вестник Международного Соломонова университета, 2000, No 4.

33. Al-Khayyal F., Faiz A., Larsen C., and Van Voorhis T. A Relaxation Method for Nonconvex Quadratically Constrained Quadratic Programs // Journal of Global Optimization 1995, No. 6, p.215-230.

34. Al-Khayyal F., Horst R., and Pardalos P. Global Optimization of Concave Functions Subject to Quadratic Constraints: an Application in Nonlinear Bilevel Programming, Preprint, Department of Computing Science, Pennsylvania State University, 1990.

35. Angelis P., Pardfalos P., and Toraldo G. Quadratic Proghramming with Box Constraints, in Developments in Global Optimization, Kluwer Academic Publishers, 1997.

36. Anstreicher K. and Wolkowicz H. On Lagrangian Relaxation of Quadratic Matrix Constraints SI AM Journal of Matrix Anal. Appl. 2000, Vol.22, No 1, p.41-55.

37. E.Antsiferov and V.Bulatov, New Mathematical Programming Algorithms and Their Applications to Energy Problems, Harwoord Academic Publishers ltd., 1992.

38. Avriel M, Diewert W., Schaible S., and Zang I. Generalized Concavity. Plenum Press, New-York, 1988.

39. Best M. and Ding B. A Decomposition Method for Global and Local Quadfratic Minimization // Journal of Global Optimization 2000, Vol. 16, No. 2, p. 133-151.

40. Bomze I. On Standard Quadratic Optimization Problems // Journal of Global Optimization 1998, Vol. 13, No. 4, p.369-387.

41. Brooke A., Kendrick D., and Meeraus A. GAMS. Release 2.25. A User's Guide. GAMS Development Corporation, 1996.

42. Dang Ch. and Xu L. A Barrier Function Method for the Nonconvex Quadfratic Programming Problem with Box Constraints // Journal of Global Optimization 2000, Vol. 18, No. 2, p.165-188.

43. Floudas C.A., Visweswaran V. Quadratic Optimization // Handbook of Global Optimization. Ed. Horst R. and Pardalos P. Dordrecht, Netherlands: Kluwer Academic Publishers, 1995, p.217-270.

44. Goffin J.-L., Haurie A., and Vial J.-P. Decomposition and Nondifferentiable Optimization with the Projective Algorithm // Management Science 1992, No. 38, p.284-302.

45. Hansen P. and Jaumard B. Reduction of Indefinite Quadratic Programs to Bilinear Programs // Journal of Global Optimization 1992, Vol. 2, No. 1, p.41-60.

46. Hiriart-Urruty J.-B. Conditions for Global Optimality 2 // Journal of Global Optimization 1998, Vol.13, N4, p.349-367.

47. Horst R., Tuy, H. Global Optimization. Deterministic Approaches. Springer-Verlag, 1993.

48. Jarre F. Interior-Point Methods for Classes of Convex Programs, in Interior Point Methods of Mathematical Programming, Kluwer Academic Publishers, 1996, p.255-296.

49. Khachiyan L., Todd M. On the Complexity of Approximating the Maximal Inscribed Ellipsoid for a Polytope // Mathematical Programming 1993, N61, p.137-159.

50. Kojima M., Mizuno S., and Yoshise A. A Polynomial-Time Alghorithm for a Class of Linear Complementarity Problems // Mathematical Programming 1989, No 44, p.1-26.

51. Kojima M. and Tuncel L. Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets // SIAM Journal of Optimization 2000, vol.10, No 3, p.750-778.

52. Mokhtarian F. and Goffin J.-L. An Analitic Center Quadratic Cut Method for the Convex Quadratic Feasibility Problem, Preprint, Concordia University, 2000.

53. Monteiro R.D.C. and Adler I. Interior Path Following Primal-Dual Algorithms. Part II: Convex Quadratic Programming // Mathematical Programming 1989, No 44, p.43-66.

54. Murty K. and Kabadi S. Some NP-Complete Problems in Quadratic and Nonlinear Programming // Mathematical Programming 1987, vol.39, No 2, p.117-130.

55. Nesterov Yu. and Nemirovskii A. Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms, SI AM Publications, Philadelphia, 1993.

56. Nowak I. Dual Bounds and Optimality Cuts for All-Quadratic Programs with Convex Constraints // Journal of Global Optimization 2000, vol. 18, No. 4, p.337-356.

57. Pardalos P. and Vavasis S. Quadratic Proghramming with One Neghative Eigenvalue is NP-Hard // Journal of Global Optimization 1991, Vol. 1, No. 1, p.15-22.

58. Polyak B.T. Convexity of Quadratic Transformations and Its Use in Control and Optimization // Journal of Optimization Theory and Applications, 1998, vol. 99, No 3, p.553-583.

59. Raber U. A Simplicial Branch-and-Bound Method for Solving Nonconvex All-Quadratic Programs // Journal of Global Optimization 1998, vol.13, N4, p.417-432.

60. Tuncel L. On the Slater Condition for the SDP Relaxations of Nonconvex Sets // CORR 2000-13.

61. Vavasis S. Nonlinear Optimization. Complexity Issues, Oxford University Press, New York, Oxford, 1991.

62. Vandenberghe L. and Boyd S. Connection between Semi-Infinite and Semidefinite Programming, in Semi-Infinite Programming, Kluwer Academic Publishers, 1998.

63. Wolkowicz H. Semidefinite and Lagrangian Relaxations for Hard Combinatorial Problems, in System Modelling and Optimization, Kluwer Academic Publishers, 1999.

64. Ye. Y. Further Development of the Interior Algorithm for Convex Quadratic Programming, Preprint, Stanford University, 1987.

65. Ye Y. On the Affine Scaling Algorithm for Nonconvex Quadratic Programming // Mathematical Programming 1992, N 56, p.285-300.

66. Ye Y. Approximating Global Quadratic Optimization with Convex Quadratic Constrants // Journal of Global Optimization 1999, vol.15, N1, p.1-17.

67. Yuan Y. On a Subproblem of Trust Region Algorithms for Constrained Optimization // Mathematical Programming, 1990, N47, p.53-63.

68. Yuan Y. A Dual Algorithm for Minimizing a Quadratic Function with Two Quadratic Constraints // Journal of Computational Mathematics, 1991, vol.9, N4, p.348-359.