サブグラディエント法の概要
サブグラディエント法は、目的関数が滑らかでない場合でも用いることのできる最適化手法である。各反復で得られる方向情報を手がかりに、現在点を少しずつ更新し、最小値やその近傍へ近づける。凸解析に基づく枠組みとして整備されており、絶対値、最大値型関数、ノルム、ヒンジ損失のような非滑らかな問題で広く使われる。
この方法の利点は、勾配が定義されない点を含む関数に対しても、更新規則を構成できることである。もっとも、一般に勾配法より収束が遅く、設計するステップサイズや問題の構造に強く依存する。
サブグラディエントの定義
サブグラディエントとは、凸関数に対して勾配の代替として用いられるベクトルである。関数値がその点での一次近似より下にあることを保証する方向を表し、微分不能点でも複数の候補を持ちうる。
凸関数における支持超平面
凸関数では、ある点で関数を下から支える直線や超平面を考えることができる。このときの傾きに相当する量がサブグラディエントであり、関数全体の局所的な下界を与える。
サブ勾配集合の性質
ある点でのサブグラディエントは一つに限られず、集合として表される。凸関数ではこの集合は閉凸集合になり、点ごとの性質を記述するうえで都合がよい。滑らかな点では通常の勾配をただ一つ含む。
微分可能な場合との関係
サブグラディエントは、微分可能な場合には通常の勾配を拡張する概念として理解できる。したがって、滑らかな最適化と非滑らかな最適化を同じ言語で扱うための橋渡しとなる。
勾配とサブグラディエントの一致
関数がその点で微分可能なら、サブグラディエント集合は勾配ただ一つに一致する。このため、サブグラディエント法は勾配法を含む一般化とみなせる。
非滑らか点での解釈
絶対値の折れ点や最大値関数の切り替わり点では、勾配が定義されないことがある。そこでは、どの方向が下界を与えるかを表す複数のサブグラディエントが現れ、アルゴリズムはその中から一つを選んで進む。
問題設定と最適性条件
この手法が主に扱うのは、凸最小化問題である。目的関数は非滑らかでもよく、必要に応じて制約集合の上で最適化する。理論的には、最適点を特徴づける条件がサブグラディエントを用いて表される。
対象となる最適化問題
標準的には、与えられた関数を最小にする点を求める問題として定式化する。ユークリッド空間上の凸関数が基本だが、制約や正則化項を含む場合にも拡張できる。
凸最小化問題の標準形
典型形は、凸関数の最小化、あるいは凸関数と指示関数の和の最小化である。後者では制約条件を目的関数側に取り込むことで、射影操作と相性のよい形式になる。
最適性条件（停留条件）
最適点では、サブグラディエント集合が原点を含むという条件が成り立つ。これは非滑らかな場合における停留点の基準であり、勾配がゼロであることの一般化にあたる。
0 がサブグラディエント集合に含まれる条件
凸関数の最小点では、ゼロベクトルがサブグラディエント集合に属する。逆に、適切な凸性のもとではこの条件が最適性を与えるため、理論と計算の両面で重要である。
制約付き問題への拡張の考え方
制約がある場合は、可行集合への射影やラグランジュ的な考え方を組み合わせる。これにより、更新後の点が制約を満たすように調整できる。
アルゴリズム（基本形）
基本アルゴリズムは、現在点でサブグラディエントを計算し、その逆向きに少し進むという単純な反復から成る。実装上は、制約を満たすための射影や、収束を左右するステップサイズの設計が重要となる。
更新則
反復法の骨格は明快で、各時刻で得た部分勾配を用いて次の点を決める。滑らかな勾配法に似ているが、選ばれる方向は一意でない場合がある。
サブグラディエントに基づく反復
現在点 \(x_k\) においてサブグラディエント \(g_k\) を選び、\(x_{k+1}=x_k-\alpha_k g_k\) のように更新する。ここで \(\alpha_k\) はステップサイズであり、進み方の大きさを調整する。
射影（プロジェクション）を含む形
可行集合から外れないように、更新後に集合へ射影する形がよく用いられる。これにより、制約付き最適化でも単純な反復を保ちやすい。
ステップサイズの設計
収束性や実用上の性能は、ステップサイズの選び方に大きく左右される。固定値、減衰列、あるいは平均化を伴う設計など、状況に応じて複数の流儀がある。
固定ステップと収束
固定ステップは実装しやすいが、厳密な意味で最適点へ近づくとは限らない。しばしば近傍への到達や実用的な安定性を優先する場面で使われる。
減衰ステップの典型例
反復が進むにつれて小さくするステップサイズは、理論的収束のためによく採用される。たとえば、総和は発散するが二乗和は収束するような列が代表的である。
長い時間平均やスケジュール
各反復点そのものではなく、長期平均を取ることで挙動を平滑化できる。これは揺れの大きい更新列に対して有効で、理論解析でも扱いやすい。
収束性と性能評価
サブグラディエント法の収束は、滑らかな最適化よりも穏やかである。どの量がどの意味で収束するかを区別することが重要で、関数値、解列、平均点で性質が異なる。
収束の種類
「収束」といっても、目的関数値が下がること、点列がある解に近づくこと、平均点が安定することなど複数の意味がある。非滑らかな場合は、これらが必ずしも同時には成り立たない。
関数値の収束
実務上は、目的関数値が最小値に近づくかが重要である。サブグラディエント法では、関数値の減少が遅くても、平均化により良い評価が得られることがある。
解の収束（弱い収束を含む）
点そのものの収束は、空間の性質や制約の形に左右される。無限次元の場合には弱収束の概念が現れ、強い意味での収束とは区別して議論される。
計算量・誤差評価
理論解析では、反復回数に対してどの程度誤差が減るかを評価する。一般に、滑らかな二次収束のような速さは期待できず、上界の見積もりは保守的になる。
極限的な収束率の考え方
サブグラディエント法の典型的な解析では、誤差が反復回数の平方根程度でしか減らない場合がある。これにより、精度向上には比較的多くの反復が必要になる。
実務での停止基準
計算の打ち切りは、目的関数値の変化量、反復点の移動量、制約違反の大きさなどで判断する。理論上の極限到達を待つより、実用的な許容誤差で止めることが多い。
よくある落とし穴
実装では、単純な更新式の見た目に反して失敗しやすい点がある。特に、ステップの設定とモデル仮定の確認を怠ると、期待した挙動が得られない。
ステップサイズの選び方の誤り
ステップが大きすぎると振動し、小さすぎると進みが鈍くなる。理論条件を満たさない設定では、収束どころか不安定化する場合もある。
非凸や不適切なモデル化の影響
この手法は本質的に凸解析に依拠しているため、非凸問題にそのまま適用すると保証が弱くなる。さらに、目的関数の定式化が不適切だと、得られた結果の解釈自体が難しくなる。