.

. . . . . .

Explicit Dynamic Quadratic Programming

creating

Fibonacci number and Golden ratio

Seiichi IWAMOTO Yutaka KIMURA Masami YASUDA

Workshop on Games and MDP at WUT July, 2011

1 / 27

.. Contents

Abstract: We list several classes of Dynamic Programming, especially, Linear Quadratic Control problem. These are simple optimizations but interesting since they are related to famous subjects:

Division of numbers with quadratic criterion.

Golden optimal solution in quadratic programming. Matrix of threefold diagonal form with Fibonacci components. Multi-variate stopping with a monotone rule for three persons.

These are basically connected with Fibonacci Number and Golden Ratio, which means recurrence, iterative structure, duality and so on.

2 / 27

Abstract: We list several classes of Dynamic Programming, especially, Linear Quadratic Control problem. These are simple optimizations but interesting since they are related to famous subjects:

Division of numbers with quadratic criterion.

Golden optimal solution in quadratic programming. Matrix of threefold diagonal form with Fibonacci components. Multi-variate stopping with a monotone rule for three persons.

These are basically connected with Fibonacci Number and Golden Ratio, which means recurrence, iterative structure, duality and so on.

2 / 27

Abstract: We list several classes of Dynamic Programming, especially, Linear Quadratic Control problem. These are simple optimizations but interesting since they are related to famous subjects:

Division of numbers with quadratic criterion.

Golden optimal solution in quadratic programming. Matrix of threefold diagonal form with Fibonacci components. Multi-variate stopping with a monotone rule for three persons.

These are basically connected with Fibonacci Number and Golden Ratio, which means recurrence, iterative structure, duality and so on.

2 / 27

Abstract: We list several classes of Dynamic Programming, especially, Linear Quadratic Control problem. These are simple optimizations but interesting since they are related to famous subjects:

Division of numbers with quadratic criterion.

Golden optimal solution in quadratic programming. Matrix of threefold diagonal form with Fibonacci components. Multi-variate stopping with a monotone rule for three persons.

These are basically connected with Fibonacci Number and Golden Ratio, which means recurrence, iterative structure, duality and so on.

2 / 27

.. Rules and criterion

(1) Given c, divide it into two.

(2) By selection a x, one is x and the other is c − x .

(3) Criterion is the each of quadratics; x^{2} + (c − x)^{2}.

(4) Next is consider c − x and so divide it until the final stop.

(5) Aim is to minimize the total sum of division

3 / 27

.. Start number is ”5”

[figure: 5; 1; 4; 3; 1]

1^{2} + 4^{2} + 3^{2} + 1^{2} = 27(Try another!)

4 / 27

[figure: 5; 1; 4; 3; 1]

1^{2} + 4^{2} + 3^{2} + 1^{2} = 27(Try another!)

4 / 27

[figure: 5; 1; 4; 3; 1]

1^{2} + 4^{2} + 3^{2} + 1^{2} = 27(Try another!)

4 / 27

[figure: 5; 1; 4; 3; 1]

1^{2} + 4^{2} + 3^{2} + 1^{2} = 27(Try another!)

4 / 27

Optimal partition is

[figure: 5; 3; 2; 1; 1]

3^{2} + 2^{2} + 1^{2} + 1^{2} = 15(Optimal Partition!)

5 / 27

[figure: 5; 3; 2; 1; 1]

3^{2} + 2^{2} + 1^{2} + 1^{2} = 15(Optimal Partition!)

5 / 27

[figure: 5; 3; 2; 1; 1]

3^{2} + 2^{2} + 1^{2} + 1^{2} = 15(Optimal Partition!)

5 / 27

[figure: 5; 3; 2; 1; 1]

3^{2} + 2^{2} + 1^{2} + 1^{2} = 15(Optimal Partition!)

5 / 27

[figure: 13; 3; 10; 6; 4; 1; 3]

[figure: 13; 3; 10; 6; 4; 1; 3]

[figure: 13; 3; 10; 6; 4; 1; 3]

[figure: 13; 3; 10; 6; 4; 1; 3]

[figure: 13; 3; 10; 6; 4; 1; 3]

[figure: 13; 7; 6; 3; 3; 2; 1]

[figure: 13; 7; 6; 3; 3; 2; 1]

[figure: 13; 7; 6; 3; 3; 2; 1]

[figure: 13; 7; 6; 3; 3; 2; 1]

[figure: 13; 7; 6; 3; 3; 2; 1]

[figure: 13; 8; 5; 3; 2; 1; 1]

[figure: 13; 8; 5; 3; 2; 1; 1]

[figure: 13; 8; 5; 3; 2; 1; 1]

[figure: 13; 8; 5; 3; 2; 1; 1]

[figure: 13; 8; 5; 3; 2; 1; 1]

[figure: 13; 9; 4; 2; 2; 1; 1]

[figure: 13; 9; 4; 2; 2; 1; 1]

[figure: 13; 9; 4; 2; 2; 1; 1]

[figure: 13; 9; 4; 2; 2; 1; 1]

[figure: 13; 9; 4; 2; 2; 1; 1]

.. Change Sign

[figure: c; c − x_{1}; c + x_{1}; x_{1}; x_{1} − x_{2}; x_{1} + x_{2}; x_{2}; x_{2} − x_{3}; x_{2} + x_{3}; x_{3}]

minimize (c − x_{1})^{2} + x_{1}^{2} + (x_{1} − x_{2})^{2} + x_{2}^{2} + (x_{2} − x_{3})^{2} + x_{3}^{2}

subject to (x_{1}, x_{2}, x_{3}) ∈ R^{3} minimize (c + x_{1})^{2} + x_{1}^{2} + (x_{1} + x_{2})^{2} + x_{2}^{2} + (x_{2} + x_{3})^{2} + x_{3}^{2}

subject to (x_{1}, x_{2}, x_{3}) ∈ R^{3}

10 / 27

.. Change Sign

[figure: c; c − x_{1}; c + x_{1}; x_{1}; x_{1} − x_{2}; x_{1} + x_{2}; x_{2}; x_{2} − x_{3}; x_{2} + x_{3}; x_{3}]

minimize (c − x_{1})^{2} + x_{1}^{2} + (x_{1} − x_{2})^{2} + x_{2}^{2} + (x_{2} − x_{3})^{2} + x_{3}^{2}

subject to (x_{1}, x_{2}, x_{3}) ∈ R^{3} minimize (c + x_{1})^{2} + x_{1}^{2} + (x_{1} + x_{2})^{2} + x_{2}^{2} + (x_{2} + x_{3})^{2} + x_{3}^{2}

subject to (x_{1}, x_{2}, x_{3}) ∈ R^{3}

10 / 27

.. Alternative sign Positive/Negative

Optimal partition:

[figure: 5; 3; −2; −1; 1; c; x_{1}; x_{2}; (c + x_{1}); (x_{1} + x_{2})]

3^{2} + (−2)^{2} + (−1)^{2} + 1^{2} = 15Optimal

11 / 27

Optimal partition:

[figure: 5; 3; −2; −1; 1; c; x_{1}; x_{2}; (c + x_{1}); (x_{1} + x_{2})]

3^{2} + (−2)^{2} + (−1)^{2} + 1^{2} = 15Optimal

11 / 27

Optimal partition:

[figure: 5; 3; −2; −1; 1; c; x_{1}; x_{2}; (c + x_{1}); (x_{1} + x_{2})]

3^{2} + (−2)^{2} + (−1)^{2} + 1^{2} = 15Optimal

11 / 27

Optimal partition:

[figure: 5; 3; −2; −1; 1; c; x_{1}; x_{2}; (c + x_{1}); (x_{1} + x_{2})]

3^{2} + (−2)^{2} + (−1)^{2} + 1^{2} = 15Optimal

11 / 27

.. Three steps

[figure: 13; 8; −5; −3; 2; 1; −1; c; x_{1}; x_{2}; x_{3}; (c + x_{1}); (x_{1} + x_{2}); (x_{2} + x_{3})]

[figure: 13; 8; −5; −3; 2; 1; −1; c; x_{1}; x_{2}; x_{3}; (c + x_{1}); (x_{1} + x_{2}); (x_{2} + x_{3})]

[figure: 13; 8; −5; −3; 2; 1; −1; c; x_{1}; x_{2}; x_{3}; (c + x_{1}); (x_{1} + x_{2}); (x_{2} + x_{3})]

[figure: 13; 8; −5; −3; 2; 1; −1; c; x_{1}; x_{2}; x_{3}; (c + x_{1}); (x_{1} + x_{2}); (x_{2} + x_{3})]

[figure: 13; 8; −5; −3; 2; 1; −1; c; x_{1}; x_{2}; x_{3}; (c + x_{1}); (x_{1} + x_{2}); (x_{2} + x_{3})]

.. Lucas Formula
.（Lucas formula）

..

. . . . . .  ^{∑_{k=1}^{n} F_{k}^{2} = F_{n}F_{n+1}}
n 0 1 2 3 4 5 6 7 8 9 10 11 12
F_{n} 0 1 1 2 3 5 8 13 21 34 55 89 144

Table 1: Fibonacci sequence {F_{n}}

For exapmle, n = 5

F_{1}^{2} + F_{2}^{2} + F_{3}^{2} + F_{4}^{2} + F_{5}^{2}
= 1^{2} + 1^{2} + 2^{2} + 3^{2} + 5^{2}
= 40
= F_{5}F_{6}

13 / 27

.. Lucas Formula
.（Lucas formula）

..

. . . . . .  ^{∑_{k=1}^{n} F_{k}^{2} = F_{n}F_{n+1}}
n 0 1 2 3 4 5 6 7 8 9 10 11 12
F_{n} 0 1 1 2 3 5 8 13 21 34 55 89 144

Table 1: Fibonacci sequence {F_{n}}

For exapmle, n = 5

F_{1}^{2} + F_{2}^{2} + F_{3}^{2} + F_{4}^{2} + F_{5}^{2}
= 1^{2} + 1^{2} + 2^{2} + 3^{2} + 5^{2}
= 40
= F_{5}F_{6}

13 / 27

Optimal value V9 of Number division problem is given by

V9 = [(F_{9} − F_{7})^{2} + (−F_{7})^{2}]+ [(−F_{7} + F_{5})^{2} + F_{5}^{2}]

+ [(F_{5} − F_{3})^{2} + (−F_{3})^{2}]+ [(−F_{3} + F_{1})^{2} + F_{1}^{2}]

Clearly this leads to

= F_{8}^{2} + F_{7}^{2} + F_{6}^{2} + F_{5}^{2} + F_{4}^{2} + F_{3}^{2} + F_{2}^{2} + F_{1}^{2}
= F_{8} · F_{9} = 104

by Lucas formula.

14 / 27

Optimal value V9 of Number division problem is given by

V9 = [(F_{9} − F_{7})^{2} + (−F_{7})^{2}]+ [(−F_{7} + F_{5})^{2} + F_{5}^{2}]

+ [(F_{5} − F_{3})^{2} + (−F_{3})^{2}]+ [(−F_{3} + F_{1})^{2} + F_{1}^{2}]

Clearly this leads to

= F_{8}^{2} + F_{7}^{2} + F_{6}^{2} + F_{5}^{2} + F_{4}^{2} + F_{3}^{2} + F_{2}^{2} + F_{1}^{2}
= F_{8} · F_{9} = 104

by Lucas formula.

14 / 27

.. Quasi-cubic sum

. Lemma （quasi-cubic sum） .. . . . . . .

For {F_{k}}, we have

2 ∑_{k=1}^{n} F_{k}^{2}F_{k+1} = F_{n}F_{n+1}F_{n+2}.
n 0 1 2 3 4 5 6 7 8 9 10 11 12
F_{n} 0 1 1 2 3 5 8 13 21 34 55 89 144

Table 1: Fibonacci sequence {F_{n}}

This relates with a tiling problem in a plan or a space by using the unit of fibonacci square or cubes.

15 / 27

.. Quasi-cubic sum

. Lemma （quasi-cubic sum） .. . . . . . .

For {F_{k}}, we have

2 ∑_{k=1}^{n} F_{k}^{2}F_{k+1} = F_{n}F_{n+1}F_{n+2}.
n 0 1 2 3 4 5 6 7 8 9 10 11 12
F_{n} 0 1 1 2 3 5 8 13 21 34 55 89 144

Table 1: Fibonacci sequence {F_{n}}

This relates with a tiling problem in a plan or a space by using the unit of fibonacci square or cubes.

15 / 27

.. References I

S. Iwamoto, The Golden optimum solution in quadratic programming, Nonlinear Analysis and Convex Analysis (NACA05), Yokohama, 2007, pp. 199–205.

S. Iwamoto and Y. Kimura, The Alternately Fibonacci Complementary Duality in Quadratic Optimization Problem, Journal of Nonlinear Analysis and Optimization, Vol.2, No.1, 2011, pp.93–103.

S. Iwamoto and M. Yasuda, Golden optimal path in discrete-time dynamic optimization processes, Advanced Studies in Pure Mathematics 53, June 2009, pp.77–86.

16 / 27

.. Matrix form for recurrsiveness

Object function

I_{3}(x) = ∑_{i=0}^{3}{x_{i}^{2} + (x_{i} − x_{i+1})^{2}}

is a quadratic of x = (x_{0}, x_{1}, x_{2}, x_{3}), x_{0} = c:

I_{3}(x) = (x, Bx) + 2(b, x) + c^{2}
b = (c, 0, 0, 0)^{T}

provided starting number equals c. Expanding it, 4×4 matrix

B = ( \begin{matrix}3 & 1 & 0 & 0 \\ 1 & 3 & 1 & 0 \\ 0 & 1 & 3 & 1 \\ 0 & 0 & 1 & 2 \end{matrix} )

becomes a posive definite and threefold diagonal form.

17 / 27

Its inverse is

B^{−1} = \frac{1}{34} ( \begin{matrix}13 & −5 & 2 & −1 \\ −5 & 15 & −6 & 3 \\ 2 & −6 & 16 & −8 \\ −1 & 3 & −8 & 21 \end{matrix} ) ,

x̂ = −B^{−1}b = −B^{−1} ( \begin{matrix}c \\ 0 \\ 0 \\ 0 \end{matrix} ) = \frac{c}{34} ( \begin{matrix}−13 \\ 5 \\ −2 \\ 1 \end{matrix} ) .

Note that each element is one of the ”fibonacci” numbers.

18 / 27

That is,

x̂ = \frac{c}{34} ( \begin{matrix}−13 \\ 5 \\ −2 \\ 1 \end{matrix} ) = \frac{c}{F_{9}} ( \begin{matrix}−F_{7} \\ F_{5} \\ −F_{3} \\ F_{1} \end{matrix} ) .

The minimum value m_{4} is given by

m_{4} = c^{2} − (b, B^{−1}b)
= c^{2} − \frac{13}{34} c^{2} = \frac{21}{34} c^{2}
= \frac{F_{8}}{F_{9}} c^{2}.

When we starting with c = F_{9}, these becomes simple ones.

19 / 27

Its inverse equals

C^{−1} = \frac{1}{34} ( \begin{matrix}21 & −8 & 3 & −1 \\ −8 & 16 & −6 & 2 \\ 3 & −6 & 15 & −5 \\ −1 & 2 & −5 & 13 \end{matrix} )

Thus

μ^{∗} = C^{−1}b = \frac{c}{34} ( \begin{matrix}21 \\ −8 \\ 3 \\ −1 \end{matrix} ) = \frac{c}{F_{9}} ( \begin{matrix}F_{8} \\ −F_{6} \\ F_{4} \\ −F_{2} \end{matrix} )

the maximum value is

M_{4} = (b, C^{−1}b) = \frac{21}{34} c^{2} = \frac{F_{8}}{F_{9}} c^{2}

20 / 27

.. Notes

These are easyly extended in n × n form. The symmetric matrix A_{n} of the objective:

I_{n}(x) = ∑_{i=0}^{n}{x_{i}^{2} + (x_{i} − x_{i+1})^{2}}

is a quadratic of x = (x_{0}, x_{1}, x_{2}, ⋯, x_{n+1}), x_{0} = c:

.Theorem ..

. . . . . .

The determinant satisfies that

… 1

|A_{n}| − 3|A_{n−1}| + |A_{n−2}| = 0, |A_{1}| = 1, |A_{2}| = 2

… 2

|A_{n}| = F_{2n−1}(2n − 1-th fibonacci number)

Details are omitted.

21 / 27

.. Notes

Refer to S.Iwamoto, A.Kira and M.Yasuda; ” Golden Duality in Dynamic Optimization ”, Proceeding of Kosen Workshop, MTE2008, 2008, 1-13.

22 / 27

.. MDP model

MDP (S, A, P, R): S; {x_{n}} ∈ R^{1}, A; {u_{n}} ∈ R^{1}, P : x_{n+1} = x_{n} + u_{n}, x_{0} = c, R :

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

with a given initial state x_{0} = c. This section minimizes two quadratic cost functions.

23 / 27

.. MDP

Both problems are solved as a control process with criterion:

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

24 / 27

.. MDP model

Let v(c) be the minimum value with initial value c. Then the value function v = v(x) satisfies Bellman equation:

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

This has a quadratic form v(x). A quadratic minimum value function v(x) = ϕx^{2}, where

ϕ = \frac{1 + \sqrt{5}}{2} , u = − \frac{ϕ}{1 + ϕ} x.

Since

min_{0≤a≤x}\{Aa^{2} + B(x − a)^{2}\} = \frac{x^{2}}{1/A + 1/B}

hold, so the continued fraction leads to Golden number.

25 / 27

.. monotone rule

A value function v(x) of the multivariate optimal stopping where three persons and the rule is as

ϕ(x_{1}, x_{2}, x_{3}) = x_{1} · x_{2} + x_{3}

of the logical operation. Then the first and second player’s gain for uniform distribution [0, 1] is the Golden number since it is by solving x^{2} = x + 1 and the third is 1.

26 / 27

.. monotone rule

Refer to S.Iwamoto , Masami Yasuda; ” Dynamic programming creates the Golden ratio, too ”, Kyoto RIMS Kokyuroku 1477, 2006, pp.136-140. M.Kurano, M.Yasuda and J.Nakagami; ”Multi-variate stopping problems with a monotone rule”, J Oper Res Soc Japan, Vol.25, pp.334-350(1982) .

27 / 27