大規模無制約最適化問題に対する
数値解法アルゴリズム～基礎から微分不可能な正則化項を含む問題への拡張まで～

慶應義塾大学成島康史

2023年8月8日
RIMS共同研究「組合せ最適化セミナー」
2023/8/8

COSS2023

1

目次• 第1部（10:00～11:00）• 無制約最適化の基礎• 反復法• 直線探索• 最急勾配法，ニュートン法，準ニュートン法• 第2部（11:15～12:15）• 大規模無制約最適化問題に対する反復法• 記憶制限準ニュートン法，BB法• 非線形共役勾配法• メモリーレス準ニュートン法• 第3部（13:25～14:25）• 微分不可能な正則化項を含む問題への拡張• 近接勾配法• ニュートン型近接勾配法

2023/8/8

COSS20232

無制約最適化問題
無制約最適化問題
minimize𝑓𝑓(𝒙𝒙)

𝑓𝑓: 𝑅𝑅 𝑛𝑛 → 𝑅𝑅
無制約最適化問題のイメージ図••

任意の𝒙𝒙 ∈ 𝑅𝑅 𝑛𝑛 に対して，𝑓𝑓 𝒙𝒙∗ ≤ 𝑓𝑓(𝒙𝒙) となる点 𝒙𝒙∗ ∈ S を(大域的)最適解という．
ある近傍 𝐵𝐵 𝒙𝒙∗ = 𝒙𝒙 𝒙𝒙∗ − 𝒙𝒙 ≤ 𝜀𝜀} が存在して，任意の 𝒙𝒙 ∈ 𝐵𝐵(𝑥𝑥 ∗ )に対して 𝑓𝑓 𝒙𝒙∗ ≤ 𝑓𝑓(𝒙𝒙) となる点 𝒙𝒙∗ を局所的最適解という．
局所的最適解（の一つ）を見つけるアルゴリズムを考える(目的関数の凸性などがあれば大域的最適解の保証あり)

2023/8/8

COSS20233

反復法
minimize
反復式

反復法：初期点 𝑥𝑥0 ∈ 𝑅𝑅 𝑛𝑛 からスタートして逐次的に最適解に近づけていく
数値解法

𝑓𝑓(𝒙𝒙)

局所的最適解𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑘𝑘 𝑑𝑑𝑘𝑘

𝑑𝑑𝑘𝑘 ∈ 𝑅𝑅 𝑛𝑛 : 探索方向
𝛼𝛼𝑘𝑘 > 0 : ステップ幅

𝑥𝑥3

(初期点)
2023/8/8

𝑥𝑥0

𝑥𝑥2

𝑥𝑥1

𝑑𝑑0

目的関数の等高線
COSS2023

4反復法のアルゴリズム
アルゴリズム（プロトタイプ）
1.
2.
3.
4.
5.
6.

初期点 𝑥𝑥0 ∈ 𝑅𝑅 𝑛𝑛 を与える．𝑘𝑘 = 0 として，ステップ 2. へ進む．
終了判定を行い終了判定条件を満たしていれば終了する．
探索方向 𝑑𝑑𝑘𝑘 を計算する．

直線探索により ステップ幅 𝛼𝛼𝑘𝑘 を計算する．
𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑘𝑘 𝑑𝑑𝑘𝑘 により点列を更新．

𝑘𝑘 ← 𝑘𝑘 + 1 としてステップ 2. に戻る．

ステップ 2. の終了判定では，1次の最適性条件を満たしているかを判定する．例えば，•||𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )|| が十分小さくなったら終了などを使用する
2023/8/8

COSS2023

5

アルゴリズムの大域的収束性
大域的収束性：任意の初期点からスタートした時に生成される点列 𝑥𝑥𝑘𝑘 が局所的最適解 𝑥𝑥 ∗ に収束する性質＊「大域的最適解に収束する性質」ではないことに注意
定理（無制約最適化問題の最適性条件）

1.

𝑥𝑥 ∗が無制約最適化問題の局所最適解ならば•
𝛻𝛻𝑓𝑓 𝑥𝑥 ∗ = 0 (1次の必要条件)•
𝛻𝛻 2 𝑓𝑓(𝑥𝑥 ∗ ) は半正定値 (2次の必要条件)
2. 𝑥𝑥 ∗が以下の条件を満たすならば、𝑥𝑥 ∗ は局所最適解である(2次の十分条件)•
𝛻𝛻𝑓𝑓 𝑥𝑥 ∗ = 0•
𝛻𝛻 2 𝑓𝑓(𝑥𝑥 ∗ ) は正定値
𝛻𝛻𝑓𝑓 𝑥𝑥 = 0 を満たす点は解の候補 𝛻𝛻𝑓𝑓 𝑥𝑥 = 0を満たす点は停留点と呼ばれる
実際には lim 𝑥𝑥𝑘𝑘 − 𝑥𝑥 ∗ = 0 の代わりに
𝑘𝑘→∞

lim

𝑘𝑘→∞

∇𝑓𝑓 𝑥𝑥𝑘𝑘= 0,

liminf ∇𝑓𝑓 𝑥𝑥𝑘𝑘
𝑘𝑘→∞

をもって大域的収束と呼ぶことが多い
2023/8/8

COSS2023=06

アルゴリズムの局所的収束性
局所的収束性：点列 𝑥𝑥𝑘𝑘 が解の近くにいるときに，どのように収束するかを表す性質＊主に収束する速さを考えることが多い

•

•

•

•

(q-)1次収束: 正定数 𝑐𝑐 < 1 が存在して以下を満たす
𝑥𝑥𝑘𝑘+1 − 𝑥𝑥 ∗ ≤ 𝑐𝑐||𝑥𝑥𝑘𝑘 − 𝑥𝑥 ∗ ||(q-)2次収束: 正定数 𝑐𝑐 が存在して以下を満たす
𝑥𝑥𝑘𝑘+1 − 𝑥𝑥 ∗ ≤ 𝑐𝑐 𝑥𝑥𝑘𝑘 − 𝑥𝑥 ∗2(q-)超1次収束: 0に収束する正の数列 𝑐𝑐𝑘𝑘 が存在して以下を満たす
𝑥𝑥𝑘𝑘+1 − 𝑥𝑥 ∗ ≤ 𝑐𝑐𝑘𝑘 ||𝑥𝑥𝑘𝑘 − 𝑥𝑥 ∗ ||r-p次収束：正定数 𝑐𝑐 とq-p次収束する数列𝜉𝜉𝑘𝑘 が存在して以下を満たす
𝑥𝑥𝑘𝑘 − 𝑥𝑥 ∗ ≤ 𝑐𝑐𝜉𝜉𝑘𝑘

2023/8/8

COSS2023

7

無制約最適化問題に対する反復法
無制約最小化問題
最小化

𝑓𝑓(𝑥𝑥)

アルゴリズム（プロトタイプ）
1.
2.
3.
4.
5.
6.

2023/8/8

初期点 𝑥𝑥0 ∈ 𝑅𝑅 𝑛𝑛 を与える．𝑘𝑘 = 0 として，ステップ 2. へ進む．
||𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )|| が十分小さくなったら終了する．

探索方向 𝑑𝑑𝑘𝑘 を計算する．

直線探索により ステップ幅 𝛼𝛼𝑘𝑘 を計算する．
𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑘𝑘 𝑑𝑑𝑘𝑘 により点列を更新．

𝑘𝑘 ← 𝑘𝑘 + 1 としてステップ 2. に戻る．

COSS20238降下方向
方向微係数が負，つまり，∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘 < 0∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘 → 0 の時，∇𝑓𝑓 𝑥𝑥𝑘𝑘 → 0 を保証であるとき，𝑑𝑑𝑘𝑘 は降下方向であるという．さらに，ある正の定数 𝑐𝑐 が存在して∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘 ≤ −𝑐𝑐 ∇𝑓𝑓 𝑥𝑥𝑘𝑘を満たすとき，𝑑𝑑𝑘𝑘 は十分な降下方向であるという．

2𝑦𝑦 = 𝑓𝑓(𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑑𝑑𝑘𝑘 )𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )2023/8/8

𝑥𝑥𝑘𝑘

𝑑𝑑𝑘𝑘

𝛼𝛼

COSS2023

接線の傾き  ∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘

9

直線探索(正確な直線探索)
𝑑𝑑𝑘𝑘 方向に最小となるステップ幅

𝛼𝛼𝑘𝑘 = argmin𝛼𝛼>0 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑑𝑑𝑘𝑘

を選択することを正確な直線探索と呼ぶ．
例）狭義2次凸関数

1 ⊤𝑓𝑓 𝑥𝑥 = 𝑥𝑥 𝐴𝐴𝐴𝐴 + 𝑏𝑏⊤ 𝑥𝑥 (𝐴𝐴は正定値対称行列)2の場合，正確なステップ幅はで計算可能．
2023/8/8

𝐴𝐴𝑥𝑥𝑘𝑘 + 𝑏𝑏 ⊤ 𝑑𝑑𝑘𝑘
𝛼𝛼𝑘𝑘 = −𝑑𝑑𝑘𝑘⊤ 𝐴𝐴𝑑𝑑𝑘𝑘
COSS202310直線探索（Wolfe条件）
直線探索においては, ステップ幅𝛼𝛼𝑘𝑘 に何らかの条件を課すことが多い

Wolfe条件

𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑑𝑑𝑘𝑘 ≤ 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝛿𝛿1 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘
𝛿𝛿2 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘 ≤ 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑑𝑑𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘

(単独でArmijo条件)(0 < 𝛿𝛿1 < 𝛿𝛿2 < 1)𝑦𝑦 = 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝛿𝛿1 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 𝑇𝑇𝑑𝑑𝑘𝑘

𝑦𝑦 = 𝑓𝑓(𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑑𝑑𝑘𝑘 )傾き𝛿𝛿2 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 𝑇𝑇𝑑𝑑𝑘𝑘

選択可能2023/8/8

COSS202311直線探索(分割法)

選択可能2023/8/8

COSS2023

12

反復法の収束性に関連する仮定
仮定

目的関数 𝑓𝑓 は下に有界，かつ初期点𝑥𝑥0における準位集合 ℒ = 𝑥𝑥 | 𝑓𝑓 𝑥𝑥 ≤ 𝑓𝑓(𝑥𝑥0 )の適当な凸近傍𝒩𝒩において連続微分可能で，勾配 ∇𝑓𝑓 はリプシッツ連続，つまり，ある正の定数 𝐿𝐿 が存在して，任意の 𝑢𝑢, 𝑣𝑣 ∈ 𝒩𝒩 に対してが成立する．

∇𝑓𝑓 𝑢𝑢 − ∇𝑓𝑓 𝑣𝑣≤ 𝐿𝐿 𝑢𝑢 − 𝑣𝑣

∇𝑓𝑓 の(定数𝐿𝐿を伴った)リプシッツ連続は 𝐿𝐿-平滑 とも呼ばれる．
𝐿𝐿-平滑な関数 𝑓𝑓 に対して••

𝑓𝑓 𝑦𝑦 ≤ 𝑓𝑓 𝑥𝑥が成立する．

2023/8/8+ ∇𝑓𝑓 𝑥𝑥 ⊤ 𝑦𝑦 − 𝑥𝑥

𝐿𝐿2+
𝑥𝑥 − 𝑦𝑦𝑓𝑓𝑓𝑓𝑓𝑓 ∀𝑥𝑥, 𝑦𝑦 ∈ 𝒩𝒩
2

COSS2023

13

ズーテンダイク条件
ズーテンダイク(Zoutendjik)条件
前述の仮定が成り立っているとする．探索方向が降下方向であり，直線探索で
Wolfe条件を満たす任意の反復法において，以下が成立する：∞

� ∇𝑓𝑓 𝑥𝑥𝑘𝑘

𝑘𝑘=0

2

cos 2 𝜃𝜃𝑘𝑘 =

∞

�

𝑘𝑘=0

∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘 2
𝑑𝑑𝑘𝑘

2

< ∞.

• 勾配ベクトルと探索方向のなす角を 𝜃𝜃𝑘𝑘 とすると cos 𝜃𝜃𝑘𝑘 =∞� ∇𝑓𝑓 𝑥𝑥𝑘𝑘

𝑘𝑘=0

2

cos 2 𝜃𝜃𝑘𝑘 < +∞∃𝑐𝑐̅ > 0, 𝑠𝑠. 𝑡𝑡. cos 𝜃𝜃𝑘𝑘 ≥ 𝑐𝑐̅ 𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎𝑎𝑎𝑎𝑎 𝑘𝑘 ≥ 02023/8/8

COSS2023∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘∇𝑓𝑓 𝑥𝑥𝑘𝑘
𝑑𝑑𝑘𝑘

→ lim

𝑘𝑘→∞

∇𝑓𝑓 𝑥𝑥𝑘𝑘=0
14

大域的収束性の例
定理
ズーテンダイク条件のときと同様の仮定が成り立っており，
探索方向が十分な降下方向であるとする．さらに，正の定数 𝛾𝛾 が存在して，すべての 𝑘𝑘 に対して，
𝑑𝑑𝑘𝑘

𝑏𝑏

≤ 𝛾𝛾 ∇𝑓𝑓 𝑥𝑥𝑘𝑘

0 < 𝑏𝑏 ≤ 2(探索方向の有界性)が成立するならば，アルゴリズムによって生成される点列は，ある 𝑘𝑘 番目の反復において ∇𝑓𝑓 𝑥𝑥𝑘𝑘 = 0 となるか，もしくは，liminf𝑘𝑘→∞の意味で大域的に収束する．

∇𝑓𝑓 𝑥𝑥𝑘𝑘=0

注意：ある 𝑘𝑘 番目で ∇𝑓𝑓 𝑥𝑥𝑘𝑘 = 0 となる場合は，そこでアルゴリズムが停止するので，以降では ∇𝑓𝑓 𝑥𝑥𝑘𝑘 ≠ 0 for all 𝑘𝑘 ≥ 0 として考える．

2023/8/8

COSS2023

15

大域的収束性の例
2• 十分な降下条件： ∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘 ≤ −𝑐𝑐 ∇𝑓𝑓 𝑥𝑥𝑘𝑘
• 探索方向の有界性： 𝑑𝑑𝑘𝑘•

≤ 𝛾𝛾 ∇𝑓𝑓 𝑥𝑥𝑘𝑘

∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘∞
ズーテンダイク条件： ∑𝑘𝑘=0
2
𝑑𝑑
𝑘𝑘

証明

背理法の仮定として liminf𝑘𝑘→∞が成立する．したがって，∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘 2
𝑑𝑑𝑘𝑘

2

≥

∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘∞∑となり， 𝑘𝑘=02𝑑𝑑𝑘𝑘

よって証明終了．□

2023/8/8

2∇𝑓𝑓 𝑥𝑥𝑘𝑘∇𝑓𝑓 𝑥𝑥𝑘𝑘

𝑐𝑐 2 ∇𝑓𝑓 𝑥𝑥𝑘𝑘

𝛾𝛾 2 ∇𝑓𝑓 𝑥𝑥𝑘𝑘

2

𝑏𝑏

<∞

(0 ≤ 𝑏𝑏 < 2)

≠ 0 とすると，𝜀𝜀 > 0 が存在して,≥ 𝜀𝜀4(∀𝑘𝑘 ≥ 0)

𝑐𝑐 2 ∇𝑓𝑓 𝑥𝑥𝑘𝑘
2𝑏𝑏 =
𝛾𝛾 2

2(2−𝑏𝑏)𝑐𝑐 2𝜀𝜀 2(2−𝑏𝑏)≥𝛾𝛾 2= ∞ が成立するが，これはズーテンダイク条件に反する．
COSS2023

16

Armijo条件下での大域的収束性
Armijo条件のみの場合の大域的収束性を考えてみる• 十分な降下条件： ∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘 ≤ −𝑐𝑐 ∇𝑓𝑓 𝑥𝑥𝑘𝑘

• 探索方向の有界性： 𝑑𝑑𝑘𝑘

2≤ 𝛾𝛾 ∇𝑓𝑓 𝑥𝑥𝑘𝑘

• Armijo条件: 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑑𝑑𝑘𝑘 ≤ 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑘𝑘 𝛿𝛿1 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘

• ステップ幅の下限が存在: ∃𝛼𝛼� > 0 , 𝑠𝑠. 𝑡𝑡. 𝛼𝛼� ≤ 𝛼𝛼𝑘𝑘 𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎𝑎𝑎𝑎𝑎 𝑘𝑘

証明 上記の条件より

𝑓𝑓 𝑥𝑥𝑘𝑘 − 𝑓𝑓 𝑥𝑥𝑘𝑘+1 ≥ −𝛼𝛼𝑘𝑘 𝛿𝛿1 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘 ≥ 𝛼𝛼𝑐𝑐𝛿𝛿� 1 ∇𝑓𝑓 𝑥𝑥𝑘𝑘

2>0が成立する．一方， {𝑓𝑓 𝑥𝑥𝑘𝑘 } は下に有界な単調減少列なので，極限が存在するので，上式よりlim ∇𝑓𝑓 𝑥𝑥𝑘𝑘 = 0
𝑘𝑘が成立する．
2023/8/8

COSS202317無制約最適化問題に対する反復法
最小化

𝑓𝑓(𝑥𝑥)

反復法
𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑘𝑘 𝑑𝑑𝑘𝑘

代表的な方法（探索方向の選択法）
•

最急降下法

𝑑𝑑𝑘𝑘 = −𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )1次収束する方法だが，（特に悪条件な問題に対して）効率が悪い•

ニュートン法𝛻𝛻2 𝑓𝑓 𝑥𝑥𝑘𝑘 𝑑𝑑𝑘𝑘 = −𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 または 𝑑𝑑𝑘𝑘 = −𝛻𝛻2 𝑓𝑓 𝑥𝑥𝑘𝑘 −1 𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )2次収束する方法だが，探索方向が目的関数値の下がる方向(降下方向)とは限らない•

準ニュートン法(𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 𝑇𝑇 𝑑𝑑𝑘𝑘 < 0)𝐵𝐵𝑘𝑘 𝑑𝑑𝑘𝑘 = −𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 または 𝑑𝑑𝑘𝑘 = −𝐻𝐻𝑘𝑘 𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )ただし，𝐵𝐵𝑘𝑘 ≈ 𝛻𝛻 2 𝑓𝑓 𝑥𝑥𝑘𝑘 , 𝐻𝐻𝑘𝑘 = 𝐵𝐵𝑘𝑘−1(近似行列をうまく選べば)降下方向を生成し，さらに超1次収束する方法
ただし，𝐵𝐵𝑘𝑘 , 𝐻𝐻𝑘𝑘 は密行列なので，大規模な問題には不向き)

2023/8/8

COSS2023

18

最急降下法
最急降下法: 目的関数の1次近似を(局所的に)最小にする方向を選択
1次近似 : 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝑑𝑑 ≈ ℓ 𝑑𝑑 = 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 𝑇𝑇 𝑑𝑑

1次近似は 𝑑𝑑 について線形なので，いくらでも小さくできる 𝑑𝑑 が一定と仮定して ℓ(𝑑𝑑) を最小化する 𝑑𝑑 を選択
𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 𝑇𝑇𝑑𝑑 = 𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )𝑑𝑑 cos 𝜃𝜃  cos 𝜃𝜃 = −1 のときが最小

𝑑𝑑𝑘𝑘 = −𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )最急降下方向𝑑𝑑𝑘𝑘 = −𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )2023/8/8

𝑥𝑥𝑘𝑘
COSS2023𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )19

最急降下法の収束性
大域的収束性𝑑𝑑𝑘𝑘 = −∇𝑓𝑓 𝑥𝑥𝑘𝑘 なので，

∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘 = − ∇𝑓𝑓 𝑥𝑥𝑘𝑘

2,

𝑑𝑑𝑘𝑘 = ∇𝑓𝑓(𝑥𝑥𝑘𝑘 )が成立する．よって，ズーテンダイク条件と同様の仮定の下で liminf ∇𝑓𝑓 𝑥𝑥𝑘𝑘が成り立つ．

𝑘𝑘→∞=0凸二次関数に対する収束率12

目的関数が 𝑓𝑓 𝑥𝑥 = 𝑥𝑥 ⊤ 𝑄𝑄𝑄𝑄 + 𝑐𝑐 ⊤ 𝑥𝑥 (𝑄𝑄 は正定値対称行列)であるとする．この時，𝛼𝛼𝑘𝑘 = argmin𝛼𝛼>0 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑑𝑑𝑘𝑘

正確な直線探索

とした最急降下法によって生成される点列の収束率は以下のとおりである：
𝑥𝑥𝑘𝑘+1 − 𝑥𝑥 ∗ 𝐴𝐴 ≤𝜆𝜆𝑚𝑚𝑚𝑚𝑚𝑚 − 𝜆𝜆𝑚𝑚𝑚𝑚𝑚𝑚
𝜆𝜆𝑚𝑚𝑚𝑚𝑚𝑚 + 𝜆𝜆𝑚𝑚𝑚𝑚𝑚𝑚

𝑥𝑥𝑘𝑘 − 𝑥𝑥 ∗ 𝐴𝐴

𝜆𝜆𝑚𝑚𝑚𝑚𝑚𝑚 ≫ 𝜆𝜆𝑚𝑚𝑚𝑚𝑚𝑚 の時に収束が非常に遅くなる

ただし， 𝜆𝜆𝑚𝑚𝑚𝑚𝑚𝑚 と𝜆𝜆𝑚𝑚𝑚𝑚𝑚𝑚 は𝑄𝑄 の最大固有値と最小固有値であり， 𝑥𝑥 𝐴𝐴 =ある．

2023/8/8

COSS2023

𝑥𝑥 ⊤𝑄𝑄𝑄𝑄 で20

点列の挙動(最急降下法)

2023/8/8

COSS202321

点列の挙動(準ニュートン法)

2023/8/8

COSS2023

22

Nesterovの加速法
1.
2.
3.
4.
5.
6.

•

初期点 𝑥𝑥0 ∈ 𝑅𝑅 𝑛𝑛 を与える． 𝑘𝑘 = 0 , 𝑧𝑧0 = 𝑥𝑥0, 𝜏𝜏0 = 0, として，ステップ 2へ.
終了判定を行う．
1
𝐿𝐿

𝑥𝑥𝑘𝑘+1 = 𝑧𝑧𝑘𝑘 − ∇𝑓𝑓 𝑧𝑧𝑘𝑘
𝜏𝜏𝑘𝑘+1 =12(定数ステップサイズの最急降下法)

1 + 1 + 4𝜏𝜏𝑘𝑘2
𝜏𝜏 −1𝜏𝜏𝑘𝑘+1

𝑧𝑧𝑘𝑘+1 = 𝑥𝑥𝑘𝑘+1 + 𝑘𝑘

𝑥𝑥𝑘𝑘+1 − 𝑥𝑥𝑘𝑘

𝑘𝑘 ← 𝑘𝑘 + 1 としてステップ 2. に戻る．

𝑓𝑓 が𝐿𝐿-平滑な凸関数のとき
𝑓𝑓 𝑥𝑥𝑘𝑘 − 𝑓𝑓 𝑥𝑥

2023/8/8∗

1= 𝑂𝑂 2
𝑘𝑘

𝑥𝑥𝑘𝑘
𝑧𝑧𝑘𝑘

−𝛻𝛻𝑓𝑓(𝑧𝑧𝑘𝑘 )COSS2023

𝑥𝑥𝑘𝑘+1

𝑧𝑧𝑘𝑘+123

ニュートン法
ニュートン法: 目的関数の2次近似を最小にする方向を選択
12次近似 : 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝑑𝑑 ≈ 𝑞𝑞 𝑑𝑑 = 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑 + 𝑑𝑑⊤ 𝛻𝛻2 𝑓𝑓 𝑥𝑥𝑘𝑘 𝑑𝑑
2

ヘッセ行列 𝛻𝛻 2 𝑓𝑓 𝑥𝑥𝑘𝑘 が正定値対称であると仮定すると, 𝛻𝛻𝑑𝑑 𝑞𝑞 𝑑𝑑 = 0 を考えればよいので

𝛻𝛻𝑑𝑑 𝑞𝑞 𝑑𝑑 = 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛻𝛻2 𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑 = 0

ニュートン方向𝛻𝛻 2 𝑓𝑓 𝑥𝑥𝑘𝑘 𝑑𝑑𝑘𝑘 = −𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 , または 𝑑𝑑𝑘𝑘 = −𝛻𝛻 2 𝑓𝑓 𝑥𝑥𝑘𝑘 −1 𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )2次近似の等高線•••

局所的に2次収束する
降下方向を生成するとは限らない
ヘッセ行列（2回偏微分）を計算する必要がある

2023/8/8

COSS2023

𝑥𝑥𝑘𝑘

𝑑𝑑𝑘𝑘

24

準ニュートン法
準ニュートン法: ニュートン法のヘッセ行列を近似行列で置き換えた方法
準ニュートン法

𝐵𝐵𝑘𝑘 𝑑𝑑𝑘𝑘 = −𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 または 𝑑𝑑𝑘𝑘 = −𝐻𝐻𝑘𝑘 𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )ただし，𝐵𝐵𝑘𝑘 ≈ 𝛻𝛻 2 𝑓𝑓 𝑥𝑥𝑘𝑘 , 𝐻𝐻𝑘𝑘 = 𝐵𝐵𝑘𝑘−1

𝐵𝐵𝑘𝑘 , 𝐻𝐻𝑘𝑘 は正定値対称であることが望ましい

𝐵𝐵𝑘𝑘 が正定値対称であるならば，𝐻𝐻𝑘𝑘 も正定値対称であり，∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘 = −∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝐻𝐻𝑘𝑘 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 < 0となるので，降下方向を生成する．
2023/8/8

COSS2023

25

準ニュートン法定理
直線探索でWolfe条件を用いた準ニュートン法を考える．ズーテンダ
イク条件と同様の仮定が成り立っており，さらに，正の定数𝑀𝑀, 𝑚𝑚が存在して，すべての𝑘𝑘に対して
𝑚𝑚 𝑣𝑣

2

≤ 𝑣𝑣 ⊤𝐻𝐻𝑘𝑘 𝑣𝑣 ≤ 𝑀𝑀 𝑣𝑣

2∀𝑣𝑣 ∈ 𝑅𝑅 𝑛𝑛が成立するならば，準ニュートン法は liminf ∇𝑓𝑓 𝑥𝑥𝑘𝑘
𝑘𝑘→∞
収束する．

= 0 の意味で大域的に• 十分な降下条件： ∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘 = −∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤ 𝐻𝐻𝑘𝑘 ∇𝑓𝑓 𝑥𝑥𝑘𝑘 ≤ −𝑚𝑚 ∇𝑓𝑓 𝑥𝑥𝑘𝑘
• 探索方向の有界性： 𝑑𝑑𝑘𝑘

2023/8/8≤ −𝐻𝐻𝑘𝑘 ∇𝑓𝑓 𝑥𝑥𝑘𝑘

COSS2023≤ 𝐻𝐻𝑘𝑘∇𝑓𝑓 𝑥𝑥𝑘𝑘

2≤ 𝑀𝑀 ∇𝑓𝑓 𝑥𝑥𝑘𝑘

26

準ニュートン法の収束率
定理 (Dennis-Moré条件)
目的関数 𝑓𝑓 は2回連続微分可能であるとする．点列 𝑥𝑥𝑘𝑘 は
𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 − 𝐵𝐵𝑘𝑘−1∇𝑓𝑓 𝑥𝑥𝑘𝑘

で生成され，さらに2次の十分条件を満たす局所最適化 𝑥𝑥 ∗ に収束する
ものと仮定する．このとき，𝐵𝐵𝑘𝑘 が
lim

𝑘𝑘→∞

𝐵𝐵𝑘𝑘 − ∇2 𝑓𝑓 𝑥𝑥𝑘𝑘

𝑥𝑥𝑘𝑘+1 − 𝑥𝑥𝑘𝑘

𝑥𝑥𝑘𝑘+1 − 𝑥𝑥𝑘𝑘=0を満たすならば，点列 𝑥𝑥𝑘𝑘 の収束率は超一次である．

2023/8/8

COSS202327近似行列の選択とセカント条件
近似行列𝐵𝐵𝑘𝑘 の選択

𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 ) の1次近似を考えると, 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘 ≈ 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘+1 − 𝛻𝛻 2 𝑓𝑓(𝑥𝑥𝑘𝑘+1 )(𝑥𝑥𝑘𝑘+1 − 𝑥𝑥𝑘𝑘 )𝛻𝛻2 𝑓𝑓 𝑥𝑥𝑘𝑘+1 𝑥𝑥𝑘𝑘+1 − 𝑥𝑥𝑘𝑘 ≈ 𝛻𝛻𝑓𝑓 𝑥𝑥𝑘𝑘+1 − 𝛻𝛻𝑓𝑓(𝑥𝑥𝑘𝑘 )= 𝑠𝑠𝑘𝑘セカント条件 (近似行列が満たすべき条件)
𝐵𝐵𝑘𝑘+1 𝑠𝑠𝑘𝑘 = 𝑦𝑦𝑘𝑘 ,セカント条件を満たす更新公式= 𝑦𝑦𝑘𝑘または 𝑠𝑠𝑘𝑘 = 𝐻𝐻𝑘𝑘+1 𝑦𝑦𝑘𝑘

BFGS(Broyden-Fletcher-Goldfarb-Shanno) 公式
𝐵𝐵𝑘𝑘 𝑠𝑠𝑘𝑘 𝑠𝑠𝑘𝑘⊤ 𝐵𝐵𝑘𝑘 𝑦𝑦𝑘𝑘 𝑦𝑦𝑘𝑘⊤
𝐵𝐵𝑘𝑘+1 = 𝐵𝐵𝑘𝑘 − ⊤+ ⊤𝑠𝑠𝑘𝑘 𝐵𝐵𝑘𝑘 𝑠𝑠𝑘𝑘
𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘•••

2023/8/8

𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘⊤
𝑦𝑦𝑘𝑘 𝑠𝑠𝑘𝑘⊤
𝑠𝑠𝑘𝑘 𝑠𝑠𝑘𝑘⊤
𝐻𝐻 𝐼𝐼 − ⊤+ ⊤𝐻𝐻𝑘𝑘+1 = 𝐼𝐼 − ⊤𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘 𝑘𝑘
𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘
𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘

もっともよく知られた更新公式で様々なソフトウェアでも使用されている
Wolfe条件のもとで正定値性が保証される
適当な仮定の下，超一次収束性が保証される
COSS2023

28

その他の更新公式
DFP(Davidon-Fletcher-Powell) 公式:
𝑦𝑦𝑘𝑘 𝑠𝑠𝑘𝑘⊤
𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘⊤
𝑦𝑦𝑘𝑘 𝑦𝑦𝑘𝑘⊤
𝐵𝐵𝑘𝑘+1 = 𝐼𝐼 − ⊤𝐵𝐵 𝐼𝐼 − ⊤+ ⊤𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘 𝑘𝑘
𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘
𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘

𝐻𝐻𝑘𝑘 𝑦𝑦𝑘𝑘 𝑦𝑦𝑘𝑘⊤ 𝐻𝐻𝑘𝑘 𝑠𝑠𝑘𝑘 𝑠𝑠𝑘𝑘⊤+ ⊤𝐻𝐻𝑘𝑘+1 = 𝐻𝐻𝑘𝑘 − ⊤𝑦𝑦𝑘𝑘 𝐻𝐻𝑘𝑘 𝑦𝑦𝑘𝑘
𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘

SR1(Symmetric Rank one) 公式:
𝑦𝑦𝑘𝑘 − 𝐵𝐵𝑘𝑘 𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘 − 𝐵𝐵𝑘𝑘 𝑠𝑠𝑘𝑘 ⊤𝐵𝐵𝑘𝑘+1 = 𝐵𝐵𝑘𝑘 +𝑦𝑦𝑘𝑘 − 𝐵𝐵𝑘𝑘 𝑠𝑠𝑘𝑘 ⊤ 𝑠𝑠𝑘𝑘

𝑠𝑠𝑘𝑘 − 𝐻𝐻𝑘𝑘 𝑦𝑦𝑘𝑘 𝑠𝑠𝑘𝑘 − 𝐻𝐻𝑘𝑘 𝑦𝑦𝑘𝑘 ⊤𝐻𝐻𝑘𝑘+1 = 𝐻𝐻𝑘𝑘 +𝑠𝑠𝑘𝑘 − 𝐻𝐻𝑘𝑘 𝑦𝑦𝑘𝑘 ⊤𝑦𝑦𝑘𝑘

•
•

•
•

2023/8/8

歴史的に最も古い更新公式の一つ
効率的にはBFGS公式のほうが有用紹介した中では唯一の1ランクの更新公式
必ずしも正定値対称行列になるとは限らない

COSS2023

29

その他の更新公式
Broyden公式族:
𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵

𝐵𝐵𝑘𝑘+1
•
•

•

𝜙𝜙𝑘𝑘
𝜃𝜃𝑘𝑘
2023/8/8

𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐷𝐷𝐷𝐷𝐷𝐷= (1 − 𝜙𝜙𝑘𝑘 )𝐵𝐵𝑘𝑘+1+ 𝜙𝜙𝑘𝑘 𝐵𝐵𝑘𝑘+1

𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏

𝐻𝐻𝑘𝑘+1

𝐷𝐷𝐷𝐷𝐷𝐷𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵= (1 − 𝜃𝜃𝑘𝑘 )𝐵𝐵𝑘𝑘+1+ 𝜃𝜃𝑘𝑘 𝐵𝐵𝑘𝑘+1

BFGS公式とDFP公式の線形結合
𝜙𝜙𝑘𝑘 ∈ 0,1 を凸結合族， 𝜙𝜙𝑘𝑘 ∈ 𝜙𝜙𝑘𝑘∗ , 0 をプレコンベックスクラスと呼ぶ．
𝜙𝜙𝑘𝑘 =

𝑠𝑠𝑘𝑘⊤ 𝑦𝑦𝑘𝑘とおくとSR1公式に帰着
𝑦𝑦𝑘𝑘 −𝐵𝐵𝑘𝑘𝑠𝑠𝑘𝑘 ⊤𝑠𝑠𝑘𝑘

プレコンベックス
クラス
𝜙𝜙𝑘𝑘∗

0

B公式

凸結合族

凸結合族
COSS2023

1

プレコンベックス
クラス

+∞
H公式

30

数値例
Ex. Rosenblock関数での実験例
100

10000

1000001000000

反復回数 実行時間 反復回数 実行時間 反復回数 実行時間 反復回数 実行時間
Newton法

305

0.09

305

98.64

memory overmemory over

BFGS法(H公式)

27

0

35

91.17

memory overmemory over

CG-HS+法

58

0

26

0.16

67

3.58

36

7.39

加速付き最急降下法

235

0.02

237

0.67

237

2.33

247

14.72

非単調BB法

68

0

68

0

68

0.52

68

3.98

2023/8/8

COSS2023

31

目次• 第1部（10:00～11:00）• 無制約最適化の基礎• 反復法• 直線探索• 最急勾配法，ニュートン法，準ニュートン法• 第2部（11:15～12:15）• 大規模無制約最適化問題に対する反復法• 記憶制限準ニュートン法，BB法• 非線形共役勾配法• メモリーレス準ニュートン法• 第3部（13:25～14:25）• 微分不可能な正則化項を含む問題への拡張• 近接勾配法• ニュートン型近接勾配法

2023/8/8

COSS2023

32

大規模無制約最適化問題の解法
いかにして大規模問題に適応させるか？
ヘッセ行列の疎性を利用する
信頼領域法＋ニュートン法スパース準ニュートン法

行列を陽には使用しない
記憶制限準ニュートン法
Barzilai-Borwein法
非線形共役勾配法
メモリーレス準ニュートン法
2023/8/8

COSS202333

記憶制限準ニュートン法
逆行列版BFGS公式

2023/8/8

COSS2023

34

Barzilai-Borwein(BB)法
注意：以降では, しばらくの間

𝑔𝑔 = ∇𝑓𝑓 , 𝑔𝑔𝑘𝑘 = ∇𝑓𝑓(𝑥𝑥𝑘𝑘 ) と表記する

準Newton法

Barzilai-Borwein法

更新式
セカント条件

2023/8/8

COSS202335非線形共役勾配法
線形共役勾配法

非線形共役勾配法
一般の非線形関数最小化問題を解く方法

2023/8/8

COSS202336線形共役勾配法（前準備）緩和法（軸探索法）
楕円の場合

2023/8/8

COSS202337共役方向法（共役性とは？）1次変換された空間での直行性

2023/8/8

元の空間

COSS202338共役方向法の収束性

2023/8/8

COSS202339

(線形)共役勾配法のアルゴリズム

2023/8/8

COSS202340非線形共役勾配法のアルゴリズム

2023/8/8

COSS202341非線形共役勾配法(CG法)• Fretcher-Reevs (1964)• Polak-Ribiére (1969)• Hestenes-Stiefel (1952)• Dai-Yuan (1999)
2023/8/8

COSS202342

DY法の収束性の概要

1.

2

𝑔𝑔𝑘𝑘
𝐷𝐷𝐷𝐷
𝛽𝛽𝑘𝑘 = ⊤𝑑𝑑𝑘𝑘−1 𝑦𝑦𝑘𝑘−1

𝑑𝑑𝑘𝑘 = −𝑔𝑔𝑘𝑘 + 𝛽𝛽𝑘𝑘𝐷𝐷𝐷𝐷 𝑑𝑑𝑘𝑘−1 ,⊤𝑔𝑔𝑘𝑘⊤ 𝑑𝑑𝑘𝑘 = 𝛽𝛽𝑘𝑘𝐷𝐷𝐷𝐷 𝑔𝑔𝑘𝑘−1
𝑑𝑑𝑘𝑘−1 < 0 𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎𝑎𝑎𝑎𝑎 𝑘𝑘 ≥ 1 を示す

⊤

𝑔𝑔 𝑑𝑑
降下方向を生成することと，𝛽𝛽𝑘𝑘𝐷𝐷𝐷𝐷 = ⊤ 𝑘𝑘 𝑘𝑘𝑔𝑔𝑑𝑑

𝑘𝑘−1 𝑘𝑘−1= 0 を示す．

2. Zoutendjik条件を用いてliminf 𝑔𝑔𝑘𝑘𝑘𝑘→∞

𝛽𝛽𝑘𝑘𝐷𝐷𝐷𝐷 𝑑𝑑𝑘𝑘−1 = 𝑔𝑔𝑘𝑘 + 𝑑𝑑𝑘𝑘 より
𝑑𝑑𝑘𝑘

2023/8/8

𝛽𝛽𝑘𝑘𝐷𝐷𝐷𝐷 𝑑𝑑𝑘𝑘−1
2

2 ≤⊤𝑔𝑔𝑘𝑘 𝑑𝑑𝑘𝑘

2𝑑𝑑𝑘𝑘−1= 𝑔𝑔𝑘𝑘2

2⊤
𝑔𝑔𝑘𝑘−1𝑑𝑑𝑘𝑘−1

を得る+

COSS20232+ 2𝑔𝑔𝑘𝑘⊤ 𝑑𝑑𝑘𝑘 + 𝑑𝑑𝑘𝑘
1

𝑔𝑔𝑘𝑘

2 ≤

𝑑𝑑0

2

2
𝑔𝑔0⊤ 𝑑𝑑0

2
𝑘𝑘

+�
𝑖𝑖=1

1

𝑔𝑔𝑖𝑖

2
43

DY法の収束性の概要
背理法の仮定として， ∃𝜀𝜀 > 0, 𝑠𝑠. 𝑡𝑡. 𝑔𝑔𝑘𝑘 ≥ 𝜀𝜀 𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎𝑎𝑎𝑎𝑎 𝑘𝑘 ≥ 0 を仮定すると，
𝑑𝑑𝑘𝑘

2

𝑘𝑘

2

𝑘𝑘
2 ≤
2 +�
2 ≤ 𝑐𝑐1 + 𝜀𝜀⊤⊤
𝑔𝑔𝑘𝑘 𝑑𝑑𝑘𝑘
𝑔𝑔0 𝑑𝑑0𝑖𝑖=1 𝑔𝑔𝑖𝑖となり, Zoutenjdik 条件

2023/8/8

𝑑𝑑0∇𝑓𝑓 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘
∑∞
2
𝑘𝑘=0
𝑑𝑑
𝑘𝑘

2

1

< ∞ に反する □COSS2023

44

HS+法の証明の概要
Property*
正の定数𝛾𝛾1 , 𝛾𝛾2 が存在して，すべての𝑘𝑘に対して 𝛾𝛾1 ≤ ∇𝑓𝑓 𝑥𝑥𝑘𝑘
立していると仮定する. このとき, すべての𝑘𝑘に対し,|𝛽𝛽𝑘𝑘 | ≤ 𝑏𝑏,

𝑎𝑎𝑎𝑎𝑎𝑎𝑠𝑠𝑘𝑘−1≤ 𝛾𝛾2 が成1
≤ 𝜂𝜂 → |𝛽𝛽𝑘𝑘 | ≤𝑏𝑏を満たす定数 𝑏𝑏 > 1 と 𝜂𝜂 > 0 が存在するとき，共役勾配法はProperty*を満たすという．

定理
Zoutendjik条件と同様の仮定が成り立っているとする．このとき，以下の条件を満たすCG法は liminf 𝑔𝑔𝑘𝑘 = 0 の意味で大域的に収束する．
𝑘𝑘→∞

1. 𝛽𝛽𝑘𝑘 ≥ 0 𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎𝑎𝑎𝑎𝑎 𝑘𝑘 ≥ 1
2. 十分な降下条件を満たす
3. Property* を満たす

2023/8/8

COSS2023

45

HS+法の証明の概要
𝛽𝛽𝑘𝑘𝐻𝐻𝐻𝐻+ = max

𝑔𝑔𝑘𝑘⊤ 𝑦𝑦𝑘𝑘−1
0, ⊤𝑑𝑑𝑘𝑘−1 𝑦𝑦𝑘𝑘−1

1. 十分な降下条件は仮定とする（必ずしも満たされるとはかぎらない）．
2. Property* を満たすことを示す．
Property*を満たすことを確認するには，∃𝑐𝑐 > 0,𝑠𝑠. 𝑡𝑡. 𝛽𝛽𝑘𝑘 ≤ 𝑐𝑐 𝑠𝑠𝑘𝑘−1
を確認すれば十分．

2023/8/8

COSS202346非線形共役勾配法の発展
1.

曲率の情報を取り込むためにセカント条件を利用した方法

Dai and Liao (2001)、Yabe and Takano (2003)、
Zhou and Zhang (2006)、Ford, Narushima and Yabe (2007) など

2.

直線探索に依存せずに降下方向を生成する方法
 パラメータβの修正Hager and Zhang (2005)、Yu, Guan and Chen (2008)、Yu, Guan and Li(2008)、Dai
and Kou(2013)

スケーリング／3項共役勾配法

Zhang, Zhou and Li （2006，2006，2007）、Cheng （2006）、
Narushima, Yabe and Ford （2011）、Al-Baali, Narushima and Yabe(2015)


3.

その他
 ハイブリッド法


部分空間最小化法との組み合わせ

Hager and Zhang(2013)(通常の意味での)無制約最適化問題以外への拡張2023/8/8

Chen and Liu(2010)、Narushima and Yabe(2012)、Sugiki, Narushima andYabe(2012)

多様体上の最適化問題への拡張(Sato and Iwai2015, Sato 2016, Sakai and Iiduka 2020など）
不動点制約付き問題への拡張(Iiduka2008など)
COSS202347

3項共役勾配法(N, Yabe and Ford 2011)

2023/8/8

COSS202348

3項共役勾配法
スケーリングCG法

2023/8/8

COSS202349非線形共役勾配法の探索方向

2023/8/8

COSS202350非線形共役勾配法の探索方向

2023/8/8

COSS2023

51大規模無制約最適化問題の解法
いかにして大規模問題に適応させるか？
ヘッセ行列の疎性を利用する
信頼領域法＋ニュートン法スパース準ニュートン法

行列を陽には使用しない
記憶制限準ニュートン法
Barzilai-Borwein法
非線形共役勾配法
メモリーレス準ニュートン法
2023/8/8

COSS202352

記憶制限準ニュートン法（再掲）
逆行列版BFGS公式

2023/8/8

COSS202353

メモリーレス準ニュートン法
準ニュートン法(逆行列版)

BFGS公式

2023/8/8

COSS202354

メモリーレス準ニュートン法

 ある種の3項共役勾配法としてとらえられるとなるため，非線形共役勾配法(HS公式)に一致する．

2023/8/8

COSS202355

メモリーレス準ニュートン法と三項共役勾配法の比較
メモリーレス準ニュートン法(BFGS公式の例)
𝑑𝑑𝑘𝑘 = −𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘⊤
𝐼𝐼 − ⊤
𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘

𝑦𝑦𝑘𝑘 𝑠𝑠𝑘𝑘⊤
𝑠𝑠𝑘𝑘 𝑠𝑠𝑘𝑘⊤
𝐼𝐼 − ⊤+ ⊤𝑔𝑔
𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘
𝑠𝑠𝑘𝑘 𝑦𝑦𝑘𝑘 𝑘𝑘=𝐻𝐻𝑘𝑘• 𝑠𝑠𝑘𝑘⊤ 𝑦𝑦𝑘𝑘 > 0 ならば正定値対称• セカント条件を満たしている

三項共役勾配法(HS公式，𝑝𝑝𝑘𝑘 = 𝑦𝑦𝑘𝑘−1の場合)⊤⊤
𝑔𝑔𝑘𝑘⊤ 𝑦𝑦𝑘𝑘−1
𝑔𝑔𝑘𝑘⊤ 𝑦𝑦𝑘𝑘−1 𝑔𝑔𝑘𝑘⊤ 𝑑𝑑𝑘𝑘−1
𝑑𝑑𝑘𝑘−1 𝑦𝑦𝑘𝑘−1
𝑦𝑦𝑘𝑘−1 𝑑𝑑𝑘𝑘−1
𝑑𝑑𝑘𝑘 = −𝑔𝑔𝑘𝑘 + ⊤
𝑑𝑑
− ⊤
𝑦𝑦
= − 𝐼𝐼 + ⊤− ⊤𝑔𝑔
𝑑𝑑𝑘𝑘−1 𝑦𝑦𝑘𝑘−1 𝑘𝑘−1 𝑑𝑑𝑘𝑘−1
𝑦𝑦𝑘𝑘−1 𝑔𝑔𝑘𝑘⊤ 𝑦𝑦𝑘𝑘−1 𝑘𝑘−1
𝑑𝑑𝑘𝑘−1 𝑦𝑦𝑘𝑘−1 𝑑𝑑𝑘𝑘−1
𝑦𝑦𝑘𝑘−1 𝑘𝑘• 対称性，正定値性，セカント条件などは考慮していない

2023/8/8

COSS2023

=𝐻𝐻𝑘𝑘

56

メモリーレス準ニュートン法の特徴
情報の量
準ニュートン法

記憶制限
準ニュートン法

メモリーレス
準ニュートン法

探索方向の計算に必要な計算量
準ニュートン法•

メモリーレス
準ニュートン法

非線形
共役勾配法

非線形
共役勾配法

記憶制限準ニュートン法と比較すると
•

•

記憶制限
準ニュートン法?
≈

BFGS公式以外でも簡単に探索方向を考える事ができる

非線形共役勾配法や三項共役勾配法と比較すると•対称性を持つので正定値になるように選べば計量として使用可能
 無制約以外の問題に拡張しやすい

2023/8/8

COSS202357

メモリーレス準ニュートン法の研究• 最初のメモリーレス準ニュートン法• Shanno(1978)• BFGS公式に基づくメモリーレス準ニュートン法• Kou and Dai (2015)• SR1公式に基づくメモリーレス準ニュートン法• Moyi and Leong (2016), Nakayama et al. (2018)• ブロイデン公式族に基づくメモリーレス準ニュートン法• Nakayama N. and Yabe (2019), Nakayama (2018)• その他• 上下限制約付き問題への拡張（有効制約法） Nakayama et al.
(2021)• 多様体上の最適化問題に対する拡張 N. et al. (2023)• 微分不可能な関数を含む最適化問題に対する拡張 Becker et al.
(2019), Nakayama et al.(2021), N. and Nakayama (2023) など
2023/8/8

COSS2023

58

Nakayama N. and Yabe (2019)の概要
通常の（BFGS公式に基づいた）メモリーレス準ニュートン法

セカント条件自体を修正

2023/8/8

COSS2023

59

Nakayama N. and Yabe (2019)の概要
2次近似

微分して
𝑥𝑥 = 𝑥𝑥𝑘𝑘−1

スペクトラルスケーリング(SS)セカント条件(Cheng and Li (2010))

𝐵𝐵𝑘𝑘 𝑠𝑠𝑘𝑘−1 = 𝛾𝛾𝑘𝑘−1 𝑦𝑦𝑘𝑘−1 または 𝑠𝑠𝑘𝑘−1 = 𝛾𝛾𝑘𝑘−1 𝐻𝐻𝑘𝑘 𝑦𝑦𝑘𝑘−1

SSセカント条件に基づくメモリーレスBFGS法(実際にはBroyden族を提案)

2023/8/8

COSS202360

メモリーレス準ニュートン法の数値実験例••

CUTEr問題集から138問を選択して実験
実験の詳細は以下を参照

2023/8/8「無制約最適化問題に対するメモリーレス準ニュートン法について」, 応用数理, 29 (2019), 8-17

COSS202361修正メモリーレス準ニュートン法
修正メモリーレス準ニュートン法(修正mless-BFGS公式)⊤⊤
𝑠𝑠𝑘𝑘−1 𝑠𝑠𝑘𝑘−1
𝑧𝑧𝑘𝑘−1 𝑧𝑧𝑘𝑘−1
𝐵𝐵𝑘𝑘 = 𝐼𝐼 − ⊤+ ⊤𝑠𝑠𝑘𝑘−1 𝑠𝑠𝑘𝑘−1 𝑠𝑠𝑘𝑘−1
𝑧𝑧𝑘𝑘−1

𝐻𝐻𝑘𝑘 =⊤
𝑠𝑠𝑘𝑘−1 𝑧𝑧𝑘𝑘−1
𝐼𝐼 − ⊤
𝑠𝑠𝑘𝑘−1 𝑧𝑧𝑘𝑘−1⊤
𝑧𝑧𝑘𝑘−1 𝑠𝑠𝑘𝑘−1
𝐼𝐼 − ⊤
𝑠𝑠𝑘𝑘−1 𝑧𝑧𝑘𝑘−1

ただし, 𝑧𝑧𝑘𝑘−1 は•⊤• 𝑠𝑠𝑘𝑘−1
𝑧𝑧𝑘𝑘−1 ≥ 𝑐𝑐2 𝑠𝑠𝑘𝑘−1を満たすベクトル⊤𝑠𝑠𝑘𝑘−1 𝑠𝑠𝑘𝑘−1+ ⊤𝑠𝑠𝑘𝑘−1 𝑧𝑧𝑘𝑘−1

上記の 𝐵𝐵𝑘𝑘 の固有値は 1 (重複度 𝑛𝑛 − 2) と⊤𝑠𝑠𝑧𝑧𝑘𝑘−1𝑘𝑘−1,
𝜆𝜆̅ 𝑘𝑘 + 𝜆𝜆̅ 2𝑘𝑘 − 4 ⊤2𝑠𝑠𝑘𝑘−1 𝑠𝑠𝑘𝑘−1

1
𝜆𝜆+
=
𝑘𝑘

1
𝜆𝜆−𝑘𝑘 =⊤𝑧𝑧𝑧𝑧である. ただし，𝜆𝜆̅ 𝑘𝑘 = 1 + ⊤𝑘𝑘−1 𝑘𝑘−1 とする．

𝑧𝑧𝑘𝑘−1 ≤ 𝑐𝑐1 𝑠𝑠𝑘𝑘−12

𝜆𝜆̅ 2𝑘𝑘 −2⊤
𝑠𝑠𝑘𝑘−1𝑧𝑧𝑘𝑘−1,
𝜆𝜆̅ 𝑘𝑘 − 4 ⊤𝑠𝑠𝑘𝑘−1𝑠𝑠𝑘𝑘−1

𝑠𝑠𝑘𝑘−1 𝑧𝑧𝑘𝑘−1

2023/8/8

COSS202362修正メモリーレス準ニュートン法
補題 正の定数 𝑚𝑚, 𝑀𝑀 が存在して, すべての𝑘𝑘 ≥ 1に対して，が成立する．

𝑚𝑚 ≤ 𝜆𝜆−𝑘𝑘 ≤ 𝜆𝜆+𝑘𝑘 ≤ 𝑀𝑀

𝑚𝑚 𝑣𝑣

2

≤ 𝑣𝑣 ⊤𝐵𝐵𝑘𝑘 𝑣𝑣 ≤ 𝑀𝑀 𝑣𝑣

2

𝑓𝑓𝑓𝑓𝑓𝑓 ∀𝑣𝑣 ∈ 𝑅𝑅 𝑛𝑛 を意味する

定理 ズーテンダイク条件と同様の仮定が成り立っているとする．このとき，
直線探索でWolfe条件を用いた修正mless-BFGS法は liminf ∇𝑓𝑓 𝑥𝑥𝑘𝑘 = 0 の意
𝑘𝑘→∞
味で大域的に収束する．

2023/8/8

COSS2023

63

目次• 第1部（10:00～11:00）• 無制約最適化の基礎• 反復法• 直線探索• 最急勾配法，ニュートン法，準ニュートン法• 第2部（11:15～12:15）• 大規模無制約最適化問題に対する反復法• 記憶制限準ニュートン法，BB法• 非線形共役勾配法• メモリーレス準ニュートン法• 第3部（13:25～14:25）• 微分不可能な正則化項を含む問題への拡張• 近接勾配法• ニュートン型近接勾配法

2023/8/8

COSS2023

64正則化項付き最適化問題
min 𝑓𝑓 𝑥𝑥 = 𝑔𝑔 𝑥𝑥 + ℎ 𝑥𝑥
𝑥𝑥

𝑔𝑔: 𝑅𝑅 𝑛𝑛 → 𝑅𝑅, 𝐿𝐿-平滑な関数ℎ: 𝑅𝑅 𝑛𝑛 → 𝑅𝑅 ∪ +∞ , 真凸関数だが微分可能とは限らない＊前半と𝑔𝑔の定義が異なることに注意

LASSO（least absolute shrinkage and selection operator）

min 𝐴𝐴𝐴𝐴 − 𝑏𝑏2

+ 𝜆𝜆 𝑥𝑥 1

最小２乗問題＋ℓ1 正則化

凸最適化問題(指示関数)

min

Subject to2023/8/8

𝑔𝑔 𝑥𝑥

𝑥𝑥 ∈ 𝑆𝑆 (𝑆𝑆 は凸集合)
COSS2023

min 𝑔𝑔 𝑥𝑥 + 𝛿𝛿𝑆𝑆 (𝑥𝑥)ただし，0𝑥𝑥 ∈ 𝑆𝑆𝛿𝛿𝑆𝑆 𝑥𝑥 = �+∞ 𝑥𝑥 ∈ 𝑆𝑆

65

LASSOのイメージ
最小化
最小化
制約条件

目的関数の等高線
左図の例
最小化
制約条件

2023/8/8

COSS2023

実行可能領域66

正則化項付き最適化問題
min 𝑓𝑓 𝑥𝑥 = 𝑔𝑔 𝑥𝑥 + ℎ 𝑥𝑥
𝑥𝑥

𝑔𝑔: 𝑅𝑅 𝑛𝑛 → 𝑅𝑅, 𝐿𝐿-平滑な関数ℎ: 𝑅𝑅 𝑛𝑛 → 𝑅𝑅 ∪ +∞ , 真凸関数だが微分可能とは限らない
𝑦𝑦 = ℎ 𝑥𝑥

1次の最適性条件

0 ∈ ∇𝑔𝑔 𝑥𝑥 + 𝜕𝜕𝜕 𝑥𝑥

ただし， 𝜕𝜕𝜕 𝑥𝑥 は凸関数 ℎ の劣微分とする．

𝜕𝜕𝜕 𝑥𝑥 = 𝜉𝜉 | ℎ 𝑦𝑦 ≥ ℎ 𝑥𝑥 + 𝜉𝜉 ⊤ 𝑦𝑦 − 𝑥𝑥 𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎𝑎𝑎𝑎𝑎 𝑦𝑦 ∈ 𝑅𝑅 𝑛𝑛

1次の最適性条件を満たす点を以下では停留点と呼ぶ．

2023/8/8

COSS2023

67

近接写像
近接写像
Proxℎ 𝑧𝑧 = argmin𝑥𝑥ℓ1 正則化 (ℎ 𝑥𝑥 = 𝜆𝜆 𝑥𝑥 1 , 𝜆𝜆 > 0) の場合•

𝑧𝑧𝑖𝑖 − 𝜆𝜆Prox ℎ 𝑧𝑧 𝑖𝑖 = � 0𝑧𝑧𝑖𝑖 + 𝜆𝜆•

12ℎ 𝑥𝑥 +𝑥𝑥 − 𝑧𝑧2

𝑧𝑧𝑖𝑖 ≥ 𝜆𝜆−𝜆𝜆 ≤ 𝑧𝑧𝑖𝑖 ≤ 𝜆𝜆𝑧𝑧𝑖𝑖 ≤ 𝜆𝜆−𝜆𝜆𝜆𝜆

指示関数 (ℎ 𝑥𝑥 = 𝛿𝛿𝑆𝑆 𝑥𝑥 , 𝑆𝑆は凸集合) の場合
Proxℎ 𝑧𝑧 = argmin𝑥𝑥∈𝑆𝑆 𝑥𝑥 − 𝑧𝑧

2023/8/8(集合Sへの正射影)

COSS202368近接勾配法
𝑥𝑥𝑘𝑘+1 = argmin𝑥𝑥 𝑔𝑔 𝑥𝑥𝑘𝑘 + ∇𝑔𝑔 𝑥𝑥𝑘𝑘
= argmin𝑥𝑥= Prox 1
𝐿𝐿

•
•
•

ℎ

𝑔𝑔 の1次近似⊤

𝑥𝑥 − 𝑥𝑥𝑘𝑘

𝐿𝐿+ ℎ 𝑥𝑥 +𝑥𝑥 − 𝑥𝑥𝑘𝑘
2

1
1
1ℎ 𝑥𝑥 +𝑥𝑥 − 𝑥𝑥𝑘𝑘 − ∇𝑔𝑔(𝑥𝑥𝑘𝑘 )
𝐿𝐿
2
𝐿𝐿

1
𝑥𝑥𝑘𝑘 − ∇𝑔𝑔 𝑥𝑥𝑘𝑘
𝐿𝐿

最急降下法

2

2

近接項

𝑦𝑦 = 𝑓𝑓(𝑥𝑥)𝑥𝑥𝑘𝑘+1

𝑔𝑔が強凸の場合の収束率は線形収束，凸の場合の収束率は 𝑂𝑂ℎが指示関数の場合は射影勾配法に帰着する

1

𝑘𝑘

𝑥𝑥𝑘𝑘

近接勾配法はISTA (Iterative Shrinkage Thresholding Algorithm)
や Forward-backward splitting algorithmなどとも呼ばれる

2023/8/8

COSS202369

加速付き近接勾配法(FISTA)
1.
2.
3.

初期点 𝑥𝑥0 ∈ 𝑅𝑅 𝑛𝑛 を与える． 𝑘𝑘 = 0 , 𝑧𝑧0 = 𝑥𝑥0, 𝜏𝜏0 = 0, として，ステップ 2へ.
終了判定を行う．

1
𝐿𝐿

𝑥𝑥𝑘𝑘+1 = Proxℎ 𝑧𝑧𝑘𝑘 − ∇𝑔𝑔 𝑧𝑧𝑘𝑘
1
2

1 + 1 + 4𝜏𝜏𝑘𝑘2

4.

𝜏𝜏𝑘𝑘+1 =6.

𝑘𝑘 ← 𝑘𝑘 + 1 としてステップ 2. に戻る．

5.

•

𝜏𝜏 −1
𝜏𝜏𝑘𝑘+1

𝑧𝑧𝑘𝑘+1 = 𝑥𝑥𝑘𝑘+1 + 𝑘𝑘

𝑥𝑥𝑘𝑘+1 − 𝑥𝑥𝑘𝑘

𝑔𝑔 が𝐿𝐿-平滑な凸関数のとき
𝑓𝑓 𝑥𝑥𝑘𝑘 − 𝑓𝑓 𝑥𝑥 ∗ = 𝑂𝑂

2023/8/8

1
𝑘𝑘 2
COSS202370ニュートン型近接勾配法
𝑥𝑥𝑘𝑘+ = argmin𝑥𝑥

𝑔𝑔 𝑥𝑥𝑘𝑘 + ∇𝑔𝑔 𝑥𝑥𝑘𝑘⊤

1
𝑥𝑥 − 𝑥𝑥𝑘𝑘 + ℎ 𝑥𝑥 +𝑥𝑥 − 𝑥𝑥𝑘𝑘2

正定値対称行列に対して
𝑥𝑥 𝐴𝐴 = 𝑥𝑥 ⊤ 𝐴𝐴𝐴𝐴

= argmin𝑥𝑥 𝑔𝑔 𝑥𝑥𝑘𝑘 + ∇𝑔𝑔 𝑥𝑥𝑘𝑘
= argmin𝑥𝑥

𝑔𝑔 の2次近似

𝑥𝑥 − 𝑥𝑥𝑘𝑘

Proxℎ𝐵𝐵 𝑧𝑧= Proxℎ𝐵𝐵 𝑥𝑥𝑘𝑘 − 𝐻𝐻𝑘𝑘 ∇𝑔𝑔 𝑥𝑥𝑘𝑘

(準)ニュートン法

𝐵𝐵𝑘𝑘

重み付き近接項

1+ 𝑥𝑥 − 𝑥𝑥𝑘𝑘 ⊤ 𝐵𝐵𝑘𝑘 𝑥𝑥 − 𝑥𝑥𝑘𝑘 + ℎ 𝑥𝑥
21
ℎ 𝑥𝑥 +𝑥𝑥 − 𝑥𝑥𝑘𝑘 − 𝐵𝐵𝑘𝑘−1∇𝑔𝑔 𝑥𝑥𝑘𝑘
2

𝐻𝐻𝑘𝑘 = 𝐵𝐵𝑘𝑘−1,

2023/8/8

⊤

2

2

𝐵𝐵𝑘𝑘

1
2
= argmin𝑥𝑥 ℎ 𝑥𝑥 +𝑥𝑥 − 𝑧𝑧 𝐵𝐵
2
COSS202371ニュートン型近接勾配法•

Lee, Sun and Saunders (2014)••

Scheinberg and Tang (2016)••

DC関数に対する非厳密ニュートン型近接勾配法

Nakayama and N. (2023)••

メモリーレスブロイデン族に基づく非厳密ニュートン型近接勾配法

Liu and Takeda(2022)••

特殊な場合での重み付き近接写像の計算法＋それを用いた近接SR1法

Nakayama, N., and Yabe (2021)••

セルフコンコーダント関数に対する非厳密ニュートン型近接勾配法

Becker, Fadili and Ochs (2019)••

L1正則化付き問題に対する非厳密ニュートン型近接勾配法

Andersen and Vandenberghe (2017)••

非厳密ニュートン型近接勾配法

Byrd, Nocedal and Oztoprak (2017)••

最初のニュートン型近接勾配法

SR1公式に基づくニュートン型近接勾配法

Nakayama, N., and Yabe, submitted

2023/8/8•

Nakayama et al. (2021)のDC関数への拡張と部分問題の改良
COSS202372

非厳密ニュートン型近接勾配法(Nakayama et al. 2021)
通常のニュートン型近接勾配法の探索方向と問題点••

𝑑𝑑𝑘𝑘 = 𝑥𝑥𝑘𝑘+ − 𝑥𝑥𝑘𝑘

𝐵𝐵

𝑥𝑥𝑘𝑘+ = Proxℎ 𝑘𝑘 𝑥𝑥𝑘𝑘 − 𝐻𝐻𝑘𝑘 ∇𝑔𝑔 𝑥𝑥𝑘𝑘

= argmin ∇𝑔𝑔 𝑥𝑥𝑘𝑘 𝑥𝑥 − 𝑥𝑥𝑘𝑘 +計量であるため正定値対称
密行列の場合は大規模問題
では使用できない1
𝑥𝑥 − 𝑥𝑥𝑘𝑘 ⊤ 𝐵𝐵𝑘𝑘 𝑥𝑥 − 𝑥𝑥𝑘𝑘 + ℎ(𝑥𝑥)2𝑥𝑥
重み付き近接写像の計算に元の問題と同じ次元・構造の2次最適化問題を解く必要がある．

•

重み付き近接写像を近似的に解く•

近似行列 𝐵𝐵𝑘𝑘 , 𝐻𝐻𝑘𝑘 をメモリーレス準ニュートン法で構築する

2023/8/8

COSS2023

73

非厳密ニュートン型近接勾配法(Nakayama et al. 2021)
𝐵𝐵

𝑥𝑥𝑘𝑘+ = Proxℎ 𝑘𝑘 𝑥𝑥𝑘𝑘 − 𝐻𝐻𝑘𝑘 ∇𝑔𝑔 𝑥𝑥𝑘𝑘
= argmin ∇𝑔𝑔 𝑥𝑥𝑘𝑘
𝑥𝑥

残差の定義
非厳密の基準1
𝑥𝑥 − 𝑥𝑥𝑘𝑘 + 𝑥𝑥 − 𝑥𝑥𝑘𝑘 ⊤ 𝐵𝐵𝑘𝑘 𝑥𝑥 − 𝑥𝑥𝑘𝑘 + ℎ(𝑥𝑥)2部分問題の最適性条件
0 ∈ ∇𝑔𝑔 𝑥𝑥 + 𝐵𝐵𝑘𝑘 𝑥𝑥 − 𝑥𝑥𝑘𝑘 + 𝜕𝜕𝜕 𝑥𝑥

𝑟𝑟𝑘𝑘 ∈ ∇𝑔𝑔 𝑥𝑥𝑘𝑘 + 𝐵𝐵𝑘𝑘 𝑥𝑥𝑘𝑘+ − 𝑥𝑥𝑘𝑘 + 𝜕𝜕𝜕 𝑥𝑥𝑘𝑘+
𝑟𝑟𝑘𝑘

𝐻𝐻𝑘𝑘

𝜃𝜃𝑘𝑘 = 1  厳密に解く≤ 1 − 𝜃𝜃𝑘𝑘

𝑥𝑥𝑘𝑘+ − 𝑥𝑥𝑘𝑘

𝐵𝐵𝑘𝑘

(𝜃𝜃𝑘𝑘 ∈ 𝜃𝜃,̅ 1 , 𝜃𝜃̅ ∈ 0,1 )𝜃𝜃𝑘𝑘 = 𝜃𝜃̅  緩く解く
2023/8/8

COSS202374近似行列の選択
Nakayama et al. (2019)のメモリーレスブロイデン族を修正

元々のSSセカント条件
𝛾𝛾𝑘𝑘−1 ∇2 𝑓𝑓 𝑥𝑥𝑘𝑘 𝑠𝑠𝑘𝑘−1 ≈ 𝛾𝛾𝑘𝑘−1 𝑦𝑦𝑘𝑘−1

修正SSセカント条件

𝐵𝐵𝑘𝑘 𝑠𝑠𝑘𝑘−1 = 𝛾𝛾𝑘𝑘−1𝑦𝑦𝑘𝑘−1

𝛾𝛾𝑘𝑘−1 ∇2 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝜈𝜈𝑘𝑘 𝐼𝐼 𝑠𝑠𝑘𝑘−1 ≈ 𝛾𝛾𝑘𝑘−1 𝑦𝑦𝑘𝑘−1 + 𝜈𝜈𝑘𝑘 𝑠𝑠𝑘𝑘−1= 𝑧𝑧𝑘𝑘−1
𝐵𝐵𝑘𝑘 𝑠𝑠𝑘𝑘−1 = 𝛾𝛾𝑘𝑘−1𝑧𝑧𝑘𝑘−1

修正SSセカント条件に基づくブロイデン族

パラメータを適切に選択すれば，0 < 𝑚𝑚 ≤ 𝑀𝑀 < ∞が存在して,
𝑚𝑚 𝑣𝑣

2

≤ 𝑣𝑣 ⊤ 𝐵𝐵𝑘𝑘 𝑣𝑣 ≤ 𝑀𝑀 𝑣𝑣

2

𝑓𝑓𝑓𝑓𝑓𝑓 ∀𝑣𝑣 ∈ 𝑅𝑅 𝑛𝑛が成立する．(以下はこれを満たす行列を使用していると仮定する)

2023/8/8

COSS202375

アルゴリズム
1. 初期設定：𝑥𝑥0 ∈ 𝑅𝑅 𝑛𝑛 とし，定数 𝛿𝛿, 𝛽𝛽 ∈ 0,1 等のパラメータを与える．
𝑘𝑘 = 0として 2. へ
2. 近似的に以下の最小化問題を解き，探索方向を計算する：
𝑑𝑑𝑘𝑘 = 𝑥𝑥𝑘𝑘+ − 𝑥𝑥𝑘𝑘 ,such that𝑥𝑥𝑘𝑘+ ≈ argmin

𝑟𝑟𝑘𝑘 𝐻𝐻 ≤ 1 − 𝜃𝜃𝑘𝑘
𝑘𝑘

3. 停止判定を行う．
4. 条件∇𝑔𝑔 𝑥𝑥𝑘𝑘 𝑥𝑥 − 𝑥𝑥𝑘𝑘

1+
𝑥𝑥 − 𝑥𝑥𝑘𝑘
2

2

𝐵𝐵𝑘𝑘

+ ℎ(𝑥𝑥)𝑥𝑥𝑘𝑘+ − 𝑥𝑥𝑘𝑘 , 𝑟𝑟𝑘𝑘 ∈ ∇𝑔𝑔 𝑥𝑥𝑘𝑘 + 𝐵𝐵𝑘𝑘 𝑥𝑥𝑘𝑘+ − 𝑥𝑥𝑘𝑘 + 𝜕𝜕𝜕 𝑥𝑥𝑘𝑘+ .

Armijo条件に相当する条件

𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛽𝛽 𝑖𝑖 𝑑𝑑𝑘𝑘 ≤ 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛿𝛿𝛽𝛽 𝑖𝑖 ∇𝑔𝑔 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘 + ℎ 𝑥𝑥𝑘𝑘+ − ℎ 𝑥𝑥𝑘𝑘

5.
2023/8/8を満たす最小の非負定数 𝑖𝑖 を見つけ，𝛼𝛼𝑘𝑘 = 𝛽𝛽 𝑖𝑖 とする．
𝑥𝑥𝑘𝑘+1 = 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑘𝑘 𝑑𝑑𝑘𝑘 , 𝑘𝑘 = 𝑘𝑘 + 1 として，２へ戻る．
COSS202376

直線探索に関する命題
命題

𝛼𝛼 ∈ 0,1 に対して，以下が成立する:

𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑑𝑑𝑘𝑘 ≤ 𝑓𝑓 𝑥𝑥𝑘𝑘

+ 𝛼𝛼 ∇𝑔𝑔 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘 + ℎ 𝑥𝑥𝑘𝑘+∇𝑔𝑔 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘 + ℎ 𝑥𝑥𝑘𝑘+ − ℎ 𝑥𝑥𝑘𝑘 ≤ −𝜃𝜃̅ 𝑑𝑑𝑘𝑘2

− ℎ 𝑥𝑥𝑘𝑘

𝐵𝐵𝑘𝑘

𝛼𝛼 2 𝐿𝐿
+
𝑑𝑑𝑘𝑘
2

2

(A)
(B)

直線探索条件𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛼𝛼𝑘𝑘 𝑑𝑑𝑘𝑘 ≤ 𝑓𝑓 𝑥𝑥𝑘𝑘 + 𝛿𝛿𝛼𝛼𝑘𝑘 ∇𝑔𝑔 𝑥𝑥𝑘𝑘 ⊤ 𝑑𝑑𝑘𝑘 + ℎ 𝑥𝑥𝑘𝑘+ − ℎ 𝑥𝑥𝑘𝑘
≤ −𝜃𝜃̅ 𝑑𝑑𝑘𝑘

2

𝐵𝐵𝑘𝑘

直線探索は実行可能でさらに 𝑓𝑓 𝑥𝑥𝑘𝑘+1 ≤ 𝑓𝑓 𝑥𝑥𝑘𝑘 が成立．
2023/8/8

𝑥𝑥𝑘𝑘 ∈ ℒ 0 = 𝑥𝑥 | 𝑓𝑓 𝑥𝑥 ≤ 𝑓𝑓(𝑥𝑥0 )COSS202377

停留点である条件
命題
ある𝑘𝑘回目の反復において 𝑥𝑥𝑘𝑘 が停留点である必要十分条件は𝑑𝑑𝑘𝑘 = 0

である．

⇒ の証明 省略
⇐ の証明（概略）++
残差の定義 𝑟𝑟𝑘𝑘 ∈ ∇𝑔𝑔 𝑥𝑥𝑘𝑘 + 𝐵𝐵𝑘𝑘 𝑥𝑥𝑘𝑘 − 𝑥𝑥𝑘𝑘 + 𝜕𝜕𝜕 𝑥𝑥𝑘𝑘
非厳密の基準 𝑟𝑟𝑘𝑘
≤ 1 − 𝜃𝜃𝑘𝑘 𝑥𝑥𝑘𝑘+ − 𝑥𝑥𝑘𝑘
(𝜃𝜃𝑘𝑘 ∈ 𝜃𝜃,̅ 1 , 𝜃𝜃̅ ∈ 0,1 )𝐻𝐻𝑘𝑘

𝑑𝑑𝑘𝑘 = 𝑥𝑥𝑘𝑘+ − 𝑥𝑥𝑘𝑘 = 0 より 𝑟𝑟𝑘𝑘 = 02023/8/8

𝐵𝐵𝑘𝑘

COSS20230 ∈ ∇𝑔𝑔 𝑥𝑥𝑘𝑘 + 𝜕𝜕𝜕 𝑥𝑥𝑘𝑘□

78

大域的収束性
補題 以下が成立する：

正の定数定理
目的関数が下で有界であるならば
lim 𝑑𝑑𝑘𝑘𝑘𝑘→∞=0が成立する．さらに， 𝑥𝑥𝑘𝑘 が有界ならば， 𝑥𝑥𝑘𝑘 の任意の集積点は停留点である．

2023/8/8

COSS2023

79

大域的収束性の証明（概略）
直線探索条件より
𝑓𝑓 𝑥𝑥𝑘𝑘+1 − 𝑓𝑓(𝑥𝑥𝑘𝑘 ) ≤ 𝛿𝛿𝛼𝛼𝑘𝑘 ∇𝑔𝑔 𝑥𝑥𝑘𝑘 ⊤𝑑𝑑𝑘𝑘 + ℎ 𝑥𝑥𝑘𝑘+ − ℎ 𝑥𝑥𝑘𝑘2
≤ −𝛿𝛿𝛼𝛼𝑘𝑘 𝜃𝜃̅ 𝑑𝑑𝑘𝑘
𝐵𝐵𝑘𝑘

2
≤ −𝛿𝛿𝛼𝛼� 𝜃𝜃̅ 𝑑𝑑𝑘𝑘 𝐵𝐵

𝑘𝑘2̅≤ −𝛿𝛿𝛼𝛼� 𝜃𝜃𝑚𝑚𝑑𝑑𝑘𝑘
≤0

𝑓𝑓 𝑥𝑥𝑘𝑘 は下に有界な非増加列なので極限が存在する．
よって， lim 𝑑𝑑𝑘𝑘 = 0 が成立する．
𝑘𝑘→∞

残差の定義

非厳密の基準𝑟𝑟𝑘𝑘 ∈ ∇𝑔𝑔 𝑥𝑥𝑘𝑘 + 𝐵𝐵𝑘𝑘 𝑥𝑥𝑘𝑘+ − 𝑥𝑥𝑘𝑘 + 𝜕𝜕𝜕 𝑥𝑥𝑘𝑘+
𝑥𝑥𝑘𝑘+ − 𝑥𝑥𝑘𝑘

𝑟𝑟𝑘𝑘 𝐻𝐻 ≤ 1 − 𝜃𝜃𝑘𝑘
𝑘𝑘

一方，非厳密の基準 と lim 𝑑𝑑𝑘𝑘 = 0 より
𝑘𝑘→∞

lim 𝑟𝑟𝑘𝑘 = 0

𝑘𝑘→∞

𝐵𝐵𝑘𝑘

(𝜃𝜃𝑘𝑘 ∈ 𝜃𝜃,̅ 1 , 𝜃𝜃̅ ∈ 0,1 )なので，任意の停留点を 𝑥𝑥̅ とすると， 0 ∈ ∇𝑔𝑔 𝑥𝑥̅ + 𝜕𝜕𝜕 𝑥𝑥̅ が成立する

2023/8/8

COSS2023□
80

R-1次収束性定理
関数𝑔𝑔は強凸関数，つまり，正の定数 𝜇𝜇 が存在して
𝑔𝑔 𝑦𝑦 ≥ 𝑔𝑔 𝑥𝑥 + ∇𝑔𝑔 𝑥𝑥⊤

𝜇𝜇2𝑦𝑦 − 𝑥𝑥 +𝑦𝑦 − 𝑥𝑥
𝑓𝑓𝑓𝑓𝑓𝑓 𝑎𝑎𝑎𝑎𝑎𝑎 𝑥𝑥, 𝑦𝑦 ∈ 𝑅𝑅 𝑛𝑛2を満たすものとする．このとき，以下が成立する：

ただし，𝑥𝑥𝑘𝑘 − 𝑥𝑥

∗

𝑘𝑘

≤ 𝜌𝜌

𝜇𝜇
𝑓𝑓 𝑥𝑥0 − 𝑓𝑓 𝑥𝑥 ∗
2
∈ 0,1

である．
2023/8/8

COSS202381数値実験 その1
テスト問題
1 ⊤min 𝑥𝑥 𝐴𝐴𝐴𝐴 − 𝑏𝑏⊤ 𝑥𝑥 𝑠𝑠. 𝑡𝑡. 𝑥𝑥 ∈ Ω ,
𝑥𝑥 2
•
•
•
•
•

2023/8/8

1
min 𝑥𝑥 ⊤ 𝐴𝐴𝐴𝐴 − 𝑏𝑏⊤ 𝑥𝑥 + ℎ 𝑥𝑥 ,2

Ω = 𝑥𝑥 |𝑒𝑒 ⊤ 𝑥𝑥 = 𝑐𝑐, 𝑥𝑥 ≥ 0ℎ 𝑥𝑥 = �0𝑥𝑥 ∈ Ω
+∞ 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜

内部反復はV-FISTAで求解𝐴𝐴, 𝑏𝑏 は乱数で生成
次元 𝑛𝑛 = 1000, 2500, 5000, 7500 とし，各次元で50問（合計200
インスタンス）作成
その他詳細は Nakayama, N. and Yabe (2021) を参照
比較対象• PNOPT：Lee et al. (2014) のニュートン型近接勾配法• PG:近接勾配法• PGe:Wen et al. (2017)の外挿付き近接勾配法• mless-Pre(0.8): 提案法（プレコンベックスクラス）• mless-SR1：提案法(SR1公式)
COSS202382数値実験 その1
BFGS公式で非厳密さのパラメータ 𝜃𝜃𝑘𝑘 を動かした場合

2023/8/8

COSS202383数値実験 その1全体

次元ごと

2023/8/8

COSS202384数値実験 その2
テスト問題•

𝑎𝑎𝑖𝑖 ∈ 𝑅𝑅 𝑛𝑛 , 𝑏𝑏𝑖𝑖 ∈ −1,1 , 𝑖𝑖 = 1, … , 𝑝𝑝 は以下のデータセットを利用
Name

a9a

a1a

w8a

w1a

サンプル数 𝑝𝑝 16,281 30,956 292,363 47,272•

2023/8/8

次元 𝑛𝑛

123

123

300

300

leukemia

gisette

34

1000

7129

5000

比較方法
• PNOPT：Lee et al. (2014) のニュートン型近接勾配法• TFOCS：FISTAを実装したソフトウェア• mless-Pre(0.8): 提案法（プレコンベックスクラス）• mless-SR1：提案法(SR1公式)
COSS202385数値実験 その2

2023/8/8

COSS202386ニュートン型近接勾配法の課題(私見)𝐿𝐿

近接勾配法: 𝑥𝑥𝑘𝑘+1 = argmin𝑥𝑥 𝑔𝑔 𝑥𝑥𝑘𝑘 + ∇𝑔𝑔 𝑥𝑥𝑘𝑘 ⊤ 𝑥𝑥 − 𝑥𝑥𝑘𝑘 + ℎ 𝑥𝑥 + 2𝑘𝑘 𝑥𝑥 − 𝑥𝑥𝑘𝑘

ニュートン型近接勾配法: 𝑑𝑑𝑘𝑘 = 𝑥𝑥𝑘𝑘+ − 𝑥𝑥𝑘𝑘 , 𝑥𝑥𝑘𝑘+ ≈ argmin ∇𝑔𝑔 𝑥𝑥𝑘𝑘 𝑥𝑥 − 𝑥𝑥𝑘𝑘 +

1
2

2

2

𝑥𝑥 − 𝑥𝑥𝑘𝑘 𝐵𝐵 + ℎ(𝑥𝑥)•FISTAなどと比較するとやはり1回あたりの内部反復の手間が大きい• Becker et al. (2012)の結果の利用•

FISTAのような加速の提案•

収束率 𝑂𝑂•

2023/8/8

1
𝑘𝑘2

𝑘𝑘

の保証, KL Property の下での理論保証など

直線探索をProxの計算の外側で実行しているのがネック
COSS2023

87

まとめ
• 第1部

• 無制約最適化の基礎• 反復法• 直線探索• 最急勾配法，ニュートン法，準ニュートン法• 第2部• 大規模無制約最適化問題に対する反復法• 記憶制限準ニュートン法，BB法• 非線形共役勾配法• メモリーレス準ニュートン法• 第3部• 微分不可能な正則化項を含む問題への拡張• 近接勾配法• ニュートン型近接勾配法

2023/8/8

COSS2023

88