Scilabで最急降下法 その2

Scilabで最急降下法 その1では1変数の関数 f(x) に対して最急降下法を用いて最小値を求めました。今回は2変数の関数 f(x,y) について最小値を求めます。

001_20170509143114675.png
Fig.1: 最急降下法による最小値探査



具体的には二次元のガウス関数に-1を掛けた関数を f(x,y) とします。
\begin{equation}
f(x,y)=\frac{1}{2 \pi \sigma_1 \sigma_2 \sqrt{1-\rho^2}}\exp\left\{-\frac{1}{2(1-\rho^2)}\\
\times\left(\frac{(x-\mu_1)^2}{\sigma_1^2}-2\rho\frac{(x-\mu_1)(y-\mu_2)}{\sigma_1\sigma_2} +\frac{(y-\mu_2)^2}{\sigma_2^2}\right) \right\}
\end{equation}
ここで
\begin{equation}
\rho=\frac{\sigma_{12}}{\sigma_1\sigma_2}
\end{equation}

最急降下法の値の更新は二次元の場合は以下のように行います。
\begin{equation}
\begin{pmatrix}
x^{(k+1)}\\
y^{(k+1)}
\end{pmatrix}
=
\begin{pmatrix}
x^{(k)}\\
y^{(k)}
\end{pmatrix}
-\alpha
\begin{pmatrix}
\frac{\partial f(x^{(k)}, y^{(k)})}{\partial x}\\
\frac{\partial f(x^{(k)}, y^{(k)})}{\partial y}
\end{pmatrix}
\end{equation}
停止条件は ∂f/∂x < ε かつ ∂f/∂y < ε とすればよいと思います。

clear;

// *** 二次元ガウス分布 ***
mu1 = 3; mu2 = 1;
mu = [mu1; mu2];
sigma1 = sqrt(10); sigma2 = sqrt(10); sigma12 = 5;
SIGMA = [sigma1^2, sigma12; sigma12, sigma2^2];
rho = sigma12 / (sigma1 * sigma2);
function z = func(x, y)
z = -1 ./ (2 * %pi * sigma1 * sigma2 * sqrt(1 - rho)) ..
.* exp(-1 / (2 .* (1 - rho^2)) ..
.* ((x - mu1) .^ 2 ./ (sigma1 ^ 2) - 2 .* rho .* (x - mu1) .* (y - mu2) ./ (sigma1 * sigma2) + ((y - mu2) .^ 2) ./ (sigma2 ^ 2)))
endfunction


// *** 数値微分 ***
h = 1E-3;
function dzx = dfx(x, y)
dzx = (func((x+h), y) - func((x-h), y)) ./ (2 * h)
endfunction

function dzy = dfy(x, y)
dzy = (func(x, (y+h)) - func(x, (y-h))) ./ (2 * h)
endfunction

// *** グラフのプロット ***
x = linspace(-10,10);
y = linspace(-10,10);
[X,Y] = ndgrid(x,y);
Z = func(X,Y);
// 色の設定
//xset("colormap",jetcolormap(64))
// xset("colormap",graycolormap(64))
// Sgrayplot(x,y,Z)
xset("fpf"," "); // 等高線に値を表示しない
contour2d(x,y,Z,10);
xmin = min(X); xmax = max(X); ymin = min(Y); ymax = max(Y);
zoom_rect([xmin,ymin,xmax,ymax]);




// *** 最小値の計算 ***
// 停止条件
err = 1E-5;
a = 200;
// 初期値
x = -4; y = 4;
z = func(x, y);
dx = dfx(x, y);
dy = dfy(x, y);
plot(x, y, "xk");
// 最小値の計算
while ((abs(dx) > err) | (abs(dy) > err))
x = x - a * dx;
y = y - a * dy;
dx = dfx(x, y);
dy = dfy(x, y);
plot(x, y, ".r");
end
// 計算結果
x, y
plot(x, y, "xk");


関連エントリ




参考URL




付録


このエントリで使用したファイルを添付します。ファイル名末尾の".txt"を削除して、"_"を"."に変更すれば使えるはずです。(参考:ねがてぃぶろぐの付録)


参考文献/使用機器




フィードバック



にほんブログ村 その他趣味ブログ 電子工作へ

 ↑ 電子工作ブログランキング参加中です。1クリックお願いします。


コメント・トラックバックも歓迎です。 ↓      


 ↓ この記事が面白かった方は「拍手」をお願いします。

tag: Scilab 最適化 最小値 最大値 

Scilabで最急降下法 その1

Scilabで何らかの関数 f(x) の最小値(あるいは最大値)を計算することを考えます。関数の値を計算するのが簡単な場合は x の定義域全体で f(x) を計算した後 minmax を使うという方法もあります。しかしながら f(x) の計算にそれなりの時間がかかる場合や f(x, y) といったように引数がたくさんある場合は効率的ではないと思います。

そこで今回は最急降下法のアルゴリズムを利用して f(x) の最小値を求めるということをやってみます。

001_20170507020049254.png

Fig.1: 最急降下法での最小値探索。上が関数f(x)の値、下が微分値f'(x)



最小値を求める関数


さて、実際に最小値を求める関数 f(x) ですが、今回は単純にガウス関数に -1 を掛けたものにします。
\begin{equation}
f(x) = - \frac{1}{\sqrt{2\pi\sigma^2}} \exp \left( -\frac{(x-\mu)^2}{2\sigma^2}\right)
\end{equation}
当然ながら、f(x)が最小になるのは x = μ のときです。

最急降下法


高校の数学で習ったとおり f(x) が最大値や最小値(や極値)をとるときその微分は f'(x) = df(x)/dx = 0 となります。最急降下法は、関数の微分を計算しその傾きが大きいほうへ f'(x)=0 となる x を探すアルゴリズムです。具体的には以下の手続きを繰り返します。
  1. x の初期値 x(0) を決める
  2. f'(x) < ε なら終了
  3. x(k+1) = x(k) - αf'(x(k))
  4. 2.に戻る

実際には α や ε を上手に決めておく必要があります。αは勾配の方向にどの程度進むかを決めるパラメータ(下記Scilabスクリプトではa)で、εは計算の終了条件を決めるパラメータ(下記Scilabスクリプトではerr)です。

Scilabスクリプト


clear;

// *** 一次元ガウス分布 ***
function y = func(x)
mu = 3;
sigma = 1;
y = -1 / sqrt(2*%pi*sigma^2) * exp(-1 * ((x - mu) .^ 2) ./ (2*sigma^2))
// y = cos(x)
endfunction

// *** 数値微分 ***
function y = dfunc(x)
h = 1E-4;
y = (func(x+h) - func(x-h)) ./ (2*h)
endfunction

// *** グラフのプロット ***
X = linspace(0,6);
Y = func(X);
dY = dfunc(X);
subplot(2,1,1);
plot(X, Y);
subplot(2,1,2);
plot(X, dY);

// *** 最小値の計算 ***
// 停止条件
err = 1E-3;
a = 0.5;
// 初期値
x = 1;
y = func(x);
dx = dfunc(x);
subplot(2,1,1);
plot(x, y, ".r");
subplot(2,1,2);
plot(x, dx, ".r");

// *** 最小値の計算 ***
while abs(dx) > err
x = x - a * dx;
dx = dfunc(x);
y = func(x);
subplot(2,1,1);
plot(x, y, ".r");
subplot(2,1,2);
plot(x, dx, ".r");
end

// *** 計算結果 ***
x
subplot(2,1,1);
plot(x, y, "xk");


参考URL




付録


このエントリで使用したファイルを添付します。ファイル名末尾の".txt"を削除して、"_"を"."に変更すれば使えるはずです。(参考:ねがてぃぶろぐの付録)


参考文献/使用機器




フィードバック



にほんブログ村 その他趣味ブログ 電子工作へ

 ↑ 電子工作ブログランキング参加中です。1クリックお願いします。


コメント・トラックバックも歓迎です。 ↓      


 ↓ この記事が面白かった方は「拍手」をお願いします。

tag: Scilab 最適化 最小値 最大値 

FC2カウンター
カテゴリ
ユーザータグ

LTspiceAkaiKKRmachikaneyamaScilabKKRPSoC強磁性CPAPICOPアンプecalj状態密度モンテカルロ解析常微分方程式odeトランジスタインターフェースDOSスイッチング回路定電流PDS5022分散関係半導体シェルスクリプトレベルシフト乱数HP6632AR6452Aブレッドボード温度解析トランジスタ技術可変抵抗I2Cバンドギャップ数値積分セミナー確率論反強磁性バンド構造偏微分方程式非線形方程式ソルバ絶縁熱設計A/DコンバータシュミットトリガPWscfマフィンティン半径フォトカプラ三端子レギュレータLM358カオスGW近似LEDISO-I2C補間74HC4053TL431アナログスイッチサーボ数値微分発振回路カレントミラーPC817CUSB直流動作点解析標準ロジックアセンブラVESTAbzqlty電子負荷パラメトリック解析2ちゃんねるチョッパアンプ単振り子量子力学BSch開発環境トレーナーバトルFFTスーパーリーグ基本並進ベクトルブラべ格子LDAイジング模型ポケモンGOQuantumESPRESSOキュリー温度Quantum_ESPRESSO仮想結晶近似Maxima六方最密充填構造熱伝導スピン軌道相互作用抵抗失敗談相対論GGA繰り返しラプラス方程式VCAコバルトgfortran状態方程式不規則合金スイッチト・キャパシタTLP621ランダムウォークQSGWFETewidth最適化位相図SMPcygwinスレーターポーリング曲線シュレディンガー方程式固有値問題条件分岐Writer509awkデータロガーマントル自動計測ガイガー管詰め回路MCU三角波ダイヤモンド過渡解析ハーフメタルubuntu格子比熱UPSQNAPFXA-7020ZR井戸型ポテンシャルテスタ熱力学LM555平均場近似UbuntuNE555最大値第一原理計算最小値TLP521フェルミ面ZnOCIF差し込みグラフ起電力ゼーベック係数TLP552fsolveスーパーセルブラウン運動OpenMPxcrysden不純物問題擬ポテンシャルハイパーリーグgnuplotc/a全エネルギー状態図multiplot合金P-10磁気モーメントcif2cellPWgui半金属BaOOPA2277ウルツ鉱構造edelt2SC1815リジッドバンド模型ナイキスト線図岩塩構造スワップ領域PGA二相共存重積分ノコギリ波ルチル構造CapSenseSICデバイ模型quantumESPRESSOフィルタフォノン電荷密度Excel円周率初期値ヒストグラムGimpシンボル凡例線種interp1不規則局所モーメントウィグナーザイツ胞縮退疎行列文字列PvP入出力軸ラベルグラフの分割specx.fifort正規分布マテリアルデザインヒストグラム確率論等高線ジバニャン方程式境界条件連立一次方程式両対数グラフ片対数グラフHiLAPW熱拡散方程式Crank-Nicolson法陰解法化学反応三次元トラックボールMAS830LCK1026PC直流解析TS-112TS-110トランスPIC16F785MBEEAGLEAACircuit固定スピンモーメントLMC662FSM等価回路モデルパラメータ・モデルフラクタルマンデルブロ集合L10構造fcc面心立方構造クーロン散乱キーボードRealforce最小二乗法日本語関数フィッティングTeX非線型方程式ソルバ結晶磁気異方性負帰還安定性

最新コメント
リンク

にほんブログ村 その他趣味ブログ 電子工作へ