Дальневосточный математический журнал

К содержанию выпуска


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


А. С. Величко

2012, выпуск 2, С. 160–170


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

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

Полный текст статьи (файл PDF)

Библиографический список

[1] И. И. Еремин, “О некоторых итерационных методах в выпуклом программировании”, Экономика и математические методы, 2:6 (1966), 870–886.
[2] И. И. Еремин, В. Л. Мазуров, Нестационарные процессы математического программирования, Наука, М., 1979.
[3] И. И. Еремин, “Методы фейеровских приближений в выпуклом программировании”, Математические заметки, 3:2 (1968), 217–234.
[4] Л. М. Брэгман, “Релаксационный метод нахождения общей точки выпуклых множеств и его применение для задач выпуклого программирования”, Журн. вычисл. матем. и матем. физики, 7:3 (1967), 620–631.
[5] Л. Г. Гурин, Б. Т. Поляк, Э. В. Райк, “Методы проекций для отыскания общей точки выпуклых множеств”, Журн. вычисл. матем. и матем. физики, 7:6 (1967), 1211–1228.
[6] Е. Г. Гольштейн, Е. Г. Третьяков, Модифицированные функции Лагранжа. Теория и методы оптимизации, Наука, М., 1989.
[7] H. H. Bauschke, J. M. Borwein, “On projection algorithms for solving convex feasibility problems”, SIAM Review, 38:3 (1996), 367–426.
[8] Y. Censor, W. Chen, P. L. Combettes, R. Davidi, G. T. Herman, “On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints”, Computational Optimization and Applications, 2012, no. 3, 1065–1088.
[9] Е. А. Бердникова, И. И. Еремин, Л. Д. Попов, “Распределенные фейеровские процессы для систем линейных неравенств и задач линейного программирования”, Автоматика и телемеханика, 2004, № 2, 16–32.
[10] И. И. Еремин, Л. Д. Попов, “Фейеровские процессы в теории и практике: обзор последних результатов”, Известия ВУЗов. Математика, 2009, № 1, 44–65.
[11] Е. А. Нурминский, “Использование дополнительных малых воздействий в фейеровских моделях итеративных алгоритмов”, Журн. вычисл. матем. и матем. физики, 48:12 (2008), 2121–2128.
[12] Е. А. Нурминский, “Фейеровские процессы c малыми возмущениями”, Доклады АН, 422:5 (2008), 601–605.
[13] C. Michelot, “A finite algorithm for finding the projection of a point onto the canonical simplex of Rn”, Journal of Optimization Theory and Applications, 50:1 (1986), 195–200.
[14] Е. А. Нурминский, “Проекция на внешне заданные полиэдры”, Журн. вычисл. матем. и матем. физики, 48:3 (2008), 387–396.
[15] Б. Т. Поляк, Введение в оптимизацию, Наука, М., 1983.
[16] Ю. Е. Нестеров, Введение в выпуклую оптимизацию, МЦНМО, М., 2010.
[17] И. И. Еремин, “Обобщение релаксационного метода Моцкина – Агмона”, Успехи матем. наук, 20:2 (1965), 183–187.
[18] Б. Т. Поляк, “Минимизация негладких функционалов”, Журн. вычисл. матем. и матем. физики, 9:3 (1969), 509–521.
[19] Н. З. Шор, “О скорости сходимости метода обобщенного градиентного спуска с растяжением пространства”, Кибернетика, 1970, № 2, 80–85.
[20] А. С. Величко, “Решение задач оптимизации методом последовательных проекций с различными способами выбора начального приближения и шаговых множителей”, св. о гос. рег. прог. для ЭВМ Росс. Фед. 2011614018 от 24.05.11; заявл. 06.04.11; опубл. 20.09.2011., RU ОБПБТ, 3, 319 с.
[21] E. D. Dolan, J. J. More, “Benchmarking optimization software with perfomance profiles”, Mathematical programming, 91:2 (2002), 201–213.

К содержанию выпуска