Новые универсальные самообучающиеся алгоритмы адаптивны.
Ученые Дальневосточного федерального университета (ДВФУ) вместе с коллегами из Московского физико-технического института (МФТИ) разрабатывают математические методы выпуклой оптимизации для ускоренного решения самого широкого спектра задач экономики, науки, многих прикладных направлений человеческой деятельности. О своих результатах ученые сообщили в новой книге «Численные методы выпуклой оптимизации» издательства Springer, передает пресс-служба ДВФУ.
Новые универсальные самообучающиеся алгоритмы адаптивны, то есть в процессе работы сами распознают все необходимые параметры, и экономны, для их работы требуется относительно небольшой объем памяти. Использовать их целесообразно для эффективного решения широкого класса задач, например, моделирования транспортных потоков, борьбы с пробками и оптимизации маршрутов грузового транспорта, расчета платы за проезд, ранжирования веб-страниц, решения обратных задач, когда требуется понять причины, породившие некоторые последствия.
«В основе негладкой, или выпуклой оптимизации лежит принцип декомпозиции. Это значит, что большую задачу часто можно разделить на много мелких, которые потом увязываются между собой с помощью специальной координирующей задачи. Сегодня это актуально для работы с большими данными, — объясняет профессор Школы естественных наук ДВФУ Евгений Нурминский. — В современном мире часто возникает необходимость обрабатывать, передавать данные, измеряемые гигабайтами и более, а также решать на их основе весьма сложные задачи. Наивный прямой подход, даже с применением самых быстрых суперкомпьютеров, потребует для решения таких задач сотни и тысячи лет. Математика ускоряет эти процессы настолько, что они приобретают практический смысл».
Ученый рассказал, что для классической задачи решения системы линейных уравнений современные алгоритмы многократно эффективнее традиционных методов, трудоемкость которых примерно равна кубу от количества переменных.
«Если в задаче пять переменных, то на ее решение вы затрачиваете 125 операций и, скажем, одну секунду времени. Если переменных 50, то вам понадобится 125 тысяч операций и примерно 15 минут. Представьте, что переменных 5000. Решать новую задачу традиционным способом придется около 30 лет. Новые методы сократят это время до 40 секунд. Конечно, можно потратить десятки миллиардов рублей или долларов, соорудить суперкомпьютер величиной с пирамиду Хеопса и энергопотреблением ледокола, который все же решит вашу задачу за день. Но не лучше ли выделить тысячную часть этой суммы на талантливых учеников, которые сделают намного больше? Конечно, и суперкомпьютер не помешает!» — говорит профессор Нурминский.
На основе новых алгоритмов можно обработать «тяжелое» изображение так, чтобы на выходе оно требовало в 10 раз меньше места, чем на входе, но сохранило 95 процентов изначальных свойств. Вместе с тем, такую картинку на глаз нельзя будет отличить от исходной.
«Если говорить очень приземленно, оптимизация помогает меньше копать и буквально, и фигурально, — рассказывает доцент кафедры математических основ управления МФТИ Александр Гасников. — Например, надо решить, как выкопать подземный переход, соединяющий четыре точки на перекрестке так, чтобы можно было из любого входа попасть в любой выход на другой стороне дороги. Казалось бы, надо начертить квадрат и прокопать туннели по двум его диагоналям. Математика говорит нам, что для меньших трудозатрат копать придется иначе. Проектируя очень большие механические конструкции, методами выпуклой оптимизации можно посчитать, как получить наименьшую массу этих конструкций без потерь в прочности. Другой пример — выпуклая оптимизация помогает определить оптимальный способ взимания платы за проезд по платным дорогам, приводящий к минимизации суммарных потерь пользователей сети в дороге».
Ученый отметил, что задачи оптимизации имеют непосредственное отношение к жизни, то есть сама природа часто говорит на языке математики, и чтобы понять ее устройство, надо решить задачу оптимизации.
«В сложных (невыпуклых) задачах мы, правда, в большинстве случаев не можем получить идеального решения, но часто этого и не требуется. На практике часто вполне устраивают субоптимальные результаты, полученные с некоторой погрешностью, но за разумное время. Это применимо, например, ко многим задачам глубокого обучения», — говорит Александр Гасников.
Алгоритмы выпуклой оптимизации можно применять для правильного построения моделей реального мира, и в таких областях как сбор, обработка и передача данных, машинное обучение и искусственный интеллект, инженерные науки, экономика и бизнес, компьютерная химия, физика и медицина.
Книга «Численные методы выпуклой оптимизации» раскрывает традиционные и более современные методы. Работа предназначена для студентов, преподавателей, ученых и практиков, чья область деятельности связана с выпуклой оптимизацией. О своих методах ученые ДВФУ и МФТИ рассказали в отдельной главе «Субградиентные методы решения задачи выпуклой оптимизации с малыми затратами памяти». Издатели собрали под одной обложкой ведущих ученых, которые развивают область выпуклой оптимизации. Книга может быть полезна для всех, кто желает получить актуальную информацию о состоянии дел и новых инструментах, которые содержит эта область математики.