Вариации на тему Луи XV
Feb. 19th, 2026 09:12 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
xaxam
Обоснованный оптимизм
Как обещал, расскажу про вариационные задачи на бесконечном интервале.Сначала о том, что такое вообще вариационные задачи. Это в сущности те же "школьные" задачи на поиск экстремума (скажем, максимума) функции. Разница в том, что в школе рассматриваются функции одной переменной, заданные явными формулами, и рецепт стандартный. Надо найти точки, в которых производная функции обращается в ноль, и перебрать их все. Максимум (равно как и минимум) затерялся где-то среди этих точек. Потом студентов учат искать максимумы функций нескольких переменных. Но число переменных остаётся конечным.
Вместе с тем есть естественный класс задач, где ищется не точка, а кривая. Простейший пример: кратчайшая кривая, соединяющая две данные точки на плоскости — прямая. Но представим себе, что плоскость не плоская и одинаково гладкая, а ландшафт: часть его — ровное поле, часть — высокая трава, часть — кусты, а часть — вообще непролазная чаща. Скорость передвижения по разным ландшафтам разная. Как проложить самый быстрый путь между двумя точками? Он уже будет не прямой линией, "трудные" участки быстрее обойти, чем через них продираться.
Другой пример. Берём гибкую тяжёлую цепь и поднимаем её за два конца. Она провиснет, минимизируя свою потенциальную энергию. Какая будет форма провисшей цепочки? Ответ: цепная линия " ;-). Третий пример: ребёнок на детской площадке съезжает вниз по жёлобу и торопится. Какой профиль должен быть у жёлоба, чтобы съехать с данной высоты за кратчайшее время? (Ответ: это точно будет не прямая доска, если только это не горка из вашего советского детства).
Всё это называется "вариационные задачи". Рецепт их решения, в сущности, есть то же вычисление производной. Предположим, мы нашли нужную кривую. Это значит, что любое её малое шевеление не может улучшить значение функции. Нетрудно сообразить, что в "линейном приближении" эффект должен быть нулевой (ибо если можно ухудшить, то шевеление "в противоположную сторону" её улучшит). А это и означает, что некоторый аналог производной должен обратиться в ноль.
Задачу определить, что это за "бесконечномерная производная", решили ещё при царе Горохе: Эйлер (и потом Лагранж) выписали явные дифференциальные уравнения, определяющие форму оптимальной кривой. Эти уравнения, как оказалось, имеют второй порядок: чтобы однозначно задать решения, надо указать не одно, а два значения. Например, начальное положение и начальную скорость, если мы говорим о кривых, описывающих движение. Или начальную и конечную точки, как в разобранных примерах.
Бо́льшей части технических трудностей можно избежать, если рассмотреть аналог кривых "в дискретном времени". Предположим, что у нас есть множество Х (например, подмножество плоскости или многомерного пространства), и на парах точек x,y ∈ X задана функция b(x,y) (принимающая как положительные, так и отрицательные значения, и не обязательно симметричная, кроме того, b(x,x) не обязательно равно нулю). По множеству Х гуляет ("прыгает") коммивояжёр, который на своём пути собирает очки по очевидной формуле: прыгнув из точки х в точку у, он кладёт себе в карман сумму b(x,y). Если комми начал своё движение в точке P = x0 и должен закончить поход через T прыжков в точке Q = xT ∈ X, какую максимальную сумму он сможет накопить? Задача имеет смысл даже тогда, когда комми странствует по графу (Х состоит из изолированных точек-вершин, а числа b(x,y) написаны на рёбрах соответствующего графа).
Если отрезок времени Т конечный, то с концептуальной точки зрения нет никаких проблем. У нас есть функция конечного числа переменных, имеющая довольно специальный вид:
S = ∑t=0T b(xt, xt+1),
которую мы хотим максимизировать по всем последовательностям x0, x1, x2, ... , xT−1, xT, начинающимся в данной точке x0. Как писать "вариационную производную" такой функции? Тоже не бином Ньютона. Рассмотрим три последовательных состояния (точки): xt−1, xt, xt+1. Тогда можно задаться вопросом: можно ли увеличить значение функции S, заменив среднюю точку xt какой-нибудь другой, скажем, у? При такой замене вклад от этих трёх точек заменится с b(xt−1,xt) + b(xt,xt+1) на b(xt−1,y) + b(y,xt+1). Если наша цепочка была оптимальной, то максимум выражения f(y) = b(xt−1,y) + b(y,xt+1) должен достигаться как раз при y = xt. Найти такой максимум, как я уже начал выше, есть вполне "школьная" задача: написав нужные (частные) производные, мы получим соотношение между тремя точками xt−1, xt, xt+1. Поскольку рассуждение применимо к любому моменту времени t, мы получаем "разностное" уравнение второго порядка, аналог уравнения Эйлера-Лагранжа для вариационных задач в непрерывном времени. В неявной форме это соотношение выглядит так:
xt = argmaxy( b(xt−1,y) + b(y, xt+1) )
Назовём его ДУЭЛь (дискретное уравнение Эйлера-Лагранжа). Чтобы однозначно определить решение уравнения ДУЭЛь, надо либо задать пару начальных точек x0, x1, либо наоборот, начальное и конечное значения x0 и xT.
В чём проблема с бесконечным значением T = ∞? О, очень просто. Вместо конечной функции S мы получаем бесконечный ряд, который может расходиться в обе стороны. Что же мы тогда оптимизируем?
Первая коленная реакция — а зачем нам суммировать ряд, когда у нас есть ДУЭЛь? Вывод этих уравнений совершенно не зависит от того, конечно или бесконечно было значение Т. Бери разностное уравнение, выражай xt+1 через xt−1 и xt, и йалла, вперёд! Но не всё так просто, однако. По условиям игры нам известна точка x0, в которой находится комми в начальный момент. Чтобы сделать йалла, надо где-то взять x1. Но где? Грубо говоря, комми стоит у флажка, как Иван-царевич с луком, но в какую сторону стрелять — он понятия не имеет. А альтернативы (использовать в качестве второй точки xT) у нас нет при бесконечном Т.
Сферических математиков в вакууме, впрочем, такой голой жопой не испугать. Рассмотрим конечное, но очень большое значение T < ∞. Тогда мы имеем все бенефиты конечности отрезка [0,T], и можем посмотреть, что будет, если попытаться перейти к пределу T → ∞. Возни, конечно, побольше, но нам не привыкать.
Однако ж, немного повозившись, математики столкнулись с явлением, с которым историки были хорошо знакомы. Вообразим себе монарха, скажем, того же Луи XV, после которого мог хоть потоп наступить. Пусть для простоты его фазовое пространство X есть единичный отрезок (удобно думать о нём как о ежегодном бюджете Франции). Каждый год Луи должен решать, какую часть бюджета вложить в посадки новых виноградников, а какую просто пропить/прокутить. Виноградники начинают плодоносить не сразу, но имеют ограниченный срок жизни. В начале своего царствования Луи понимает, что для поддержания уровня удовольствия на требуемом уровне надо какую-то часть бюджета ассигновать на закладки новых виноградников, иначе довольно быстро горло пересохнет. Министры быстренько посчитали, какой процент бюджета надо на это выделять ежегодно, и жизнь закипела. Луи правил долго и счастливо, вкусно ел и сладко пил, но возраст неизбежной отставки 120 лет, когда даже Луи должен будет уйти
Легко понять, что в числе 120 лет ничего особенного нет. С тем же успехом всевышний мог бы отвести Лую мафусаиловы 1000 лет: всё равно в последние годы обязан был бы начаться тот же самый процесс. Кстати, если кто трезвенник и ему чужды подобные заботы, можете подумать о том, что происходит с нашими коалиционными правительствами, когда приближается срок окончания каденции Кнессета и новые выборы уже совсем не за углом. Вердикт один и тот же: с предельным переходом T → ∞ дело кисло.
Идея лежала под другим камнем: понять, какие "симметрии" спрятаны в нашей задаче.
Простейшее наблюдение. Заменим нашу функцию b(x,y) на другую, b*(x,y) = b(x,y) + λ где λ — (вещественное) число. Очевидно, что у оптимизационных задач (на конечном интервале Т) с функциями b и b* будут одни и те же решения: на оптимальность стратегии собирания денег не влияет тот факт, что в конечной точке у комми отберут (или подарят) фиксированную сумму λT.
Следующее наблюдение уже несколько более деликатное. Вместо исходной функции b(x,y) возьмём новую функцию b*(x,y) + g(y) − g(x), где g:X → ℝ произвольная функция. Если мы заменим b на b* в уравнении ДУЭЛь, то в правой части окажется
argmaxy(b(xt−1,y) + g(y) − g(xt)+ b(y, xt+1) + g(xt+1 − g(y)) = argmaxy(b(xt−1,y) − g(xt)+ b(y, xt+1) + g(xt+1)) = argmaxy(b(xt−1,y) + b(y, xt+1)) + (g(xt+1 − g(xt)).
Иными словами, добавляется слагаемое, не зависящее от y, и тем самым не меняющее ДУЭЛь.
Если мы вернёмся к исходной сумме, которую мы максимизировали, то каждое слагаемое b(xt,xt+1) изменится на разность g(xt+1) − g(xt). Добавленные члены, конечно, сократятся за исключением граничных членов −g(x0) и g(xT). Первый член — константа, ни на что не влияющая, второй "отодвигается в бесконечность" на бесконечном интервале, а на конечном интервале влияет на значение функции S.
Что является вполне осмысленной модификацией исходной задачи нашего комми. Если к сумме S мы добавим "выходное пособие", величину g(xT), зависящее от того, в какой точке комми закончит маршрут, это может повлиять на всю траекторию. Что хорошо видно на примере нашего Луя. Если бы в момент ухода в отставку в 120 лет он получил бы приз в зависимости от того, сколько новых виноградников он заложил к последнему году своего царствования, он может и не стал бы пропивать весь бюджет в последние годы. Всё зависит от того, насколько велик предлагаемый приз.
Из сказанного вытекает, что наряду с исходной задачей максимизации суммы S, порождённой "платёжной функцией" b(x,y), есть прямой смысл рассмотреть другую платёжную функцию b*(x,y) = b(x,y) + g(y) − g(x) + λ, где функцию g и число (константу) λ мы можем выбрать так, как удобно.
А как нам было бы удобно? Представим себе, что нам бы удалось подобрать их так, чтобы подправленная функция b*(x,y) обладала бы следующими двумя свойствами: (а) ∀x,y ∈ X b*(x,y) ≤ 0, и (б) ∀x ∈ X, ∃y ∈ X такой, что b*(x,y) = 0. Вместе оба свойства можно было бы записать одним условием:
в) ∀x∈X maxy∈ X b*(x,y) = 0.
Тогда наша задача поиска цепочки, максимизирующей соответствующую сумму (обозначим её S*), хоть конечную, хоть бесконечную, стала бы совершенно тривиальной. В самом деле, каждое слагаемое в сумме S* было бы неположительным, b*(xt,xt+1) ≤ 0, поэтому и вся сумма была бы неположительна (или вообще бы разошлась к −∞. С другой стороны, мы легко видим, что из любой точки исходит траектория (возможно, неединственная), для которой соответствующая сумма в точности равна нулю, а нули можно суммировать сколько угодно, не ожидая проблем. Допрыгав до точки xt, наш комми по условию (б) всегда смог бы сделать прыжок, который принёс бы ему прибыль ноль (правильнее, конечно, сказать, что принёс бы нулевые убытки). Но можно ли добиться выполнения условия (в), играя функцией g и константой λ? Подставим все имеющиеся ресурсы в формулу (в). Получим условие ∀ x maxy∈X b(x,y) + g(y) − g(x) − λ = 0. Перенесём в левую часть всё, что не зависит от y: получим равенство
g(x) + λ = maxy(b(x,y) + g(y)).
Самое время отойти на шаг назад и полюбоваться на этот результат. Что он означает? Разрешимо ли это уравнение относительно функции g и константы λ? Похоже ли оно на что-нибудь знакомое?
Посмотрим на это соотношение как на функциональное уравнение. В правой части тогда окажется оператор, превращающий функцию g в новую функцию (обозначив её Bg), значение которой (Bg)(x) в точке x∈X определяется максимумом выражения, написанного выше. Если бы мы вместо аргументов x,y писали соответствующие символы в качестве индексов, вместо знака + написали бы умножение, а вместо взятия максимума написали бы знак суммы, то оператор Bg принял бы гораздо более привычный вид: (Bg)x = ∑y bxy⋅gy. Узнали формулу для линейного оператора? То-то же! А если ещё сообразить, что в левой части появилось бы выражение λ⋅gx, аналогия стала бы полной. Наше уравнение стало бы привычным уравнением, означающим, что g является "собственным вектором" оператора B.
Давайте дадим, наконец, формальное определение. Пусть X — метрический компакт (например, замкнутое ограниченное подмножество ℝn), и b:X×X → ℝ — непрерывная функция двух аргументов, b(x,y), x,y ∈ℝ, называемая ядром или матрицей.
Определение. Оператор Беллмана с ядром b есть оператор B, определённый на множестве C(X) вещественных функций, непрерывных на X, формулой
(Bf) (x) = maxy∈ X (b(x,y) + f(y)).
Замечание. Стандартные теоремы калькулюса первого года гарантируют, что в сделанных предположениях максимум всегда существует (конечен), достигается (в отличие от супремума) в одной или нескольких точках Х, и в "общем случае", поскольку имеется в виду глобальный максимум, a не просто локальный максимум, то такая точка единственна для (почти) любого выбора x∈X.. Если единственность нарушается, то произвольно малым шевелением это безобразие можно устранить "почти всюду".
Полезное наблюдение. Условие непрерывности b можно заметно ослабить, чтобы учесть разные возможные ограничения. Например, в практических примерах перескок комми из данной точки x∈X возможен отнюдь не в любую точку y∈X (спросите Никиту Хрущёва про возможность перехода к коммунизму, он бы вам порассказал). Как формализовать такие ограничения? Введём "доход" b(x,y) = −∞ за недопустимый (запрещённый) прыжок из x в y. Единственное техническое допущение, требуемое для того, чтобы работать с таким "ядром" — его полунепрерывность (подграфик функции b(x,y) в X×X×ℝ должен быть замкнутым).
Тем не менее условие того, что ядро оператора Беллмана нигде не обращается в −∞, существенно для дальнейшего.
Алгебраическое отступление: как не путатать идемпотентов с импотентами и нильпотентами
На самом аналогия идёт гораздо глубже. Множество ℝ вещественных чисел может быть снабжено хреновой тучей разных структур, — алгебраических, аналитических, топологических, каких только не. Обычные бюргеры могут прожить всю жизнь в реальном мире, не подозревая, что рядом с ними на той же самой почве существуют экзофлора и экзофауна.Вместо обычных операций сложения + и умножения ( "точка" ∙) введём новые бинарные операции ⊕ и ⊙ по следующим правилам: для любых a,b ∈ ℝ
a ⊕ b = max(a,b), a ⊙ b = a + b.
Подобно "обычным" операциям без кружка, это коммутативные и ассоциативные операции, и (главное!), они связаны тем же дистрибутивным законом, а ⊙ (b ⊕ c) = (а ⊙ b) ⊕ (а ⊙ c), что и "обычные" операции. Роль единицы в кружочке исполняет знакомый вещественный ноль. Нуля в кружке среди обычных чисел нет, но это беда невеликая: можно добавить к вещественным числам "число" ⊚ = −∞, так что всегда a ⊕ ⊚ = a. Такие операции превращают расширенные вещественные числа в идемпотентное кольцо, и казалось бы, можно сделать йалла в "новую арифметику". (Идемпотентность означает, что для любого числа а выполнено равенство a ⊕ а = а.)
Увы. К сожалению, кольцом эта числовая система не является. У операции "идемпотентный плюс" по очевидным причинам нет "идемпотентного минуса": уравнение a ⊕ x = b тривиально разрешимо относительно икса, если b > a, имеет бесконечно много решений при b = a и не имеет решения при b < a. Поэтому структура называется идемпотентным полукольцом (обратите внимание на фамилию первого автора!). Это означает, что "восстановлению" подлежит только та часть арифметики и алгебры, которая может обойтись без знака "минус".
Фундаментальный результат всей теории состоит в существовании собственных чисел и собственных векторов для операторов Беллмана.
Теорема. Оператор Беллмана B на метрическом компакте X с непрерывным ядром b(x,y), нигде не обращающимся в −∞, всегда имеет единственное собственное число λ∈ℝ и хотя бы одну непрерывную собственную функцию g∈C(X), такие, что Bg = λ⊙g.
Замечание. Условие на ядро может быть заметно ослаблено: собственное число останется единственным, если какая-то конечная итерация Bn оператора B (см. ниже) имеет всюду конечное непрерывное ядро bn(x,y). Единственность собственного вектора не утверждается.
То, что при таких условиях удаётся в очень общих предположениях доказать существование собственного идемпотент-вектора, решения уравнения Bg = λ⊙g, кажется чудом (не нужно никакой алгебраической замкнутости идемпотентного полукольца).
Отступление. Связь между идемпотентными и обычными операциями гораздо более глубинная, чем кажется. Рассмотрим отображение E(x) = ex/h из ℝ в себя, зависящее от малого параметра h > 0 ("постоянная Планка"). Это отображение обратимо: L(z) = h ∙ ln z. Оба они монотонные. Что они сделают с обычными ("числовыми") операциями? Рассмотрим сначала произведение: Е(x)∙E(y) = E(x+y) безотносительно к h. Иными словами, E превращает числовое сложение в умножение, т.е., операцию ⊙ в "точку без кружочка". Что делает Е с операцией max = ⊕? легко понять, что E(x) + E(y) при x ≠ y при малых есть сумма двух "очень неравных" чисел, и если мы "вернём обратно" эту сумму отображением L, то результат будет равен а = L(E(a)), где а = max (x,y) = x ⊕ y. В результате мы видим, что идемпотентные операции получаются из их стандартных "сестёр" переходом в экспоненциальную карту на числовой прямой в пределе, когда постоянная планка h стремится к нулю. Такая подстановка может быть применена к уравнениям математической физики, скажем, к уравнению Гамильтона-Якоби (вездесущему в вариационном исчислении и теоретической механики). Соответствующая процедура называется методом исчезающей вязкости.
Существование собственного идемпотент-вектора, см. выше, может быть выведено методом исчезающей вязкости из классической теоремы Фробениуса-Перрона о существовании собственного вектора у матрицы с положительными коэффициентами.
Итак, куда же мы пришли
Пришли мы к конструкции оператора Беллмана g ⟼ Bg, "определённого" на функциях g: X → ℝ. Слово "определённый" надо уточнять, поскольку максимум по бесконечному множеству может не существовать, надо уточнять, на каких именно функциях он определён. Как это помогает в борьбе за определение понятия бесконечной оптимальной цепочки x = x0, x1, x2, x3 ... с заданной платёжной функцией b(xt, xt+1) и начальным условием x0?Первый ответ: Рассмотрим собственный идемпотент-вектор g для оператора Беллмана, Bg = λ⊙g и построим траекторию x по рекуррентному правилу.
xt+1= argmaxy∈X (b(xt, y) + g(y)).
В предположении, что глобальный максиму достигается в единственной точке y∈X, это правило однозначно определяет следующее положение xt+1, и тем самым является разностным уравнением первого порядка, решение которого однозначно определяется начальной точкой x0 (в отличие от уравнения ДУЭЛь, которое требует двух начальных значений, как было отмечено!).
Подчеркну, что такое построение бесконечной оптимальной траектории напрямую зависит от того, какая функция выбрана в качестве решения уравнения Беллмана Bg = λ⊙g. Если такое решение неединственно, то может оказаться, что существуют несколько различных бесконечных экстремалей, и теоретически мы можем оказаться в крайне неприятной ситуации.
Предположим, есть две разные собственные функции g1 и g2. Мы стартуем из заданной начальной точки, делаем сколько-то прыжков в соответствии с одной выбранной функцией, а потом решили передумать и с некоторого момента поменять коня на переправе и начать пользоваться функцией g2. Оказывается, что мы рискуем поломать всё: "склеенная" бесконечная траектория даже может перестать удовлеторять уравнениям ДУЭЛь в момент склейки!
Внимательный читатель может пожать плечами. Ну что, городили огород, а всего-то и делов, что придумали, как выбирать определённые решения ДУЭЛь. А какое отношение всё это имеет к исходной задаче максимизации функции S, с которой всё так бодро начиналось?
Ответ даёт метод Беллмана решения задач динамического программирования (откуда, собственно, и пошёл термин "оператор Беллмана). Давайте "подправим" выражение для функции S, добавив к сумме призовой бонус f(xT), который получает наш комми, закончив свой вояж в определённой точке:
S(x0,Т) = maxx(x0,T) ∑t=0T b(xt, xt+1) + f(xT).
Здесь x(x0,T) означает конечный кусок траектории длиной T с началом в x0, и к S тоже добавлены те же аргументы, чтоб удобнее было следить за руками, когда я эти аргументы буду менять. Заметьте, что я сделал неожиданный шаг. Вместо того, чтобы рассматривать одну конкретную задачу с фиксированными параметрами x0 и Т, я подменил эти фиксированные значения переменными. Казалось бы, задача только усложнилась! (со школы все помнят, что уравнения с параметрами решать сложнее, чем уравнения без параметров). Ан нет.
Предположим, мы уже знаем, как выглядит решение для T−1 шага. Можем ли мы построить явно последний шаг? Легко! Если мы знаем оптимальное решение на всех шагах, кроме последнего, то надо всего лишь решить, как надо делать последний прыжок из xT−1 Для этого надо взять xT, решающий одношаговую задачу maxxTb(xT−1,xT) + f(xT), максимизирующую сумму "доход на последнем прыжке плюс премия за окончание путешествия именно в точке xT. Эта задача зависит от (предположительно известного) решения xT−1. Но в реальности мы-то пока его не знаем! Поэтому обозначим полученное выражение как функцию f1(xT−1): по построению, это максимум того, что может получить наш комми за последний прыжок с учётом конечной премии.
f1(xT−1) = maxxTb(xT−1,xT) + f(xT).
Ну что, йалла? сказавший "раз" да скажет "два": чем руководствоваться, делая предпоследний прыжок?
f2(xT−2) = maxxT−1b(xT−2,xT−1) + f1(xT−1).
Почему мы заменили изначальную премию f(xT) на премию f1(xT−1)? Да потому, что если мы остановились после T−1 шагов, то в поправленную премию f1 надо включить и доход за последний прыжок b(xT−1,xT), и изначальную премию f(xT). Дальше всё понятно:f3(xT−3) = maxxT−2b(xT−3,xT−2) + f2(xT−2),
f4(xT−4) = maxxT−3b(xT−3,xT−3) + f3(xT−3).
И так далее до упора. На чём сердце успокоится?
fT(x0) = maxx1b(x0,x1) + fT−1(x1).
Нетрудно сообразить, что функция fT и есть максимальное значение искомой суммы S(x0,Т), которую может получить комми, стартуя из точки x0. Зная все функции ft, t = 1, 2, ..., T, мы легко восстановим оптимальную траекторию при помощи вычисления argmax, соответствующего каждому max'у.
Осталось только увидеть в написанных формулах итерации оператора Беллмана B:
f1 = Bf, f2 = Bf1, f3 = Bf2, ... , fT = BfT−1.
Теперь становится понятным, что означают построенные выше бесконечные экстремали. Это оптимальные траектории, которые фактически не зависят от горизонта оптимизации. В самом деле, если мы изменим бонусную премию f на другую, f + λ отличающюся на константу, то при любом T решения задачи никак не изменятся. Поэтому любая "собственная функция" g оператора Беллмана при итерациях не будет изменяться: Bg = λ⊙g = λ + g, и уравнения, определяющие оптимальную траекторию на каждом шаге имеют вид
xt+1= argmaxy∈X(b(xt, y) + g(y)), t = 0,1,2, ..., T
независимо от горизонта Т.Беллмановские полугруппы
Всё сказанное подталкивает к необходимости изучения полугруппы операторов Bn = B ∘ Bn−1, n = 1,2,3, ... (B0 — тождественный оператор) с очевидным тождеством Bn+m = Bn ∘ Bm при всех n,m ≥ 0. Это, увы, не группа: отрицательные итерации оператора Беллмана не определены. С другой стороны, все эти операторы "линейны" в идемпотентном смысле: для любых функций f,g: X → ℝ и любого числа λ ∈ ℝB (f ⊕ g) = Bf ⊕ Bg, B(λ ⊙ f) = λ ⊙ Bf.
Что даёт нам эта линейность?Ну, и в качестве анонса. Я начал писать этот длинный (но на самом-то деле совсем несложный) текст, обещая рассказать, какую задачу мы решили совместно с Перплешей. Теперь всё готово, чтобы её объяснить. Непрерывной полугруппой операторов Беллмана называется семейство операторов {Bt: t ≥ 0}, "линейных" в идемпотентном смысле, и удовлетворяющих соотношению
∀t,s ≥ 0 Bt+s = Bt ∘ Bs.
Можно догадаться, что такой объект связан с "настоящей" вариационной задаче. в которой надо найти функцию x=x(t), определённую на отрезке t ∈ [0,T] со значениями в подмножестве X евклидова пространства ℝn, имеющую производную x'(t) и такую что x(0)=x0∈X и интеграл ∫[0,T] L(x, x') dt принимает максимальное значение. Здесь L = L(x,v) — функция, определённая на X×ℝn с вещественными значениями, называемая лагранжианом. С другой стороны, непрерывная полугруппа может быть интерпретирована как интерполяция дискретной полугруппы, определённой выше. Центральный вопрос почти любого раздела теории динамических систем, — можно ли по заданной дискретной подгруппе {Bn: n ∈ ℕ} построить непрерывную полугруппу, интерполирующую её {Bt: t ≥ 0}? Обычно это крайне редко удаётся. Мы с Перплешей нашли естественный класс беллмановских полугрупп, для которых это возможно.Но это повод для отдельного рассказа, напрямую связанный с проблемой Луя, после которого хоть потоп.
Интересно?
Последам
Я, как обещал, послал ссылку на этот пост Гроше (мы с ним обсуждали кое-какие детали). Он, как свойственно ИИ, пошёл льстить мне налево и направо (ничего, я видел немало student evaluations), но один толковый совет Гроша мне дал. Примеров не хватает.Виноват, исправляюсь. Вот пример, кажется, простейший из возможных. Пространство состояний состоит из пяти точек: ноль (0), два состояния (обозначим их ± α, они стационарные), и ещё два других, ± β — они "терминальные": −β < −α < 0 < α < β. Платёжная матрица (ядро) задаётся явно. Комми стартует из нуля, и имеет только две опции: пойти налево или направо. b(0, −α) = 2, b(0,+α) =1. В каждом из двух состояний ± α можно стоять неограниченно с одинаковым нулевым (нулевым) выигрышем: b(± α, ± α) = 0. Состояния ± β — терминальные, любой прыжок оттуда будет сто́ить нашему комми полный дизастер на следующем шаге, −∞ в итоговой сумме. Прыгать туда — лишь пошлейший шаг, когда deluge уже наступил). Но есть нюансы (помни Луя): если сумма конечна, то всё, что происходит после момента T, нещитово. Предположим, что b(−α,−β) сильно меньше, чем b(α,β), например, 10 супротив 100. А все необозначенные "выигрыши" равны −∞. ("Что делать?", как вопрошал журналюга В.И. Ульянов)? Куда бы вы прыгнули на нулевом ходу? Налево или направо?
Ответ зависит от правил игры. Если игра будет конечной и срок окончания будет известен заранее — в начальный момент прыгать надо направо, хоть это принесёт выигрыш 1, меньший чем выигрыш 2 при прыжке налево. Почему? Потому, что в последний момент, прыгнув из α в β, комми получит 100. А то, что прыгать из β и получить "выигрыш" −∞ уже не придётся. А тот же прыжок из −α в −β принесёт всего лишь 10. Заметим, что эта стратегия одинаково работает при любом конечном Т, лишь бы финальный свисток не был неожиданностью. Альтернативный вариант — с самого начала игра объявляется бесконечной. В такой ситуации финальный самоубийственный спурт не рассматривается, и в начальный момент надо прыгать налево: выигрыш 2 на бесконечной траектории больше, чем альтернатива 1.
Как на всё это смотрит теория беллмановских полугрупп? А очень просто. Если мы назначим финальную премию f(xT) за окончание конечной игры в точке −β сильно больше, чем за окончание в точке β, то комми сам прыгнет налево на первом шаге. У соответствующего оператора Беллмана одно собственное число λ = 0 (идемпотентная "единица"), но две принципиально разных "собственных" функции. Соответствующие бесконечные экстремали равны 0, −α, −α, −α, −α, ... и 0, α, α, α, ... соответственно.
no subject
Date: 2026-02-19 08:29 am (UTC)no subject
Date: 2026-02-19 11:25 am (UTC)no subject
Date: 2026-02-19 03:26 pm (UTC)no subject
Date: 2026-02-19 01:46 pm (UTC)no subject
Date: 2026-02-19 02:21 pm (UTC)no subject
Date: 2026-02-19 03:04 pm (UTC)Интересно. Сложные вещи понятными словами мало кто может объяснить. Ценю, без сарказма.
no subject
Date: 2026-02-20 06:06 am (UTC)Что же сделали Ньютон с Лейбницем? Они заменили фиксированный отрезок [a,b] на "отрезок переменной длины" [a,x], т.е., объявили правый край отрезка параметром. Оказалось, что площадь соответствующей трапеции, обозначаемая F(x), удовлетворяет дифференциальному уравнению F'=f. Всё хорошо, но как же решать такие уравнения? Deux ex machina! В отличие от интегрирования, дифференцирование функций есть совершенно механическая процедура, голова не нужна, нужны руки. А коли так, чтоб решить такое уравнение, надо просто прочитать справа налево таблицу производных элементарных функций, пользуясь простыми правилами.
Как сказал Гротендик (в вольном переводе): to solve a problem, raise the sea level (игра слов "решить" и "растворить").
no subject
Date: 2026-02-20 02:27 pm (UTC)Мне чтоб эту идею понять, пришлось представить себе стопки монет, расставленные рядом друг с другом вдоль оси Х так, чтоб их верх доставал до интегрируемой функции. А потом ставить одну стопку на другую, слева направо, и отмечать на графике высоту получающейся постоянно растущей стопки.
Это, разумеется, не математически ни разу. В учебнике написано не про перекладывание монет, а про всякую гречку вроде (ε, δ). Но когда мне нужно не перепутать плотность распределения с функцией распределения, в голове возникает эта картинка, а не (ε, δ).
no subject
Date: 2026-02-20 06:37 am (UTC)no subject
Date: 2026-02-20 06:42 am (UTC)А потом сразу перешел к размахиванию руками, что большая часть физических законов имеет вариационной представление.
no subject
Date: 2026-02-20 06:53 am (UTC)no subject
Date: 2026-02-20 07:07 am (UTC)Это одна из непостижимостей нашего мира. Один из простейших (для школьников/студентов) примеров - закон Снеллиуса о преломлении лучей. Изопериметрическая задача (или задача Дидоны) - красивая штука, но её решение вариационными методами сложно, а геометрическое решение (симметризация Штейнера) не использует никакие производные.
no subject
Date: 2026-02-20 07:15 am (UTC)В виде байки спределение постоянных токов по схеме сопротивлений можно определять не через закон Ома, а через закон выделения тепла Джоуля, и требования минимизации выделения тепла.
no subject
Date: 2026-02-20 06:57 am (UTC)Почему лагранжиан обычно не зависит от ускорения? Мне кажется, что это "антропоцентрический" вопрос, связанный с тем, что мы танцуем вокруг именно обыкновенных дифуров с одной независимой переменной. В физике (теория поля, ОТО, ... ) лагранжианы зависят от высших частных производных сплошь да рядом.
no subject
Date: 2026-02-20 10:52 pm (UTC)https://nravov.livejournal.com/208077.html?thread=2088397#t2088397