Singkatnya, secara grafis

Objektif

Konfirmasikan apakah pemahaman tentang KKT benar atau tidak. Cari penjelasan dan konfirmasi lebih lanjut tentang KKT.

Latar Belakang

Mencoba memahami kondisi KKT, terutama yang saling melengkapi, yang selalu muncul tiba-tiba dalam artikel SVM. Saya tidak perlu daftar formula abstrak tetapi perlu penjelasan konkret, intuitif, dan grafis.

Pertanyaan

Jika P, yang meminimalkan fungsi biaya f (X), berada di dalam batasan (g (P)> = 0), itu adalah solusinya. Tampaknya KKT tidak relevan dalam kasus ini.

Tampaknya KKT mengatakan jika P tidak di dalam kendala, maka solusi X harus memuaskan di bawah ini dalam gambar. Apakah ini semua tentang KKT atau apakah saya kehilangan aspek penting lainnya?

Klarifikasi lainnya

Haruskah f (x) cembung untuk diterapkan KKT?
Haruskah g (x) linier untuk diterapkan pada KKT?
Haruskah λ diperlukan dalam λ * g (X) = 0? Mengapa g (X) = 0 atau g (Xi) = 0 tidak cukup?

Referensi

Perbarui 1

Terima kasih atas jawabannya tetapi masih berjuang untuk memahami. Fokus pada kebutuhan hanya di sini:

Apakah kondisi (2) dalam jawaban Matthew Gunn tentang titik tidak optimal (dalam lingkaran hijau) dan KKT tidak akan terpenuhi di sana? Dan intinya akan diidentifikasi dengan melihat Hessian seperti dalam jawaban Mark L. Stone?

Saya kira situasi lain adalah poin sadel, tetapi hal yang sama berlaku?

pengguna23658

svm optimization lagrange-multipliers mon
sumber

Pertanyaan ini dapat mengumpulkan lebih banyak perhatian di situs matematika; Kondisi KKT belum tentu "statistik". Ahli statistik meminjam ini dan hasil lainnya dari analisis numerik untuk menyelesaikan masalah statistik yang menarik, tetapi ini lebih merupakan pertanyaan matematika.

user23658

(1) Jika kendala tidak mengikat, masalah optimasi dengan kendala memiliki solusi yang sama dengan masalah optimasi tanpa kendala. (2) Baik

perlu cembung maupun

tidak perlu linier agar kondisi KKT diperlukan secara optimal. (3) Anda memang membutuhkan kondisi khusus (mis. Masalah cembung di mana kondisi Slater berlaku) agar kondisi KKT cukup untuk kondisi optimal.

f

$f$

g

$g$

Matthew Gunn

Gagasan dasar dari kondisi kelonggaran komplementer (yaitu

mana

adalah kendala) adalah bahwa jika kendala kendur (yaitu

) pada

optimal , maka penalti

untuk mengencangkan kendala adalah 0. Dan jika ada penalti positif

untuk mengencangkan kendala, maka kendala harus mengikat (yaitu

λ g (x) = 0

$\lambda g(\mathbf{x}) = 0$

g (x) \leq 0

$g(\mathbf{x}) \leq 0$

g (x) < 0

$g(\mathbf{x}) < 0$

x

$\mathbf{x}$

λ

$\lambda$

λ

$\lambda$

g (x) = 0

$g(\mathbf{x}) = 0$ ). Jika lalu lintas berjalan lancar, jembatan tol

untuk mobil lain adalah nol. Dan jika jembatan tol

, maka jembatan harus pada batas kapasitas.

λ

$\lambda$

λ > 0

$\lambda > 0$

Matthew Gunn

Teorema KKT dasar mengatakan bahwa jika kondisi KKT tidak terpenuhi pada titik

, maka titik

tidak optimal. Kondisi KKT diperlukan untuk optimal tetapi tidak mencukupi. (Misalnya, jika fungsi memiliki titik sadel, minimum lokal dll ... kondisi KKT mungkin terpenuhi tetapi titik tersebut tidak optimal!) Untuk kelas masalah tertentu (mis. Masalah cembung di mana kondisi Slater berlaku), KKT kondisi menjadi kondisi yang cukup .

x

$\mathbf{x}$

x

$\mathbf{x}$

Matthew Gunn

Jawaban:

Gagasan dasar dari kondisi KKT sebagai kondisi yang diperlukan untuk optimum adalah bahwa jika mereka tidak bertahan pada titik yang layak , maka ada arah yang akan meningkatkan tujuan tanpa meningkatkan (dan karenanya mungkin melanggar) kendala. (Jika kondisi KKT tidak berlaku di maka $\mathbf{x}$ $\boldsymbol{\delta}$ $f$ $\mathbf{x}$ $\mathbf{x}$ tidak bisa menjadi optimal, maka kondisi KKT diperlukan untuk suatu titik menjadi optimal.)

Bayangkan Anda memiliki masalah pengoptimalan:

\begin{array}{llr} minimize (over x) & f (x) \\ subject to & \forall_{j \in {1 \dots k}} g_{j} (x) \leq 0 \end{array}

$\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{x}$)} & f(\mathbf{x}) \\ \mbox{subject to} & \forall_{j \in \{1\ldots k\}}\; g_j(\mathbf{x}) \leq 0 \end{array} \end{equation}$

Di mana dan ada kendala . $\mathbf{x} \in \mathbb{R}^n$ $k$

Kondisi KKT dan Farkas Lemma

Misalkan menjadi vektor kolom yang menunjukkan gradien dievaluasi pada . $\nabla f(\mathbf{x})$ $f$ $\mathbf{x}$

Diterapkan pada situasi ini, Farkas Lemma menyatakan bahwa untuk setiap titik tepat satu $\mathbf{x} \in \mathbb{R}^n$ pernyataan berikut berlaku:

Ada ada sehingga dan $\boldsymbol{\lambda} \in \mathbb{R}^k$ $\sum_{j=1}^k \lambda_j \nabla g_j(\mathbf{x}) = -\nabla f(\mathbf{x})$ $\boldsymbol{\lambda} \geq \mathbf{0}$
Ada sedemikian rupa sehingga dan $\boldsymbol{\delta} \in \mathbb{R}^n$ $\forall_j \boldsymbol{\delta}' g_j(\mathbf{x}) \leq 0$ $\boldsymbol{\delta}'\nabla f(\mathbf{x}) < 0$

Apa artinya ini? Ini berarti bahwa untuk setiap titik layak , baik: $\mathbf{x}$

Kondisi (1) tahan dan kondisi KKT terpenuhi.
Kondisi (2) bertahan dan ada arah yang layak yang meningkatkan fungsi tujuan tanpa meningkatkan kendala . (mis. Anda dapat meningkatkan dengan berpindah dari ke $\boldsymbol{\delta}$ $f$ $g_j$ $f$ $\mathbf{x}$ $\mathbf{x} + \epsilon \boldsymbol{\delta}$ )

Kondisi (1) menyatakan bahwa ada pengganda non-negatif sehingga kondisi KKT terpenuhi pada titik . (Secara geometris, dikatakan bahwa $\boldsymbol{\lambda}$ $\mathbf{x}$ $- \nabla f$ terletak pada kerucut cembung didefinisikan oleh gradien dari kendala.)

Kondisi (2) menyatakan bahwa pada titik , ada arah $\mathbf{x}$ $\boldsymbol{\delta}$ untuk bergerak (lokal) sehingga:

Bergerak ke arah mengurangi fungsi objektif (karena produk titik dan $\boldsymbol{\delta}$ $\nabla f(\mathbf{x})$ $\boldsymbol{\delta}$ kurang dari nol).
Bergerak ke arah tidak meningkatkan nilai kendala (karena produk titik dan kurang dari atau sama dengan nol untuk semua kendala ). $\boldsymbol{\delta}$ $\nabla g_j(\mathbf{x})$ $\boldsymbol{\delta}$ $j$

(Secara geometris, arah yang layak mendefinisikan hyperplane pemisah antara vektor dan kerucut cembung yang ditentukan oleh vektor $\boldsymbol{\delta}$ $-\nabla f(\mathbf{x})$ $\nabla g_j(\mathbf{x})$ .)

(Catatan: untuk memetakan ini ke Farkas Lemma , tentukan matriks ) $A = \begin{bmatrix} \nabla g_1, \nabla g_2, \ldots, \nabla g_k \end{bmatrix}$

Argumen ini memberi Anda perlunya (tetapi tidak mencukupi) kondisi KKT secara optimal. Jika kondisi KKT tidak terpenuhi (dan kualifikasi kendala terpenuhi), dimungkinkan untuk meningkatkan tujuan tanpa melanggar kendala.

Peran kualifikasi kendala

Apa yang salah? Anda bisa mendapatkan situasi yang merosot di mana gradien dari kendala tidak secara akurat menggambarkan arah yang memungkinkan untuk bergerak.

Ada banyak kualifikasi kendala yang berbeda untuk dipilih yang akan memungkinkan argumen di atas bekerja.

Penafsiran min, maks. (Yang paling intuitif)

Bentuk Lagrangian

L (x, λ) = f (x) + \sum_{j = 1}^{k} λ_{j} g_{j} (x)

$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{j=1}^k \lambda_jg_j(\mathbf{x})$

Alih-alih meminimalkan tunduk pada batasan , bayangkan bahwa Anda sedang berusaha untuk meminimalkan sementara beberapa lawan sedang mencoba untuk memaksimalkan itu. Anda dapat mengartikan pengganda $f$ $g_j$ $\mathcal{L}$ $\lambda_i$ sebagai penalti (dipilih oleh beberapa lawan) karena melanggar kendala.

Solusi untuk masalah pengoptimalan asli setara dengan:

min_{x} max_{λ} L (x, λ)

$\min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

Itu adalah:

Anda pertama-tama memilih untuk meminimalkan Lagrangian , menyadari bahwa ... $\mathbf{x}$ $\mathcal{L}$
Saya kemudian akan memilih untuk memaksimalkan Lagrangian (setelah mengamati pilihan Anda ). $\boldsymbol{\lambda}$ $\mathbf{x}$

Misalnya, jika Anda melanggar batasan , saya dapat menghukum Anda dengan mengatur $g_2$ $\lambda_2$ hingga tak terbatas!

Dualitas yang lemah

Untuk fungsi apa pun perhatikan bahwa: $f(x, y)$

\forall_{\hat{x}, \hat{y}} min_{x} f (x, \hat{y}) \leq f (\hat{x}, \hat{y}) \leq max_{y} f (\hat{x}, y)

$\forall_{\hat{x},\hat{y}} \quad \min_x f(x, \hat{y}) \leq f(\hat{x}, \hat{y}) \leq \max_y f(\hat{x}, y)$

Sejak itu berlaku untuk setiap dan juga menyatakan bahwa: $\hat{x}$ $\hat{y}$

max_{y} min_{x} f (x, y) \leq min_{x} max_{y} f (x, y)

$\max_y \min_x f(x, y) \leq \min_x \max_y f(x, y)$

Dalam pengaturan Langrian, ini menghasilkan bahwa $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) \leq \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$ dikenal sebagai dualitas yang lemah.

Masalah ganda $\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$ memberi Anda batas yang lebih rendah pada solusi

Dualitas yang kuat

Di bawah kondisi khusus tertentu (mis. Masalah cembung di mana kondisi Slater berlaku), Anda memiliki dualitas yang kuat (yaitu properti saddle point).

max_{λ} min_{x} L (x, λ) = min_{x} max_{λ} L (x, λ)

$\max_\lambda \min_x \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = \min_x \max_\lambda \mathcal{L}(\mathbf{x}, \boldsymbol{\lambda})$

Hasil yang indah ini menyiratkan bahwa Anda dapat membalik urutan masalah.

$\boldsymbol{\lambda}$
$\mathbf{x}$ $\mathcal{L}$

$\lambda$

Matthew Gunn
sumber

Hargai informasi dan tautan untuk mengisi kesenjangan pemahaman. Izinkan saya untuk mengonfirmasi. Kondisi (1) berarti bahwa KKT mengatakan bahwa titik X menjadi solusi, ia harus memenuhi λ * g (X) = 0, λ> = 0, dan panjang gradien g (X) adalah λ kali dari bahwa dari f (X), kalau tidak kita akan menemukan gradien dari arah titik f (X) di mana lebih kecil f (X ') dapat ditemukan?

Senin

Kondisi slater (hanya) kualifikasi kendala yang dapat diterapkan untuk masalah optimasi cembung, yaitu membuat KKT diperlukan. Cembung membuat KKT mencukupi. Jadi, kondisi Slater untuk masalah optimisasi cembung di mana fungsi objektif dan batasannya cembung dan terus-menerus dibedakan membuat KKT diperlukan dan cukup untuk minimum global. Kondisi slater adalah bahwa setidaknya ada satu titik layak (yaitu, memenuhi semua kendala) yang ada di interior ketat semua kendala nonlinier (apa pun yang berjalan dengan kendala linier, selama layak).

Mark L. Stone

f (x) menjadi cembung diperlukan agar KKT mencukupi untuk x minimum lokal. Jika f (x) atau -g (x) tidak cembung, x pemenuhan KKT dapat berupa minimum lokal, saddlepoint, atau maksimum lokal.

g (x) menjadi linier, bersama dengan f (x) dapat dibedakan secara kontinu sudah cukup untuk kondisi KKT diperlukan untuk minimum lokal. g (x) menjadi linier berarti bahwa kualifikasi kendala Linearitas untuk KKT yang diperlukan untuk minimum lokal terpenuhi. Namun, ada kualifikasi kendala lain yang kurang membatasi yang cukup untuk kondisi KKT diperlukan untuk minimum lokal. Lihat bagian Kondisi keteraturan (atau kualifikasi kendala) di https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions .

Jika minimum lokal tidak memiliki kendala "aktif" (jadi dalam kasus hanya kendala ketimpangan, kendala itu tidak puas dengan kesetaraan), pengganda Lagrange terkait dengan kendala tersebut harus nol, dalam hal ini, KKT mengurangi ke kondisi yang gradien objektif = 0. Dalam kasus seperti itu, ada nol "biaya" untuk nilai objektif optimal dari pengetatan epsilon dari kendala.

Info lebih lanjut :

Fungsi dan kendala obyektif adalah cembung dan dapat dibedakan secara terus-menerus menyiratkan KKT cukup untuk minimum global.

Jika fungsi dan kendala obyektif secara terus-menerus dibedakan dan kendala memenuhi kualifikasi kendala, KKT diperlukan untuk minimum lokal.

Jika fungsi dan kendala obyektif dibedakan secara terus-menerus, cembung, dan kendala memenuhi kualifikasi kendala, KKT diperlukan dan cukup untuk minimum global.

$Z$ $Z^T H Z$ $H$ $Z$

Mark L. Stone
sumber