【備忘】Optimization Methods for Large-Scale Machine Learning

Stochastic Optimization
論文の概要

　本論文は確率的最適化（以下、SG法）をバッチ最適化と比較しつつ、手法のサーベイをしたものである。バッチ最適化を代表する、古典的な非線形計画法は収束性が高い一方、大規模問題においてはSG法が主として用いられている。SG法には大きな研究の流れが２つあり、１）推定される勾配のノイズを低減、２）二次情報の利用が挙げられる。
　本論文では上記の内容を次の３つの内容：１）機械学習における最適化問題の難しいポイント（成功を収めている、近年のDeepLearningのような非線形性が強い非凸最適化問題）、２）、大規模機械学習において有用な最適化手法と有用であることの理由、３）顕著な進展とOpen Quetstionを踏まえて紹介している。
　本稿での各章の接頭語として記載されている数字は、論文の章番号を指す。

2. 大規模非線形非凸最適化問題を考える動機

　機械学習の予測モデルにおいて、滑らかでパラメータ表現が簡便な関数は現実的ではない。例えば文章分類問題などにおいて、簡便な代理モデルは既存のデータセットにおいては有効であるが、実運用に耐えうるものではなかった。近年、Deep Learningのような大規模非線形非凸最適化が台頭し、これまでの代理モデルと大きく乖離しているモデルが大成功を収めており、そのような複雑なモデルを対象とする必要が出てきた。
　本論文で対象とする問題はデータ数やモデルのパラメータ数が非常に多いものとし、モデルの関数系は定まっているものの、データとパラメータによりその形状が変わるものとする。機械学習のモデルを検討するにあたり、以下が注意すべき事項である。

  • 経験誤差最小化
    　事前の知識を使って適した関数を選ぶ。
  • 経験誤差と期待誤差のギャップの最小化
    　データ数を増やす。学習に用いるデータにより得られるモデルの形状が異なるため、ギャップを見積もるためにVC次元を考える必要がある。運用では交差検証法を用いる。
3. SG法とバッチ最適化の違い
3.1 SG法

  • 必ずしも降下方向に解を更新するとは限らない。

  • 全てのデータを使わずとも最適解に解を近づけられるため、バッチ最適化よりも効率的に関数の情報を用いていると思われる。

  • 最初の1、2エポックで急激にコスト関数の値が減少し、それ以降は緩やかになる。

  • 狭義凸な経験誤差に対して、データをiidサンプリングして勾配を算出した場合の収束レートは劣線形であり、データの標本サイズに依存しない。

  • 経験誤差の収束レートは、期待誤差の収束レートと同じ。

  • $\epsilon$誤差を得るために必要な計算時間は$1/\epsilon$オーダーでデータ数に関係ない。

  • 並列計算は可能だが、パラメータを高頻度で共有してしまうためにそれがオーバーヘッドとなり、効率の良い分散計算は難しい。

  • 研究の方向性（推定勾配のノイズ低減、Hessianの活用）

3.2 バッチ最適化

  • 勾配情報を用いられるため、種々の手法に繋がる。

  • 計算量の大半が目的関数やその勾配の評価にあたるため、並列化可能である。

  • 強凸な経験誤差に対して、収束レートは線形。

  • 十分時間をかけた際、コスト関数はSG法よりも小さい。

  • 勾配法を用いて $\epsilon$誤差の解を得るために必要な計算時間は$n \operatorname{log}(1 / \epsilon)$が目安で、データ数に比例する。

3.3 比較

  • SG法とバッチ最適化は経験誤差の最小化において、解を１回更新するための計算量とその時の経験誤差の減少量が異なるという点でトレードオフ。

  • データ数が十分多い場合は、SG法の方が収束までの時間が早い。

4. SG法のアルゴリズムの概略

　シンプルなSG法の特徴として、解の更新に用いる勾配の推定値がiidの確率変数に依存することと、ステップ幅が機械的に計算されることが挙げられる。勾配の推定値は１サンプル若しくは複数サンプルで計算されたり、その推定値をHessianでスケール変換することもある。
　通常SG法は平滑な関数を対象にしており、平滑であれば勾配の推定値の1次・2次モーメントを用いることで、解の更新によるコスト関数の減少値の上限を見積もることができる。見積もりにあたり、１）コスト関数が下に有界、２）勾配の推定値の1次・2次モーメントの上下限、３）勾配の推定値の分散の上界を仮定することで、コスト関数の減少値の期待値がアルゴリズムのパラメータに依存する形で得られる。以下の収束性の議論では、基本的に上記内容を仮定し、また解の更新により解が減少することを保証するため初期点が最適解近傍であることを仮定する。

  • Theorem 4.6：強凸関数に対してSG法を適用する際、固定ステップ幅を適切に定めると最適性ギャップの期待値が定数に収束する。この定理からわかることとして、ステップ幅を小さくすることで最適解近傍に近付くようになるが、収束性が悪化することが挙げられる。そのため、ステップ幅を大きい値から徐々に小さくすること（例：最適性ギャップの2倍に到達する毎にステップ幅を半分にするなど）が良いと考えられる。収束性を考えるとステップサイズに面倒な調整が出ないよう、目的関数に局所的な凸性があると望ましい。

  • Theorem 4.7：強凸関数に対してSG法を適用する際、ステップ幅を解の更新回数に反比例となるように減少させると、最適性ギャップの期待値も更新回数に反比例して減少していく。

  • Theorem 4.8：凸とは限らない関数に対してSG法を適用する際、固定ステップ幅を適切に定めると、勾配の更新履歴の二乗ノルムの平均値に対する期待値は、上限値が定数に収束する。

  • Theorem 4.9 ：凸とは限らない関数に対してSG法を適用する際、Theorem 4.7と同じステップ幅を用いると、勾配の二乗ノルムの期待値は0に収束する。

  • Theorem 4.10：Theorem 4.9と同じ条件の下、勾配の履歴の二乗ノルムの重みつき平均値に対する期待値は0に収束する。

5. SG法の発展：１）推定される勾配のノイズを低減

　SG法は推定される勾配のノイズの影響を受け、解への収束が妨げられる。線形収束するSG手法に対して、ノイズの影響を低減させる手法は大きく３つあり、１）Dynamic Sampling：徐々にノイズを低減させるようミニバッチのサイズを増加させていく方法、２）Gradient Aggregation：過去の更新方向の重み付けなどして、解の更新方向をより良くする方法、３）Iterate Averaging：最適解近傍での振動を抑えられるよう、解の更新履歴の平均を用いる方法が挙げられる。以下では、この３つの手法の詳細を述べる。

5.1：Dynamic Sampling

　Dynamic Samplingは次のTheorem 5.1を満たす手法の１つである。Theorem 5.1では、Theorem4.6と同様の仮定の下（固定ステップ幅の決め方は異なる）かつ推定勾配の分散が解の更新に応じて幾何級数的に減少するならば、最適性ギャップの期待値も幾何級数的に減少することを主張している。推定勾配の分散を幾何級数的に下げるには、Theorem 5.3より勾配を計算する際のサンプルサイズを幾何級数的に増大させれば良いことがわかる。このことから、バッチ最適化のアルゴリズムが与えらた際にサンプリングにより収束性の高いSG法の構築ができることが期待される。強凸関数に対してそのようなサンプリング方法は、劣線形収束レートを示すアルゴリズムに対しては存在しないが、線形収束レートのものに対しては幾何級数的にサンプリング、超線形収束レートの場合のものに対しては幾何級数よりも大きくサンプリングすると望ましいことがわかっている。
　実際の運用ではサンプルレートの調整は何度か計算を実行して決める必要があるため、適応的に決める方法も研究がなされているが、幾何級数的に増加することが保障されない。またDynamic Samplingは機械学習ではほとんど使用されていないため、本論文では他手法を検討する際の出発点として扱われている。

5.2：Gradient Aggregation

　この手法は、更新により解があまり変化していなければ、その更新情報を再利用しても良いのではないかという着想のものである。この手法は基本的に劣線形オーダーの収束しか得られないが、以下に示す手法は強凸関数に対して線形収束オーダーを示す。

  • Stochastic Variance Reduced Gradient（SVRG）
    　SVRGでは解の更新方向を$\tilde{g}_j \leftarrow \nabla f_{ij} (\tilde{w}_{j}) - \big( \nabla f_{ij}(w_k) - \nabla R_n(w_k) \big)$と定義しており、$\tilde{g}_j$は勾配の平均値の不偏推定量となっている。この勾配を用いた解の更新方法は種々あり、他のSG法と比較してコスト関数をよく下げられるが、ステップ幅などのパラメータは実験的に決める必要がある。

  • SAGA
    　SAGAでは解の更新方向を$g_k \leftarrow \nabla f_j(w_k) - \nabla f_j(w_{[j]}) + \frac{1}{n} \Sigma_{i=1}^{n} \nabla f_i(w_{[i]})$と定義しており、勾配の不偏推定量となっている。この手法は勾配ベクトルを$n$個格納する必要があるため、大規模問題には適用しにくい。

これらの手法はSG法よりも収束性は高いが、計算時間が早いとは限らないことに注意が必要である。（SG法：$T(n, \epsilon) \sim \frac{L^{2}}{(c \epsilon)^{2}}$、$T(n, \epsilon) \sim (n+\frac{L}{c})log(1/\epsilon)$）

5.3：Iterate Averaging

　SG法は最適解近傍で振動するため、Iterate Averagingではその挙動を抑えるためにパラメータの更新履歴の平均値、次のパラメータの値とする。平均を取ることやステップ幅を調整しても漸近収束性の改善にはつながらないことに注意が必要である。

6. SG法の発展：２）二次情報の利用

　古典的なSG法は、関数の二次情報を用いて非線形性や悪い条件数に対処することで性能を上げることができる。 二次情報を用いるアルゴリズムとしてNewton法や自然勾配法などが挙げられ、Newton法は変数の線形変換に対して不変である一方、自然勾配法は可逆変換に対して不変である。以下ではNewton法、自然勾配法の順番でSG法へ拡張した手法を確認していく。

6.1：Newton法

　Newton法にはHessian-Free Inexact Newton Methodsと呼ばれる手法がある。これは収束レートが超線形オーダーのInexact Newton Methodsを基にしたものである。Hessian-Freeの名前の由来は、Hessianを直接扱わずHessianとの内積を扱うことである。それをSG法に拡張したものが、Subsampled Hessian-Free Newton Methodsである。このSubsamplingは、暫定解に対して条件付き無相関にしなければならない。Hessianは勾配と比較してノイズに対して頑健であるため、そこまで精度よく計算する必要はないが、曲率を正確に捉えられるようにサンプル数は大きくしたいという要望はある。サンプル数を適切に設定すれば、ロバストかつ効率的に解の更新が得られる。この議論は、Hessianを推定する際に用いるデータセットの方が、勾配を推定する際に用いるデータセットの数よりも小さいことを前提としているため、それが崩れる場合はSG法を用いるのがよい。
　Hessian Freeの手法は、非凸最適化問題の機械学習にも適用されている。例えばGauss-Newton法のように正定値行列に近似するものは、機械学習だけでなく深層学習の学習でも有用である。特に深層学習の学習において、負の曲率と鞍点が果たす役割について多くの議論がある。（詳細は文献を参照のこと）
　メモリ効率の良い手法として、Quasi-Newton Methodが挙げられる。この手法は解の更新方向をベクトルのペアから求めるためメモリ効率が良い。これをSG法に拡張したものはStochastic Quasi-Newton Methodと呼ばれ、通常のSG法と同様に劣線形の収束レートである。この利点は、近似したHessianが元の関数のHessianに一致する際、収束レートに含まれる定数がHessianに関係なくなるため、SG法よりも条件数の観点で理論的に良い手法である。この手法を適用する際のミニバッチのサイズは、Hessian Freeのように大きくする必要はないが、少なくとも20 or 50以上が望ましい。基本的なBFGS法であれば、推定した勾配の分散が大きい場合、つまり曲率の推定が悪い場合も問題なく適用できる。しかし、SG法へ拡張したOnline L-BFGS法は問題となる。

6.2：自然勾配法

　冒頭でも述べたが、Newton法はパラメータの線形変換に対して不変である一方、自然勾配法は微分可能な可逆変換に対して不変である。自然勾配法のパラメータ空間での挙動は、コスト関数に小さな影響を与える方向には速くパラメータを変化させ、大きな影響を与える方向には慎重に変化させるものである。関数空間では、パラメータを変化させたときのパラメータの変化をKL-divergenceで定義した際リーマン多様体を形成しており、その変化（ノルム）は局所的にFisher Information Matrix（$FIM$）で近似できる。この事実を基に自然勾配法は解の更新にあたり、KL-divergenceで定義したパラメータの変化が十分小さい範囲で、コスト関数を最小にするパラメータを計算するものである。その更新式は、Newton法のように勾配を$FIM$の逆行列で補正するものである。この形は、最尤推定法でよく使われる最適化手法であるスコア関数法と非常によく似ている。また最適解近傍においては、$FIM$はHessianと同じような値になるため、その場合においては自然勾配法とNewton法は同等の類似手法と言える。
　SG法への拡張にあたり、$FIM$をSubsamplingしたデータで計算する方法があるが、Gauss-Newton法と同様の議論ができる。

6.3：その他

　上記２つの方法の様に２次情報を取り込むなどして収束性を高めたいが、追加で発生するHessianなど２次情報を求める計算が原因で、計算量が多くなりすぎてしまう時がある。計算量を抑えるために、Hessianの対角成分のみを近似した対角行列やブロック対角行列で代用することを考える。
　例えばGauss-Newton法の場合は、新たに計算したHessianをまま使用するのではなく、前の更新で利用したものと凸結合をとったものを採用する。解の更新にあたっては、その様にして得られたHessianの近似行列の対角成分のみを用いて勾配に適用する。こうすることで、一次法を拡張したSG法と比較して２倍ほど計算量は増加するが、パラメータをよくチューニングしたSG法よりも優れた結果が得られている。 Hessianの逆行列を直接近似する方法もあるが、解の更新の際に相関のあるノイズが原因で曲率の推定に悪影響を及ぼしてしまったり、近似した行列の挙動に規則性がないためステップ幅を決めるのが難しかったりという報告がなされておりと、望ましい方法ではない。
　Hessian行列の近似を考えたが、曲率情報を考慮せずに、解の更新方向をスケーリングするために対角行列を導入することもある。曲率情報を考慮した解の更新方向の大きさは、必ずしも現実的ではなくステップ幅を調整した方が望ましい。バッチ最適化ではステップ幅の調整は容易だが、SG法では、非凸関数を対象にしている場合は困難である。解の更新方向の大きさをスケーリングすることは単純であるが、深層学習に対しては効果的であるとの報告がある。ステップ幅は更新に応じて減少させていくものを採用すれば良く、ADAGRADを用いた場合深層学習に対して優れた性能を発揮する。ただし、最適化の初期の段階でステップ幅が小さくなりすぎることが課題として上がっている。

7. その他の手法
7.1：モーメンタム法

　前回の更新方向も考慮して、$w_{k+1} = w_k - \alpha_k \nabla f(w_k) + \beta_k(w_k - w_{k-1})$として解を更新する方法である。$(\alpha_k , \beta_k)$は定数でも更新ごとに値を変えても良い。コスト関数が２次凸関数であれば、解の更新ごとに最適化問題を解くことで、最も減少させられる$(\alpha_k , \beta_k)$が得られる。過去の勾配方向の系列を考慮する方法もあり、更新方向の振動が抑えられるという利点がある。勾配を推定値に置き換えてSG法に拡張した際の理論的性質は明らかではない。

7.2：加速勾配法

　$w_{k+1} = w_k - \alpha_k \nabla f(w_k + \beta_k(w_k - w_{k-1})) + \beta_k(w_k - w_{k-1})$として解を更新する方法である。$\alpha_k = \alpha >0, {\beta_k} \rightarrow 1$となるよう適切に設定することで、連続微分可能でリプシッツ連続な凸関数の収束レートが最適レートを達成する。勾配を推定値に置き換えてSG法に拡張した際は、バッチ最適化の様に収束レートは改善せず、Theorem 4.7の定数が改善される可能性がある程度である。

7.3：座標降下法

　座標降下法は、解の更新にあたり特定の座標軸のみを更新する方法である。パラメータとしては、ステップ幅と更新する座標軸の選定方法の２つである。座標軸の選定には、１）順繰りに選んでいく方法、２）更新する順番をランダムに並び替え、選定が一巡するごとにランダムに並び替える方法、３）解を更新する度に選定する座標軸をランダムに選ぶ方法が挙げられる。ランダム性を持った２）、３）の方が１）よりも理論的には優れている。
　座標降下法の収束性は、連続微分可能な関数に対しては保証されておらず、簡易な非凸関数に適用した際に収束が見られなかったことが報告されている。強凸関数を対象にした場合は収束が保証されており、特に連続微分可能で勾配の各要素に対してリプシッツ連続であるならば、３）の方法で軸を選択する際、線形オーダーで収束する。更新する軸の選択確率を各要素のリプシッツ定数で重み付けしても同様に線形収束となる。

8. 正則化付きの最適化問題に対する手法

　本章で対象とする最適化問題は以下のような正則化付きの最適化問題で、目的関数は平滑な凸関数$f(w)$であるが、正則化項は平滑とは限らないが凸関数であるとする。この問題を解く手法としてproximal gradient methodやproximal Newton methodなどが挙げられ、ここではそれらの手法について述べる。（Orthant-basedは割愛）
$$ \min_{w \in \mathbb{R}^{n}} f(w) + \lambda g(w) $$

8.1：proximal gradient method

　この手法は目的関数を勾配を用いて二次関数で近似し、正則化項との和を最小にするように解を更新する方法である。

\begin{aligned} w_{k+1} = \operatorname{argmin}_{ w \in \mathbb{R}^{n} } f(w_k) + \nabla f(w_k)^{T} (w - w_k) + \frac{1}{2 \alpha_{k}} \| w - w_k \|_{2}^{2} + \lambda g(w) \end{aligned}

　$\alpha_k$を適切な定数として、$f(x)$が連続微分可能な強凸かつ平滑ならば、唯一解に最適値の意味で収束することが保障されている（Theorem 8.1）。また、第$3,4$項（近接項と正則化項）が効率よく計算できる時は実用的である。具体的には、$g$が多面体のような単純な集合の指示関数や$l1$ノルム、計算が分離可能なものである。
　これをSG法に拡張するためには、$\nabla f(w_k)$を推定値に置き換えてあげれば良い。$l1$ノルムを対象にしたISTAもSG法として拡張できる。また正則化項としての$l1$ノルムを変数変換して滑からな最適化問題とした場合、射影勾配法を解くことなり、スパース解が得られなくなるかもしれないが、同様にSG法へ拡張できる。

8.2：Second-Order Methods：proximal Newton method

　この手法は、proximal gradient methodの解の更新方法をベースに、近接項の係数をHessianもしくは準ニュートン法で行う近似したHessianに置き換える手法である。proximal gradient methodと比較して解析や実装が難しいという課題があるが、それを解決できればスケーラビリティだけでなく、高い性能を出すことができる。課題としては、１）部分問題が非平滑関数であること、２）部分問題の計算の終了判定に微分が含まれていること、３）計算量が大きいことが挙げられる。
　それらには対応策があり、以下順に述べる。１）Lassoのようによく研究されている関数の最適化手法はCD法などの解き方が種々存在する。２）ISTAによる解の変化の大きさを終了判定にとる。この基準は微分が不要だけでなく、最適解に到達すれば$0$を示し、実数空間において連続関数であるという重要な性質を持つ。３）（L1 正則の場合）各部分問題において、いくつかの変数の要素を$0$に固定する。$0$ に固定する変数は、（Orthant-Based Methodで議論される）感度情報などを用いれば良い。

参考文献

Bottou, Léon, Frank E. Curtis, and Jorge Nocedal. "Optimization methods for large-scale machine learning." SIAM review 60.2 (2018): 223-311

Proposition 1.3.2（Bertsekas 2009）

Convex Set
定理

非空の凸集合$C$に対して以下が成立する。

(a) $\operatorname{ri}C$ は非空の凸集合であり、$C$と同じアフィン包を持つ。

(b) $m$が $\operatorname{aff}C$ の次元であり、$m > 0$ であれば、ベクトル $x_0, x_1, \dots, x_m \in \operatorname{ri}C$ が存在し、$x_1 - x_0, \dots, x_m - x_0$ が $\operatorname{aff}C$ に平行な部分空間を張る。

方針

(a)　$\operatorname{aff}C$の相対開集合（open relative）$X$を構築する。それが非空であることから$\operatorname{ri}C$が非空であることを導き、$\operatorname{aff}C = \operatorname{aff}X$であることから$\operatorname{aff}(\operatorname{ri}C) = \operatorname{aff}C$を導く。

不明点

(a)　$\operatorname{ri}C$ が非空という条件を用いずに、非空な$m$次元凸集合$C$から$m$個の線型独立なベクトルが存在すること。本稿では、原著に倣い既知の事実としています。

証明

(a)
　$\operatorname{ri}C$ の凸性はTheorem 6.1（Rockafellar 1970）において、$y \in \operatorname{ri}C$とすることで得られる。

（$C$には線型独立なベクトルが$n$個含まれる。）
　$0 \in C$とする。（$0 \notin C$の場合は、適当な$x \in C$だけ並行移動させれば良い。）
$\operatorname{aff}(C)$は$C$を含む部分空間であり、その次元を$m$とする。

　$m = 0$ならば、$C$と$\operatorname{aff}C$は単一の点からならなり、その点は単一の相対的内点となる。
$m > 0$ならば、$C$に含まれる$m$個の線形独立なベクトル$\lbrace z_1, \cdots, z_m \rbrace$が存在し、それらは$\operatorname{aff}C$の基底ベクトルとなる。（不明点で言及した箇所）

（$\operatorname{ri}C$に含まれる$n$次元凸集合$X$の定義）
　以下では、次のような集合$X$を考える。

\begin{aligned} X = \lbrace x \mid x = \sum_{i=1}^m \alpha_i z_i, \sum_{i=1}^m \alpha_i < 1, \alpha_i > 0, i = 1, \dots, m \rbrace \end{aligned}

　$C$は凸集合であり、その定義から $X \subset C$ となる。 このとき、$X$は $\operatorname{aff}C$ の相対開集合（$\exists \epsilon > 0 \quad \text{s.t.} \quad \lbrace x \in B(\bar{x}, \epsilon)\mid B(\bar{x}, \epsilon) \cap \operatorname{aff}C \subset X, \bar{x} \in X \rbrace \neq \emptyset$）となる。（証明は後述）

（非空及び同じアフィン包ことの証明）
　相対開集合であることと$X \subset C$より、$\operatorname{ri}C$は非空であり、$X \subset \operatorname{ri}C$である。
$X, C$は定義よりそのアフィン包は$n$次元凸集合であることから、$\operatorname{aff}C = \operatorname{aff}X$となり、$\operatorname{aff}C \subset \operatorname{aff}(\operatorname{ri}C)$が導ける。 （一致することの理由が正しいかは議論の余地あり）
　また$\operatorname{ri}C \subset C$であることから$\operatorname{aff}C \supset \operatorname{aff}(\operatorname{ri}C)$となるため、$\operatorname{aff}C = \operatorname{aff}(\operatorname{ri}C)$が示される。

（参考：$X$は$C$の相対開集合であることの証明）
　以下を定義する。

\begin{aligned} &B(\bar{x}, \epsilon) = \lbrace x \mid \| x - \bar{x} \| < \epsilon \rbrace \\ &A = \left\lbrace (\alpha_1, \cdots, \alpha_m) \mid \Sigma_i^{m} \alpha_i <1, \alpha_i > 0, i = 1, \cdots,m \right\rbrace \\ &Z = (z_1, \cdots, z_n) \in \mathbb{R}^{n \times m} \end{aligned}

　$\bar{x} \in X, x \in \operatorname{aff}C$となる$x, \bar{x}$について考える。それぞれは基底ベクトルと適切な係数を用いて表現でき、$\bar{x} = Z \bar{\alpha}, x = Z \alpha$とできる。$Z$が線型独立な基底ベクトルから成るため、$Z^{T}Z$が正定値対称行列となり、以下が成立する。

\begin{aligned} \| \bar{x} - x \|^{2} = (\bar{\alpha} - \alpha)^{T} Z^{T} Z (\bar{\alpha} - \alpha) \ge \gamma (\bar{\alpha} - \alpha)^{2} \end{aligned}

　$\bar{x} \in X$であるため、$\bar{\alpha} \in A$となる。$x \in B(\bar{x}, \epsilon)$のとき上式より$\epsilon > \gamma ( \bar{\alpha} - \alpha )^{2}$となることから$\alpha \in A$となり、$x \in X$が導かれる。
　以上を整理すると、$X \subset\operatorname{aff}C$であることから$B(\bar{x}, \epsilon) \cap \operatorname{aff}C$は空集合ではなく、十分小さい$\epsilon$に対して$B(\bar{x}, \epsilon) \cap \operatorname{aff}C \subset X$が成立する。よって相対開集合であることが示された。

(b)
　(a)より$\operatorname{ri}C$は非空であるため、$\exists x_0 \in C$となる。また、その点を中心に摂動を加えた点も$\operatorname{ri}C$に含まれるため、その点を標準基底の係数倍だけ並行移動させて得られるベクトルも含まれることから、$m$個の線形独立なベクトル$\lbrace z_1, \cdots, z_m \rbrace$が存在する。Theorem 6.1（Rockafellar 1970）より$0 \in \operatorname{ri}(C-x_0)$との凸結合を考えると、$\alpha \in (0,1)$に対して$\alpha z_i \in \operatorname{ri}(C-x_0)$が成立する。
　これを$x_0$だけ並行移動させると、$\forall i \ (1 \le i \le m) \quad x_i = x_0 + \alpha z_0 (\in \operatorname{ri}C \subset C)$なり、$x_0, x_1, \cdots, x_m \in \operatorname{ri}C$は示される。
　また$x_i - x_0 = z_i \in \operatorname{ri}(C-x_0)$は$\operatorname{aff}(C-x_0)$を構成する基底ベクトルである。つまり、$x_1-x_0, \cdots, x_n - x_0$は$\operatorname{aff}C$を$x_0$だけ並行移動させた部分空間を張る。

参考文献

Bertsekas, Dimitri. Convex optimization theory. Vol. 1. Athena Scientific, 2009. p24

【備忘】KAN 2.0: Kolmogorov-Arnold Networks Meet Science

Kolmogorov-Arnold Networks

論文の概要

　本論文は先行研究のKANであるSpl-KANを改良し、KANを用いて科学的な知見を発見できるような工夫を提案したものである。KANの改良にあたっては、１）Spl-KANで表現できなかった乗算を表現できるようにした。また、科学的な知見を発見できるよう、２）重要な特徴量の特定方法、３）近似対象の関数からモジュール構造の抽出方法、４）事前知識の活用として、所与の関数からKANを記述方法を提案した。
　これらを組み合わせることで、物理現象を始めとする種々の自然科学の知見を得られるようになると期待される。

提案手法MultKANの特徴：

KANの改良：乗算表現

　KANの関数表現はKART（Kolmogorov-Arnold Representation Theorem）に基づいている。具体的には、写像関数$\Phi_q, \phi_{p,q}$および入力$x = (x_1, \cdots, x_n)$を用いて、関数$f(x)$を$f(x) = \Sigma_{q=1}^{2n+1} \Phi_{q} \big( \Sigma_{p=1}^{n} \phi_{q,p} (x_p) \big)$のように表現する。このように入力の各要素の写像の線形和を更に写像するため、$xy$のような乗算を表現することは難しい。先行研究においては、乗算の表現は$xy = \frac{(x + y)^{2} - (x-y)^{2}}{4}$となっており、これがKANの解釈性を下げることにつながる。
　本研究では、KANの各層の出力先に乗算ノードのみから構成される層を用意した。これにより、乗算を平易に表現することができるようになった。乗算ノードと出力ノードの結合は、疎になるようにKANの学習と同様、L1+Entropy Reguralizationでスパースとなるようしている。

科学的な知見を発見するための工夫

重要な特徴量の特定

　重要な特徴量（ノード）の特定にあたり、Spl-KANでは着目するノードから出る出力のエッジの値に着目をしていた。しかし、ある出力層において大きな値が得られても、最終層に及ぼす影響が大きいとは限らない。そこで本研究では、最終層から全てのエッジの値を遡って考慮することにした。

モジュール構造の抽出

　上述の重要な特徴量は、エッジがノードにどのように接続しているのかを示すモジュール構造については言及していない。モジュール構造はNeural Networkの理解を容易にするため、検討する方が望ましい。モジュール構造はAnatomical ModularityとFunctional Modularityの２つに分けられる。

  • Anatomical Modularity

　脳のニューロンでは空間的に近いニューロン同士は強い接続を持つ。空間的な近接性をNerural Netoworkに導入することでノード間の接続が視覚的に見やすくなるため、本研究でも導入している。この近接性の導入方法は、重要度の高い上位k番目までノードを各層ごとに並び替えることである。ここでの重要度は、ノードに前後の層から接続されるエッジの絶対値の総和である。

  • Functional Modularity

　このモジュール構造として変数の分離可能性と対称性が挙げられる。分離可能性は、和（イメージ：$f(x_1, x_2) = g(x_1)+h(x_2)$）、積（イメージ：$f(x_1, x_2) = f(x_1)f(2)$）について考えており、対称性は当該変数を入れ替えても結果が変わらない構造（例：L2ノルム）を指す。
　和に関する分離可能性は、関数のHessianの要素が0になる変数の組み合わせに着目すれば抽出できる。一方積に関する分離可能性は、関数を対数変換した後、和と同様にHessianに着目することで確認できる。これらを組み合わせることで、分離可能な関数の合成関数に対しても適用できる。対称性も同様に考えば良く、対称となる変数群の微分を、対称ではない変数群で微分すると０になれば、その関数は対象となる。これらを確認するプログラムコードは実装されている。

所与の関数からKANを記述、運用

　KANに事前知識を導入しなければ、既に知っている事前知識の学習に時間をかけてしまう虞れがある。そこで、数式表現されている事前知識をKANに埋め込み、その後データを用いて学習させれば効率が良いと考えられる。KANへの埋め込みでは、所与の数式を木構造で表現し、KANの計算グラフのような構造に変形していくことで達成される。この表現は所与の数式を簡潔に表現できているが、深さ・幅が少ないため表現力が低い可能性がある。そこでKANを大きくする必要がある。
　実際にKANを用いる際は、データからモジュール構造を抽出した後にその構造をKANに埋め込み、再度学習をしていく。再学習にあたって、スパース正則の調整を容易にするため、エッジの初期化はスパースにした方が望ましい。学習を種々行うことで複数モデルが得られた場合は、残差やパラメータ数（簡潔表現かどうか）でKANのモデルを採用するかを判断する。

参考文献

Liu, Ziming, et al. "Kan 2.0: Kolmogorov-arnold networks meet science." arXiv preprint arXiv:2408.10205 (2024).

以上。

【備忘】Wav-KAN: Wavelet Kolmogorov-Arnold Networks

Kolmogorov-Arnold Networks
論文の概要、手法の利点

　先行研究のKolmogorov-Arnold Networksは（従来法：Spl-KAN）、スプライン曲線を用いて関数近似を行った。本研究は近似する関数としてwavelet関数を採用したもので（提案手法：Wav-KAN）、従来と違い区間をデータに応じて動的に決定でき、またパラメータ数が少ないため学習の時間も短くできることが特徴である。 　それぞれの手法の利点・欠点は用いる関数の特性に由来する。Spl-KANの利点は、スプライン関数が区間ごとに滑らかに関数を近似していくため、データに局所的な変化が起きたとしても関数全体が変わることはない。応用先として、CADやコンピューターグラフィックなど滑らかな表現が必要な分野が挙げられる。欠点は滑らかに近似することから学習の計算量の大きさと、データのノイズまでとらえてしまうことである。
　一方Wav-KANは、Wavlet解析のように関数の高周波と低周波の両方を疎な表現で捉えることができ、無関係なノイズの影響を受けにくい。また非定常で局所的に特徴のある関数にも適用でき、関数の特徴抽出も可能である。Spl-KANと違って区間に関するパラメータが不要となるため、学習のための計算量は少ない。性能評価としてMNISTのクラス分類問題にWaV-KANを適用した結果、Spl-KANと同等以上の正答率が得られた。mother waveletにより性能が異なるため、適切な選定が必要となる。

（参考：Spl-KAN、Wav-KANともに学習の際にバッチ正則化を行うと、学習の計算時間が短くなり、精度が向上するという実験結果が得られた。)

参考文献

Bozorgasl, Zavareh, and Hao Chen. "Wav-kan: Wavelet kolmogorov-arnold networks." arXiv preprint arXiv:2405.12832 (2024).

以上。

Theorem 6.1（Rockafellar 1970）

Convex Function
定理

$C$ を $\mathbb{R}^n$ の凸集合とする。$x \in \text{ri } C$ 及び $y \in \text{cl } C$ とする。このとき、$0 \leq \lambda < 1$ に対して $(1 - \lambda)x + \lambda y$ は $\text{ri } C$（従って特に $C$）に属する。

証明

$B(x, a) = \lbrace x \mid d(x,a) \le 1 \rbrace$とすると$\operatorname{ri}C$の定義より、$(1 - \lambda)x + \lambda y + \epsilon' B(x,0) \subset C$を証明すれば良い。

\begin{aligned} (1 - \lambda)x + \lambda y + \epsilon' B(x,0) &\subset (1 - \lambda)x + \lambda \big( C + \epsilon B(x,0) \big) + \epsilon' B(x,0) \\ &= (1-\lambda) \big( x + \frac{\lambda \epsilon + \epsilon'}{1-\lambda} B(x,0) \big) + \lambda C \end{aligned}

となる。
　$C$が$n$次元空間上で定義された凸集合であるため、$\operatorname{ri}C = \operatorname{int}C$であり、$x \in \operatorname{int}C$となる。その定義より、十分小さい$\epsilon'' = \frac{\lambda \epsilon + \epsilon'}{1-\lambda}$に対して、$x + \frac{\lambda \epsilon + \epsilon'}{1-\lambda} B(x,0) \in C$となる。
　また、$C$は凸集合であるため、Theorem 3.2（Rockafellar 1970）より$(1-\lambda)C + \lambda C = C$となる。 よって、$(1 - \lambda)x + \lambda y + \epsilon' B(x,0) \in C$は示された。

参考文献

Tyrrell Rockafellar, R, 1970 p45

Theorem 5.8（Rockafellar 1970）

Convex Function
定理

$f_1, \dots, f_m$ を $\mathbb{R}^n$上の真凸関数とする。以下も凸関数である。

\begin{aligned} &f(x) = \inf \big\lbrace \max \lbrace f_1(x_1), \dots, f_m(x_m) \rbrace \ &\mid& \ x_1 + \cdots + x_m = x \big \rbrace \\ &g(x) = \inf \big\lbrace (f_1 \lambda_1)(x) + \cdots + (f_m \lambda_m)(x) \ &\mid& \lambda_i \ge 0, \ \lambda_1 + \cdots + \lambda_m = 1 \big\rbrace \\ &h(x) = \inf \big\lbrace \max \lbrace (f_1 \lambda_1)(x) , \cdots, (f_m \lambda_m)(x) \rbrace \ &\mid& \lambda_i \ge 0, \ \lambda_1 + \cdots + \lambda_m = 1 \big\rbrace \\ &k(x) = \inf \big\lbrace \max \lbrace \lambda_1 f_1(x_1), \cdots, \lambda_m f_m(x_m) \rbrace \ &\mid& \lambda_1 x_1 + \dots + \lambda_m x_m = x \big\rbrace \\ \end{aligned}

方針

$f,g,h,k$順に、その関数を定義する錐に対して、$x$、$\lambda, \mu$ 、$\lambda$、$\lambda, x$についてpartial addtionをとれば良い。

証明

錐$K \equiv \lbrace (\lambda, x, \mu) \mid \lambda \ge 0, x \in \mathbb{R}^{n}, \mu \ge (f \lambda)(x) \rbrace$ を用いて、$F = \lbrace (x, \mu) \mid (1, x, \mu) \in K \rbrace$を定義する。
Theorem 5.3（Rockafellar 1970）より、凸関数は$\inf \lbrace \mu \mid (x, \mu) \in F \rbrace$より定まるため、そのことを念頭に以下を証明していく。

($f$の凸性)
$i = 1, \cdots, m$に対して、$K_{x_i} = \lbrace (\lambda, {x_i}, \mu) \mid \lambda \ge 0, x_i \in \mathbb{R}^{n}, \mu \ge (f_i \lambda)(x_i) \rbrace$を考え、$x$についてpartial addtionを行う。

\begin{aligned} K_{x} = \lbrace (\lambda, {x}, \mu) \mid &\lambda \ge 0, \\ &x_1, \cdots, x_m \in \mathbb{R}^{n}, \ x = x_1 + \cdots + x_m, \\ &\mu \ge (f_1 \lambda)(x_1) , \cdots, \ \mu \ge (f_m \lambda)(x_m) \rbrace \end{aligned}

この$K_x$から定まる関数を$f(x)$とすると、

\begin{aligned} f(x) &= \inf \lbrace \mu &\mid &\ x_1, \cdots, x_m \in \mathbb{R}^{n}, \ x = x_1 + \cdots + x_m, \\ & & & \mu \ge (f_1)(x_1) , \cdots, \ \mu \ge (f_m)(x_m) \rbrace \\ & = \inf \big\lbrace \max \lbrace f_1(x_1) , \cdots, f_m \rbrace &\mid & x_1, \cdots, x_m \in \mathbb{R}^{n}, x = x_1 + \cdots + x_m, \big\rbrace \end{aligned}

$K_{x_i}$から定まる$F$について、$x_i \in \mathbb{R}^{n}$で、$f_i$が真凸関数であることから凸集合となる。よって、Theorem 3.1（Rockafellar 1970）よりそのparitial additionで定まる集合も凸集合となる。このことからTheorem 5.3（Rockafellar 1970）より、$f(x)$が凸関数であることが言える。

($g$の凸性)
$i = 1, \cdots, m$に対して、$K_{\lambda_i, \mu_i} = \lbrace (\lambda_i, x, \mu_i) \mid \lambda_i \ge 0, x \in \mathbb{R}^{n}, \mu_i \ge (f_i \lambda_i)(x) \rbrace$を考え、$\lambda, \mu$についてpartial addtionを行う。

\begin{aligned} K_{\lambda, \mu} = \lbrace (\lambda, {x}, \mu) \mid &\lambda = \lambda_1 + \cdots + \lambda_m, \lambda_1, \cdots, \lambda_m \ge 0, \\ &x \in \mathbb{R}^{n}, \mu = \mu_1 + \cdots + \mu_m, \mu_1 \ge (f_1 \lambda_1)(x) , \cdots, \ \mu_m \ge (f_m \lambda_m)(x) \rbrace \end{aligned}

この$K_{\lambda, \mu}$から定まる関数を$g(x)$とすると、

\begin{aligned} g(x) & = \inf \lbrace \mu &\mid &(1, x, \mu) \in K_{\lambda, \mu} \rbrace \\ & = \inf \lbrace \mu_1 + \cdots + \mu_m &\mid &\Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0 , \\ & & & \mu_1 \ge (f_1 \lambda_1)(x) , \cdots, \ \mu_m \ge (f_m \lambda_m)(x) \rbrace \\ & = \inf \lbrace (f_1 \lambda_1)(x) + \cdots + (f_m \lambda_m)(x) & \mid &\Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0 \rbrace \\ \end{aligned}

となる。$(f_i \lambda_i)(x)$は$\lambda_i \operatorname{epi}f_i$から定まる凸関数であるため、$K_{\lambda, \mu}$はそれらの積集合となるため、凸集合となる。よって、Theorem 5.3（Rockafellar 1970）より、$g(x)$が凸関数であることが言える。

($h$の凸性)
$i = 1, \cdots, m$に対して、$K_{\lambda_i} = \lbrace (\lambda_i, x, \mu) \mid \lambda_i \ge 0, x \in \mathbb{R}^{n}, \mu \ge (f_i \lambda_i)(x) \rbrace$を考え、$\lambda$についてpartial addtionを行う。

\begin{aligned} K_{\lambda} = \lbrace (\lambda, x, \mu) \mid &\lambda = \lambda_1 + \cdots + \lambda_m, \lambda_1, \cdots, \lambda_m \ge 0, \\ \ &x \in \mathbb{R}^{n}, \mu \ge (f_1 \lambda_1)(x) , \cdots, \ \mu \ge (f_m \lambda_m)(x) \rbrace \end{aligned}

この$K_{\lambda, \mu}$から定まる関数を$h(x)$とすると、

\begin{aligned} h(x) & = \inf \lbrace \mu \mid (1, x, \mu) \in K_{\lambda} \rbrace \\ & = \inf \lbrace \mu \mid \Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0 , \ \mu \ge (f_1 \lambda_1)(x) , \cdots, \ \mu \ge (f_m \lambda_m)(x) \rbrace \\ & = \inf \big\lbrace \max \lbrace (f_1 \lambda_1)(x) , \cdots , (f_m \lambda_m)(x) \rbrace \mid \Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0 \big\rbrace \\ \end{aligned}

となる。、$K_{\lambda, \mu}$から定まる$F$は、$\lambda$については確率単体であり、$x,\mu$については凸関数のepigraphであることから凸集合となっている。よって、Theorem 5.3（Rockafellar 1970）より、$h(x)$が凸関数であることが言える。

($k$の凸性)
$i = 1, \cdots, m$に対して、$K_{\lambda_i, x_i} = \lbrace (\lambda_i, x_i, \mu) \mid \lambda_i \ge 0, x_i \in \mathbb{R}^{n}, \mu \ge (f_i \lambda_i)(x_i) \rbrace$を考え、$\lambda$についてpartial addtionを行う。

\begin{aligned} K_{\lambda, x} = \lbrace (\lambda, x, \mu) \mid &\lambda = \lambda_1 + \cdots + \lambda_m, \lambda_1, \cdots, \lambda_m \ge 0, \\ &x = x_1 + \cdots + x_m, x_1, \cdots, x_m \in \mathbb{R}^{n}, \\ &\mu \ge (f_1 \lambda_1)(x_1) , \cdots, \ \mu \ge (f_m \lambda_m)(x_m) \rbrace \end{aligned}

この$K_{\lambda, x}$から定まる関数を$k(x)$とすると、

\begin{aligned} k(x) & = \inf \lbrace \mu &\mid &(1, x, \mu) \in K_{\lambda, x} \rbrace \\ & = \inf \lbrace \mu &\mid &\Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0, \\ & & &x = \Sigma_{i=1}^{m} x_i,\ x_1, \cdots, x_m \in \mathbb{R}^{n}, \\ & & & \forall i \ \ \mu \ge (f_i \lambda_i)(x_i) \rbrace \\ & = \inf \big\lbrace \max \lbrace (f_1 \lambda_1)(x_1) , \cdots , (f_m \lambda_m)(x_m) \rbrace &\mid &\Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0, \\ & & &x = \Sigma_{i=1}^{m} x_i,\ x_1, \cdots, x_m \in \mathbb{R}^{n} \big\rbrace \\ & = \inf \big\lbrace \max \lbrace \lambda_1(f_1)({\lambda_1}^{-1}x_1) , \cdots , \lambda_m(f_m)({\lambda_m}^{-1}x_m) \rbrace &\mid & \Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0,\\ & & &x = \Sigma_{i=1}^{m} x_i,\ x_1, \cdots, x_m \in \mathbb{R}^{n} \big\rbrace \\ & = \inf \big\lbrace \max \lbrace \lambda_1f_1(x_1) , \cdots , \lambda_m f_m(x_m) \rbrace &\mid &\Sigma_{i=1}^{m} \lambda_i = 1, \lambda_i, \cdots, \lambda_m \ge 0,\\ & & &x = \Sigma_{i=1}^{m} \lambda_i x_i,\ x_1, \cdots, x_m \in \mathbb{R}^{n} \big\rbrace \\ \end{aligned}

となる。最後２つの等式はright scalar multiplicationの定義および変数変換である。
$K_{\lambda, \mu}$から定まる$F$も凸集合となっており、Theorem 5.3（Rockafellar 1970）から$k(x)$が凸関数であることが言える。

参考文献

Tyrrell Rockafellar, R, 1970 p40

【備忘】Uniqueness of Solution In Linear Programming

Linear Programming

本論文の概要

　本論文は与えられた線形計画問題の最適解がただ一つであるかどうかを確認する方法を示したものである。確認するにあたっては、最適解がただ一つであることの必要十分条件から導かれる線形計画問題を解けば良い。このブログでは主問題に焦点を絞っているが、論文では双対問題に対しても同値条件を考えている。主問題と双対問題の両方の同値条件を満たしていれば、問題を記述する全てのパラメータの十分小さい摂動に対して安定していると言える。

取り組む問題

線形計画問題
\begin{eqnarray*} &\min_{x \in \mathbb{R}^{n}} p^{T}x \tag{1} \\ \text{s.t.} \quad &Ax = b \quad Cx \ge d \end{eqnarray*}
双対問題
\begin{eqnarray*} &\max_{u,v} b^{T}u + d^{T}v \tag{2} \\ \text{s.t.} \quad &A^{T}u + C^{T}v = p \quad v \ge 0 \end{eqnarray*}
記法

　$x, p \in \mathbb{R}^{n} \quad b,u \in \mathbb{R}^{m} \quad d ,v \in \mathbb{R}^{k} \quad A \in \mathbb{R}^{m \times n} \quad C \in \mathbb{R}^{k \times n}$とする。
　次に添え字集合$J, K, L$を定義する。$x^{*}$を$(1)$の、$(u^{*}, v^{*})$の最適解とし、また$C_i$を行列$C$の$i$行目の行ベクトルとする。

\begin{eqnarray*} J &=& \lbrace i \mid C_i x^{*} = d_i \rbrace \\ K &=& \lbrace i \mid v_i^{*} >0 \rbrace = \lbrace i \mid C_i x^{*} = d_i, v_i^{*} > 0 \rbrace \\ L &=& \lbrace i \mid C_i x^{*} = d_i, v_i^{*} = 0 \rbrace \end{eqnarray*}

双対変数の定義域を考えると、$J = K \cup L$が成立する。

内容

定理１
定理

線形計画問題$(1)$が最適解$x^{*}$を唯一つ持つための必要十分条件は、$x^{*}$が最適化問題$(3)$の最適解となることである。$(3)$は、$(1)$のコスト関数に十分小さい大きさ$\epsilon > 0$で任意の方向$q \in \mathbb{R}^{n}$に摂動を加えた最適化問題である。

\begin{eqnarray*} &\min_{x \in \mathbb{R}^{n}} (p + \epsilon q)^{T}x \tag{3} \\ \text{s.t.} \quad &Ax = b \quad Cx \ge d \end{eqnarray*}

証明（方針）

　証明の詳細は割愛し、方針のみを述べる。$(1)$が最適解を唯一つしか持たないことの必要十分条件として、$(1), (2)$の制約条件を満たし、コスト関数を改善する実行可能解の係数倍が存在しないことが挙げられる。この必要十分条件を、過去の報告を用いて種々変形していくことで、題意を示すことができる。

定理2

線形計画問題$(1)$の最適解を$x^{*}$とする。次の命題は同値である：

  1. $x^{*}$が唯一の最適解である。

  2. $\forall q \in \mathbb{R}^{n}$に対して、$x^{*}$が$(3)$の最適解になるような$\epsilon > 0$が存在する。

  3. 次を満たす$x$は存在しない：$Ax = 0, \quad C_J x \ge 0, \quad p^{T} x \le 0, \quad x \neq 0.$

  4. 次を満たす$x$は存在しない：$Ax = 0, \quad C_K x = 0, \quad C_L x \geq 0, \quad x \neq 0.$

  5. $[A^{T} \ C_K^{T} \ C_L^{T}]$の行は線形独立で、次を満たす$x$は存在しない：$Ax = 0, \quad C_K x = 0, \quad C_L x \geq 0.$

  6. 任意の$a, c, h \in \mathbb{R}$に対して、集合$\lbrace x | Ax = a, C_K x = c, C_L x \geq h \rbrace$は空か有界である。

  7. 任意の$q \in \mathbb{R}^{n}$に対して、次の線型方程式を満たす$\epsilon > 0$が存在する：$A^{T} u + C_J^{T} v_J = p + \epsilon q, \quad v_J \geq 0.$

  8. 任意の$s \in \mathbb{R}^{n}$に対して、次の線型方程式を満たす$(u, v_K, v_L)$が存在する：$A^{T} u + C_K^{T} v_K + C_L^{T} v_L = s, \quad v_L \geq 0.$

  9. 任意の$s \in \mathbb{R}^{n}$に対して、次の線型方程式を満たす$(u, v_K, v_L)$が存在する：$A^{T} u + C_K^{T} v_K + C_L^{T} v_L = s, \quad v_L > 0.$

  10. $[A^{T} \ C_K^{T} \ C_L^{T}]$の行は線形独立で、次の線型方程式を満たす$(u, v_K, v_L)$が存在する：$A^{T} u + C_K^{T} v_K + C_L^{T} v_L = 0, \quad v_L > 0.$

証明

（1. ⇨ 2.の証明）
　定理１より成立する。

（1. ⇨ 7.の証明）
　定理１より、1.が成立するならば$x^{*}$は$(3)$の最適解である。$(3)$の双対問題や強双対問題を考えると、$A^{T}u + C^{T}v = p + \epsilon q \quad b^{T} u + d^{T} v = (p + \epsilon q) x^{*} \quad v \ge 0$が導かれ、このことから$v^{T}(C x^{*} - d) = 0$が得られる。$v_i \ge 0$であり、$i \notin J$に対して$v_i = 0$であるから、$C v^{*} = C_J v_J^{*}$となる。よって$A^{T}u + C^{T}_J v_J = p + \epsilon q$が成立する。

（7. ⇨ 4.の証明）
　4.の式を満たす$x$が存在するとして、背理法を用いて証明する。任意の$q$に対して7.が成立することから、$q = 0, -x$とする。それぞれを満たす$(u, v)= (u^{0}, v^{0}), (u^{*}, v^{*} )$に対して、$p = Au^{0} + C_J^{T} v_J^{0} = A u^{*} + C_J^{T} v_J^{*} - \epsilon x$が成立する。7.より$(u^{*}, v^{*} )$を$(2)$の最適解であるとして、この式を基に、$x$を両辺に掛け算すると、

\begin{eqnarray*} 0 > - \epsilon x^{T} x &=& x^{T} A(u^{0} - u^{*} ) + x^{T} C_J^{T} (v_J^{0} - v_J^{*} ) \\ & = & (u_0 - u^{*} )^{T} A x + (v_J^{0} - v_J^{*} )^{T} C_J x \\ & = & (u_0 - u^{*} )^{T} A x + (v_K^{0} - v_K^{*} )^{T} C_K x + (v_L^{0})^{T} C_L x \\ & \ge & 0 \end{eqnarray*}

が成立する。最後の不等式は、4.の仮定および$v^{*}_L = 0$を使用した。

（4. ⇨ 1.の証明）
　1.が成立しないとして、背理法を用いて証明する。$(1)$の異なる最適解を$x^{*},x^{**} $、$x^{*} \neq x^{**} $とする。$J$の添字集合に対応する最適解を$x^{**}$とすると、それぞれ共に$(1)$の最適解であるから、

\begin{eqnarray*} p^{T}( x^{*} - x^{**} ) = 0 \\ A ( x^{*} - x^{**} ) = 0 \\ C_J ( x^{*} - x^{**} ) \ge 0 \end{eqnarray*}

が成立する。$C_J ( x^{*} - x^{**} ) = (<{C_K}_i, x^{*} - x^{**} >, \cdots, <{C_K}_{|K|}, x^{*} - x^{**} >, <{C_L}_{i}, x^{*} - x^{**} >, \cdots, <{C_L}_{|L|}, x^{*} - x^{**} >)^{T} \ge 0$であり、4.が成立することから、$K$は非空であり、$\exists i \in K \quad \text{s.t.} \quad <{C_K}_{i}, x^{*} - x^{**} >0$となる。ここで、

\begin{eqnarray*} 0 &=& p^{T}( x^{*} - x^{**} ) = (A u^{**} + C_J^{T} v_J^{**})( x^{*} - x^{**} ) \\ &=& {v_K^{**}}^{T} C_K ( x^{*} - x^{**} ) \\ &>& 0 \end{eqnarray*}

となることから、4.から導かれる式に反する。よって、1.は成立する。

（4. ⇨ 5.の証明）
　対偶を考える。5.は 「$[A^{T} \ C_K^{T} \ C_L^{T}]$が線型独立ならば、$Ax = 0, \quad C_K x = 0, \quad C_L x \geq 0.$を満たす$x$が存在する」であり、明らかに4.の否定「$Ax = 0, \quad C_K x = 0, \quad C_L x \geq 0.$を満たす$x$が存在する」は成立する。よって示された。

（5. ⇨ 10.の証明）
　Tucker's Theorem of the Alternativeより、10.を満たす$v_K \ge 0, v_L >0$が存在する。よって示された。

（10. ⇨ 9.の証明）
　10.より$[A^{T} \ C_K^{T} \ C_L^{T}]$のランクはその行数と一致し、非自明解$(u, v_K, v_L > 0)$を持つことから列数よりも小さい。また、その拡大係数行列のランクは行数と一致するため、$A^{T} u(s) + C_K^{T} v_K(s) + C_L^{T} v_L(s) = s$を満たす解$(u(s), v_K(s), v_L(s))$は存在する。
　ここで、十分大きい正数$\lambda$を用いると、$(u(s) + \lambda u, v_K(s) + \lambda v_K, v_L(s) + \lambda v_L >0)$は9.を満たす。よって示された。

（9. ⇨ 8.の証明） 　9.の解は明らかに8.を満たすため、成立する。

（8. ⇨ 4.の証明）
　　対偶を考え、4.が成立するとして、8.の式に$x^{T}$を左から掛け合わせる。

\begin{eqnarray*} x^{T} s = (Ax)^T u + (C_K x)^{T} v_K + (C_L x)^T v_L = (C_L x)^T v_L \ge 0 \end{eqnarray*}

　となる。ここで$s$は任意であるため、$s=-x(\neq 0)$とすると、上の式は成立しない。よって示された。

（8. ⇔ 6.の証明）
　6. が成立し有界ならば、$\forall s \in \mathbb{R}^{n}$に対して、それを定義域に持つ次の線形計画問題は最適解を持つ。

\begin{eqnarray*} \min s^{T} x \quad \text{s.t.} \quad x \in \lbrace x | Ax = a, C_K x = c, C_L x \geq h \rbrace \end{eqnarray*}

　これは次の双対問題が解を持つことと同値である。

\begin{eqnarray*} \max_{u, v_K, v_L} a^{T} u + c^{T} v_K + h^{T} v_L \quad \text{s.t.} \quad A^{T} u + C_K^{T} v_K + C_L v_L, \quad v_L \ge 0 \end{eqnarray*}

　つまり、この定義域である8.は解を持つ。
　（注意：原著では6.が空である場合を考えていない。空ならば、8.は非有界もしくは空となる思われる。)

（3. ⇔ 7.の証明）
　3. と同値な線形不等式系：

\begin{eqnarray*} -sx > 0, \quad (C_J, -p^{T}) x \ge 0, \quad Ax =\boldsymbol{0}, \quad \forall s \in \mathbb{R}^n \end{eqnarray*}

　が解$x$を持たないことは、Motzkin’s Theorem of the Alternativeより、

\begin{eqnarray*} -s \eta + (C_J, -p^{T})^{T} (v_{J}, \epsilon) + A^{T}y = \boldsymbol{0}, \quad (v_{J}, \epsilon) \ge \boldsymbol{0}, \quad \eta >0 \end{eqnarray*}

　が解を持つことと同値である。この式の順番を並び替え、$s = p+q$とすると

\begin{eqnarray*} A^{T}y + C_J^{T} v_J = p(\eta + \epsilon) + \eta q, \quad (v_{J}, \epsilon) \ge \boldsymbol{0} \end{eqnarray*}

　となり、両辺を$1+\epsilon, \eta$について変数変換するなど整理すれば7.の式と一致し、題意は示される。

解がただ一つであることの確認方法

　定理２の条件5.および10.が最も確認しやすく、以下にはそれぞれの条件を使った問題とその確認方法を示す。
（変数に定義のないものや、コスト関数の取り方に工夫の余地があると思われるので、以下は原文ママとする。）

（条件5.）
　$[A^{T} \ C_K^{T} \ C_L^{T}]$の行は線形独立である場合、次の最大化問題の最適値が$0$である。

\begin{eqnarray*} \max e^{T} C_L x \\ \text{s.t.} \quad &Ax = 0 \quad C_K x = 0 \quad C_L x \ge 0 \end{eqnarray*}

（条件10.）
　$[A^{T} \ C_K^{T} \ C_L^{T}]$の行は線形独立である場合、次の最大化問題は上に非有界である。

\begin{eqnarray*} \max \delta \\ \text{s.t.} \quad &A^T u + C_K^{T} v_k + C_L^{T} v_L = 0, \quad v_L \ge e \delta \end{eqnarray*}

参考文献

Mangasarian, Olvi. Uniqueness of solution in linear programming. University of Wisconsin-Madison Department of Computer Sciences, 1978.