Сэм Вонг (Sam Wong) из Университета Калифорнии в Беркли и двое студентов Массачусетского технологического института Инь-Тат Ли (Yin-Tat Lee) и Аарон Сидфорд (Aaron Sidford) разработали новый алгоритм решения проблемы оптимизации, который увеличит эффективность ее решения на несколько порядков. Полностью он представлен в статье на сайте arxiv.org, кратко о нем рассказывает сайт MIT.

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

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

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