最適化問題のソースを表示

'''最適化問題'''（さいてきかもんだい、{{lang-en-short|optimization problem}}）とは、特定の[[集合]]上で定義された[[実数]]値[[関数 (数学)|関数]]または[[整数]]値関数についてその値が[[最小]]（もしくは最大）となる状態を解析する問題である<ref name="矢部2006-2">[[#矢部2006|矢部2006]]、2頁。</ref>。こうした問題は総称して'''数理計画問題'''（すうりけいかくもんだい、{{lang-en-short|mathematical programming problem}}, mathematical program）、'''数理計画'''とも呼ばれる<ref name="矢部2006-2" />。最適化問題は、[[自然科学]]、[[工学]]、[[社会科学]]などの多種多様な分野で発生する基本的な問題の一つであり、その歴史は18世紀の[[変分問題]]に遡る<ref name="矢部2006-ⅳ">[[#矢部2006|矢部2006]]、ⅳ頁。</ref>。1940年代に[[線型計画法]]が登場して以来、理論的な研究や数値解法の研究が非常に活発に行われ、その応用範囲はいろいろな分野に拡大されていった<ref name="矢部2006-2" />。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。[[物理学]]や[[コンピュータビジョン]]における最適化問題は、考えている関数を[[モデル (自然科学)|モデル]]化された[[系 (自然科学)|系]]の[[エネルギー]]を表すものと見なすことによって、'''エネルギー最小化問題'''と呼ばれることもある。

== 定義 ==
最適化問題を[[数学]]的に記述すると、最小化問題の場合
: 与えられた関数 <math>f: A \to \mathbb{R}</math> について、<math>x_0 \in A: \forall x \in A,\ f(x_0) \le f(x)</math> なる <math>x_0</math> を求めよ

となる。最大化問題の場合には <math>\forall x \in A, f(x_0) \ge f(x)</math> となる <math>x_0</math> を探すことになる。最大化問題は<math>\max f(x) = \min (-f(x))</math>のように目的関数の符号を反転させることにより等価な最小化問題に書き直せるので、最小化用の[[アルゴリズム]]が使える<ref name="矢部2006-5">[[#矢部2006|矢部2006]]、5頁。</ref>。

このときの関数 <math>f</math>を'''目的関数'''（{{lang-en-short|objective function, cost function}}） と呼び、探すべき変数 <math>x</math> が集合 <math>A</math> に含まれるという条件のことを'''制約条件、制約関数'''（{{lang-en-short|constraint,constraint function}}）と呼ぶ<ref name="矢部2006-2" />。制約条件の集合 A を'''実行可能領域'''（{{lang-en-short|feasible region}}）あるいは'''許容領域'''と呼び、その元（要素）を'''実行可能解、可能解、許容解'''（{{lang-en-short|feasible solution, candidate solution}}）などと呼ぶ<ref name="矢部2006-46">[[#矢部2006|矢部2006]]、46頁。</ref>。目的関数を最小あるいは最大にするような実行可能解を（大域的）最小解、最大解と呼び、そのときの目的関数値を最小値、最大値と呼ぶ。また最小・最大を区別しないで'''最適解、最適値'''（{{lang-en-short|optimal solution}}）とも呼ばれる<ref name="矢部2006-47">[[#矢部2006|矢部2006]]、47頁。</ref>。なお、ここで「領域」という用語は単に「集合」と同じ意味で使っている。また「解」は「点」と同義語である。したがって実行可能集合とか実行可能点などということもある。（この分野での伝統的・慣習的表現であり、数学的な意味の「領域＝連結な開集合」、「解＝問題の(最終的つまり最適)解」ということではないので注意。）

== 問題の分類 ==
最適化問題（数理計画問題）は、いろいろな観点・切り口によって多種多様に分類されるが、基本的な分類として以下がある。

まず考える集合 A の含まれる空間によって、無限次元と有限次元の問題に大別される。すなわち、A が関数空間に含まれる場合、無限次元の最適化問題となり、変分問題や最適制御問題が代表的である。A がユークリッド空間に含まれる場合は、有限次元の最適化問題となる。

また A が全空間のように実質的に制約条件がない問題は無制約問題（制約なし問題）となり、そうでない場合は有制約問題（制約付き問題）となる。

以下、それ以外の分類を有限次元の場合で説明する。

最適化問題は目的関数や制約条件の種類によっていくつかの問題クラスに分けることができる。

; [[線型計画問題]]
: 目的関数が1次式として表され、制約条件の集合が[[一次方程式]]・[[一次不等式]]によって定義されている場合。
; [[整数計画問題]]
: 線型計画問題のうち、各変数のとる値が[[整数]]に制限されている場合。
; [[2次計画問題]]
: 目的関数が[[2次式]]で定義され、制約条件の集合が一次方程式・一次不等式によって定義されている場合。
; [[凸計画問題]]
: 目的関数が[[凸関数]]で、制約条件の集合も[[凸集合]]である場合。
; [[半正定値計画問題]]
: [[行列の定値性|半正定値行列]]を変数とする凸計画問題。
; [[非線形計画問題]]
: 目的関数や制約条件に非線型なものが含まれる場合。
; [[二次錐計画問題]]
: 実行可能領域が二次錐であるような問題。

== 連続最適化問題 ==
{{main|数理最適化}}
連続最適化問題（{{lang-en-short|continuous optimization problem}}）とは、制約条件の集合 A が[[ユークリッド空間]] <math>\mathbb{R}^n</math> の部分集合の物。

無制約問題を解析的に解く場合は、最適性の必要条件（[[偏微分]]を取って 0 ）を満たす点の中に最小解がある。束縛条件がある場合は[[ラグランジュの未定乗数法]]が使える。

=== 導関数が必要なアルゴリズム ===
導関数が必要なアルゴリズムを[[勾配法]]という。以下は、勾配法のアルゴリズム。
* [[直線探索]]と[[信頼領域]] - 勾配法における2つの主要な反復法の枠組み
* [[最急降下法]] - 最も単純な勾配法
** [[確率的勾配降下法]] - 最急降下法のオンライン学習版（[[ニューラルネットワーク]]などで使用）
*** AdaGrad - 学習率の自動調整を行う
*** RMSProp
*** Adam
* [[共役勾配法]]
** [[:en:Biconjugate gradient method|双共役勾配法]]
** [[非線形共役勾配法]]
* [[ニュートン法]]
* [[準ニュートン法]]
** [[DFP法]]
** [[BFGS法]]
** [[BHHH法]]
** [[SR1法]]
** 記憶制限準ニュートン法 - 大規模（高次元）問題に対応した物
*** [[L-BFGS]]
**** L-BFGS-B - L-BFGSに定義域の境界を指定できるようにした物
**** OWL-QN - L-BFGSにおいて目的関数にL1[[正則化]]項がついた形に対応できるようにした物
* [[ガウス・ニュートン法]] - [[非線形最小二乗法]]の問題（平方和の最適化問題）を解く
** [[レーベンバーグ・マーカート法]]
* [[内点法]]
[[Mathematica]]のFindMinimumのデフォルトの設定は、制約条件付きは内点法<ref>[http://reference.wolfram.com/language/tutorial/ConstrainedOptimizationLocalNumerical.html 局所的非線形数値最適化—Wolfram言語ドキュメント]</ref>、目的関数が平方和の場合はレーベンバーグ・マーカート法を使い<ref>[http://reference.wolfram.com/language/tutorial/UnconstrainedOptimizationIntroductionLocalMinimization.ja.html 極小値探索概論—Wolfram言語ドキュメント]</ref>、そうで無い場合はBFGS法を使い、250次元以上の場合L-BFGS法を使う<ref>[http://reference.wolfram.com/language/tutorial/UnconstrainedOptimizationQuasiNewtonMethods.ja.html 準ニュートン法—Wolfram言語ドキュメント]</ref>。

=== 導関数が不要なアルゴリズム ===
以下は、導関数が不要（{{lang-en-short|[[:en:Derivative-free optimization|Derivative-free optimization]]}}）なアルゴリズム。
* [[ネルダー–ミード法]]
* [[座標降下法]]
** [[:en:Adaptive coordinate descent|適応座標降下法]]
** ブロック座標降下法（block coordinate descent）
* [[:en:Michael J. D. Powell|Michael J. D. Powell]] 開発
** [[パウエル法]]
** [[:en:BOBYQA|BOBYQA]] - 非線形関数とパラメータの値域で制約
** [[:en:LINCOA|LINCOA]] - 非線形関数と線形制約条件
** [[:en:COBYLA|COBYLA]] - 非線形関数と非線形制約条件
** [[:en:TOLMIN (optimization software)|TOLMIN]]
** [[:en:UOBYQA|UOBYQA]]
** [[:en:NEWUOA|NEWUOA]]
* [[進化戦略]]
** [[CMA-ES]]
** [[:en:Natural evolution strategy|自然進化戦略]]
* [[差分進化]]

[[Mathematica]]のNMinimumのデフォルトの設定は、線形計画問題ならば単体法を使い、整数パラメータがある場合などは差分進化を使い、それ以外はNelder-Mead法を使う<ref>[http://reference.wolfram.com/language/tutorial/ConstrainedOptimizationGlobalNumerical.html 大域的非線形数値最適化—Wolfram言語ドキュメント]</ref>。

=== 1次元用 ===
2次元以上に対応している連続最適化問題のアルゴリズムでも内部で1次元用のアルゴリズムを使用している場合も多い。以下は、1次元用のアルゴリズム。
* [[黄金分割探索]]
* [[ブレント法]]

=== 線形計画問題用 ===
以下は[[線形計画問題]]用のアルゴリズム。
* [[単体法]]
* [[楕円体法]]
* [[カーマーカー法]]

==離散最適化問題==
{{main|組合せ最適化}}
離散最適化問題（{{lang-en-short|discrete optimization problem}}）とは、制約条件の集合 A が <math>\mathbb{Z}^n</math> の部分集合の物。詳細は[[組合せ最適化]]を参照。

=== 計算理論の問題のクラス ===
* [[P (計算複雑性理論)|P]]
* [[NP]]
* [[co-NP]]

== 歴史 ==
最適化問題としての手法の最も古い登場は[[カール・フリードリッヒ・ガウス]]までさかのぼることができる[[最急降下法]] (steepest descent) である。歴史的に始めに導入された用語は1940年代に[[ジョージ・ダンツィク]]によって作られた「[[線型計画法]]」(linear programming) である。この（「計画法」と訳される）''programming''という語の由来は、コンピュータなどのプログラムを書く、機器を設定する、といった意味の「[[プログラミング]]」とは別で、軍などにおける（特に、この分野では先行していた米国において、[[アメリカ軍]]の用語としての）訓練・補給の予定、という語の''program''からきている。最適化問題の発展に貢献した数学者として
* [[ジョン・フォン・ノイマン]]
* [[レオニート・カントロヴィチ]]
* Naum Shor
* Leonid Khachian
* Boris Polyak
* ユーリー・ネステロフ
* Arkadii Nemirovskii
* Michael J. Todd
* [[リチャード・ベルマン]]
* [[ホアン・トゥイ (数学者)]]
らがあげられる。

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

== 参考文献 ==
*{{Cite book|和書
|author    = 矢部博
|date      = 2006-03-25
|title     = 工学基礎 最適化とその応用
|publisher = 数理工学社
|edition     = 初版
|isbn      = 4-901683-34-9
|ref = 矢部2006
}}

<!--
== 論文誌 ==
* [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日).

日本語図書
* 今野浩、山下浩：「非線形計画法」、日科技連出版社 (ORライブラリー 6)、ISBN 978-4-81715306-7、（1978年3月）。
* 茨木俊秀、福島雅夫：「最適化の手法」、共立出版(情報数学講座)、ISBN 978-4-320-02664-3、（1993年7月）。
* G.L. Nemhauser (編), M.J.Todd (編), A.H.G. Rinnooy Kan (編)：「最適化ハンドブック」、[[朝倉書店]]、ISBN 978-4-25412102-5、（1995年10月1日）。 
* 矢部博、八巻直一：「非線形計画法」（ＦＤ付き）、朝倉書店 (応用数値計算ライブラリ)、ISBN 978-4-25411489-8、（1999年6月）。
* 田村明久、村松正和：「最適化法」、共立出版 (工系数学講座 17)、ISBN 978-4-320-01616-3、（2002年4月1日）。
* 久保幹雄、田村明久、松井知己(編)：「応用数理ハンドブック」、朝倉書店、ISBN 978-4-254-11141-5（2002年11月15日）。
* 金谷健一：「これなら分かる最適化数学―基礎原理から計算手法まで」、共立出版、ISBN 978-4-320-01786-3、（2005年9月1日）。
* 矢部博：「工学基礎 最適化とその応用」、数理工学社 (新・工科系の数学)、ISBN 978-4-90168334-0、（2006年4月1日）。 
* 山下信雄、福嶋雅夫：「数理計画法」、コロナ社、(2008年）。
* 加藤直樹：「数理計画法」、コロナ社、（2008年）。
* 福島雅夫：「数理計画入門(新版)」、朝倉書店、（2011年）。
* 茨木俊秀：「最適化の数学」、共立出版(共立講座 21世紀の数学　13)、ISBN 978-4-320-01565-4、（2011年6月23日）。
* 久野誉人、繁野麻衣子、後藤順哉：「数理最適化」、オーム社、（2012年8月）。
* 鈴木大慈：「確率的最適化」、講談社サイエンティフィク、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日).
* 山本芳嗣(編著)：「基礎数学— IV.最適化理論」、東京化学同人、(2019年）。
* 梅谷俊治：「しっかり学ぶ数理最適化 モデルからアルゴリズムまで」、講談社(KS情報科学専門書)、ISBN 978-4-06-521270-7、(2020年10月26日）。
* 福田公明、田村明久：「計算による最適化入門」、共立出版（シリーズ、コンピュータが育む数学の展開）、ISBN 978-4-320-11521-7、(2022年7月25日）。
* Mykel J. Kochenderfer，Tim A. Wheeler：「最適化アルゴリズム」、共立出版、ISBN 978-4-320-12492-9、(2022年12月23日）。
* 飯塚秀明：「連続最適化アルゴリズム」、オーム社、ISBN 978-4-274-23006-6、(2023年2月25日）。
* 小林和博：「Juliaによる数理最適化」、コロナ社、ISBN 978-4-33902934-5、(2023年4月12日）。
* 佐藤寛之：「多様体上の最適化理論」、オーム社、ISBN 978-4-274-23118-6、(2024年1月29日）。

== 外部リンク ==
{{外部リンクの注意|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回目）]

-->

== 関連項目 ==
* [[メタヒューリスティクス]]
* [[組合せ最適化]]
* [[双対問題]]
* [[数理最適化]]

{{最適化アルゴリズム}}
{{主要な最適化問題の分類}}
{{数学}}

{{Normdaten}}
{{DEFAULTSORT:さいてきかもんたい}}
[[Category:最適化|*]]
[[Category:オペレーションズリサーチ]]
[[Category:数学の問題]]
[[Category:数学に関する記事]]