← 戻る ライブラリ › 応用数学と計算数学 › 最適化理論 応用数学と計算数学
凸最適化 凸集上で凸関数を最小化する: なぜすべての局所最小が大域的最小になるのか、最適性を保証するKKT条件、そして難しい探索をより易しい探索に変える双対性について。
直観 なぜ形が重要か：凸と非凸 常に下り坂へ進むことで地形の最も低い点を探すところを想像してほしい。地形がひとつのお椀のような形なら、この貪欲な戦略はどこから始めても必ず本当の最低点を見つける。いくつものくぼみ、尾根、鞍状の峠がある地形では、同じ戦略が最低点でも何でもないくぼみで止まってしまうことがある。凸最適化はまさにこの「ひとつのお椀」の場合を研究し、なぜそれがこれほど扱いやすいのかを正確に説明する。
z = x 2 + y 2 z = x^2 + y^2 z = x 2 + y 2 z = x 2 − y 2 z = x^2 - y^2 z = x 2 − y 2 同じ罠の1次元版: 3次曲線には、全体で最も低い点ではない谷（局所最小）が存在しうる。なぜなら曲線はさらに遠くでも下降し続けるからだ。凸性はまさにこれを排除する性質である。
y = x 3 − 3 x y = x^3 - 3x y = x 3 − 3 x − ∞ -\infty − ∞ x → − ∞ x \to -\infty x → − ∞ 大学 凸集合と凸関数 定義: 凸集合
集合 C ⊆ R n C \subseteq \mathbb{R}^n C ⊆ R n 凸 であるとは、任意の x , y ∈ C x, y \in C x , y ∈ C θ ∈ [ 0 , 1 ] \theta \in [0,1] θ ∈ [ 0 , 1 ] θ x + ( 1 − θ ) y \theta x + (1-\theta) y θ x + ( 1 − θ ) y C C C C C C C C C
定義: 凸関数
関数 f : C → R f : C \to \mathbb{R} f : C → R C C C 凸 であるとは、任意の x , y ∈ C x, y \in C x , y ∈ C θ ∈ [ 0 , 1 ] \theta \in [0,1] θ ∈ [ 0 , 1 ] f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) f(\theta x + (1-\theta) y) \le \theta f(x) + (1-\theta) f(y) f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) f f f
f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) , θ ∈ [ 0 , 1 ] f(\theta x + (1-\theta) y) \le \theta f(x) + (1-\theta) f(y), \qquad \theta \in [0,1] f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) , θ ∈ [ 0 , 1 ] f f f ヘッセ行列 ∇ 2 f ( x ) \nabla^2 f(x) ∇ 2 f ( x ) C C C f ′ ′ ≥ 0 f'' \ge 0 f ′′ ≥ 0 凸最適化問題 とは、凸関数 f f f C C C C = { x : g i ( x ) ≤ 0 , h j ( x ) = 0 } C = \{x : g_i(x) \le 0, h_j(x) = 0\} C = { x : g i ( x ) ≤ 0 , h j ( x ) = 0 } g i g_i g i h j h_j h j
f f f C C C x ⋆ x^\star x ⋆ f f f C C C x ⋆ x^\star x ⋆ f f f C C C
なぜ正しいのか? x ⋆ x^\star x ⋆ y ∈ C y \in C y ∈ C f ( y ) < f ( x ⋆ ) f(y) < f(x^\star) f ( y ) < f ( x ⋆ ) f f f x ⋆ x^\star x ⋆ y y y x ⋆ x^\star x ⋆ θ > 0 \theta > 0 θ > 0 f ( θ y + ( 1 − θ ) x ⋆ ) ≤ θ f ( y ) + ( 1 − θ ) f ( x ⋆ ) < f ( x ⋆ ) f(\theta y + (1-\theta) x^\star) \le \theta f(y) + (1-\theta) f(x^\star) < f(x^\star) f ( θ y + ( 1 − θ ) x ⋆ ) ≤ θ f ( y ) + ( 1 − θ ) f ( x ⋆ ) < f ( x ⋆ ) x ⋆ x^\star x ⋆ θ y + ( 1 − θ ) x ⋆ \theta y + (1-\theta)x^\star θ y + ( 1 − θ ) x ⋆ x ⋆ x^\star x ⋆
証明 x ⋆ ∈ C x^\star \in C x ⋆ ∈ C r > 0 r > 0 r > 0 ∥ z − x ⋆ ∥ ≤ r \|z - x^\star\| \le r ∥ z − x ⋆ ∥ ≤ r z ∈ C z \in C z ∈ C f ( z ) ≥ f ( x ⋆ ) f(z) \ge f(x^\star) f ( z ) ≥ f ( x ⋆ ) y ∈ C y \in C y ∈ C f ( y ) < f ( x ⋆ ) f(y) < f(x^\star) f ( y ) < f ( x ⋆ )
任意の θ ∈ ( 0 , 1 ) \theta \in (0, 1) θ ∈ ( 0 , 1 ) z θ = θ y + ( 1 − θ ) x ⋆ ∈ C z_\theta = \theta y + (1 - \theta)x^\star \in C z θ = θ y + ( 1 − θ ) x ⋆ ∈ C f ( z θ ) ≤ θ f ( y ) + ( 1 − θ ) f ( x ⋆ ) = f ( x ⋆ ) + θ ( f ( y ) − f ( x ⋆ ) ) < f ( x ⋆ ) f(z_\theta) \le \theta f(y) + (1 - \theta)f(x^\star) = f(x^\star) + \theta(f(y) - f(x^\star)) < f(x^\star) f ( z θ ) ≤ θ f ( y ) + ( 1 − θ ) f ( x ⋆ ) = f ( x ⋆ ) + θ ( f ( y ) − f ( x ⋆ )) < f ( x ⋆ )
∥ z θ − x ⋆ ∥ = θ ∥ y − x ⋆ ∥ \|z_\theta - x^\star\| = \theta \|y - x^\star\| ∥ z θ − x ⋆ ∥ = θ ∥ y − x ⋆ ∥ 0 < θ ≤ r ∥ y − x ⋆ ∥ 0 < \theta \le \dfrac{r}{\|y - x^\star\|} 0 < θ ≤ ∥ y − x ⋆ ∥ r ∥ z θ − x ⋆ ∥ ≤ r \|z_\theta - x^\star\| \le r ∥ z θ − x ⋆ ∥ ≤ r f ( z θ ) < f ( x ⋆ ) f(z_\theta) < f(x^\star) f ( z θ ) < f ( x ⋆ )
よくある誤り. 上で見た鞍面と3次曲線は、まさにこの定理が凸問題に対して排除するものである: 鞍点や大域的でない局所最小が起こるのは、f f f ない 場合に限られる。先に凸性を確かめておけば、「局所最小を見つけた」がすでに「問題を解いた」を意味するかどうかがわかる。 大学 制約付き問題とKKT条件 制約のない微分可能な凸関数 f f f x ⋆ x^\star x ⋆ ∇ f ( x ⋆ ) = 0 \nabla f(x^\star) = 0 ∇ f ( x ⋆ ) = 0 f ( x ) f(x) f ( x ) g i ( x ) ≤ 0 g_i(x) \le 0 g i ( x ) ≤ 0 i = 1 , … , m i=1,\dots,m i = 1 , … , m h j ( x ) = 0 h_j(x) = 0 h j ( x ) = 0 j = 1 , … , p j=1,\dots,p j = 1 , … , p λ i ≥ 0 \lambda_i \ge 0 λ i ≥ 0 ν j ∈ R \nu_j \in \mathbb{R} ν j ∈ R ラグランジュ関数 を導入する:
L ( x , λ , ν ) = f ( x ) + ∑ i = 1 m λ i g i ( x ) + ∑ j = 1 p ν j h j ( x ) \mathcal{L}(x,\lambda,\nu) = f(x) + \sum_{i=1}^m \lambda_i\, g_i(x) + \sum_{j=1}^p \nu_j\, h_j(x) L ( x , λ , ν ) = f ( x ) + i = 1 ∑ m λ i g i ( x ) + j = 1 ∑ p ν j h j ( x ) 正則条件（例えばスレーター条件: すべての g i ( x ) < 0 g_i(x) < 0 g i ( x ) < 0 h j ( x ) = 0 h_j(x) = 0 h j ( x ) = 0 x ⋆ x^\star x ⋆ λ ⋆ , ν ⋆ \lambda^\star, \nu^\star λ ⋆ , ν ⋆ 停留性 ∇ x L ( x ⋆ , λ ⋆ , ν ⋆ ) = 0 \nabla_x \mathcal{L}(x^\star, \lambda^\star, \nu^\star) = 0 ∇ x L ( x ⋆ , λ ⋆ , ν ⋆ ) = 0 主実行可能性 g i ( x ⋆ ) ≤ 0 g_i(x^\star) \le 0 g i ( x ⋆ ) ≤ 0 h j ( x ⋆ ) = 0 h_j(x^\star) = 0 h j ( x ⋆ ) = 0 双対実行可能性 λ i ⋆ ≥ 0 \lambda_i^\star \ge 0 λ i ⋆ ≥ 0 相補スラック性 λ i ⋆ g i ( x ⋆ ) = 0 \lambda_i^\star g_i(x^\star) = 0 λ i ⋆ g i ( x ⋆ ) = 0 i i i
なぜ正しいのか? 相補スラック性は、不等式制約 g i ( x ) ≤ 0 g_i(x) \le 0 g i ( x ) ≤ 0 x ⋆ x^\star x ⋆ 非有効 である（g i ( x ⋆ ) < 0 g_i(x^\star) < 0 g i ( x ⋆ ) < 0 x ⋆ x^\star x ⋆ λ i ⋆ = 0 \lambda_i^\star = 0 λ i ⋆ = 0 有効 である（g i ( x ⋆ ) = 0 g_i(x^\star) = 0 g i ( x ⋆ ) = 0 λ i ⋆ ≥ 0 \lambda_i^\star \ge 0 λ i ⋆ ≥ 0 − ∇ f ( x ⋆ ) -\nabla f(x^\star) − ∇ f ( x ⋆ ) ∇ g i ( x ⋆ ) \nabla g_i(x^\star) ∇ g i ( x ⋆ )
証明 まず、( x ⋆ , λ ⋆ , ν ⋆ ) (x^\star, \lambda^\star, \nu^\star) ( x ⋆ , λ ⋆ , ν ⋆ ) λ i ⋆ ≥ 0 \lambda_i^\star \ge 0 λ i ⋆ ≥ 0 x ↦ L ( x , λ ⋆ , ν ⋆ ) x \mapsto \mathcal{L}(x, \lambda^\star, \nu^\star) x ↦ L ( x , λ ⋆ , ν ⋆ ) ∇ x L ( x ⋆ , λ ⋆ , ν ⋆ ) = 0 \nabla_x \mathcal{L}(x^\star, \lambda^\star, \nu^\star) = 0 ∇ x L ( x ⋆ , λ ⋆ , ν ⋆ ) = 0
g i ( x ) ≤ 0 g_i(x) \le 0 g i ( x ) ≤ 0 h j ( x ) = 0 h_j(x) = 0 h j ( x ) = 0 x x x λ i ⋆ g i ( x ⋆ ) = 0 \lambda_i^\star g_i(x^\star) = 0 λ i ⋆ g i ( x ⋆ ) = 0 f ( x ⋆ ) = L ( x ⋆ , λ ⋆ , ν ⋆ ) ≤ L ( x , λ ⋆ , ν ⋆ ) = f ( x ) + ∑ i = 1 m λ i ⋆ g i ( x ) + ∑ j = 1 p ν j ⋆ h j ( x ) ≤ f ( x ) f(x^\star) = \mathcal{L}(x^\star, \lambda^\star, \nu^\star) \le \mathcal{L}(x, \lambda^\star, \nu^\star) = f(x) + \sum_{i=1}^m \lambda_i^\star g_i(x) + \sum_{j=1}^p \nu_j^\star h_j(x) \le f(x) f ( x ⋆ ) = L ( x ⋆ , λ ⋆ , ν ⋆ ) ≤ L ( x , λ ⋆ , ν ⋆ ) = f ( x ) + ∑ i = 1 m λ i ⋆ g i ( x ) + ∑ j = 1 p ν j ⋆ h j ( x ) ≤ f ( x )
逆にスレーター条件のもとでは、強双対性により双対最適乗数が存在して f ( x ⋆ ) = g ( λ ⋆ , ν ⋆ ) = inf x L ( x , λ ⋆ , ν ⋆ ) ≤ L ( x ⋆ , λ ⋆ , ν ⋆ ) = f ( x ⋆ ) + ∑ i = 1 m λ i ⋆ g i ( x ⋆ ) ≤ f ( x ⋆ ) f(x^\star) = g(\lambda^\star, \nu^\star) = \inf_x \mathcal{L}(x, \lambda^\star, \nu^\star) \le \mathcal{L}(x^\star, \lambda^\star, \nu^\star) = f(x^\star) + \sum_{i=1}^m \lambda_i^\star g_i(x^\star) \le f(x^\star) f ( x ⋆ ) = g ( λ ⋆ , ν ⋆ ) = inf x L ( x , λ ⋆ , ν ⋆ ) ≤ L ( x ⋆ , λ ⋆ , ν ⋆ ) = f ( x ⋆ ) + ∑ i = 1 m λ i ⋆ g i ( x ⋆ ) ≤ f ( x ⋆ )
例: 直線上で原点に最も近い点
f ( x , y ) = x 2 + y 2 f(x,y) = x^2 + y^2 f ( x , y ) = x 2 + y 2 x + y = 1 x + y = 1 x + y = 1
解答 f f f h ( x , y ) = x + y − 1 = 0 h(x,y) = x + y - 1 = 0 h ( x , y ) = x + y − 1 = 0 L ( x , y , ν ) = x 2 + y 2 + ν ( x + y − 1 ) \mathcal{L}(x,y,\nu) = x^2 + y^2 + \nu(x + y - 1) L ( x , y , ν ) = x 2 + y 2 + ν ( x + y − 1 ) 2 x + ν = 0 2x + \nu = 0 2 x + ν = 0 2 y + ν = 0 2y + \nu = 0 2 y + ν = 0 x = y x = y x = y x + y = 1 x + y = 1 x + y = 1 x ⋆ = y ⋆ = 1 2 x^\star = y^\star = \tfrac{1}{2} x ⋆ = y ⋆ = 2 1 f ( x ⋆ , y ⋆ ) = 1 2 f(x^\star, y^\star) = \tfrac{1}{2} f ( x ⋆ , y ⋆ ) = 2 1
例: 相補スラック性による有効な不等式制約の解法
不等式制約 g ( x ) = x − 1 ≤ 0 g(x) = x - 1 \le 0 g ( x ) = x − 1 ≤ 0 f ( x ) = ( x − 3 ) 2 f(x) = (x - 3)^2 f ( x ) = ( x − 3 ) 2
解答 ラグランジュ関数 L ( x , λ ) = ( x − 3 ) 2 + λ ( x − 1 ) \mathcal{L}(x, \lambda) = (x - 3)^2 + \lambda(x - 1) L ( x , λ ) = ( x − 3 ) 2 + λ ( x − 1 ) ∂ L ∂ x = 2 ( x − 3 ) + λ = 0 \dfrac{\partial \mathcal{L}}{\partial x} = 2(x - 3) + \lambda = 0 ∂ x ∂ L = 2 ( x − 3 ) + λ = 0 x − 1 ≤ 0 x - 1 \le 0 x − 1 ≤ 0 λ ≥ 0 \lambda \ge 0 λ ≥ 0 λ ( x − 1 ) = 0 \lambda(x - 1) = 0 λ ( x − 1 ) = 0
相補スラック性から2つの場合を調べる：もし λ = 0 \lambda = 0 λ = 0 x = 3 x = 3 x = 3 x − 1 ≤ 0 x - 1 \le 0 x − 1 ≤ 0
したがって制約は有効でなければならず、x ⋆ = 1 x^\star = 1 x ⋆ = 1 λ ⋆ = 2 ( 3 − 1 ) = 4 > 0 \lambda^\star = 2(3 - 1) = 4 > 0 λ ⋆ = 2 ( 3 − 1 ) = 4 > 0 λ ≥ 0 \lambda \ge 0 λ ≥ 0 x ⋆ = 1 x^\star = 1 x ⋆ = 1 f ( 1 ) = 4 f(1) = 4 f ( 1 ) = 4
発展 双対性と凸性を超える大域的最適化 L ( x , λ , ν ) \mathcal{L}(x,\lambda,\nu) L ( x , λ , ν ) x x x ラグランジュ双対関数 g ( λ , ν ) = inf x L ( x , λ , ν ) g(\lambda,\nu) = \inf_x \mathcal{L}(x,\lambda,\nu) g ( λ , ν ) = inf x L ( x , λ , ν ) g g g ( λ , ν ) (\lambda,\nu) ( λ , ν ) g g g 凹関数 である。任意の λ ≥ 0 \lambda \ge 0 λ ≥ 0 x x x λ i g i ( x ) ≤ 0 \lambda_i g_i(x) \le 0 λ i g i ( x ) ≤ 0 ν j h j ( x ) = 0 \nu_j h_j(x) = 0 ν j h j ( x ) = 0 g ( λ , ν ) ≤ f ( x ) g(\lambda,\nu) \le f(x) g ( λ , ν ) ≤ f ( x ) g ( λ , ν ) g(\lambda,\nu) g ( λ , ν ) λ ≥ 0 \lambda \ge 0 λ ≥ 0 双対問題 と呼ばれ、その最適値 d ⋆ d^\star d ⋆ 弱双対性 d ⋆ ≤ p ⋆ d^\star \le p^\star d ⋆ ≤ p ⋆ d ⋆ = p ⋆ d^\star = p^\star d ⋆ = p ⋆ 強双対性 が成り立つといい、双対ギャップ p ⋆ − d ⋆ p^\star - d^\star p ⋆ − d ⋆
主線形計画問題 min { c ⊤ x : A x = b , x ≥ 0 } \min\{c^\top x : Ax = b,\; x \ge 0\} min { c ⊤ x : A x = b , x ≥ 0 } x ⋆ x^\star x ⋆ max { b ⊤ y : A ⊤ y ≤ c } \max\{b^\top y : A^\top y \le c\} max { b ⊤ y : A ⊤ y ≤ c } y ⋆ y^\star y ⋆ c ⊤ x ⋆ = b ⊤ y ⋆ c^\top x^\star = b^\top y^\star c ⊤ x ⋆ = b ⊤ y ⋆
なぜ正しいのか? 線形計画問題は多面体の実行可能集合を持つ凸問題である。多面体制約では内点の仮定は不要であり、分離超平面定理（ファルカシュの補題）によって双対ギャップがゼロとなる双対乗数 y ⋆ y^\star y ⋆
証明 A x = b Ax = b A x = b x ≥ 0 x \ge 0 x ≥ 0 A ⊤ y ≤ c A^\top y \le c A ⊤ y ≤ c b ⊤ y = ( A x ) ⊤ y = x ⊤ ( A ⊤ y ) ≤ x ⊤ c = c ⊤ x b^\top y = (Ax)^\top y = x^\top(A^\top y) \le x^\top c = c^\top x b ⊤ y = ( A x ) ⊤ y = x ⊤ ( A ⊤ y ) ≤ x ⊤ c = c ⊤ x
乗数 s ≥ 0 s \ge 0 s ≥ 0 L ( x , y , s ) = c ⊤ x + y ⊤ ( b − A x ) − s ⊤ x = b ⊤ y + ( c − A ⊤ y − s ) ⊤ x \mathcal{L}(x, y, s) = c^\top x + y^\top(b - Ax) - s^\top x = b^\top y + (c - A^\top y - s)^\top x L ( x , y , s ) = c ⊤ x + y ⊤ ( b − A x ) − s ⊤ x = b ⊤ y + ( c − A ⊤ y − s ) ⊤ x c − A ⊤ y − s = 0 c - A^\top y - s = 0 c − A ⊤ y − s = 0 g ( y , s ) = b ⊤ y g(y, s) = b^\top y g ( y , s ) = b ⊤ y
x ⋆ x^\star x ⋆ p ⋆ = c ⊤ x ⋆ p^\star = c^\top x^\star p ⋆ = c ⊤ x ⋆ A ⊤ y ⋆ ≤ c A^\top y^\star \le c A ⊤ y ⋆ ≤ c b ⊤ y ⋆ ≥ p ⋆ b^\top y^\star \ge p^\star b ⊤ y ⋆ ≥ p ⋆ y ⋆ y^\star y ⋆ b ⊤ y ⋆ = c ⊤ x ⋆ b^\top y^\star = c^\top x^\star b ⊤ y ⋆ = c ⊤ x ⋆
歴史的ノート
問題が本質的に非凸 である場合はどうなるだろうか — 例えば、多面体上で凹 関数を最小化する問題（最小値は内部ではなく頂点に現れる）や、2つの凸関数の差 f ( x ) = g ( x ) − h ( x ) f(x) = g(x) - h(x) f ( x ) = g ( x ) − h ( x ) ホアン・トゥイ （Hoàng Tụy, 1927–2019）は線形制約下の凹最小化に対する凹カット（トゥイのカット ）を導入した。この論文は、凸性によって局所最小が大域的最小であることが保証されない状況で真の大域的最適解を体系的に探す、決定論的大域的最適化 の創始論文として広く認められている。
ホアン・トゥイ
R n \mathbb{R}^n R n 手法の族 1ステップの情報 1ステップの計算量 精度 ε \varepsilon ε 勾配法 / 加速勾配法（ネステロフ） 1次（∇ f \nabla f ∇ f O ( n ) O(n) O ( n ) O ( 1 / ε ) O(1/\varepsilon) O ( 1/ ε ) O ( 1 / ε ) O(1/\sqrt{\varepsilon}) O ( 1/ ε ) ニュートン法 2次（∇ f , ∇ 2 f \nabla f, \nabla^2 f ∇ f , ∇ 2 f O ( n 3 ) O(n^3) O ( n 3 ) 局所的に O ( log log ( 1 / ε ) ) O(\log\log(1/\varepsilon)) O ( log log ( 1/ ε )) 内点法（バリア法） − ∑ ln ( − g i ) -\sum \ln(-g_i) − ∑ ln ( − g i ) ニュートン1ステップあたり O ( n 3 ) O(n^3) O ( n 3 ) O ( m log ( 1 / ε ) ) O(\sqrt{m}\,\log(1/\varepsilon)) O ( m log ( 1/ ε ))
研究の最前線 2026年時点
2026年現在 、凸最適化の研究と応用は2つの領域に大別される。高精度を要する中規模問題（n n n 内点法 が、線形・二次・二次錐・半正定値計画問題を数十回のニュートン反復で解く。近年の理論研究では、線形計画法の最悪計算量は行列積の指数に近いところまで改善されている。一方、機械学習や信号処理の超大規模問題（n n n O ( n 3 ) O(n^3) O ( n 3 ) O ( 1 / k 2 ) O(1/k^2) O ( 1/ k 2 ) 1次法・確率的手法 が主力となっている。現在の研究課題には、高次滑らかさのもとでの最適計算量限界、通信最適分散凸最適化、そして凸理論の保証（暗黙の正則化や良性な鞍点幾何など）のどれが深層ネットワークの非凸損失地形に引き継がれるかの解明がある。
R \mathbb{R} R
f ( x ) = x 2 f(x)=x^2 f ( x ) = x 2 f ( x ) = − x 2 f(x)=-x^2 f ( x ) = − x 2 f ( x ) = x 3 − 3 x f(x)=x^3-3x f ( x ) = x 3 − 3 x f ( x ) = sin x f(x)=\sin x f ( x ) = sin x 凸最適化問題において、局所最小である点は
常に大域的最小である 実行可能集合が有界な場合にのみ大域的最小である それが一意でない限り大域的最小にはならない 鞍点である
KKT条件における相補スラック性 λ i ⋆ g i ( x ⋆ ) = 0 \lambda_i^\star g_i(x^\star) = 0 λ i ⋆ g i ( x ⋆ ) = 0
非有効な不等式制約（g i ( x ⋆ ) < 0 g_i(x^\star) < 0 g i ( x ⋆ ) < 0 λ i ⋆ = 0 \lambda_i^\star = 0 λ i ⋆ = 0 最適点ではすべての制約が有効でなければならない すべての乗数は正でなければならない 目的関数は最適点でゼロにならなければならない 実行可能かつ有界な最適解を持つ線形計画問題に対して、強双対性が示すのは
双対最適値は主最適値と等しい 双対問題には解がない 双対ギャップは問題サイズとともに大きくなる これは非線形凸計画問題でのみ保証される