ラグランジュデュアルとKKTの条件を1つの記事で理解する

I.最適化問題解決

1.等値制約の極値法

$$
\ begin {gather *}
h_i(t)= 0、i = 1、\ cdots、p(t)
\ end {gather *}
$$

目的関数:$ f(t)$は、ラグランジュ演算子を導入します。$ L(t、\ beta)= f(t)+ \ sum_ {i = 1} ^ n \ beta_ih_i

2.不等制約極値法

$$
\ begin {gather *}
(t)\ le 0、i = 1、\ cdots、p \\ {t} {min}
&h_j(t)= 0、j = 1、\ cdots、q
\ end {gather *}
$$

目的関数:$ f(t)$
制約:

  • $ g_i(t)\ le 0、i = 1、\ cdots、p $
  • $ h_j(t)\ le 0、j = 1、\ cdots、q $

多くの場合、不等式制約は等価制約に新しい変数を導入する可能性があるため、上記の問題は次のように単純化できます。

$$
g_i(t)= 0、i = 1、\ cdots、n {t} {min}
$$

3.最適化問題の分類

制約と目的関数のタイプに応じて、3つのカテゴリに分けられます。

  1. 線形計画法:目的関数と制約の両方が変数の線形関数です
  2. 二次計画法:目的関数は変数の二次関数であり、制約は一次関数である。
  3. 非線形計画法:目的関数または制約は非線形関数です

4. KKT条件の広い定義

KKT条件は、 非線形計画問題が特定の条件下で最適解を持つために必要かつ十分な条件であり、一般化されたラグランジュ乗数の重要な結果です(一般化最適化問題(等式制約と不等式制約制約を含む))。

$$
\ begin {gather *}
(t)\ le 0、i = 1、\ cdots、p \\ {t} {min}
&h_j(t)= 0、j = 1、\ cdots、q
\ end {gather *}
$$

ラグランジュ演算子$ \ alpha、\ beta $の紹介:

$$
(t)+ \ sum_ {j = 1} ^ q \ beta_j h_j(t)
$$

2つの制約$ g_i(t)\ le 0とg_j(t)\ 0 $のそれぞれの制約として$ \ alphaと\ beta $を考えることができます。

KKT条件は、上記の問題$ x ^ * $の最大の利点が以下を満たす必要があることを意味します。
(1)制約が満たされる:$ g_i(x ^ *)\ le0、h_i(x ^ *)= 0 $
(2)式中、L(t、\ alpha、\ beta)|| {t = x ^ *} = \ nabla f(x ^ *)+ \ sum_ {i = 1} ^ p \ alpha_i \ nabla g_i x ^ *)+ \ sum_ {j = 1} ^ q \ beta_j \ nabla h_j(x ^ *)= 0 $
すなわち、
最良の利点は$ x ^ * $、$ \ nabla f $は$ \ nabla g_i $と$ \ nabla h_j $の線形結合でなければなりません
極値を導入する理由は、ラグランジュ演算子を導入することによって得ることができる

$ f(t)$の$ dt $変化方向は他の不等式によって制約され、極値x x ^ * $では$ f(t $)$ \ nabla f(x ^ *)$と$ \ nabla g(x ^ *)$、$ \ nabla h(x ^ *)$の間には線形関係があり、ラグランジュ演算子を使って極値を見つけることができます。

(3)$ \ beta_j \ ne 0 $と$ \ alpha_i \ ge 0、\; \ alpha_i g_i(x ^ *)= 0 $

不等式$ g_i(t)\ le0 $の制約は方向性があるので、$ \ alpha_i \ ge 0 $の方程式は$ h_j(t)= 0 $の制約には方向性がないので、$ \ beta_j $は符号なしです。

5 SVMが最大化間隔の問題を解決するためにLagrange二重性を使用するのはなぜですか?

不等式制約は常に最適化問題において問題であった。二重問題を解くことは、サポートベクトルマシンの元の問題制約における不等式制約を等式制約に変換することができる。

高次元マッピングはサポートベクトルマシンで使用されますが、マッピング関数の特定の形式はほとんど完全に決定できません。二重問題を解決した後、カーネル関数を使用して問題を解決することができます。

ラグランジュ二重性を使う必要はない。 ラグランジュ二元性の使用は最適解を変えないが、アルゴリズムの複雑さを変えることに注意すべきである:
元の問題の下では、解法の複雑さはサンプルの次元(ウェイトwの次元に等しい)に関連しています。
二重問題では、アルゴリズムの複雑さはサンプル数(ラグランジアン演算子aの数に等しい)に関係しています。

このため、

  1. 線形分類を行い、サンプルの次元がサンプルの数よりも少ない場合は、元の問題の問題を解決する方が良いでしょう.Liblinearのような線形SVMはこれをデフォルトで行います。
  2. 非線形分類を行っている場合は、昇順の次元が含まれます(たとえば、カーネル関数としてガウスカーネルを使用します。実際にはサンプルを無限大にします)。また、ディメンション後のサンプルディメンションはしばしばサンプルサイズよりも大きくなります。二重問題のもとで問題を解決する方が良いでしょう。

この方法:

  • 固有ベクトルwをスケーリング係数aに変換することが可能であり、
  • 内部製品フォームを使用して目的関数をエクスポートすることができます。
  • 非線形分類の目的を達成するために、内積の後にグラム行列上のカーネル関数を使用することが可能である。

非線形法を実現するためのサポートベクトルマシンの数学的本質は、上の次元です。上の次元が無限次元に上がると、wを表現することはできませんので、ラグランジュの二重の方法を使用する方が良いです。 正確には、いくつかの最適化アルゴリズムを使用して最小間隔を直接見つけることができますが、ディメンションがディメンション化されている場合、カーネルは正定であり、昇順ディメンションはカウント可能であり、それほど大きくない場合に使用できます。

2.ラグランジュデュアルとKKT

制約付き最適化問題

制約付きの最適化は、次のように書くことができます。

$$
\ begin {gather *}
\ fI(x)\ le 0、i = 1、\ cdots、m \\
&h_i(x)= 0、i = 1、\ cdots、p
\ end {gather *}
$$

  • 任意の$ f_i(x)\ le 0 $に対して$ h_i(x)= 0 $。
  • $ maxf(x)$質問は$ 1-maxf(x)$に変換できます
  • $ f_0、f_1、\ cdots、f_m $が凸関数であるとすると、$ h_1、h_2、\ cdots、h_p $はアフィン関数($ Ax + b $など)であるとすると、上記の問題は凸最適化問題、非常にユニークな

プライマル問題

上述の制約付き最適化問題は、制約されていない最適化問題に変換され、ラグランジュ関数は以下のように定義される。

$$
pv_ih_i(x)= 1の場合には、L(x、lambda、v)= f_0(x)+ \ sum_ {i = 1} ^ m \ lambda_if_i
$$

ラグランジュを最大化する

$$
(x、\ lambda、v)は、次のように定義される。z(x)= \ underset {\ lambda \ ge 0、v}
$$

$ f_0(x)$に等しい値を持つ元の制約を満たすz(x)x:
初期の制約が満たされると、$ h_i(x)= 0 $となり、ラグランジュ関数の第3項は削除されます。
$ x L(x、\ lambda、v)= f_0(x)+ \ sum_ {i = 1} ^ m \ lambda_if_i(x)$$
そして、$ \ lambda_if_i(x)\ le0 $のため、$ L(x、\ lambda、v)$の最大値は$ f_0(x)$で得られる。

したがって、元の拘束最適化問題は、以下の拘束されていない最適化問題と同等です。

$$
\ begin {gather *}
min {f_0(x)} \; st&f_i(x)\ le 0、i = 1、\ cdots、m \\
&h_i(x)= 0、i = 1、\ cdots、p
\ end {gather *}
$$

以下に相当する:

$$
L(x、\ lambda、v){\ lambda \ ge0、v} {max} L {x} {min}
$$

上記の問題をプライム問題
要約:

  1. 制約付き最適化問題は、$ minf_0(x)$
  2. ラグランジュ関数を用いて制約付き最適化を無制約最適化問題に変換する
  3. 初期制約は常に$ f_i(x)\ le0 $とラグランジュ演算子$ \ lambda_i \ ge0 $と書くことができるので、$ maxL(x、\ lambda、v)$は制約を取り除きます:

制約するには:
\ x、\ lambda、v(x、y)= 0 \ cong \ underset {\ lambda \ ge0、v} {max} )$
最適化:
L(x、\ lambda、v)$ {un} {\ lambda \ ge0、v} {max} L(x、\ lambda、v)$ \ underset {

二重問題

二重問題は、minとmaxの位置のためのプライムプローブを単に交換するだけです:

$$
\ minders {x} {min} L(x、\ lambda、v)\ underset {\ lambda \ ge0、v}
$$

上記の数式と$$に注意してください
{max} L(x、lambda、v){un}
$$は同等ではありません。
注文:

$$
g(\ lambda、v)= \ underset {x} {min} L(x、\ lambda、v)
$$

上の式では、$ g(\ lambda、v)$はラグランジュ二重関数であり、$ g(\λ、v)$は素数関数の下限です。
つまり、prime probleの最小値が$ p ^ * $として記録されていれば、すべての$ \ lambda \ ge 0とv $に対して、次のようになります。

$$
g(\ lambda、v)\ le p ^ *
$$

証明:
制約を満たすすべてのxについて、常に次のようになります。

$$
\ sum_ {i = 1} ^ m \ lambda_i f_i(x)+ \ sum_ {i = 1} ^ pv_ih_i(x)\ le 0
$$

したがって、

$$
pv_ih_i(x)\ le f_0(x)とすると、L(x、l)= f_0(x)+ \ sum_ {i = 1} ^ m \ lambda_i f_i
$$

$ L(x、\ lambda、v)$が$ x ^ * $の極値を得たとすると、
$$ minf_0(x)= f_0(x ^ *)$$
上記の式に代入する:

$$
(x ^ *)+ \ sum_ {i = 1} ^ pv_ih_i(x ^ *) )\ le f_0(x ^ *)= p ^ *
$$

その後、

$$
(x ^ *、\ lambda、v)\ le f_0(x ^ *)= p *(x、\ lambda、v)
$$

したがって、$ g(\ lambda、v)$の下限は$ p ^ * $ですので、次のようになります。

$$
\ underset {\ lambda \ ge0、v} {max} g(\ lambda、v)
$$

主な問題の最大の下限ですか?
二重問題の最適値は$ d ^ * $であり、次のようになります。

$$
d ^ * \ le p ^ *
$$

このプロパティは弱双対と呼ばれ、すべての最適化問題に当てはまります。
さらに、
$$ p ^ * – d ^ * $$は双対ギャップと呼ばれます。

弱い二重性に基づく重要な結論:

主問題の形式に関わらず、二重問題は常に凸最適化の問題であり、その極値は固有である(存在すれば)。その二重問題のうち、この二重問題を最適化して、元の問題の推定値を下げる。

いつ
$$ d ^ * = p ^ * $$が成り立つとき、それは強い二重性と呼ばれます。

強い二重性の場合、我々は二重の問題を解決することによってプライム問題を最適化することができます。例えば、SVMの場合、強い双対性の確立を直接仮定します。

4. KKT条件

4.1スレーター状態

制約を厳密に満たす点xは、$ f_i(x)\ le0 $が$ f_i(x)<0 $に対して厳密に厳密であることを意味します。つまり、xが満たされます。

$$
F_i(x)<0 \; i = 1、\ cdots、m \\
H_i(x)= 0 \; i = 1、\ cdots、p
$$

4.2強い二重性

元の問題は凸であり、落ち着いた条件を満たす場合、強い双対性は真です:$ d ^ * = p ^ * $
特殊ケース: 非凸最適化の場合、強い双対性もまた真です。

4.3 SVMにおける強い双対性

  • SVMは一種の凸最適化であり、SVMはQP(二次計画法)によって解決され、QPは凸最適化問題の特殊なケースです。
  • スレーター条件は、データを分離するためにSVM内に超平面が存在することと等価です。

4.4強い二重性の性質

  1. プライマリおよびデュアルの問題を確認する

原始問題 :$ \ underset {x} {min} \; \ underset {\ lambda \ ge 0、v} {max} L(x、\ lambda、v)$
二重問題 :$ \ underset {\ lambda \ ge 0、v} {max} \; \ underset {x} {min} L(x、\ lambda、v)$

  1. 二重問題極値$ d ^ * $は$(\ lambda ^ *、v ^ *)$で得られ、原問題極値$ p ^ * $は$ x ^ * $で得られる
  2. 強い双対性が成立すると、$ d ^ * = p ^ * $、双対性のギャップは0
  3. $ f_0(x ^ *)\ le f_0(x ^ *)$が成立する:

$$
\ begin {align *}
F_0(x ^ *)&= g(\ lambda ^ *、v ^ *)\\
&= \ underset {x} {min}
\ left(
f_i(x)+ \ sum_ {i = 1} ^ pv_i ^ * h_i(x)
\ right)\\
(x ^ *)+ \ sum_ {i = 1} ^ pv_i ^ * h_i(x ^ *)\\ f_i(x ^ *)
&\ le f_0(x ^ *)
\ end {align *}
$$

〜によって

$$
(x)+ \ sum_ {i = 1} ^ pv_ih_i(x)\ f_0(x)
$$

取得:

$$
F_0(x ^ *)\ le L(x ^ *、\ lambda ^ *、v ^ *)
$$

だから$ x ^ * $は$ L(x、\ lambda ^ *、v ^ *)$の極端な点なので、

$$
(x ^ *)+ \ sum_ {i = 1} ^ pv_i ^ * \ nabla h_i(x ^ *) = 0 \;(条件1)
$$

〜によって

$$
f_i(x ^ *)+ \ sum_ {i_ 1} ^ \ h_i(x ^ *) *)
$$

取得:

$$
\ lambda_i ^ * f_i(x ^ *)\ le 0
$$

したがって、極端な点は$ x ^ * $です:

$$
\ lambda_i ^ * f_i(x ^ *)= 0、\; i = 1、\ cdots、m \;(条件2)
$$

条件(1)および(2)は、相補的な弛緩と総称される。

4.5補完スラックネス条件分析

条件(2)において、もし$ f_i(x ^ *)<0 $が$ \ lambda_i ^ * = 0 $を得ることができれば、$ \ lambda_i ^ *> 0 $は$ f_iこの条件は、非サポートベクトル$ f_i(x ^ *)<0 $に対して係数$ \ alpha_i $を証明するためにSVMで使用されます

4.6 KKT条件の紹介

相補スラックと他の制約条件はKKT条件です:

$$
\ begin {align *}
(x ^ *)+ \ sum_ {i = 1} ^ pv_i ^ * \ nabla h_i(x ^ *) &= 0&(条件1)\\
\ lambda_i ^ * f_i(x ^ *)&= 0、\; i = 1、\ cdots、m&(条件2)\\
F_i(x ^ *)&\ le 0、\; i = 1、\ cdots、m&(条件3)\\
\ lambda_i ^ *&\ ge0、\; i = 1、\ cdots、m&(条件4)\\
H_i(x ^ *)&= 0、\; i = 1、\ cdots、p&(条件5)
\ end {align *}
$$

  • 強い二重性を満足する問題は、KKT条件を満たす
  • 原始問題は凸最適化問題であり、KKTは必要十分条件にアップグレードされている.KKT条件は、主問題の極点である$ x ^ * $、$ 2を得るために使用できる。そして強力な二重性が確立される

要約

重大な問題の解決は、二重の問題によって得ることができます:

  1. 弱双対性のみが確立された場合、少なくとも1つの(下限問題)下限を得ることができる。
  2. 強力な二重性が確立され、次に二重の問題を直接解決する
    二重問題はプライム問題よりも解決しやすい
    二重問題には優れた構造があるかもしれません(SVMはカーネルトリックを使用するために二重問題を使用して問題を内部製品に変換します)
  3. 反復的な解決策では、同僚はデュアルとプライマリの問題を解決し、
元のリンク