Ученые ННГУ доказали теорему о равномерной сходимости нового алгоритма

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

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

«Усложнение математических моделей процессов, протекающих в объекте, может приводить к тому, что характеристики эффективности не будут обладать свойством монотонности, что обуславливает недостаточность методов локального поиска для оценки наилучшего варианта», – отмечает профессор Роман Стронгин.

Применяемые в таких задачах (называемых также задачами многоэкстремальной оптимизации) процедуры глобального поиска обеспечивают целенаправленность за счет учета ограниченности изменения характеристик объекта при ограниченных изменениях его параметров. Математическая формулировка этого факта может иметь форму условия Липшица, равномерного условия Гёльдера и т.п.
Задачи многоэкстремальной оптимизации обладают узкой сферой возможностей аналитического исследования и высокой трудоемкостью численного решения, поскольку в последнем случае для них характерен экспоненциальный рост вычислительных затрат с ростом размерности.
По словам доцента кафедры математического обеспечения и суперкомпьютерных технологий ННГУ Константина Баркалова, использование современных параллельных вычислительных систем расширяет сферу применения методов глобальной оптимизации и, в то же время, ставит задачу эффективного распараллеливания процесса поиска.

«Именно поэтому разработка эффективных параллельных методов для численного решения задач многоэкстремальной оптимизации и создание на их основе программных средств для современных вычислительных систем является основным вектором развития в данной области», – подчеркивает Константин Баркалов.

Обычно рассматриваемые методы, как последовательные, так и параллельные, предназначены для решения одной, выделенной оптимизационной задачи. Если же требуется решить некоторую серию из q задач, то задачи из данной серии решаются одна за другой, последовательно. Тем самым оценка оптимума в i-й задаче серии является неопределенной до момента полного решения всех предшествующих ей задач с номерами 1, 2, …, i−1. В случае ограниченности вычислительных ресурсов оценки оптимума в задачах i+1, …, q не будут получены, если исчерпание вычислительного ресурса произойдет при решении i-й задачи.
Ситуация, в которой требует решить серию из q задач, не является экстраординарной. Например, серия скалярных задач возникает при поиске множества Парето для задачи многокритериальной оптимизации. При этом решение одной скалярной задачи соответствует одной из парето-оптимальных точек многокритериальной задачи. Серии оптимизационных задач также возникают при использовании методов редукции размерности при решении многомерных задач оптимизации. Наконец, серия задач тестового характера может быть получена при помощи того или иного генератора тестовых задач.
Ученые считают, что при решении множества задач нужно изначально иметь оценки решений сразу во всех задачах, чтобы в любой момент времени иметь возможность оценить целесообразность продолжения поиска. При этом оценки оптимума во всех задачах желательно иметь с одинаковой точностью.
Запуск в параллельной вычислительной системе множества независимых процессов, каждый из которых будет решать одну задачу из серии, обладает рядом недостатков. Во-первых, будет наблюдаться дисбаланс вычислительной нагрузки между процессорами. Если решение i-й задачи требует значительно меньшего числе итераций метода, чем решение j-й задачи, то в этом случае процессор, решающий i-ю задачу, будет простаивать. Во-вторых, оценки оптимума в разных задачах будут получены с разной точностью. Более простые задачи будут решены с высокой точностью, в то время как более сложные задачи будут решены менее точно.
Целью проведенного исследования стала разработка нового метода решения серии задач глобальной оптимизации, который обеспечивал бы: (i) равномерную загрузку всех используемых ядер/процессоров; (ii) равномерную сходимость к решениям всех задач серии.
Также учеными Университета Лобачевского в рамках теоретической части работы была доказана теорема о равномерной сходимости нового алгоритма. Экспериментальная часть работы заключалась в решении серии из нескольких сотен тестовых задач разной размерности, результаты которых убедительно продемонстрировали наличие равномерной сходимости.
Разработанный метод является развитием алгоритма глобальной оптимизации и его параллельного обобщения, детально описанных в монографиях: Strongin R.G., Sergeev Ya.D. Global optimization with non-convex constraints. Sequential and parallel algorithms. – Dordrecht: Kluwer Academic Publishers. – 2000. – 704 p.; Стронгин Р.Г., Гергель В.П., Гришагин В.А., Баркалов К.А. Параллельные вычисления в задачах глобальной оптимизации – М.: Издательство Московского университета. – 2013. – 280 с.

barkalov