しっかり学ぶ数理最適化・第２章３.１節 - 双対問題
双対問題
線形計画問題において、最適値を求めるのが困難な際に重要となるのが、最適値の上界と下界を求めることです。最大化問題において、ある実行可能解が得られた時、それは必ず最適値以下であるはずです。つまり得られた実行可能解を下界として捉えることができます。では上界を求めるにはどうすれば良いのでしょうか？上界を求める一つの手段として2.3.1節で述べられる双対問題による手法があります。双対問題を考えることで最大化問題を最小化問題に置き換えることができ、最適値の上界を求めることができるというなんとも不思議な求め方です。賢いですね。まあただ実行可能解を１つ得ることが容易でない問題もあるということで、世の中そんな甘くはなさそうですが...
本節では、やや天下り的な具体例から手法の流れを把握し、その後に一般化を行うことで双対問題を用いた最適値の上界・下界を求める手法に関してみていきます。
数式が非常に多くアレルギーが出そうになりましたがよくよく見てみると別に大した式じゃありません。数式ばかりに目がいきがちですが、著者の梅谷先生はこの節で行っていることを簡潔にまとめてくださってます。まとめると以下です。
制約条件の１次結合を用いて線形計画問題の最適値の良い上界を求めた
理解する前にこの文言を見ても「？」だったでしょうが、理解した後に聞くとなんとも簡潔な表現に聞こえます。後の2.3.2節では緩和問題に触れており、双対問題の導出にはこちらを利用することの方が多いようです。気が向いたらまとめます（多分向かない）
しっかり学ぶ数理最適化輪読回・第２章
数理最適化勉強会も始めました
僕は数学があまり得意ではないので、こういう勉強には気が乗らないのですが、数学から逃げずに少しずつでも工学をやる上で必要な素地を身につけていかなければならないな、と最近ひしひしと感じています。同期もみんなひしひしと感じているようで、数学ゼミを開講する運びになりました。
集合と位相、圏論あたりのマジの基礎からやっていた時期もあったのですが、M2になったしより実用的な分野の勉強会をしたいねってことで数理最適化を学ぶことになりました。個人的には、MLPシリーズの機械学習のための連続最適化をやりたかったりしたのですが、多数決の結果ラボの勉強会で扱う書籍は「しっかり学ぶ数理最適化」に決定しました。カバーしてる範囲がどのくらい違うのかもあまり把握してないですが、とても重厚で名著感が凄まじいため、どうせいつか読む本だと思ってます。なので気合入れて読みたいですね。
「気合入れて読みたいですね」と言ったそばから「最後の生産計画問題サボっとるやんけ」とツッコまれそうですが、疲れたので仕方ないっす。人間限界あるんで。
線形計画問題
目的関数も、制約条件も線形な関数で表現できるものを線形計画問題と呼ぶようです。この章では定式化を行っているだけに留まっていて、それをどのように解くのかまでは議論していません。線形計画問題を解く手法は線形計画法と呼ばれており、後の章で述べられる単体法などに代表される手法を用いることで多くの場合効率的に大域的な最適解を得られるようです。 僕は担当ではなかったので資料を作ってないですが、2.1.2節以降では線形でない問題も近似を行うことで線形計画問題に落とし込めるよ、という話をしており（全てではない）、実用上、様々な問題を線形計画で解けちゃうようです。
この章は読んでいて、確かに、まぁ、そうなるな、みたいな感想をもった章で特別難しい概念や理解に苦しむ定式化なんかはありませんでした。ですがよくよく問題を見てみると「この問題も線形関数だけで表現できるのか！」みたいな発見があって楽しかったです。次回は緩和問題と双対定理に関して発表するのでがんばります。
経済・ファイナンスデータの計量時系列分析 勉強会（１）
時系列解析のお勉強会を始めました
ハミルトン先生の時系列解析本を読めるくらい賢かったらよかったんですが、残念ながら僕はそこまで賢くないので、まだ頑張ったら読めそうな沖本先生の本を読むことになりました。ハミルトン本は日本語版が絶版になってるっぽいのも相まって学習難度が高いっすね。英語版は話に聞く限り無料のPDFがインターネッツに落っこちてるらしい。
ところで期待値の表記に違和感がある。僕の理解不足か？
僕のスライドでいうところの8Pです。分散、標準偏差のところ見てください。大括弧っていらないんすか？（本書がそのような表記になってたためそのまま載せてます）。自己共分散に関しては大括弧ついてるんすけども違いは何なんでしょう。よくわからん。時系列解析以前に基本的な確率統計をもっとガッツリ深くまで勉強した方がいい気もしてますが、時間は有限なのでね.... それと有識者から聞いた話によるとPRMLの13章あたりで（時）系列データが扱われているとのことなのでそちらもセットで読み込んでいきたいっすね。8章のグラフィカルモデルの途中で読むの止まってる。頑張ろう。
ブログ始めようかな
軽い自己紹介
2021年4月現在、東京大学大学院でコンピュータサイエンス（以下、CS）を学んでいる者です。スマートシティを大きなテーマとして扱う研究室に所属しています。旅行が大好きです。学部の頃は横国で機械工を専攻していたのですが、専門に全く興味が持てずダラダラと生活を送っていたのですが、投機目的で興味をもったBitcoin、Blockchainを調べてるうちにCSそのものに魅入られて気づいたら専門が変わってました。
何をかくか
主にIT関連の技術に関するetc...いわゆるテックブログ...を書いていたら褒めてください。
なぜ書くか
明確な目的は特にないです。まじでなんとなくです。強いて言えば日本語の訓練です。
大学院も２年目に入ってなんか新しいこと始めようかなみたいなアレです。研究をやれ。
タイトルにある通り「始めようかな」くらいの感じなのでこれが最初で最後の投稿になるかもしれません。いやこういうのってあんまし敷居高くしないほうがいいと思うんですよね。友達見ててもまじでブログ更新しないし。気が向いたら投稿します。ゆるく、ゆるく、ひたすらにゆるく。
