数学、物理、機械学習
数学、物理、機械学習を中心に、
理論、応用例を紹介していきたいと思います
また、参考図書や論文なども適宜載っけていきます。
趣味、大学入試、院試や資格などの勉強にお使いください。
あと、時々無関係な話題が入ってきますが、無視してください。
しっかり学ぶ数理最適化の演習解説ー2.7:相補性定理と、その応用
線形計画法において、主問題とその双対問題が実質的に等しい値を持つことが強双対定理により要請される。では、値ではなく最適解同士にはどういう関係があるのだろうか?以下の相補性定理がそれに対するアンサーとなる。
・相補性定理
以下、とし、かつの全ての行ベクトルが一次独立であるとする。
主問題を
とし、その双対問題を
とする。このとき、それぞれの実行可能解がともに最適解であるための必要十分条件は、
が成り立つことである。この条件を相補性条件と呼ぶ。
・応用事例として
これを用いて問題を解いてみよう(自己流の解き方のため間違っていたらご容赦ください)。例えば、「しっかり学ぶ数理最適化」の演習2.7は下記のような問題である。
ただし、とする。
まずの場合は、明らかにが最適解で、値をとる。
次に、の場合を考える。まず相補性定理が使えるかを吟味する。行列はベクトルとなり一行のみの行列となるので、明らかに一次独立となる。また、制約の数もなのでを満たしているため、相補性定理が適用できる。
演習2.7の主問題は制約が1つのみであるため双対問題の方が解きやすいはずである。双対問題は
であり、制約条件を整理するととなるため、この問題の最適解はで、値をとる。
相補性定理により、主問題の実行可能解が最適解であることは、すべてのに対してが成り立つことと同値である。今、であるため、を最大化するの集合をで定義すると、相補性条件は
と等価になる。従って、これを満たし、かつ実行可能となるため制約を満たすような解が最適解となる。
以上より、主問題の最適解はかつなる任意の解であって、このとき値をとる(の結果もこれに含めることができる)。
なお上記の最適解は、の要素が1つのみの場合は1つに限られる。すなわち、その要素をとして最適解はに一意に決まる。の要素が2つ以上の場合は最適解は無数に存在する。
相補性定理の証明は下記の参考書を参照されたい。また、上記では等式制約の主問題を考えたが、不等式制約の場合の相補性条件についても参考書では述べられている。
しっかり学ぶ数理最適化の演習解説ー2.9:ファルカスの補題から強双対定理を示す
線形計画問題のファルカスの補題から、強双対定理を証明する。なお、これは「しっかり学ぶ最適化」の演習問題2.9である。解答は自己流なので間違っていたらご容赦ください。強双対定理およびファルカスの補題については、下記を参照のこと。
su-butsu-kikaigakusyuu.hatenablog.com
以下、証明
双対問題は
と表せる。これに実行可能解が存在するとすると、弱双対定理により、が成り立つ。
よって、強双対定理を示すには、あるが
を満たすことを示せばよい。
この条件を別の表現で表すと、、、を用いて、
と等価になる。
ファルカスの補題により、これは
と等価となる。
この条件式を整理すると、
を得る。すなわち、の左辺を満たすような全てのに対して、右辺が成り立つことを示せば強双対定理を示すことができる。以下、を示す。
の場合
とした上で、の各式をで除算すると、下記を得る。
この左辺は元の主問題の制約条件そのものであり、が実行可能解であるという仮定となる。今、題意によりは最適解であるから、上式の右辺は常に成り立つ。
の場合
は以下のように書き直せる。
この左辺を仮定すると、は主問題の制約を満たすことが容易に示され、実行可能解となる。。今、題意によりは最適解であるから、であり、となるため上式の右辺が成り立つ。
以上によりが示された。
しっかり学ぶ数理最適化の演習解説ー2.8:弱双対定理からファルカスの補題を示す
線形計画問題の弱双対定理から、ファルカスの補題を証明する。なお、これは「しっかり学ぶ最適化」の演習問題2.8である。解答は自己流なので間違っていたらご容赦ください。弱双対定理およびファルカスの補題については、下記を参照のこと。
su-butsu-kikaigakusyuu.hatenablog.com
以下、証明
ファルカスの補題の(1)が成り立つとき、(2)が成り立たないことを示す
(1)の仮定の下では、主問題
は実行可能解を持つ。ここで、特にとすると、これの双対問題は
となる。
よって、を仮定すると、このは双対問題の実行可能解となる。よって、弱双対定理より、
が成り立つ。従って、とを満たすようなは存在せず、ファルカスの補題の(2)が成り立たないことが示された。
ファルカスの補題の(2)が成り立つとき、(1)が成り立たないことを示す
(2)の仮定の下では、双対問題
は実行可能解を持つ。この解をとすると、これを正定数倍したもまた上記の制約を満たすため実行可能解となる。
今、(2)の仮定によりであるため、はとすればに発散し、上記の双対問題は非有界となる。
弱双対定理の系により、「主問題と双対問題のいずれか一方が非有界なら、他方は実行不能となる」ため、
主問題
は実行不能となる。よって、ファルカスの補題の(1)が成り立たないことが示された。
以上により、ファルカスの補題が示された。
ファルカスの補題、弱双対定理、強双対定理
線形計画法による最適化で特に重要な概念が、ファルカスの補題、弱双対定理、強双対定理である。これらにより、主問題とその双対問題を解くことの関係性が示される。
以下、これらの定理をまとめる。
・ファルカスの補題(Farkas' lemma)
行列とベクトルが与えられる。この時、次のいずれか一方の条件のみが成り立つ。
(1) を満たす解が存在する。
(2) を満たす解が存在する。
このように二律背反な関係にある形の定理を、一般に二者択一定理と呼ぶ。なお、上記を必要十分条件の形式の主張に言い換えると、下記のようになる。
(1') を満たす解が存在する。
と、
(2') ならば、が成り立つ。
は等価である。
ファルカスの補題には色々証明方法があり、後述する弱双対定理を用いて示すこともできる(おいおい記載する)。
・主問題と双対問題
弱双対定理をステートする前に、線形計画問題における主問題と双対問題をまとめておく。以下、とし、かつの全ての行ベクトルが一次独立であるとする。
主問題は、
双対問題は、
とする。
・弱双対定理
がそれぞれ主問題と双対問題の実行可能解ならば、下記が成り立つ。
これより、以下の系も成り立つ。
弱双対定理の証明は、各制約条件を組み合わせれば容易に示すことができる。
・強双対定理
主問題に最適解が存在すれば、双対問題にも最適解が存在し、
とが成り立つ。
つまり、主問題に最適解が存在すれば、主問題と双対問題が実質的に等価になることを示している。強双対定理には複数のステートメントが存在し、例えば「主問題と双対問題に実行可能解が存在する」場合にもこの同値な関係が成り立つ。
強双対定理により、主問題の次元が制約条件数よりも十分小さい場合には、双対問題の方が次元が小さく解きやすくなるためこちらを解く方が楽になる。
この定理はファルカスの補題を用いて証明することができる(おいおい記載)。
以上の記述は下記の参考書を参考にした。
参考書紹介(数理系) 2021年版
☆数学
学部レベルの数学を中心に、オススメの参考書を紹介します。
線形代数
・チャート式シリーズ 大学教養 線形代数
高校向け参考書メーカのチャート式が、大学向けにも参考書を書いた!問題も豊富で分かりやすい、新しいスタンダード教科書。
微積分
統計
- 作者: 東京大学教養学部統計学教室
- 出版社/メーカー: 東京大学出版会
- 発売日: 1991/07/09
- メディア: 単行本
- 購入: 158人 クリック: 3,604回
- この商品を含むブログ (79件) を見る
- 作者: 東京大学教養学部統計学教室
- 出版社/メーカー: 東京大学出版会
- 発売日: 1992/08/01
- メディア: 単行本
- 購入: 26人 クリック: 308回
- この商品を含むブログ (22件) を見る
- 作者: 二宮嘉行,大西俊郎,小林景,椎名洋,笛田薫,田中研太郎,岡田謙介,大屋幸輔,廣瀬英雄,折笠秀樹,日本統計学会,竹村彰通,岩崎学
- 出版社/メーカー: 東京図書
- 発売日: 2013/04/08
- メディア: 単行本
- この商品を含むブログ (5件) を見る
・確率統計演習 (2)
複素解析、フーリエ変換、特殊関数
・詳解物理応用数学演習
上記分野の練習問題がいっぱい
・フーリエ解析入門
数学科向け。同シリーズの別本もオススメ。
微分方程式
・詳解物理応用数学演習
・偏微分方程式入門 (基礎数学)
確率微分方程式
・確率微分方程式とその応用
・確率微分方程式
- 作者: ベァーントエクセンダール,Bernt Oksendal,谷口説男
- 出版社/メーカー: シュプリンガー・フェアラーク東京
- 発売日: 1999/03
- メディア: 単行本
- 購入: 3人 クリック: 13回
- この商品を含むブログ (4件) を見る
グレブナー基底
・グレブナー道場
参考書紹介(量子物理、統計物理編) 2021年版
☆物理(量子物理、統計物理編)
大学レベルの物理を中心に、オススメの参考書を紹介します。分野の偏りは愛嬌。
量子力学
・量子力学 (KS物理専門書)
満遍なく基本的な話題に触れてるし、そこそこ練習問題が豊富。
- 作者: 猪木慶治,川合光
- 出版社/メーカー: 講談社
- 発売日: 1994/03/24
- メディア: 単行本
- 購入: 2人 クリック: 9回
- この商品を含むブログ (17件) を見る
場の理論(物性向け)
・凝縮系物理における場の理論
物性のほぼ全ての分野の話題を扱ってるのではなかろうか。特にメソ系、非平衡の記載が詳しい。
- 作者: Alexander Altland,Ben Simons,新井正男,井上純一,鈴浦秀勝,田中秋広,谷口伸彦
- 出版社/メーカー: 吉岡書店
- 発売日: 2012/06
- メディア: 単行本
- 購入: 1人 クリック: 1回
- この商品を含むブログを見る
- 作者: Alexander Altland,Ben Simons,新井正男,井上純一,鈴浦秀勝,田中秋広,谷口伸彦
- 出版社/メーカー: 吉岡書店
- 発売日: 2012/12
- メディア: 単行本
- この商品を含むブログを見る
各物性値のミクロな導出において、グリーン関数の計算法が事細かに掲載。こいったコンセプトの本は意外に少なかった気がする(フェッターワレッカは字が読みにくいし)。
物性物理のための場の理論・グリーン関数 2018年 06 月号 [雑誌]: 数理科学 別冊
- 作者: 小形正男
- 出版社/メーカー: サイエンス社
- 発売日: 2018/06/21
- メディア: 雑誌
- この商品を含むブログを見る
熱、統計力学
・熱統計力学(物理学基礎シリーズ)
掲載してるコードが化石を通り越して石油になりつつあるが、入門書としてはGOOD。
・大学演習 熱学統計力学
量子統計は少なめだが、古典の話題は詳しすぎるくらい網羅してる。問題数が無限にあるので院試の際にも使える。日頃の業務にも使ってます。
・統計力学
難しめだが、含蓄深い記述が多い。非平衡詳しい。
相転移
・相転移 臨界現象の統計物理学
量子アニーリングの父の本。相転移に関する大体の基本事項は網羅。
磁性
・磁性体の統計理論
厳密解、強磁性体&反強磁性体の局在スピン、スピン波の振る舞いが網羅的に詳しく載ってる。
・磁性と超伝導の物理
ミクロな視点からの磁性発現や、遍歴電子系との絡みが詳しい。最終的には近藤効果や超伝導にたどり着く。
スピントロニクス
基本理論から、最近の話題まで内容が豊富。
理論面が詳しい。特に非平衡グリーン関数を用いた輸送等。同著者の前書「スピントロニクス理論の基礎」より内容が整理されてる印象。
量子輸送
・半導体量子輸送物性
メゾ系の話題が豊富。実験の話も多い。
・量子輸送
非平衡グリーン関数を用いて、量子デバイスの輸送現象を解説する名著。ち
- 作者: Supriyo Datta,森藤正人,森伸也,鎌倉良成
- 出版社/メーカー: 丸善
- 発売日: 2008/09/20
- メディア: 単行本
- 購入: 1人 クリック: 2回
- この商品を含むブログ (1件) を見る
- 作者: Supriyo Datta,森藤正人,鎌倉良成,森伸也
- 出版社/メーカー: 丸善
- 発売日: 2008/12/27
- メディア: 単行本
- 購入: 1人 クリック: 1回
- この商品を含むブログを見る
量子コンピュータ
・量子コンピューティング ―基本アルゴリズムから量子機械学習まで―
量子ゲート方式のアルゴリズム紹介。基本的なアルゴリズムはもちろん、最近の量子機械学習にも言及。
・量子アニーリングの基礎
量子コンピュータのうち、量子アニーリングに焦点を当てた本。安いし、理論の詳細が載ってる。最近流行りつつある量子機械学習の説明もあり。
量子アニーリングの基礎 (基本法則から読み解く物理学最前線 18)
- 作者: 西森秀稔,大関真之,須藤彰三,岡真
- 出版社/メーカー: 共立出版
- 発売日: 2018/05/19
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
量子制御
・量子測定と量子制御
古典制御〜量子制御の対応がわかりやすい。
量子測定と量子制御 2016年 03 月号 [雑誌] (数理科学 別冊)
- 作者: 沙川貴大,上田正仁
- 出版社/メーカー: サイエンス社
- 発売日: 2016/03/22
- メディア: 雑誌
- この商品を含むブログ (1件) を見る
超伝導
・超伝導入門
格好の入門書。
統計力学の問題として記述されており、物性に詳しくなくても取り組みやすい。
結晶と物性
・物質の対称性と群論
大判の本なので、結晶構造の理解が容易。配位子場のミクロな計算をもっと練習したい人は、次の参考書をチェック。
・配位子場理論とその応用
これ以上詳しい本は存在しない。