日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

1-A-5

十分な降下条件を満たす探索方向を生成する Riemann 多様体上の共役勾配法
05001362
01016200

1.

明治大学
明治大学

*酒井 裕行飯塚 秀明

はじめに制約空間が Riemann 多様体と呼ばれる幾何学的構造を持つような制約付き最適化問題は Riemann多様体上の制約なし最適化問題と捉えることができる。文献 [1, 2, 3, 4] において、非線形共役勾配法の Riemann 多様体上への拡張や、その収束性についての証明が与えられている。本発表では、Riemann 多様体上の制約なし最適化問題における共役勾配法について、十分な降下条件という観点から議論した上で、新たなアルゴリズムを提案する。

2.

Riemann 多様体上の共役勾配法

微分可能多様体 M がRiemann 多様体であるとは、微分可能多様体の各点 x ∈ M における接空間
Tx M に正定値内積 ⟨·, ·⟩x が与えられているようなもののことをいう。
M を Riemann 多様体とする。このとき、次の最適化問題を解くことを考える。

Minimize
Subject tof (x)x ∈ M.

(1)

問題 (1) を解くため、Euclid 空間における共役勾配法が Riemann 多様体上へ拡張されており、アルゴリズム 1 のような枠組みで表される。アルゴリアルゴリズム 1 Riemann 多様体上の共役勾配法
Require:Riemann 多様体 (M, g), レトラクション R
1: x0 ∈ M, η0 = −gradf (x0 ).
2: for k = 0, 1, . . . do
3:
ステップ幅 αk を決定.
4:
xk+1 = Rxk (αk ηk )5:
βk を計算.
6:
gk+1 := − grad f (xk+1 ) を計算.
7:
ηk+1 = −gk+1 + βk+1 Tαk ηk (ηk )8: end forズム 1 におけるパラメータ βk+1 は様々な選び方

SAKAI Hiroyuki
IIDUKA Hideakiが考えられ、Hestenes–Stiefel (HS) 法、Fletcher–Reeves (FR) 法 [2]、Polak–Ribière–Polyak (PRP)法や Dai–Yuan (DY) 法 [3] が Euclid 空間からの拡張として知られており、それぞれ以下のように表される。

⟨gk+1 , yk+1 ⟩xk+1HS
⟩
βk+1
=⟨
, (2)
− ⟨gk , ηk ⟩xk
gk+1 , TαSk ηk (ηk ) xk+1

∥gk+1 ∥2xk+1
FR
βk+1 =,∥gk ∥2xk
PRPβk+1=⟨gk+1 , yk+1 ⟩xk+1∥gk ∥2xk(3),(4)∥gk+1 ∥2xk+1DY⟩=⟨
βk+1, (5)gk+1 , TαSk ηk (ηk ) x− ⟨gk , ηk ⟩xkk+1

ここで、T S : T M ⊕ T M → T M は scaled vectortransport [2] と呼ばれる写像である。ただし、T Mは M の接束であり、⊕ は Whitney 和と呼ばれるベクトル束の演算である。[4] では、(2) と (5) のハ
イブリッド手法として
Hyb1
HS
DY
βk+1= max{0, min{βk+1, βk+1}}が提案されている。

3.

十分な降下条件を満たす探索方向

アルゴリズム 1 の探索方向について、以下のような条件を考えることができる。ある正の実数 κ > 0が存在して、⟨gk , ηk ⟩xk ≤ −κ ∥gk ∥2(6)を満たす。式 (6) を十分な降下条件 [6] といい、(3)や (5) を用いた場合、適切な直線探索を用いることで、この条件を満たすことが知られている。十分な降下条件は Euclid 空間においても広く研究されており [5]、式 (6) は Riemann 多様体への自然な拡張である。

4.

提案手法

本発表では、式 (6) を満たすような、以下のような 2 種類の手法を提案する。

⟨⟩
SD
βk+1
= βk+1 − µ ∥ξk+1 ∥2xk+1 gk+1 , TαSk ηk (ηk ) xk+1(7)Hyb2FR
PRPβk+1= max{0, min{βk+1, βk+1}}.

(8)

ここで、ξk+1 ∈ Txk+1 M および、µ > 1/4 である。
式 (7) は、Euclid 空間における Hager–Zhang 法 [7]の拡張であり、以下の命題 1 に示すように直線探索に依らずに式 (6) を満たす [6, Theorem 3.4]。とくに、κ = 1 − 1/(4µ) である。
SD
命題 1 アルゴリズム 1 において βk+1 = βk+1とすると、アルゴリズム 1 により生成される点列{xk }k=0,1··· は以下の不等式を満たす。
)(1⟨gk , ηk ⟩xk ≤ − 1 −∥gk ∥2xk .
4µ

ここで gk := grad f (xk ) である。
一方、式 (8) は Euclid 空間におけるハイブリッド手法 [8] の拡張であり、適切な直線探索などの仮定のもとで、式 (6) を満たすことを示すことができる [6, Theorem 3.1]。さらに、式 (8) を用いた場合、自然な条件のもとで大域収束性を示すこともできる [6, Theorem 3.3]。

5.

数値実験

数値実験では、様々な Riemann 多様体上の制約なし最適化問題を合計 400 問解くことで、提案手法である式 (7) や式 (8) を既存手法と比較する。数値実験の結果から、式 (7) を用いた場合、直線探索アルゴリズムの選び方に依らず、安定して少ない反復回数で問題を解けることが示される。一方、
式 (8) を用いた場合では、適切な直線探索を用いれば非常に少ない反復回数で問題を解けるが、直線探索が不適切な場合は解に収束できないことが多くなることが示される。

参考文献[1] P.-A. Absil, R. Mahony and R. Sepulchre,
Optimization Algorithms on Matrix Manifolds, Princeton University Press, 2008.

[2] H. Sato and T. Iwai, A new, globally convergent Riemannian conjugate gradient method.
Optimization, 64(4), 1011-1031, 2015.
[3] H. Sato, A Dai-Yuan-type Riemannian conjugate gradient method with the weak Wolfe
conditions, Computational Optimization andApplications, 64: 101-118, 2016.
[4] H. Sakai and H. Iiduka, Hybrid Riemannian conjugate gradient methods with global
convergence properties, Computational Optimization and Applications, 77(3), 811-830,
2020.
[5] Y. Narushima and H. Yabe, A survey of suﬃcient descent conjugate gradient methods forunconstrained optimization, SUT journal ofMathematics, 50(2), 2014.
[6] H. Sakai, and H Iiduka. Suﬃcient Descent
Riemannian Conjugate Gradient Methods.
Journal of Optimization Theory and Applications, 1-21, 2021.
[7] W. W. Hager and H. Zhang, A new conjugate
gradient method with guaranteed descent andan eﬃcient line search. SIAM Journal on optimization, 16(1), 170-192, 2005.
[8] Y. F. Hu, and C. Storey, Global convergence
result for conjugate gradient methods, Journal of Optimization Theory and Applications,71(2), 1991.