Рівняння Беллмана

Рівняння Беллмана, назване в честь Річарда Беллмана, це — необхідна умова для оптимальності, пов’язаної з методом математичної оптимізації, відомим як динамічне програмування. Рівняння записує “цінність” проблеми рішення в деякій точці часу з точки зору нагороди від деяких початкових рішень разом з “цінністю” залишкової проблеми рішення, що з’явилася на основі тих самих рішень. Це дозволяє розбити проблему динамічної оптимізації на послідовність менших задач, як говорить “принцип оптимальності” Беллмана.

Рівняння Беллмана було вперше використано до інженерної теорії керування та до інших задач прикладної математики, таким чином ставши важливим інструментом у економіці, не дивлячись на те, що базові концепти динамічного програмування були представлені як Джоном фон Нейманом та Оскаром Морґенштерном у книзі “Теорія ігор та економічної поведінки”, так і Абрахамом Вальдом у його дослідженнях послідовного аналізу. Поняття “рівняння Беллмана” зазвичай посилається на рівняння динамічного програмування, асоційоване з задачами оптимізації з дискретним часом. Якщо говорити про задачі оптимізації з неперервним часом, то аналогічне рівняння є диференціальним рівнянням з частинними похідними та називається рівнянням Гамільтона-Якобі-Беллмана.

У дискретному часі будь-яка багатоетапна задача оптимізації може бути вирішена шляхом аналізу відповідного рівняння Беллмана. Таке рівняння може бути знайдено додаванням нових змінних стану (аугментація стану). Однак, слід зауважити, що отримана багатоетапна задача з аугментованим станом має більшу розмірність простору стану ніж оригінальна, що може призвести до недосяжності рішення ввиду “прокляття розмірності”. Альтернативно було показано, якщо функція багатоетапної задачі оптимізації відповідає “зворотно роздільній” структурі, то відповідне рівняння Беллмана може бути знайдено без аугментації стану.

Аналітичні концепти в динамічному програмуванні

Щоб зрозуміти рівняння Беллмана, слід ознайомитися з кількома основними концептами. По-перше, будь-яка задача оптимізації має власну ціль: мінімізація часу подорожі або ціни, максимізація доходу або практичності і т. д.. Математична функція, яка описує дану ціль, називається функцією втрат.

Динамічне програмування розбиває багатоперіодичну проблему планування на менші частини у різних моментах часу. Таким чином, це вимагає чітке спостереження за тим, як еволюціонує ситуація, в якій прийняття рішення є невідворотнім. Інформація про теперішню ситуацію, яка є необхідною, щоб прийняти правильне рішення, називається «станом». Наприклад, щоб дізнатися скільки витратити у кожній точці часу, людям потрібно знати їхнє початкове багатство. Таким чином, багатство $(W)$ буде однією із змінних стану, котрих може бути більше ніж одна.

Змінні, обрані у деякій точці часу, часто називають змінною управління. Наприклад, маючи деяке багатство, люди можуть вирішити скільки витратити зараз. Вибір змінних контролю можливо прирівняти до вибору наступного стану, але, в загальному, на наступний стан впливають не тільки змінні контролю, а і інші фактори. Якщо говорити про приклад, то теперішнє багатство (змінна стану) і витрати (змінна управління) можуть визначити наступний стан (багатство), хоча можуть існувати інші фактори, що також вплинуть на наступний стан.

Метод динамічного програмування описує оптимальний план шляхом знаходження правила, яке говорить про те, чим змінні контролю повинні бути, маючи будь-які значення змінних стану. Наприклад, якщо витрати $c$ залежать лише від багатства $W$, то слід шукати функцію $c(W)$, що задає витрати як функцію від багатства. Таке правило, яке задає змінні контролю як функцію від стану, називається функцією стратегії.

За визначенням, оптимальне правило прийняття рішення це те, яке дозволяє досягти найбільше значення цілі. Наприклад, якщо хтось обирає рівень споживання на основі власного багатства, щоб максимізувати рівень щастя (за умови, що щастя H може бути представлено деякою математичною функцією та є чимось, що базується на багатстві), тоді кожен рівень багатства буде асоційований із деяким найбільшим рівнем щастя, $H(W)$. Найбільш можливе значення цілі, записане як функція від стану, називається функцією цінності.

Беллман показав, що динамічна задача оптимізації з дискретним часом може бути представлена у рекурсивній, покроковій формі, відомій як зворотна індукція, шляхом запису відношення між функцією цінності за перший та наступний періоди. Відношення між цими двома функціями цінності називається рівнянням Беллмана. У цьому підході оптимальна стратегія в останній період часу визначається заздалегідь як функція значення змінної стану на той момент, і результуюче оптимальне значення цільової функції виражається через це значення змінної стану. Далі оптимізація передостаннього періоду включає максимізацію суми цільової функції, специфічної для цього періоду, та оптимального значення майбутньої цільової функції, що дає оптимальну стратегію цього періоду залежно від значення змінної стану на передостанній період. Ця логіка продовжується рекурсивно назад у часі, доки не буде отримано правило прийняття рішення про перший період як функцію значення змінної початкового стану шляхом оптимізації суми цільової функції, специфічної для першого періоду і значення функції вартості другого періоду, яка дає значення для всіх майбутніх періодів. Таким чином, рішення для кожного періоду приймається за явного припущення, що всі майбутні рішення будуть прийматися за оптимальною стратегією.