Российские математики обобщили знания о глобальной оптимизации

В издательстве Springer при поддержке Российского научного фонда (РНФ) вышла книга «Детерминированная глобальная оптимизация: введение в диагональный подход». Ее авторы — профессор кафедры математического обеспечения и суперкомпьютерных технологий Института информационных технологий, математики и механики Нижегородского государственного университета имени Н.И. Лобачевского, д.ф.-м.н. Ярослав Сергеев и научный сотрудник того же университета, к.ф.-м.н. Дмитрий Квасов. Последние результаты по данной теме были представлены на Молодежной научной школе «Высокопроизводительные вычисления, оптимизация и приложения», которая прошла с 7 по 10 сентября 2017 года в Нижнем Новгороде.

Реклама

Книга посвящена одной из интереснейших областей математического программирования – глобальной оптимизации. Задачей глобальной оптимизации называют поиск оптимальных решений в различных областях человеческой деятельности. Оптимизировать функцию – значит найти ее минимум, то есть минимальное значение, в определенном интервале или во всей области определения. Традиционные методы оптимизации, которым учат в курсе высшей математики, обычно сводятся к поиску локальных минимумов функций и зачастую не позволяют найти глобальный.

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

«Представим, что у нас есть модель некой сложной структуры, например моста, — поясняет профессор Сергеев, — и есть программа, которая, например, считает его вес. При этом есть ограничения, что мост должен не сломаться, иметь определенную длину, и множество других ограничений. Тогда можно поставить задачу оптимизации веса моста, при этом его стоимость не должна превысить определенную границу, а прочность должна сохраниться высокой. Либо наоборот: нам все равно, какой вес, но нужна максимальная прочность и так далее».

В подобных задачах математикам приходится за минимальное количество вычислений целевой функции искать наилучшее решение, и одним из путей решения является диагональный подход. В случае одномерной функции для нее на отрезке всегда можно построить нижнюю огибающую (в этом случае – кусочно-линейную функцию), с помощью которой легко оценить минимум целевой функции на интересующем участке. «Идея диагонального подхода состоит в том, что если параметров много, то вместо того, чтобы исследовать весь многомерный гиперкуб параметров, мы исследуем функцию на его диагонали и находим ее минимум как в одномерном случае, — рассказал профессор Сергеев. – Теория говорит, что если этот минимум умножить на определенный коэффициент, то мы получим оценку минимума функции на всем многомерном гиперинтервале». Таким образом, задача поиска минимума многомерной функции на гиперинтервале сводится к задаче поиска минимума на отрезке.

Задачи глобальной оптимизации решаются с помощью суперкомпьютеров, поскольку их численное решение связано с огромным количеством вычислений. Преимущество диагонального подхода перед иными методами в его быстроте. «Мы многих обыгрываем, у нас есть много рекордов по скорости вычислений, и за этот метод мы получали несколько премий», — рассказал Сергеев, который минувшей весной был избран президентом Международного общества глобальной оптимизации.

Изначально диагональный подход был предложен Яношем Пинтером в 1996 году, при этом 20 лет Сергеев и его сотрудники работали над его совершенствованием. Сергеев — лауреат международных премий Пифагора (Италия, 2010 г.) и Хорезми (Иран, 2017 г.), а также ряда других российских и международных премий.

Книга посвящена вопросам разработки теории и численных методов решения широкого класса задач глобальной оптимизации, удовлетворяющей условию Липшица, то есть тех случаев, когда скорость изменения целевой f(x) на любых участках отрезка [a, b] ограничена некоторым числом. Книга дает введение в предмет и обобщает ряд последних научных достижений авторов, развивающих традиции Нижегородской школы глобальной оптимизации. Результаты исследований, вошедшие в книгу, были опубликованы в ведущих международных научных журналах, получили международные премии и используются более чем в 40 странах мира. Книга рассчитана на широкий круг научных и инженерных работников, аспирантов и студентов, интересующихся теоретическими и прикладными аспектами глобальной оптимизации.