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

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

ДВОЙСТВЕННЫЕ И ПРЯМО-ДВОЙСТВЕННЫЕ МЕТОДЫ

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

ЗАДАЧ ПОЛУОПРЕДЕЛЕННОГО ПРОГРАММИРОВАНИЯ

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

кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2012

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

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

Официальные оппоненты: Доктор физико-математических наук, профессор Афанасьев Александр Петрович, Институт системного анализа РАН, заведующий отделом Доктор физико-математических наук, профессор Измайлов Алексей Феридович, факультет ВМиК МГУ им.

М. В. Ломоносова, профессор

Ведущая организация: Институт проблем управления им. В. А. Трапезникова РАН

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

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

Автореферат разослан «» ноября 2012 г.

Ученый секретарь диссертационного совета Федько О. С.

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

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

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

Хотя формулировка задачи SDP была впервые дана Р.

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

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

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

Монтейро).

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

Среди российских авторов помимо Ю. Е. Нестерова и А. С.

Немировского следует отметить вклад Б. Т. Поляка, П. С. Щербакова, И. И. Дикина в развитие методов решения задач 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 n обозначает пространство симметричных матриц порядка n, S его подмножество, состоящее из положительно полуn определенных матриц. Скалярное произведение матриц L и M одного размера вводится как след матрицы LT M и обозначается L M. Прямая задача SDP имеет следующий вид:

где матрицы X, C и Ai,1 i m принадлежат множеству S n. Неравенство X 0 означает, что матрица X является положительно полуопределенной, то есть, X S.

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

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

Точка X S называется допустимой в задаче (P), если выполn няется условие: Ai X b, i 1...m.

Точка [u,V ] называется допустимой в задаче (D), если V S и выполняется условие:

Предположим, что решения задач (P) и (D) существуют и что матрицы Ai,1 i m, линейно независимы.

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

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

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

Если X * и [u*,V* ] - решения задач (P) и (D), то можно указать ортогональную матрицу Q и векторы * и *, такие, что X * QD(* )QT, V* QD(* )QT, где D(a) - диагональная матрица с вектором a на диагонали. Для собственных значений * и * тогда выполняется равенства: ** 0, i 1,..., n. Если для каждого i 1,..., n одно из значений * или * положительно, то решения X * и V* называются строго комплементарными.

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

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

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

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

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

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

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

Утверждение 1. Для симметричных матриц X 0 и V равенство X V 0nn возможно в том и только том случае, когда XV VX 0nn.

С учетом утверждения 1 система оптимальных условий (1) может быть переписана как При построении методов используются операторы векторизации матриц. Если M квадратная матрица порядка n, то символом vecM обозначается прямая сумма ее столбцов, то есть векторстолбец длины n 2, в котором последовательно один под другим располагаются столбцы матрицы M. Для симметричных матриц имеет смысл вместо вектор-столбца vecM рассматривать векторстолбец vechM. В него также помещаются последовательно сверху-вниз столбцы матрицы M, но не полностью, а только их нижние части, начиная с диагонального элемента. Аналогичным образом определяется вектор-столбец vecsM. От vechM он отличается только тем, что все элементы, не стоящие на диагонали матрицы M при помещении в vecsM умножаются на два.

Введем обозначение k (n) n(n 1) / 2. Длина векторов vechM и vecsM равна k (n).

Для перехода от вектора vecM к вектору vechM и для обратного перехода используются специальные элиминационные и дуплицирующие матрицы. Элиминационная матрица Ln для каждой квадратной матрицы M порядка n осуществляет преобразование Ln vecM vechM. Напротив, дуплицирующая матрица Dn для каждой симметричной матрицы M порядка n осуществляет преобразование Dn vechM vecM.

Используя введенные обозначения, а также известную формулу vecABC (C A)vecB, где символ обозначает произT ведение матриц по Кронекеру, перепишем систему равенств и неравенств (2) в следующем виде:

Здесь через Avec обозначена m n2 матрица, строками которой являются векторы vecAi, V [V I n I n V ]/ 2 - кронекеровская полусумма матрицы V, I n - единичная матрица порядка n.

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

где (V ) Avec Avec V. Переходя к вектору vechX, получаем следующую зависимость прямых переменных от двойственных:

где (V ) Avech Avecs LnV Dn.

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

Пусть RA - подпространство в S n, порожденное матрицами Ai, 1 i m и пусть RA - его ортогональное дополнение. Обозначим также X и V - касательные подпространства к S в точках X и V соответственно.

Определение (Ализаде, Хайберли, Овертон). Точка V называется невырожденной в двойственной задаче, если при некотором u m точка [u,V ] является допустимой и V RA S n. Допустимая точка X называется невырожденной в прямой задаче, если X RA S n.

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

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

Если пара [u,V ] удовлетворяет третьему равенству в системе нелинейных уравнений относительно m неизвестных:

[ Avecs1(V (u)) Avech I m ]b 0m.

Применим для решения системы (6) метод простой итерации:

В пространстве двойственной переменной V итерационный процесс (7) в векторном виде представим как:

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

или, после перехода от вектора vecX к вектору vechX, Здесь для упрощения записи введено обозначение F (u, vech(V )) Avechb (vechV Avechu vechC ).

Решая уравнение (10) относительно X получаем:

Переменная X теперь зависит от двух переменных u и V, т.е.

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

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

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

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

uk 1 uk k [b Avecs 1 (Vk ) F (uk, vechVk )], vechVk 1 vechVk k LnVk Dn 1 (Vk ) F (uk, vechVk ), Итерационные процессы (7), (8) и (14) будут являться методами внутренней точки при надлежащем выборе шага k 0, если потребовать, чтобы в начальной точке [u0,V0 ] выполнялось V0 0.

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

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

Отметим, что нуль-пространство у матрицы V совпадает с нуль-пространством ее квадрата. Поэтому, в принципе, первое равенство в (3) можно было бы заменить на (V ) vecX 0 и построить соответствующие итерационные процессы, в которых вместо матрицы V использовалась бы матрица (V )2. Однако, такие процессы уже могут не обладать локальной сходимостью во всем пространстве, даже при сделанных предположениях относительно решений задач (P) и (D).

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

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

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

Таким образом, чтобы определить (u ), следует найти матрицу Якоби от вектор-функции vechX (u ).

Обратимся к тождеству:

Дифференцируя его по u и используя равенство находим:

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

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

[ I m Avecs [ Avech Avecs LnVk Dn ]1 Avech ]b, где Vk V (uk ), X k X (uk ). Итерационный процесс (15) корректно определен, если на каждой итерации матрица (uk ) неособая.

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

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

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

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

Пусть l k (n) m, K1,..., Kl - линейно независимые матрицы в S n со свойством (vecsKi )T vechAj 0 i [1...l ], j [1...m].

Матрицы K1,..., Kl образуют базис в линейном подпространстве S n, ортогональном к подпространству, порожденному матрицами A1,..., Am. Обозначим через K vecs матрицу размера l k (n), строками которой являются векторы vecsKi.

Используя матрицу K vecs, перепишем систему оптимальных условий (3) в следующем виде:

где b Kvecs vechC.

Введем в рассмотрение вектор-функцию и рассмотрим систему содержащую 2k (n) уравнений и 2k (n) неизвестных.

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

где Выполнив дифференцирование, находим явный вид матрицы W1 ( X,V ) :

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

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

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

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

Учтем явный вид зависимости V (u ) C i 1 u i Ai и будем решать систему оптимальных условий в здаче SDP относительно переменных ( X, u ) :

Введем вектор-функцию и рассмотрим систему Данная система содержит k (n) m уравнений и k (n) m неизвестных. Будем решать систему (23) методом Ньютона:

где Матрица W2 ( X, u ) имеет следующий вид:

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

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

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

1. Задавались параметры n, m, r (где r rank (V* ) ), удовлетворяющие необходимому условию невырожденности точек X * и [u*,V* ] : k (n r ) m k (n) k (r ). Были проведены эксперименты для n от 2 до 50.

2. Генерировались случайным образом положительные числа 1,..., r и 1,..., nr и ортогональная матрица Q. После этого генерировалась пара задач (P) и (D), решением которой являютX * QDiag (0,...,0, 1,..., nr )QT и V* QDiag (1,..., r,0,...,0) QT, для этого:

A1,..., Am и случайный вектор u* [u*,..., u* ] 4. Задавался вектор b [b1,..., bm ] по правилам bi Ai X * 5. Задавалась матрица C по правилу C u* Ai V* В результате мы получали прямую и двойственную задачи полуопределенного программирования с известным решением X * и [u*,V* ]. На данной задаче проводились тесты допустимого варианта двойственного метода простой итерации из главы 2, двойственного ньютоновского метода из главы 3 и двух вариантов прямодвойственных ньютоновских методов из главы 4.

В ходе экспериментов в окрестности решения генерировалась случайным образом начальная точка. Для этого задавалось прираu || щение u :

либо 0.07. После этого определялись u0 u* u, V0 V (u0 ) и X 0 X (V (u0 )) по формуле (5). При генерации начальной точки одной из целей было получить относительно «равномерное» отклонение от решения по норме переменных X,V и u (под нормой матрицы здесь подразумевается норма по Фробениусу). Поэтому, || V0 V* ||. В случае, если оказывалось, что оба эти значения больV* || ше чем / 3, из построенной таким образом начальной точки осуществлялись итерации, причем, условием остановки являлось X k Vk 105. Если же хотя бы одно из них было меньше / 3, то генерация задач (P) и (D) осуществлялась повторно.

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

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

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

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

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

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

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

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

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

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

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

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

2. Жадан В.Г., Орлов А.А. Двойственный метод Ньютона для линейной задачи полуопределенного программирования// Оптимизация и приложения. – 2010. М.: ВЦ РАН. – С. 87- 3. Орлов А.А. Двойственный метод Ньютона для задачи полуопределенного программирования// Труды 53-й научной конференции МФТИ, Часть VII, Том 1 / МФТИ – М.Долгопрудный, 2010,– С. 75- 4. Жадан В.Г., Орлов А.А. О сходимости двойственного метода Ньютона для линейной задачи полуопределенного программирования// Известия Иркутского государственного университета.

– 2011. – Т.4 №2 – С. 75- 5. Жадан В.Г., Орлов А.А. Двойственные методы внутренней точки для линейной задачи полуопределенного программирования// Журнал вычисл. матем. и матем физики – 2011. – Т. №12 – С. 2158- 6. Жадан В.Г., Орлов А.А. Допустимый и общий двойственные методы внутренней точки для линейной задачи полуопределенного программирования//Тезисы 15й Байкальской международной школы-семинара «Методы оптимизации и их приложения»

- Т.2 «Математическое программирование» - Иркутск: РИО ИДСТУ СО РАН, 2011 - С. 81- 7. Жадан В.Г., Орлов А.А. Допустимый двойственный метод внутренней точки для линейной задачи полуопределенного программирования// Автоматика и телемеханика – 2012. – № – С. 25-

ДВОЙСТВЕННЫЕ И ПРЯМО-ДВОЙСТВЕННЫЕ МЕТОДЫ

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

ЗАДАЧ ПОЛУОПРЕДЕЛЕННОГО ПРОГРАММИРОВАНИЯ

АВТОРЕФЕРАТ

Подписано в печать 30.10.2012 Формат 60 84 1/16. Усл. печ. л. 1,0.

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)»

Отдел оперативной полиграфии «Физтех-полиграф»

141700, Московская обл., г. Долгопрудный, Институтский пер.,