数理最適化の基礎：テイラー展開とMax-Plus代数の実装

Oct 18, 2024 Academic

#optimization #taylor-series #max-plus-algebra #matlab

背景 (Background)

「限られた予算と時間の中で、最大の利益を生み出す生産計画はどれか？」「AIが最も賢く推論できるように、数億個のパラメータをどう調整すればよいのか？」。これらは全て、与えられた条件の中で最も良い答えを見つけ出す「数理最適化」という問題に帰着します。世の中のあらゆる効率化の裏には、目に見えない多次元の「山の頂上（最大値）」や「谷の底（最小値）」を目指して一歩ずつ進む最適化アルゴリズムが存在しています。本研究では、現代の機械学習やディープラーニングの学習プロセスの根幹でもある「最急降下法」や「ニュートン法」といった代表的な最適化手法に焦点を当て、微分の力（勾配やヘッセ行列）を使って複雑な数理の谷をいかに速く、正確に下っていくかを数学的かつ実践的に探求します。

導入と目的

現実社会における様々な制約のもとで最適な選択肢を求める問題は最適化問題と呼ばれる。最適化問題を解くための数理的手法は数理最適化と称され、産業界から学術界に至るまで幅広い分野で活用されている。本プロジェクトの目的は、数理最適化を現実問題に適用する際に不可欠となる基礎理論と思考プロセスを習得し、実装を通じてその有効性を検証することである。

プロジェクトの一環として、線形計画問題のモデリングや、無制約最適化問題を解くための最急降下法およびニュートン法（勾配ベクトルとヘッセ行列に基づく）をMATLAB上でスクラッチから実装した。これにより、ヘッセ行列や勾配に関する理論的な理解を深めるとともに、近似手法や行列演算アルゴリズムの挙動についても詳細な分析を行った。

基礎理論と実装環境

数値解析ソフトウェアであるMATLABを用いてアルゴリズムの実装と検証を行った。MATLABは行列演算を基礎として設計されており、数式やデータを直感的に扱い、結果を可視化する能力に長けている。

本研究で用いた主な機能と環境は以下の通りである。

プロセッサ：APPLE M1
メモリ：8GB
開発言語：MATLAB
活用機能：行列演算、プロット機能による可視化、数値解析アルゴリズムの開発

関数の近似とテイラー展開の評価

最適化において関数の局所的な振る舞いを理解することは重要である。そこで、正弦関数と逆正接関数についてテイラー展開による近似アルゴリズムを実装し、近似の精度と収束性を評価した。

正の整数 $n$ に対して関数 $f_{n} (x)$ と $g_{n} (x)$ をそれぞれ以下のように定義した。

f_{n} (x) = k = 0 \sum n - 1 \frac{( - 1 ) ^{k}}{( 2 k + 1 )!} x^{2 k + 1}

g_{n} (x) = k = 0 \sum n - 1 \frac{( - 1 ) ^{k}}{2 k + 1} x^{2 k + 1}

正弦関数の近似結果

適当な座標軸を設定し、 $f_{n} (x)$ の挙動を $n$ を変化させながらプロットした。

f_n(x)とsin xの図

グラフから、 $[- 2 π, 2 π]$ の範囲において $n$ の値が大きくなるにつれて関数 $f_{n} (x)$ が $sin (x)$ をより正確に近似する様子が確認できる。 $n$ が小さい場合は $x$ の絶対値が大きい領域で誤差が顕著になるが、 $x = 0$ を中心とした展開であるため、中心付近での近似精度は常に高い。

実装したMATLABコードは以下の通りである。

function [output] = fx(x,n)
% sinxテイラー展開
output=0;
for k=0 : n-1
    output = output+(((-1)^k)/factorial(2*k+1))*power(x,(2*k+1));
end
end

逆正接関数の近似結果

同様に、 $g_{n} (x)$ についてもプロットによる評価を行った。

g_n(x)とarctan xの図

逆正接関数の場合も、 $n$ の増加に伴って近似精度が向上する。ただし、 $f_{n} (x)$ の収束範囲が広いのに対し、 $g_{n} (x)$ は $[- 1, 1]$ の範囲で良好な近似を示すことがわかる。この比較から、展開する関数によって収束半径が異なる性質を持つことが視覚的に確認できた。

function [output] = gx(x,n)
% テイラー展開
output=0;
for k=0 : n-1
    output = output+(((-1)^k)/(2*k+1))*power(x,(2*k+1));
end
end

Max-Plus代数に基づく行列演算の実装

数理最適化の応用例として、Max-Plus代数的な行列演算を行う関数を実装した。 $(m, l)$ 型の行列 $A = (a_{ij})$ と $(l, n)$ 型の行列 $B = (b_{ij})$ に対して、新しい $(m, n)$ 型行列を計算するアルゴリズムである。

各成分は以下のように計算される。

tMP (A, B) の i 行 j 列成分は max (a_{i 1} + b_{1 j}, a_{i 2} + b_{2 j}, \dots, a_{i l} + b_{l j})

アルゴリズムの実装

三重ループ構造を用いて各組み合わせの和を計算し、最大値を更新していくアプローチを採用した。

function [output1] = tMP(A,B)
output1=zeros(size(A,1),size(B,2));
for i=1:size(A,1)
    for j=1:size(B,2)
        max_val=-Inf;
        for k=1:size(A,2)
            tem_val=A(i,k)+B(k,j);
            if tem_val>max_val
                max_val=tem_val;
            end
        end
        output1(i,j)=max_val;
    end
end
end

この実装では、出力行列を zeros で事前に初期化することでメモリ確保の効率化を図っている。計算の最適化としては、内側のループの演算結果を一時的に保存したり、MATLAB特有のベクトル化演算を用いることで、さらなる処理速度の向上が見込める。

乱数を用いた検証

生成した乱数行列を用いて本アルゴリズムの動作検証を行った。

乱数行列を用いたtMP(A,B)の実行結果

アルゴリズムは正しく機能し、複雑な条件を持つ行列演算も適切に処理できることが確認された。

結論と今後の展望

本プロジェクトを通じて、MATLABを活用した数値解析および数理最適化手法の実装経験を積むことができた。テイラー展開による関数近似の可視化は、アルゴリズムの収束性や誤差の性質を直感的に理解する上で非常に有効であった。

さらに、勾配ベクトルとヘッセ行列に基づく最急降下法やニュートン法の実装を通し、理論上の数式を実際のプログラムに落とし込む過程で生じる課題（計算量、メモリ効率、収束条件の設定など）を深く考察することができた。多変数関数の最適化問題において、これらの手法がどのように機能するかを体験的に学べたことは大きな収穫である。今後は、機械学習やより高度な数理モデルの最適化問題に対しても、これらの知識とアルゴリズムを応用していく。