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

1-A-1

メモリーレス準ニュートン法に基づく
非厳密ニュートン型近接 DC アルゴリズム

1.

05000392

中央大学*中山 舜民NAKAYAMA Shummin

01406032

慶應義塾大学成島康史

NARUSHIMA Yasushi

01702330

東京理科大学矢部博

YABE Hiroshi

はじめにNesterov の加速法を加えた近接勾配法と同様に，近接 DCA においても外挿付き近接 DCA [1] が有効な方

本稿では，次の最適化問題を扱う：

法として知られている．また，近接勾配法において，minn f (x) = g(x) + h(x).

x∈R(1)

ただし，g は L-平滑な関数とし，h は二つの凸関数 h1 とh2 の差で表される DC 関数 (Diﬀerence of two Convexfunctions)：

Nesterov の加速法とは別のアプローチとしてニュートン型近接勾配法が知られている．通常，ニュートン型近接勾配法は重み付き近接写像 (2) の計算に手間がかかるため，Nakayama et al. [2] は非厳密に重み付き近接写像を計算する非厳密ニュートン型近接勾配法を考え，

h(x) = h1 (x) − h2 (x)重み行列としてメモリーレス準ニュートン法を取り入であるとする．以降，∇g は g の勾配，∂h は h の劣微分とする．また，凸関数 h1 に対して正定値対称行列 Aを重み行列とした近接写像を{}
12ProxA(x̄)=argminh(x)+∥x−x̄∥
1h1A2x∈Rnれた非厳密ニュートン型近接勾配法を提案した．本研
究では，非厳密ニュートン型近接勾配法を拡張した非厳密ニュートン型近接 DCA の提案と，重み行列としてメモリーレス準ニュートン法の更新式を使用した方法(2)を提案する．

xT Ax は重み付きノル

2. 提案手法
2.1. 非厳密ニュートン型近接 DCAムである．ここで，I ∈ Rn×n を単位行列とし，A = I提案手法の反復式は，以下で与えられる：で定義する．ただし，∥x∥A ≡√のときは重み付き近接写像と重み付きノルムの A の表

xk+1 = xk + ηk dk , dk = x+
k − xk .

記を省略することとする．

(4)

問題 (1) を解くための方法として近接 DCA(DC Al-

ただし，ηk > 0 はステップ幅であり，探索方向に含まgorithm) が知られている．近接 DCA は，任意の初期れている x+k は以下の最適化問題の非厳密な解とする：{argmin h1 (x) + g(xk ) − h2 (xk )点 x0 ∈ Rn に対し，k 回目の反復点 xk での h2 の劣勾
配 ξk ∈ ∂h2 (xk ) を用いて，{
xk+1 = argmin h1 (x) + g(xk ) − h2 (xk )x∈Rn}
L+ (∇g(xk ) − ξk )T (x − xk ) + ∥x − xk ∥22)
(1= Prox L1 h1 xk − (∇g(xk ) − ξk )(3)
Lによって点列を生成する方法である．h2 (x) = 0 (ξk = 0)の場合，近接 DCA は通常の近接勾配法と一致することから，近接勾配法を拡張した方法となっている．まx∈Rn}
1+ (∇g(xk ) − ξk )T (x − xk ) + ∥x − xk ∥2Bk2k= ProxB(x−H(∇g(x)−ξ)).
(5)kkkkh1
ここで，Bk はヘッセ行列 ∇2 g(xk ) の正定値対称な近似行列であり1 ，Hk = Bk−1 とする．また，(5) を非厳密に計算する基準としてパラメータ θk ∈ [θ̄, 1] を与え，

∥rk ∥Hk ≤ (1 − θk )∥x+k − xk ∥Bk ,(6)+rk ∈ ∇g(xk ) − ξk + Bk (x+k − xk ) + ∂h1 (xk )(7)た，近接 DCA は以下で定義される臨界点に収束するを満たす x+k を (5) の近似解として採用する．ここで rkことが知られている．

は勾配残差である．
∗

定義 1. 以下の条件を満たす点 x を臨界点と呼ぶ．

以上をまとめたアルゴリズムは以下の通りである．

0 ∈ ∇g(x∗ ) + ∂h1 (x∗ ) − ∂h2 (x∗ ).

1 B = L × I, η = 1 のとき反復式 (4)–(5) は近接 DCA (3) のkk
反復式と一致する．

アルゴリズム 1 (非厳密ニュートン型近接 DCA).

メータである．パラメータ γk と νk を適切に選択する

Step 0: 初期点 x0 ∈ Rn , δ, β ∈ (0, 1), θ̄ ∈ (0, 1] を与ことで，仮定 2 が成立することを注意しておく．
次に，アルゴリズム 1 の k 回目の反復における Step 2

え，k = 0 とする．

Step 1: 終了条件を満たすならばアルゴリズムを停止で x+k を求める方法を考える．以降では x̄ = xk −Hk (∇g(xk ) − ξk ),√γk
Step 2: Bk と Hk ，ξk ∈ ∂h2 (xk ), θk ∈ [θ̄, 1] を与え，
u=zk−1 ,1T z
Bk+s(6)–(7) を満たす xk ≈ Proxh1 (xk − Hk (∇g(xk ) −k−1 k−1
して xk を最適解とする．

ξk )) を求め，探索方向を dk = x+k − xk とする．
Step 3: 以下の条件を満たす最小の非負整数 i を見つけ，ステップ幅を ηk = β i とする：
iと置き，α = (α1 , α2 )T ∈ R2 に対して，ζ(α) = x̄ −α1 u1 + α2 (I + u1 uT1 )−1 u2 とし，α∗ を連立非線形方

uT1 (x̄ + α2 (I + u1 uT1 )−1 u2 − Proxh1 (ζ(α))) + α1 = 0

λk = (∇g(xk ) − ξk )T dk + h1 (x+k ) − h1 (xk ).

uT2 (x̄ − Proxh1 (ζ(α))) + α2 = 0Step 4: 点 xk+1 を (4) によって更新する．
Step 5: k = k + 1 として Step 1 に戻る．

2の唯一解であるとする．このとき，∗kProxB
h1 (x̄) = Proxh1 (ζ(α ))このアルゴリズムは h2 (x) = 0 (ξk = 0) である場合に [2] のアルゴリズムの枠組みと一致する．次に，収束定理のために目的関数とアルゴリズムにそれぞれ以下の仮定を設ける．
仮定 1.

sk−1
∥sk−1 ∥程式

f (xk + β dk ) ≤ f (xk ) + δβ λk ,iu2 =1. g は連続的微分可能であり，∇g はリプシッが成立する [3]．よって，一般化ニュートン法を用いて上述の 2 次元の連立非線形方程式を解くことで x+k を容易に計算できる．

3.

ツ連続である．

2. h1 は下半連続な真凸関数とし，h2 は連続な凸関数

数値実験提案手法（公式 (8) を用いたアルゴリズム１）と外挿付き近接 DCA [1] の比較を行い，提案手法の有効性をとする．
仮定 2. すべての反復 k において Bk は一様正定値か検証する．数値実験の結果は当日発表する．

つ有界である．

参考文献

上記の仮定の下で以下の定理が成り立つ．
定理 1. 仮定 1–2 を満たすとし，点列 {xk } はアルゴリ
ズム 1 によって生成されるとする．このとき，目的関数 f が下に有界であれば

diﬀerence-of-convex algorithm with extrapolation,Computational Optimization and Applications, 69(2018), 297–324.

lim ∥dk ∥ = 0[2] S. Nakayama, Y. Narushima and H. Yabe Inex-k→∞が成り立つ．さらに，点列 {xk } が有界であれば点列{xk } の任意の集積点は (1) の臨界点である．

2.2.

[1] B. Wen, X. Chen and T.K. Pong, A proximalact proximal memoryless quasi-Newton methods
based on the Broyden family for minimizing composite functions, Computational Optimization andメモリーレス BFGS 公式

Applications, 79 (2021), 127–154.

提案手法では，アルゴリズム 1 の Step 2 の Bk とし[3] 中山舜民，成島康史，矢部博，“メモリーレス BFGSて Nakayama et al. [2] の提案したメモリーレス BFGS

公式に基づく非厳密ニュートン型近接勾配法におけ公式を用いる2 ：る内部反復の改良について”，日本オペレーションTzk−1 zk−1
sk−1 sTk−1+ γk T.
Bk = I − T
sk−1 sk−1
sk−1 zk−1(8)

ここで，sk−1 = xk − xk−1 , zk−1 = ∇g(xk ) −∇g(xk−1 ) + νk sk−1 であり，γk > 0, νk ≥ 0 はパラ2 H = B −1 も B −1 を計算するのではなく，更新公式から計算
kkk
可能だが，紙面の都合上，その更新公式は省略する．

ズ・リサーチ学会 2021 年春季研究発表会アブスト
ラクト集， 1-A-9.