1

第 3 章 最適性の条件
前回までで，数理計画問題がどのような問題であるかを説明した．その数理計画問題を計算機で解こうとした場合，どうしたらよいのだろうか？問題が与えられただけでは途方にくれてしまう．
計算機ができることは，ある点 x ∈ Rn が与えられたとき，その点での関数の値 f (x), g(x), h(x)や，それらの微分の値を計算するだけである．そのような大域的な情報が得られない計算機において，大域的最小解を求めることは容易ではない．そこで局所的最小解を求めることになるのだが，それでは，どのような条件を満たした点 x が，局所的最小解とみなすことができるのだろうか？もちろん，その条件は，計算機で容易に判別できるものでなければならない．この節の目的は，そのような最適性の条件を与えることである．
この章では，まず、制約なし最小化問題の最適性の条件を導き，それを用いて，制約つき最小化問題の最適性の条件を与えることにする．

3.1

制約無し最小化問題

制約なし問題の最適性条件は直感的にも理解しやすく、またその証明も簡単である．そこで、この節では、制約なし最小化問題の最適性の条件を実際に導く。
最適性の条件は、次のように必要条件と十分条件の 2 つにわけることができる。
点 x∗ が局所的最小解である
点 x∗ は最適性の十分条件を満たす⇒⇒

x∗ は最適性の必要条件を満たす
x∗ が局所的最小解である

もちろん、本来の目的からは、必要十分条件を導くことが望ましい。しかし、最適性の必要十分条件を持つような数理計画問題は、凸計画問題など限られた問題の種類に限られる。そこで、よりよい十分条件を求めることを考える。
十分条件は必要条件を満たさなければならないので、まず必要条件を与える。ここで，x∗ は局所的最小解であるとする．このとき，x∗ から d 方向に少しずらした点を考える．そのずれを α ∈ Rで表すこととすると，ずらした点は x∗ + αd となる．x∗ は局所的最適解であるので，α が十分小さければ，f (x∗ + αd) − f (x∗ ) ≥ 0が成り立つ．よって，α を正の領域から 0 に近づければ，合成関数の微分を考えれば、

f (x∗ + αd) − f (x∗ )= ∇f (x∗ )T dα↓0α0 ≤ limを得る．このことがすべての方向 d に対して成り立たなければならないので，∇f (x∗ ) = 0 でなければならない．この条件を制約なし最小化問題のと呼ぶ．
∗
次に，f が 2 回微分可能とする．f に対して x のまわりで 2 次のテーラー展開をすると，

f (x∗ + αd) − f (x∗ ) = α∇f (x)T d +α2 T 2d ∇ f (x∗ )d + o(α2 )
2

2

第3章

最適性の条件を得る．1 次の必要条件より ∇f (x∗ ) = 0 であり，さらに x∗ が局所的最小解であることから，

0≤f (x∗ + αd) − f (x∗ )1 T 2o(α2 )∗d=∇f(x)d+α22α2を得る．ここで，α → 0 とすると，

0 ≤ dT ∇2 f (x∗ )dを得る．これは，すべての方向 d で成り立たなければならないので，∇2 f (x∗ ) は半正定値行列でと呼ぶ．
あることを意味している．これを，以上のことをまとめると次の定理を得る．
✏

定理 1 x∗ は f の制約なし最小化問題の局所的最小解とする．また，f は x∗ の近傍で微分可能とする．このとき，(3.1)∇f (x∗ ) = 0が成り立つ (最適性の 1 次の必要条件)．さらに，f が 2 回微分可能とする．このとき，∇2 f (x∗ )は半正定値行列である (最適性の 2 次の必要条件)．

✒✑

半正定値行列 任意のベクトル x ∈ Rn に対して、

xT Ax ≥ 0となる n 行 n 列行列 A を半正定値行列と呼ぶ。さらに、0 でない任意のベクトル x ∈ Rn に対して、
xT Ax > 0が成り立てば、この行列を正定置行列と呼ぶ。たいていの線形代数の教科書で半正定値行列は扱われているが、この行列がどのようなものかイメージするのは難しい。半正定値行列は数理計画法で非常に重要な役割を果たす行列の概念である。これは、後の章で示すように、凸関数のヘシアンは半正定値行列になるからである。また、逆にすべての領域でヘシアンが半正定値行列となる関数は凸関数となる。半正定値性は、スカラーの非負性を、行列に対して一般化したものだと考えられる。実際に n = 1 のとき、行列 (スカラー)A が半正定値であるとは A ≥ 0 を意味しており、また、正定置であるとは、A > 0 を意味している。

1 次の必要条件を満たしている点を f の考えてみよう。
(3.2)
minと呼ぶことがある．ここで、次の問題を
22ex1 +x2

この問題の一次の必要条件は、
x21 +x22∇e=222x1 ex1 +x2222x1 ex1 +x2

=0となり、この条件を満たす点は、(x1 , x2 ) = (0, 0) だけである。一方、あきらかにこの点は、この問題の大域的最適解である。さらに、
2 x21 +x22

∇ e=2222222ex1 +x2 + 4x21 ex1 +x24x1 x2 ex1 +x22222224x1 x2 ex1 +x22ex1 +x2 + 4x22 ex1 +x2

3.1. 制約無し最小化問題3であるので、この点における最適性の 2 次の条件を調べてみると、
2 00 2となり、確かに半正定値行列になっている。この問題に限って言えば、1 次の”必要”条件は”十分”条件にもなっている。しかし、次の例が示すように、局所的最小解の必要条件を与えているだけで，十分条件は与えていないことに注意しよう．実際，f (x) = −x4 という関数を考えてみよう．
このとき，∇f (0) = ∇2 f (0) = 0 となるため，x̂ = 0 は 1 次，2 次両方の必要条件をみたしているが，0 はこの問題の局所的最大値であり，最小値ではない．
それでは，局所的最適解となるための十分条件になる条件は何であろうか？先ほどの例では，−x4 という関数が凹関数 (マイナスにすると凸関数になる関数) であるということに気づいたであろうか？もし，−x4 が凸関数である x4 であれば，明らかに 0 は最小解であったはずである．このことは，実は一般の凸関数に対しても言えるのである．ここで，f は凸関数で，∇f (x∗ ) = 0 だったとしよう．さらに，x̄ をこの問題の大域的最小解としよう．すると，凸関数の定義より，f (αx̄ + (1 − α)x∗ ) ≥ αf (x̄) + (1 − α)f (x∗ )が成り立つ．この式を変形すると，

f (x∗ + α(x̄ − x∗ ) − f (αx∗ )≥ f (x̄) − f (x∗ )αを得る．この左辺において，α → 0 とすると，左辺は ∇f (x∗ ) となり，x∗ が停留点であったことより 0 になる．結局，f (x∗ ) ≤ f (x̄)
を得る．x̄ が大域的最適解であったので，x∗ も大域的最適解となる．以上のことをまとめると，
✏

定理 2 目的関数 f が凸であるとする．このとき，停留点は大域的最小解である．また，f が狭義の凸関数，つまり，f (αx + (1 − α)y) < αf (x) + (1 − α)f (y) ∀α ∈ [0, 1] ∀x, y ∈ Rn with x = yを満たせば，停留点 (大域的最小解) はたかだかひとつである．

✷✒

✑となる．
次に，目的関数が凸関数でない一般の関数の場合の最適性の十分条件を考えてみよう．大域的最適解であることまで保証しなければ，x∗ のまわりで f が (狭義の) 凸関数であり，1 次の十分条件が成り立っていれば，上記の定理より，x∗ は局所的最小解であるということが期待できる (図3.1)．
以上のことをまとめると最適性の十分条件は以下のように与えられる。
✏

定理 3 f を 2 回微分可能関数とする．このとき，x∗ において∇f (x∗ ) = 0
かつ ∇2 f (x∗ ) が正定値行列とする (最適性の十分条件)．このとき，x∗ は f の制約のない最小化問題の狭義の局所的最小点となる．

✒✑4第3章

最適性の条件fx∗x
この区間で関数 f は狭義凸関数

図 3.1: 最適性の十分条件と目的関数の凸性
この定理を証明してみよう。∇2 f (x∗ ) は正定値行列であるので，次の不等式を満たす正の定数λ が存在する．
dT ∇2 f (x∗ )d ≥ λ d 2よって，2 次のテーラー展開をすると，

1λd 2 + o( d 2 )f (x∗ + d) − f (x∗ ) = ∇f (x)T d + dT ∇2 f (x∗ )d + o( d 2 ) ≥22を得る．オーダー記号 o の定義より，十分小さい d を考えると，

λλd 2 + o( d 2 ) ≤d 224となるので

λd 24を得る．よって，x∗ は f の制約のない最小化問題の狭義の局所的最小解である．
始めに考えた問題 (3.2) では、

20∇2 f (0, 0) =0 2f (x∗ + d) − f (x∗ ) ≥は正定値行列であったので、確かに十分条件が成り立っている。一方、f (x) = −x4 では、∇2 f (0) = 0であり、十分条件が成り立っていない。
このように簡単な問題では、最適性の条件を手計算で求めることによって、最適解を求めることができる場合が多い。一方、複雑な問題でも、後の章で紹介する反復法によって、最適性の 1次の必要条件を求めることが可能である。そのとき、反復法の終了条件としては、最適性の 1 次の必要条件がどれくらい満たされているか調べることによって可能である。

∇f (xk ) ≤ ε
ここで ε は、求めたい”精度”を表している。

3.2. Karush-Kuhn-Tucker 条件

5ペナルティ関数

実行可能領域 F
図 3.2: ペナルティ関数

3.2

Karush-Kuhn-Tucker 条件この節では、制約付き最小化問題の最適性の条件を考える．この条件はと呼ばれる数理計画法では非常に重要なものである．この条件を厳密に証明することは，かなりの労力を必要とするので，ここでは，直感的に導出をすることにする．
まず，制約付き最小化問題を，近似的に制約無し最小化問題に置き換えることを考える．そのために，制約をみたしていないときには，その罰として，大きな値を目的関数に付け加えることにする．そのような罰を与える関数を，一般にはペナルティー関数と呼ぶ (図 3.2)．
ここでは，等式制約に対するペナルティー関数として h(x) 2 を，不等式制約に対するペナル2ティー関数として mj=1 max{0, gj (x)} を使うことにする．このとき，ペナルティー関数を加えた，目的関数は，

θγ (x) := f (x) + γ h(x) 2 + γm

max{0, gj (x)}2j=1となる．ここで，γ はペナルティーの大きさを調節するパラメータで、ペナルティーパラメータと呼ばれる．実際，

ω(x) := lim (γ h(x)γ→∞とすると，ω(x) =2+γm

max{0, gj (x)}2 )j=10 x が制約を満たすとき∞ x が制約を満たさないときとなる．このペナルティー関数を用いた次の制約なし最小化問題を考えよう．

(3.3)

min

θγ (x)

この問題の最適解は，先ほど述べたペナルティー関数の性質より，γ → ∞ とすると，元の問題の最適解と同じになることが予想される．最小化問題 (3.3) は，制約なしの問題であるので，この問
題の最適性の 1 次の必要条件は，(3.4)

0 = ∇θγ (x) = ∇f (x) + γ∇h(x)h(x) + γ∇g(x)ĝ(x)6

第3章となる．ここで，

最適性の条件

max{0, g1 (x)}
max{0, g2 (x)} ĝ(x) = ..
. max{0, g (x)}rである．この必要条件に対して，γ → ∞ としたら，制約無し最小化問題の必要条件らしきものが出てきそうである．そこで，まず次の仮定が成り立つとしよう。
仮定 1： γ → 0 のとき，(3.4) を満たす x, γh(x) と γĝ(x) それぞれ，x∗ , µ∗ と λ∗ に収束する．
このとき，0 = ∇f (x∗ ) + ∇h(x∗ )µ∗ + ∇g(x∗ )λ∗となる．さらに，先ほどの議論より，h(x∗ ) = 0 かつ g(x∗ ) ≤ 0 でなければならない．また，ĝ(x∗ )の定義より，明らかに λ∗ ≥ 0 である．さらに，gi (x∗ ) < 0 であれば、ĝi (x∗ ) = 0 となるので，
λ∗i = limγ→∞ γĝi (x) == 0 となる．以上のことより，λ∗i gi (x∗ ) = 0 がすべての i に対して成り立つ．
ところで、これらの性質が成り立つためには、仮定 1 が成り立つ必要があった。一般にはこのが成り立てば、仮定 1 が成り立つこような仮定は成り立たないが、以下に定義するとを示すことができる。
まず，不等式制約に対して，集合 A を次のように定義する．

A(x) = {i | gi (x) = 0}
この集合をと呼ぶ．このとき，実行可能点 x に対して，∇hi (x), i = 1, . . . , m と∇gj (x), j ∈ A(x) が１次独立であるとき，x において 1 次独立の制約想定 (LICQ) が成り立つという．
この LICQ のもと、制約つき最小化問題の最適性に 1 次の必要条件が以下のように与えられる。
ここで、
L : Rn+m+r を以下のように定義する。

(3.5)

L(x, λ, µ) = f (x) + λT h(x) + µT g(x)ここで，λ，µ は，それぞれ，制約 h(x) = 0，g(x) ≤ 0 に対する元ベクトルである．と呼ばれる m, r 次

✏

定理 4 x∗ を制約つき最小化問題

minf (x)subject to h(x) = 0g(x) ≤ 0の局所的最小解とし，x∗ で LICQ が成り立つとする．このとき， 次の等式を満たすラグラン
ジュ乗数 λ∗ と µ∗ が一意に求まる．

(3.6)∇x L(x∗ , λ∗ , µ∗ ) = 0, ∇λ L(x∗ , λ∗ , µ∗ ) = 0(3.7)µ∗ ≥ 0, g(x∗ ) ≤ 0, g(x)T µ∗ = 0.

✒

この定理において，(3.6) と (3.7) を合わせて，Karush-Kuhn-Tucker 条件 (KKT 条件) と呼ばれている．図 3.3 のような物理現象を考えると，KKT 条件は理解しやすい．この図では，等高線 f (x) = c で示された地形上をボールが転がることを考えている．また，ボールが入ってはい✑3.2. Karush-Kuhn-Tucker 条件

7l"∇g 2 ( x*)∇g1 ( x*)− ∇f (x*)Ý1 (∇g ( x) = 0)1

Ý2 (∇g ( x) = 0)2

図 3.3: KKT 条件の物理的解釈
けないところは，壁 gj (x) = 0 によって塞がれている．このとき，ボールが静止するのは，局所的に窪んでおり，壁に押さえられているところである．そのため，静止しているボールにかかる力は均衡している．この均衡を表すのが，式 (3.6) である．そのとき，∇f (x∗ ) は重力から受ける力に表しており，∇g(x∗ )µ∗ は壁から受ける反作用の力を表している．(3.7) で µ∗i = 0 となるということは，壁に接していないこと (gi (x∗ ) < 0) を意味している．
なお制約想定が成り立たない場合、定理が成り立たない例として以下のものがあげられる。

minsubject toxx2 = 0

この問題の最適解は、x = 0 である。このとき、∇h(0) = 2 × 0 = 0 となり、LICQ はなりなっていない。一方、∇f (0) = 1 であり、0 = ∇x L(x∗ , λ∗ ) = 1 + λ∗ × 0 = 1となり、定理を満たす λ∗ は存在しない。
次に、制約付き最小化問題の 2 次の必要条件を与えよう。

8第3章
制約なし最小化問題

制約つき最小化問題

目的関数
全空間 Rnラグランジュ関数
T (x∗ )

ヘシアン
微小方向 d

最適性の条件表 3.1: 制約なし最小化問題と制約付き最小化問題の 2 次の必要条件
✏

定理 5 x∗ を非線形最小化問題

minf (x)subject to h(x) = 0g(x) ≤ 0の局所的最小解とし，x∗ で LICQ が成り立つとする．さらに f と h が 2 回微分可能であるならば，y T ∇2xx L(x∗ , λ∗ )y ≥ 0 ∀y ∈ T (x∗ )ここで T (x∗ ) はT (x∗ ) = {y|∇hi (x∗ )T y = 0, i = 1, . . . , m, ∇gj (x∗ )T y = 0 ∀j ∈ A(x∗ )}.
である．

✒✑

証明は大変なため省略するが、簡単な意味を説明しておこう。まず, 集合 T (x∗ ) は、x∗ からh(x) = 0, gj (x) = 0, j ∈ A(x∗ ) を満たすように微小に動かすことができる方向 d の集合である。
そして、その方向に対して、ラグランジュ関数は半正定値行列であるということを意味している。
このことは、さらに、その方向に対してラグランジュ関数の値が増えないことを意味している。
この関係は制約なし最小化問題の最適性の 2 次の必要条件と対応付けて考えると理解しやすい (表3.1)。
後の章で紹介する制約付き最小化問題に対する多くの解法では，この Karush-Kuhn-Tucker 条
件を満たす点 (KKT 点) を求めることが目的となっている．もちろん，この条件は必要条件であり，この条件をみたしているからといって，x∗ が局所的最小解となるとは限らない．例えば、minsubject to−x4x2 − 1 ≤ 0を考えてみよう。このとき、x = 0 は必要条件を満たしているが、この点は局所的最小解ではない。一方，f, g が凸関数, h がアフィン関数で与えられていれば，LICQ のもと，KKT 条件は必要十分条件になることが知られている．
✏定理 6 f, g が凸関数, h がアフィン関数であるとする。点 x∗ 点いおいて LICQ が成り立つとする。このとき、x∗ が最小化問題の大域的最適解であることの必要十分条件は Karush-Kuhn✷
Tucker 条件を満たす (x∗ , λ∗ , µ∗ ) が存在することである。
✒✑

3.2. Karush-Kuhn-Tucker 条件

9練習問題 1 次の問題の解を求めよ。

minsubject tox21 + x22−x1 − x2 + 1 ≤ 0

次に f, g を凸関数と仮定しない場合における十分条件を与える．

✏定理 7 f と h と g が 2 回微分可能であるとする．x∗ と λ∗ と µ∗ は次の条件を満たすとする．

∇x L(x∗ , λ∗ , µ∗ ) = 0, ∇λ L(x∗ , λ∗ , µ∗ ) = 0µ∗ ≥ 0, g(x∗ ) ≤ 0, g(x∗ )T µ∗ = 0.
y T ∇2xx L(x∗ , λ∗ , µ∗ )y > 0 ∀y ∈ T (x∗ ) with y = 0
ここで，T (x∗ ) はT (x∗ ) = {y|∇hi (x∗ )T y = 0, i = 1, . . . , m, ∇gj (x∗ )T y = 0 ∀j ∈ A(x∗ )}.
である．さらに，(3.8)µ∗j − gj (x∗ ) > 0 ∀jが成り立つとする．このとき，x∗ は問題の狭義局所的最小解である．
✒✷✑

この定理の意味するところは、制約条件を満たすように変化するときにはラグランジュ関数は増加するということである。つまりラグランジュ関数が狭義の凸関数のようなものになっているということができる。
この定理中の (3.8) を，と呼ぶ．この定理で示された最適性の十分条件のもとで，制約付き最小化問題に対する多くのアルゴリズムが超一次収束することが示されている．