数理解析研究所講究録 1477 巻 2006 年 136-140

138

Dynamic Programming creates The Gold enRatio, too
岩本誠一 (九州大学大学院経済学研究院) Seiichi Iwamoto,
Faculty of Economics, Kyushu University, Fukuoka 812-8581, Japaniwamoto@en.kyushu-u.ac.jp
安田 正實 (千葉大学理学部) Masami Yasuda

Faculty of Science, Chiba University, Chiba 263-8522, Japan
yasuda@math.s.chiba-u.ac.jp
Abstract
Since ancient times of Greek as the Parthenon at Athens, the Golden
Ratio has been keeping to give a profound influence in many various fields.
Mathematicians love the number to explain the nature of the universe
and of human life. It comes up even with a formula for the human decision making process; aesthetics, etc. Also in the typical sequential or
multi-stage decision processes, the rule is not exceptional. We will show
a few explicit famous problems which cooperate with Dynamic Programming: Allocation problem and Linear-Quadratic control problem. For
both problems, there appears the Golden Ratio(\phi ) in the solution of Bell-man equation.

Keywords: Dynamic Programming; The Golden Ratio; Allocation problem; Optimal Control.

1Introduction

The Golden Rat $p\mathrm{o}j(\phi=1.161803\ldots)$ has been a profound influence sinceancient times such as the Parthenon at Athens. The shape of the Golden
Ratio is supposed to be interesting in a graphic forms for their sculpturesand paintings. The beauty appears even in the ingredient of nature creatures. The most influential mathematics textbook by Euclid of Alexandria
defines the proportion. These information presents a broad sampling of-related topics in an engaging and easy-to-understand format.
The Fibonacci sequence(1,1,2,3,5,8,13,) occurs closely the Golden
Ratio between two successive numbers. It is known also that the diagonal summation produces the Fibonacci sequence in the Pascal’s triangle.
These repeated procedure or iteration have something in common.
The principle of Dynamic Programming is said to ’divide and conquer’.
In fact, if it is not possible to work out directly, divide up a problem
into smaller ones. The basic idea of Dynamic Programming is aiming
to provide effective sub-problem to the original problem. The Bellman’scurse of dimensionality conquers the computational explosion with theproblem dimension through the use of parametric representations. The
more it’s in a complex, the more it is divided. When a problem were$\phi$$\cdots$

137
needed in a multi-stage or sequential decision, we should consider theproblem in repeatedly. If the procedure of this reduction gives a selfsimilar one, the methodology shows its effectiveness. The Golden Ratio iscreated repeatedly by its own in a quite same form. Recurrence relations
are ubiquitous including that a beautiful continued fraction represents theGolden number. It is interesting that this quite introductory problem ofDynamic programming produce the basic mathematical aspects.
In the following section, we treat a few exact problems which is typical of Dynamic Programming; Allocation problem and Linear-Quadratic
Control problem. However problems are in a simple fashion, it figure out
the essence of Dynamic Programming.

2Dynamic Programming

The conceptual cluster of Dynamic Programming are profound ed throughout the mathematics. Not only the analytical aspect of optimization
method, but also the repeated structure of investigate problem. To give a
useful explanation and an interesting implication, we show some problems
which are quit easy and explicitly solved.
First the general setting of Dynamic Programming problem are illusbe a state space in thetrated. It is composed as $(5, A, r, T)$ . Let, $x\in S$ means a feasible action
Euclidean space and $A=(A_{x})$ ,space depending on a current state $x\in S$ . The immediate reward is a. And the terminal
function of $r=r(x, a, t)$ , $x\in S$, $a\in A_{x}$ , $t=0,1,2$ ,reward $K=K(x)$ , $x\in S$ is given. The transition law from the current
to the new $y=m(x, a, t)$ by the action or decision $a\in A_{x}$ at a time .
If the transition law $m(x, a, t)$ does not depend , it is called a stationary$m(x, a, t)$ and we treat it in this paper. Here we consider additive costs
and the optimal value of will be depend on the decision history. Assume
its value at time denoted by $t, which enjoy the following properties:
is observable at time .
(a) The value offollow a recurrence in time:(b) The sequence$S$$A_{x}\subset R$$R$$\cdots$

$x$

$t$

$t$

$a_{t}$$t$$t$$x_{\mathfrak{t}}$$\{x_{t}\}$$x_{t+1}=m(x_{t}, a_{t}, t)$.

(2.1)

It is termed that the function $y=m(x, \pi(x, t), t)$ means a move fromthe current to the next at so the law of motion or the plant
equation by adapting a policy $a=\pi(x, t)$ .
and .
(c) The set of at may adopt depends on$=T-t$
starting a state at time-to-go(d) The cost function
to optimize over all policies has the additive form;
$x$

$t$

$y$

$t$

$x_{\mathrm{t}}$$C_{\pi}(x, t)$$T_{t}$

$x$

$\pi$

,

$C_{\pi}(x_{0}, t_{0})= \sum_{t=t_{0}}^{T-1}r(x_{\ell}, a_{t}, t)+\mathrm{K}(\mathrm{x})$with $x0=x_{t_{0}}$ and$x_{t+1}=m(x_{t}, \pi(x_{\mathrm{f}}, t), t)$,$a_{\mathrm{t}}=\pi(x_{t}, t)$where $T$ is a given finite planning horizon.

Let$F(x, t)=$$\inf_{\pi}$$C_{\pi}(x, t)$.

(2.2)

138
It is well known that the optimization with state structure of recursively
satisfies the optimality equation(DP equation) :(2.3)$F(x, t+1)= \inf_{a\in x}[r(x, a, t)+F(m(x_{\mathrm{t}}a, T_{C}), t)]$for $x\in S$ , $0\leq t<T$ .
with the boundary $F(x, T)$ $=K(x)$ where
Whittle[4],Bertsekas[l],All of these are referred from text books by$T_{\mathrm{t}}=T-t$

Sniedovich[ , etc.
The relation between The Golden ratio formula and Fibonacci sequence is known as [7] etc. To produce the Fibonacci sequence, it is
Also the Fibonacci sea good example in a recursive programming
quence are related with continued fraction. For the notation of continued
fraction, we adopt ourself to the following notations;$5\mathrm{j}$$b\mathit{0}+$$=b_{0}+ \frac{c_{1}}{b_{1}+}\frac{c_{2}}{b_{2}+}\frac{c_{3}}{b_{3}+}\frac{c_{4}}{b_{4}+}\cdots$$c_{1}c_{2}$.

$b_{1}+$$b_{2}+ \frac{c_{3}}{b_{3}+\frac{\mathrm{c}_{4}}{b_{4}+}}\ldots$

Note that the Golden number satisfy the quadratic equation:$1+\phi$ .
By using this relation repeatedly, $\phi=1+\frac{1}{\phi}=1+\frac{1}{1+\frac{1}{\phi}}=$$\phi^{2}=$$1+ \frac{1}{1+}\frac{1}{\phi}=1+\frac{1}{1+}\frac{1}{1+}\frac{1}{\phi}=1+\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\cdots$. Similarly the reciprocal (orsometimes called as a dual Golden number) is denoted $\phi^{-1}=0.618$ $\cdots=$.

$\phi-1=\frac{1}{\phi}=\frac{1}{1+}\frac{1}{\phi}=\frac{1}{1+}\frac{1}{1+}\frac{1}{\phi}=\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\ldots$

This reproductive property suggests our fundamental claim for thefollowing a typical example of Dynamic Programming. Before we solveasthe problem, let us induce sequences$\{\phi_{n}\}$$(n\geq 1)$$\phi_{n+1}=1+\frac{1}{1+1/\phi_{n}}=1+\frac{1}{1+}\frac{1}{\phi_{n}}$Also let$\{\hat{\phi}_{\tau\iota}\}$, $\phi_{1}=1$ .

as$\hat{\phi}_{n+1}=\frac{1}{1+}\frac{1}{1+}\hat{\phi}_{n}$$(n\geq 1),\hat{\phi}_{1}=1$

,i.e.

(2.5)

$\hat{\phi}_{n+1}^{-1}=\frac{1}{\hat{\phi}_{n+1}}=1+\frac{1}{1+\hat{\phi}_{n}}=1+\frac{1}{1+}-n$

The sequence(2.4)$\{\phi_{n}\}$$(n\geq 1)$.

of (2.4) satisfies$\phi_{n+1}$$=1+ \frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{\phi_{n-1}}$

111111$=1+\overline{1+}\overline{1+}\overline{1+}\overline{1+}\overline{1+}\overline{\phi_{n-2}}$

Similarly$\{\hat{\phi}_{n}\}$of (2.5) satisfies$\frac{1}{\hat{\phi}_{n+1}}$$=1+ \frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\hat{\phi}_{n-1}$$=1+ \frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\frac{1}{1+}\hat{\phi}_{n-2}$

From this definition, it is seen easily that$\lim_{narrow\infty}\phi_{n}=\phi=(\sqrt{5}+1)/2$(2.6)$\lim_{narrow\infty}\hat{\phi}_{n}=1/\phi=(\sqrt{5}-1)/2$(2.3)

139Linear-Quadratic Control problem

3The Linear Quadratic(LQ) control problem is to consider minimizing acontrol for the linear system over the quadratic cost function. If the state
moves onof system$\{x_{t}\}$$x_{t+1}=x\iota$ $+a_{t_{j}}t=0,1$

with
is

$x\mathit{0}$$=1$, 2,(3.1)$\cdots$

by an input control $\{a_{\ell}, -\infty<a_{t}<\infty\}$ . The cost incured$t=0,1_{1}2, \cdot\cdot T-1\sum_{\prime}.(x_{l}^{2}+a_{t}^{2})+x_{T}^{2}$.

(3.2)

LQ of the DP equation(3.3)$v_{t+1}(x)= \min_{a\in A_{\mathrm{a}\mathrm{e}}}\{r(a, x)+v_{l}(a+x)\}$where$r(a, x)=a^{2}+x^{2}$ ,$a\in A_{x}=(-\infty, \infty)$, $x\in(-\infty, \infty)$

Theorem 3. 1
The solution of (3.3) is given by$v_{0}(=\phi\tau x^{2}$$\{$$v_{\mathrm{t}}(x)=\phi_{T-\mathrm{t}}x^{2}$, $t=1,2$ ,using the Golden number related sequence$\{\phi_{n}\}$$\cdots$by (2.4).

(Proof) The proof is immediately obtained by the elementary quadratic
minimization and then the mathem atical induction.
$\square$4

Allocation problem

Allocation problem or sometime called as partition problem is the problemof the form
(4.1)

$v_{\mathrm{t}+1}(x)= \min_{a\in A_{x}}\{r(a, x)+v_{t}(a)\}$for $t=0,1,2$ ,$\cdots$, , where$T$$r(a, x)=a^{2}+(x-a)^{2}$ ,$a\in A_{x}=[0, x]$ , $x\in(-\infty, \infty)$.

Theorem 4. 1
The solution of (4.1) is given by using the dual golden number as$v0(x)=\hat{\phi}\tau x^{2}$$\{$$v_{\ell}(x)=\hat{\phi}_{T-t}x^{2}$, $t=1,2$ ,$\cdot$..

(Proof) Using the Schwartz inequality, the following holds immediately:
For given positive constants and $B$ with a fixed ,
$A$

$x$

$\min_{0\leq a\leq 1}\{Aa^{2}+B(x-a)^{2}\}=\frac{x^{2}}{1/A+1/B}$

So the proof could be done inductively,$\square$.

140
Remark 1 : We note here that the number $\phi^{-1}=0.618\cdots$ of reciprocalof the Golden number is called sometimes The Dual Golden number. The
above two problem are closely related.
$\mathrm{s}$Remark 2 : It is seen that the same quadratic function of the form;$v(x)=Cx^{2}$ whereis a constant, becomes a solution if the DP equationis, for Allocation and,$c$$\mathrm{L}\mathrm{Q}$$v_{\mathrm{f}+1}$(4.2)$( =\min_{a\in A_{x}}\{r(a, x)+2\int_{0}^{a}v_{t}(y)/ydy\}$$v_{t+1}(x)= \min_{a\in A_{x}}\{r\langle a$, )+2 $\int_{0}^{a+x}v_{t}(y)/ydy\}$$x$(4.3)

respectively. Refer to [3].

References[1] Dimitri P Bertsekas, Dynamic Programming and Stochastic Control,
Academic Press, New York, 1976.

[2] Seiichi Iwamoto, Theory of Dynamic Program(in Japanese), Kyushu
Univ. Press, Pukuoka, Japan 1987.
[3] Seiichi Iwamoto, Controlled integral equations on nondeterminstic dynarnic programming: Fredholm and Volterra types, Abstract of Math
Soc Japan, Statistic Division, 51-52, March, 2003.

[4] Peter Whittle, Optmization over Time, Dynamic Programming andStochastic Control, Vol. I, John Wiley & Sons Ltd, New York, 1982.
[5] Moshe Sniedovich, Dynamic Programming, Marshal Dekker, Inc.
New York, 1992.
[6] DE Knuth, The Art of Computing Programming: Vol1 Fundamental
A lgorithms, Addison-Wesley, third edition, 1997.
[7] R A Dunlap, The Golden Ratio and Fibonacci Numbers, World Scientific Press, 1997.
[8] Ron Knott,“Fibonaccition”
inkttp:Numbers$//\mathrm{w}\mathrm{w}\mathrm{w}.\mathrm{m}\mathrm{c}\mathrm{s}$$\mathrm{F}\mathrm{i}\mathrm{b}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{i}/\mathrm{f}$ib . html.surrey.

andtheGoldenSec-$\mathrm{a}\mathrm{c}.\mathrm{u}\mathrm{k}/\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}/\mathrm{R}.\mathrm{K}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{t}/-$