🐼 ♌️ 🤞🏼 Sedikit tentang dualitas kerucut 🤱🏽 🙇🏿 👸🏾

Ketika mempelajari kursus teori dalam pembelajaran mesin (matematika. Ekonomi, optimisasi, keuangan, dll.), Konsep "masalah ganda" sering ditemukan.

Tugas ganda sering digunakan untuk mendapatkan perkiraan yang lebih rendah (atau atas) untuk target fungsional dalam masalah optimasi. Selain itu, untuk hampir semua pernyataan yang bermakna dari masalah optimisasi, masalah ganda memiliki interpretasi yang bermakna. Artinya, jika Anda dihadapkan dengan masalah optimisasi yang penting, maka masalah gandanya juga kemungkinan besar penting.

Dalam artikel ini saya akan berbicara tentang dualitas kerucut. Cara membangun dua tugas ini, menurut pendapat saya, tidak semestinya kehilangan perhatian ...

Matan selanjutnya ...

Bagaimana biasanya tugas ganda dibangun?

Biarkan beberapa masalah optimasi diberikan:

$\ min_ {x \ dalam R ^ n} f (x) \\ f_i (x) \ leq 0, \ quad 1 \ leq i \ leq k \\ h_i (x) = 0, 1 \ leq i \ leq m$

Tugas ganda dibangun menurut skema berikut:

Bangun Lagrangian

$L (x, \ lambda, \ mu) = f (x) + \ sum_ {i = 1} ^ k \ lambda_i f_i (x) + \ sum_ {i = 1} ^ m \ mu_i h_i (x)$

Membangun fungsi ganda

$g (\ lambda, \ mu) = \ inf_x L (x, \ lambda, \ mu)$

Dapatkan tugas ganda

$\ max _ {\ lambda, \ mu} g (\ lambda, \ mu) \\ \ lambda \ geq 0$

Kesulitan utama dalam skema ini adalah kabel pada langkah pencarian

$\ inf_x L (x, \ lambda, \ mu)$ .

Jika masalahnya bukan cembung, maka ini adalah peti mati - dalam kasus umum, itu tidak dapat diselesaikan dalam waktu polinomial (jika

$P \ neq NP$ ) dan masalah seperti itu dalam artikel ini yang tidak akan kami bahas di masa mendatang.

Asumsikan masalahnya adalah cembung, lalu apa?

Jika masalahnya lancar, maka kita dapat menggunakan kondisi optimal tingkat pertama

$\ nabla_x L (x, \ lambda, \ mu) = 0$ . Dari kondisi ini, jika semuanya OK, ternyata untuk menyimpulkan atau

$x (\ lambda, \ mu) = \ arg \ min_x L (x, \ lambda, \ mu)$ dan

$g (\ lambda, \ mu) = L (x (\ lambda, \ mu), \ lambda, \ mu)$ atau langsung berfungsi

$g (\ lambda, \ mu)$ .

Jika masalahnya tidak mulus, maka kita bisa menggunakan analog dari kondisi orde pertama

$0 \ in \ partial_x L (x, \ lambda, \ mu)$ (di sini

$\ partial_x L (x, \ lambda, \ mu)$ menunjukkan subdifferential dari suatu fungsi

$L (x, \ lambda, \ mu)$ ), bagaimanapun, prosedur ini biasanya jauh lebih rumit.

Kadang-kadang ada masalah optimasi “halus” yang setara dan seseorang dapat membuat masalah ganda untuk itu. Tetapi untuk perbaikan struktur (dari non-halus ke halus), sebagai aturan, Anda selalu harus membayar peningkatan dimensi.

Dualitas kerucut

Ada beberapa tugas optimasi (contoh di bawah) yang menerima representasi berikut:

$\ min_ {x \ dalam R ^ n} c ^ Tx \\ Ax + b \ dalam K$

dimana

$A$ - matriks

$b$ - vektor

$K$ - kerucut cembung non-merosot.

Dalam hal ini, tugas ganda dapat dibangun sesuai dengan skema berikut:

Tugas ganda dibangun menurut skema berikut:

Bangun Lagrangian

$L (x, \ lambda) = c ^ Tx + \ lambda ^ T (Ax + b)$

Membangun fungsi ganda

$g (\ lambda) = \ inf_x L (x, \ lambda) = \ begin {cases} \ lambda ^ T b, \ quad c + A ^ T \ lambda = 0 \\ - \ infty, \ quad c + A ^ T \ lambda \ neq 0 \ end {cases}$

Dapatkan tugas ganda

$\ maks _ {\ lambda} b ^ T \ lambda \\ c + A ^ T \ lambda = 0 \\ - \ lambda \ dalam K ^ *$

dimana cone konjugat

$K ^ *$ untuk kerucut

$K$ didefinisikan sebagai

K ^ * = \ kiri \ {y \ dalam R ^ k | z ^ T y \ geq 0, \ quad \ forall z \ dalam K \ right \}

$K ^ * = \ kiri \ {y \ dalam R ^ k | z ^ T y \ geq 0, \ quad \ forall z \ dalam K \ right \}$ .

Seperti yang kita lihat, seluruh kerumitan membangun masalah ganda dipindahkan ke konstruksi kerucut ganda. Tetapi kegembiraannya adalah ada kalkulus yang bagus untuk membangun kerucut ganda dan sangat sering kerucut ganda dapat segera dihapus.

Contoh

Misalkan kita perlu membuat masalah optimisasi ganda untuk masalah tersebut:

$\ min_ {x \ dalam R ^ n} \ | x \ | _2 + \ | x \ | _1 \\ Ax \ geq b$

Di sini

$\ | x \ | _1 = \ sum_ {i = 1} ^ n | x_i |$ ,

$\ | x \ | _2 = \ sqrt {\ sum_ {i = 1} ^ n x_i ^ 2}$

Hal pertama yang dapat Anda perhatikan: fungsi objektif selalu dapat dibuat linier!

Sebaliknya, selalu ada masalah setara dengan fungsi objektif linier:

$\ min_ {x \ dalam R ^ n, y \ di R, z \ dalam R} y + z \\ \ | x \ | _2 \ leq y \\ \ | x \ | _1 \ leq z \\ Ax \ geq b$

Sekarang Anda perlu menggunakan sedikit pengetahuan rahasia: banyak

K_1 = \ {(x, t) \ dalam R ^ n \ kali R | \ quad \ | x \ | _1 \ leq t \}

$K_1 = \ {(x, t) \ dalam R ^ n \ kali R | \ quad \ | x \ | _1 \ leq t \}$

dan

$K_2 = \ {(x, t) \ dalam R ^ n \ kali R | \ quad \ | x \ | _2 \ leq t \}$

adalah kerucut cembung.

Jadi, kita sampai pada notasi yang setara dengan masalah:

$\ min_ {x \ dalam R ^ n, y \ di R, z \ dalam R} y + z \\ I_ {n + 1} \ begin {pmatrix} x \\ y \ end {pmatrix} + 0_ {n +1} \ dalam K_2 \\ I_ {n + 1} \ begin {pmatrix} x \\ z \ end {pmatrix} + 0_ {n + 1} \ di K_1 \\ Ax-b \ dalam R _ + ^ k$

Sekarang kita dapat segera menulis masalah ganda:

$\ max _ {\ lambda, \ mu, \ nu} -b ^ T \ nu \\ \ lambda_i + \ mu_i + [A ^ T \ nu] _i = 0, \ quad 1 \ leq i \ leq n \\ \ lambda_ { n + 1} + 1 = 0 \\ \ mu_ {n + 1} +1 = 0 \\ - \ lambda \ dalam K_2 ^ * (= K_2) \\ - \ mu \ dalam K_1 ^ * (= K _ {\ infty}) \\ - \ nu \ dalam R ^ k _ +$

atau, untuk menyederhanakan sedikit,

$\ maks _ {\ lambda, \ mu, \ nu} -b ^ T \ nu \\ \ lambda + \ mu + A ^ T \ nu = 0 \\ \ | \ lambda \ | _2 \ leq 1 \\ \ | \ mu \ | _ {\ infty} \ leq 1 \\ - \ nu \ dalam R ^ k _ +$

dimana

$\ | \ mu \ | _ {\ infty} = \ max_ {i} | \ mu_i |$ .

Tautan untuk studi lebih lanjut:

Sedikit tentang dualitas kerucut

Bagaimana biasanya tugas ganda dibangun?

Dualitas kerucut

Contoh

More articles: