Golden optimal path in discrete-time dynamic optimization processes

Seiichi IWAMOTO and Masami YASUDA

Department of Economic Engineering Graduate School of Economics, Kyushu University Fukuoka 812-8581, Japan

tel&fax. +81(92)642-2488, email: iwamoto@en.kyushu-u.ac.jp

and Department of Mathematical Science Faculty of Science, Chiba University Chiba 263-8522, Japan

tel&fax. +81(43)290-3662, email: yasuda@math.s.chiba-u.ac.jp

Abstract

We are concerned with dynamic optimization processes from a viewpoint of Golden optimality. A path is called Golden if any state moves to the next state repeating the same Golden section in each transition. A policy is called Golden if it, together with a relevant dynamics, yields a Golden path. The probelm is whether an optimal path/policy is Golden or not. This paper minimizes a quadratic criterion and maximizes a square-root criterion over an infinite horizon. We show that a Golden path is optimal in both optimizations. The Golden optimal path is obtained by solving a corresponding Bellman equation for dynamic programming. This in turn admits a Golden optimal policy.

1 Introduction

Recently the Golden optimal solution, its duality, and its equivalence have been discussed in static optimization problems [4–6]. In this paper we consider the Golden optimal solution in dynamic optimization problems.

We consider two typical types of criterion — quadratic and square-root — in a deterministic optimization. We minimize quadratic criteria

I(x) = ∑_{n=0}^{∞} [x_{n}^{2} + (x_{n} − x_{n+1})^{2}] , J(x) = ∑_{n=0}^{∞} [(x_{n} − x_{n+1})^{2} + x_{n+1}^{2}]

and maximize square-root criteria

K(x) = ∑_{n=0}^{∞} β^{n} (\sqrt{x_{n}} + \sqrt{x_{n} − x_{n+1}} ) , L(x) = ∑_{n=0}^{∞} β^{n} (\sqrt{x_{n} − x_{n+1}} + \sqrt{x_{n+1}} )

, respectively. Here β is 0 < β < 1. The differences between I and J and between K and L are

J(x) = I(x) − x_{0}^{2}
L(x) = K(x) + ∑_{n=0}^{∞} (β^{n−1} − β^{n}) \sqrt{x_{n}} (β^{−1} = 0).

We show that a Golden path is optimal in these four optimization problems. The Golden optimal path is obtained by solving Bellman equation for dynamic programming [3,7].

2 Golden Paths

A real number

ϕ = \frac{1 + \sqrt{5}}{2} ≈ 1.618

is called Golden number [1,2,8]. It is the larger of the two solutions to quadratic equation

x^{2} − x − 1 = 0.  (1)

Sometimes (1) is called Fibonacci quadratic equation. The Fibonacci quadratic equation has two real solutions: ϕ and its conjugate \overline{ϕ} := 1 − ϕ. We note that

ϕ + \overline{ϕ} = 1, ϕ ·\overline{ϕ} = −1.

Further we have

ϕ^{2} = 1 + ϕ, \overline{ϕ}^{2} = 2 − ϕ
ϕ^{2} + \overline{ϕ}^{2} = 3, ϕ^{2} ·\overline{ϕ}^{2} = 1.

A point (2−ϕ)x splits an interval [0, x] into two intervals [0, (2−ϕ)x] and [(2−ϕ)x, x]. A point (ϕ − 1)x splits the interval into [0, (ϕ − 1)x] and [(ϕ − 1)x, x]. In either case, the length constitutes the Golden ratio (2 − ϕ) : (ϕ − 1) = 1 : ϕ. Thus both divisions are the Golden section.

Definition 2.1 A sequence x : {0, 1, … } → R^{1} is called Golden if and only if either

\frac{x_{t+1}}{x_{t}} = ϕ − 1 or \frac{x_{t+1}}{x_{t}} = 2 − ϕ.

Lemma 2.1 A Golden sequence x is either

x_{t} = x_{0}(ϕ − 1)^{t} or x_{t} = x_{0}(2 − ϕ)^{t}.

O x

t +  +  +  +  +  +  +

+ + +

1  2  3  4  5

1 2 3

Fig. 1 Golden paths x = c(ϕ − 1)^{t} c = 1, 2, 3

O x

t +  +  +  +  +  +  +

+ + +

1  2  3  4  5

1 2 3

Fig. 2 Golden paths (c) x = c(2 − ϕ)^{t} c = 1, 2, 3

We remark that

(ϕ − 1)^{t} = ϕ^{−t}, (2 − ϕ)^{t} = (1 + ϕ)^{−t}

where

ϕ − 1 = ϕ^{−1} ≈ 0.618, 2 − ϕ = (1 + ϕ)^{−1} ≈ 0.382

Let us introduce a controlled linear dynamics with real parameter b as follows.

x_{t+1} = bx_{t} + u_{t} t = 0, 1, …  (2)

where u : {0, 1, … } → R^{1} is called control. If u_{t} = px_{t}, the control u is called proportional, where p is a real constant, proportional rate. A sequence x satisfying (2) is called path.

Definition 2.2 A proportional control u on dynamics (2) is called Golden if and only if it generates a Golden path x.

Lemma 2.2 A proportional control u_{t} = px_{t} on (2) is Golden if and only if

p = −b + ϕ − 1 or p = −b + 2 − ϕ.  (3)

3 Control processes

This section minimizes two quadratic cost functions

∑_{n=0}^{∞} [x_{n}^{2} + (x_{n} − x_{n+1})^{2}] and ∑_{n=0}^{∞} [(x_{n} − x_{n+1})^{2} + x_{n+1}^{2}] .

Both problems are solved as a control process with criterion

∑_{n=0}^{∞} (x_{n}^{2} + u_{n}^{2}) and ∑_{n=0}^{∞} (u_{n}^{2} + x_{n+1}^{2})

under a common additive dynamics with a given initial state

x_{n+1} = bx_{n} + u_{n}, x_{0} = c

where c ∈ R^{1}.

3.1 Quadratic in current state

Let us now consider a control process with an additive transition T (x, u) = bx + u. Here b is a constant, which represents a characteristics of the process :

minimize ∑_{n=0}^{∞} (x_{n}^{2} + u_{n}^{2})
subject to (i) x_{n+1} = bx_{n} + u_{n}
C(c)  n ≥ 0

(ii) − ∞ < u_{n} < ∞

(iii) x_{0} = c.

Let v(c) be the minimum value of C(c). Then the value function v satisfies Bellman equation [3]:

v(x) = min_{−∞<u<∞} [x^{2} + u^{2} + v(bx + u)] .  (4)

Eq. (4) has a quadratic form v(x) = vx^{2}, where v ∈ R^{1}.

Lemma 3.1 The control process C(c) with characteristic value b (∈ R^{1}) has a proportional optimal policy f^{∞}, f(x) = px, and a quadratic minimum value function v(x) = vx^{2}, where

v = \frac{b^{2} + \sqrt{b^{4} + 4}}{2} ,  p = − \frac{v}{1 + v} b.

The proportional optimal policy f^{∞} splits at any time an interval [0, x] into [0, (b +

p)x] = [0, \frac{bx}{1 + v} ] and [ \frac{bx}{1 + v} , x] . In particular, when b = 1, the quadratic coefficient

v is reduced to the Golden number

ϕ = \frac{1 + \sqrt{5}}{2} ≈ 1.618

Further the division of [0, x] into [0, \frac{x}{1 + ϕ} ] and [ \frac{x}{1 + ϕ} , x] is Golden. A quadratic

function w(x) = ax^{2} is called Golden if a = ϕ.

Theorem 3.1 The control process C(c) with characteristic value b = 1 has a Golden optimal policy f^{∞}, f(x) = (1 − ϕ)x, and the Golden quadratic minimum value function v(x) = ϕx^{2}.

3.2 Qquadratic in next state

Here we consider the cost function r : X×U → R^{1} which is quadratic in current control and next state :

r(x, u) = u^{2} + (bx + u)^{2}.

Then a control process is represented by the following sequential minimization problem :

minimize ∑_{n=0}^{∞} (u_{n}^{2} + x_{n+1}^{2})
subject to (i) x_{n+1} = bx_{n} + u_{n}
C′(c)  n ≥ 0
(ii) − ∞ < u_{n} < ∞
(iii) x_{0} = c.

The value function v satisfies Bellman equation [3]:

v(x) = min_{−∞<u<∞} [u^{2} + (bx + u)^{2} + v(bx + u)] .  (5)

Eq. (5) has a quadratic solution v(x) = vx^{2}, where v ∈ R^{1}.

Lemma 3.2 The control process C′(c) with characteristic value b has a proportional optimal policy f^{∞}, f(x) = px, and a quadratic minimum value function v(x) = vx^{2}, where

v = \frac{b^{2} − 2 + \sqrt{b^{4} + 4}}{2} ,  p = − \frac{1 + v}{2 + v} b.

The policy f^{∞} splits an interval [0, x] into [0, \frac{bx}{2 + v} ] and [ \frac{bx}{2 + v} , x] . When b = 1,

the coefficient v is reduced to the inverse Golden number

ϕ^{−1} = ϕ − 1 = \frac{−1 + \sqrt{5}}{2} ≈ 0.618

Further the division of [0, x] into [0, (2 − ϕ)x] and [(2 − ϕ)x, x] is Golden. A quadratic function w(x) = ax^{2} is called inverse Golden if a = ϕ^{−1}.

Theorem 3.2 The control process C′(c) with characteristic value b = 1 has a Golden optimal policy f^{∞}, f(x) = (1 − ϕ)x, and the inverse Golden quadratic minimum value function v(x) = (ϕ − 1)x^{2}.

4 Allocation processes

This section maximizes two discounted square-root reward functions

∑_{n=0}^{∞} β^{n} (\sqrt{x_{n}} + \sqrt{x_{n} − x_{n+1}} ) and ∑_{n=0}^{∞} β^{n} (\sqrt{x_{n} − x_{n+1}} + \sqrt{x_{n+1}} ) .

Both problems are solved as an allocation process with criterion

∑_{n=0}^{∞} β^{n} (\sqrt{x_{n}} + \sqrt{u_{n}}) and ∑_{n=0}^{∞} β^{n} (\sqrt{u_{n}} + \sqrt{x_{n+1}} )

under a common subtractive dynamics with a given initial state

x_{n+1} = x_{n} − u_{n}, x_{0} = c

where c ≥ 0.

4.1 Square-root in current state

Let us now consider an allocation process with a subtractive transition T (x, u) = x − u :

Maximize ∑_{n=0}^{∞} β^{n} (\sqrt{x_{n}} + \sqrt{u_{n}})

subject to (i) x_{n+1} = x_{n} − u_{n}

A(c)  n ≥ 0

(ii) 0 ≤ u_{n} ≤ x_{n}

(iii) x_{0} = c.

Let v(c) be the maximum value of A(c). Then the maximum value function v satisfies the following Bellman equation:

v(x) = Max_{0≤u≤x} [\sqrt{x} + \sqrt{u} + βv(x − u)] .  (6)

Eq. (6) has a square-root form v(x) = v\sqrt{x}, where v ∈ R^{1}.

Let us adopt a proportional policy f^{∞} (f(x) = px) with proportional rate p (0 < p < 1). Then state x under the control u = px goes deterministically to the next state T (x, u) = x−u = x−px = (1−p)x. Thus we have x = (1−p)x+px. The state transition of control process A(c) governed by the proportional policy f^{∞} means that the current control u = px splits the state interval [0, x] into two intervals [0, (1−p)x] and [(1−p)x, x]. When the split yields a Golden section, the proportional policy f^{∞} (f(x) = px) is called Golden.

Lemma 4.1 The allocation process A(c) has a proportional optimal policy f^{∞}, f(x) = px, and a square-root maximum value function v(x) = v\sqrt{x}, where

v = \frac{2}{1 − β^{2}} , p = \frac{(1 − β^{2})^{2}}{(1 + β^{2})^{2}} .

We remark that the coefficient v is the solution to

v = 1 + \sqrt{1 + (βv)^{2}} , v ≥ 2.

Let us solve 1 − p = ϕ − 1 or 2 − ϕ. Then we have the following result.

Theorem 4.1 When β = ϕ (1 − \sqrt{ϕ − 1} ) ≈ 0.346 or β = \sqrt{ϕ} − \sqrt{ϕ − 1} ≈ 0.486, the proportional policy f^{∞}, f(x) = px, is Golden optimal.

4.2 Square-root in next state

Now we consider an allocation process with transition T (x, u) = x − u :

Maximize ∑_{n=0}^{∞} β^{n} (\sqrt{u_{n}} + \sqrt{x_{n+1}} )

subject to (i) x_{n+1} = x_{n} − u_{n}

A′(c)  n ≥ 0
(ii) 0 ≤ u_{n} ≤ x_{n}
(iii) x_{0} = c.

Let v(c) be the maximum value of A′(c). Then the maximum value function v satisfies an optimality equation:

v(x) = Max_{0≤u≤x} [\sqrt{u} + \sqrt{x − u} + βv(x − u)] .  (7)

Eq. (7) has a square-root solution v(x) = v\sqrt{x}, where v ∈ R^{1}.

Let us adopt a proportional policy f^{∞} (f(x) = px) with p (0 < p < 1). Then the current control u = px splits the interval [0, x] into [0, (1 − p)x] and [(1 − p)x, x].

Lemma 4.2 The allocation process A′(c) has a proportional optimal policy f^{∞}, f(x) = px, and a square-root maximum value function v(x) = v\sqrt{x}, where

v = \frac{β + \sqrt{2 − β^{2}}}{1 − β^{2}} , p = \frac{1 − β\sqrt{2 − β^{2}}}{2} .

Note that the coefficient v is the positive solution to

v = \sqrt{1 + (1 + βv)^{2}} .

By solving 1 − p = ϕ − 1, we have the following result.

Theorem 4.2 When β = \sqrt{1 − 2\sqrt{2ϕ − 3}} ≈ 0.168, the proportional policy f^{∞}, f(x) = px, is Golden optimal.

References

[1] A. Beutelspacher and B. Petri, Der Goldene Schnitt 2., überarbeitete und erweiterte Auflange, ELSEVIER GmbH, Spectrum Akademischer Verlag, Heidelberg, 1996.

[2] R.A. Dunlap, The Golden Ratio and Fibonacci Numbers, World Scientific Publishing Co.Pte.Ltd., 1977.

[3] S. Iwamoto, Theory of Dynamic Program: Japanese, Kyushu Univ. Press, Fukuoka, 1987.

[4] S. Iwamoto, Cross dual on the Golden optimum solutions, Mathematical Economics, Research Institute for Mathematical Sciences, Kyoto University, RIMS Kôkyûroku 1443, 2005, pp. 27–43.

[5] S. Iwamoto, The Golden optimum solution in quadratic programming, Ed. W. Takahashi and T. Tanaka, Proceedings of the International Conference on Nonlinear Analysis and Convex Analysis (Okinawa, 2005), Yokohama Publishers, Yokohama, 2007, pp.109–205.

[6] S. Iwamoto, The Golden trinity — optimility, inequality, identity —, Mathematical Economics, Research Institute for Mathematical Sciences, Kyoto University, RIMS Kôkyûroku 1488, 2006, pp. 1–14.

[7] S. Iwamoto and M. Yasuda, Dynamic programming creates the golden ratio, too, Decision-Making and Mathematical Model under Uncertainty, Research Institute for Mathematical Sciences, Kyoto University, RIMS Kôkyûroku 1477, 2006, pp. 136– 140.

[8] H. Walser, DER GOLDENE SCHNITT, B.G. Teubner, Leibzig, 1996.