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

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

Автор: Филатов, Александр Юрьевич

Шифр специальности: 05.13.18

Научная степень: Кандидатская

Год защиты: 2001

Место защиты: Иркутск

Количество страниц: 123 с. ил

Артикул: 2285149

Автор: Филатов, Александр Юрьевич

Стоимость: 250 руб.

Содержание
Введение
Глава 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) неограниченна сверху на множестве допустимых решений этой задачи.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.267, запросов: 244