Диплом, курсовая, контрольная работа
Помощь в написании студенческих работ

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

Диссертация: Алгоритмы внутренних точек с квадратичными аппроксимациями
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Повышенный интерес к методам внутренних точек возник в 80-х годах прошлого века благодаря работам над полиномиальными методами Л. Г. Хачияна, Д. Б. Юдина, А. С. Немировского, Ю. Е. Нестерова и созданию в 1984. году Н! Кармаркаром полиномиального алгоритма внутренних точек для решения задач линейного программирования. Это послужило импульсом появления большого количества публикаций, посвященных… Читать ещё >

Содержание

  • Глава 1. Алгоритмы внутренних точек в выпуклом программировании
    • 1. 1. Теоретические основы выпуклой оптимизации
    • 1. 2. Алгоритмы внутренних точек
    • 1. 3. Варианты алгоритма И. И. Дикина в линейном и квадратичном программировании
    • 1. 4. Последовательное квадратичное программирование
  • Выводы
  • Глава 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−587 («Развитие теории и методов решения систем линейных и квадратичных неравенств с приложением к моделям энергетики») и № 09−01−306 («Квадратичная оптимизация и ее приложение к моделям энергетики»). Основные результаты докладывались на студенческих конференциях ИМЭИ ИГУ (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. Предложена модификация алгоритма внутренних точек с квадратичными аппроксимациями. В модифицированном алгоритме допускается нарушение нелинейных ограничений-неравенств. Экспериментальные исследования алгоритма на модели оценки дефицита мощности показали его вычислительную эффективность. Направлением дальнейших исследований является теоретическое обоснование модифицированного алгоритма внутренних точек с квадратичными аппроксимациями ограничений.

Показать весь текст

Список литературы

  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. — С. 583 597.
  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. 377 440.
  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. 2719.
  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, 19 921 — 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. Ведущий научный сотрудник, д.т.н.
Заполнить форму текущей работой

На отлично!