- Получены новые миноранты и нижние оценки для минимизации скалярных функций. Предложены новые миноранты, основанные на оценке спектра матрицы Гессе, разработан метод вычисления таких оценок. Для задач оптимизации с параллелепипедными ограничениями предложены новые миноранты, учитывающие необходимые условия оптимальности.
- В методе неравномерных покрытий предложены способы сокращения области поиска, основанные на построении дополнения покрывающего множества до параллелепипеда, позволяющие существенно повысить быстродействие метода.
- Метод неравномерных покрытий перенесен на задачи частично-целочисленного программирования, доказана корректность алгоритма.
- Для задачи многокритериальной оптимизации с параллелепипедны ми ограничениями доказаны новые свойства ε-Парето множества,устанавливающие связь между этим множеством, границей Парето и оболочкой Эджворта-Парето.
- Метод неравномерных покрытий для задач многокритериальной оптимизации обобщен на случай произвольных минорант, доказана сходимость метода.
- Для задач многокритериальной оптимизации с функциональными ограничениями введено новое понятие приближенного решения - множество ε, (δ-Парето и предложен алгоритм для его построения, доказана сходимость метода.
- На основе идей многокритериальной оптимизации введено понятие эффективной оболочки множества, показано, что эта оболочка содержится в его выпуклой оболочке. Введены понятия ε-эффективной границы и ε-оболочки множества, предложены методы их численного построения. Разработанные понятия и методы применены для задачи построения внешней границы рабочей области многосекционного робота-манипулятора с заданной точностью.
- Разработан подход к оценке сложности метода неравномерных покрытий, с помощью которого получены верхние оценки сложности различных вариантов этого метода для различных классов задач.
- Получены оценки сложности метода ветвей и границ для задачи о булевом ранце. Проведено экспериментальное исследование и сопоставление их точности.
- Исследован вопрос параллельной вычислительной сложности одной из возможных реализаций метода ветвей и границ. Получена общая оценка вычислительной сложности, не зависящая от конкретной задачи. Для задачи о сумме подмножеств получены асимптотические формулы для минимальной параллельной сложности, максимального параллельного ускорения и эффективности.
- Предложен подход к реализации детерминированных и гибридных методов глобальной оптимизации на многопроцессорных вычислительных комплексах, основанный на разделении вычислительной, коммуникационной и управляющей функциональности в программе. Разработан язык описания управления параллельным процессом поиска глобального экстремума, основанный на формализме конечных автоматов. Этот язык позволяет описывать как управление процессом оптимизации, так и балансировку вычислительной нагрузки между процессорами параллельной системы. Такой подход позволяет независимым образом реализовывать и отлаживать соответствующие компоненты, а также, облегчать процесс расширения программного комплекса за счет повторного использования ранее разработанных компонент.
- На основе разработанного подхода реализован программный комплекс для решения задач глобальной оптимизации на последовательных, параллельных и распределенных системах. В рамках этого программного комплекса были реализованы различные алгоритмы для решения задач конечномерной оптимизации с одним и несколькими критериями, проведены многочисленные эксперименты на различных вычислительных платформах. В частности, разработана и выполнена эффективная параллельная реализация метода ветвей и границ для задачи о булевом ранце с одним ограничением, превосходящая по скорости работы известные аналоги.
1.М.А. Посыпкин, И.Х. Сигал, Исследование алгоритмов параллельных вычислений в задачах дискретной оптимизации ранцевого типа. // ЖВМ и МФ, 45(10), С. 1801-1809, 2005.
2.М.А. Посыпкин, И.Х. Сигал, Оценки ускорения для некоторых вариантов параллельной реализации метода ветвей и границ// ЖВМ и МФ, 46(12), С. 2289-2304, 2006.
3.М.А.Посыпкин, Архитектура и программная организация библиотеки для решения задач дискретной оптимизации методом ветвей и границ на многопроцессорных вычислительных комплексах// Труды ИСА РАН, Т. 25, С. 18-25, 2005.
4.И.Х. Сигал, Я.Л. Бабинская, М.А.Посыпкин, Параллельная реализация метода ветвей и границ в задаче коммивояжера на базе библиотеки BNB-Solvcr// Труды ИСА РАН, Т. 25, С. 26-36.
5.А.П. Афанасьев, В.В. Волошинов, М.А. Посыпкин, И.Х. Сигал, Д.А. Хуторной, Программный комплекс для решения задач оптимизации методом ветвей и границ на распределенных вычислительных системах// Труды ИСА РАН, Т. 25, С. 5-17.
6.М.А. Посыпкин, А.С. Хританков, О понятии производительности в распределенных вычислительных системах// Труды ИСА РАН, Т. 32, 2008 г., С. 26-32.
7.P.M. Колпаков, М.А. Посыпкин, Асимптотическая оценка сложности метода ветвей и границ с ветвлением по дробной переменной для задачи о ранце// Труды ИСА РАН, Т. 32, 2008 г., С. 109-136.
8.P.M. Колпаков, М.А. Посыпкин, Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце// Труды ИСА РАН, Т. 32, 2008 г., С. 137-158.
9.М.А. Посыпкин, Параллельный эвристический алгоритм глобальной оптимизации // Труды ИСА РАН, Т. 32, 2008 г., С. 166-179.
10.М.А. Посыпкин, И.Х. Сигал, Комбинированный параллельный алгоритм решения задачи о ранце, Известия РАН, Теория и системы управления, №4, 2008 , С. 50-58.
11.М.А. Посыпкин, Мультиплатформенный программный комплекс для решения задач оптимизации в распределенной вычислительной среде. // Проблемы вычислений в распределенной среде / Под ред. СВ. Емельянова, А.П. Афанасьева. Труды ИСА РАН, Т. 46. - М.: КРАСАНД, 2009. С. 24-43.
12.А.Л. Игнатьев, М.А. Посыпкин, И.Х. Сигал, Решение задачи коммивояжера на многопроцессорных системах с общей и распределенной памятью // Проблемы вычислений в распределенной среде / Под ред. СВ. Емельянова, А.П. Афанасьева. Труды ПСА РАН, Т. 46. - М.: КРА-САНД, 2009. С. 111-119
13.М.А. Посыпкин, О.С. Заикин, Д.В. Беспалов, А.А. Семенов, Решение задач криптоанализа поточных шифров в распределенных вычислительных средах // Проблемы вычислений в распределенной среде / Под ред. СВ. Емельянова, А.П. Афанасьева. Труды ПСА РАН, Т. 46. - М.: КРАСАНД, 2009. С 119-138
14.А.П. Афанасьев, В.Д. Лахно, М.А. Посыпкин, В.Б. Султанов, Стационарные состояния в нелинейной модели переноса заряда в ДНК // Проблемы вычислений в распределенной среде / Под ред. СВ. Емельянова, А.П. Афанасьева. Труды ИСА РАН, Т. 46. - М.: КРАСАНД, 2009. С. 147-153
15.P.M. Колпаков, М.А. Посыпкин, О масштабируемости и эффективности одного метода решения задачи о ранце в распределенной вычислительной среде // Проблемы вычислений в распределенной среде / Под ред. СВ. Емельянова, А.П. Афанасьева. Труды ИСА РАН, Т. 46. -М.: КРАСАНД, 2009. С. 164-174
16.М.А. Посыпкин, Решение задач глобальной оптимизации в среде распределенных вычислений // Программные продукты и системы. №1. 2010. С. 23-29.
17.М.А. Посыпкин, Методы и распределенная программная инфраструктура для численного решения задачи поиска молекулярных кластеров с минимальной энергией //Вестник нижегородского университета им. Н.И. Лобачевского №1. 2010. С. 210-219.
18.P.M. Колпаков, М.А. Посыпкин, Верхняя и нижняя оценки трудоемкости метода ветвей и границ для задачи о ранце // Дискретная математика, Т. 22, вып. 1, 2010, С. 58-73
19.P.M. Колпаков, М.А. Посыпкин, И.Х. Сигал, О нижней оценке вычислительной сложности одной параллельной реализации метода ветвей и границ // Автоматика и телемеханика. 2010. №10. С. 156-166.
20.Ю. Г. Евтушенко, М. А. Посыпкин, Применение метода неравномерных покрытий для глобальной оптимизации частично целочисленных нелинейных задач. // ЖВМиМФ, 2011, том 51, №8, С. 1376-1389.
21.Р. М. Колпаков, М. А. Посыпкин, Об оценках вычислительной сложности варианта параллельной реализации метода ветвей и границ для задачи о ранце // Известия РАН: Теория и системы управления. №5, 2011, С. 74-83.
22. Ю.Г. Евтушенко, М.А. Посыпкин, Варианты метода неравномерных покрытий для глобальной оптимизации частично-целочисленных нелинейных задач. // Доклады Академии Наук, 2011, том 437, №2, С. 168-172.
23.Ю.Г. Евтушенко, М.А. Посыпкин, Метод неравномерных покрытий для решения задач многокритериальной оптимизации с гарантированной точностью. // ЖВМиМФ, 2013, том 53, №2, С. 209-224.
24.М.А. Посыпкин, Метод решения задач условной многокритериальной оптимизации с гарантированной точностью // Доклады академии наук, 2013, том 452, №4, с. 375-378.
25.Ю.Г. Евтушенко, М.А. Посыпкин, Метод неравномерных покрытий для решения задач многокритериальной оптимизации с заданной точностью. // Автоматика и телемеханика, 2014, №6, С. 49-68.
Статьи в реферируемых международных изданиях:
26.Y. Evtushcnko, M. Posypkin, I. Sigal, A framework for parallel large-scale global optimization // Computer Science - Research and Development 23(3), pp. 211-215, 2009.
27.Y. Evtushenko, M. Posypkin. A Deterministic Algorithm for Global Optimization // Lecture Notes in Economics and Mathematical Systems, Vol. 658, ISBN 978-3-642-22883-4, P. 205-218, 2012.
28.Y. Evtushenko, M. Posypkin. A deterministic approach to global box-constrained optimization // Optimization Letters, 2013, Volume 7, Issue 4, pp 819-829.
29.A. Afanasiev, Yu. Evtushenko, M. Posypkin. The Layered Software Infrastructure for Solving Large-scale Optimization Problems on the Grid,Horizons in Computer Science Research, Vol. 4, pp. 129-145, Nova Science Publishers Inc, 2012.
30.Yu.G. Evtushenko. M.A. Posypkin. A deterministic algorithm for global multiobjective optimization // Optimization Methods and Software, Vol. 29, Iss. 5, pp. 1005-1009, 2014.