Kuhn Tucker Kondisi dengan kendala non-negatif lebih sedikit daripada jumlah variabel

5

Saya memiliki jenis masalah berikut:

$ Maksimalkan \, \, F (s, x, y, z) $
$ s, x, y, z $

s.t. (i) $ g (x, y, z) \ le I $
(ii) $ x \ ge 0 $
(iii) $ y \ ge 0 $
(iv) $ s & gt; 0 $

Artinya tidak ada batasan non-negatif pada variabel $ z $. Saya telah membaca tentang metode Kuhn-Tucker di buku-buku tetapi dalam semua kasus masalahnya empat kali dirumuskan sehingga kendala non-negatif berlaku untuk semua variabel pilihan. Bagaimana kondisi optimalitas K-T saya akan berubah jika saya tidak memiliki batasan non-negatif pada $ z $?

Perasaan saya adalah bahwa selain ketentuan KT biasa untuk $ x $ dan $ y $ dan pengganda Lagrange, $ \ lambda $, kita akan memiliki (a) $ \ frac {\ partial \ Large {L}} {\ partial z} = 0 $ (yaitu tidak ada ketimpangan di sini) dan TIDAK ada kondisi seperti (b) $ z \,. \ Frac {\ partial \ Large {L}} {\ partial z} = 0 $ (yang jelas benar diberikan (a) ). Seluruh kebingungan saya adalah karena saya belum melihat formulasi seperti itu di buku-buku di mana kondisi K-T dibahas dan hanya ingin memastikan tentang langkah-langkah saya.

Bagaimana kondisinya jika $ s $, di mana ketimpangannya sangat ketat?

Di sini saya akan berpikir bahwa dengan ketimpangan yang ketat masalah tidak didefinisikan dengan baik. Set kendala tidak kompak (tidak tertutup).

Terima kasih banyak sebelumnya.

user200947
sumber

Jawaban:

4

Batasan non-negatif tidak ada yang spesial dan tidak penting untuk validitas umum pendekatan Karush-Kuhn-Tucker. Pertama, sadari bahwa kita dapat memiliki $ x \ geq a & gt; 0 $ dan kemudian kita dapat menulis $ x-a \ geq 0 $ dan melihat batasan "non-negatif" ini sebagai satu lagi kendala ketidaksetaraan pada solusi.

Ketika variabel keputusan terikat dengan lemah, fenomena baru yang muncul adalah kita mungkin memiliki turunan parsial non-nol (sangat negatif, untuk kasus maksimalisasi), jika pada solusi variabel keputusan ini terletak pada batas.

Jika tidak dibatasi, maka kita harus memiliki turunan orde pertama sama dengan nol. Seperti pertanyaan lain tunjukkan, ini dapat menciptakan masalah dalam konteks tertentu, tetapi itu tidak membatalkan pendekatan.

Adapun pertanyaan kedua Anda, memang ketidaksetaraan yang ketat dapat menciptakan masalah, tetapi jangan langsung beralih ke pernyataan berat "tidak didefinisikan dengan baik". Masalahnya akan muncul hanya jika (bintang menunjukkan solusi optimal)

$$ \ frac {\ partial F (s ^ *, x ^ *, y ^ *, z ^ *)} {\ partial s ^ *} & lt; 0 $$

yang akan "mendorong" vektor solusi ke arah batas nol-bawah yang tidak terjangkau untuk $ s $. Untuk menghindarinya, kita mengharuskan turunan orde pertama w.r.t ke $ s $ sama dengan nol, dan melihat apakah kita memang bisa mendapatkan vektor solusi. Jika kami bisa, itu berarti batasan $ s & gt; 0 $ bahkan tidak "cenderung" mengikat, jadi Anda dapat mengabaikannya.

Alecos Papadopoulos
sumber
3

Perasaan saya adalah:

(1) Keberadaan ekstrem mungkin tidak dijamin. Jika salah satu variabel pilihan bisa negatif, katakanlah dalam teori konsumen salah satu barang, saya menduga anggaran yang ditetapkan tidak lagi padat. Misalnya dalam kasus $ L = 2 $, misalkan Anda membiarkan kuantitas untuk barang 2 menjadi negatif. Apa artinya ini? Mungkin itu sampah atau polusi, jadi pada ekstremnya, Anda tidak akan menginginkannya dengan cara apa pun. Jadi set anggaran yang mungkin akan terlihat seperti fungsi quasiconcave (misalnya kurva lonceng dengan puncak) pada sumbu vertikal di mana tidak ada jaminan penutupan atau batasan.
(2) Kualifikasi kendala akan dilanggar sehingga penyelesaian metode KT tidak ada artinya . Ketika memeriksa kualifikasi kendala, kami menggunakan fakta bahwa vektor harga sangat positif untuk menyelidiki matriks memiliki peringkat penuh bukan pada titik kepentingan. Katakan, kali ini Anda mengizinkannya menjadi negatif atau nol, kualifikasi kendala akan dilanggar, dan mungkin memecahkan KT biasa akan memberi Anda sesuatu, tetapi itu mungkin bukan sesuatu yang Anda inginkan.

Hanya 2 sen saya.

Frank Swanton
sumber
1

Secara umum, bahkan memiliki batasan nonnegativitas pada semua variabel Anda tidak akan menjamin bahwa ruang kendala Anda kompak. Untuk membuat pernyataan apa pun tentang ruang kendala Anda, Anda perlu mempertimbangkan batasan akun (i). Biasanya, $ g $ akan sedemikian rupa sehingga $ \ lim _ {\ | x, y, z \ | \ to \ infty} g (x, y, z) = \ infty $, dan Anda dapat memiliki jaminan bahwa ruang kendala Anda kompak selama semua variabel dibatasi menjadi tidak negatif. Tanpa kendala pada $ z $, Anda harus melihat bentuk $ g $ untuk dapat menjamin ruang kendala Anda kompak. Misalnya, jika $ g (x, y, z) = z ^ 2 + h (x, y) $, tidak adanya kendala $ z \ ge 0 $ tidak menimbulkan masalah untuk menyelesaikan masalah (ruang kendala masih kompak.)

Namun, batasan ketimpangan yang ketat pada $ s $ (iv) memungkinkan ruang kendala Anda tidak kompak, karena tidak tertutup. Dari pengalaman saya (relatif terbatas) dengan pemrograman kendala, Anda hanya akan menyelesaikan masalah Anda seperti biasa, mengabaikan kendala (iv), dan membuang solusi apa pun yang $ s \ le 0 $. (Pengguna lain dapat memperbaiki saya jika ini tidak benar.) Bergantung pada bentuk spesifik masalah Anda, Anda dapat memperoleh solusi yang memuaskan $ s & gt; 0 $, atau Anda mungkin menemukan satu-satunya maksimum memiliki $ s \ le 0 $, dalam hal ini maksimum tidak ada untuk masalah Anda.

Untuk meringkas, ya, hanya menyelesaikan kondisi K-T untuk kendala ketimpangan (i-iii). Masalah Anda tidak dijamin memiliki solusi (karena kurangnya batasan ketimpangan pada $ z $, dan ketimpangan yang ketat pada $ s $), tetapi jika ada solusi, K-T akan memberikannya kepada Anda.

Blue_vision
sumber