\documentclass[a4paper]{article}
\usepackage{amssymb,amsmath,latexsym}
\usepackage{theorem}
  \theorembodyfont{\upshape}
  \theoremstyle{break}
  \newtheorem{Def}{Definition}[section]
  \newtheorem{Thm}[Def]{Theorem}
  \newtheorem{Lem}[Def]{Lemma}
  \newtheorem{Cor}[Def]{Corollary}

%\topmargin = -1cm
%\oddsidemargin = 0cm  \evensidemargin =0cm 
%\textheight = 24cm  \textwidth = 16.5cm 


\makeatletter
\@addtoreset{equation}{section}
\def\theequation{\thesection.\arabic{equation}}
\makeatother

\def\dfrac#1#2{\displaystyle\frac{#1}{#2}}
\def\cfrac#1#2{\dfrac{\mathstrut #1}{#2}}

\begin{document}

\title{
Dynamic Programming creates The Golden Ratio, too
}
\author{
��{����i��B��w��w�@�o�ϊw�����@�j
Seiichi Iwamoto,\\ 
Faculty of Economics, Kyushu University, Fukuoka 812-8581, Japan\\ 
iwamoto@en.kyushu-u.ac.jp
\and
���c�����i��t��w���w���jMasami Yasuda\\ 
Faculty of Science, Chiba University, Chiba 263-8522, Japan\\ 
yasuda@math.s.chiba-u.ac.jp
}

\date{%\today%
}

\maketitle


\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 Bellman equation. 
}

%\keyword
Keywords:
\textit{%
Dynamic Programming; The Golden Ratio; Allocation problem; 
Optimal Control.
}

\section{Introduction}
\label{sec1}

The Golden Ratio($\phi = 1.161803\cdots $) has been a profound influence 
since ancient times such as the Parthenon at Athens. 
The shape of the Golden Ratio is supposed to be interesting 
in a graphic forms for their sculptures and 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 $\phi-$related topics 
in an engaging and easy-to-understand format.

The Fibonacci sequence(1,1,2,3,5,8,13,$\cdots$ ) 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's curse of dimensionality conquers the computational
explosion with the problem dimension through the use of parametric
representations. The more it's in a complex, the more it is divided.
When a problem were needed in a multi-stage or sequential decision,
we should consider the problem in repeatedly. 
If the procedure of this reduction gives a self-similar one, 
the methodology shows its effectiveness.  
The Golden Ratio is created repeatedly by its own in a quite same form.
Recurrence relations are ubiquitous including that a beautiful 
continued fraction represents the Golden number. 
It is interesting that this quite introductory problem of Dynamic
programming produce the basic mathematical aspects. 
%We are afraid that
%there might be discussions in a journal already.

 
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.


\section{Dynamic Programming}
\label{DP}

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 illustrated. It is composed as 
$(S,A,r,T)$.
Let $S$ be a state space in the Euclidean space
$R$ and $A=(A_x), A_x \subset R, x \in S$ means a feasible action
space depending on a current state $x \in S$.
The immediate reward is a function of 
$r=r(x,a,t), x \in S, a \in A_x, t=0,1,2,\cdots  $.
And the terminal reward $K=K(x), x \in S$ is given.
The transition law from the current $x$ to the new $y = m(x,a,t)$
by the action or decision $ a \in A_x$ at a time $t$.
If the transition law $m(x,a,t)$ does not depend $t$,
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 $a_t$
will be depend on the decision history.
Assume its value at time $t$ denoted by $x_t$, which enjoy the
following properties:
 \begin{itemize}
    \item [(a)] The value of $x_t$ is observable at time $t$.
    \item [(b)] The sequence $\{ x_t \}$ follow a recurrence in time:
   \begin{equation}\label{eq:21}
     x_{t+1} = m(x_t, a_t, t). 
   % (2.1)
   \end{equation}
     It is termed that the function 
     $y = m(x,\pi(x,t),t)$ means a move from the current $x$ to the 
     next $y$ at $t$ so 
     the law of motion or the plant equation by adapting a policy
     $a= \pi(x,t)$.
    \item [(c)] The set of $a_t$ may adopt depends on $x_t$ and $t$.
    \item [(d)] The cost function $C_\pi(x,t) $ starting a state $x$
    at time-to-go $T_t = T-t$ to optimize 
    over all policies $\pi$ has the additive form;
   \begin{equation}\label{eq:22}
      C_\pi(x_0,t_0 ) = \sum_{t=t_0}^{T-1} r(x_t,a_t,t) + K(x_T)
   % (2.2)
   \end{equation}
   with $x_0 = x_{t_0}$ and 
      $$
       x_{t+1} = m(x_t,\pi(x_t,t),t ), \quad a_t = \pi(x_t,t)
      $$
   where $T$ is a given finite planning horizon.
   % If $T < \infty$, the problem is a finite horizon of planning 
   % problem and alternatively if it is $T=\infty$ and 
   %\begin{equation}\label{eq:23}
   %   C = \sum_{t=0}^{\infty} g(x_t,a_t,t), 
   %% (2.3)
   %\end{equation}
   % provided it is convergent,
   % is an infinity horizon of planning problem.
 \end{itemize}

Let 
$$
 F(x,t) = \inf_{\pi} C_{\pi }(x,t).
$$
It is well known that the optimization with state structure of 
recursively satisfies the optimality equation(DP equation):
 \begin{equation}\label{eq:24}
    F(x,t+1) = \inf_{a \in A_x} [r(x, a, t) 
    + F(m(x,a,T_t), t)]
 % (2.4)
 \end{equation}
with the boundary $F(x,T) = K(x)$
where $T_t = T-t$ for $x \in S$, $0 \leq t < T $.

All of these are referred from text books by Bertsekas\cite{Ber76}, Whittle\cite{Whi82}, 
Sniedovich\cite{Sni92}, etc.

The relation between The Golden ratio formula and Fibonacci sequence 
is known as \cite{Dun97} etc.
To produce the Fibonacci sequence, it is a good example in
a recursive programming\cite{Knu97}.
Also the Fibonacci sequence are related with continued fraction.
For the notation of continued fraction, 
we adopt ourself to the following notations:
\[  b_0 + \cfrac{c_1}{b_1 +
           \cfrac{c_2}{b_2 +
            \cfrac{c_3}{b_3 +
              \cfrac{c_4}{b_4+ \cdots }}}}
= b_0 + \dfrac{c_1}{b_1 +} \dfrac{c_2}{b_2 +} 
         \dfrac{c_3}{b_3 + } \dfrac{c_4}{b_4 + } \cdots. 
\] 

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

This reproductive property suggests our fundamental claim for 
the following a typical example of Dynamic Programming.
Before we solve the problem, let us induce sequences
$ \{\phi_n\}$  as
\begin{equation}
\label{eq:2-5}
  \phi_{n+1} = 1 + \dfrac{1}{1 + {1}/{\phi_n} } 
    = 1 + \dfrac{1}{1+}\dfrac{1}{\phi_n} \quad (n \ge 1),\ 
  \phi_1 = 1.
\end{equation}
Also let $\{\hat{\phi_n}\}$ as
\begin{equation}
\label{eq:2-6}
  \begin{array}{l}
  \hat\phi_{n+1} 
    = \dfrac{1}{1+}\dfrac{1}{1+}{\hat\phi_n} \quad (n \ge 1), \ 
  \hat\phi_1 = 1, \\
  i.e. \\ 
  \hat\phi_{n+1}^{-1} = \dfrac{1}{\hat\phi_{n+1}}=  1+ \dfrac{1}{1 + \hat\phi_n } 
    = 1 + \dfrac{1}{1+}{\hat\phi_n} \quad (n \ge 1). 
  \end{array}
\end{equation}

\noindent
The sequence $\{ \phi_{n} \} $ of (\ref{eq:2-5})  satisfies
\[
 \begin{array}{ll}
  \phi_{n+1} % & = 1 + \cfrac{1}{1+\cfrac{1}{\phi_n}} 
             %   = 1 + \dfrac{1}{1+}\dfrac{1}{\phi_n} \\[2ex] 
          & = 1 + 
               \dfrac{1}{1+}\dfrac{1}{1+}\dfrac{1}{1+}
               \dfrac{1}{\phi_{n-1}} \\
          & = 1 + 
               \dfrac{1}{1+}\dfrac{1}{1+}\dfrac{1}{1+}
               \dfrac{1}{1+}\dfrac{1}{1+}
               \dfrac{1}{\phi_{n-2}} \\
 \end{array}
\]


\noindent
Similarly $\{ \hat\phi_{n} \} $ of (\ref{eq:2-6}) 
satisfies
\[
 \begin{array}{ll}
  \dfrac{1}{\hat\phi_{n+1}} 
          % & = 1 + \dfrac{1}{1 + \hat\phi_{n}}
          %   = 1 + \dfrac{1}{1+}\hat\phi_{n} \\ 
          & = 1 + 
               \dfrac{1}{1+}\dfrac{1}{1+}\dfrac{1}{1+}
               {\hat\phi_{n-1}} \\
          & = 1 + 
               \dfrac{1}{1+}\dfrac{1}{1+}\dfrac{1}{1+}
               \dfrac{1}{1+}{\hat\phi_{n-2}} \\
 \end{array}
\]



\noindent
From this definition, it is seen easily that
\begin{equation}
   \lim_{n \rightarrow \infty } \phi_n = \phi  = (\sqrt{5}+1)/2
\end{equation}
\begin{equation}
   \lim_{n \rightarrow \infty } \hat\phi_n  
   =  1/\phi = (\sqrt{5}-1)/2
\end{equation}







%=== section 3 ================================================
\section{Linear-Quadratic Control problem}
\label{LQ}

The Linear Quadratic(LQ) control problem is to consider
minimizing a control for the linear system
over the quadratic cost function.
If the state of system $\{ x_t \}$ moves on
\begin{equation}
 %x_{n+1} =  x_n +  u_n + \epsilon_n , \ n=1,2,\cdots
 x_{t+1} =  x_t +  a_t, \ t=0,1,2,\cdots
\end{equation}
with $x_0 =1$ by an input control $\{ a_t, -\infty < a_t < \infty \}$
%with a random noize $\epsilon_n$ such that $E\epsilon_n =0$
. 
The cost incured is
\begin{equation}
  %\sum_{n=1,2,\cdots,n} E(x_n^2 + u_n^2).
  \sum_{t=0,1,2,\cdots,T-1} (x_t^2 + a_t^2) + x_T^2.
\end{equation}



LQ of the DP equation
\begin{equation}
  \label{eq:LQ} 
   v_{t+1}(x) 
 = \min_{a \in A_x} \left\{ r(a,x) + v_{t}(a+x)\right\}
\end{equation}
where
\[ 
  \begin{array}{l}
    r(a,x) = a^2 + x^2, \\
    a \in A_x = (-\infty, \infty ),
    x \in (-\infty, \infty ) 
  \end{array}
\] 




\begin{Thm}
 The solution of (\ref{eq:LQ}) is given by 
 \[\left\{
  \begin{array}{l}
   v_0(x) = \phi_T x^2 \\[1.2ex]
   v_t(x) = \phi_{T-t} x^2, t= 1,2,\cdots 
  \end{array} \right.
 \] 
using the Golden number related sequence $\{ \phi_n \} $ by
(\ref{eq:2-5}).
\end{Thm}

\noindent
{\it (Proof)}
The proof is immediately obtained by the elementary quadratic
minimization and then the mathematical induction.
$\Box$

%==== section 4 =======================================
\section{Allocation problem}
\label{Alloc}

Allocation problem or sometime called as partition problem 
is the problem of the form
\begin{equation}
  \label{eq:AL} 
   v_{t+1}(x) 
 = \min_{a \in A_x} \left\{ r(a,x) + v_{t}(a)\right\}
\end{equation} 
for $ t= 0,1,2,\cdots, T,$ where
\[ 
  \begin{array}{l}
    r(a,x) = a^2 + (x - a)^2, \\
    a \in A_x = [0, x],
    x \in (-\infty, \infty ) .
  \end{array}
\] 



\begin{Thm}
The solution of (\ref{eq:AL}) is given by using the dual
golden number as
\[
\left\{
  \begin{array}{l}
   v_0(x) = \hat\phi_T x^2 \\[1.2ex]
   v_t(x) = \hat\phi_{T-t} x^2, t= 1,2,\cdots 
  \end{array} \right.
\] 
\end{Thm}

\noindent
{\it (Proof)}
Using the Schwartz inequality, the following holds
immediately:
For given positive constants $A$ and $B$ with a fixed $x$,
$$
 \min_{0 \le a \le 1} \{ A a^2 + B(x-a)^2 \} = \dfrac{x^2}{1/A + 1/B}. 
$$ 
So the proof could be done inductively. $\Box$ 










\vspace{2ex}
\noindent
{\bf Remark 1 :} We note here that the number $\phi^{-1}= 0.618\cdots$ of reciprocal of 
the Golden number is called sometimes 
{\it The Dual Golden number}. The above two problems are closely related.

\vspace{2ex}
\noindent
{\bf Remark 2 :} It is seen that the same quadratic function
 of the form; $ v(x) = C x^2$ where $c$ is a constant, 
 becomes a solution if
 the DP equation is, for Allocation and LQ,
\begin{equation}
  \label{eq:AL2} 
   v_{t+1}(x) 
 = \min_{a \in A_x} 
   \left\{ r(a,x) + 2 \int_{0}^{a}v_{t}(y)/y \, dy\right\}
\end{equation} 
\begin{equation}
  \label{eq:LQ2} 
   v_{t+1}(x) 
 = \min_{a \in A_x} 
   \left\{ r(a,x) + 2 \int_{0}^{a+x}v_{t}(y)/y \, dy \right\}
\end{equation}
respectively. Refer to \cite{Iwa05}.


\begin{thebibliography}{99}

\bibliography{}

\bibitem{Ber76}
   Dimitri P Bertsekas,
   {\it Dynamic Programming and Stochastic Control},
   Academic Press, New York, 1976.

\bibitem{Iwa87}
   Seiichi Iwamoto,
   {\it Theory of Dynamic Program(in Japanese)}, Kyushu Univ. Press,
   Fukuoka, Japan 1987.

\bibitem{Iwa05}
   Seiichi Iwamoto, 
   {\it Controlled integral equations on nondeterminstic dynamic programming: 
   Fredholm and Volterra types}, 
   Abstract of Math Soc Japan, Statistic Division, 51--52, March, 2003.
   
\bibitem{Whi82}
   Peter Whittle, 
   {\it Optmization over Time,
   Dynamic Programming and Stochastic Control, Vol.I},
   John Wiley \& Sons Ltd, New York, 1982.

\bibitem{Sni92}
   Moshe Sniedovich,
   {\it Dynamic Programming},
   Marshal Dekker, Inc. New York, 1992.

\bibitem{Knu97}
   D E Knuth,
   {\it The Art of Computing Programming: Vol 1
    Fundamental Algorithms},
    Addison-Wesley, third edition,  1997.

\bibitem{Dun97}
   R A Dunlap,
   {\it The Golden Ratio and Fibonacci Numbers},
    World Scientific Press, 1997.

\bibitem{Kno97}
 Ron Knott, 
 %Surrey University in Guildford, UK
 ``Fibonacci Numbers and the Golden Section'' in
 {\tt 
http://www.mcs.surrey.ac.uk/\-Personal/\-R.Knott/\-Fibonacci/fib.html}

\end{thebibliography}

\end{document}
