数学における最適化：理論、問題の種類、代表的な解法

主な区別

• 凸と非凸：凸問題では、任意の局所最適解が大域最適解でもあるため、解析とアルゴリズムが簡潔になる。
• 連続と離散：連続問題では変数は区間内の任意の実数値を取り得る。一方、離散問題または整数問題では、一部の変数が整数値に制限される。
• 単一目的と多目的：複数の基準を両立させる必要がある場合、解は単一の最良値ではなく、しばしばトレードオフ（パレート最適性）によって記述される。
• 決定論的と確率的：確率的最適化では、問題データの一部がランダムまたは不確実であり、目的には期待値やリスク尺度が含まれる。

解法

手法は問題の種類によって異なる。代表的な方法には次がある。

• 滑らかな無制約問題に対し、導関数または勾配をゼロと置く微積分を用いた解析的方法。
• 微分可能な問題に対する、勾配降下法、ニュートン法、準ニュートン法などの数値アルゴリズム。
• 特化したアルゴリズム。線形計画法には単体法と内点法、整数計画法には分枝限定法と切除平面法がある。
• 逐次的または段階的な構造をもつ問題に対する動的計画法。
• 厳密解の取得が難しい場合、あるいは目的関数にノイズや不連続性がある場合の、ヒューリスティックおよびメタヒューリスティック手法（遺伝的アルゴリズム、焼きなまし法、粒子群最適化）。

応用と留意点

最適化モデルは、実験やシステムの設計、資源のスケジューリング、物流計画、データへのモデルの当てはめ、プロセスの制御に用いられる。実務で手法を適用する際には、計算コスト、データおよびモデリング仮定に対する感度、制約の実行可能性、得られた解が大域最適解か局所最適解にとどまるかが重要な論点となる。

最適化は分野横断的に応用されるため、科学と数学における研究は、アルゴリズム上の手法と理論的理解を継続的に発展させている。その核心は、定められた制限のもとで、与えられた関数に対して変数の最良の値を選ぶことを形式的に研究する点にある。