さいてきか‐もんだい〔サイテキクワ‐〕【最適化問題】
最適化問題
【英】：optimization problem
概要
「与えられた制約条件の下で目的を最適に達成するための数理モデル」で数理計画問題(mathematical programming problem)ともいう. 数学的には,
 |  あるいは,  |
 |  |
と表現される. ここで, 
は 
次元ベクトル空間 
の部分集合(実行可能集合)で, 
は で定義された実数値関数(目的関数).
詳説
最適化問題 （optimization problem）（数理計画問題）は, 「与えられた制約条件の下でより良い目的を達成するための数理モデル」で, 数学的には,
 あるいは,  |
 |
のように表現される. ここで, は 次元ベクトル空間 
の部分集合で実行可能集合（feasible region）（許容集合）と呼ばれ, は で定義された実数値関数で目的関数（objective function）と呼ばれる. また, 
を実行可能解（許容解）, 実行可能解の中で目的関数の最大（あるいは, 最小）を達成する
を最適解（optimal solution）と呼ぶ. 実行可能集合 は,
 |
のように表現されることが多い. ただし, 
は で定義された実数値関数である. また, 
は対象とする最適化問題を記述するのに用いられる基礎となる空間と考えればよい. 基礎となる空間 , 実行可能領域 を表現するのに使われる関数 
および, 目的関数 に種々の条件を課した多くのクラスの最適化問題が研究されている. 最適化問題は,
（
は
が仮定され, 変数ベクトル が連続的な値をとる連続最適化問題（continuous optimization problem）と,
または 
（
ある
が仮定され, 変数ベクトル が離散的な値をとる離散最適化問題（discrete optimization problem）に, 大きく分けることができる. 関数 
に連続性（あるいは, 微分可能性）のみを仮定する非線形離散最適化問題のクラスも考えることができるが, そのような問題は非常に難しく, 関数 が線形（あるいは, 高々２次）関数である場合に限定することが多い. このように限定したとしても, 離散最適化問題には広範な応用がある. 個々の最適化問題は, それが定式化された元の（現実）問題と結びつけた名前で呼ばれることも多い. たとえば, 最小費用フロー問題, 最大フロー問題, 巡回セールスマン問題, グラフ分割問題等である. また, 上記の最適化問題に関する分類は厳密ではなく, 連続最適化と離散最適化の両方の特徴を共有する問題（たとえば, 施設配置問題, 線形混合整数計画問題）や, それらからはみ出た最適化問題も存在する.
最適化問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/13 15:16 UTC 版)
最適化問題（さいてきかもんだい、英: optimization problem）とは、特定の集合上で定義された実数値関数または整数値関数についてその値が最小（もしくは最大）となる状態を解析する問題である[1]。こうした問題は総称して数理計画問題（すうりけいかくもんだい、英: mathematical programming problem, mathematical program）、数理計画とも呼ばれる[1]。最適化問題は、自然科学、工学、社会科学などの多種多様な分野で発生する基本的な問題の一つであり、その歴史は18世紀の変分問題に遡る[2]。1940年代に線型計画法が登場して以来、理論的な研究や数値解法の研究が非常に活発に行われ、その応用範囲はいろいろな分野に拡大されていった[1]。実世界の現象の数理的な解析に関わる問題や抽象的な理論の多くをこの最適化問題という一般的なくくりに入れることができる。物理学やコンピュータビジョンにおける最適化問題は、考えている関数をモデル化された系のエネルギーを表すものと見なすことによって、エネルギー最小化問題と呼ばれることもある。
最適化問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/30 23:37 UTC 版)
詳細は「最適化問題」を参照 最適化問題は、与えられた関数が最大（または最小）となる点を求める問題である。解には条件として何らかの制約を課すことがよくある。 最適化問題はさらに、関数や制約の形式によっていくつかに分類される。例えば、線形計画問題は関数と制約条件の式が共に線型である場合を扱う。線形計画問題の解法としては、シンプレックス法や内点法などが挙げられる。 制約条件付きの最適化問題を制約条件のない問題の形に変換するためにラグランジュの未定乗数法が用いられる。
※この「最適化問題」の解説は、「数値解析」の解説の一部です。
「最適化問題」を含む「数値解析」の記事については、「数値解析」の概要を参照ください。
最適化問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/28 07:52 UTC 版)
詳細は「最適化問題」を参照 最適化問題は、次のように表現される： 与えられるもの：ある集合 A から実数への函数 f : A → {\displaystyle \to } R 目的：A 内のすべての x に対して f(x0) ≤ f(x) を満たす A 内の元 x0（最小化）あるいは f(x0) ≥ f(x) を満たす A 内の元 x0（最大化）を見つけること。 このような問題は最適化問題あるいは数理計画問題（コンピュータプログラミングとは直接的には関係ないが、例えば線型計画法では用いられる）と呼ばれる。多くの実世界での問題や理論的問題は、一般的な枠組みでモデル化される。物理学やコンピュータビジョンの分野における、この手法による問題は、エネルギー最小化（energy minimization）と呼ばれることもある。この場合、函数 f の値はモデル化されるシステムのエネルギーを表す。 典型的に A はユークリッド空間 Rn の部分集合であり、しばしばある制約（英語版）の集合によって特徴づけられ、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）と呼ばれる。目的函数を最小化（あるいは最大化）する可能解は、最適解と呼ばれる。 数学において慣習的な最適化問題は、通常、最小化に関するものである。一般に、最小化問題において目的函数と可能領域が両方とも凸でない限り、いくつかの局所最小解が存在しうる。ここで局所最小解 x* は、ある定数 δ > 0 が存在して、 ‖ x − x ∗ ‖ ≤ δ ; {\displaystyle \|\mathbf {x} -\mathbf {x} ^{*}\|\leq \delta ;\,} を満たすすべての x に対して次が成立するもののことをいう。 f ( x ∗ ) ≤ f ( x ) . {\displaystyle f(\mathbf {x} ^{*})\leq f(\mathbf {x} ).} すなわち、x* のまわりのある領域における函数のすべての値は、その点での値よりも大きいか等しくなる。局所最大解も同様に定義される。
※この「最適化問題」の解説は、「数理最適化」の解説の一部です。
「最適化問題」を含む「数理最適化」の記事については、「数理最適化」の概要を参照ください。
最適化問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/26 14:13 UTC 版)
「逐次最小問題最適化法」の記事における「最適化問題」の解説
詳細は「サポートベクターマシン」を参照 データセット (x1, y1), ..., (xn, yn) に関する二項分類問題を考える。ここで xi は入力ベクトル、yi ∈ {-1, +1} はそれに対応する2値ラベルである。ソフトマージンサポートベクターマシンは以下の双対問題で表される2次計画問題を解くことによって訓練される: max α ∑ i = 1 n α i − 1 2 ∑ i = 1 n ∑ j = 1 n y i y j K ( x i , x j ) α i α j , {\displaystyle \max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K(x_{i},x_{j})\alpha _{i}\alpha _{j},} ただし 0 ≤ α i ≤ C , for i = 1 , 2 , … , n , {\displaystyle 0\leq \alpha _{i}\leq C,\quad {\mbox{ for }}i=1,2,\ldots ,n,} ∑ i = 1 n y i α i = 0 {\displaystyle \sum _{i=1}^{n}y_{i}\alpha _{i}=0} ここで C は SVM hyperparameter、K(xi, xj) はカーネル関数（英語版）で、どちらもユーザが与える。変数 α i {\displaystyle \alpha _{i}} はラグランジュ乗数である。
※この「最適化問題」の解説は、「逐次最小問題最適化法」の解説の一部です。
「最適化問題」を含む「逐次最小問題最適化法」の記事については、「逐次最小問題最適化法」の概要を参照ください。
「最適化問題」の例文・使い方・用例・文例
- 最適化問題のページへのリンク
