最適化問題の分類｜数理最適化

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：最適化問題とは　|　関連：局所最適と大域最適・凸性の役割

要点（BLUF）

最適化問題は 複数の軸（連続/離散・線形/非線形・凸/非凸・制約有無・確定/確率）で分類できる。
解きやすさを最も支配するのは 「凸か非凸か」 と 「連続か離散か」。線形/非線形より効く。
この地図があると、目の前の問題がどの章のどの手法に対応するかが一目で分かる。

概念 ── 問題を測る軸

「線形計画」「整数計画」「凸最適化」といった呼び名は、すべて以下の軸の組み合わせに過ぎない。軸を分けて見ると、各章がどこを担当しているかが見えてくる。

軸	一方	もう一方	効き目
変数の種類	連続（実数）	離散（整数・組合せ）	大（離散は一般に難しい）
目的・制約の形	線形	非線形	中
凸性	凸	非凸	最大（凸なら局所＝大域）
制約	なし	あり	中（解法の枠組みが変わる）
不確実性	確定的	確率的・ロバスト	中（第7章）

主要クラスの地図

graph TD
  OPT["最適化問題"] --> CONT["連続"]
  OPT --> DISC["離散 (整数・組合せ)"]
  CONT --> LP["線形計画 LP"]
  CONT --> NLP["非線形計画 NLP"]
  NLP --> CVX["凸計画 (QP/SOCP/SDP)"]
  NLP --> NONCVX["非凸計画"]
  DISC --> IP["整数計画 IP/MILP"]
  DISC --> COMB["組合せ最適化"]

LP（線形計画）：目的・制約がすべて線形。凸であり、多項式時間で解ける（第2章）。
凸計画：目的が凸・制約が凸集合。QP/SOCP/SDP を含み、局所最適が大域最適（第5章）。
非凸 NLP：局所最適が複数。勾配法やニュートン法は局所解しか保証しない（第4章）。
整数計画・組合せ：変数が整数。一般に NP 困難で、分枝限定やヒューリスティクスが要る（第3・6章）。

なぜ「凸か非凸か」が最も効くのか

最適化の難しさの本質は 「局所最適が大域最適か」 に尽きる。凸問題ではこれが一致するので、勾配がゼロの点を1つ見つければ世界最良が保証される。非凸問題では、見つけた解が「たまたま近くで一番良いだけ」かもしれず、大域最適である保証が原理的に得られない。だから「線形か非線形か」よりも「凸か非凸か」のほうが、解きやすさを強く支配する。詳しくは局所最適と大域最適・凸性の役割。

線形計画が嬉しいのは「線形だから」ではなく「線形ゆえに凸（しかも実行可能領域が凸多面体）だから」である、という見方をここで持っておくとよい。

連続 vs 離散 ── もう一つの大きな段差

連続問題では微分（勾配・ヘッセ行列）が使え、「少し動かして改善する」滑らかな探索ができる。離散問題では微分が使えず、選択肢が指数的に増える（ $n$ 個の0/1変数で $2^n$ 通り）。この組合せ爆発が、整数計画を一般に難しくしている（計算複雑性とNP困難の地図）。LP 緩和（整数条件を一旦外す）が橋渡しになる（整数計画とは・LP緩和）。

数式の直観的意味

分類は「どの定理が使えるか」を決める。たとえば：

凸 ⇒ KKT 条件が 十分条件になり、局所解＝大域解（凸最適化問題と双対理論）。
線形 ⇒ 最適解が頂点に存在し、シンプレックス法が使える（線形計画の標準形と幾何）。
離散 ⇒ 連続の最適性条件が直接使えず、緩和＋分枝で攻める（分枝限定法）。

つまり分類は飾りではなく、「この問題にどの理論的武器を抜けるか」の判断そのもの。

⚠️ よくある誤解・落とし穴

「非線形＝難しい」とは限らない。凸な非線形（QP など）は LP に近い扱いやすさ。難しさは非線形性ではなく非凸性から来る。
「整数変数が少しだけ」でも油断しない。0/1 変数が混じった瞬間に MILP となり、最悪指数時間になり得る。
線形の皮をかぶった非凸に注意。たとえば双線形項 $x_1 x_2$ は線形に見えて非凸。
分類は排他的でない。実問題は「非凸・離散・確率的」のように複数の難しさを併せ持つ。