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

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

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

Гарантия берётся в неожиданном месте – в математической задаче, известной, как "сумма квадратов". Её поставил в 1900-м году великий математик Давид Гильберт. Он спросил, всегда ли определённые уравнения можно выразить в виде суммы из двух отдельных членов, каждый из которых возведён в квадрат. Математики ответили на вопрос Гильберта через несколько десятилетий. Затем, почти 90 лет спустя, специалисты по информатике и инженеры обнаружили, что это математическое свойство – выразимость уравнения через сумму квадратов – помогает решать множество реальных проблем, которые они хотели бы решить. «В том, что я делаю, используется много классической математики XIX века, вместе с очень современной вычислительной математикой», — сказал Ахмади. Однако, как только исследователи поняли, что сумма квадратов может помочь ответить на многие типы вопросов, они столкнулись с проблемами применения такого подхода. Новая работа устраняет одну из крупнейших таких проблем, заставляя старый математический вопрос решать некоторые из наиболее важных технологических вопросов современности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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