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

• Автор: Нечаева, Мария Станиславовна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Иркутск
• Количество страниц: 103 с. : ил

Содержание
Введение

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

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

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

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

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

пересечение двух эллипсоидов

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

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

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

1.3.2 Оценка
1.3.3 Оценка
1.3.4 Оценка
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 Результаты численного тестирования
4 Заключение

Введение
Квадратичное программирование представляет собой один из важнейших разделов математического программирования. Большое количеством прикладных (технических и экономических) постановок сводятся к квадратичным оптимизационным задачам разной сложности. Квадратичные задачи возникают также и как вспомогательные в рамках методов решения более общих задач.
Задача квадратичного программирования в общем виде записывается следующим образом:
тш./(ж), х £ С, (1)
/(х) = хтСЭ0х + с^х, (2)
С = {х 6 Еп : хт(^1Х + с[х < 7Ц, г = 1,т}. (3)
Здесь (^1, с*, г — 0,1,т, - соответственно симметричные матрицы и
заданные векторы в пространстве Еп, гг- £ {—1, 0,1}.
Среди ограничений (3) как частный случай могут присутствовать и линейные. Если матрица г Е {О,т}, неотрицательно определена, а г, = 1, г £ {1,..., т}, то соответствующая квадратичная функция выпукла. Если это справедливо для всех г = 1,..., п, задача (1)-(3) относится к классу задач выпуклого программирования и решается за полиномиальное время. Если же не накладывается никаких ограничений на определенность матриц хотя бы только в (2) или в (3) или на значение правой части в (3), задача переходит в класс труднорешаемых — ИР-трудных, и к ней требуется применять аппарат глобальной оптимизации.
Невыпуклое квадратичное программирование как область математического программирования переживает в настоящее время период активного развития. Обнаружена полиномиальная разрешимость отдельных классов задач квадратичного программирования. Для других классов разрабатывают варианты методов глобальной оптимизации, стремясь ускорить сходимость за счет учета специфики задачи. Имеются отдельные попытки адаптировать методы глобальной оптимизации и к задаче квадратичного программирования в ее самой общей постановке.
Выпуклая квадратичная задача
Ряд выпуклых квадратичных задач возникает в экономике [48]. Например, пусть известно, что проданное количество с некоторого товара за-

ограничена на этом отрезке. Производная представляет собой дробь, числитель /(г?) которой есть полином третьей степени, ограниченный на рассматриваемом отрезке. Значит, д(у) нигде на этом отрезке не обращается в ноль. Поскольку этот полином принимает положительные значения на концах отрезка [0, знаменатель (1.28) производной мажорирующей функции положителен на всем отрезке.
Между тем, числитель (1.27) производной принимает отрицательное значение на левом конце отрезка [О, Н. Если (1.29) имеет два различных корня на рассматриваемом отрезке, то значение (1.27) на его правом конце также отрицательно, и внутри [0, имеется промежуток, где числитель производной положителен. Тогда вся производная дважды меняет знак на отрезке: с отрицательного на положительный и вновь на отрицательный. Однако для квазивыпуклой функции это невозможно. Таким образом, (1.29) имеет не более одного корня на исследуемом отрезке.
2. Числитель (1.27) производной принимает неотрицательное значение на левой границе отрезка [0, ^]. Следовательно, в случае существования на этом промежутке действительного корня полинома (1.27) производная меняет в этой точке знак с отрицательного на положительный. Ввиду квазивыпуклости функции Щап{и, у) это означает, что в этой точке достигается минимум верхней оценки сокращения объема.
3. Предположим, уравнение (1.29) не имеет корня на отрезке [0,^]. Тогда (1.27) принимает отрицательные значения на всем этом промежутке, и, ввиду положительности (1.28), логарифмическая производная функции Утап(и,у) отрицательна на всем отрезке, что свидетельствует об убывании мажорирующей функции. £
Утверждение 3 теоремы 1.2 означает, что если уравнение (1.29) не имеет корня на требуемом отрезке, то следует положить V = и = 0,

т.е. выбрать в качестве аппроксимирующего эллипсоида шар (1.14).
Итак, если пара (й,у) доставляет минимум функции Утап(и,ь), то, учитывая сокращение ктап объема на втором шаге, имеем следующую общую оценку:
ТТап = У(и,и) ■ КТаП■ (1-30)
Для всякого г = 1, ...,п выполняется следующее неравенство:
и + Vд2 _ Д _ и(А, - /л) < 0 (-и + гщ)2 и + гщ (и + гщ)2 ~
Следовательно, оценка (1.30) более точно аппроксимирует сокращение