Ученые Дальневосточного федерального университета вместе с другими российскими коллегами предложили новые математические методы выпуклой оптимизации, чтобы быстро решать широкий спектр задач экономики, логистики и других наук. Результаты работы исследователей представлены в монографии, опубликованной издательством Springer.

Новые универсальные самообучающиеся алгоритмы могут эффективно решать большое количество задач. Эти программы способны адаптироваться — распознавать в процессе работы все необходимые параметры — и используют относительно небольшой объем оперативной памяти. Они могут найти применение, например, при создании моделей транспортных потоков, устранении пробок на дорогах и оптимизации маршрутов грузового транспорта, расчета платы за проезд, ранжирования веб-страниц и решения обратных задач.

«Негладкая, или выпуклая, оптимизация, которой мы занимаемся, использует принцип декомпозиции. Это значит, что большую задачу часто можно разделить на несколько мелких, которые потом объединяются друг с другом при помощи специальной координирующей задачи. Этот метод целесообразно использовать для работы с большими данными, — рассказывает профессор Школы естественных наук ДВФУ Евгений Нурминский. — В современном мире часто возникает необходимость обрабатывать и передавать данные. Зачастую размеры файлов превышают несколько гигабайт, и все их надо обработать и вывести какие-то общие закономерности. При использовании прямого подхода, даже с помощью самых быстрых суперкомпьютеров, такие задачи будут решаться сотни или даже тысячи лет. Метод выпуклой оптимизации может сократить это время до нескольких минут».

По словам автора работы, для классической задачи решения системы линейных уравнений современные алгоритмы многократно эффективнее традиционных методов, трудоемкость которых примерно равна кубу от количества переменных. Новые алгоритмы позволяют также сжимать «тяжелое» изображение, чтобы на выходе оно занимало в 10 раз меньше места, чем на входе, но при этом его качество осталось на уровней 95% от исходного. Вместе с тем, такую картинку на глаз нельзя будет отличить от исходной.

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