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

Пержабинский, Сергей Михайлович

Алгоритмы внутренних точек с квадратичными аппроксимациями тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Пержабинский, Сергей Михайлович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Иркутск МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

4840604

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

ПЕРЖАБИНСКИЙ Сергей Михайлович

АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК С КВАДРАТИЧНЫМИ АППРОКСИМАЦИЯМИ

01.01.09 - дискретная математика и математическая кибернетика

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

Иркутск-2011

2 И ЮН 2011

4848834

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Иркутский государственный университет»

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор технических наук,

профессор Зоркальцев Валерий Иванович

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

кандидат физико-математических наук, доцент Веников Анатолий Исаакович

Институт вычислительной математики и математической геофизики СО РАН

Защита состоится 17 июня 2011 г. в 14:00 на заседании диссертационного совета Д.212.074.01 в Иркутском государственном университете по адресу: 664003, г. Иркутск, бульвар Гагарина, 20.

С диссертацией можно ознакомиться в библиотеке Иркутского государственного университета (г. Иркутск, бульвар Гагарина, 24).

Автореферат разослан "_16_" мая 2011г.

Ученый секретарь диссертационного совета,

канд. физ.-мат.наук, доцент Ж^^^х7 /Антоник В.Г./

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

Известно, что алгоритмы внутренних точек являются высокоэффективными процедурами решения задач математического программирования. При этом в особый класс выделяются алгоритмы внутренних точек, в которых поиск направления улучшения решения основывается на идее стимулирования движения вдоль границ области допустимых по ограничениям-неравенствам решений. Это обуславливает оригинальность и эффективность таких методов, но в то же время затрудняет их теоретическое обоснование. Пионерные разработки этих алгоритмов были осуществлены в СССР в 60 - 70-х гг. прошлого века С.М. Анцызом, И.И. Дикиным, Ю.Г. Евтушенко, В.Г. Жаданом, В.И. Зор-кальцевым.

Повышенный интерес к методам внутренних точек возник в 80-х годах прошлого века благодаря работам Л.Г. Хачияна, Д.Б. Юдина, A.C. Немировского, Ю.Е. Нестерова над полиномиальными методами и созданию в 1984 году Н. Кармаркаром полиномиального алгоритма внутренних точек для решения задач линейного программирования. Это послужило импульсом для появления большого числа публикаций, посвященных теоретическим и экспериментальным исследованиям алгоритмов внутренних точек. Из зарубежных ученых, занимавшихся этой тематикой, отметим А. Адлера, Л. Висенте, Ю. Йе, М. Коджимо, Н. Меджиддо, Ш. Мицуно, Р. Монтейро, М. Тодца, Т. Тсучия.

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

Алгоритмы внутренних точек обсуждаемого типа успешно используются с 70-х гг. прошлого века при реализации ряда моделей энергетики в Институте систем энергетики им. Л.А. Мелентьева СО РАН (ИСЭМ СО РАН). При этом для моделей с нелинейными ограничениями применяются процедуры итеративной линеаризации. Вполне естественно ожидать, что в тех случаях, когда вычисление вторых производных функций в ограничениях не трудоемко, использование в алгоритмах внутренних точек квадратичных аппроксимаций этих функций позволит повысить эффективность вычислительного процесса. Основная задача

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

В диссертации исследуется одно из приложений методов внутренних точек - модель оценки дефицита мощности электроэнергетических систем (ЭЭС). Модель является составной частью методики анализа надежности ЭЭС, разработанной и развиваемой в ИСЭМ СО РАН. Методика построена на базе статистических испытаний (метод Монте-Карло). В модели потери мощности при ее передаче по межузловым связям задаются в виде квадратичных функций от объема передаваемой мощности. Это обуславливает нелинейность балансовых ограничений. В связи с этим возникает необходимость доказательства существования и единственности решения в модели, возможности ее сведения к задаче выпуклого программирования. Для данной модели актуально ускорение процесса вычислений, поскольку это позволяет повысить количество рассчитываемых вариантов состояний ЭЭС и тем самым повысить качество анализа надежности ЭЭС.

Цели работы

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

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

3. Теоретическое исследование модели оценки дефицита мощности ЭЭС с квадратичными функциями в ограничениях. Исследование возможности применения алгоритма внутренних точек с квадратичными аппроксимациями для реализации модели.

Научная новизна

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

Впервые предложена модификация модели оценки дефицита мощности электроэнергетических систем в виде задачи выпуклого программирования. Исследована проблема существования и единственности решения в данной модели.

Методы исследования

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

Основные результаты диссертации, выносимые на защиту

1. Разработано семейство алгоритмов внутренних точек с квадратичными аппроксимациями ограничений. Осуществлено теоретическое обоснование одного алгоритма из этого класса.

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

3. Проведены теоретические исследования модели оценки дефицита мощности ЭЭС с нелинейными ограничениями. Предложена и теоретически обоснована модификация модели в виде задачи выпуклого программирования. Доказано, что оптимальное распределение дефицита мощности по узлам системы будет единственным. Единственность распределения дефицита гарантирует однозначность оценок рассчитанных показателей надежности ЭЭС. Для нахождения минимального дефицита мощности в модели реализован алгоритм внутренних точек с квадратичными аппроксимациями ограничений. Алгоритм показал высокую вычислительную эффективность.

Теоретическая и практическая значимость работы

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

2. Разработанная на базе алгоритма внутренних точек с квадратичными аппроксимациями вычислительная программа передана на внедрение в программно-вычислительный комплекс «Янтарь», созданный в ИСЭМ СО РАН, для анализа надежности электроэнергетических систем.

3. Доказано, что модель оценки дефицита мощности представима в виде задачи выпуклого программирования. Это позволяет эффективно применять теорию и методы выпуклой оптимизации для исследования и реализации модели.

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

Апробация работы

Исследования выполнялись в рамках грантов РФФИ № 05-01-00587 («Развитие теории и методов решения систем линейных и квадратичных неравенств с приложением к моделям энергетики») и № 09-01-00306 («Квадратичная оптимизация и ее приложение к моделям энергетики»). Основные результаты докладывались на студенческих конференциях ИМЭИ ИГУ (2005 - 2009), на конференциях научной молодежи ИСЭМ СО РАН (2005 - 2010), XIII и XIV Байкальских международных школах-семинарах «Методы оптимизации и их приложения» (Иркутск, 2005,2008), IX Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Кемерово, 2008), Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2009), Российской конференции «Дискретная оптимизация и исследование операций» (республика Алтай, 2010), II Международной школе-семинаре «Нелинейный анализ и экстремальные задачи» (Иркутск, 2010), Шестой азиатской международной школе-семинаре «Проблемы оптимизации сложных систем» (Казахстан, 2010). Диссертация обсуждалась на научных семинарах в ИСЭМ СО РАН, Институте динамики систем и теории управления СО РАН, Институте вычислительной математики и математической геофизики СО РАН, Институте математики им. С.Л. Соболева СО РАН, Институте математики и механики УрО РАН.

Публикации и личный вклад автора

По теме диссертации опубликовано 17 научных работ. Наиболее значимые результаты представлены в работах [1-13]. В число указанных публикаций входят 6 статей [1-6] из Перечня ведущих рецензируемых журналов и изданий ВАК РФ (2011 г.), 5 статей [7-8, 11-13] в научных сборниках, 2 полных текста докладов [9,10] в материалах международных конференций.

Работы [3-6, 9] выполнены в нераздельном соавторстве с научным руководителем. Из совместных публикаций [3, 4] в диссертационную работу включены результаты, полученные автором самостоятельно и не затрагивающие интересы других соавторов.

Структура и объем работы

Диссертационная работа состоит из введения, трех глав, заключения, списка литературы, содержащего 99 наименований, и одного приложения. Общий объем работы составляет 120 страниц, включая 2 рисунка и 10 таблиц.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

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

Ш->ш, Х = {хеЯп:Ах = Ь, х>0}. (1)

леХ

Здесь А - матрица размера тхп,Ь- вектор из Ят.

Пусть в начале итерации к = 0,1,2.....заданы параметр д. > 0 и

вектор хк еЯ" такой, что Ахк =Ь, х*>0. Итеративный переход осуществляется по формуле хм =х к+ЛкАхк.

Для идеализированного метода логарифмической барьерной функции направление спуска вычисляется по правилу

Ахк = а^тт|/0(хк + Ах)-цк £\п(хк + Ах/): ААх = 01. (2)

Шаг вдоль направления Ахк находится по формуле

Хк =агёт1п{/0(У + АЛх*): хк +АДх* >(1-у>*}

л>0

при заданном у е (0,1). Из неравенства хк > 0 следует, что хы > 0.

Метод логарифмической барьерной функции для более общего класса задач оптимизации подробно рассматривался А. Фиакко и Г. Мак-Кормиком. Известно, что если выбранная последовательность цк такая,

что ¡лк 0 при к—>со, то последовательность векторов хк сходится к множеству оптимальных решений задачи (1), если таковые имеются.

При практической реализации алгоритма нет смысла в точном решении вспомогательной задачи (2). Уместно воспользоваться

аппроксимацией этой задачи. Получаем следующую вспомогательную задачу поиска направления улучшения решения:

Дх* = аг8шт /0(х* + Дх) - н ¿^ + : ЛДх = 0 , (3)

здесь /0 - некоторая аппроксимация целевой функции /0 в точке хк (например, квадратичная).

Аппроксимация логарифмической штрафной функции породила в (3)

п Дх,

две составляющие. Одна из них £—— стимулирует при выборе

направления корректировки решения к «отталкиванию» от границ множества допустимых решений по условию х £ 0.

я (Д*,-)2 *

Вторая составляющая £ , стимулирует при выборе Дх к

движению «вдоль» ограничений-неравенств х > О, особешю и в большей степени по тем компонентам, по которым текущее значение х* более

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

Дх* = агётт{/0(х* + Дх) +1| Дх : ЛДх = 0}, (4)

где

»4 «Ё- ,4

Н a j

- квадрат евклидовой нормы вектора Дх с весовыми коэффициентами dj -(х*)2, j' = l,...,п. Если функция /0(х) линейная, то алгоритм внутренних точек, в котором поиск направления Дх осуществляется по правилу (4), является вариантом алгоритма внутренних точек И.И. Дикина. В зарубежной литературе такой алгоритм внутренних точек принято называть affine scaling method. Наряду с указанным могут использоваться и другие правила формирования весовых коэффициентов, например,

dj = {х*У,т№ 7=1.....п.

Отметим, что во многих методах оптимизации в целевой функции задачи поиска направления улучшения решения присутствует квадрат

нормы искомого вектора. При этом используется одна и та же норма на всех итерациях. Принципиальное отличие правила (4) состоит в том, что норма || • ||4 изменяется по итерациям за счет весовых коэффициентов.

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

Рассмотрим задачу нелинейного выпуклого программирования /0О)->тт, (5)

ЛГ = {*€ЛП: х<х<х, /¡(х)<0, г = 1,...,т}. (6)

Заданы векторы х, х из Я" (причем х<х) и выпуклые дважды дифференцируемые функции /¡(х), 1 = 0т.

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

:/,(*)<(),/ = 1,...,/я, х<х<х).

Будем считать, что т\Хфф и задан вектор из ШХ. В рассматриваемом вычислительном процессе последовательность векторов хк из нйХ вырабатывается по правилу

хм =хк+АкАхк. (7)

Здесь ¿ = 0,1,2,..., - номер итерации, Ах* - вектор спуска, Хк- шаг корректировки.

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

Если с1- 0, то дальнейшие вычисления прекращаются, т.к. хк - точка минимума функции /0 (х). Далее будем считать, что ск * 0.

После этого находится матрица Ак размера тхп, строками которой являются градиенты функции /¡(х), 1 = 1, ...,т. Затем вычисляется взвешенная сумма матриц вторых производных функций /¡(х), / = 0,..., т,

1=1

где у,ы - приближения на итерации к-1 к множителям Лагранжа нелинейных ограничений задачи (5), (6). На начальной итерации можно положить V,0 = 1, ¡' = 1,..., т.

Затем определяем векторы весовых коэффициентов с1к еЛ", кк е Ят. Их компоненты должны удовлетворять неравенствам

Здесь

у* у=1,...,и,

о, о - некоторые непрерывные неубывающие функции положительного аргумента, удовлетворяющие двум условиям: О<гг(/)<а{г), У/>0;

при некоторых с > О, М > 0 для всех Г е (0, г].

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

= 1.....я, 1=1,...,т. (8)

Обозначим

^ =сЙа2(^), II к =<Иа%{}1к) диагональные матрицы размера ихп и тх т с компонентами векторов с1к и Ь.к на главной диагонали.

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

Вектор Дх* определим как результат решения вспомогательной задачи минимизации квадратичной выпуклой функции от векторов Ахей" У1геЯт

(ск)т Ах + ^АхтВкАх +1АхтD^Ax + ~^THkz -> min, (9)

при линейных ограничениях-равенствах

АкАх - z. (10)

В целевой функции задачи (9), (10) составляющие AxTDkl Ах, zTH'kz (по аналогии с задачей (4)) стимулируют при выборе Ахк к движению «вдоль» границ множества векторов, удовлетворяющих неравенствам х<х<х, f{(х)<0, г = ],...,от. Составляющая АхтВкАх представляет вторые производные в аппроксимации функций /,. (х), i = 0,...,m.

Обозначим и* вектор множителей Лагранжа этих ограничений. Определим вектор приближений к множителям Лагранжа нелинейных ограничений исходной задачи

v* = тах{0, и*}, / = 1,..., от. Множество номеров /, при которых ик < 0, обозначим 1к.

Вспомогательная задача (9), (10) сводится к решению системы линейных уравнений с симметрической положительно определенной матрицей. Возможны два варианта вычислений векторов Ахк, zk,uk.

Один из них основывается на решении системы линейных уравнений с матрицей размера пхп

{Bk + D-kl+Alirk,A^ = -ck. (И)

Найдя в результате решения системы (11) вектор &хк, определяем векторы

zk =Ак Ахк,

„к - ии -Нк z .

Система (11) следует из задачи безусловной минимизации

(ckf Ах + i АхтВк Ах + ^ ДxTDlxAx + ^АхтАктЩ1АкАх min,

к которой приходим в результате подстановки вектора z (из условия (10)) в целевую функцию (9).

Второй вариант вычислений основан на решении системы размера

mxm

{Ак{Вк + Ht)u = ~Ak(Bk +Dk1)~1ck. (12)

Вычислив ик, находим вектор

Ахк =-(В,+D'klrl(ATkuk +ск)

и по формуле (10) - вектор zk. Система (12) - результат решения задачи (9), (10) методом неопределенных множителей Лагранжа.

Второй из двух вариантов вычислений предпочтительней в том случае, когда т<п и нахождение обратной матрицы (Вк + Dkl)~' не трудоемко (например, если функции fi(х), i = 0,...,m, сепарабельные). Шаг корректировки вычисляется следующим образом:

1. Я,4 = /тах{Я:хк + ЛАхк еХ, Я>0}, у- заданный параметр из интервала (0,1);

2. если 1к Ф ф, то = тах{Я: ft(xk + ЛАхк) <, /,(**), ieIk,0<Ä<tf};

3. если 1к = ф, то = jtf;

4. Лк = argmin /„(** + ЯДх*).

Oä/li^

Правила нахождения шага Як гарантируют, что вектор хы будет находиться в irAX.

В качестве критерия останова можно использовать выполнение следующих двух условий: векторы v*, ак, ßk близки к допустимому решению двойственной задачи, для векторов хк, vk, ак, ßk с заданной точностью выполняются условия дополняющей нежесткости. Здесь а) =max{0, = тах{0, qk), j = 1,..., я,

где

qk=-{Bk+D?)Ax.

Векторы ar*, ßk являются приближениями на итерации к к множителям Лагранжаограничений х<х.

Экспериментальные исследования алгоритма внутренних точек с квадратичными аппроксимациями, в котором весовые коэффициенты определяются по правилу (8), проводились на серии из 50 задач разной размерности. В численном эксперименте решались задачи вида (5), (6) с квадратичными строго выпуклыми функциями /¡(х), / = 0,..., м. Эксперименты отличались размерностью задач и количеством ограничений. Задачи решались алгоритмом внутренних точек с использованием квадратичных аппроксимаций и алгоритмом внутренних точек, основывающимся на линеаризации. В алгоритме внутренних точек, базирующемся на линеаризации, полагалось Вк=Е, к = 0,1,2,..., где Е -единичная матрица. В сравниваемых алгоритмах использовалось значение параметра у, равное 0,6. Результаты расчетов (минимальное, максимальное, среднее число итераций) представлены в табл. 1 и 2.

Таблица 1

Число итераций, необходимых для решении тест овых задач алгоритмом внутренних точек, базирующимся на линеаризации

Число Число Число итераций

переменных ограничений Максимальное Минимальное Среднее

3 2 147 7 55

10 5 250 36 106

20 10 361 67 148

40 20 397 80 173

Таблица 2 Число итераций, необходимых для решения тестовых задач алгоритмом внутренних точек с квадратичными аппроксимациями

Число Число Число итераций

переменных ограничений Максимальное Минимальное Среднее

3 2 61 7 24

10 5 118 21 51

20 10 128 29 61

40 20 155 34 82

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

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

Будем считать, что целевая функция линейна: при заданном сей",

сф О

/й(х) = стх.

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

ЛхеЛ", г е Ят, удовлетворяющих условиям А{х){^Х-2- О,

сгДх = -1.

Здесь А(х) -матрица размера тхп, строками которой являются градиенты функций /,(*), 1 = 1,..., т.

Линейное многообразие Ь2(х) состоит из векторов qeRn, иеВ.т, удовлетворяющих условию д-(А(х))Ти = с.

Пусть Ь- линейное многообразие в Я". Вектор s€¿ назовем опорным вектором многообразия Ь, если не существует вектора уеЬ такого, что 3{у) с J{s), .¡{у) , где J{y) = {у: у] ф 0} - множество номеров ненулевых компонент вектора у.

С изменением вектора х могут меняться значения опорных векторов линейных многообразий (х), Ьг (х). Предположим, что объединения по всем х, удовлетворяющим х£хйх, множеств опорных векторов многообразий ¿^(дг), Ь2(х) являются ограниченными множествами.

Задачу (5), (6) назовем невырожденной, если для любого Зс е X либо не существует, либо существует единственный набор векторов «6Л™, а е К", для которых выполняются соотношения

иЛ(х) = 0, / = 1,...,/я,

= 7 = 1.-..,п,

аД*/~*/) = 0> 7 = 1> •••. иВ диссертации приводится доказательство следующей теоремы. Теорема 1. Пусть

а) задача (5), (6) невырождена;

б) целевая функция линейна;

в) функции /¡(х), 1 = 1 ,...,т, еепарабельные;

г) объединения по всем х, удовлетворяющим условию х<х<х, множеств опорных векторов линейных многообразий ^(х), Ь7 (х) ограничены;

д) существует г > 0 такое, что Лк ^ т, к-1, 2.....

Тогда существуют векторы х е X, и еКт, аеИ", /3 еЛ" такие, что хк —>5с, ик -»и, ак ->а, /}к ->Д при к->°о.

Вектор х является оптимальным решением, а векторы и, а, р-множителями Лагранжа ограничений задачи (5), (6).

В третьей главе исследуется модель оценки дефицита мощности в электроэнергетической системе. В 70-х годах прошлого века под руководством академика АН СССР Ю.Н. Руденко была разработана методика анализа надежности ЭЭС, базирующаяся на методе многовариантных статистических испытаний. Методика состоит из трех блоков: вероятностного блока, в котором формируются случайным образом возможные состояния ЭЭС; блока оценки дефицита мощности сформированных расчетных состояний (модель оценки дефицита мощности); блока вычисления показателей надежности ЭЭС, в котором обрабатывается информация, накопленная в результате работы первых двух блоков. В указанной методике модель оценки дефицита мощности электроэнергетической системы занимает центральное место. Первые варианты модели оценки дефицита мощности ЭЭС, разработанные в ИСЭМ СО РАН, представлялись в виде задачи о максимальном потоке.

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

Рассмотрим схему электроэнергетической системы, состоящей из п узлов и некоторого набора связей между ними. Заданы располагаемая мощность хп нагрузка у, в 1-ом узле ЭЭС, предел пропускной способности линии электропередачи, связывающей узлы / и у. Считается, что для всех /' и у Зс,->0, у ¡'¿О, 1у> 0. Если Щ=0 при некоторых I и у, то поток мощности из узла г в узел у фактически не возможен.

Переменными задачи являются: х: - используемая мощность, у-покрываемая нагрузка в узле I, г у - поток мощности из узла г в узел у.

Требуется минимизировать суммарный дефицит мощности в системе

Ш-у^-^тш, (13)

1=1

учитывая балансы мощности в узлах

+ г = 1,..., и, (14)

>1 >1

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

0<у,<й,г = 1,...,«, (15)

0<Х; <Х(, 1=1,..., п, (16)

= 7 = 1,...,и. (17)

Здесь - коэффициент потерь на потоки мощности из узла ] в узел г. Коэффициенты а&- для всех»и] должны удовлетворять условию

где е -некоторая величина из интервала (0, 1). Это условие означает то, что каждая единица мощности, передаваемая из узла / в узел _/, достигает узла у с положительным значением при любом е [0, г у ].

Множество допустимых решений задачи (13) - (17), как правило, невыпукло (за исключением некоторых тривиальных случаев). Для представления задачи (13) - (17) в виде эквивалентной задачи выпуклого программирования заменим ограничения (14) на следующие:

х^у^Ы-а^^^-Ъц ^0, / = 1(18)

Множество векторов, удовлетворяющих ограничениям (15) - (18), является выпуклым.

Задачу (13) - (17) будем называть исходной задачей минимизации дефицита мощности. Задачу (13), (15) - (18) будем называть расширенной задачей минимизации дефицита мощности. Множество допустимых решений расширенной задачи содержит множество решений исходной задачи минимизации дефицита мощности. В диссертации приводится доказательство следующего утверждения.

Теорема 2. Пусть значения переменных у„ х^г^, 1=1

_/ = 1 ,...,п, являются оптимальным решением задачи (13), (15) - (18). Тогда существуют такие х,, г^, что значения переменных ур г,-,-, г = 1,..., п, ] = 1,..., п составляют оптимальное решение задачи (13) -(17).

Из теоремы 2 и указанного выше соотношения множества допустимых решений исходной и расширенной задачи минимизации дефицита мощности следует справедливость обратного утверждения: если значения переменных у1, х1, г у, г = 1,..., п, } =1,..., п, составляют

оптимальное решение исходной задачи минимизации дефицита мощности (13) - (17), то они составляют и оптимальное решение расширенной задачи минимизации дефицита мощности (13), (15) - (18).

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

покрываемым нагрузкам yt и соответственно по величинам дефицита мощности yt - yi во всех узлах i = 1,..., п.

Задача (13), (15) - (18) имеет решение, так как множество допустимых решений не пусто (векторы у= 0, х=0, 2=0 составляют допустимое решение), выпукло и ограничено (в силу условий (15) - (17)), целевая функция линейна. Из существования решения в задаче (13), (15) -(18) следует (согласно теореме 1) существование решения в задаче (13) -(17). В диссертации доказана теорема.

Теорема 3. Решение задачи (13), (15) - (18) единственно по переменным у¡, i = 1,..., п.

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

В диссертации показано, что для задачи (13), (15) - (18) выполняется условие ограниченности объединений множеств опорных векторов линейных многообразий Ь2 при всех значениях переменных из диапазонов, определяемых условиями (15) - (17). Условия б), в) теоремы 1 для задачи (13), (15) - (18) выполняются автоматически.

До недавнего времени задача (13) - (17) решалась в программно-вычислительном комплексе «Янтарь» на базе алгоритма внутренних точек, основывающегося на линеаризации. В диссертации представлено описание алгоритма внутренних точек с квадратичными аппроксимациями для решения задачи (13), (15)-(18).

Проведены сравнительные расчеты тестовых примеров, основанных на схемах реальных электроэнергетических систем. Для тестирования алгоритмов при помощи датчика случайных чисел были сформированы серии из пятидесяти режимов для двух схем ЭЭС. Рассматривалась расчетная схема ЭЭС № 1, состоящая из 7 узлов и 7 связей, и схема ЭЭС № 2, содержащая 23 узла и 39 связей между ними. Схема ЭЭС №1 представляет укрупненную схему единой электроэнергетической системы России, схема ЭЭС №2 - схему электроэнергетической системы Тюменской области.

Тестовые примеры рассчитывались алгоритмом внутренних точек с квадратичными аппроксимациями и алгоритмом внутренних точек, базирующимся на линеаризации. В расчетах использовалось значение параметра у, равное 0,6. В табл. 3, табл. 4 указано минимальное, максимальное и среднее число итераций, потребовавшееся для решения всех тестовых задач для заданных схем ЭЭС.

Таблица 3

Количество итераций для решения тестовых задач,

сконструированных на основе схемы ЭЭС №1

Алгоритм внутренних точек Число итераций

Минимальное Максимальное Среднее

Базирующийся на линеаризации 15 87 25

С квадратичными аппроксимациями 15 36 22

Таблица 4

Количество итераций для решения тестовых задач, сконструированных на основе схемы ЭЭС №2

Алгоритм внутренних точек Число итераций

Минимальное Максимальное Среднее

Базирующийся па линеаризации 28 238 56

С квадратичными аппроксимациями 25 81 39

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК

[1] Пержабинский С.М. Алгоритм внутренних точек, использующий квадратичные аппроксимации / С.М. Пержабинский ÍÍ Современные технологии. Системный анализ. Моделирование. - 2008. - Т. 18. - №3. -С.97-101.

[2] Пержабинский С.М. Расчет дефицита мощности электроэнергетической системы алгоритмом внутренних точек, использующим квадратичные аппроксимации / С.М. Пержабинский // Современные технологии. Системный анализ. Моделирование. — 2009. - Т. 24. - №4. -С.117-122.

[3] Пержабинский С.М. Модель оценки дефицита мощности электроэнергетической системы с учетом квадратичных потерь мощности в линиях электропередач / В.И. Зоркальцев, Л.М. Лебедева, С.М. Пержабинский // Сиб. журн. вычислит, математики. - 2010. - Т. 13. - №3. -С.285-295.

[4] Пержабинский С.М. Минимизация дефицита монщости в ЭЭС с учетом потерь мощности в линиях электропередачи / В.И. Зоркальцев,

Г.Ф. Ковалев, Л.М. Лебедева, С.М. Пержабинский // Электричество. -2010. - №9. - С.56-60.

[5] Пержабинский С.М. Модель оценки дефицита мощности электроэнергетической системы / В.И. Зоркальцев, С.М. Пержабинский // Изв. Иркут. гос. ун-та. Серия Математика. - 2010. - Т. 3. - № 3. - С.80-92.

[6] Пержабинский С.М. Модель оптимизации дефицита мощности электроэнергетической системы / В.И. Зоркальцев, С.М. Пержабинский // Управление большими системами. - 2010. - Специальный выпуск 30.1 «Сетевые модели в управлении». - С.ЗОО-318.

Прочие публикации

[7] Пержабинский С.М. Решение систем двусторонних линейных неравенств с минимальным значением энергетических норм / С.М. Пержабинский // Системные исследования в энергетике: Тр. молод, учен. ИСЭМ СО РАН. - Иркутск: ИСЭМ СО РАН, 2004. - Вып. 34. - С. 184-189.

[8] Пержабинский С.М. Алгоритмы решения нелинейных задач, учитывающие погрешности линеаризации / С.М. Пержабинский // Системные исследования в энергетике: Тр. молод, учен. ИСЭМ СО РАН. -Иркутск: ИСЭМ СО РАН, 2006. - Вып. 36. - С.242-244.

[9] Пержабинский С.М. Оптимизация на основе линеаризации с учетом квадратичной аппроксимации / В.И. Зоркальцев, С.М. Пержабинский // Труды III Всероссийской конференции «Проблемы оптимизации и экономические приложения». - Омск: Изд-во ОмГТУ, 2006. - С.30-31.

[10] Пержабинский С.М. Решение задач выпуклого программирования алгоритмом внутренних точек, использующим квадратичные аппроксимации / С.М. Пержабинский // Труды XIV Байкальской международной школы-семинара «Методы оптимизации и их приложения» - Иркутск, 2008. - Т. 1. - С.196-203.

[11] Пержабинский СМ. Решение задач квадратичного программирования алгоритмом оптимизации, использующим квадратичные аппроксимации / С.М. Пержабинский // Системные исследования в энергетике: Тр. молод, учен. ИСЭМ СО РАН. - Иркутск: ИСЭМ СО РАН,

2008. - Вып. 38. - С. 165-170.

[12] Пержабинский С.М. Нахождение минимального дефицита мощности алгоритмом внутренних точек, использующим квадратичные аппроксимации / С.М. Пержабинский // Системные исследования в энергетике: Тр. молод, учен. ИСЭМ СО РАН. - Иркутск: ИСЭМ СО РАН,

2009. - Вып. 39. - С. 198-206.

[13] Пержабинский С.М. Модель оценки дефицита мощности электроэнергетической системы с учетом потерь мощности в линиях электропередачи / С.М. Пержабинский // Системные исследования в энергетике: Тр. молод, учен. ИСЭМ СО РАН. - Иркутск: ИСЭМ СО РАН,

2010.-Вып. 40.-С.110-119.

Подписано к печати 10.05.2011. Формат 60 х 84 / 16 Усл. печ. л. 1. Заказ № 86. Тираж 120 экз.

Отпечатано полиграфическим участком ИСЭМ СО РАН 664033, Иркутск, ул. Лермонтова, 130

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Пержабинский, Сергей Михайлович

Введение.

Глава 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. Расчеты тестовых примеров, основанных на схемах реальных электроэнергетических систем.

Выводы.

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

Актуальность темы

Известно, что алгоритмы внутренних точек являются высокоэффективными процедурами- решения задач математического программирования. Из множества алгоритмов внутренних точек в особый класс выделяются алгоритмы, в которых поиск направления улучшения, решения4 основывается на идее стимулирования движения вдоль границ области допустимых по ограничениям-неравенствам решений. Это обуславливает оригинальность, и эффективность, этих методов, но в то же время затрудняет их теоретическое обоснование. Пионерные разработки таких алгоритмов были осуществлены в. СССР в 60 - 70-х гг. прошлого века С.М. Анцызом [1], И.И. Дикиным [12-15], Ю.Г. Евтушенко [16-18], В.Г. Жаданом [18, 20]; В.И. Зоркальцевым [14, 22-25, 27, 29].

Повышенный интерес к методам внутренних точек возник в 80-х годах прошлого века благодаря работам над полиномиальными методами Л.Г. Хачияна [51], Д.Б. Юдина [54], А.С. Немировского [39], Ю.Е. Нестерова [40] и созданию в 1984. году Н! Кармаркаром [71] полиномиального алгоритма внутренних точек для решения задач линейного программирования. Это послужило импульсом появления большого количества публикаций, посвященных теоретическим и экспериментальным исследованиям алгоритмов внутренних точек. Из, зарубежных ученых, занимавшихся этой тематикой, отметим А. Адлера [56, 80], Л. Висенте [62, 92, 93], Ю. Йе [97-99], М. Коджимо [72], Н. Меджиддо [77], Ш. Мицуно [72], Р. Монтейро [80, 81], М. Райт [95, 96], М. Тодда [87], Т. Тсучия [81, 89, 90], А. Фиакко [50, 67], А. Форсгрина [69].

Наиболее исследованы алгоритмы внутренних точек, основанные на идее стимулирования движения вдоль границ допустимой области, для задач линейного программирования. Известны также теоретические результаты по обоснованию алгоритмов внутренних точек этого типа для задач оптимизации с нелинейной целевой функцией при линейных ограничениях (в частности, для задач квадратичного программирования) [81, 90, 98]. Актуальной проблемой является теоретическое обоснование алгоритмов для задач с нелинейными ограничениями.

Алгоритмы внутренних точек обсуждаемого в диссертации типа успешно используются с 70-х гг. прошлого века при- реализации ряда моделей энергетики в Институте систем энергетики им: Л'.А. Мелентьева СО- РАН- (ИСЭМ СО РАН). При- этом для моделей с нелинейными ограничениями применяются процедуры итеративной линеаризации. Вполне естественно ожидать, что в тех случаях, когда вычисление вторых производных функций в ограничениях не трудоемко, использование в алгоритмах внутренних точек квадратичных аппроксимаций этих функций позволит повысить эффективность вычислительного процесса. Основная задача данной диссертации состоит в разработке, теоретическом и экспериментальном исследовании« алгоритмов внутренних точек, использующих квадратичные аппроксимации.

В диссертации исследуется одно из приложений методов внутренних точек - модель оценки дефицита мощности электроэнергетических систем (ЭЭС). Модель является составной частью методики анализа надежности ЭЭС, разработанной и развиваемой в ИСЭМ СО РАН [47]. Методика построена на базе метода статистических испытаний (метод Монте-Карло [78]). В модели потери мощности при ее передаче по межузловым связям задаются в виде квадратичных функций от объема передаваемой мощности. Это обуславливает нелинейность балансовых ограничений. Необходимо исследование существования и единственности решения в модели, возможности ее сведения к задаче выпуклого программирования. Для данной модели особенно актуально ускорение процесса вычислений, поскольку это позволяет повысить количество рассчитываемых вариантов состояний ЭЭС и тем самым повысить качество анализа надежности ЭЭС.

Цели работы

2. Программная реализация; экспериментальное исследование алгоритмов внутренних точек с квадратичными аппроксимациями.

Научная новизна

Методы исследований

Основные результаты, составляющие научную новизну работы и выносимые на защиту

1. Разработано семейство алгоритмов внутренних точек с квадратичными. аппроксимациями ограничений. Осуществлено теоретическое обоснование алгоритма из этого класса (при некоторых предположениях, в т.ч. о невырожденности задачи).

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

3. Проведены теоретические исследования модели оценки дефицита мощности ЭЭО с нелинейными? ограничениями. Предложена и теоретически обоснована модификация модели в виде задачи выпуклого программирования. Доказано, что оптимальное распределение дефицита мощности по узлам системы будет единственным. Единственность распределения дефицита гарантирует однозначность оценок рассчитанных показателей надежности ЭЭС. Для нахождения минимального дефицита мощности в модели реализован алгоритм внутренних точек с квадратичными аппроксимациями ограничений. Алгоритм имеет высокую вычислительную эффективность.

Теоретическая и практическая значимость работы'

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

3. Доказано, что модель оценки1 дефицита мощности представима в виде задачи» выпуклого программирования. Это позволяет эффективно применять теорию и методы выпуклой оптимизации* для исследования и реализации модели.

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

Апробация работы

Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2009), Российской конференции «Дискретная оптимизация и исследование операций» (республика Алтай, 2010), II Международной школе-семинаре «Нелинейный анализ и экстремальные задачи» (Иркутск, 2010), Шестой азиатской международной школе-семинаре «Проблемы оптимизации сложных систем» (Казахстан, 2010). Диссертация обсуждалась на научных семинарах в ИСЭМ СО РАН, Институте динамики систем и теории управления СО РАН, Институте вычислительной математики и математической геофизики СО РАН, Институте математики им. С.Л. Соболева СО РАН, Институте математики и механики УрО РАН.

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

Выводы

1. В данной главе представлена история создания и описание математических свойств вариантов модели оценки дефицита мощности, предназначенной для анализа надежности ЭЭС.

2. Для модели оценки дефицита мощности ЭЭС с квадратичными потерями мощности в ЛЭП предложен и теоретически обоснован способ представления модели в виде задачи выпуклого программирования.

3. Доказано, что распределение дефицита мощности по узлам электроэнергетической системы единственно. Однозначность распределения дефицита гарантирует однозначность оценок вероятности и математических ожиданий дефицита в< узлах системы после проведения расчетов.

4. Показано, что для задачи (3.1), (3.3) - (3.5), (3.16) выполняется* условие ограниченности объединений множеств опорных векторов линейных многообразий^ Ьх (г), Ь2 (г) при всех значениях переменных из диапазонов, определяемых условиями (3.5).

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

6. Результаты экспериментальных исследований подтвердили работоспособность алгоритма внутренних точек с квадратичными аппроксимациями и его модифицированного варианта. Тестовые расчеты показали пригодность алгоритмов для реализации модели оценки дефицита мощности с учетом ее квадратичных потерь в сетях. При этом алгоритмами внутренних точек с квадратичными аппроксимациями решение тестовых задач находилось * существенно быстрее (по числу итераций), чем алгоритмами внутренних точек, базирующимися только на линеаризации. Более того, лучшее результаты среди сравниваемых алгоритмов показал модифицированный алгоритм внутренних точек с квадратичными аппроксимациями.

Заключение

Сформулируем основные результаты диссертации.

1. Разработаны новые алгоритмы решения задач выпуклого программирования — алгоритмы внутренних точек с квадратичными аппроксимациями ограничений. Осуществлено теоретическое обоснование алгоритма из этого класса для решения задач выпуклого программирования с нелинейными ограничениями (при некоторых предположениях; в т.ч. о невырожденности задачи).

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

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

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

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Пержабинский, Сергей Михайлович, Иркутск

1. Анцыз С.М. Об одном численном методе решения задачи линейного программирования и некоторых ее обобщений / С.М. Анцыз, И.И. Дикин // Управляемые системы: Сб. науч. тр. — Новосибирск: ИМ СО АН СССР, 1969. Вып. 3. - С. 54-56.

2. Аоки М. Введение в методы оптимизации» / М. Аоки. М.: Наука, 1977.-343 с.

3. Булатов В.П. Методы погружения в задачах оптимизации / В.П. Булатов. Новосибирск: Наука, 1977. - 161 с.

4. Булатов В.П. Метод ортогональных симплексов и его приложения в выпуклом программировании / В.П. Булатов // Журн. вычислит, математики и мат. физики. 2008. - Т. 48. - №4. - С. 610-622.

5. Базара М. Нелинейное программирование. Теория и алгоритмы / М. Базара, К. Шетти. -М.: Мир, 1982. 573 с.

6. Васильев О.В. Лекции по методам оптимизации / О.В. Васильев. -Иркутск: Изд-во Иркут. ун-та, 1994. 344 с.

7. Васильев Ф.П. Методы оптимизации / Ф.П. Васильев. М.: Факториал Пресс, 2002. - 824 с.

8. Войтов О.Н. Исследование систем неравенств алгоритмами внутренних точек на задачах поиска допустимых режимов электроэнергетических систем / О.Н. Войтов, В.И. Зоркальцев, А.Ю. Филатов Иркутск: ИСЭМ СО РАН, 1997. - 30 с.

9. Данциг Дж. Линейное программирование, его применения и обобщения / Дж. Данциг. М.: Прогресс, 1966. - 600 с.

10. Дементьев В.Т. Задачи оптимизации иерархических структур / В.Т. Дементьев, А.И. Ерзин, P.M. Ларин, Ю.В. Шамардин. Новосибирск: Изд-во Новосиб. ун-та, 1996. - 167 с.

11. Демьянов В.Ф. Приближенные методы решения экстремальных задач / В.Ф. Демьянов, В.Н. Малоземов. Л.: Изд-во Ленингр. ун-та, 1968. -180 с.

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

13. Дикин И.И. О сходимости одного итерационного процесса / И.И. Дикин // Управляемые системы: Сб. науч. тр. Новосибирск: ИМ СО АН СССР; 1974.-Вып. 12.-С. 54-60.

14. Дикин И.И. Итеративное решение задач математического программирования (алгоритмы метода внутренних точек) / И.И. Дикин, В.И. Зоркальцев. Новосибирск: Наука, 1980. - 144 с.

15. Дикин И.И. Метод внутренних точек в линейном и нелинейном программировании / И.И. Дикин. М.: КРАСАНД, 2010.-120 с.

16. Евтушенко Ю.Г. Численные методы решения некоторых задач исследования операций / Ю.Г. Евтушенко, В.Г. Жадан // Журн. вычислит, математики и мат. физики. 1973. - Т. 13. - №3. - С. 583597.

17. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации / Ю.Г. Евтушенко. — М.: Наука, 1982.-432 с.

18. Евтушенко Ю.Г. Барьерно-проективные и барьерно-ньютоновские численные методы оптимизации (случай линейного программирования) / Ю.Г. Евтушенко, В.Г. Жадан. М.: ВЦ РАН, 1992.-76 с.

19. Еремин И.И. Теория линейной оптимизации / И.И. Еремин. -Екатеринбург: Изд-во «Екатеринбург», 1999. 312 с.

20. Жадан В.Г. Метод Ньютона с наискорейшим спуском для задач линейного программирования / В.Г. Жадан М.: ВЦ РАН, 1997. - 62 с.

21. Зангвилл У.И. Нелинейное программирование / У.И. Зангвилл. М.: Советское радио, 1973. — 312 с.

22. Зоркальцев В.И. Метод относительно внутренних точек / В.И. Зоркальцев. Сыктывкар: Коми филиал АН СССР, 1986. - 18 с.

23. Зоркальцев В.И. Алгоритмы внутренних точек в линейном программировании / В.И. Зоркальцев // Оптимизация, управление, интеллект. 1995.-№1. - С. 20-35.

24. Зоркальцев В.И. Модели оценки дефицита мощности электроэнергетических систем / В.И. Зоркальцев, Г.Ф. Ковалев, Л.М. Лебедева. -Иркутск: ИСЭМ СО РАН, 2000. 25 с.

25. Зоркальцев В.И. Алгоритмы оптимизации в конусе центрального пути / В.И. Зоркальцев // Журн. вычислит, математики и мат. физики. -2000. Т. 40. - №2. - С. 318-327.

26. Зоркальцев В.И. Системы линейных неравенств / В.И. Зоркальцев, М.А. Киселева. Иркутск: Изд-во Иркут. гос. ун-та, 2007. - 129 с.

27. Зоркальцев В.И. Об одном классе алгоритмов внутренних точек / В.И. Зоркальцев // Журн. вычислит, математики и мат. физики. 2009. - Т. 49. - №12. - С. 2114-2130.

28. Зоркальцев В.И. Минимизация дефицита мощности в ЭЭС с учетом потерь мощности в линиях электропередачи / В.И. Зоркальцев, Г.Ф. Ковалев, Л.М. Лебедева, С.М. Пержабинский // Электричество. 2010. -№9. с. 56-60.

29. Зоркальцев В.И. Модель оценки дефицита мощности электроэнергетической системы / В.И. Зоркальцев, С.М. Пержабинский // Изв. Иркут. гос. ун-та. Сер. «Математика». 2010. - Т. 3. - № 3. - С. 80-92.

30. Зоркальцев В.И. Модель оптимизации дефицита, мощности электроэнергетической системы / В.И. Зоркальцев, С.М. Пержабинский // Управление большими системами. 2010. - Специальный выпуск 30.1 «Сетевые модели в управлении». — С. 300-318.

31. Измаилов А.Ф. Численные методы, оптимизации: Учебное пособие / А.Ф. Измаилов, М.В. Солодов. М.: ФИЗМАТЛИТ, 2005. - 304 с.

32. Канторович Л.В. Математические методы организации и планирования производства / Л.В. Канторович. Л.: ЛГУ, 1939. - 68 с.

33. Ковалев Г.Ф. Комплекс моделей, оптимизации режимов расчетных состояний при оценке надежности электроэнергетических систем / Г.Ф. Ковалев, Л.М. Лебедева. Иркутск: ИСЭМ СО РАН, 2000. - 73 с.

34. Немировский A.C. Сложность задач и эффективность методов оптимизации / A.C. Немировский, Д.Б. Юдин. -М.: Наука, 1979. 383 с.

35. Нестеров ЮЕ. Эффективные методы в нелинейном программировании / Ю.Е. Нестеров. М. Радио и связь, 1989: - 301 с.

36. Поляк Б.Т. Введение в оптимизацию /Б.Т. Поляк.- М.: Наука, 1983. — 384 с.

37. Пшеничный Б.Н. Численные методы в экстремальных задачах / Б.Н: Пшеничный, Ю.М. Данилин. М.: Наука, 1975. - 319 с.

38. Пшеничный Б.Н. Метод линеаризации / Б.Н. Пшеничный. М.: Наука, 1983.- 136 с.

39. Рокафеллар Р. Выпуклый анализ7 Р. Рокафеллар. М.: Мир, 1973. -469 с.

40. Руденко Ю.Н. Надежность и резервирование в электроэнергетических системах / Ю.Н. Руденко, М.Б. Чельцов. — Новосибирск: Наука, 1974.-263 с.

41. Срочко В.А. Численные методы: Курс лекций / В.А. Срочко. -Иркутск: Изд-во Иркут: гос. ун-та, 2004. 205 с.

42. Фиакко А. Нелинейное программирование. Методы последовательной безусловной минимизации / А. Фиакко, Г. Мак-Кормик. М.: Мир, 1972.-240 с.

43. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании / Л.Г. Хачиян // Доклады АН СССР. 1979. - Т. 244. - С. 1093-1096.

44. Чукреев Ю.Я. Модели обеспечения надежности электроэнергетических систем / Ю.Я. Чукреев. Сыктывкар: Коми НЦ УрО РАН, 1995.-173 с.

45. Шор Н.З. Методы отсечения с растяжением пространства для решения задач выпуклого программирования / Н.З. Шор // Кибернетика. -1977. -№1.~ С. 94-95.

46. Юдин Д:Б. Информационная сложность и эффективные методы решения выпуклых экстремальных задач / Д.Б. Юдин, А.С. Немиров-ский // Экономика и математические методы. 1976. - Т. 12. -№ 2. -С. 357-369.

47. Absil P.A. Newton-KKT Interior-Point Methods for Indefinite Quadratic Programming / P.A. Absil, A.L. Tits // Computational Optimization and Applications. 2007. - №36. - Pp. 5-41.

48. Adler I. An implementation of Karmarkar's algorithm for linear programming problems / I. Adler, M. Resende, G. Veiga, N. Karmarkar // Mathematical programming. 1989. - №44. - Pp. 297-335.

49. Barnes E.R. A variation on Karmarkar's algorithm for solving linear programming problems / E.R. Barnes // Mathematical programming. -1986.-№36.-Pp. 174-182.

50. Boggs P.T. Sequential quadratic programming / P.T. Boggs, J.W. Tolle I I Acta Numerica. Cambridge, UK: Cambridge University Press, 1995. -Pp. 1-51. '

51. Bonnas J. The trust region affine interior point algorithm for convex and nonconvex quadratic programming / J. Bonnas, M. Bouhtou // Oper. Res. -1961.-№9.-Pp. 169-184.

52. Dennis J.E. Trust-region interior-point1 algorithms for minimization problems with simple bounds / J.E. Dennis, L.N. Vicente // Tech. Rep. TR94-42. 1995. - Pp. 1-10.

53. Gilbert J.C. Examples of ill-behaved central paths in convex optimization / J.C. Gilbert, C.C. Gonzaga, E. Karas // Mathematical Programming. -2005.-Vol. 103. — №1. — Pp. 63-94.

54. Gill P.E. On projected Newton barrier methods for linear programming and' an equivalence to Karmarkar's projective method / P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin, M.H. Wright // Mathematical Programming.-1986.-№36.-Pp. 183-209.

55. Gonzaga C.C. A primal affine-scaling algorithm for linearly constrained convex programs / C.C. Gonzaga, L.A. Carlos // Tech. report ES-238/90. -1990.-Pp. 1-17.

56. Hertog D. Interior Point Approach to Linear, Quadratic and Convex Programming: Algorithms and Complexity / D. Hertog. London, Kluwer Academic Publishers, 1994. - 209 pp.

57. Fiacco A.V. Barrier methods for nonlinear programming / A.V. Fiacco // Operations Research Support Methodology. New York, 1979. - Pp. 377440.

58. Ford L.R. Maximal flow through a network / L.R. Ford, D.R. Fulkerson // Canadian Journal of Mathematics. 1956. - №8. - Pp. 399-404.

59. Karmarkar N. A new polynomial-time algorithm for linear programming / N. Karmarkar // Combinatorica. 1984. - №4. - Pp. 373-395.

60. Kojima M. A primal-dual interior point algorithm for linear programming / M. Kojima, S. Mizuno, A. Yoshise // Progress in mathematical programming: interior point and related methods. New York: Springer Verlag, 1989.-Pp. 29-47.

61. Kuhn H.W. Nonlinear programming / H.W. Kuhn, A.W. Tucker // Proceedings of 2nd Berkeley Symposium. Berkeley: University of California Press, 1951. - Pp. 481-^92.

62. Lootsma F.A. Hessian matrices of penalty functions for solving constrained-optimization problems / F.A. Lootsma // Philips Res. Rep. -1969. -№24. Pp. 322-330.

63. Mangasarian O.L. The Fritz-John necessary optimality condition in the presence of equality and inequality constraints / O.L. Mangasarian, S. Fromovitz // J. Math. Anal. Appl. 1967. - №17. - Pp. 37-47.

64. Mascarenhas W. The affine scaling algorithm fails for stepsize 0.999 / W. Mascarenhas // SIAM J. Optim. 1997. - №1. - Pp. 34-46.

65. Megiddo N. Pathways to the optimal set in linear programming / N. Megiddo // Progress in mathematical programming: interior point and related methods. New York: Springer Verlag, 1989.-Pp. 131-158.

66. Metropolis N. The Monte Carlo Method / N. Metropolis, S. Ulam // Journal of the American statistical association. 1949. - Vol. 44. - №247. - Pp. 335-341.

67. Monma C.L. Computational experience with a dual affine variant of Karmarkar's method for linear programming / C.L. Monma, A.J. Morton. // Oper. Res. Letters 1987. - №6. - Pp. 261-267.

68. Monteiro R. Interior path-following primal-dual algorithms. Part 1: Linear programming / R. Monteiro, I. Adler // Mathematical* programming. -1989. -№44. -Pp. 27^19.

69. Monteiro R. Global convergence of the affine scaling algorithm for convex quadratic programming / R. Monteiro, T. Tsuchiya' // SIAM J. Optim. -1998.-Vol. 8. -№1. Pp. 26-58.

70. Nesterov Yu.E. Interior-Point Polynomial Algorithms in Convex Programming / Yu.E. Nesterov, A.S. Nemirovskii. Philadelphia: SIAM, 1994.-405 pp.

71. Nocedal J. Numerical Optimization / J. Nocedal, S.J. Wright. New York: Springer, 2006. - 664 pp.

72. Polyak R. Modified barrier functions (theory and methods) / R. Polyak // Mathematical programming. 1992. - №54. - Pp. 177-222.

73. Robinson S.M. Perturbed Kuhn-Tucker points and rates of convergence for a class of nonlinear programming algorithms / S.M. Robinson. // Mathematical programming. 1974. - №7. - Pp. 1-16.

74. Sun J. A convergence proof for an affme-scaling algorithm for convex programming without nondegeneracy assumptions / J. Sun // Mathematical programming. 1993. - №60. - Pp. 69-79.

75. Todd M. Combined phase I and phase II in a potential reduction algorithm for linear programming / M. Todd // Mathematical programming. 1993. -№59.-Pp. 133-150.

76. Tseng P. On the convergence of the affine-scaling algorithm / P. Tseng, Z.Q. Luo // Mathematical programming. 1992. - №56. - Pp. 301-319.

77. Tsuchiya T. Global convergence of the affine scaling methods for degenerate linear programming problems / T. Tsuchiya // Mathematical programming. 1991. - №52. - Pp. 377-404.

78. Tsuchiya T. Global convergence of the affine scaling algorithm-for primal degenerate strictly convex quadratic programming / T. Tsuchiya // Ann. Oper. Res. 1993. - №47. - Pp. 509-539.

79. Vanderbey R.J. Modification of Karmarkar's linear programming algorithm / R.J. Vanderbey, M.S. Meketon, B.A. Freedman // Algorithmica. -1986. — №1. Pp. 395-407.

80. Vicente L.N. Trust-region interior-point algorithms for a class for nonlinear programming problems: Thesis of Doctor of Philosophy / L.N. Vicente, Rise University. 1996. - 192 pp.

81. Vicente L.N. Local convergence of affine-scaling interior-point algorithm for nonlinear programming / L.N. Vicente // Computational Optimization and Applications. 2000. - №17. - Pp. 23-35.

82. Von Neumann J. Discussion of a maximization problem / J. Von Neumann. Princeton: Institute for Advanced Studies, 1947. - 10 pp.

83. Wright M.H. Interior methods for constrained optimization / M.H. Wright // Acta Numerica. New York: Cambridge University Press, 19921 - Pp. 341-407.

84. Wright M.H. The interior-point revolution in optimization: history, recent developments, and lasting consequences / M.H. Wright // Bulletin of the American mathematical society. 2004. - Vol. 42. - №1. - Pp. 39-56.

85. Ye Y. An extension of Karmarkar's projective algorithm and the trust region method for quadratic programming / Y. Ye // Progress in Mathematical Programming: Interior Point and Related Methods. Berlin: Springer-Verlag. - 1989. - Pp. 49-63.

86. Ye Y. An extension of Karmarkar's projective algorithm for convex quadratic programming / Y. Ye, E. Tse // Mathematical programming. -1989. -№44. -Pp. 157-180.

87. Ye Y. On an affine scaling algorithm for nonconvex quadratic programming / Y. Ye // Mathematical programming. — 1992. №56. - Pp. 285-300.

88. Ведущий научный сотрудник, д.т.н.