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

На правах рукописи

Орлов Александр Алексеевич

Ч1^

ДВОЙСТВЕННЫЕ И ПРЯМО-ДВОЙСТВЕННЫЕ МЕТОДЫ АФФИННО-МАСШТАБИРУЮЩЕГО ТИПА ДЛЯ ЛИНЕЙНЫХ ЗАДАЧ ПОЛУОПРЕДЕЛЕННОГО ПРОГРАММИРОВАНИЯ

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

кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2012

С ДЕК 2012

005056411

005056411

Работа выполнена на кафедре математических основ управления Московского физико-технического института (государственного университета)

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

профессор Жадан Виталий Григорьевич

Официальные оппоненты: Доктор физико-математических наук,

профессор Афанасьев Александр Петрович, Институт системного анализа РАН, заведующий отделом

Доктор физико-математических наук, профессор Измайлов Алексей Феридович, факультет ВМиК МГУ им. М. В. Ломоносова, профессор

Ведущая организация: Институт проблем управления

им. В. А. Трапезникова РАН

Защита состоится « » декабря 2012 года в 9 час. на заседании диссертационного совета Д 212.156.05 при Московском физико-техническом институте (государственном университете) по адресу: 141700, г. Долгопрудный Московской обл., Институтский пер. д.9, ауд. 903 КПМ.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан «_3_» ноября 2012 г. Ученый секретарь

диссертационного совета / Федько О. С.

Общая характеристика работы

Актуальность темы. Линейные задачи полуопределенного программирования (SDP - semidefinite programming) представляют важный раздел математического программирования, активно развивающийся на протяжении последних двух десятилетий. Данные задачи играют существенную роль в таких областях как комбинаторная и квадратичная оптимизация, теория управления, структурная оптимизация, оптимизационные задачи на собственные числа. Поэтому методам решения линейных задач полуопределенного программирования в последнее время уделяется огромное внимание.

Хотя формулировка задачи SDP была впервые дана Р. Беллманом и К. Фаном в 1963 году, основные результаты в данной области были получены после появления методов внутренней точки для задач линейного программирования (LP - linear programming). Ю. Е. Нестеров и А. С. Немировский, а также Ф. Ализаде впервые обобщили методы внутренней точки на случай задач SDP в 1990-1991 годах. В их работах были предложены прямые и двойственные методы решения.

Следующим этапом развития стало распространение прямо-двойственных методов, главным образом, методов центрального пути, со случая задач LP на задачи SDP. В отличие от задач LP существует множество способов построения ньютоновских направлений движения для прямо-двойственных методов в задачах SDP. В связи с этим доказательство сходимости таких методов для задач SDP оказывается более сложным. Первыми из появившихся и наиболее часто используемыми на практике являются следующие три направления движения в прямо-двойственных методах: АНО (Ализаде, Хайберли, Овертон), Ж (Нестеров, Тодд), HRVW/KSH/M (Хельмберг, Рендл, Вандербей, Волкович; Кожима, Шиндо, Хара; Монтейро).

В дальнейшем рядом авторов были построены семейства направлений поиска решения в прямо-двойственных методах для задач SDP, включающих указанные выше направления как частные случаи, а также дано обоснование сходимости алгоритмов, использующих эти семейства направлений. Наиболее известными семействами являются: MZ (Монтейро, Жанг), KSH (Кожима, Шиндо, Хара), МТ (Монтейро, Цучия).

Среди российских авторов помимо Ю. Е. Нестерова и А. С. Немировского следует отметить вклад Б. Т. Поляка, П. С. Щербакова, И. И. Дикина в развитие методов решения задач SDP.

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

Для достижения этой цели ставились следующие задачи:

1. Сведение системы оптимальных условий в задаче SDP к системе уравнений с меньшим числом неизвестных путем построения зависимости прямых переменных от двойственных.

2. Решение полученной нелинейной системы уравнений методом простой итерации и методом Ньютона. Аналитическое исследование сходимости данных методов.

3. Построение прямо-двойственных методов решения задачи SDP, основанных на решении системы оптимальных условии методом Ньютона. Обоснование локальной сходимости построенных методов.

Научная новизна. Все выводы и результаты работы являются оригинальными. Предложенные в работе методы можно отнести к двойственным и прямо-двойственным методам аффинно-масштабирующего типа. В некотором роде, построенные методы являются обобщением барьерно-проективных методов, предложенных ранее Ю.Г. Евтушенко и В.Г. Жаданом для решения задач

линейного программирования на более сложные линейные задачи полуопределенного программирования.

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

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

Апробация результатов диссертации. Основные положения диссертации были доложены и обсуждены на следующих конференциях и семинарах:

• 52, 53, 54 научные конференции МФТИ, ноябрь 2009-2011, Москва;

• VI Московская международная конференция по исследованию операций, октябрь 2010, Москва;

• 15я Байкальская международная школа-семинар «Методы оптимизации и их приложения», июнь 2011, пос. Листвянка, озеро Байкал;

• VII Всероссийская научная конференция «Математическое моделирование развивающейся экономики и экологии» (ЭКОМОД-2012), июль 2012, Киров.

Публикации. По теме диссертации опубликовано 7 работ, из них три [4,5,7] из списка, рекомендованного ВАК РФ. В работах с соавторами лично соискателем выполнено следующее:

• построение зависимости прямых переменных от двойственных, обоснование корректности данной зависимости;

• получение двойственных и прямо-двойственных методов решения линейной задачи полуопределенного программирования;

• обоснование сходимости двойственного метода простой итерации;

• доказательство теорем о сходимости прямо-двойственных методов Ньютона;

• реализация построенных методов в среде MATLAB;

• подготовка тестовых задач и проведение вычислительных экспериментов.

Объем и структура работы. Диссертация состоит из введения, пяти глав, заключения и приложения. Список использованных источников включает 70 наименований. Текст диссертации содержит 102 страницы.

Содержание работы

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

В первой главе рассматривается постановка линейной задачи полуопределенного программирования, приводятся некоторые из известных на данный момент численных методов ее решения, а также примеры сведения различных оптимизационных задач к задачам SDP.

Пусть S" обозначает пространство симметричных матриц порядка п, S" его подмножество, состоящее из положительно полуопределенных матриц. Скалярное произведение матриц Z и М одного размера вводится как след матрицы ÜM и обозначается L*M. Прямая задача SDP имеет следующий вид:

тт С*Х

А^Х = Ь\ ¡ = \...т, (Р)

ХЯ),

где матрицы X, С и Д, 1 < г < т принадлежат множеству Б". Неравенство ХМ) означает, что матрица X является положительно

полуопределенной, то есть, /

Двойственной к (Р) является задача: тахЬТи

т

2Уд. + г = с, (О)

1=1

¥у 0.

Переменная X в дальнейшем назьшается прямой, а переменные ми Vдвойственными.

Точка X Е называется допустимой в задаче (Р), если выполняется условие: Д- • X = Ь', 1=1...т.

Точка [и, К] называется допустимой в задаче (Б), если V е Б"

т

и выполняется условие: ^и'Д- + V = С.

/=1

Предположим, что решения задач (Р) и (Б) существуют и что матрицы Д ,1 <1<т,линейно независимы.

Из предположения о существовании решений у задач (Р) и (Б) следует, что имеет решение следующая система равенств и неравенств:

x*v=o,

А^Х = Ъ\ i-\...m, XeS"

i=l

Z^O, VtO,

являющаяся условиями оптимальности для (Р) и (D).

Отметим, что для симметричных положительно полуопределенных матриц равенство X • V = 0 эквивалентно равенству XV = VX = 0пп, то есть, в решении матрицы Хя Vкоммутируют.

Если Х*и \u*,V*] - решения задач (Р) и (D), то можно указать ортогональную матрицу Q и векторы Г|* и 0*, такие, что

X* = QD(y\*)QT, V* = QD(Q*)QT, где D(a) - диагональная матрица с вектором а на диагонали. Для собственных значений Г|1 и 9i тогда выполняется равенства: Г)'*0г* = 0, i = 1,п. Если для каждого / = 1,...,и одно из значений т}* или 0* положительно, то решения X* и К называются строго комплементарными.

Многие численные методы решения задачи SDP могут быть проинтерпретированы как некоторые способы решения системы (1) или ее модификаций. В качестве примера, в первой главе диссертации приводятся следующие известные методы решения:

• Прямо-двойственные методы аппроксимации центрального пути.

• Прямо-двойственные аффинно-масштабирующие методы.

Кроме данных методов существуют и другие, не использующие напрямую систему оптимальных условий, например, методы

s

уменьшающегося потенциала, которые также описаны в первой главе.

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

В первой главе приведены также два наиболее известных примера практического использования задач SDP. Рассмотрена задача оптимизации собственных значений матриц, а также задача о максимальном разрезе графа MAX-CUT.

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

Обозначим через X * V симметризованное произведение симметричных матриц X и V, определяемое как X*V = (XV + VX) / 2. Имеет место следующее утверждение.

Утверждение 1. Для симметричных матриц Х>0 и V>ß равенство X*V = 0пп возможно в том и только том случае, когда

XV = VX = QM.

С учетом утверждения 1 система оптимальных условий (1) может быть переписана как

Л ' vпп'

Х = Ъ\ i = l...m, XeS",

» • (2) 5У4+Р = С, VeSn,

i=1

ХуО, V^Q.

При построении методов используются операторы векторизации матриц. Если М квадратная матрица порядка п, то симво-

лом \есМобозначается прямая сумма ее столбцов, то есть вектор-столбец длины и2, в котором последовательно один под другим располагаются столбцы матрицы М. Для симметричных матриц имеет смысл вместо вектор-столбца уесМ рассматривать вектор-столбец уесИМ . В него также помещаются последовательно сверху-вниз столбцы матрицы М, но не полностью, а только их нижние части, начиная с диагонального элемента. Аналогичным образом определяется вектор-столбец уесяМ. От уесНМ он отличается только тем, что все элементы, не стоящие на диагонали матрицы М при помещении в уесяМ умножаются на два.

Введем обозначение к&(п) = п(п+\)/2. Длина векторов

гесИМи хесзМравна кА(п) .

Для перехода от вектора хесМ к вектору VесЬМ и для обратного перехода используются специальные элиминационные и дуп-лицирующие матрицы. Элиминационная матрица ¿„для каждой квадратной матрицы М порядка п осуществляет преобразование ЬпуесМ-\echM. Напротив, дуплицирующая матрица £>„ для каждой симметричной матрицы М порядка п осуществляет преобразование и^есЬМ = vecM.

Используя введенные обозначения, а также известную форТ

мулу где символ ® обозначает произ-

ведение матриц по Кронекеру, перепишем систему равенств и неравенств (2) в следующем виде:

¥%есХ = 0 2,

п

ХМ), ГуО.

Здесь через Д,ес обозначена тхп2 матрица, строками которой являются векторы тЦ, V® =[У®1п+1л®У]12 - кронекеров-ская полусумма матрицы V, /„ - единичная матрица порядка п.

Домножая в (3) второе уравнение на матрицу и складывая с первым уравнением приходим к равенству:

Ф (У)уесХ = 4есЬ, (4)

— Т 0

где Ф(У) = А^>есАуес + V . Переходя к вектору \echX, получаем

следующую зависимость прямых переменных от двойственных:

уесИХ = Ф~\У)А^есф, (5)

гдеФ^Л^А^+^Я.

Система (5) дает зависимость уескХ(У), которой соответствует матричная зависимость .

Пусть ЯА - подпространство в 5", порожденное матрицами Д., 1 </<ти пусть - его ортогональное дополнение. Обозначим также Тг и Ту - касательные подпространства к в точках Хп Г соответственно.

Определение (Ализаде, Хайберли, Овертон). Точка V называется невырожденной в двойственной задаче, если при некотором не1™ точка [и, V] является допустимой и Ту + ЯА~5". Допустимая точка X называется невырожденной в прямой задаче, если

В диссертации показывается, что в невырожденных точках зависимость (5) определена корректно, что подтверждается следующей теоремой.

Теорема 2. В невырожденной точке V матрица Ф (V) неособая.

Если пара [и, К] удовлетворяет третьему равенству в системе (1), то V = У(и) — С — Д- ■ Тогда зависимость Х(У) фак-

тически становится зависимостью Х(и) = Х(У(и)). Если подставить ее во второе равенство системы (3), то приходим к системе т нелинейных уравнений относительно т неизвестных:

К(6)

Применим для решения системы (6) метод простой итерации: ик+1 = ик + - АесзФ~1 (Ук)^есИ~\Ь> (?)

где ак >0,й0еЕ".

В пространстве двойственной переменной V итерационный процесс (7) в векторном виде представим как: уесйК.., = уесИУ^ -

Т -1 г <8>

~акА/еск I/т ~ Лем^ (Ук ) АесЛ

где

Помимо итерационных процессов (7) и (8) во второй главе рассматривается также более общий итерационный процесс, в котором уже не обязательно сохраняется равенство Ук = У(ик). Для получения данного процесса снова домножим в (3) второе уравнение на матрицу третье уравнение на произвольную константу

т > 0 и сложим получившиеся уравнения с первым уравнением из

(3):

Ф (У)уесХ = А^всЪ + х {уесУ + А$еси - гесС) (9)

или, после перехода от вектора \есХ к вектору уесИХ,

Ф(У)уескХ = Е(и,уес!г(У)). (10)

Здесь для упрощения записи введено обозначение

F(w, уеск(У)) = А1есф + фесИУ + А^есЬи - \echC). Решая уравнение (10) относительно X получаем: увсХ = Опф-\У)Г(и, уескУ). (11)

Переменная X теперь зависит от двух переменных и и Г, т.е. становится функцией Х(и,У). Данная зависимость переходит в зависимость (5), если взять т = 0 или если взять V = У(и).

Подставляя зависимость Х{и, V) в первые два равенства системы (3), получаем:

У®Опф-1(У)Г(и^ес!гУ) = Оп1, ^

4,ес,ф-1(У)Г(и,уесЬУ)-Ь = 0т.

Данная система состоит из т+п2 уравнений. На самом деле, она может быть сведена к системе из меньшего числа уравнений:

1пУ®Опф-\У)Г(и,уескУ) = 0Лд(л), (п)

Ауес,ф-\У)Р(и,гескУ)-Ь = 0т.

Снова применяя для решения системы (13) метод простой итерации, приходим к итерационному процессу:

ик+1 = ик + а к[Ъ - Аес,Ф~\Ук)Р(икуескУк)1 (М)

уесИУк+1 ^есНУк-акЦгУ®Ппф-\Ук)Р{ик,уесИУк), где м0ейи, Уд=У(иа)еЯ"-

Итерационные процессы (7), (8) и (14) будут являться методами внутренней точки при надлежащем выборе шага ак> 0, если

потребовать, чтобы в начальной точке [и0,¥0] выполнялось У0 >- О.

Локальная сходимость итерационного процесса (14) (а следовательно и его частных случаев - процессов (7) и (8)) подтверждается следующей теоремой:

Теорема 3. Пусть X, и [и*,К] - решения задач (Р) и (О) соответственно, причем X, и К строго комплементарны. Пусть, кроме того, точки X. и V, невырожденные. Тогда, итерации, представленные формулами (14), в который шаг ак берется постоянным и достаточно малым, локально сходятся к [и.,К] с линейной скоростью.

Отметим, что нуль-пространство у матрицы К® совпадает с нуль-пространством ее квадрата. Поэтому, в принципе, первое ра-

бЬ

венство в (3) можно было бы заменить на (V ) уесХ = 0и построить соответствующие итерационные процессы, в которых вместо матрицы V® использовалась бы матрица (Г®)2. Однако, такие процессы уже могут не обладать локальной сходимостью во всем пространстве, даже при сделанных предположениях относительно решений задач (Р) и (Е)).

В третьей главе предложен метод, который можно отнести к классу двойственных методов Ньютона и обоснована его локальная сходимость со сверхлинейной скоростью.

Как и во второй главе, мы будем решать систему уравнений (6) относительно переменных и, однако теперь применим для ее решения метод Ньютона. Тогда, соответствующий итерационный процесс запишется в виде:

Щ+1 = Щ+Л~\ик)[1т ~\Ук)4еси\Ъ, (15)

здесь через А (и) обозначена матрица

аи

Для того чтобы уточнить вид матрицы Ми) представим ее в виде:

А(и) = А^ес5 ^-уес1гХ(и). аи

Таким образом, чтобы определить А(и), следует найти матрицу Якоби от вектор-функции месЬХ{и). Обратимся к тождеству:

[4еЛес + У%фесХ(и) = 4есЬ. Дифференцируя его по и и используя равенство

—хескХ{и) = Ьп —\ecXiu) с1\и йи

находим:

4-^ескХ(и) = Ф"ЧП«))" ЬпХ®(и)Пп4ес}1 аи

и, соответственно:

Ми) = 4>ес*[4есЛес* + ■

После подстановки найденной матрицы Л(м), итерационный процесс (15) принимает вид:

ик+1 ~ 11 к + (А>ес*[у^ес/гА>есх + ^гУк

■Ь^оЛсиГ" ■ О7)

■ит - ЛесМ^/Ае« + 1п¥кВпТ14сс}г\Ь^

где Ук =У(ик), Хк-Х(ик). Итерационный процесс (15) корректно определен, если на каждой итерации матрица А.(ик) неособая.

(16)

Локальная сходимость итерационного процесса (15) обосновывается следующей теоремой.

Теорема 4. Пусть X, и [и„К] - решения задач (Р) и (D) соответственно, причем X, и К строго комплементарны. Пусть, кроме того, точки X, и V, невырожденные. Тогда, итерационный процесс (15) локально сходится к решению двойственной задачи и,

со сверхлинейной скоростью.

В четвертой главе были построены два прямо-двойственных ньютоновских метода для решения задач SDP и показана их локальная сходимость со сверхлинейной скоростью.

Опишем сначала прямо-двойственный процесс в пространстве точек (X, V). Для этого обратимся снова к системе оптимальных условий (3) и рассмотрим подробнее третье уравнение. Из него следует, что вектор vech(C-V) является линейной комбинацией

линейно независимых векторов vechAx,...,vechAm.

Пусть I = кй(п)-т, КЛ,...,К, - линейно независимые матрицы в S" со свойством

СvecsKfvechAj = 0 Vi е[1. J],j e[l...m]. Матрицы КХ,...,К, образуют базис в линейном подпространстве

S", ортогональном к подпространству, порожденному матрицами А1,...,Ат. Обозначим через ^„матрицу размера lxkä(n), строками которой являются векторы vecsKt.

Используя матрицу Krecs, перепишем систему оптимальных условий (3) в следующем виде: vech(X*V) = 0кА{п),

AecsvechX=b,

KvecsvechV = b, ХуО, VyO,

где Ь = К^ескС.

Введем в рассмотрение вектор-функцию г \

Рх{уескХ ,уесЬУ) =

уеск(Х*У) А^^есНХ-Ъ

^уесНУ-Ъ,

и рассмотрим систему

Рх(уесЬХ,уескУ) = 0, (19)

содержащую 2кА (я) уравнений и 2кА (и) неизвестных.

Будем решать систему (19) методом Ньютона. Соответствующий итерационный процесс в таком случае имеет вид:

1 4 * к) (20)

V есЬУъ

¿+1 у

уесИ V,

к У

(уесИХк, уесИ Ук),

где

дРх(уесШ,уесНУ)

1 д(уесИХ)т д(уескУ)т

Выполнив дифференцирование, находим явный вид матрицы

Щ (х,уу.

Л

Щ (Х,Г) =

1 У В ^пг п

^Кесз 0

0 V V есз

(21)

В диссертационной работе доказана следующая теорема и, как следствие, получен результат о локальной сходимости итерационного процесса (20).

Теорема 4. Пусть X, и [u,,V,\ - решения задач (Р) и (D) соответственно, причем X, и К строго комплементарны. Пусть, кроме того, точки X. и V, невырожденные. Тогда, матрица

Щ (Х*,К) неособая.

Следствие 1. Пусть X, и [u„V.] - решения задач (Р) и (D) соответственно, причем X, и К строго комплементарны. Пусть, кроме того, точки X, и V, невырожденные. Тогда, итерационный процесс (20) локально сходится к [X„V,] со сверхлинейной скоростью.

Теперь рассмотрим прямо-двойственный итерационный процесс, в котором на каждой итерации пересчитывалась пара (Х,и).

Учтем явный вид зависимости V(u) -С-(и Ai и будем решать

систему оптимальных условий в здаче SDP относительно переменных (Х,и):

vech(X*V(u)) = 0,

A^vechX = b, (22)

X>Q, F(u)y0.

Введем вектор-функцию

\AecSvechX-b ) и рассмотрим систему

F2(vechX,н) = 0 . (23)

Данная система содержит кА(и) + туравнений и кА(п)+тпет-вестных. Будем решать систему (23) методом Ньютона:

rvechXk+^

( vechX

к

\

uk

-W2-\Xk,uk)-

■F2(vechXk,uk),

где

W2(X,u) = dF^VechXT>u)T, щ e]Rm, X0eS\ 2 d(vechX)du

Матрица W2 (Ж>м) имеет следующий вид: Щ(Х,и) =

rLnV®(u)Dn -LnX®DXed?

(25)

Avecs 0

Теорема 5. Пусть X. и [и., К ] - решения задач (Р) и (D) соответственно, причем X, и V, строго комплементарны. Пусть, кроме того, точки X, и V. невырожденные. Тогда, матрица

W2 {X*, и* ) неособая.

Следствие 2. Пусть X, и [и,,К] - решения задач (Р) и (D) соответственно, причем X. и К строго комплементарны. Пусть, кроме того, точки X, и К невырожденные. Тогда, итерационный процесс (24) локально сходится к [Xt,u,] со сверхлинейной скоростью.

В пятой главе описаны результаты численных экспериментов, которые проводились с использованием среды MATLAB на задачах малой и средней размерности. Для получения тестов, «обратным ходом» генерировались задачи SDP, решение которых было известно. Генерация осуществлялась по следующим правилам: 1. Задавались параметры п,т,г (где г = гапк(К)), удовлетворяющие необходимому условию невырожденности точек Xt и [ut,V,]: кА(п-г) < т < кК(п)-кА(г). Были проведены эксперименты для п от 2 до 50.

2. Генерировались случайным образом положительные числа т]1,...,?]г и в\...,вПтГк ортогональная матрица О. После этого генерировалась пара задач (Р) и (О), решением которой являются матрицы X.=QDiag(0,...,0,e\■■■,в"~r)QГк К = ()01аё(т}\..., для этого:

3. Генерировался набор случайных симметричных матриц А1,...,Ат и случайный вектор и. =[м!,...,иГ]

4. Задавался вектор Ь = [Ь\...,Ьт] по правилам 6' = Д • X

т

5. Задавалась матрица С по правилу С ~ + V,

¡=1

В результате мы получали прямую и двойственную задачи полуопределенного программирования с известным решением X, и [и,,К]. На данной задаче проводились тесты допустимого варианта двойственного метода простой итерации из главы 2, двойственного ньютоновского метода из главы 3 и двух вариантов прямо-двойственных ньютоновских методов из главы 4.

В ходе экспериментов в окрестности решения генерировалась случайным образом начальная точка. Для этого задавалось приращение Лы: ^ = е, причем е принимало значение 0.15 либо 0.1,

II ".II

либо 0.07. После этого определялись иа = и, +Аи, У0-У(ид) и Х0 = Х(У(и0)) по формуле (5). При генерации начальной точки одной из целей было получить относительно «равномерное» отклонение от решения по норме переменных Х,У и ы(под нормой матрицы здесь подразумевается норма по Фробениусу). Поэтому,

IIX,-Х||

после генерации Х0,У0 вычислялись значения —■ — и

IIX» ||

———. В случае, если оказывалось, что оба эти значения боль-

IIУII

ше чем е/3, из построенной таким образом начальной точки осу-

20

ществлялись итерации, причем, условием остановки являлось Хк • ¥к < 10'5. Если же хотя бы одно из них было меньше е!3, то генерация задач (Р) и (Б) осуществлялась повторно.

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

В таблице 1 приведены некоторые из параметров выборочных тестовых задач, а также результаты работы предложенных методов на данных задачах. В таблице используются следующие обозначения: метод 1 - допустимый вариант двойственного метода из главы 1, метод 2 - ньютоновский метод из главы 3, методы 3 и 4 - прямо-двойственные методы из главы 4 в пространстве точек (Х,¥) и (Х,и) соответственно.

Таблица 1. Результаты эксперимента.

Параметры задачи Число итераци Й

п т К е 11ХЦ IW-r.ll II К II Метод 1 Метод 2 Метод 3 Метод 4

2 1 1 0.15 0.080 0.063 -1.903 1 1 1 1

5 7 3 0.15 0.145 0.082 2.961 3 3 3 2

10 25 5 0.15 0.106 0.109 -2.981 5 2 4 3

15 60 8 0.15 0.091 0.124 1.728 9 11 9 7

20 95 10 0.15 0.095 0.132 -4.146 12 23 13 12

25 165 13 0.15 0.103 0.062 -3.544 37 28 18 20

30 215 15 0.1 0.076 0.049 2.612 31 46 31 30

35 315 18 0.15 0.146 0.124 1.408 77 49 39 41

40 415 20 0.07 0.040 0.025 3.272 55 46 51 49

45 515 23 0.15 0.104 0.127 0.553 53 90 58 55

50 615 25 0.07 0.050 0.069 -3.796 70 92 88 80

В заключении приведены основные результаты работы.

В приложении содержатся примеры тестовых задач небольшой размерности.

Основные результаты работы

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

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

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

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

5. Проведены вычислительные эксперименты на тестовых задачах (рандомизированные данные малой и средней размерности), которые подтвердили корректность работы данных методов, а также проведен сравнительный анализ скорости их работы.

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

Публикации автора по теме диссертации

1. Орлов A.A. О численных методах решения задач полуопределенного программирования и примерах задач, для которых они являются неэффективными// Труды 52-й научной конференции МФТИ, Часть VII, Том 1 / МФТИ - М.-Долгопрудный, 2009,-С. 120-122.

2. Жадан В.Г., Орлов A.A. Двойственный метод Ньютона для линейной задачи полуопределенного программирования// Оптимизация и приложения. - 2010. М.: ВЦ РАН. - С. 87-108

3. Орлов A.A. Двойственный метод Ньютона для задачи полуопределенного программирования// Труды 53-й научной конференции МФТИ, Часть VII, Том 1 / МФТИ - М.Долгопрудный, 2010,- С. 75-77

4. Жадан В.Г., Орлов A.A. О сходимости двойственного метода Ньютона для линейной задачи полуопределенного программирования// Известия Иркутского государственного университета.

- 2011. -Т.4 №2 - С. 75-90

5. Жадан В.Г., Орлов A.A. Двойственные методы внутренней точки для линейной задачи полуопределенного программирования// Журнал вычисл. матем. и матем физики - 2011. - Т.51 №12-С. 2158-2180

6. Жадан В.Г., Орлов A.A. Допустимый и общий двойственные методы внутренней точки для линейной задачи полуопределенного программирования//Тезисы 15й Байкальской международной школы-семинара «Методы оптимизации и их приложения»

- Т.2 «Математическое программирование» - Иркутск: РИО ИДСТУ СО РАН, 2011 - С. 81-86

7. Жадан В.Г., Орлов A.A. Допустимый двойственный метод внутренней точки для линейной задачи полуопределенного программирования// Автоматика и телемеханика - 2012. - №12

- С. 25-40

Орлов Александр Алексеевич

ДВОЙСТВЕННЫЕ И ПРЯМО-ДВОЙСТВЕННЫЕ МЕТОДЫ АФФИННО-МАСШТАБИРУЮЩЕГО ТИПА ДЛЯ ЛИНЕЙНЫХ ЗАДАЧ ПОЛУОПРЕДЕЛЕННОГО ПРОГРАММИРОВАНИЯ

АВТОРЕФЕРАТ

Подписано в печать 30.10.2012 Формат 60 ' 84 1/16. Усл. печ. л. 1,0. Тираж _80_ экз. Заказ № 526. Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии «Физтех-полиграф» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9

Введение

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

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

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

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

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 году Л. Хачиян [69] предложил метод эллипсоидов для решения задач LP, имеющий полиномиальное время работы. Первый же полиномиальный метод внутренней точки в задачах LP, был предложен Н. Кармаркаром в 1984 году [И]. Впоследствии было предложено много других полиномиальных методов внутренней точки для решения задач LP, из которых наиболее эффективными с вычислительной точки зрения оказались прямо-двойственные методы центрального пути.

Ю. Е. Нестеров и А. С. Немировский, а также Ф. Ализаде впервые обобщили методы внутренней точки на случай задач SDP. В их работах [1] и [30] были предложены прямые и двойственные методы решения.

Следующим этапом развития стало распространение прямо-двойственных методов, главным образом, методов центрального пути, со случая задач LP на задачи SDP. В отличие от задач LP существует множество способов построения ньютоновских направлений движения для прямо-двойственных методов в задачах SDP. Как правило доказательство сходимости таких методов для задач SDP оказывается достаточно сложным. Первыми из появившихся и наиболее часто используемыми на практике являются следующие три направления движения в прямо-двойственных методах: AHO [3], NT [31, 32], HRVW/KSH/M [10, 18, 23].

Рядом авторов были построены семейства направлений поиска решения в прямо-двойственных методах для задач SDP, включающих указанные выше направления как частные случаи, а также дано обоснование сходимости алгоритмов, использующих эти семейства направлений. Наиболее известными семействами являются: MZ [23, 44], KSH [18], МТ [24].

Среди российских авторов помимо Ю. Е. Нестерова и А. С. Неми-ровского следует отметить вклад Б. Т. Поляка, П. С. Щербакова, И. И. Дикина в развитие методов решения задач SDP [50, 51, 67].

В настоящее время теория и методы решения задач SDP достаточно хорошо проработаны, опубликовано несколько монографий [41,16, 5, 38], из которых стоит отметить книгу [41], в которой дан обзор основных результатов, полученных в области полуопределенного программирования к концу предыдущего столетия.

Как уже отмечалось, многие другие оптимизационные задачи могут быть переформулированны или редуцированны к задачам SDP. Различные способы практического применения задач SDP можно найти в книгах [41, 5], а также в обзорных работах [39, 40, 38].

Научная новизна. Все выводы и результаты работы являются оригинальными. Предложенные в работе методы можно отнести к двойственным и прямо-двойственным методам аффинно-масштабирующего типа. В некотором роде, построенные методы являются обобщением барьерно-проективных методов, предложенных ранее Ю.Г. Евтушенко и В.Г. Жаданом в [53] для решения задач линейного программирования, на более сложные линейные задачи полуопределенного программирования.

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

Цель диссертационной работы:

• Сведение системы оптимальных условий в задаче SDP к системе уравнений с меньшим числом неизвестных путем построения зависимости прямых переменных от двойственных.

• Решение полученной нелинейной системы уравнений методом простой итерации и методом Ньютона. Аналитическое исследование сходимости данных методов.

• Построение прямо-двойственных методов решения задачи SDP, основанных на решении системы оптимальных условии методом Ньютона. Обоснование локальной сходимости построенных методов.

• Проверка работоспособности полученных методов на тестовых задачах.

Работа состоит из введения, пяти основных глав, заключения, списка использованных источников и приложения.

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

В данной главе указаны также несколько наиболее популярных алгоритмов решения задач SDP: прямо-двойственные методы аппроксимации центрального пути, методы уменьшающегося потенциала, прямо-двойственные аффинно-масштабирующие методы. Рассмотрены две прикладные задачи (оптимизация собственных значений матрицы и NP-полная задача комбинаторной оптимизации MAX-CUT), при решении которых могут быть использованы задачи SDP.

Кроме того, в первой главе описаны некоторые принципиальные различия между задачами LP и SDP, а также, следуя [27], приводится пример задачи размерности п = 2, на которой известные прямо-двойственные аффинно-масштабирующие методы не сходятся к решению.

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

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

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

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

Пятая глава содержит результаты численных экспериментов, проведенных на тестовых данных. Эксперименты проводились с использованием среды MATLAB на задачах малой и средней размерности. Тестовые задачи генерировались по специальным правилам таким образом, чтобы в результате получалась задача SDP с известным решением. Способы генерации тестовых задач описаны в пятой главе.

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

В заключении сформулированы основные результаты, полученные в диссертации.

В приложении содержатся примеры тестовых задач небольшой размерности.

Главное преимущество методов, предложенных в работе, состоит в том, что для них сохраняется локальная сходимость при переносе с задач линейного программирования на задачи полуопределенного программирования. Как известно, иногда такое обобщение нарушает сходимость [27]. Использование операторов векторизации, элиминационных и дупли-цирующих матриц позволяет обойти проблемы с симметричностью приращений в численных методах решения системы условий оптимальности, а за счет выбора начальной точки и длины шага можно добиться того, чтобы построенные методы являлись методами внутренней точки.

В работе использованы некоторые результаты из теории матриц, в частности, способы работы с операторами векторизации, элиминацион-ными и дуплицирующими матрицами (см. [64, 21, 49, 70]).

Основные результаты диссертации опубликованы в четырех работах [56, 58, 59, 61], а также доложены и обсуждены на следующих конференциях и семинарах:

• 52, 53, 54 научные конференции МФТИ, ноябрь 2009-2011, Москва;

• VI Московская международная конференция по исследованию операций, октябрь 2010, Москва;

• 15я Байкальская международная школа-семинар "Методы оптимизации и их приложения июнь 2011, пос. Листвянка, озеро Байкал;

• VII Всероссийская научная конференция "Математическое моделирование развивающейся экономики и экологии"(ЭКОМОД-2012), июль 2012, Киров.

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

Мп — п-мерное евклидово пространство; ж1, х2,., хп] — вектор х еЖп с координатами хг, 1 < г ^ п; ж, у) = Хл=1 х%Уг ~ евклидово скалярное произведение;

0П — нулевой п-мерный вектор;

Опт — нулевая матрица размеров п х т; — единичная матрица порядка п;

Ат — транспонированная матрица А;

А~1 — матрица, обратная к А;

А\ — определитель квадратной матрицы А;

А1//2 — квадратный корень матрицы А;

8> — кронекеровское произведение;

Т>п — дуплицирующая матрица;

Сп — элиминационная матрица; а) — диагональная матрица с вектором а на диагонали; <5>п — пространство симметричных матриц порядка п

Заключение

Итак, в диссертации получены следующие результаты:

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

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

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

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

5. Проведены вычислительные эксперименты на тестовых задачах (рандомизированные данные малой и средней размерности), которые подтвердили корректность работы данных методов, а также проведен сравнительный анализ скорости их работы.

Отметим также ряд остающихся открытыми вопросов, то есть, направления дальнейших исследований:

1. добавление регулировки длины шага в полученные ньютоновские методы.

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

3. Проведение экспериментов на задачах большой размерности из библиотеки ББРЫВ [6] и более новой библиотеке, предложенной в [17].

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

СПИСОК ИСПОЛЬЗОВАННЫХ источников

1. F. Alizadeh. Interior point methods in semidefinite programming with applications to combinatorial optimization // SIAM Journal on Optimization - 1995 - V. 5 - P. 13-51.

2. F. Alizadeh, J.-P.F. Haeberly, M.L. Overton. Complementarity and nondegeneracy in semidefinite programming // Mathematical Programming., Series B. - 1997. - V. 77, № 2. - P. 129-162.

3. F. Alizadeh, J-P.A. Haeberly, and M.L. Overton. Primal-dual interior-point methods for semidefinite programming. Convergence rates, stability and numerical results. // SIAM Journal on Optimization —1998 — V. 8 - P. 746-768.

4. R. Bellman and K. Fan. On systems of linear inequalities in Hermitian matrix variables. // Proceedings of Symposia in Pure Mathematics — 1963 - V. 7.

5. A. Ben-Tal and A. Nemirovsky Lectures on Modern Convex Optimisation: Analysis, Algorithms, Engineering Applications. // MPS-SIAM Series on Optimisation. SIAM, Philadelphia, 2000.

6. B. Borchers. SDPLIB 1.2, A Library of Semidefinite Programming Test Problems. // Optimization Methods and Software. — 1999 — V. 11(1) — P. 683-690.

7. M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. // Journal of Assoc. Comput. Mach. — 1995 -V. 42-P. 1115-1145.

8. M.X. Goemans. Semidefinite programming in combinatorial optimization. // Math. Programming — 1997 — V. 79 — P. 143162.

9. A. J. Goldman and A. W. Tucker. Theory of linear programming. // Linear inequalities and related systems — 1956 — Princeton University Press. Annals of Mathematics Studies — №. 38 — P. 53-97.

10. C. Helmberg, F. Rendí, R. J. Vanderbei, and H. Wolcowicz. An interior-point method for semidefinite programming. // SIAM Journal on Optimization - 1996 - V. 6, № 2 - P. 342-361.

11. N. Karmarkar. A new polynomial-time algorithm for linear programming // Combinatorica - 1984 - V. 4 - P. 373-395.

12. E. de Klerk, J. Peng, C. Roos, and T. Terlaky. A scaled Gauss-Newton primal-dual search direction for semidefinite optimization. // SIAM Journal on Optimization - 2001 — V. 11 № 4 - P. 870-888.

13. E. de Klerk, C. Roos, and T. Terlaky. Infeasible-start semidefinite programming algorithms via self-dual embeddings. // Fields Institute for Research in Mathematical Sciences, Communications Series — 1998 - V. 18 -P. 215-236.

14. E. de Klerk, C. Roos, and T. Terlaky. On primal-dual path-following algorithms in semidefinite programming. // New trends in Mathematical Programming - 1998 — P. 137-157.

15. E. de Klerk, C. Roos, and T. Terlaky. Primal-dual potential reduction methods for semidefinite programming using affine scaling directions. // Appl. Numer. Math. - 1999 - V. 29 - P. 335-360.

16. E. de Klerk. Aspects of Semidefinite Programming. Interior Point Algorithms and Selected Applications // Kluwer Academic Publishers - 2002.

17. E. de Klerk, and R. Sotirov. A new library of structured semidefinite programming instances. // CentER Discussion Paper Tilburg University, The Netherlands, August 2008.

18. M. Kojima, S. Shindoh and S. Hara. Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. // SIAM Journal on Optimization — 1997 — V. 7 — P. 86125.

19. J. B. Lasserre. Linear programming with positive semi-definite matrices. // Tech. Report LAAS-94099, Laboratoire d'Analyse et d'Architecture des Systemes du CNRS — 1995.

20. M. Laurent, F. Rendl. Semidefinite Programming and Integer Programming // Report PNA-R0210, CWI, Amsterdam — 2002.

21. J.R. Magnus. The elimination matrix: some lemmas and applications // SIAM J. Alg. Disc. Meth. - 1980. - V. 1, № 4. - P. 422-449.

22. R. D. C. Monteiro. Polynomial convergence of primal-dual algorithms for semidefinite programming based on Monteiro and Zhang family of directions. // SIAM Journal on Optimization — 1998 — V. 8 — P. 797-812.

23. R. D. C. Monteiro. Primal-dual path-following algorithms for semidefinite programming. // SIAM Journal on Optimization — 1997 — V. 7 — P. 663-678.

24. R. D. C. Monteiro and T. Tsuchiya. Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming. // SIAM Journal on Optimization — 1999 — V. 9 — P. 551-577.

25. R. D. C. Monteiro. Polynomiality of primal-dual algorithms for semidefinite linear complementarity problems based on theKojima-Shindoh-Hara family of directions. // Mathematical Programming — 1999 - V. 84 - P. 39-53.

26. R. D. C. Monteiro and Y. Zhang. A unified analysis for a class of path-following primal-dual interior-point algorithms for semidefinite programming. // Mathematical Programming — 1998 — V. 81 — P. 281-299.

27. M. Muramatsu, R. J. Vanderbei. Primal-dual affine scaling algorithm fails for semidefinite programming. // Mathematics of operations research — 1999 - V. 24 - P. 149-175.

28. Yu. Nesterov and A. Nemirovsky. Interior Point Polynomial Algorithms in Convex Programming // SIAM Publications, SIAM, Philadelphia — 1994 - 405 p.

29. Y. Nesterov and A. Nemirovsky. An interior point method for generalized linear-fractional programming // Math. Programming, Series B. — 1991.

30. Y. Nesterov and A. Nemirovsky. Interior-point polynomial methods in convex programming. //Studies in Applied Mathematics, SIAM, Philadelphia - 1994 — V .13.

31. Y. E. Nesterov and M. J. Todd. Self-scaled barriers and interior-point methods for convex programming // Mathematics of Operations Research - 1997 - V. 22 - P. 1-42.

32. Y. E. Nesterov and M. J. Todd. Primal-dual interior-point methods for self-scaled cones. // SIAM Journal of Optimization — 1998 — V. 8 — P. 324-364.

33. Y.E. Nesterov and B.T. Polyak. Cubic regularization of Newton method and its global performance.// Math. Program., Ser. A — 2006 — V. 108 - P. 177-205.

34. G.Pataki. Cone-LP's and semi-definite programs: facial structure, basic solutions, and the simplex method. // Tech. report, GSIA, Carnegie-Mellon University — 1995.

35. F. Rendl, R. J. Vanderbei, and H. Wolkowicz. Max-min eigenvalue problems, primal-dual interior point algorithms, and trust region subproblems. // Optim. Methods Softw. - 1995 - V. 5 — P. 1-16.

36. M.J. Todd. A study of search directions in primal-dual interior-point methods for semidefinite programming. // Optim. Methods Software — 1999 -V. 11-P. 11-46.

37. M.J. Todd, K.C. Toh, and R.H. Tutuncu. On the Nesterov-Todd direction in semidefinite programming. // SIAM Journal on Optimization — 1998 -V. 8 № 3 - P. 769-796.

38. M.J. Todd. Semidefinite optimization, manuscript // School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, USA - 2001.

39. L. Vandenberghe. Semidefinite programming // SIAM Rev. — 1996. — V. 38. - P. 49-95.

40. L. Vandenberghe and S. Boyd. Applications of semidefinite programming. // Appl. Numer. Math., - 1999 - V. 29 № 3 - P. 283-299.

41. H. Wolkowicz. Handbook of Semidefinite Programming / H. Wolkowicz, R. Saigal, L. Vandenberghe (eds). — Kluwer Academic Publishers, 2000.

- 656 p.

42. H. Wolkowicz. Semidefinite programming approaches to the quadratic assignment problem. // Nonlinear Assignment Problems: Algorithms and Applications - 2000 - V. 7 - P. 143-174.

43. H. Wolkowicz. Duality for semidefinite programming. // Encyclopedia of Optimization. Kluwer Academic Publishers, Boston, 2001.

44. Y. Zhang. On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. // SIAM Journal on Optimization - 1998 - V. 8 - P. 365-386.

45. Арнольд В.И. О матрицах, зависящих от параметров / В.И. Арнольд // УМН. - 1971. - Т. 26, вып. 2(158). - С. 101-114.

46. Необходимое условие в оптимальном управлении /А.П. Афанасьев, В.В. Дикусар, А.А. Милютин, С.В. Чуканов // М.: Наука, 1990.

47. Продолжение траекторий в оптимальном управлении // М.: Эдито-риал УРСС, 2005. - 263 с.

48. Бабынин М.С., Жадан В.Г. Барьерно-проективный метод для полуопределенного программирования. - Сообщения по прикладной математике. М.: ВЦ РАН, 2007.

49. Гантмахер Ф.Р. Теория матриц. — Издание 5-е. / М.: Физматлит, 2004

- 560с.

50. Дикин И.И. Метод внутренних точек в линейном и нелинейном программировании / И.И. Дикин. — М.: URSS, 2009. — 120 с.

51. Дикин И.И. Сходимость последовательности векторов двойственных переменных при исследовании одной задачи полуопределенного программирования // Кибернетика и системный анализ. 2003. № 2. С. 156-163.

52. Дикин И.И. Итеративное решение задач линейного и квадратичного программирования// Докл. АН СССР — 1967. — Т. 174 — №4 - С. 747-748.

53. Евтушенко Ю.Г., Жадан В.Г. Двойственные барьерно-проективные и барьерно-ньютоновские методы для линейного программирования // Журнал вычисл. матем. и матем. физики. — 1994. — Т. 36, № 7.

- С. 30-45.

54. Жадан В.Г. Двойственный мультипликативно-барьерный метод для полуопределенного программирования. М.: ВЦ РАН, 2009.

55. Орлов A.A. О численных методах решения задач полуопределенного программирования и примерах задач, для которых они являются неэффективными// Труды 52-й научной конференции МФТИ, Часть VII, Том 1 / МФТИ - М.-Долгопрудный, 2009,- С. 120-122.

56. Жадан В.Г., Орлов A.A. Двойственный метод Ньютона для линейной задачи полуопределенного программирования // Оптимизация и приложения. - 2010. М.: ВЦ РАН. — С. 87-108.

57. Орлов A.A. Двойственный метод Ньютона для задачи полуопределенного программирования// Труды 53-й научной конференции МФТИ, Часть VII, Том 1 / МФТИ - М.-Долгопрудный, 2010,- С. 75-77

58. Жадан В.Г., Орлов A.A. О сходимости двойственного метода Ньютона для линейной задачи полуопределенного программирования. // Известия Иркутского государственного университета. — 2011. — Т.4

- № 2. - С. 75-90.

59. Жадан В.Г., Орлов A.A. Двойственные методы внутренней точки для линейной задачи полуопределенного программирования. // Журнал вычисл. матем. и матем. физики. — 2011. — Т. 51, № 12. — С. 21582180.

60. Жадан В.Г., Орлов A.A. Допустимый и общий двойственные методы внутренней точки для линейной задачи полуопределенного про-граммирования//Тезисы 15й Байкальской международной школы-семинара "Методы оптимизации и их приложения—Т.2 "Математическое программирование—С. 81-86.

61. Жадан В.Г., Орлов A.A. Допустимый двойственный метод внутренней точки для линейной задачи полуопределенного программирования. // Автоматика и телемеханика. — 2012. — № 2. — С. 25-40.

62. Зоркальцев В.И. Об одном классе алгоритмов внутренних точек / В.И. Зоркальцев // Журнал вычисл. матем. и матем. физики. — 2009.

- Т. 49, № 12. - С. 2114-2130.

63. Измайлов А.Ф., Солодов М.В. Численные методы оптимизации. / М.: Физматлит, 2003.

64. Магнус Я.Р. Матричное дифференциальное исчисление с приложениями к статистике и эконометрике / Я.Р. Магнус, Ч. Нейдеккер. — М.: Физматлит, 2002. — 496 с.

65. Ортега Дж. Итерационные методы решения систем нелинейных уравнений со многими неизвестными / Дж. Ортега, В. Рейнболдт.

- М.: Мир, 1975. - 558 с.

66. Поляк Б.Т. Метод Ньютона и его роль в оптимизации и вычислительной математике.// Труды ИСА РАН. - 2006. — Т. 28, С. 44-62.

67. Поляк Б.Т., Щербаков П.С. Рандомизированный метод решения задач полуопределенного программирования.// Стохастическая оптимизация в информатике. — 2006. - Т. 2, № 1-1, С. 38-70.

68. Тыртышников Е.Е. Матричный анализ и линейная алгебра. М.: Физ-матлит, 2007.

69. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании.// ЖВМ и МФ, 1980, Т.20, № 1. С. 51-69.

70. Хорн Р., Джонсон Ч. Матричный анализ. / М.: Мир, 1989 — 655с.