PROCEEDINGS OF KOSEN WORKSHOP MTE2008

– MATHEMATICS, TECHNOLOGY AND EDUCATION –

IBARAKI NATIONAL COLLEGE OF TECHNOLOGY

HITACHINAKA, IBARAKI, JAPAN February 15-18, 2008

GOLDEN DUALITY IN DYNAMIC OPTIMIZATION

SEIICHI IWAMOTO, AKIFUMI KIRA

Department of Economic Engineering, Graduate School of Economics, Kyushu University

Hakozaki 6-19-1, Higashi-ku, Fukuoka 812-8581, Japan E-mail: iwamoto@en.kyushu-u.ac.jp, ec207004@s.kyushu-u.ac.jp

MASAMI YASUDA Department of Mathematics and Informatics, Faculty of Science, Chiba University Yayoi-cho 1-33, Inage-ku, Chiba 263-8522, Japan E-mail: yasuda@math.s.chiba-u.ac.jp

Abstract. This paper discusses the dual of infinite-variable quadratic minimization (primal) problems from a view point of Golden ratio. We consider two pairs of primal and dual (maximization) problems. One pair yields the Golden duality. While the minimum value function is Golden quadratic and the minimum point constitutes a Golden path, so is the maximum value function and the maximum point does such another. The other yields the inverse-Golden duality. While the minimum value function is inverse-Golden quadratic and the minimum point constitutes the same Golden path, so is the maximum value function and the maximum point does the same such another.

1. Introduction

The Golden ratio is one of the most beautiful numbers. The desire for optimality is inherent for humans. One minimization leads to the other maximization, which arrives at a duality. We direct our attention to both the Golden ratio and the duality. A duality of fine features is shown.

In this paper, we are concerned with dynamic optimization problems of infinitely many variables from a viewpoint of Golden duality. We take two typical quadratic minimization (primal) problems with initial condition and associate each problem with a quadratic maximization (dual) problem with transversality condition. The two pairs of primal and

2000 Mathematics Subject Classification: Primary 90C39; Secondary 49L20.

Key words and phrases: Golden ratio, dual, dynamic optimization, dynamic programming, Lagrange multiplier.

This research is supported by the Grants in Aid for Scientific Research (B) No. 17340030 in the Japan Society for the Promotion of Sciences.

dual problems have interesting characteristics. As for the first pair, the minimum value function is Golden quadratic and the minimum point constitutes a Golden path, while so is the maximum value function and the maximum point does such another. As for the second, the minimum value function is inverse-Golden quadratic and the minimum point constitutes the same Golden path, while so is the maximum value function and the maximum point does the same such another.

2. Duality

A real number

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

is called Golden number [3, 4, 17]. It is the larger of the two solutions to quadratic equation (QE)

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

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

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

Further we have

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

A quadratic function v(x) = ax^{2} is called Golden (resp. inverse-Golden) if a = ϕ (resp. ϕ^{−1}). In this section, we consider two pairs of primal and dual problems. One pair yields a duality for the Golden quadratic function. The other pair yields a duality for the inverse-Golden quadratic function.

2.1. Golden duality

We take an interval [0, x], where x > 0. Let us consider the set of all divisions of the interval [0, x]. Each division is specified by an inner point y ∈ [0, x], which splits the interval [0, x] into two intervals [0, y] and [y, x]. A point (2 − ϕ)x splits the interval into two intervals [0, (2 − ϕ)x] and [(2 − ϕ)x, x]. A point (ϕ − 1)x splits it 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 [3, 4, 17].

Definition 1. [14] A sequence x : {0, 1, … } → R^{1} is called Golden path if and only if either

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

Lemma 1. [14] A Golden path 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 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 R^{∞} be the set of all sequences of real values :

R^{∞} = {x = (x_{0}, x_{1}, …, x_{n}, …) | x_{n} ∈ R^{1} n = 0, 1, … }.

We consider a primal problem^{1} on R^{∞} :

minimize ∑_{n=0}^{∞} [x_{n}^{2} + (x_{n} − x_{n+1})^{2}]
(P_{1}) subject to (i) x ∈ R^{∞}
(ii) x_{0} = c

where c ∈ R^{1}. A dual problem is a maximization problem of λ = (λ_{0}, λ_{1}, …, λ_{n}, …) ∈ R^{∞}:

Maximize c^{2} + cλ_{0} − \frac{1}{4} ∑_{n=0}^{∞} [λ_{n}^{2} + (λ_{n} − λ_{n+1})^{2}]

(D_{1}) subject to (i) λ ∈ R^{∞}

(ii) lim_{n→∞} λ_{n} = 0.

We note that both problems contain a common series ∑_{n=0}^{∞} [y_{n}^{2} + (y_{n} − y_{n+1})^{2}]. In either

problem, we are concerned with the finite convergence case : ∑_{n=0}^{∞} [y_{n}^{2} + (y_{n} − y_{n+1})^{2}] <

∞. This implies that lim_{n→∞} y_{n} = 0. In Section 3, we will see that the additional transversality condition (ii) enables us to make dual of (P_{1}) without difficulty. Therefore, the transversality condition may be removed from the constraints.

Theorem 1. (Golden duality) (i) The primal problem (P_{1}) has the minimum value m = ϕc^{2} at the point

x̂ = c (1, (2 − ϕ), …, (2 − ϕ)^{n}, …) .

(ii) The dual problem (D_{1}) has the maximum value M = ϕc^{2} at the point

λ^{∗} = 2ϕ^{−1}c (1, (2 − ϕ), …, (2 − ϕ)^{n}, …) .

We make an observation about the two optimal solutions. Both the minimum point and the maximum point constitute a Golden path and both the minimum value function and the maximum value function are the identical Golden quadratic value function. What

1 As for corresponding finite variable problems see [8], and as for their dual and others see [5, 6, 7, 8, 15].

a beautiful duality this is! Thus, the duality is called Golden duality. The proof will be given throughout the discussion in Section 3.

We see that the minimum solution of (P_{1}) yields the maximum solution of (D_{1}). Let (P_{1}) have the minimum value m = ϕc^{2} at the minimum point x̂. Then we have

Max [c^{2} + cλ_{0} − \frac{1}{4} ∑_{n=0}^{∞} [λ_{n}^{2} + (λ_{n} − λ_{n+1})^{2}]]

= Max_{λ_{0}} [c^{2} + cλ_{0} − \frac{1}{4} min_{\{λ_{n}\}_{n≥1}} ∑_{n=0}^{∞} [λ_{n}^{2} + (λ_{n} − λ_{n+1})^{2}]]

= Max_{λ_{0}} [c^{2} + cλ_{0} − \frac{1}{4} ϕλ_{0}^{2}]
= ϕc^{2} for λ_{0} = 2ϕ^{−1}c

where the minimum is attained at

(λ̂_{1}, λ̂_{2}, …, λ̂_{n}, …) = λ_{0} (2 − ϕ, (2 − ϕ)^{2}, …, (2 − ϕ)^{n}, …) .

Theorem 2. The functional equation

f(c) = Max_{λ∈R^{1}} [c^{2} + cλ − \frac{1}{4} f(λ)] c ∈ R^{1}

has the Golden quadratic maximum value function f(c) = ϕc^{2} for maximum point function λ̂(c) = 2ϕ^{−1}c. This is a unique continuous function.

Proof. It is easily verified that f with λ̂ satisfies the functional equation. The uniqueness is shown through the well known method in dynamic programming [1, Ch.4], because of

|−\frac{1}{4}| < 1 (see also [18]). ■

Corollary 3. The functional equation

f(c) = Max_{λ∈R^{1}} [cλ + \frac{1}{4} λ^{2} − \frac{1}{4} f(λ)] c ∈ R^{1}

has the Golden quadratic maximum value function f(c) = ϕc^{2} for maximum point function λ̆(c) = 2ϕc. This is a unique continuous function.

Corollary 4. The functional equation

\frac{1}{4} f(c) = Max_{λ∈R^{1}} [λ^{2} + cλ − f(λ)] c ∈ R^{1}

has the Golden quadratic maximum value function f(c) = ϕc^{2} for maximum point func-

tion λ̃(c) = \frac{ϕ}{2} c.

2.2. Inverse-Golden duality

Second we consider a primal problem

minimize ∑_{n=0}^{∞} [(x_{n} − x_{n+1})^{2} + x_{n+1}^{2}]
(P_{2}) subject to (i) x ∈ R^{∞}
(ii) x_{0} = c

and a dual problem

Maximize cλ_{0} − \frac{1}{4} ∑_{n=0}^{∞} [λ_{n}^{2} + (λ_{n} − λ_{n+1})^{2}]

(D_{2}) subject to (i) λ ∈ R^{∞}

(ii) lim_{n→∞} λ_{n} = 0

where c ∈ R^{1}. We note that a difference between (P_{1}) and (P_{2}) is constant :

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

The difference x_{0}^{2} = c^{2} is also preserved between (D_{1}) and (D_{2}). This enables us to obtain a duality in terms of inverse-Golden number ϕ^{−1} = ϕ − 1 as follows.

Theorem 5. (Inverse-Golden duality) (i) The primal problem (P_{2}) has the minimum value m = ϕ^{−1}c^{2} at the point

x̂ = c (1, (2 − ϕ), …, (2 − ϕ)^{n}, …) .

(ii) The dual problem (D_{2}) has the maximum value M = ϕ^{−1}c^{2} at the point

λ^{∗} = 2ϕ^{−1}c (1, (2 − ϕ), …, (2 − ϕ)^{n}, …) .

We remark that both optimal points constitute a Golden path and that both optimal value functions are the same — the inverse-Golden quadratic value function —. This is a Golden duality, too. The Golden paths x̂ and λ^{∗} are the same ones in (P_{1}) and (D_{1}), respectively.

Further the minimum solution of (P_{2}) yields the maximum solution of (D_{2}). Let (P_{2}) have the minimum value m = ϕ^{−1}c^{2} at the minimum point x̂. Then we have

Max [cλ_{0} − \frac{1}{4} ∑_{n=0}^{∞} [λ_{n}^{2} + (λ_{n} − λ_{n+1})^{2}]]

= Max_{λ_{0}} [cλ_{0} − \frac{1}{4} λ_{0}^{2} − \frac{1}{4} min_{\{λ_{n}\}_{n≥1}} ∑_{n=0}^{∞} [(λ_{n} − λ_{n+1})^{2} + λ_{n+1}^{2}]]

= Max_{λ_{0}} [cλ_{0} − \frac{1}{4} λ_{0}^{2} − \frac{1}{4} ϕ^{−1}λ_{0}^{2}]
= ϕ^{−1}c^{2} for λ_{0} = 2ϕ^{−1}c

where the minimum is attained at

(λ̂_{1}, λ̂_{2}, …, λ̂_{n}, …) = λ_{0} (2 − ϕ, (2 − ϕ)^{2}, …, (2 − ϕ)^{n}, …) .

Theorem 6. The functional equation

g(c) = Max_{λ∈R^{1}} [cλ − \frac{1}{4} λ^{2} − \frac{1}{4} g(λ)] c ∈ R^{1}

has the inverse-Golden quadratic maximum value function g(c) = ϕ^{−1}c^{2} for maximum point function λ̆(c) = 2ϕ^{−1}c. This is a unique continuous function.

Corollary 7. The functional equation

g(c) = Max_{λ∈R^{1}} [−c^{2} + cλ − \frac{1}{4} g(λ)] c ∈ R^{1}

has the inverse-Golden quadratic maximum value function g(c) = ϕ^{−1}c^{2} for maximum point function λ̂(c) = 2ϕc. This is a unique continuous function.

Corollary 8. The functional equation

\frac{1}{4} g(c) = Max_{λ∈R^{1}} [−cλ − λ^{2} − g(λ)] c ∈ R^{1}

has the inverse-Golden quadratic maximum value function g(c) = ϕ^{−1}c^{2} for maximum

point function λ̃(c) = \frac{ϕ}{2} c.

3. Lagrangean Method

In this section we show how the Lagrangean method derives a maximization (dual) problem from the minimization (primal) problem.

Let us reconsider the primal problem

minimize ∑_{n=0}^{∞} [x_{n}^{2} + (x_{n} − x_{n+1})^{2}]
(P_{1}) subject to (i) x ∈ R^{∞}
(ii) x_{0} = c.

We introduce a sequence of variables u = {u_{0}, u_{1}, …, u_{n}, … } by

u_{k} = x_{k+1} − x_{k}.

Then (P_{1}) is formulated into a quadratic minimization under a linear constraint

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

Let us now solve this problem through a Lagrangean multiplier’s method. We introduce a sequence of variables λ = {λ_{0}, λ_{1}, …, λ_{n}, … } with the property lim_{n→∞} λ_{n} = 0, which is called a Lagrange multiplier. Let us construct the Lagrangean

L(x, u, λ) = ∑_{n=0}^{∞} [x_{n}^{2} + u_{n}^{2} − λ_{n}(x_{n+1} − x_{n} − u_{n})] .

Then it has the partial derivatives

L_{x_{n}} = 2x_{n} + λ_{n} − λ_{n−1}  n ≥ 1
L_{u_{n}} = 2u_{n} + λ_{n}  n ≥ 0
L_{λ_{n}} = x_{n+1} − x_{n} − u_{n}  n ≥ 0.

Here we notice that the Lagrangean is not one for a regular (a finite n variables with a finite m constraints) extremal problem. The problem has a countably infinte variables under a countably infinite linear constraints.

Lemma 2. Let (x, u) be an extremum point. Then there exists a λ satisfying the condition that all the partial derivatives at point (x, u, λ) vanish:

(2)  L_{x_{n}} = 0 n ≥ 1, L_{u_{n}} = L_{λ_{n}} = 0 n ≥ 0.

Proof. Let x̂ = (x̂_{n})_{n≥0}, û = (û_{n})_{n≥0} be an extremum point for (P′_{1}). We take any large positive integer N and consider a finite-truncated conditional minimization problem of x = (x_{n})_{0}^{N}, u = (u_{n})_{0}^{N} :

minimize ∑_{n=0}^{N} (x_{n}^{2} + u_{n}^{2})
(T_{N}) subject to (i) x_{n+1} = x_{n} + u_{n} 0 ≤ n ≤ N − 1
(ii) x̂_{N+1} = x_{N} + u_{N}
(iii) x_{0} = c.

This has (2N + 1) variables x_{1}, …, x_{N}, u_{0}, …, u_{N} and (N + 1) linear constraints. Let us construct the Lagrangean L^{N} by

L^{N}(x, u, λ) = ∑_{n=0}^{N−1} [x_{n}^{2} + u_{n}^{2} − λ_{n}(x_{n+1} − x_{n} − u_{n})]
+ x_{N}^{2} + u_{N}^{2} − λ_{N}(x̂_{N+1} − x_{N} − u_{N}) for λ = (λ_{n})_{0}^{N}.

Then the point (x̂_{n})_{1}^{N}, (û_{n})_{0}^{N} is also an extremum point for the truncated problem. It satisfies the linear independent constraint qualification [16]. Therefore, Lagrange Multiplier Theorem (for a regular problem) implies that there exists a (λ_{n}^{∗})_{0}^{N} such that (x̂_{n})_{1}^{N}, (û_{n})_{0}^{N}; (λ_{n}^{∗})_{0}^{N} satisfies

L_{x_{n}}^{N} = 0 1 ≤ n ≤ N, L_{u_{n}}^{N} = L_{λ_{n}}^{N} = 0 0 ≤ n ≤ N.

Thus we have

2x̂_{n} + λ_{n}^{∗} − λ_{n−1}^{∗} = 0 1 ≤ n ≤ N
2x̂_{n} + λ_{n}^{∗} = 0 0 ≤ n ≤ N
x̂_{n+1} − x̂_{n} − û_{n} = 0 0 ≤ n ≤ N.

Since N is arbitrarily large, we conclude that there exists a (λ_{n}^{∗})_{n≥0} such that (x̂_{n})_{n≥1}, (û_{n})_{n≥0} ; (λ_{n}^{∗})_{n≥0} satisfies (2). This completes the proof. ■

Then (2) is equivalent to

2x_{n} = −(λ_{n} − λ_{n−1}) n ≥ 1
2u_{n} = −λ_{n} n ≥ 0
u_{n} = x_{n+1} − x_{n} n ≥ 0.

Now we solve this equivalent system in the following. Deleting u and λ, we get a system of linear equations:

x_{0} = c

(3)

x_{n−1} − 3x_{n} + x_{n+1} = 0 n ≥ 1.

Thus we have

u_{n} = x_{n+1} − x_{n}

(4)

λ_{k} = −2(x_{n+1} − x_{n}).

We see that Eq.(3) has the solution^{2}

x_{n} = c(2 − ϕ)^{n} n ≥ 0. (5)

where ϕ is the Golden number (ratio). Thus we have

u_{n} = − \frac{c}{ϕ} (2 − ϕ)^{n}

(6)

λ_{n} = \frac{2c}{ϕ} (2 − ϕ)^{n}.

Lemma 3. The solution (x, u) in (5),(6) is a minimum point for (P′_{1}). Hence, x is a minimum point for (P_{1}).

2 A general solution of (3) is x_{n} = A(2 − ϕ)^{n} + B(1 + ϕ)^{n}, where A + B = c. The case A = c, B = 0 attains a minimum value for (P_{1}).

10  S. IWAMOTO, A. KIRA AND M. YASUDA

Proof. We show that the (x, u) is a minimum point. Let (X, U) be any solution satisfying

X_{n+1} = X_{n} + U_{n} n ≥ 0
X_{0} = c.

Here we take the λ in (6). First we see that for any n-stage process

∑_{k=0}^{n} (x_{k}^{2} + u_{k}^{2}) = ∑_{k=0}^{n} [x_{k}^{2} + u_{k}^{2} − λ_{k}(x_{k+1} − x_{k} − u_{k})]
= c^{2} + cλ_{0} − λ_{0}x_{1} + ∑_{k=1}^{n−1} [x_{k}^{2} − λ_{n}(x_{k+1} − x_{k})] + x_{n}^{2} + λ_{n}x_{n}

+ ∑_{k=0}^{n} (u_{k}^{2} + λ_{k}u_{k}) − λ_{n}x_{n+1}

= c^{2} + cλ_{0} + ∑_{k=1}^{n} [x_{k}^{2} + (λ_{k} − λ_{k−1})x_{k}] + ∑_{k=0}^{n} (u_{k}^{2} + λ_{k}u_{k}) − λ_{n}x_{n+1}
= c^{2} + cλ_{0} − \frac{1}{4} ∑_{k=1}^{n} (λ_{k} − λ_{k−1})^{2} − \frac{1}{4} ∑_{k=0}^{n} λ_{k}^{2} − λ_{n}x_{n+1}

+ ∑_{k=1}^{n} [x_{k} + \frac{1}{2}(λ_{k} − λ_{k−1})]^{2} + ∑_{k=0}^{n} (u_{k} + \frac{1}{2}λ_{k})^{2} . (7)

We may consider the set of all feasible x satisfying lim_{n→∞} λ_{n}x_{n+1} = 0 in (P_{1}), because of the quadratic minimization and lim_{n→∞} λ_{n} = 0. This set in turn includes the set of all feasible x satisfying lim_{n→∞} x_{n} = 0. Thus letting n → ∞ in (7), we have

∑_{n=0}^{∞} (x_{n}^{2} + u_{n}^{2}) = c^{2} + cλ_{0} − \frac{1}{4} ∑_{n=0}^{∞} [λ_{n}^{2} + (λ_{n} − λ_{n+1})^{2}]

+ ∑_{n=1}^{∞} [x_{n} + \frac{1}{2}(λ_{n} − λ_{n−1})]^{2} + ∑_{n=0}^{∞} (u_{n} + \frac{1}{2}λ_{n})^{2} . (8)

Similarly, we have for (X, U)

∑_{n=0}^{∞} (X_{n}^{2} + U_{n}^{2}) = c^{2} + cλ_{0} − \frac{1}{4} ∑_{n=0}^{∞} [λ_{n}^{2} + (λ_{n} − λ_{n+1})^{2}]

+ ∑_{n=1}^{∞} [X_{n} + \frac{1}{2}(λ_{n} − λ_{n−1})]^{2} + ∑_{n=0}^{∞} (U_{n} + \frac{1}{2}λ_{n})^{2} . (9)

Since (x, u) satisfies

x_{n} + \frac{1}{2}(λ_{n} − λ_{n−1}) = 0, u_{n} + \frac{1}{2}λ_{n} = 0, lim_{n→∞} λ_{n} = 0

a comparison between (8) and (9) yields

∑_{n=0}^{∞} (x_{n}^{2} + u_{n}^{2}) ≤ ∑_{n=0}^{∞} (X_{n}^{2} + U_{n}^{2}) .

GOLDEN DUALITY  11

This completes the proof. ■

From (9) we have a basic inequality as follows.

Lemma 4. It holds that

∑_{n=0}^{∞} (x_{n}^{2} + u_{n}^{2}) = c^{2} + cλ_{0} − \frac{1}{4} ∑_{n=0}^{∞} [λ_{n}^{2} + (λ_{n} − λ_{n+1})^{2}]

+ ∑_{n=1}^{∞} [x_{n} + \frac{1}{2}(λ_{n} − λ_{n−1})]^{2} + ∑_{n=0}^{∞} (u_{n} + \frac{1}{2}λ_{n})^{2} (10)

≥ c^{2} + cλ_{0} − \frac{1}{4} ∑_{n=0}^{∞} [λ_{n}^{2} + (λ_{n} − λ_{n+1})^{2}]

for any (x, u) satisfying (i), (ii) and any λ satisfying lim_{n→∞} λ_{n} = 0. The equality holds if and only if

2x_{n} = −(λ_{n} − λ_{n−1}) n ≥ 1 and 2u_{n} = −λ_{n} n ≥ 0.

This lemma states that L(x̂, û : λ) ≤ L(x̂, û : λ^{∗}) ≤ L(x, u : λ^{∗}) (11) where

L(x, u : λ) = ∑_{n=0}^{∞} [x_{n}^{2} + u_{n}^{2} − λ_{n}(x_{n+1} − x_{n} − u_{n})]

and

x̂_{n} = c(2 − ϕ)^{n}
û_{n} = − \frac{c}{ϕ} (2 − ϕ)^{n} n ≥ 0
λ_{n}^{∗} = \frac{2c}{ϕ} (2 − ϕ)^{n}.

In fact, we have the equality between left-hand side and middle side:

L(x̂, û : λ) = L(x̂, û : λ^{∗}) ∀λ ; lim_{n→∞} λ_{n} = 0.

Hence we have a maximization problem for λ = (λ_{0}, λ_{1}, …, λ_{n}, …) as follows:

Maximize c^{2} + cλ_{0} − \frac{1}{4} ∑_{n=0}^{∞} [λ_{n}^{2} + (λ_{n} − λ_{n+1})^{2}]

(D_{1}) subject to (i) λ ∈ R^{∞}

(ii) lim_{n→∞} λ_{n} = 0.

Thus we have derived the desired dual problem together with the optimum solution.

Lemma 5. The point λ^{∗} with λ_{n}^{∗} = \frac{2c}{ϕ} (2 − ϕ)^{n} is a maximum point for (D_{1}). It yields the maximum value M = ϕc^{2}.

4. Dynamic Programming

This section discusses a dynamic programming aspect of the two primal problems [1, 2, 8, 10]. It is shown that both optimal value function and optimum point function are Golden. The optimal value function is Golden quadratic. The optimum point yields what we call Golden section.

Let f(c) be the minimum value of (P_{1}) for c ∈ R^{1}. Then we have the following results. Theorem 9. The minimum value function f satisfies the Bellman equation

\begin{cases}f(0) = 0 \\ f(c) = min_{x∈R^{1}} [c^{2} + (c − x)^{2} + f(x)] . \end{cases}

This has the Golden quadratic minimum value function f(c) = ϕc^{2} for a minimum point function x̂(c) = ϕ^{−2}c.

Let g(c) be the minimum value of (P_{2}) for c ∈ R^{1}. Then we have the following results. Theorem 10. The minimum value function g satisfies the Bellman equation

\begin{cases}g(0) = 0 \\ g(c) = min_{x∈R^{1}} [(c − x)^{2} + x^{2} + g(x)] . \end{cases}

This has the inverse-Golden quadratic minimum value function g(c) = ϕ^{−1}c^{2} for a minimum point function x̂(c) = ϕ^{−2}c.

We remark that the minimum point function x̂(c) = ϕ^{−2}c is called a Golden decision function. Because it divides an interval [0, c] into [0, x̂(c)] = [0, (2 − ϕ)c] and [x̂(c), c] = [(2 − ϕ)c, c], which is the so-called Golden section. Thus x̂ is Golden (and) optimal. The Golden (Golden optimal) decision function leads to the Golden (Golden optimal) policy in dynamic programming. Recently the Golden optimal policy for dynamic optimization problems has been discussed in [9, 11, 12, 14]. It has a strong connection with duality, as we have shown in this paper.

References

[1] R.E. Bellman, Dynamic Programming, Princeton Univ. Press, NJ, 1957.

[2] R.E. Bellman, Introduction to Matrix Analysis, McGraw-Hill, New York, NY, 1970 (Second Edition is a SIAM edition 1997).

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

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

[5] S. Iwamoto, Inverse theorem in dynamic programming I, II, III, J. Math. Anal. Appl. 58(1977), 113–134, 247–279, 439–448.

[6] S. Iwamoto, Dynamic programming approach to inequalities, J. Math. Anal. Appl. 58(1977), 687–704.

[7] S. Iwamoto, Reverse function, reverse program and reverse theorem in mathematical programming, J. Math. Anal. Appl. 95(1983), 1–19.

[8] S. Iwamoto, Theory of Dynamic Program, Kyushu Univ. Press, Fukuoka, 1987 (in Japanese).

[9] S. Iwamoto, Cross dual on the Golden optimum solutions, Proceedings of the Workshop in Mathematical Economics, Research Institute for Mathematical Sciences, Kyoto Univ., Suri Kagaku Kokyu Roku No. 1443, 2005, 27-43.

[10] S. Iwamoto, The Golden trinity — optimality, inequality, identity —, Proceedings of the Workshop in Mathematical Economics, Research Institute for Mathematical Sciences, Kyoto Univ., Suri Kagaku Kokyu Roku No. 1488, 2006, 1-14.

[11] 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, 109–205.

[12] S. Iwamoto, Golden optimal policy in calculus of variation and dynamic programming, Advances in Mathematical Economics 10 (2007), 65–89.

[13] S. Iwamoto and M. Yasuda, Dynamic programming creates the Golden ratio, too, Proceedings of the Workshop “Decision Making under Uncertainty and Mathematical Models,” Research Institute for Mathematical Sciences, Kyoto Univ., Suri Kagaku Kokyu Roku No. 1477, 2006, 136-140.

[14] S. Iwamoto and M. Yasuda, Golden optimal path in discrete-time dynamic optimization processes, The 15-th International Conference on Difference Equations and Applications (ICDEA 2006), Kyoto Univ., Kyoto, 2006.

[15] S. Iwamoto, R.J. Tomkins and C.-L. Wang, Some theorems on reverse inequalities, J. Math. Anal. Appl. 119(1986), 282-299.

[16] H.W. Kuhn and A.W. Tucker, Nonlinear programming, Proceedings of the 2nd Berkeley Symposium on Mathematical Statistics and Probability, J. Neyman (Ed.), Univ. of California Press, Berkeley, Calif., 1951, 481–492.

[17] H. Walser, Der Goldene Schnitt, B.G. Teubner, Leibzig, 1996.

[18] W. Walter, On a functional equation of Bellman in the theory of dynamic programming, Aequations Math. 14 (1976), 435–444.