SLIDE

INFORMS International Puerto Rico 2007

AM10:00–11:30, Sunday July 8

S. Iwamoto Kyushu Univ. & M. Yasuda Chiba Univ. July 6, 2007

The Golden Optimal Trajectories in Continuous Dynamic Optimization

Seiichi Iwamoto & Masami Yasuda

Faculty of Economics, Kyushu University Faculty of Science, Chiba University

The Golden Optimal

Trajectories

in Continuous Dynamic Optimization

Seiichi Iwamoto & Masami Yasuda Kyushu University & Chiba University

Japan

Is optimal policy Golden ? Continuous dynamic programming (DP) problems

1. Control process

2. Allocation process �. CONTROL PROCESSES Min

∫{∞ \atop 0}(x2 + u2) dt and  ∫{∞ \atop 0}(ẋ2 + u2) dt

under

ẋ = bx + u, x(0) = c.

�. ALLOCATION PROCESSES Max

∫{∞ \atop 0}e−ρt(√x + √u)dt and  ∫{∞ \atop 0}e−ρt√u dt

under

ẋ = bx − u, x(0) = c.

�. APPROACHES

(i) one-variable optimization method (ii) calculus of variation (Euler Eq.) (iii) dynamic programming (Bellman Eq.).

(i) and (ii) ⟹ Golden trajectory (iii) ⟹ Golden policy.

The Golden number

ϕ = \frac{1 + √5}{2} ≈ 1.61803

is the positive sol. to x^{2} − x − 1 = 0. Solutions: ϕ and conjugate \overline{ϕ} := 1 − ϕ.

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

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

Def. 1 A d’ble ft x : [0, ∞) → R^{1} is called Golden iff either

\frac{ẋ(t)}{x(t)} = log(ϕ − 1) or \frac{ẋ(t)}{x(t)} = log(2 − ϕ).

Lem. 1 A Golden ft x is either

x(t) = x(0)e−t log ϕ or x(t) = x(0)e−t log(1+ϕ).

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

O O

x

t + + + + +

+ + +

1 2 3 3 4 5 1 2 3

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

O

x

t + + + +

+ + +

1 2 3 4 3 2 1

+ 5

In Fig. 1

e−t log ϕ = et log(ϕ−1) = ϕ−t = (ϕ − 1)t. log ϕ ≈ 0.481, ϕ − 1 = ϕ−1 ≈ 0.618

In Fig. 2

e−t log(1+ϕ) = et log(2−ϕ) = (1 + ϕ)−t = (2 − ϕ)t. log(1 + ϕ) ≈ 0.962, 2 − ϕ = (1 + ϕ)−1 ≈ 0.382

Consider a controlled linear dynamics with real parameter b:

ẋ = bx + u on [0, ∞)  (1)

where u : R^{1} → R^{1} is called control function or control. If u(x) = px (resp. px+q), the control is called proportional (resp. linear), where p, q are real constants. A differentiable solution x to (1) is called trajectory.

Def. 2 A proportional control u on dynamics (1) is called Golden iff it generates a Golden trajectory .

Lem. 2 A proportional control u = px on (1) is Golden iff

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

Consider the first control process with b (−∞ < b < ∞) :

minimize ∫_{0}^{∞}(x^{2} + u^{2}) dt subject to (i) ẋ = bx + u

C(c)  0 ≤ t < ∞
(ii) u ∈ C^{1}
(iii) x(0) = c.

Let v(c) be the minimum value. Then v(0) = 0. The value function v = v(x) satisfies the BE

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

Lem. 3 A pair of proportional control and quadratic value function

û(x) = −kx, v(x) = kx^{2}, ( k = b + √b^{2} + 1 )

satisfies the BE.

Then the dynamical system

ẋ = −√b^{2} + 1 x, x(0) = c

yields a trajectory

x̂(t) = ce^{−√b^{2}+1 t}.

The proportional policy û generates an optimal trajectory x̂, which is not Golden. Thus the control process C(c) does not admit an Golden optimal policy. However, when b = \frac{1}{2} , the coefficient k reduces to the Golden ratio

k = ϕ.

Consider the second control process with b (−∞ < b < ∞) :

minimize ∫_{0}^{∞}(ẋ^{2} + u^{2}) dt subject to (i) ẋ = bx + u

C′(c)  0 ≤ t < ∞
(ii) u ∈ C^{1}
(iii) x(0) = c.

Let v(c) be the minimum value. Then

min_{−∞<u<∞} [(bx + u)^{2} + u^{2} + v′(x)(bx + u)] = 0, v(0) = 0. (3)

Lem. 4 A pair of proportional control and quadratic value function

û(x) = px, v(x) = kx^{2}

where

p = − \frac{1}{2} (2 + √2 )b, k = (1 + √2 )b

satisfies the BE.

Then the dynamical system

ẋ = − \frac{b}{√2} x, x(0) = c

yields an optimal trajectory

x̂(t) = ce^{−(b/√2)t}.

• Case (i) When b = √2 log(1 + ϕ) ≈ 1.361, the op. prop’l pol. û(x) = −(1 + √2 ) log(1 + ϕ) x ≈ −2.323 x is Golden . It generates the Golden trajectory

x̂(t) = ce^{−t log(1+ϕ)}.

• Case (ii) When b = √2 log ϕ ≈ 0.681, the optimal prop’l policy û(x) = −(1 + √2 ) log ϕ x ≈ −1.162 x is Golden . It generates the Golden trajectory

x̂(t) = ce^{−t log ϕ}.

�. ALLOCATION PROCESSES Max

∫{∞ \atop 0}e−ρt(√x + √u)dt and  ∫{∞ \atop 0}e−ρt√u dt

under

ẋ = bx − u, x(0) = c.

Consider a general control process Maximize ∫_{0}^{∞}e^{−ρt}f(x, u)dt subject to (i) ẋ = g(x, u)

A(c)  0 ≤ t < ∞

(ii) x ∈ C^{1}, u ∈ U(x)

(iii) x(0) = c.

Let v(c) be the maximum value. Then the value function v = v(x) satisfies BE :

ρv(x) = Max_{u∈U(x)} [f(x, u) + v′(x)g(x, u)]. (4)

Let’s solve the first allocation process with a discouted total square-root criterion :

Maximize ∫_{0}^{∞}e^{−ρt}(√x + √u)dt subject to (i) ẋ = bx − u

A(c)  0 ≤ t < ∞
(ii) x ∈ C^{1}, u ≥ 0
(iii) x(0) = c.

Then BE

ρv(x) = Max_{u≥0} [√x + √u + v′(x)(bx − u)]  (5)

has

v(x) = k√x (k > 0), u(x) = \frac{1}{k^{2}}

where k = \frac{1}{√1 + 2ρ − b − 1} . This yields

ẋ = −ax, x(0) = c.

where a = 2(1 + ρ − b − √1 + 2ρ − b). We have the optimal trajectory

x^{∗}(t) = ce^{−at}

and an optimal control

u^{∗}(x) = (a + b)x.

Case b = 1. Under the condition ρ ≥ 2, we have the prop’l policy u^{∗}(x) = (1 + 2ρ − 2√2ρ) x. It generates an optimal trajectory x^{∗}(t) = ce^{−at}, where a = 2(ρ − √2ρ).

• (i) When ρ = \frac{1}{2} (1 + √1 + log(1 + ϕ) )^{2} ≈ 2.882, the op-

timal trajectory x^{∗} is Golden x_{1}^{∗}(t) = ce^{−t log(1+ϕ)}. This is generated by a Gol. opt. pol. u_{1}^{∗}(x) = (1 + log(1 + ϕ)) x ≈ 1.962 x.

• (ii) When ρ = \frac{1}{2} (1 + √1 + log ϕ)^{2} ≈ 2.458, the optimal

trajectory x^{∗} is Golden x_{2}^{∗}(t) = ce^{−t log ϕ}. This is generated by a Gol. opt. pol. u_{2}^{∗}(x) = (1 + log ϕ) x ≈ 1.481 x.

Case b = 0. Under the condition ρ ≥ 0, we have the prop’l policy u^{∗}(x) = ax. It generates an optimal trajectory x^{∗}(t) = ce^{−at}, where a = (√1 + 2ρ − 1)^{2}.

• (i) When ρ = √log(1 + ϕ) + \frac{1}{2} log(1 + ϕ) ≈ 1.462, the

optimal trajectory x^{∗} is Golden x_{1}^{∗}(t) = ce^{−t log(1+ϕ)}. This is generated by a Golden optimal policy u_{1}^{∗}(x) = x log(1 + ϕ) ≈ 0.962 x.

• (ii) When ρ = √log ϕ + \frac{1}{2} log ϕ ≈ 0.934, the optimal

trajectory x^{∗} is Golden x_{2}^{∗}(t) = ce^{−t log ϕ}. This is generated by a Golden optimal policy u_{2}^{∗}(x) = x log ϕ ≈ 0.481 x.

Let’s solve the second allocation process : Maximize ∫_{0}^{∞}e^{−ρt}√u dt subject to (i) ẋ = bx − u

A′(c)  0 ≤ t < ∞
(ii) x ∈ C^{1}, u ≥ 0
(iii) x(0) = c.

Then BE

ρv(x) = Max_{u≥0} [√u + v′(x)(bx − u)]  (6)

has

v(x) = k√x (k > 0), u(x) = \frac{1}{k^{2}}

where k = \frac{1}{√2ρ − b} . This yields

ẋ = −ax, x(0) = c.

where a = 2(ρ − b). We have the optimal trajectory

x^{∗}(t) = ce^{−at}

and an optimal control

u^{∗}(x) = (b + a)x.

Two cases: A′(c) has a Golden optimal policy for b ≥ 0. Case (i) When ρ = b + log ϕ, the optimal trajectory x^{∗} is Golden x_{1}^{∗}(t) = ce^{−t log(1+ϕ)}. This is generated by a Golden u_{1}^{∗}(x) = (b + 2 log ϕ) x. Thus we have the Golden optimal policy u_{1}^{∗}. Case (ii) When ρ = b + \frac{1}{2} log ϕ, the optimal trajectory x^{∗} is Golden x_{2}^{∗}(t) = ce^{−t log ϕ}. This is generated by a Golden u_{2}^{∗}(x) = (b + log ϕ) x. Thus u_{2}^{∗} is Golden optimal.