数理解析研究所講究録
第 1864 巻 2013 年 82-89

82

黄金最適化問題の双対化–不等式による–

岩本誠一*(九州大学・名誉教授), 木村寛 (秋田県立大学),
藤田敏治 (九州工業大学)

概要

本報告では、 $n$ 変数 2 次計画問題 (P) に対して、 “不等式による” 双対化 (dualise,dualize) に焦点をあてる。 その方法は (i) 平方完成、 (ii) 相加相乗平均である。 特に平方完成では、 拡大ラグランジュ乗数を用いて示していることに注意する。 またこのとき、 主問題 (P) および双対問題 (D) の最適解と最適値の間に黄金相補双対性が見られることを示す。

1黄金最適化問題

1.1

主問題$n$変数 $x=(x_{1}, x_{2}, \cdots, x_{n})$ の 2 次計画問題として次の最小化問題 (P) を考える。

minimizesubject to(P)

ここに $c\in R$ とする。

$\phi$$\sum_{k=0}^{n-1}[(x_{k}-x_{k+1})^{2}+x_{k+1}^{2}]+\phi^{-1}x_{n}^{2}$(i) $x\in R^{n}$(ii) $x_{0}=c.$は黄金数 (Golden number) を表し、$\phi=\frac{1+\sqrt{5}}{2}\approx 1.61803$である。 また黄金数については$1 :\phi=\phi^{-2}:\phi^{-1}, \phi^{-2}+\phi^{-1}=1$が成り立ち、 黄金数$\phi$

は 2 次方程式$x^{2}-x-1=0$の正の解としても定義される。
$*$

本研究は、 科学研究費補助金 「平成 22 年度基盤研究 (C) 」 課題番号 22540144 の助成を受けた。

(1)

83
補題 1 黄金数の和については、 任意の自然数$\phi$

1.

$\sum_{k=1}^{n}\phi^{2k-1}=\phi^{2n}-1,$2.

$\sum_{k=1}^{n}\phi^{-2k}=\phi^{-1}-\phi^{-2n-1},$

3. $\phi^{n}+\phi^{n+1}=\phi^{n+2}$

4$\cdot$$n=\cdots,$ $-2,$$n$に対して次が成り立っ。

$-1,0,1,2,$$\cdots,$$2 \sum_{k=1}^{n}\phi^{-3k-1}+\phi^{-3n-2}=\phi^{-2}.$

定義 1[5] 列$\{x_{n}\}_{n\geq 1}$

は$x_{n}=c\phi^{-2n}$

または$x_{n}=c\phi^{-n}$のとき、 黄金経路 Golden $path, GP)$ という。 ただし、といい、 後者を :1 型という。
$($$c$は定数である。 前者を 1:$\phi$型$\phi$

定理 1 主問題 (P) は$\hat{x}= (\hat{x}_{1},\hat{X}_{2}, \cdots ,\overline{x}_{n-1},\hat{x}_{n})=c(\phi^{-2}, \phi^{-4}, \cdots , \phi^{-2n+2}, \phi^{-2n})$で最小値 $m=\phi^{-1}c^{2}$ をもつ。
最小点 は 1: 型黄金経路になっている。
$\hat{x}$1.2$\phi$双対問題

問題 (P) の双対問題は$n$

変数 $\mu=(\mu_{1}, \mu_{2}, \cdots, \mu_{n})$ の最大化問題として次で与えられる :Maximize(D)$2c \mu_{1}-\mu_{1}^{2}-\sum_{k=1}^{n-1}[(\mu_{k}-\mu_{k+1})^{2}+\mu_{k+1}^{2}]-\phi^{-1}\mu_{n}^{2}$subject to (i)$\mu\in R^{n}.$定理 2 双対問題 (D) は$\mu^{*}= (\mu_{1}^{*}, \mu_{2}^{*}, \cdots, \mu_{n-1}^{*}, \mu_{n}^{*})=c(\phi^{-1}, \phi^{-3}, \cdots, \phi^{-2n+3}, \phi^{-2n+1})$

で最大値 $M=\phi^{-1}c^{2}$ をもつ。
最大点も 1:型黄金経路になっている。
$\mu^{*}$$\phi$

主問題 (P) の最小解と双対問題 (D) の最大解の間には次の 3 つの関係が成り立っている。

84
1.

最小値と最大値が等しい : $m=M$ . 共に初期値(双対性)

係数は黄金数の逆数

2.
3.

(黄金)

最小点
金経路である。

$\phi^{-1}$$c$の 2 次関数で、 そのである。

$(\hat{x}_{1},\hat{x}_{2}, .

.

.

, \hat{x}_{n})$と最大点$(\mu_{1}^{*}, \mu_{2}^{*}, .

.

.

, \mu_{n}^{*})$

は共に 1:$\phi$型の黄最小点と最大点を交互に編むと、 $\phi:1$ 型の黄金経路である。

(相補性)

この三位一体の関係を黄金相補双対性 (Golden complementary duality, $GCD$ ) という。

2不等式による双対化
ここでは主問題 (P) から双対問題 (D) を、不等式による 2 つの方法で導こう。 2.1 節では平方完成で、 2.2 節では相加・相乗平均で示す。

2.1

平方完成法

主問題 (P) に対して、 $x=(x_{1}, x_{2}, \cdots, x_{n})$ が制約条件 (i), (ii) を満たしているとして、その目的関数の値を $I(x)$ で表す。 また任意の実数列 $\mu=(\mu_{1}, \cdots, \mu_{n})$ に対して、 双対問
題 (D) の目的関数の値を $J(\mu)$ で表わす。 いま、 変数列 $u=(u_{0}, u_{1}, \cdots, u_{n-1})$ を$u_{k}=x_{k}-x_{k+1} 0\leq k\leq n-1 (’2)$
で導入する。 このとき次の定理を得る。

定理 3 主問題 (P) の実行可能解 $x\in R^{n}$ と、 双対問題 (D) の実行可能解 $\mu\in R^{n}$ に対して不等式(3)$I(x) \geq J(\mu)$が成り立つ。

Proof.

(2) を満たす任意の $(x, u)$ と、任意の実数列 $\mu=(\mu_{1}, \cdots, \mu_{n})$ を用いて、 $I(x)$ は次でも表される。
$I(x)= \sum_{k=0}^{n-1}[u_{k}^{2}+x_{k+1}^{2}+2\mu_{k+1}(x_{k}-x_{k+1}-u_{k})]+\phi^{-1}x_{n}^{2}$.

(4)(4) では列 $\{2\mu_{1},2\mu_{2}, . . . , 2\mu_{n}\}$ を等式制約に対応するラグランジュ変数列にとっている。 これを拡大ラグランジュ乗数列 (augmented Lagrange multipliers) という。 (4) より、$I(x) = 2c \mu_{1}+\sum_{k=0}^{n-1}(u_{k}^{2}-2\mu_{k+1}u_{k})+\sum_{k=1}^{n-1}[x_{k}^{2}-2(\mu_{k}-\mu_{k+1})x_{k}]$$+(1+\phi^{-1})x_{n}^{2}-2\mu_{n}x_{n}$85が得られる。

$u_{k}$の項と$x_{k}$の項を平方完成 (標準変形) すると、

$I(x) = 2c \mu_{1}+\sum_{k=0}^{n-1}[(u_{k}-\mu_{k+1})^{2}-\mu_{k+1}^{2}]$$+ \sum_{k=1}^{n-1}[\{x_{k}-(\mu_{k}-\mu_{k+1})\}^{2}-(\mu_{k}-\mu_{k+1})^{2}]$$+\phi(x_{n}-\phi^{-1}\mu_{n})^{2}-\phi^{-1}\mu_{n}^{2}.$ゆえに、 右辺から非負項を削除すると、(5)$I(X) \geq 2c\mu_{1}-\mu_{1}^{2}-\sum_{k=1}^{n-1}[(\mu_{k}-\mu_{k+1})^{2}+\mu_{k+1}^{2}]-\phi^{-1}\mu_{n}^{2}$となり、 この右辺は $\mu=(\mu_{1}, \ldots, \mu_{n})$ のみからなりを含まない。 すなわち (5) の右辺
は、 (D) の目的関数値 $J(\mu)$ を表わている。 したがって、 双対問題が得られた。
$x_{k}$$\square$定理 4(3) の等号は
$u_{k} = \mu_{k+1} k= 0,1, \cdots, n-1,$$x_{k} = \mu_{k}-\mu_{k+1} k = 1, 2, \cdots, n-1,$$x_{n} = \phi^{-1}\mu_{n}$のときに限り成り立つ。 この解愈$=$$(\hat{x},\hat{u};\mu^{*})$は、$(\hat{x}_{1}, \hat{x}_{2}, \cdots ,\hat{x}_{n-1}, \hat{x}_{n})=c(\phi^{-2}, \phi^{-4}, \cdots , \phi^{-2n+2}, \phi^{-2n})$$\hat{u}= (\hat{u}_{0},\hat{u}_{1}, \cdots ,\hat{u}_{n-2},\hat{u}_{n-1})=c(\phi^{-1}, \phi^{-3}, \cdots , \phi^{-2n+3}, \phi^{-2n+1})$$\mu^{*}=$$(\mu_{1}^{*}, \mu_{2}^{*}, \cdots , \mu_{n-1}^{*}, \mu_{n}^{*})=c(\phi^{-1}, \phi^{-3}, \cdots , \phi^{-2n+3}, \phi^{-2n+1})$である。 このとき両辺は$\phi^{-1}c^{2}$(7)(8)

等号条件は、 定理 3 の証明より明らかである。 このときのの値は、 定(2) より得られる。 ここでは両辺の値がであることを示す。
(勾については以下の通りである。

$1$、$I$,になる。

Proof.
理(6),$\hat{x},\hat{u},$定理$2$$\mu^{*}$$\phi^{-1}c^{2}$、$I( \hat{x})=\sum_{k=0}^{n-1}[(\hat{x}_{k}-\hat{x}_{k+1})^{2}+\hat{x}_{k+1}^{2}]+\phi^{-1}\hat{x}_{n}^{2}$$=c^{2} \sum_{k=0}^{n-1}[(\phi^{-2k}-\phi^{-2(k+1)})^{2}+(\phi^{-2(k+1)})^{2}]+c^{2}\phi^{-1}(\phi^{-2n})^{2}$$=c^{2}[ \sum_{k=1}^{2n}\phi^{-2k}+\phi^{-4n-1}]$$=c^{2}[(\phi^{-1}-\phi^{-4n-1})+\phi^{-4n-1}]$$=\phi^{-1}c^{2}.$(補題 1 より)

86
一方、$J(\mu^{*})$

については$J( \mu^{*})=2c\mu_{1}^{*}-\mu_{1}^{*2}-\sum_{k=1}^{n-1}[(\mu_{k}^{*}-\mu_{k+1}^{*})^{2}+\mu_{k+1}^{*2}]-\phi^{-1}\mu_{n}^{*2}$$=c^{2}[2 \phi^{-1}-\phi^{-2}-\sum_{k=1}^{n-1}\{(\phi^{-2k+1}-\phi^{-2k-1})^{2}+(\phi^{-2k-1})^{2}\}-\phi^{-4n+1}]$$=c^{2}[2 \phi^{-1}-\sum_{k=1}^{2n-2}\phi^{-2k}-(\phi^{-4n+2}+\phi^{-4n+1})]$$=c^{2}[2\phi^{-1}-(\phi^{-1}-\phi^{-4n+3})-\phi^{-4n+3}]$(補題 1 より)$=c^{2}(2\phi^{-1}-\phi^{-1})$$=\phi^{-1}c^{2}.$以上より、 両辺の値は2.2$\phi^{-1}c^{2}$口である。

相加・相乗平均法

定理 5 任意の $x,$ $y\in R^{1}$ に対して
$2xy\leq x^{2}+y^{2}$(9)が成り立つ。 等号は $x=y$ のときに限り成り立つ。
不等式 (9) は相加・相乗平均不等式 (arithmetic-geometric mean inequality, $AG$ ) とよばれる。
$AG$

不等式より、任意の実数$x_{1},$$\mu_{1}$に対して 2 つの不等式$2(c-x_{1})\mu_{1}\leq(c-x_{1})^{2}+\mu_{1}^{2},$$2 (\phi^{\frac{1}{2}}x_{1})(\phi^{-\frac{1}{2}}\mu_{1})\leq\phi x_{1}^{2}+\phi^{-1}\mu_{1}^{2}$と 2 つの等号条件 $c-x_{1}=\mu_{1},$補題 2$c$$\phi^{\frac{1}{2}}x_{1}=\phi^{-\frac{1}{2}}\mu_{1}$が成り立つ。 すなわち、次の補題を得る。

を定数とすると、 不等式$2 c\mu_{1}-\mu_{1}^{2}-\phi^{-1}\mu_{1}^{2}\leq(c-x_{1})^{2}+x_{1}^{2}+\phi^{-1}x_{1}^{2} \forall x_{1}\in R^{1}, \forall\mu_{1}\in R^{1}$が成り立つ。 等号は $x_{1}=\phi^{-2_{C}},$になる。

$\mu_{1}=\phi^{-1_{\mathcal{C}}}$のときに限り成り立つ。 このとき両辺は$\phi^{-1}c^{2}$

87
補題 3$c$を定数とする。 $(x_{1}, x_{2})\in R^{2},$のとき$(\mu_{1}, \mu_{2})\in R^{2}$

2 $c\mu_{1}-\mu_{1}^{2}-(\mu_{1}-\mu_{2})^{2}-\mu_{2}^{2}-\phi^{-1}\mu_{2}^{2}\leq(c-x_{1})^{2}+x_{1}^{2}+(x_{1}-x_{2})^{2}+x_{2}^{2}+\phi^{-1}x_{2}^{2}(10)$が成り立つ。 等号は $x_{1}=\phi^{-2_{C}},$ $x_{2}=\phi^{-4}c;\mu_{1}=\phi^{-1_{C}},$つ。 このとき両辺はになる。

$\mu_{2}=\phi^{-3_{C}}$のときに限り成り立$\phi^{-1}c^{2}$

Proof.

$AG$

不等式より、 任意の実数$x_{1},$$x_{2},$ $\mu_{1},$$\mu_{2}$に対して 4 つの不等式と等号条件$2(c-x_{1})\mu_{1}\leq(c-x_{1})^{2}+\mu_{1}^{2}$;$c-x_{1}=\mu_{1}$$2x_{1}(\mu_{1}-\mu_{2})\leq x_{1}^{2}+(\mu_{1}-\mu_{2})^{2}$;$x_{1}=\mu_{1}-\mu_{2}$$2(x_{1}-x_{2})\mu_{2}\leq(x_{1}-x_{2})^{2}+\mu_{2}^{2}$;$x_{1}-x_{2}=\mu_{2}$$2(\phi^{\frac{1}{2}}x_{2})(\phi^{-\frac{1}{2}}\mu_{2})\leq\phi x_{2}^{2}+\phi^{-1}\mu_{2}^{2}$;$\phi^{\frac{1}{2}}x_{2}=\phi^{-\frac{1}{2}}\mu_{2}$が成り立つ。 辺々加えると、 左辺は相殺して$2 c\mu_{1}\leq[(c-x_{1})^{2}+x_{1}^{2}+(x_{1}-x_{2})^{2}+\phi x_{2}^{2}]+[\mu_{1}^{2}+(\mu_{1}-\mu_{2})^{2}+\mu_{2}^{2}+\phi^{-1}\mu_{2}^{2}]$になる。 $\phi=1+\phi^{-1}$ より、 (10) を得る。 等号は 4 つの等号条件が同時に成り立っとき、
すなわち、$x_{1}=\phi^{-2_{C}}, x_{2}=\phi^{-4}c;\mu_{1}=\phi^{-1_{C}}, \mu_{2}=\phi^{-3_{\mathcal{C}}}$のとき成り立つ。 このとき両辺の値が$\phi^{-1}c^{2}$であることは、 次のようにしてわかる。 実際、左辺は次のようになる。
$(c-x_{1})^{2}+x_{1}^{2}+(x_{1}-x_{2})^{2}+x_{2}^{2}+\phi^{-1}x_{2}^{2}$$=c^{2}[(\phi^{-2}+\phi^{-4}+\phi^{-6}+\phi^{-8})+\phi^{-9}]$$=c^{2}[(\phi^{-1}-\phi^{-9})+\phi^{-9}]$$=\phi^{-1}c^{2}.$

一方、 右辺は$2 c\mu_{1}-\mu_{1}^{2}-(\mu_{1}-\mu_{2})^{2}-\mu_{2}^{2}-\phi^{-1}\mu_{2}^{2}$$=c^{2}[2\phi^{-1}-(\phi^{-2}+\phi^{-4})-(\phi^{-6}+\phi^{-7})]$$=c^{2}[2\phi^{-1}-(\phi^{-1}-\phi^{-5})-\phi^{-5}]$$=c^{2}(2\phi^{-1}-\phi^{-1})$$=\phi^{-1}c^{2}.$

したがって、 両辺の値は$\phi^{-1}c^{2}$である。

口88
定理 6

$c$を定数として、 $x_{0}=c$ とすると、 任意の $x=(x_{1}, x_{2}, \cdots, x_{n})\in R^{n},$ $\mu=$$(\mu_{1}, \mu_{2}, \cdots, \mu_{n})\in R^{n}$に対して$2 c \mu_{1}-\mu_{1}^{2}-\sum_{k=1}^{n-1}[(\mu_{k}-\mu_{k+1})^{2}+\mu_{k+1}^{2}]-\phi^{-1}\mu_{n}^{2}$(11)$\leq\sum_{k=0}^{n-1}[(x_{k}-x_{k+1})^{2}+x_{k+1}^{2}]+\phi^{-1}x_{n}^{2}$が成り立つ。 等号は
辺は$\phi^{-1}c^{2}$

Proof.

$x$が (6) の$\hat{x},$$\mu$が (8) の$\mu^{*}$であるときに限り成り立つ。 このとき両になる。 さらに (11) の右辺は $I(x)$ を、 左辺は $J(\mu)$ を表わしている。

$AG$ 不等式より、 $x,$$\mu$に対して $2n$ 個の不等式と等号条件$2x_{k-1}(\mu_{k-1}-\mu_{k})\leq x_{k-1}^{2}+(\mu_{k-1}-\mu_{k})^{2};x_{k-1}=\mu_{k-1}-\mu_{k} k=2, \ldots, n$$2(x_{k-1}-x_{k})\mu_{k}\leq(x_{k-1}-x_{k})^{2}+\mu_{k}^{2}$

2; $x_{k-1}-x_{k}=\mu_{k}$$k=1,$$\ldots,$$n$$(\phi^{\frac{1}{2}}x_{n})(\phi^{-\frac{1}{2}}\mu_{n})\leq\phi x_{n}^{2}+\phi^{-1}\mu_{n}^{2};\phi^{\frac{1}{2}}x_{n}=\phi^{-\frac{1}{2}}\mu_{n}$が成り立つ。 辺々加えると、 左辺が相殺して$2 c \mu_{1}\leq\sum_{k=0}^{n-1}[(x_{k}-x_{k+1})^{2}+x_{k+1}^{2}]+\phi^{-1}x_{n}^{2}$$+ \mu_{1}^{2}+\sum_{k=1}^{n-1}[(\mu_{k}-\mu_{k+1})^{2}+\mu_{k+1}^{2}]+\phi^{-1}\mu_{n}^{2}$になる。 $\phi=1+\phi^{-1}$ より、 (11) を得る。 $2n$ 個の等号条件が同時に成り立つとき、 等号は成り立つ。 しかもこの $2n$ 連立 $2n$ 元 1 次方程式は唯一の解 (6), (8) をもつ。 このとき両辺になる。 実際、 左辺はの値は$\phi^{-1}c^{2}$$\sum_{k=0}^{n-1}[(x_{k}-x_{k+1})^{2}+x_{k+1}^{2}]+\phi^{-1}x_{n}^{2}=c^{2}[\sum_{k=1}^{2n}\phi^{-2k}+\phi^{-4n-1}]$$=c^{2}[(\phi^{-1}-\phi^{-4n-1})+\phi^{-4n-1}]$$=\phi^{-1}c^{2}.$

一方、 右辺は$2 c \mu_{1}-\mu_{1}^{2}-\sum_{k=1}^{n-1}[(\mu_{k}-\mu_{k+1})^{2}+\mu_{k+1}^{2}]-\phi^{-1}\mu_{n}^{2}$$=c^{2}[2 \phi^{-1}-\sum_{k=1}^{2n-2}\phi^{-2k}-(\phi^{-4n+2}+\phi^{-4n+1})]$$=c^{2}[2\phi^{-1}-(\phi^{-1}-\phi^{-4n+3})-\phi^{-4n+3}]$$=c^{2}(2\phi^{-1}-\phi^{-1})$$=\phi^{-1}c^{2}.$89
したがって、 両辺の値は$\phi^{-1}c^{2}$である。

口参考文献[1] Bellman, R. ., Dynamic Programming, Princeton Univ. Press, $NJ$ , 1957.
$E$[2] Bellman, R. ., Introduction to Matrix Analysis, McGraw-Hill, $NY$ , 1970 (Second Edition is a SIAM edition 1997).
$E$[3] 岩本誠一，『動的計画論』，九大出版会，1987 年．

[4] Iwamoto, S., “The Golden trinity –optimility, inequality, identity –,” 「経済の数理解析」 , 京大数理研講究録，2006 年，pp. 1-14.
[5] 岩本誠一: 最適経路
フィボナッチから黄金へ –, 不確実性下における意思決定問題，京大数理研講究録，1734, 2011 年，pp.196-204.
–[6] 岩本誠一吉良知文・植野貴之，「 . ヴィンチ．コード」 , 経済学研究 (九大経済学会), 第 76 巻 2/3 号，2009 年，pp. 1-22.
$P^{\backslash ^{\backslash }}$[7] Iwamoto, S. and Kira, A., “The Fibonacci complementary duality in quadratic programming,” Ed. Takahashi, W. and Tanaka, T., Proceedings of the 5th Intl. Conference on Nonlinear Analysis and Convex Analysis ($NACA$ 2007 Taiwan), Yokohama,Yokohama Publishers, 2009, pp.63-73.
[8] Iwamoto, S. and Yasuda, M., “Golden optimal path in discrete-time dynamic optimization processes,” Ed. Elaydi, S., Nishimura, K., Shishikura, M. and Tose, N.,
Advanced Studies in Pure Mathematics Vol.53, Advances in Discrete Dynamic Systems, 2009, pp.77-86.
[9] Kira, A. and Iwamoto, S., “Golden complementary dual in quadratic optimization,”
Modeling Decisions for Artificial Intelligence, Proceedings of the Fifth Intl. Confern $ece$(MDAI 2008), Barcelona, 2008. Eds. Torra, V. and Narukawa, Y., Springer-Verlag
Lecture Notes in Artificial Intelligence, Vol.5285, 2008, pp.191-202.