凸最適化の完全ガイド：概要・性質・標準形と実務応用まで徹底解説
エバープレイ編集部凸最適化とは——概要と直感
凸最適化（convex optimization）は、目的関数が凸関数であり、制約集合が凸集合で表される最適化問題のクラスを指します。数学的には「グローバルな最小値が局所最小値でもある」性質を持つため、解の探索が比較的容易であり、理論的な保証や効率的なアルゴリズムが豊富に存在します。機械学習、信号処理、制御、金融工学など幅広い分野で用いられる基礎的な道具です。
凸関数と凸集合の定義（直感と正式）
直感的には、凸集合は任意の2点を結ぶ線分が集合に全て含まれる集合を指し、凸関数は定義域上の任意の2点を結ぶ線分の上の関数値が、その線分上の線形補間よりも下（または等しい）にある関数です。
- 凸集合 C: 任意の x,y∈C と 0≤t≤1 に対し tx+(1−t)y ∈ C。
- 凸関数 f: 定義域 D 上で任意の x,y∈D と 0≤t≤1 に対し f(tx+(1−t)y) ≤ t f(x) + (1−t) f(y)。
別表現として、関数 f のエピグラフ（epigraph）{(x,α) | α ≥ f(x)} が凸集合であることが凸関数の条件です。
凸最適化問題の標準形
一般的な凸最適化問題は次のように表現されます。
minimize f0(x) subject to fi(x) ≤ 0 (i=1,...,m), Aj x = bj (j=1,...,p)
ここで f0 は凸関数、各 fi は凸関数（不等式制約）、等式制約は線形であることが一般的です。二次形式であれば二次計画問題（QP）、半正定値行列を扱えば半定値計画（SDP）、二次錐を扱えば二次錐計画（SOCP）に分類されます。
凸最適化の重要な性質
- 局所最適解＝大域最適解：凸問題では局所的な最小点は必ずグローバルな最小点。
- 双対性（Lagrange双対）：凸性とスレーターの条件が満たされれば強双対が成立し、双対問題の最適値は主問題の最適値に等しい。
- 計算可能性：多くの凸問題は多項式時間で解けるアルゴリズム（内点法など）を持つ。
- 安定性と感度解析：最適解はパラメータ変化に対する解析がしやすい。
代表的な凸最適化の例
- 線形計画（LP）: 目的・制約が線形。Simplex法や内点法。
- 二次計画（QP）: 目的関数が凸な二次形式。サポートベクターマシン（SVM）の学習が代表例。
- 二次錐計画（SOCP）: 二次錐制約を含む問題。ロバスト最適化などで利用。
- 半正定値計画（SDP）: 行列変数と半正定値制約を扱う。構造推定や緩和手法に使われる。
- 最小二乗・LASSO・ロジスティック回帰：正則化を付けた凸損失最小化問題で、機械学習の基礎。
解法アルゴリズムの概要
凸最適化には問題の性質や規模に応じたさまざまなアルゴリズムがあります。
- 内点法（Interior-point methods）: 多くの凸問題（特に中規模のLP/QP/SDP）を高精度で解く。理論的に多項式時間。
- 一階法（Gradient, Subgradient, Proximal gradient）: 大規模データに適しており、確率的勾配法（SGD）やProximal法は疎性や非微分項（L1正則化）に対応。
- 拡張ADMM（Alternating Direction Method of Multipliers）: 問題を分解して並列処理しやすい。大規模・分散環境で有効。
- 専用ソルバ（OSQP, ECOS, SCS, MOSEK など）: 問題クラス（QP, SOCP, SDP, conic）に最適化された実装。
双対性とKKT条件
ラグランジュ双対は凸最適化の中心概念です。ラグランジュ関数を導入し、双対関数を最大化することで下界を得ます。凸最適化ではスレーター条件（内点が存在する程度の満たしやすい制約条件）が満たされれば強双対が成立し、主問題と双対問題の最適値が一致します。
KKT（Karush–Kuhn–Tucker）条件は最適性の必要十分条件を与えます（凸問題においては十分）。KKT 条件は、停留条件、可行性、双対可行性、補完スラック性を含みます。
凸緩和と非凸問題への応用
多くの実世界問題は非凸ですが、凸緩和（convex relaxation）を用いて近似解や下界を得る手法が広く使われます。例として、整数計画問題を線形緩和する、あるいは非凸双対問題をSDPに緩和する手法があります。これにより計算可能な下界や高品質な近似解が得られます。
実務上のポイントとモデリングのコツ
- 凸性の確認：目的関数や制約が凸かどうかをまず理論的に確認する。凸でない場合は変数変換や緩和を検討。
- スケーリング：数値安定性のために変数やデータのスケールを揃える。
- 構造利用：疎性やブロック構造がある場合は専用アルゴリズムや分散化で効率化。
- 精度と計算時間のトレードオフ：内点法は高精度だがメモリが増える。一階法やADMMは低メモリで大規模向け。
- 検証：双対ギャップやKKT残差を用いて解の品質を評価。
よくある誤解と注意点
- 凸であれば簡単、とは限らない：理論的には解きやすいが、超大規模問題や厳しい精度要求では計算負荷が高い。
- ローカル最適性の問題はないが、数値問題は存在する：丸め誤差や不十分なスケーリングで現実的に困る場合がある。
- 非凸問題を凸化すると可解性は上がるが、元問題の最適解とは乖離する可能性がある。
代表的なソフトウェア・ライブラリ
- CVX (MATLAB) / CVXPy (Python): モデル記述が宣言的で使いやすく、内部で適切なソルバへ変換される。
- MOSEK: 高性能な商用ソルバ（conic、QP、SOCP、SDP など）。
- ECOS, SCS, OSQP: オープンソースの高速ソルバ（それぞれ SOCP、conic、QPs に特化）。
- CVXOPT: Python ベースの最適化ライブラリ。
応用例（具体的）
- 機械学習: ロジスティック回帰、SVM、Lasso（L1正則化付き回帰）などは凸問題として学習可能。
- 信号処理: スパース復元（compressed sensing）はL1最小化の凸問題。
- 制御理論: ロバスト制御や最適制御の一部設定は凸化して解かれる。
- 金融: ポートフォリオ最適化（平均分散最適化）は二次計画としてモデル化。
まとめ（なぜ学ぶ価値があるか）
凸最適化は理論的な保証、効率的なアルゴリズム、実務での豊富な応用例を併せ持つ重要分野です。問題が凸であることを見抜いて適切なアルゴリズムやソルバを選べば、高速かつ安定に最適化問題を解けます。一方で、実装上のスケーリングや数値安定性、非凸問題への適用時の限界など実務的注意点もありますので、理論と実装の両面で理解することが重要です。
参考文献
- Stephen Boyd and Lieven Vandenberghe, "Convex Optimization" (2004) — Book and online notes
- Wikipedia: Convex optimization
- CVXPY — A Python-embedded modeling language for convex optimization
- MOSEK — Optimization software
- ECOS — Embedded conic solver
- OSQP — Operator Splitting QP Solver
- Boyd's lectures and course materials on convex optimization (Stanford)
投稿者プロフィール
