벨만 방정식

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않기 때문에 대체로 검증되지 않은 상태로 남아 있다. 보다 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2018년 4월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

리처드 E의 이름을 딴 벨만 방정식. Bellman은 동적 프로그래밍이라고 알려진 수학적 최적화 방법과 관련된 최적성을 위해 필요한 조건이다.^[1] 그것은 일부 초기 선택으로부터의 보상의 관점에서 특정 시점에 의사결정 문제의 "가치"와 그러한 초기 선택에서 발생하는 나머지 결정 문제의 "가치"를 기록한다.^{[citation needed]} 이것은 Bellman의 "최적성의 원리"가 규정하는 것처럼 동적 최적화 문제를 일련의 단순한 하위 문제로 세분화한다.^[2]

벨만 방정식은 처음에는 공학적 제어 이론과 응용 수학의 다른 주제에 적용되었고, 이후 경제 이론에서 중요한 도구가 되었다. 동적 프로그래밍의 기본 개념은 존 폰 노이만과 오스카 모겐스테른의 게임과 경제 행동 이론과 아브라함 월드의 순차적 개념에서 구성된다. 분석의^{[citation needed]} '벨만 방정식'이라는 용어는 보통 이산 시간 최적화 문제와 관련된 동적 프로그래밍 방정식을 가리킨다.^[3] 연속 시간 최적화 문제에서 유사 방정식은 해밀턴-자코비-벨만 방정식이라고 하는 부분 미분 방정식이다.^[4][5]

이산 시간에는 적절한 Bellman 방정식을 분석하여 다단계 최적화 문제를 해결할 수 있다. 적절한 벨만 방정식은 새로운 상태 변수(상태 확대)를 도입함으로써 찾을 수 있다.^[6] 그러나 결과적으로 발생하는 증강 상태 다단계 최적화 문제는 원래의 다단계 최적화 문제보다 차원 상태 공간이 더 높다. 즉, "차원성의 저주"로 인해 잠재적으로 증강 문제를 난치할 수 있는 문제가 될 수 있다. 대안적으로, 다단계 최적화 문제의 비용 함수가 "뒤로 분리 가능한" 구조를 만족한다면, 상태 증대 없이 적절한 벨만 방정식을 찾을 수 있다는 것이 입증되었다.^[7]

동적 프로그래밍의 해석 개념

벨만 방정식을 이해하려면 몇 가지 기본 개념을 이해해야 한다. 첫째, 최적화 문제에는 여행 시간 최소화, 비용 최소화, 수익 극대화, 효용 극대화 등 몇 가지 목표가 있다. 이 목적을 설명하는 수학적 함수를 객관적 함수라고 한다.

동적 프로그래밍은 다양한 시점에서 다주기 계획 문제를 더 간단한 단계로 세분화한다. 따라서 시간이 지남에 따라 의사결정 상황이 어떻게 진화하고 있는지 추적할 필요가 있다. 정확한 결정을 내리기 위해 필요한 현 상황에 대한 정보를 '국가'^[8][9]라고 한다. 예를 들어, 각 시점에서 얼마나 소비하고 소비할지를 결정하려면, 사람들은 그들의 초기 부를 알아야 할 것이다. 따라서 부$({\displaystyle W}$) ${\디스플레이$ 스타일$(W)}$은 그들의 상태 변수 중 하나가 되겠지만$$, 아마 다른 것도 있을 것이다.

주어진 시점에서 선택한 변수를 종종 관리 변수라고 부른다. 예를 들어, 현재의 부를 고려해 볼 때, 사람들은 지금 얼마를 소비할지 결정할 수 있다. 지금 제어 변수를 선택하는 것은 다음 상태를 선택하는 것과 같을 수 있다. 더 일반적으로 다음 상태는 현재 제어 외에 다른 요인의 영향을 받는다. 예를 들어, 가장 간단한 경우, 비록 전형적으로 다른 요소들이 내일의 부(국가)에도 영향을 미치겠지만, 오늘의 부(국가)와 소비(통제)가 내일의 부(새로운 국가)를 정확히 결정할 수도 있다.

동적 프로그래밍 접근방식은 가능한 상태 값이 주어지면 컨트롤이 무엇이어야 하는지를 알려주는 규칙을 찾아 최적의 계획을 설명한다. 예를 들어 소비(c)가 부(W)에만 의존한다면, 우리는 부(富)의 함수로 소비를 주는 규칙$$ c$){\디스플레이$ 스타일 c($W)}$를 추구할 것이다. 제어장치를 주의 함수로 결정하는 그러한 규칙을 정책함수라고 한다(Bellman, 1957, Cho. III.2 참조).^[8]

마지막으로, 정의에 따르면 최적 결정 규칙은 목표의 가능한 최고의 가치를 달성하는 규칙이다. 예를 들어, 누군가가 행복을 극대화하기 위해 부가 주어진 소비를 선택한다면(행복 H는 효용 함수와 같은 수학적 함수로 표현될 수 있고 부로 정의되는 것이라고 가정하면), 각각의 부 수준은 $H{\displaystyle }$( ${\displaystyle W}$) ${\displaysty H (W)}$와 연관될 것이다.$$. 국가의 함수로 쓰여진 목적의 가장 좋은 값을 가치함수라고 한다.

벨먼은 이산형 시간에서의 동적 최적화 문제는 한 기간의 가치 함수와 다음 기간의 가치 함수의 관계를 적음으로써 역유도라고 알려진 반복적이고 단계적인 형태로 진술할 수 있다는 것을 보여주었다. 이 두 가치 함수 사이의 관계를 "벨만 방정식"이라고 한다. 이 접근법에서, 마지막 기간의 최적 정책은 그 당시 국가 변수 값의 함수로 미리 명시되어 있고, 따라서 객관적 함수의 결과적 최적 값은 국가 변수의 그 가치의 관점에서 표현된다. 다음으로, 다음부터 마지막 기간의 최적화는 그 기간의 기간별 목적함수와 미래 목적함수의 최적 값의 합을 최대화하는 것을 포함하며, 다음에서 마지막 기간의 결정으로 국가 변수의 값에 따라 그 기간의 최적 정책을 제공한다.^{[clarification needed]} 이 논리는 제1주기 특유의 목적함수와 제2기 가치함수의 합을 최적화하여 제1주기 결정규칙이 초기 상태 변수값의 함수로 도출될 때까지, 모든 미래 기간에 대한 값을 재귀적으로 계속한다. 따라서, 각 기간의 결정은 모든 미래의 결정이 최적으로 이루어질 것임을 명시적으로 인정함으로써 이루어진다.

파생

동적 의사결정 문제

시간 $t{\displaystyle }$ ${\displaystyle t}$의 상태를 x ${\displaystyle t_{}}$ ${\$로 한다$.$ 시간 0에서 시작되는 결정에 대해서는 초기 $상태{\displaystyle {}_{}}$ ${\displaystyle {x\mathrm{}}_{}}$ 0$${\$displaystyle x_{0}$로 한다$.$ 언제든지 가능한 작업 집합은 현재 ${\displaystyle \mathrm{상태}}$에 따라 달라진다. ${\displaystyle t_{}}$ ${\displaystyle {}_{}}$ ∈ (${\displaystyle x_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle a_{t}\in \Gamma (x_{t}})$로 쓸 수 있다$.$ 여기서 ${\displaystyle t_{}}$ ${\$는 하나 이상의 제어 변수를 나타낸다$$. We also assume that the state changes from ${\displaystyle x}$ to a new state ${\displaystyle T(x,a)}$ when action ${\displaystyle a}$ is taken, and that the current payoff from taking action ${\displaystyle a}$ in state ${\displaystyle x}$ is ${\displaystyle F(x,a)}$. Finally, we 할인율 < < ${\displaystyle$ 0 $<\displaystyle <1}$으로 대표되는 조급증을 가정한다

이러한 가정 하에서 무한 수평적 의사결정 문제는 다음과 같은 형태를 취한다.

${\displaystyle V(x_{0})\;=\\\max _{\left\{a_{t}\right\}_{t=0}^{\nott=0}}}}\sum _{t=0}^{t=0}^{\ft}F(x_{t},a_{t}),}}$

제약을 받고.

${\displaystyle a_{t}\in \Gamma(x_{t}),\;x_{t+1}=T(x_{t},a_{t}),\;\forall t=0,1,2,\dots }$

가정된 제약 조건에 따라 이 목표 함수를 최대화하여 얻을 수 있는 최적의 값을 나타내기 위해$$ 표기법 $V{\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$) ${\displaystyle V(x_{0})$를 정의했다는 점에 유의하십시오. 이 함수는 값함수다. 얻을 수 있는 최상의 값은 초기 상황에 따라 달라지기 때문에 초기 상태 변수 $x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$의 함수다$.$

벨먼의 최적성 원리

동적 프로그래밍 방법은 이 결정 문제를 더 작은 하위 문제로 세분화한다. Bellman의 최적성 원리는 이것을 하는 방법을 설명한다.

최적성의 원리: 최적의 정책은 초기 상태와 초기 결정이 무엇이든, 나머지 결정은 첫 번째 결정으로 인한 국가와 관련하여 최적의 정책을 구성해야 한다는 속성을 가지고 있다. (벨먼, 1957년, 채프 참조) III.3.)^[8][9][10]

컴퓨터 과학에서는 이렇게 쪼개질 수 있는 문제가 최적의 하부 구조를 가지고 있다고 한다. 동적 게임 이론의 맥락에서, 이 원칙은 하위 게임 완전 평형 개념과 유사하지만, 이 경우에 최적의 정책을 구성하는 것은 의사결정자의 반대자들이 그들의 관점에서 유사하게 최적의 정책을 선택하는 것에 의해 조건화된다.

최적성의 원칙에서 제시한 바와 같이, 향후의 모든 결정을 제쳐 두고, 첫 번째 결정을 별도로 생각할 것이다(새로운 상태 $x{\displaystyle {}_{}}$ ${\$1}로$$1시부터 새롭게 시작할 것이다).$$ 오른쪽 괄호 안에 미래의 결정을 취합하면 위의 무한 수평 결정 문제는 다음과 같다.^{[clarification needed]}

${\displaystyle \max _{a_{0}}\left\{F(x_{0},a_{0})+\beta \left[\max _{\left\{a_{t}\right\}_{t=1}^{\infty }}\sum _{t=1}^{\infty }\beta ^{t-1}F(x_{t},a_{t}):a_{t}\in \Gamma (x_{t}),\;x_{t+1}=T(x_{t},a_{t}),\;\forall t\geq 1\right]\right\}}$

제약을 받고.

${\displaystyle a_{0}\Gamma(x_{0}),\;x_{1}=T(x_{0},a_{0}).}$

$여기$서 ${\displaystyle {우리}_{}}$는 시간 1 상태가 x $1{\displaystyle {}_{}}$= ${\displaystyle T}$( ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}{}_{}}$ 0 ) ${\displaystyle x_{1}=T(x_{0},a_{0}}}$이(가) 되도록 0 ${\$ x_{${\displaystyle {0\mathrm{}}_{}}$$}}}$을(를) 선택하고 있다$.$ 그 새로운 상태는 1시부터 의사결정 문제에 영향을 미칠 것이다. 미래의 모든 의사결정 문제는 오른쪽 대괄호 안에 나타난다.^{[clarification needed][further explanation needed]}

벨만 방정식

지금까지 우리는 오늘의 결정과 미래의 결정을 분리함으로써 문제를 더 추악하게만 만든 것 같다. 그러나 오른쪽의 대괄호 안에 있는 것이 상태 ${\displaystyle {x\mathrm{}}_{}}$ $1{\displaystyle {}_{}}$= ${\displaystyle T}$( ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {0\mathrm{}}_{}{}_{}}$ 0${\displaystyle {}_{}}$) ${\displaystyle x_{1}=T(x_{0},a_{0}}})$에서 시작하여 시간 1 결정 문제의 값임을 알아봄으로써 단순화할 수 있다$.$

따라서 우리는 이 문제를 가치 함수의 재귀적 정의로 다시 쓸 수 있다.

${\displaystyle V(x_{0})=\max _{a_{0}}\{F(x_{0},a_{0})+\beta V(x_{1})\}}$, subject to the constraints: ${\displaystyle a_{0}\in \Gamma (x_{0}),\;x_{1}=T(x_{0},a_{0}).$$}$

이것이 벨만 방정식이다. 시간 첨자를 줄이고 다음 상태의 값을 연결하면 훨씬 더 단순화할 수 있다.

${\displaystyle V(x)=\max _{a\in \감마(x)}\{F(x,a)+\beta V(T(x,a)\}.}$

벨만 방정식을 푸는 것은 값함수인 알 수 없는 $함수{\displaystyle }$ V ${\$displaystyle $V$을 찾는 것을 의미하기 때문에 기능 방정식으로 분류된다. 값 함수는 상태 $x{\displaystyle }$ ${\displaystyle$ x$}$의 함수로서 목적의 가능한 최선의 값을 기술하고 있음을 상기하라$$값 함수를 계산함으로써, 최적의 동작을 상태의 함수로 기술하는$$ $함수{\displaystyle }$a (${\displaystyle x}$ )$${\$displaystyle a(x)}$도 찾을 수 있을 것이다, 이것을 정책함수라고 한다.

확률적인 문제에서.

결정론적 설정에서 동적 프로그래밍 이외의 다른 기법을 사용하여 위의 최적 제어 문제를 해결할 수 있다. 그러나 벨만 방정식은 확률적 최적 제어 문제를 해결하는 가장 편리한 방법이다.

경제학의 구체적인 예를 들어, $0{\displaystyle \mathrm{}}${\$displaystyle {\red}a_{0}}$ 기간 0${\displaystyle 0}$에 ${\displaystyle {초기\mathrm{}}_{}}$ 부를 가진 무한정 생존 소비자를 생각해 보십시오$.$ They have an instantaneous utility function ${\displaystyle u(c)}$ where ${\displaystyle c}$ denotes consumption and discounts the next period utility at a rate of ${\displaystyle 0<\beta <1}$. Assume that what is not consumed in period ${\displaystyle t}$ carries over to the next period with interest r 레이트 $r{\displaystyle }$ ${\displaystyle r$ 그렇다면 소비자의 유틸리티 극대화 문제는 해결되는$$ 소비 계획${\displaystyle }${${\displaystyle c_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle \{\color {OliveGreen}c_{t}\}}}}$을(를) 선택하는 것이다.

${\displaystyle \max \sum _{t=0}^{\infit }\beta ^{t}u({\color {OliveGreen}c_{t}})}}}$

의 대상이 되다

${\displaystyle {\color}a_{t+1}=(1+r)({\color {Red}a_{t}-{\color {OliveGreen}c_{t}),\{\color {OliveGreen}c_{t}}\color {olor {OliveGreen}c}}}\gq 0,},},},}$

그리고

${\displaystyle \lim _{t\rightarrow \infit }{\color {Red}a_{t}\geq 0.}$

첫 번째 제약조건은 문제에 의해 명시된 자본 축적/이동법이고, 두 번째 제약조건은 소비자가 수명이 다할 때 부채를 부담하지 않는 횡단성 조건이다. 벨만 방정식은

${\displaystyle V(a)=\max _{0\leq c\leq a}\{u(c)+\beta V(1+r)(a-c)\}}$

또는 해밀턴 방정식을 사용하여 시퀀스 문제를 직접 처리할 수 있다.

이제 기간마다 금리가 다를 경우 소비자는 확률적 최적화 문제에 직면하게 된다. 이자율 r이 확률 전이함수 $Q{\displaystyle }$(${\displaystyle r}$ , ${\displaystyle {}_{}}$ ${\displaystyle {\mu }_{}}$ r$){\d\mu _{r}$를 가진 마르코프 과정을 따르도록 한다. 여기서$$ $d{\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle r_{}}$ ${\$는 현재 금리가 r ${\displaysty r}$인 경우 다음 기간의 이자율 분배를 지배하는 확률 측정치를 나타낸다$$$.$소비자는 당기의 이자율이 발표된 후에 당기의 소비량을 결정한다.

Rather than simply choosing a single sequence ${\displaystyle \{{\color {OliveGreen}c_{t}}\}}$, the consumer now must choose a sequence ${\displaystyle \{{\color {OliveGreen}c_{t}}\}}$ for each possible realization of a ${\displaystyle \{r_{t}\}}$ in such a way that their lifetime expectED 효용 최대화:

${\displaystyle \max _{\lt_{t}\right\}^{\bigg {E}{\bigg (}\sum _{t=0}^}}\beta ^{t}u({\color {oliveGreen}c_{t}}}}}}}{big )}.}$

기대 $E{\displaystyle \mathbb{}}$ ${\$은(는) R의 시퀀스에 대해 Q가 제공한 적절한 확률 측정에 대해 취한다$$. r은 마르코프 프로세스에 의해 관리되기 때문에 동적 프로그래밍은 문제를 상당히 단순화시킨다. 그렇다면 벨만 방정식은 간단히 다음과 같다.

${\displaystyle V(a,r)=\max _{0\leq c\leq a}\{u(c)+\beta \int V(1+r)(1+r(a-c),r')Q(r,d\mu _{r}\}}}.}$

어떤 합리적인 가정 하에서 최적의 정책 함수 g(a,r)를 측정할 수 있다.

Markovian 충격의 일반적인 확률론적 순차적 최적화 문제와 대리인이 이전 포스트의 결정에 직면하는 경우, Bellman 방정식은 매우 유사한 형태를 취한다.

${\displaystyle V(x,z)=\max _{c\in \감마(x,z)}\{F(x,c,z)+\beta \int V(T,c,z')d\mu _{z}(z')\}.}$

솔루션 방법

• 'guess and verify'라고도 알려진 미결정 계수의 방법은 일부 무한 수평의 자율적인 벨만 방정식을 푸는 데 사용될 수 있다.^[11]
• 벨만 방정식은 몇 가지 특수한 경우에서 분석적으로 또는 컴퓨터로 수치적으로 유도하여 해결할 수 있다. 수치 역방향 유도는 다양한 문제에 적용 가능하지만, 차원성의 저주로 인해 상태 변수가 많은 경우 실현 불가능할 수 있다. 대략적인 동적 프로그래밍은 D. P. Bertsekas와 J. N. Tsitsiklis에 의해 Bellman 함수의 근사치를 위해 인공신경망(다중기 수용체)을 사용하여 도입되었다.^[12] 이는 전체 우주영역에 대한 완전한 기능 매핑의 암기를 유일한 신경망 파라미터의 암기로 대체함으로써 차원성의 영향을 줄이는 효과적인 완화 전략이다. 특히 연속 시간 시스템의 경우, 두 정책 반복과 신경망을 결합한 대략적인 동적 프로그래밍 접근법이 도입되었다.^[13] 이산 시간에는 값 반복과 신경망을 결합한 HJB 방정식을 해결하기 위한 접근법이 도입되었다.^[14]
• 벨만 방정식과 관련된 1차적 조건을 계산한 다음, 봉투 정리를 사용하여 가치함수의 파생물을 제거함으로써 '어울러 방정식'이라 불리는 차이 방정식이나 미분 방정식의 체계를 얻을 수 있다.^[15] 차이 또는 미분 방정식의 해법에 대한 표준 기법을 사용하여 상태 변수의 역학 및 최적화 문제의 제어 변수를 계산할 수 있다.

경제학 응용 프로그램

경제학에서 벨만 방정식의 첫 번째 알려진 적용은 마틴 베크만과 리처드 무스 때문이다.^[16] 마틴 베크만은 1959년 벨만 방정식을 이용해 소비이론에 대해서도 폭넓게 썼다. 그의 작품은 에드먼드 S에 영향을 미쳤다. 펠프스, 그중에서도.

벨만 방정식의 유명한 경제 적용은 로버트 C이다. Merton의 1973년 기사 임시 자본 자산 가격 모델에 대한.^[17] (Merton의 포트폴리오 문제도 참조하십시오.)투자자들이 현재의 소득과 미래의 소득 또는 자본 이득 사이에서 선택한 머튼의 이론적 모델에 대한 해결책은 벨먼 방정식의 한 형태다. 동적 프로그래밍의 경제적 응용은 보통 차이 방정식인 벨만 방정식을 낳기 때문에 경제학자들은 동적 프로그래밍을 "재발적 방법"으로 지칭하며, 현재 경제 내에서 재귀경제학의 하위 분야가 인정되고 있다.

낸시 스토키, 로버트 E. 루카스, 그리고 에드워드 프레스콧은 확률적이고 비스토크틱한 동적 프로그래밍을 상당히 상세하게 기술하고 있으며, 특정 조건을 만족하는 문제에 대한 해결책의 존재에 대한 이론들을 개발한다. 그들은 또한 재귀적 방법을 사용하여 경제학에서 이론적 문제를 모델링하는 많은 사례들을 설명한다.^[18] 이 책은 최적의 경제 성장, 자원 추출, 주체-대리인 문제, 공공 금융, 사업 투자, 자산 가격 책정, 요인 공급, 산업 조직 등 경제학의 광범위한 이론적 문제를 해결하기 위해 동적 프로그래밍을 채택하였다. Lars Ljungqvist와 Thomas Sargent는 역동적인 프로그래밍을 적용하여 통화정책, 재정정책, 세제, 경제성장, 검색이론, 노동경제학 등에서 다양한 이론적 문제를 연구한다.^[19] 아비나시 딕싯과 로버트 핀디크는 자본 예산에 대해 생각하는 방법의 가치를 보여주었다.^[20] 앤더슨은 이 기술을 개인 소유 기업을 포함한 사업 가치 평가에 적용했다.^[21]

동적 프로그래밍을 사용하여 구체적인 문제를 해결하는 것은 관측할 수 없는 할인율을 선택하는 등 정보상의 어려움으로 인해 복잡하다. 계산상의 문제들 또한 있는데, 그 주된 문제는 최적의 전략을 선택하기 전에 고려해야 하는 수많은 가능한 조치와 잠재적인 상태 변수에서 발생하는 차원성의 저주다. 컴퓨터 문제에 대한 광범위한 설명은 미란다와 패클러,^[22] 그리고 마인 2007을 참조하십시오.^[23]

예

마르코프 의사결정 프로세스에서 벨만 방정식은 기대 보상에 대한 재귀이다. 예를 들어 특정 상태에 있고 일부 고정 정책 $following{\displaystyle }$ ${\displaystyle \pi }$에 따라 예상되는 보상에는 다음과$$ 같은 Bellman 방정식이 있다.

${\displaystyle V^{\pi }=R(s,\pi)(s)+\gamma \sum \sum_{s'}P(s,\pi)V^{\pi }'s.\ }$

이 방정식은 일부 정책 $\pi {\displaystyle }$ ${\displaystyle \pi }$에 의해 규정된 조치를 취할 경우 예상되는 보상을 설명한다$.$

최적 정책에 대한 방정식을 Bellman 최적성 방정식이라고 한다.

${\displaystyle V^{\pi *}=\max _{a}\left\{R(s,a)+\gamma \sum \sum_{s,a)V^{\pi *}\right\}.\ }$

여기서 ${\$은(는) 최적의 정책이고$$, $V{\displaystyle {}^{}}$ ${\displaystyle {\pi }^{}}$은$($는){\$displaystyle V^{\pi *}}$은 최적의 정책의 값 함수를 가리킨다$$. 위의 방정식은 가장 높은 기대 수익을 주는 조치를 취했을 때의 보상을 설명한다.

참고 항목

• 벨만 가성법
• 동적 프로그래밍 – 문제 최적화 방법
• 해밀턴-자코비-벨만 방정식
• 마르코프 의사결정 과정
• 최적제어이론
• 최적 하부구조
• 재귀적 경쟁 평형
• 확률론적 동적 프로그래밍

참조