1 基本概念
最適化問題とは、許容された範囲の中で、ある量をできるだけ大きくする、またはできるだけ小さくする解を見つける問題である。対象は数値計算だけでなく、設計、配分、選択、制御などにも及ぶ。資源、時間、費用、性能といった要素の間で折り合いをつける枠組みとして、数学と応用科学の両方で重要視される。
1.1 最適化問題の定義
最適化問題は、変数の取りうる範囲と評価基準を与え、その条件下で最良の解を求める形式で表される。一般には、目的関数を最小化または最大化し、同時に制約条件を満たすことが求められる。表現は抽象的であるが、実務では目的の設定そのものが問題の核心になることも多い。
1.2 目的関数
目的関数は、解の良し悪しを数値で表す関数である。たとえば費用の総額、誤差の大きさ、利益、効率、距離などがこれに当たる。最適化では、この関数の値を基準にして解を比較し、望ましい方向へ調整する。
1.3 制約条件
制約条件は、解が守るべき制限を示す。資源量の上限、物理法則、予算、整合性条件などが含まれる。制約は問題の現実性を担保する一方で、探索空間を狭め、解法の設計にも大きく影響する。
1.4 実行可能解
実行可能解とは、すべての制約条件を満たす解を指す。最適化では、まず実行可能性が成立しなければ候補にならない。実行可能な解が複数ある場合、その中で目的関数の値が最良のものを選ぶ。
1.5 最適解
最適解は、実行可能解の中で目的関数を最も良くする解である。最小化問題では値が最も小さい解、最大化問題では最も大きい解が該当する。複数の最適解が存在することもあり、その場合は同じ性能を持つ解の集合として扱われる。
2 問題の分類
最適化問題は、変数の型、制約の有無、関数の性質、目的の数などによって多様に分類される。分類は単なる整理ではなく、どの解法が適切かを見極める手がかりにもなる。特に連続か離散か、凸か非凸かによって、理論的扱いと計算難度は大きく変わる。
2.1 変数の種類による分類
変数が連続値を取るか、整数や組合せ的な値に限られるかで、問題の性格は大きく異なる。連続変数では微分を利用した手法が有効になりやすく、離散変数では探索や組合せの工夫が中心となる。両者を併せ持つ場合には、さらに複雑な構造を示す。
2.1.1 連続最適化
連続最適化は、変数が実数の範囲で変化する問題である。曲線や曲面の形状を利用した解析的・数値的手法が使いやすく、工学設計や機械学習で広く現れる。勾配に基づく方法が特に重要である。
2.1.2 離散最適化
離散最適化は、変数が離散的な値や組合せに制限される問題である。巡回順序、割当、選択、配置などが典型例である。候補数が急増しやすく、一般に計算負荷が高い。
2.1.3 混合整数最適化
混合整数最適化は、連続変数と整数変数を同時に含む。現実の計画問題では、数量は連続的に扱い、設備の有無や回数は整数で表すことが多い。柔軟性が高い反面、解法は複雑になる。
2.2 制約の有無による分類
制約があるかどうかは、問題の難しさと手法選択に直結する。制約なしでは局所的な性質を直接調べやすいが、制約付きでは実行可能領域の境界も考慮する必要がある。現実の応用では、制約なし問題より制約付き問題のほうが一般的である。
2.2.1 制約なし最適化
制約なし最適化は、変数が自由に動ける状況で目的関数のみを最適化する。理論的には比較的扱いやすく、関数の微分可能性を利用した手法が発達している。基礎的なモデルとして、多くの解法の出発点になる。
2.2.2 制約付き最適化
制約付き最適化は、等式や不等式の制限の下で解を求める。境界上で最適点が現れることも多く、制約の表現が解析の中心となる。ラグランジュ法やKKT条件は、この種の問題で特に重要である。
2.3 関数の性質による分類
目的関数や制約関数の形は、理論の見通しを左右する。線形なら計算上の体系が整いやすく、非線形では局所構造が複雑になる。さらに凸性の有無は、局所解と大域解の関係を決める重要な要素である。
2.3.1 線形最適化
線形最適化は、目的関数と制約がすべて線形式で表される問題である。構造が明快で、理論と計算の両面で成熟している。生産計画や輸送問題などで頻繁に現れる。
2.3.2 非線形最適化
非線形最適化は、少なくとも一部に非線形な式を含む。解の地形が複雑で、複数の局所解が現れやすい。実際の工学モデルや学習モデルでは、この分類に属するものが多い。
2.3.3 凸最適化
凸最適化は、実行可能領域と目的関数の凸性が保たれる問題である。局所最適解が大域最適解になるという強い性質があり、理論的にも計算的にも扱いやすい。安定した結果が得られやすいため、重要な基礎分野とされる。
2.3.4 非凸最適化
非凸最適化は、凸性を満たさない問題である。谷や峰が入り組み、初期値や探索経路によって結果が変わることがある。多くの現実問題はこの型に近く、近似やヒューリスティックの工夫が必要になる。
2.4 目的の数による分類
目的が一つか複数かでも問題の性質は変わる。単一の評価基準なら順位づけは明確だが、複数の基準が競合する場合は妥協点を探る必要がある。多目的の場合、最良解という概念は一つに定まりにくい。
2.4.1 単目的最適化
単目的最適化は、ひとつの目的関数だけを扱う。最適性の判定が比較的明確で、標準的な理論が適用しやすい。多くの基礎モデルはこの形で記述される。
2.4.2 多目的最適化
多目的最適化は、複数の目的関数を同時に考える。たとえばコスト削減と性能向上の両立のように、目標が相反する場合がある。こうした問題では、パレート最適という考え方が用いられる。
3 数学的基礎
最適化理論は、関数、微分、線形代数、解析学などの土台の上に成り立つ。変数の変化に対して目的関数がどう反応するかを調べることで、最適点の性質を記述できる。制約条件を扱うためには、境界や曲率の理解も欠かせない。
3.1 関数と変数
変数は解を表す量であり、関数はそれに応じて値を返す規則である。最適化では、変数の取り方によって関数値が変化する様子を分析する。複数の変数が絡むと、相互作用が現れ、単純な比較だけでは不十分になる。
3.2 勾配とヘッセ行列
勾配は関数の増減方向を示すベクトルであり、ヘッセ行列は二階微分によって曲率を表す。勾配が0に近い点は候補点となり、ヘッセ行列はその点が極大、極小、鞍点のどれに近いかを判断する材料になる。数値解法の多くは、これらの情報を利用する。
3.3 ラグランジュの未定乗数法
ラグランジュの未定乗数法は、等式制約つき最適化で使われる代表的な手法である。制約を組み込んだ新しい関数を作り、最適条件を方程式として整理する。制約面上での最適点を見つける際に有効である。
3.4 カルーシュ・クーン・タッカー条件
カルーシュ・クーン・タッカー条件は、不等式制約を含む最適化の必要条件を与える。ラグランジュ法を拡張したもので、活性化している制約の扱いが特徴である。現代の最適化理論では、制約付き問題の中心的な道具となっている。
4 解法
最適化の解法は、問題の大きさ、構造、精度要求に応じて選ばれる。厳密な解を保証する方法もあれば、計算効率を優先して近似的に解く方法もある。理論上の最良性と実用上の速さのどちらを重視するかが、手法選択の分岐点になる。
4.1 厳密解法
厳密解法は、最適解を確実に求めることを目指す。計算量が大きくなりやすいが、正確性の面で信頼性が高い。問題規模が比較的小さい場合や、厳密性が重要な場面で用いられる。
4.1.1 全探索
全探索は、候補解をすべて調べる方法である。実装は単純だが、候補数が多いと現実的でなくなる。問題の規模が小さいときに限って有効である。
4.1.2 分枝限定法
分枝限定法は、探索空間を分割し、不要と判断できる部分を上界・下界で除外する。無駄な計算を減らしながら厳密解を目指せる。組合せ最適化で広く使われる。
4.1.3 動的計画法
動的計画法は、部分問題の解を再利用して全体の最適解を構成する。再帰的な構造を持つ問題に適しており、重複計算を避けられる。最短経路や資源配分のモデルで重要である。
4.2 数値解法
数値解法は、反復計算を通じて解に近づく手法である。解析解が得にくい場合に有効で、連続最適化で特によく用いられる。収束速度や安定性の違いが、手法比較の要点となる。
4.2.1 勾配法
勾配法は、関数の傾きを利用して下降または上昇を繰り返す。比較的実装しやすく、大規模問題でも適用しやすい。学習アルゴリズムの基本形としても知られる。
4.2.2 ニュートン法
ニュートン法は、二階微分の情報を使って更新を行う。局所的には高速に収束しやすいが、計算量や初期値の影響を受けやすい。精度を重視する場面で用いられる。
4.2.3 内点法
内点法は、制約領域の内部を進みながら最適解へ近づく。線形計画や凸最適化で高い性能を示す。境界を直接たどる方法とは異なる視点を持つ。
4.2.4 反復法
反復法は、同じ型の計算を繰り返して解を改善する広い総称である。近似の精度を段階的に高められる。行列方程式や大規模最適化で頻出する。
4.3 離散問題の解法
離散問題では、連続解析だけでは対応しにくいため、組合せ構造を意識した解法が必要になる。整数条件や選択肢の並びをうまく扱う工夫が重要である。実務では、厳密法と近似法の併用も多い。
4.3.1 整数計画法
整数計画法は、変数に整数条件を課した最適化である。記号的な制約と数値的な計算を組み合わせるため、難度は高い。物流、配置、生産計画などの問題で利用される。
4.3.2 組合せ最適化手法
組合せ最適化手法は、選択や順序付けの問題に特化した方法群である。グラフ理論、枝刈り、ヒューリスティックなど多様な技法を含む。巡回セールスマン問題のような代表例がある。
4.4 近似解法
近似解法は、厳密最適よりも計算のしやすさを優先する。大規模で複雑な問題では、十分に良い解を短時間で得ることが価値を持つ。局所解を出発点に改善する戦略が中心となる。
4.4.1 局所探索
局所探索は、現在の解の近傍を調べてより良い候補へ移る方法である。単純だが応用範囲が広く、問題ごとの近傍設計が性能を左右する。停滞を避ける工夫がしばしば必要となる。
4.4.2 焼きなまし法
焼きなまし法は、悪化する変更も一定確率で受け入れながら探索する。局所的な停滞から抜け出しやすく、広い空間を試せるのが利点である。確率的な探索として古くから用いられている。
4.4.3 遺伝的アルゴリズム
遺伝的アルゴリズムは、解を個体として扱い、交叉や突然変異で集団を更新する。多峰性の問題に対して柔軟に働くことがある。厳密な最適保証はないが、探索の多様性を確保しやすい。
5 理論的性質
理論的性質の研究は、どのような条件で解が存在し、どの程度安定し、どれだけ一意に定まるかを明らかにする。これにより、単に計算できるだけでなく、結果の解釈や信頼性も評価できる。最適化理論の多くは、こうした性質の把握を通じて発展してきた。
5.1 存在定理
存在定理は、最適解が少なくとも一つ存在するための条件を述べる。実行可能領域の閉性や有界性、目的関数の連続性などが重要になる。解が存在するかどうかは、計算を始める前提として基本的である。
5.2 一意性
一意性は、最適解がただ一つに定まる性質である。これが成り立つと、結果の解釈が明快になり、数値計算の安定性も理解しやすい。凸性や強い単調性が一意性に寄与することがある。
5.3 局所最適性と大域最適性
局所最適性は、近傍の範囲で最良であることを意味する。大域最適性は、全体の実行可能領域で最良であることを指す。非凸問題では両者が一致しないことが多く、最適化の難しさの本質をなす。
5.4 感度分析
感度分析は、条件やパラメータの変化が解にどう影響するかを調べる。現実の応用では、入力値が完全に固定されることは少ないため、頑健性の評価に役立つ。小さな変更で結果が大きく変わるかどうかを知ることは重要である。
5.5 双対性
双対性は、ある問題に対して別の対応する問題を構成し、両者の関係を調べる考え方である。双対問題の解から元の問題の情報を得られることがあり、下界や証明にも有用である。線形計画や凸最適化で特に重要な理論である。
6 応用
最適化は、理論数学にとどまらず、実際の設計や運用に広く組み込まれている。限られた資源をどう使うかという問いは、多くの産業や科学分野に共通する。応用では、単に最良値を求めるだけでなく、計算時間や頑健性も重視される。
6.1 工学最適化
工学最適化では、構造物、回路、機械、熱、流体などの設計条件を調整して性能を高める。強度、重量、消費エネルギーのバランスが典型的な課題である。試作回数を減らすためにも、最適化手法は重要である。
6.2 経済最適化
経済最適化では、利益最大化、費用最小化、資源配分、投資選択などが扱われる。市場の制約や不確実性を反映するモデルが多い。意思決定の合理化に寄与する点で、理論と実践の接点が大きい。
6.3 機械学習における最適化
機械学習では、モデルの学習を目的関数の最小化として定式化することが多い。損失関数を減らしながら、汎化性能を保つことが課題となる。大規模データに対応するため、確率的勾配法などの反復手法が発達してきた。
6.4 物流と運用計画
物流と運用計画では、輸送経路、在庫、勤務、設備稼働などを最適に編成する。コスト削減だけでなく、納期やサービス品質も考慮する必要がある。組合せ最適化の代表的な応用先である。
6.5 制御理論
制御理論では、システムの状態を望ましい方向へ導くために入力を設計する。最適化は、エネルギー消費や偏差を抑えながら制御性能を高める手段となる。時間発展を含む問題では、動的最適化の考え方が用いられる。
7 関連する概念
最適化問題は、周辺分野と密接に結びついている。特に、時間に沿って制御を選ぶ考え方、変化率を扱う解析、制度的な計画法、複数の主体が相互作用する理論とは強い関連がある。これらの概念は、最適化の視野を広げる。
7.1 最適制御
最適制御は、時間の経過に応じて操作量を選び、目的を最良化する分野である。通常の静的最適化に対し、状態の遷移が含まれる点が特徴である。工学やロボティクスで重要性が高い。
7.2 変分法
変分法は、関数そのものを変化させて最適条件を導く方法である。曲線や面の形を対象にするため、連続的な最適化と深く関係する。古典解析から発展した重要な理論的基盤である。
7.3 数理計画法
数理計画法は、制約のもとで目的を最適化する問題全般を扱う体系である。線形計画、整数計画、非線形計画などを含む広い概念である。最適化問題の標準的な枠組みとして位置づけられる。
7.4 ゲーム理論
ゲーム理論は、複数の意思決定主体が互いの選択に影響される状況を研究する。各主体の最適化が相互依存するため、単独の最適化とは異なる構造を持つ。競争や協力の分析に用いられる。
8 歴史
最適化の考え方は古代から見られるが、体系的な理論としての整備は近代以降に進んだ。計算技術の発達とともに、扱える問題の規模と複雑さは大きく拡大した。歴史をたどると、解析手法から計算手法への重心移動が明瞭である。
8.1 古典的起源
古典的起源は、幾何学や力学の問題にさかのぼる。最短経路、最小面積、最大体積のような問いは、早くから数学者の関心を集めた。これらは後の最適化理論の原型となった。
8.2 近代数理計画の発展
近代には、線形計画や双対理論の整備によって、最適化が独立した学問分野として確立した。制約付き問題を一般的に扱う枠組みが整い、工業や経済への応用が一気に広がった。理論と応用が相互に刺激し合う形で進展した。
8.3 計算機利用の進展
計算機の普及により、大規模問題への数値解法が現実的になった。手計算では扱えない規模の行列や組合せにも対応できるようになり、反復的アルゴリズムが実用化された。高速計算資源の発展は、最適化の応用範囲を広げた。
8.4 現代の研究動向
現代の研究では、大規模化、不確実性、分散処理、データ駆動型の学習問題への対応が重視されている。精度だけでなく、計算効率、安定性、解釈性の両立が課題となる。理論、アルゴリズム、応用の結びつきは、以前にも増して強まっている。