数理最適化や機械学習において、本来解くべき元の最適化問題を指す用語。目的関数を最大化または最小化する制約付きの問題。対となる概念に「双対問題」があり、元となる「主問題」の最適解を直接求めるのが難しい場合などに、双対問題を解くアプローチが取られる。特にサポートベクターマシンなどで重要。
主問題とは
主問題とは、数理最適化や機械学習において、解くべき直接の対象として定式化された元の最適化問題のことです。
詳しく解説
数理最適化や機械学習（特にサポートベクターマシンやニューラルネットワークの最適化など）において、何らかの制約条件のもとで目的関数を最小化（または最大化）する問題が設定されます。これを「主問題」と呼びます。これに対して、主問題の制約条件にラグランジュ乗数を導入し、変数と制約の役割を入れ替えるように変換した問題を「双対問題」と呼びます。強双対性が成り立つ場合、主問題の最適解と双対問題の最適解は一致するため、元の主問題を解く代わりに、数学的・計算量的に扱いやすい双対問題を解くことで、主問題の最適解を間接的に得ることができます。
具体例・使われ方
代表的な例は、サポートベクターマシンにおけるマージン最大化問題です。元々の主問題は、非線形データや高次元データを扱う際にパラメータの最適化が困難になることがあります。そこで、この主問題を双対問題に変換することにより、計算がカーネル関数を用いた内積計算のみに置き換わり、高次元の特徴空間でも効率的に分類境界を学習できるようになります。
似た用語との違い
主問題と混同されやすいのが双対問題です。主問題が元の変数（例えばモデルの重み）を最適化するのに対し、双対問題はラグランジュ乗数を変数として最適化を行います。主問題が最小化問題である場合、双対問題は最大化問題となり、双対問題の解は常に主問題の解の下限を与えます。また、主成分分析などの次元削減手法における固有値問題とも文脈が異なりますが、主問題はあらゆる制約付き最適化の基本となる定式化全般を指します。
注意点
注意点として、常に主問題と双対問題の最適解が完全に一致するとは限りません。主問題の最適値と双対問題の最適値の差を双対ギャップと呼びますが、問題が凸最適化問題であり、一定の条件を満たさない限り、双対ギャップがゼロにならない弱双対性に留まることがあります。非凸な問題では強双対性が成り立たないことが多いため、主問題をそのまま解くアプローチが依然として主に使用されます。