Хабрахабр

[Перевод] Классическая математическая задача проявляет себя в реальном мире

Сто лет назад великий математик Давид Гильберт задал исследовательский вопрос из области чистой математики. Недавние разработки теории оптимизации выносят работу Гильберта в мир робомобилей

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

В результате новой работы Амира Али Ахмади и Анируды Маджумара из Принстонского университета, классическая задача из чистой математики готова предоставить железное доказательство того, что автоматические дроны и робомобили не будут врезаться в деревья или выруливать на встречную полосу.
«Даётся полная, 100% доказуемая гарантия того, что ваша система» сможет избежать столкновений, сказала Джорджина Холл, аспирант из Принстона, сотрудничавшая с Ахмади по этой работе. Будущее наступило.

Амир Али Ахмади, профессор из Принстона

Её поставил в 1900-м году великий математик Давид Гильберт. Гарантия берётся в неожиданном месте – в математической задаче, известной, как "сумма квадратов". Он спросил, всегда ли определённые уравнения можно выразить в виде суммы из двух отдельных членов, каждый из которых возведён в квадрат.

Затем, почти 90 лет спустя, специалисты по информатике и инженеры обнаружили, что это математическое свойство – выразимость уравнения через сумму квадратов – помогает решать множество реальных проблем, которые они хотели бы решить. Математики ответили на вопрос Гильберта через несколько десятилетий.

«В том, что я делаю, используется много классической математики XIX века, вместе с очень современной вычислительной математикой», — сказал Ахмади.

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

Положительно гарантировано

Что означает, что некая величина является суммой квадратов? Возьмём число 13. Это сумма двух квадратов – 22 и 32. Число 34 равно сумме 32 и 52.

Такие многочлены иногда также можно представить в виде суммы квадратов. Вместо чисел, вопрос Гильберта – 17-я из 23-х проблем, которые он предложил на заре XX века – имеет дело с многочленами, такими, как 5x2 + 16x + 13. К примеру, 5x2 + 16x + 13 можно переписать, как (x + 2)2 + (2x + 3)2.

Гильберт хотел узнать, работает ли это в другую сторону: можно ли все неотрицательные многочлены выразить в виде суммы квадратов рациональных функций. Когда выражение является суммой квадратов, вам известно, что оно всегда положительное (все [рациональные] числа, возведённые в квадрат, дают положительное число или ноль, а сумма положительных чисел – положительна). В 1927 математик Эмиль Артин доказал, что гипотеза Гильберта была верна.

Если вам дают сложный многочлен, с десятками переменных, возведённых в высшие степени – довольно сложно сразу же определить, является ли он всегда неотрицательным. Это взаимоотношение оказывается довольно полезным. Сложно проверить их на неотрицательность», — сказал Ахмади. «Некоторые многочлены очевидно неотрицательны, другие – нет.

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

Но сто лет спустя после того, как Гильберт задал свой вопрос, неотрицательность многочленов оказалась ответом на прикладные задачи, влияющие на всех нас. Знание того, что определённый многочлен всегда неотрицателен, может показаться математической тривиальностью.

Лучший способ

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

Не существует простого алгоритма из учебника для вычисления минимального значения сложных многочленов, к тому же, их сложно построить на графике. Нахождение минимума многочлена с множеством переменных – задача трудная.

Джорджина Холл

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

Для ответа на вопрос необходимо проверять различные значения – можно ли вычесть 3, чтобы он не стал отрицательным? Один из способов найти минимальное значение – это задать вопрос: какое максимальное значение можно вычесть из неотрицательного многочлена, чтобы он не стал в какой-то точке отрицательным? А 5? А 4? Проверяется это через возможность его выражения в виде суммы квадратов. Повторяя процедуру, на каждом шаге вам нужно знать, остаётся ли многочлен неотрицательным.

– Поэтому мы используем сумму квадратов в качестве замены неотрицательности». «Вопрос, который надо задать – это „является ли многочлен неотрицательным?“ Проблема в том, что с большим количеством переменных на этот вопрос сложно ответить, — сказал Ахмади.

Однако для того, чтобы неотрицательность помогала решать проблемы оптимизации, необходимо придумать способ быстро подсчитать, выражается ли многочлен через сумму квадратов. Как только исследователям становится известен минимум – оптимальное значение многочлена – они могут использовать другие методы для определения входных параметров, которые приводят к этому значению. И на то, чтобы исследователи смогли это сделать, ушло 100 лет с момента постановки вопроса Гильбертом.

Разбивая проблему

17-я проблема Гильберта перешла из мира чистой математики в прикладную плоскость примерно в 2000-м году. Именно тогда несколько исследователей придумали алгоритм проверки того, представим ли многочлен через сумму квадратов. Они дошли до этого, решая вопрос с квадратами через "полуопределённое программирование", благодаря которому компьютеры способны справиться с такой задачей. Это сделало возможным для исследователей из таких областей, как информатика и инженерное дело, использовать возможности неотрицательности для направления своих поисков в сторону оптимальных путей решения задач.

Анируда Маджумдар

Полуопределённое программирование можно использовать для разложения на сумму квадратов таких многочленов, которые состоят не более, чем из десятка переменных, возведённых в степень не более 6. Но у полуопределённого программирования есть большое ограничение: оно медленно работает на больших задачах и неспособно обрабатывать одни из наиболее сложных многочленов, которые особенно интересуют исследователей. Программа может пережёвывать такой многочлен до конца времён, и так и не выдать сумму квадратов. В многочлены, описывающие сложные инженерные проблемы – например, гарантию того, что робот останется стоять на ногах – может входить 50 переменных, или даже более того.

Вместо того, чтобы пытаться найти разложение на сумму квадратов при помощи одной, медленной программы, они показывают, как можно сделать это при помощи решения
последовательности более простых задач, вычислить которые будет гораздо быстрее. В работе, опубликованной в онлайне в прошлом июне, Ахмади и Маджумдар объясняют, как можно обойти медленную работу полуопределённого программирования.

Линейные программы сейчас хорошо понимают и быстро решают. Задачи такого типа называют «линейными», и они были разработаны в 1940-х для решения проблем оптимизации, связанных с военными вопросами. В итоге, у инженеров появился новый, практичный инструмент, который они могут использовать для проверки на неотрицательность и быстро находить разложение на сумму квадратов. В новой работе Ахмади и Маджумдар показывают, что можно решить множество связанных линейных программ (или, в некоторых случаях, проблему другого типа, программу конуса второго порядка), и скомбинировать результаты для того, чтобы получить нечто, почти настолько же хорошее, как и ответ, который могла бы дать программа для полуопределённого программирования.

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

Доказательство безопасности

Скорость решения решает всё, если вы находитесь в робомобиле. В такой ситуации многочлен может выступать математическим барьером, установленным вокруг препятствий, в которые вы не хотите врезаться – если его можно достаточно быстро вычислить.

На парковке нет ничего, кроме будки охранника в дальнем конце. Представим простой пример: робомобиль на гигантской парковке. Ваша задача – запрограммировать машину так, чтобы она никогда не врезалась в эту будку.

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

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

Это даёт вам формальное доказательство избегания столкновений», — сказал Ахмади. «Если начать с определённого места, то робот не будет пересекать линию, за которой находится препятствие.

Нужно построить многочлен так, чтобы стена окружала препятствие как можно плотнее. Конечно, будет неудобно, если эта стена окажется на середине пути между машиной и будкой. Такой вариант оградит будку, и даст машине много места для движения.

Это достигается проверкой того, остаётся ли многочлен суммой квадратов. На практике необходимо минимизировать значение – расстояние между стеной и будкой – поэтому нужно сдвигать график многочлена и смотреть, насколько далеко его можно отодвинуть до тех пор, пока он не перейдёт из минуса в плюс.

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

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

Так что, если и когда робомобили смогут безопасно передвигаться по миру, мы сможем поблагодарить за это Google и Tesla – а также Гильберта. Новый подход Ахмади и Маджумдара открывает новый способ проведения таких мгновенных вычислений.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть