Двойственные и прямо-двойственные методы аффинно-масштабирующего типа для линейных задач полуопределенного программирования

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

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

Список основных обозначений

Глава 1. Постановка задачи. Методы решения и основные примеры

1.1. Постановка задачи

1.2. Известные классы численных методов решения задач

1.3. Использование задач SDP в приложениях

Глава 2. Двойственные методы простой итерации

2.1. Используемые обозначения и результаты

2.2. Допустимый итерационный процесс

2.3. Общий итерационный процесс
2.4. Невырожденность матрицы Ф(У)
2.5. Алгоритмические операторы и их представления
2.6. Матрица Якоби
Глава 3. Двойственный метод Ньютона
3.1. Итерационный процесс
3.2. Локальная сходимость метода
Глава 4. Прямо-двойственные методы Ньютона
4.1. Прямо-двойственный ньютоновский итерационный
процесс в пространстве точек (X,V)
4.2. Прямо-двойственный ньютоновский итерационный
процесс в пространстве точек (Х,и)
Глава 5. Численный эксперимент
Заключение
Список использованных источников
Приложение

Введение
Линейные задачи полуопределенного программирования (SDP — semidefinite programming) представляют важный раздел математического программирования, активно развивающийся на протяжении последних двух десятилетий. Данные задачи играют существенную роль в таких областях как комбинаторная и квадратичная оптимизация, теория управления, структурная оптимизация, оптимизационные задачи на собственные числа. Поэтому методам решения линейных задач полуопределенного программирования в последнее время уделялось огромное внимание.
Хотя формулировка задачи SDP была дана Р. Веллманом и К. Фаном в 1963 году [4], основные результаты в данной области были получены после появления методов внутренней точки для задач линейного программирования (LP — linear programming). И.И. Дикин в 1967 году [52] впервые рассмотрел метод внутренней точки для задач LP, который впоследствии получил в западной литературе название аффинно-масштабирующего метода. В 1979 году JI. Хачиян [69] предложил метод эллипсоидов для решения задач LP, имеющий полиномиальное время работы. Первый же полиномиальный метод внутренней точки в задачах LP, был предложен Н. Кармаркаром в 1984 году [11]. Впоследствии было предложено много других полиномиальных методов внутренней точки для решения задач LP, из которых наиболее эффективными с вычислительной точки зрения оказались прямо-двойственные методы центрального пути.

Заменяя в ней матричные равенства на их векторные аналоги, получаем
ес(Х * У) = 0„„,
AvecvecX = Ь,
vec У = vec С - А„еси,
ХУ О, V У 0.
Здесь и ниже через Avec обозначается mxn2 матрица, строками которой являются векторы vecА{, 1 і SC т.
Но в силу известной формулы
vec (ABC) — (СТ ® A)vecB, (2.2.3)
справедливой для любых матриц А, В и С, для которых определено произведение ABC, получаем, что vec(X * V) — V®vecX, где
У® = [V ® /„ + 7П ® У] /2
— кронекеровская полусума матрицы У. Таким образом, система условий (2.2.2) может быть представлена в виде
У® vec X = 0„2,
AvecvecX = 6, 2 2 4)
vec У — vec С — А„еси,
ХУ 0, У У 0.
Умножим теперь второе уравнение в (2.2.4) на матрицу А„ес: AlcAveeVec X = ATvecb. (2.2.5)
Складывая данное равенство с первым равенством из (2.2.4), получаем линейное уравнение относительно vec X
Ф(У)УесХ = АГеЛ (2.2.6)
где Ф(У) = АуЄСАуес + Н® — симметричная матрица порядка п2.