【最適化】1変数ニュートン法 C++コード付き
はじめに
今回は無制約最小化問題に対する数値解法(反復法)である、1変数ニュートン法のC++コードを公開します。例題として
を考えます。もちろん、最適解は です。反復法とは、適当な初期値 を定め、
という漸化式によって値を更新していき、最終的に最適解 へと収束させるような方法のことです。ここで、 が探索方向、 がステップのサイズです。つまり、反復法を構成しているのは探索方向とステップのサイズです。ニュートン法の場合、探索方向とステップのサイズは一度に求まります。お得ですね。
参考文献
参考文献は『最適化と変分法』pp.44-49、『最適化とその応用』pp.151-155、それと以下のPDFファイルです。どちらの本も非常に参考になります。いつも読んでいます。
http://www-optima.amp.i.kyoto-u.ac.jp/~nobuo/Ryukoku/2002/course7.pdf
- 作者: 寒野善博,土谷隆,東京大学工学教程編纂委員会
- 出版社/メーカー: 丸善出版
- 発売日: 2014/10/22
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
- 作者: 矢部博
- 出版社/メーカー: 数理工学社
- 発売日: 2006/04
- メディア: 単行本
- 購入: 1人 クリック: 10回
- この商品を含むブログ (11件) を見る
ニュートン法とは?
ニュートン法とは、目的関数(最小化しようとする対象)に対する1次の最適性条件
に対して、非線型方程式に対するニュートン法を適用したもの、と言えます。詳しく説明しましょう。現在 にいて だけ進んだ時に1次の最適性条件を満たすとしましょう。つまり、
です。我々が知りたいのは です。上の式を1次までテイラー展開すると
となります。 はヘシアンと呼ばれています。ここから について解くと
となります。これが1変数ニュートン法における探索方向とステップサイズです。一度に求まります。多変数の場合は行列になるので逆行列をかける必要があります。この を用いて
のように値を更新して収束させればよいのです。詳細は上記の参考文献を見てください。
C++コード
#include <iostream> #include <cmath> #include <fstream> #include <iomanip> #include <vector> using namespace std; //function// inline double f(double x) { return (x-2.0)*(x-2.0); } //gradient// inline double fx(double x) { return 2.0*(x-2.0); } //hessian// inline double fxx(double x) { return 2.0; } //Newton method// inline double Newton(double x) { return -fx(x)/fxx(x); } int main() { double err=pow(10.0,-10.0);//tolerance double x=10.0;//initial value double d;//direction and step size //iteration// for(int i=0;i<10000;i++) { cout<<i<<" "<<abs(fx(x))<<endl; //convergence check// if(abs(fx(x))<err) break; d=Newton(x); //update// x=x+d; } cout<<endl; cout<<x<<endl; return 0; }
【最適化】最急降下法(アルミホ条件による直線探索)C++コード付き
はじめに
今回は無制約最小化問題に対する数値解法(反復法)である、最急降下法(アルミホ条件による直線探索)のC++コードを公開します。例題として
を考えます。もちろん、最適解は です。反復法とは、適当な初期値 を定め、
という漸化式によって値を更新していき、最終的に最適解 へと収束させるような方法のことです。ここで、 が探索方向、 がステップのサイズです。つまり、反復法を構成しているのは探索方向とステップのサイズです。今回は、探索方向としては最急降下法を、ステップのサイズとしてはアルミホ(Armijo)条件による直線探索を行います。
参考文献
参考文献は『最適化と変分法』pp.35-43、『最適化とその応用』pp.130-139、それと以下のPDFファイルです。どちらの本も非常に参考になります。いつも読んでいます。
http://www-optima.amp.i.kyoto-u.ac.jp/~nobuo/Ryukoku/2002/course7.pdf
- 作者: 寒野善博,土谷隆,東京大学工学教程編纂委員会
- 出版社/メーカー: 丸善出版
- 発売日: 2014/10/22
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
- 作者: 矢部博
- 出版社/メーカー: 数理工学社
- 発売日: 2006/04
- メディア: 単行本
- 購入: 1人 クリック: 10回
- この商品を含むブログ (11件) を見る
最急降下法とは?
最急降下法とは、勾配が最もきつい方向、すなわちgradのマイナス方向に進んでいく手法のことを言います。勾配のきつい方向に進んでいくと底の部分にたどり着けるというわけです。ただし、場合によってはこの方法は効率がよくありません。そのような場合にも適用できる手法として共役勾配法などがあります。詳細は上記の参考文献を見てください。
アルミホ条件による直線探索とは?
アルミホ(Armijo)条件による直線探索とは、スタート地点での傾きに1より小さい係数をかけた傾きを使って直線をひき、その直線よりも関数の値が下回るようなステップサイズを採用する、というものです。上記のPDFの図がわかりやすいです。詳細は上記の参考文献を見てください。
C++コード
#include <iostream> #include <cmath> #include <fstream> #include <iomanip> #include <vector> using namespace std; //function// inline double f(double x) { return (x-2.0)*(x-2.0); } //gradient// inline double fx(double x) { return 2.0*(x-2.0); } //steepest gradient// inline double SteepGrad(double x) { return -fx(x); } //Armijo line search// inline double Armijo(double x, double d, double alpha, double c1, double rho) { alpha=1.0; for(int i=0;i<10000;i++) { if(f(x+d*alpha)<=f(x)+c1*fx(x)*d*alpha) break; else alpha=rho*alpha; } return alpha; } int main() { double err=pow(10.0,-10.0);//tolerance double x=10.0;//initial value double alpha;//step size double rho=0.4;//contraction ratio double c1=0.001;//coefficient double d;//direction //iteration// for(int i=0;i<10000;i++) { cout<<i<<" "<<abs(fx(x))<<endl; //convergence check// if(abs(fx(x))<err) break; //step size search// d=SteepGrad(x);//direction alpha=Armijo(x,d,alpha,c1,rho);//step size; //update// x=x+alpha*d; } cout<<endl; cout<<x<<endl; return 0; }
【Navier-Stokes方程式に対する数値計算手法】サイトマップ
はじめに
Navier-Stokes方程式を数値的に解く手法には、非常に多くのバリエーションがあり、どれから勉強してよいのか?何が違うのか?と悩む方も多いことでしょう。私もその一人でした。そこで、Navier-Stokes方程式に対する数値計算手法の本を山ほど買い込みだんだん勉強して参りました。その成果は当ブログの記事となっています。それらの記事をまとめたのがこのページです。
Navier-Stokes方程式に対する数値計算手法には、大きく分けるとMAC法系列の解法とSIMPLE法系列の解法があります。なのでMAC法とSIMPLE法を理解すれば、他の方法は簡単に理解できると思います。まだ書いている途中ですが、だんだんアップデートしていくのでよろしくお願いします。
MAC法
全ての始まりです。
フラクショナルステップ法
SIMPLE法
完全陰解法
SIMPLEC法
SIMPLE法を改良した方法です。
SIMPLER法
SIMPLE法を改良した方法です。
SIMPLEST法
SIMPLE法を改良した方法です。
PISO法
流れ関数ー渦度法
勉強中です。二次元の流れにしか適用できません。計算機の性能が今ほど優れていなかった時代によく用いられていました。当時の教科書には大体載っていましたが、現在では論文や本で見ることはほとんどありません。
文献まとめ
文献まとめを作成中です。なるべく網羅的なものにしたいです。
- 作者: 河村哲也
- 出版社/メーカー: 朝倉書店
- 発売日: 2014/03/26
- メディア: 単行本
- この商品を含むブログ (1件) を見る
- 作者: 桑原邦郎,河村哲也
- 出版社/メーカー: 朝倉書店
- 発売日: 2005/03/01
- メディア: 単行本
- クリック: 6回
- この商品を含むブログを見る
- 作者: 河村哲也,平野広和,池川昌弘,川原睦人,登坂宣好,数値流体力学編集委員会
- 出版社/メーカー: 東京大学出版会
- 発売日: 1995/02
- メディア: 単行本
- この商品を含むブログを見る
【英語】"Sapiens: A Brief History of Humankind"『サピエンス全史』【9冊目】
どんな本か?
Yuval Noah Harari 著 "Sapiens: A Brief History of Humankind" を読み終わりました。日本語の題は『サピエンス全史』です。ホリエモンも絶賛していました。この本は、人類はどうして発展することができたのか、そして今後人類はどうなっていくのか、を歴史上の例をふんだんに用いながら解説した名著です。歴史にとどまらず、あらゆる分野の知識を縦横無尽に使いこなしており、Jared Diamond の "Guns, Germs, and Steel: The Fates of Human Societies" を読んだ時のような知的興奮を覚えました。
Sapiens: A Brief History of Humankind
- 作者: Yuval Noah Harari
- 出版社/メーカー: Vintage
- 発売日: 2015/04/30
- メディア: ペーパーバック
- この商品を含むブログ (4件) を見る
- 作者: ユヴァル・ノア・ハラリ,柴田裕之
- 出版社/メーカー: 河出書房新社
- 発売日: 2016/09/08
- メディア: 単行本
- この商品を含むブログ (50件) を見る
- 作者: ユヴァル・ノア・ハラリ,柴田裕之
- 出版社/メーカー: 河出書房新社
- 発売日: 2016/09/08
- メディア: 単行本
- この商品を含むブログ (24件) を見る
- 作者: ユヴァル・ノア・ハラリ
- 出版社/メーカー: 河出書房新社
- 発売日: 2016/09/16
- メディア: Kindle版
- この商品を含むブログ (15件) を見る
Guns, Germs, and Steel: The Fates of Human Societies
- 作者: Jared Diamond
- 出版社/メーカー: W W Norton & Co Inc
- 発売日: 2017/03/07
- メディア: ペーパーバック
- この商品を含むブログを見る
要点
3つの革命によりホモ・サピエンスが発展してきたことが解説されます。3つの革命とは、「認知革命」、「農業革命」、「科学革命」です。認知革命により、ホモ・サピエンスは虚構を信じることができるようになり、互いに協力することができるようになりました。その例が、国家、法人、通貨、宗教などです。どれも実際には存在していないものです。農業革命により、生産に余剰が生じ、その余剰を充てることにより、専門的な職業が誕生しました。また、人口が増加しました。科学革命により、ホモ・サピエンスは自らの力を増大させることができることに気付きました。進歩と成長により資本主義が生まれます。科学、資本主義、帝国の相互作用によりホモ・サピエンスは発展し、その結果として現在の我々の世界があります。そして、今後ホモ・サピエンスは、この力(遺伝子工学)を使ってホモ・サピエンスをホモ・サピエンスでない新たな人、superhuman(超人)を生み出していくことが示唆され、この本は終わります。
英文の難易度
原著はヘブライ語とのことですが、英語版も著者が書いているそうです。著者はヘブライ大学の教授で歴史学者です。もちろん校閲は入っているでしょうが、ノン・ネイティブなのにこんなに流暢な英文を書けるとは驚きです。英文の構文は素直で読みやすいです。ただ、単語のレベルは非常に高いです。現在私の語彙力は20,000前後あるはずですが、それでも1ページあたり3語ほど未知語が出てきます。しかし、逆に言えば単語の勉強にもなるということです。内容が面白いことは言うまでもありません。どんな単語が出てくるかについては、今後別の記事でまとめる予定です。
おわりに
Yuval Noah Harari 著 "Sapiens: A Brief History of Humankind" を読みました。今は Jared Diamond "Upheaval: How Nations Cope with Crisis and Change" を読んでいます。日本語訳はまだないのですが『激変』とすればよいでしょうか。この本は、フィンランド、チリ、日本、ドイツ、オーストラリア、インドネシア、アメリカの7つの国を取り上げ、それぞれの国がどのように危機的な状況を乗り越えたかが分析されます。今後の世界を生きていくうえで非常に有益な内容です。どうも、「選択的に変化すること」がキーワードですね。こちらも読み終えたらまとめていきます。
Upheaval: How Nations Cope with Crisis and Change
- 作者: Jared Diamond
- 出版社/メーカー: Allen Lane
- 発売日: 2019/05/07
- メディア: ペーパーバック
- この商品を含むブログを見る
【英語】『ハイレベル実戦英文法』Section 1
はじめに
最近英語を受験生に教える機会があったのですが、あまりに英文法問題がわからなくて恥ずかしくなりました。なので、英文法を復習していこうと思います!今回から手元にあった、『ハイレベル実戦英文法』という本を1 Sectionずつ読んでいこうと思います。
- 作者: 猿谷宣弘
- 出版社/メーカー: ベレ出版
- 発売日: 2017/08/19
- メディア: 単行本
- この商品を含むブログを見る
この本は、「英語の新聞を読むことができるようになるための英語の文法事項をまとめたもの」とのことなのでちょうどよいです。私たちが忘れている文法事項も出てくると思います。
Section 1 -ing の用法 進行形、名詞化、形容詞化
ingの用法が例文とともにまとめてあります。気になった点を例文とともにまとめておきます。
- 代名詞が動名詞の意味上の主語になる場合には所有格でも目的格でもよい
なんとなく所有格しか認識していませんでした。目的格でもよいのですね。つまり
What are the advantages and disadvantages of his not keeping a driver's license?
What are the advantages and disadvantages of him not keeping a driver's license?
のようにhisでもhimでもよいのです。
forの後は普通の名詞がくるものだと思い込んでいました。つまり
People often blame parents for their children's being rude in a public place.
のように所有格にできるんですね。
おわりに
自分は英文法を理解していると思い込んでいたことがわかりました…頑張って復習します!!!
【数値流体力学】勾配を制限するか、それとも流束を制限するか
MUSCL法など勾配制限関数(slope limiter)を用いる方法は、再構築した単調な値を用いて数値流束を計算するので単調な流束(1次風上差分、HLLなど)を使う必要があります。一方、高次の流束を使う場合は、解の単調性を保つために、流束自体を流束制限関数で制限する必要があります。