Алгоритмы внутренних точек с квадратичными аппроксимациями

• Автор: Пержабинский, Сергей Михайлович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Иркутск
• Количество страниц: 120 с. : ил.

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

Глава 1. Алгоритмы внутренних точек в выпуклом программировании

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

1.2. Алгоритмы внутренних точек

1.3. Варианты алгоритма И.И. Дикина в линейном и квадратичном программировании

1.4. Последовательное квадратичное программирование . . 36 Выводы

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

2.1. Описание семейства алгоритмов внутренних точек с квадратичными аппроксимациями

2.2. Экспериментальные исследования

2.3. Теоретическое обоснование

Выводы
Глава 3. Модель оценки дефицита мощности электроэнергетической системы
3.1. История создания и развития модели оценки дефицита мощности электроэнергетических систем
3.2. Модель оценки дефицита мощности электроэнергетической системы с учетом квадратичных потерь мощности
в линиях электропередачи

3.3. Алгоритм внутренних точек с квадратичными аппроксимациями
3.4. Модификация алгоритма внутренних точек с квадратичными аппроксимациями
3.5. Расчеты тестовых примеров, основанных на схемах
реальных электроэнергетических систем
Выводы
Заключение
Список литературы
Приложение Справка об использовании результатов диссертации в Институте систем энергетики им. Л.А. Мелентьева СО РАН

Введение
Актуальность темы
Известно, что алгоритмы внутренних точек являются высокоэффективными процедурами- решения задач математического программирования. Из множества алгоритмов внутренних точек в особый класс выделяются алгоритмы, в которых поиск направления улучшения решения основывается на идее стимулирования движения вдоль границ области допустимых по ограничениям-неравенствам решений. Это обуславливает оригинальность и эффективность этих методов, но в то же время затрудняет их теоретическое обоснование. Пионерные разработки таких алгоритмов были осуществлены в. СССР в 60 - 70-х гг. прошлого века С.М. Анцызом [1], И.И. Дикиным [12—15], Ю.Г. Евтушенко [16-18],
В.Г. Жаданом [18, 20]; В.И. Зоркальцевым [14, 22-25, 27, 29].
Повышенный интерес к методам внутренних точек возник в 80-х годах прошлого века благодаря работам над полиномиальными методами Л.Г. Хачияна [51], Д.Б. Юдина [54], A.C. Немировского [39], Ю.Е. Нестерова [40] и созданию в 1984, году IE Кармаркаром [71] полиномиального алгоритма внутренних точек для решения задач линейного программирования. Это послужило импульсом появления большого количества публикаций, посвященных теоретическим и экспериментальным исследованиям алгоритмов внутренних точек. Из. зарубежных ученых, занимавшихся этой тематикой, отметим А. Адлера [56, 80], Л. Висенте [62, 92, 93], Ю. Йе [97-99], М. Коджимо [72], Н. Меджиддо [77], Ш. Мицуно [72], Р. Монтейро [80, 81], М. Райт [95, 96], М. Тодда [87], Т. Тсучия [81, 89, 90], А. Фиакко [50, 67], А. Форсгрина [69].
Наиболее исследованы алгоритмы внутренних точек, основанные на идее стимулирования движения вдоль границ допустимой области, для задач линейного программирования. Известны также теоретические

Варианты алгоритма И.И. Дикина для решения задач квадратичного программирования
Рассмотрим задачу квадратичного программирования
cTx + ^xTQx-> min (1-39)
при условиях
Ах~Ь, (1-40)
х> 0. (1.41)
Здесь с ei?", Ъ е Rm, Q — симметрическая неотрицательно определенная
матрицра размера тхп, А — матрица размера тхп.
На основе алгоритма (1.22) — (1.24) зарубежными авторами [81, 86] был разработан алгоритм внутренних точек решения задачи (1.39) - (1.41), в котором хы, к- 0, 1, 2,..., геометрически определяется, как точка минимума функции (1.39) на эллипсоиде с центром в точке хк
сТ х + ~^хт Qx -» min,
при условиях
А(х-хк)~ 0,
п(Х,.-Хк)

у-« (*;)

Здесь величина /3 геометрически означает радиус эллипсоида, /9 е (0,1). Следует отметить, что алгоритмы внутренних точек данного типа для решения задачи (1.39) - (1.41) рассматривались ранее отечественными авторами [14].
В работах [81, 86] доказывается глобальная сходимость этого алгоритма при некоторых предположениях, в т.ч., что матрица А полного ранга, множество оптимальных решений задачи (1.39) — (1.41) не пусто и ограничено, относительная внутренность множества допустимых решений