Развитие алгоритмов внутренних точек и их приложение к системам неравенств

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

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

Глава 1. Краткий обзор алгоритмов внутренних точек в линейном программировании .

1.1. Теоретические основы линейной оптимизации.

1.2. Аффинномасштабирующие алгоритмы.

1.3. Полиномиальные алгоритмы.

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

2.1. Несколько вспомогательных утверждений

2.2. Описание и теоретическое исследование алгоритмов оптимизации в конусе скошенного пути.

2.3. Экспериментальное исследование алгоритмов

Глава 3. Решение систем уравнений и неравенств алгоритмами внутренних

3.1. Задача определения допустимых режимов электроэнергетических систем.
3.2. Аффинномасштабирующие алгоритмы применительно к решению линеаризованной подзадачи.Г..
3.3. Алгоритмы центрального и скошенного пути применительно к решению линеаризованной подзадачи.
Заключение
Список литературы


Исследования выполнялись в рамках грантов РФФИ №9 (“Разработка и теоретические исследования проективных алгоритмов оптимизации с приложением в задачах энергетики”) и №0 (“Развитие алгоритмов внутренних точек и их применение в задачах энергетики”). Основные результата опубликованы в научных работах, в том числе, в статьях, а также докладывались и обсуждались на конференциях научной молодежи ИСЭМ СО РАН (-), XI и XII международных Байкальских школах-семинарах “Методы оптимизации и их приложения” (Иркутск, , ), международных конференциях “Дискретный анализ и исследование операций” (Новосибирск, , ), международной конференции “Математическое программирование и приложения” (Екатеринбург, ), международной конференции “Распределенные системы: оптимизация и приложения” (Екатеринбург, ), на семинарах ИСЭМ СО РАН и ИДСТУ СО РАН. Линейная оптимизация [2], [] (поиск экстремума линейной функции при ограничениях в форме линейных неравенств) - один из важнейших разделов математики как в плане теоретических исследований, так и в плане практических приложений. Как математическая дисциплина линейная оптимизация ведет отсчет с основополагающей работы Л. В.Канторовича [], каждый из разделов которой посвящен моделированию конкретной экономической задачи. В этой же работе был представлен метод разрешающих множителей - прообраз разработанного в году Дж. Данцигом симплекс-метода [6]. Благодаря простоте реализации и высоким скоростным характеристикам модификации симплекс-метода стали наиболее распространенным способом решения задач линейного программирования. В то же время, симплекс-метод является далеко не единственным таким способом. В частности, статьями [8], [9], [] было порождено альтернативное направление - алгоритмы внутренних точек. Их название связано с тем, что, в отличие от симплекс-метода, перебирающего угловые точки многогранника допустимых решений, вычислительный процесс в алгоритмах внутренних точек происходит в относительной внутренности допустимого множества. Кроме того, вырабатываемая последовательность приближений сходится к относительно внутренней точке множества оптимальных решений. За рубежом повышенный интерес к алгоритмам внутренних точек возник в -х годах и был обусловлен созданием полиномиальных алгоритмов для задач линейного программирования. Понятие полиномиальной разрешимости класса задач играет основную роль в теории сложности. В работе Л. Г.Хачияна [] на основе использующейся в выпуклом программировании техники построения последовательности сокращающихся в объеме множеств [] было показано, что линейное программирование относится к классу полиномиально разрешимых задач. Несмотря на то, что алгоритм, исследуемый Хачияном, на практике показан невысокую скорость сходимости, результат Хачияна был крайне важен в теоретическом плане и способствовал последующим исследованиям в этой области. Кроме того, на основе используемой в [] техники впоследствии был разработан оригинальный класс полиномиальных алгоритмов погружения-отсечения [1], в последние годы существенно повысивших свою эффективность []. В году Н. Кармаркаром был создан первый полииомианьный алгоритм внутренних точек [] для задачи линейного программирования. Хотя анонсированное Кармаркаром утверждение, что программная реализация его метода решает практические и тестовые задачи линейного программирования быстрее, чем имеющиеся программные реализации симплекс-метода, в результате проведенных рядом исследователей экспериментов не подтвердилось [], [], статья вызвала огромный интерес к алгоритмам внутренних точек, следствием которого было более работ, посвященных данному направлению, выполненных за последующие лет учеными всего мира. Следует отметить, что зарубежные ученые часто воспроизводили и переоткрывали сделанное в России И. И.Дикиным, Ю. Г.Евтушенко, В. И.Зор-кальцевым, В Г. Жаданом и другими в - годах. Rn, b 6 Rm, А - матрица размерности т х п, rank А = т. X = ArgmincTx, U = Arg max bTu . Введем функцию от векторов х € R n, u е Rт /(х,и) = стх- Ьти. Xjgjiu). У=! A1 uj = с1 х - (Ати) х = стх - uTAx = стх - bTu . X = 0, U = 0. Тогда X = 0, U = 0. Х = 0, U *0. Тогда Х = 0, U = 0, целевая функция задачи (2) неограниченна сверху на множестве допустимых решений этой задачи.