Алгоритмы внутренних точек с квадратичными аппроксимациями тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Пержабинский, Сергей Михайлович

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

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

Введение.

Глава 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]). В модели потери мощности при ее передаче по межузловым связям задаются в виде квадратичных функций от объема передаваемой мощности. Это обуславливает нелинейность балансовых ограничений. Необходимо исследование существования и единственности решения в модели, возможности ее сведения к задаче выпуклого программирования. Для данной модели особенно актуально ускорение процесса вычислений, поскольку это позволяет повысить количество рассчитываемых вариантов состояний ЭЭС и тем самым повысить качество анализа надежности ЭЭС.

Цели работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 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 раза быстрее, чем метод внутренних точек, использующий только линеаризацию ограничений.

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

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

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

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

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

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. Ведущий научный сотрудник, д.т.н.