数理最適化のソースを表示

[[File:MaximumParaboloid.png|right|thumb|f(''x'', ''y'') = −(''x''² + ''y''²) + 4 で与えられる[[放物面]]のグラフ。(0, 0, 4) での最大値が赤い点で示されている。]]

[[数学]]の[[計算機科学]]や[[オペレーションズリサーチ]]の分野における'''数理最適化'''（すうりさいてきか、{{Lang-en-short|mathematical optimization}}）または'''数理計画法'''（{{Lang-en-short|mathematical programming|links=no}}）とは、（ある条件に関して）最もよい元を、利用可能な集合から選択することをいう<ref>"[http://glossary.computing.society.informs.org/index.php?page=nature.html The Nature of Mathematical Programming] {{webarchive|url=https://web.archive.org/web/20140305080324/http://glossary.computing.society.informs.org/index.php?page=nature.html |date=2014年3月5日 }}," ''Mathematical Programming Glossary'', INFORMS Computing Society.</ref>。

最も簡単な[[最適化問題]]には、ある許された集合から入力をシステマティックに選び、[[函数]]の値を計算することによる{{仮リンク|実数函数|en|function of a real variable}}の[[極値|最大化と最小化]]がある。最適化理論とその手法の、他の形式への一般化は[[応用数学]]の広範な分野をなすものである。より一般に、最適化はある与えられた定義域（あるいは制約の集合）についてある目的函数の「利用可能な最も良い」値を見つけることも含む。そのような目的函数と定義域は多様な異なるタイプのものも含む。

== 最適化問題 ==
{{main|最適化問題}}

最適化問題は、次のように表現される：
:''与えられるもの''：ある[[集合]] ''A'' から[[実数]]への[[函数]] ''f'' : ''A'' <math>\to</math> '''R''' 
:''目的''：''A'' 内のすべての ''x'' に対して最小化問題であれば ''f''(''x''<sub>0</sub>) ≤ ''f''(''x'') を満たす ''A'' 内の元 ''x''<sub>0</sub>（最小点）と、あるいは最大化問題であれば ''f''(''x''<sub>0</sub>) ≥ ''f''(''x'') を満たす ''A'' 内の元 ''x''<sub>0</sub>（最大点）を見つけること。

このような問題は[[最適化問題]]（optimization）あるいは'''数理計画問題'''（mathematical programming）（[[プログラミング (コンピュータ)|コンピュータプログラミング]]とは直接的には関係ないが、例えば[[線型計画法]]では用いられる）と呼ばれる。多くの実世界での問題や理論的問題は、一般的な枠組みでモデル化される。[[物理学]]や[[コンピュータビジョン]]の分野における、この手法による問題は、エネルギー最小化（energy minimization）と呼ばれることもある。この場合、函数 ''f'' の値はモデル化されるシステムのエネルギーを表す。

典型的に集合 ''A'' は[[ユークリッド空間]] '''R'''<sup>''n''</sup> の[[部分集合]]であり、しばしばある[[制約 (数学)|制約]]の集合によって特徴づけられ、''A'' の元は求められる等式あるいは不等式を満たす必要がある。''f'' の[[定義域]] ''A'' は探索空間（search space）あるいは選択集合（choice set）あるいは[[実行可能領域]]と呼ばれ、''A'' の元は可能解（candidate solution, feasible solution）あるいは実行可能解と呼ばれる。

函数 ''f'' は、'''目的函数'''（objective function）や'''損失函数'''（loss function）、'''費用函数'''（cost function）、'''効用函数'''（utility function）、'''適合函数'''（fitness function）、'''エネルギー函数'''（energy function）あるいは'''エネルギー汎函数'''（energy functional）と呼ばれる<ref>W. Erwin Diewert  (2008).  "cost functions," ''The New Palgrave Dictionary of Economics'', 2nd Edition [http://www.dictionaryofeconomics.com/article?id=pde2008_C000390&edition=current&q= Contents].</ref>。目的函数を最小化（あるいは最大化）する可能解は、最適解と呼ばれる。

数学においてよくある最適化問題は、最小化に関するものである。最小化問題においては，「可能領域が凸領域でかつ目的函数がそこに於ける凸関数」となっていない場合には，一般に複数の局所最小解が存在しうる。ここで　x<sup>*</sup>　が局所最小解であるとは、ある定数 δ &gt; 0 が存在して、

:<math>\|\mathbf{x}-\mathbf{x}^*\|\leq\delta;\,</math>

を満たすような任意の x に対して次が成立することをいう。

:<math>f(\mathbf{x}^*)\leq f(\mathbf{x}).</math>

すなわち、点 x<sup>*</sup> はその（十分小さな）近傍内での最小点である。局所最大解も同様に定義される。

対比して問題の可能領域''A''全体における最小点のことを大域（的な）最小点ということがある。

== 記号 ==

最適化問題では、しばしば特殊な記号が用いられる。ここではそれらのいくつかを紹介する。

=== 函数の最小値と最大値 ===

次の記号を考える：

:<math>\min_{x\in\mathbb R}\; (x^2 + 1).</math>

これは ''x'' を[[実数]]の集合 <math>\mathbb R</math> から選んだときの目的函数 <math>x^2 + 1</math> の最小値を意味する。この場合の最小値は <math>x = 0</math> のときの <math>1</math> である。

同様に、記号

:<math>\max_{x\in\mathbb R}\; 2x</math>

は、任意の実数 ''x'' に対する目的函数 2''x'' の最大値を意味する。この場合、目的函数は非有界なのでそのような最大値は存在せず、「無限大」あるいは「定義されない」が答えとなる。

=== 最適入力引数 ===
{{Main|arg max}}

次の記号を考える。

:<math>\underset{x\in(-\infty,-1]}{\operatorname{arg\,min}} \;(x^2 + 1).</math>

あるいは、次の同値なものを考える。

:<math>\underset{x}{\operatorname{arg\,min}} \; (x^2 + 1), \; \text{subject to:} \; x\in(-\infty,-1].</math>

これは、区間 <math>(-\infty,-1]</math> において目的函数 ''x''<sup>2</sup>&nbsp;+&nbsp;1 を最小化する[[引数]] ''x'' 自身の値を与える（その函数の最小値がどのような値であるかはここでは問題とされない）。この場合、''x'' = 0 は不可能、すなわち[[実行可能領域]]に属さないため、答えは ''x'' = -1 となる。

同様に

:<math>\underset{x\in[-5,5], \; y\in\mathbb R}{\operatorname{arg\,max}} \; x\cos(y)</math>

あるいは

:<math>\underset{x, \; y}{\operatorname{arg\,max}} \; x\cos(y), \; \text{subject to:} \; x\in[-5,5], \; y\in\mathbb R</math>

は、''x'' が区間 <math>[-5,5]</math> に属するという制約の下で、目的函数 <math>x\cos(y)</math> の値を最大化する <math>(x,y)</math> のペアを意味する（再び、その関数の最大値については問われていない）。この場合の解は、すべての[[整数]] ''k'' に対する (5, 2k[[Pi|π]]) と (−5,(2k+1)π) である。

'''arg min''' と '''arg max''' はしばしば、'''argmin''' および '''argmax''' と書かれることもあり、それらは「最小値の引数」および「最大値の引数」を意味する。

== 歴史 ==
[[ピエール・ド・フェルマー|フェルマー]]と[[ジョゼフ＝ルイ・ラグランジュ|ラグランジュ]]は解が最適であるための条件を微分積分学を利用して求めた。一方で[[アイザック・ニュートン|ニュートン]]と[[カール・フリードリヒ・ガウス|ガウス]]は最適解に向かって収束させる反復法を提唱した。

ある種の最適化問題に関する[[線型計画法]]という語は[[ジョージ・ダンツィク]]によるものである。一方で、1939年に[[レオニート・カントロヴィチ]]によって多くの理論が構築された（この文脈における「計画法（programming）」は[[プログラミング (コンピュータ)|コンピュータ・プログラミング]]とは異なり、アメリカ軍隊によって訓練や[[物流]]のスケジュールを表すために用いられていた "program" （講演会などの"プログラム"と同様の意味）が語源である。ダンツィクは当時その研究をしていた）。ダンツィクは1947年に Simplex Algorithm（[[シンプレックス法]]）を出版し、[[ジョン・フォン・ノイマン]]は同年に[[線型計画法|双対性]]の理論を発展させた。

{{雑多な内容の箇条書き|date=2024年12月|section=1}}
その他の主要{{誰2|date=2024年12月}}な数理最適化の研究者を以下に挙げる：
{{Div col||20em}}
* [[今野浩]]
* [[リチャード・E・ベルマン]]
* [[ロジャー・フレッチャー (数学者)|ロジャー・フレッチャー]]
* {{仮リンク|ロナルド・A・ハワード|en|Ronald A. Howard}}
* {{仮リンク|フリッツ・ジョン|en|Fritz John}}
* [[ナレンドラ・カーマーカー]]
* {{仮リンク|ウィリアム・カルーシュ|en|William Karush}}
* {{仮リンク|レオニード・カチヤン|en|Leonid Khachiyan}}
* {{仮リンク|バーナード・コープマン|en|Bernard Koopman}}
* [[ハロルド・クーン]]
* [[ラースロー・ロヴァース]]
* {{仮リンク|アルカディ・ネミロフスキ|en|Arkadi Nemirovski}}
* {{仮リンク|ユーリ・ネステロフ|en|Yurii Nesterov}}
* [[ボリス・ポリャク]]
* [[レフ・ポントリャーギン]]
* [[ジェームス・レネガー]]
* {{仮リンク|R・ティレル・ロックフェラー|en|R. Tyrrell Rockafellar}}
* [[コルネリス・ロース]]
* {{仮リンク|ナウム・Z・ショール|en|Naum Z. Shor}}
* [[ミカエル・J・トッド]]
* [[アルバート・タッカー]]
{{Div col end}}
<!--In fact, some mathematical programming work had been done previously... (anyone? - Gauss did some stuff here), Gauss developed the method of least squares, which is an optimization method. -->

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

<!--
== 論文誌 ==
* [http://www.springer.com/mathematics/journal/10589 ''Computational Optimization and Applications'']
* [https://www.novapublishers.com/catalog/product_info.php?products_id=6353 Journal of Computational ''Optimization in Economics and Finance'']
* [http://www.journals.elsevier.com/journal-of-economic-dynamics-and-control/ ''Journal of Economic Dynamics and Control'']
* [http://www.siam.org/journals/siopt.php ''SIAM Journal on Optimization'' (SIOPT)] and  [http://www.siam.org/journals/siopt/policy.php Editorial Policy] 
* [http://www.siam.org/journals/sicon.php ''SIAM Journal on Control and Optimization'' (SICON)] and [http://www.siam.org/journals/sicon/policy.php Editorial Policy]

== 学習用参考図書など ==
外国語図書
* Philip E. Gill, Walter Murray and Margaret H. Wright: "Practical Optimization", Emerald group publishing, ISBN 978-0-12-283952-8 (1982).
* G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (eds.): "Optimization", Elsevier, (1989).
* Stanislav Walukiewicz："Integer Programming", Springer，ISBN 978-9048140688（1990年12月）。
* R. Fletcher: "Practical Methods of Optimization", 2nd Ed.,Wiley (2000).
* Panos M. Pardalos："Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems"，Springer，ISBN 978-1441948298（2000年7月）。
* Xiaoqi Yang (編), K. L. Teo (編), Lou Caccetta (編)："Optimization Methods and Applications"，Springer, ISBN 978-0792368663 (2001年4月1日）。
* Panos M. Pardalos (編), Mauricio G. C. Resende (編)："Handbook of Applied Optimization"、Oxford Univ Pr on Demand，ISBN 978-0195125948（2002年2月22日）。
* [https://web.stanford.edu/~boyd/cvxbook/ Boyd and Vandenberghe: "Convex Optimization", Cambridge Univ. Press (2004).]
* Jorge Nocedal and Stephen J. Wright: "Numerical Optimization", 2nd Ed., Springer (2006).
* Wil Michiels, Emile Aarts, Jan Korst: "Theoretical Aspects of Local Search",　Springer, ISBN 978-3642071485（2006年11月28日）。
* Der-San Chen, Robert G. Batson, Yu Dang：”Applied Integer Programming: Modeling and Solution”，Wiley，ISBN 978-0470373064（2010年1月12日）。
* Mykel J. Kochenderfer and Tim A. Wheeler: "Algorithms for Optimization", The MIT Press, ISBN 978-0262039420 (2019). ※ 邦訳版あり。
* Vladislav Bukshtynov: "Optimization: Success in Practice", CRC Press (Taylor & Francis), ISBN 978-1-032229478 (2023) .
* Rosario Toscano: "Solving Optimization Problems with the Heuristic Kalman Algorithm: New Stochastic Methods", Springer，ISBN 978-3-031-52458-5 (2024年3月22日).

日本語図書
* J.コワリック、M.R.オズボーン：「非線形最適化入門」、培風館 (1970年12月10日).
* 今野浩、山下浩：「非線形計画法」、日科技連出版社 (ORライブラリー 6)、ISBN 978-4-81715306-7（1978年3月)。
* 福島雅夫：「非線形最適化の理論」、産業図書（講座・数理計画法4)、(1980年11月19日)。
* 坂和正敏：「非線形システムの最適化：一目的から多目的へ」、森北出版、ISBN 4-627-91250-1 (1986年5月1日)。
* 茨木俊秀、福島雅夫：「FORTRAN77 最適化プログラミング」、岩波書店、ISBN 4-00-007700-7 (1991年4月10日)。
* 茨木俊秀、福島雅夫：「最適化の手法」、共立出版(情報数学講座)、ISBN 4-320-02664-0（1993年7月20日)。
* 中山恵子：「非線形計画と非線形固有値問題」、中京大学経済学部（1995年3月30日)。
* G.L. Nemhauser (編), M.J. Todd (編), A.H.G. Rinnooy Kan (編)：「最適化ハンドブック」、[[朝倉書店]]、ISBN 978-4-25412102-5（1995年10月1日)。
* 矢部博、八巻直一：「非線形計画法」（ＦＤ付き）、朝倉書店 (応用数値計算ライブラリ)、ISBN 978-4-254-11489-8（1999年6月10日)。
* 長尾智晴：「最適化アルゴリズム」、昭晃堂、ISBN 4-7856-3112-0 (2000年5月29日)。
* 坂和正敏：「離散システムの最適化：一目的から多目的へ」、森北出版、ISBN 4-627-91701-5 (2000年5月31日)。
* 田村明久、村松正和：「最適化法」、共立出版 (工系数学講座 17)、ISBN 978-4-320-01616-3（2002年4月20日)。
* 久保幹雄、田村明久、松井知己(編)：「応用数理ハンドブック」、朝倉書店、ISBN 978-4-254-11141-5（2002年11月15日)。
* 金谷健一：「これなら分かる最適化数学―基礎原理から計算手法まで」、共立出版、ISBN 978-4-320-01786-3 (2005年9月1日)。
* 矢部博：「工学基礎 最適化とその応用」、数理工学社、ISBN 4-901683-34-9 (2006年3月25日)。 
* 山下信雄、福嶋雅夫：「数理計画法」、コロナ社(電子情報通信レクチャーシリーズ C-4)、ISBN 978-4-339-01838-7 (2008年)。
* 加藤直樹：「数理計画法」、コロナ社、ISBN 978-4-339-02719-8（2008年1月7日)。
* 並木誠：「線形計画法」、朝倉書店、ISBN 978-4-254-11786-8 (2008年6月25日)。
* 坂和正敏：「非線形システムの最適化：一目的から多目的へ」POD版、森北出版、ISBN 978-4-627-91259-5 (2010年9月1日)。
* 福島雅夫：「数理計画入門(新版)」、朝倉書店（2011年)。
* 茨木俊秀：「最適化の数学」、共立出版(共立講座 21世紀の数学　13)、ISBN 978-4-320-01565-4（2011年6月23日)。
* 久野誉人、繁野麻衣子、後藤順哉：「IT Text 数理最適化」、オーム社（2012年8月25日)。
* 久保幹雄、J.P.ペドロソ、村松正和、A.レイス：「あたらしい数理最適化：Python言語とGurobiで解く」、近代科学社、ISBN 978-4-7649-0433-0 (2012年11月30日)。
* 穴井宏和：「数理最適化の実践ガイド」、講談社サイエンティフィク、ISBN 978-4-06-156510-4 (2013年3月1日)。
* 山下信雄：「非線形計画法」、朝倉書店（シリーズ応用最適化 6）、ISBN 978-4-254-11791-2 (2015年7月25日)。
* 鈴木大慈：「確率的最適化」、講談社サイエンティフィク、ISBN 978-4-06-152907-6 (2015年8月7日)。
* 河原吉伸、永野清仁：「劣モジュラ最適化と機械学習」、講談社サイエンティフィク、ISBN 978-4-06-152909-0 (2015年12月8日)。
* 金森敬文、鈴木大慈、竹内一郎、佐藤一誠：「機械学習のための連続最適化」、講談社サイエンティフィク、ISBN 978-4-06-152920-5 (2016年12月6日)。
* 久保幹雄、並木誠：「Pythonによる数理最適化入門」、朝倉書店、ISBN 978-4-254-12895-6 (2018年4月10日)。
* 山本芳嗣(編著)：「基礎数学— IV.最適化理論」、東京化学同人、(2019年)。
* 寒野善博、駒木文保：「最適化手法入門」、講談社サイエンティフィク、ISBN 978-4-06-517008-3 (2019年8月29日)。
* 小林和博：「錐最適化・整数最適化・ネットワークモデルの組合せによる　最適化問題入門」、近代科学社、ISBN 978-4-7649-0614-3 (2020年6月30日)。
* 梅谷俊治：「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」、講談社(KS情報科学専門書)、ISBN 978-4-06-521270-7 (2020年10月26日)。
* 北山哲士：「工学系のための最適設計法」、共立出版、ISBN 978-4-320-11441-8 (2021年5月15日)。
* 福田公明、田村明久：「計算による最適化入門」、共立出版（シリーズ、コンピュータが育む数学の展開）、ISBN 978-4-320-11521-7 (2022年7月31日)。
* Mykel J. Kochenderfer、Tim A. Wheeler：「最適化アルゴリズム」、共立出版、ISBN 978-4-320-12492-9 (2022年12月31日)。
* 飯塚秀明：「連続最適化アルゴリズム」、オーム社、ISBN 978-4-274-23006-6 (2023年2月25日)。
* 小林和博：「Juliaによる数理最適化」、コロナ社、ISBN 978-4-339-02934-5 (2023年4月12日)。
* 佐藤寛之：「多様体上の最適化理論」、オーム社、ISBN 978-4-274-23118-6 (2024年1月29日)。
* 齋藤努：「Pythonで学ぶ　数理最適化による問題解決入門」、翔泳社、ISBN 978-4-7981-7269-9 (2024年4月11日)。
-->

== 関連項目 ==
{{multicol}}
*[[最速降下曲線]]
*[[曲線あてはめ]]
*{{仮リンク|目標計画|en|Goal programming}}
*[[最小二乗法]]
*{{仮リンク|プロセス最適化|en|Process optimization}}
*[[変分法]]
{{multicol-end}}

<!--
== 外部リンク ==
{{外部リンクの注意|date=2024年2月18日 (日) 03:37 (UTC)|section=1}}
* [http://www.coin-or.org/ COIN-OR]—Computational Infrastructure for Operations Research
* [http://plato.asu.edu/guide.html Decision Tree for Optimization Software] Links to optimization source codes
* [http://www.mat.univie.ac.at/%7Eneum/glopt.html Global optimization]
* [http://glossary.computing.society.informs.org/ Mathematical Programming Glossary]
* [http://www.mathprog.org/ Mathematical Programming Society]
* [https://web.archive.org/web/20020822203831/http://www-fp.mcs.anl.gov/otc/GUIDE/index.html NEOS Guide] currently being replaced by the [http://wiki.mcs.anl.gov/neos NEOS Wiki]{{dead link|date=June 2015}}
* [http://www.optimization-online.org Optimization Online] A repository for optimization e-prints
* [http://www2.arnes.si/%7Eljc3m2/igor/links.html Optimization Related Links]
* [https://web.archive.org/web/20090204025624/http://see.stanford.edu/SEE/courseinfo.aspx?coll=2db7ced4-39d1-4fdb-90e8-364129597c87 Convex Optimization I] EE364a: Course from Stanford University
* [http://www.stanford.edu/~boyd/cvxbook Convex Optimization – Boyd and Vandenberghe] Book on Convex Optimization
* [http://apmonitor.com/me575/index.php/Main/BookChapters Book and Course] on Optimization Methods for Engineering Design
* [https://speakerdeck.com/umepon/mathematical-optimization-in-60-minutes 梅谷俊治：「60分で学ぶ数理最適化」（スライド、2020年6月16日）]
* [http://www.turbare.net/transl/scipy-lecture-notes/advanced/mathematical_optimization/index.html Scipy Lecture Notes, 第2.7節. "数学的最適化: 関数の最小値を求める"]
* [https://ceopt.org/ CEopt (Cross-Entropy Optimizer)]
* 連続最適化および関連分野に関する夏季学校 (統計数理研究所）
** [https://www.ism.ac.jp/~mirai/sscoke/2021/ 2021年度（第1回目）]
** [https://www.ism.ac.jp/~mirai/sscoke/2022/ 2022年度（第2回目）]
** [https://www.ism.ac.jp/~mirai/sscoke/2023/ 2023年度（第3回目）]
** [https://www.ism.ac.jp/~mirai/sscoke/2024/ 2024年度（第4回目）]
-->
{{Authority control}}
{{最適化アルゴリズム}}
{{Systems engineering}}

{{DEFAULTSORT:すうりさいてきか}}
[[Category:最適化]]
[[Category:オペレーションズリサーチ]]
[[Category:数学に関する記事]]