Dalil Kecukupan Kuhn-Tucker: Pemrograman Cekung
Situsekonomi.com - Pada masalah optimisasi klasik, syarat cukup untuk maksimum dan minimum secara tradisional diekspresikan dalam tanda dari derivatif atau diferensial orde kedua. Akan tetapi, syarat orde kedua ini berhubungan erat dengan konsep kecekungan dan kecembungan dari fungsi tujuan (Chiang, 2005: 399).
Di sini, dalam pemrograman nonlinear, syarat cukup juga dapat dinyatakan secara langsung dalam kecekungan dan kecembungan. Sesungguhnya, konsep ini bahkan akan diterapkan tidak hanya pada fungsi tujuan f (x) tapi fungsi kendala gi(x) juga.
Untuk masalah maksimisasi, Kuhn dan Tucker menawarkan pernyataan syarat cukup berikut (dalil kecukupan):
Misalkan terdapat masalah pemrograman nonlinear
(a) fungsi tujuan f (x) dapat dibedakan dan cekung dalam orthant nonnegatif
(b) setiap fungsi kendala gi(x) dapat dibedakan dan cembung dalam orthant nonnegatif
(c) titik x* memenuhi kondisi maksimum Kuhn-Tucker
maka x* memberikan maksimum global π = f (x)
Perhatikan bahwa dalam dalil ini, kualifikasi kendala tidak disinggung. Ini disebabkan karena kita telah mengasumsikan, dalam kondisi (c), bahwa kondisi Kuhn-Tucker dipenuhi pada x* dan, sebagai akibatnya, pertanyaan mengenai kualifikasi kendala tidak lagi dipersoalkan (Chiang, 2005: 400).
Seperti yang telah dinyatakan, kedua dalil mengindikasikan bahwa kondisi (a), (b), dan (c) cukup untuk membentuk x* menjadi suatu pemecahan yang optimal. Melihat dari sisi lain, kita juga mungkin menginterpretasikannya untuk mengartikan bahwa (a) dan (b) yang diberikan, maka kondisi maksimum Kuhn-Tucker sudah cukup maksimum.
Kita mengetahui bahwa kondisi Kuhn-Tucker, walau tidak selalu diperlukan secara sendirian, diperlukan ketika kualifikasi kendala dipenuhi. Mengkombinasikan informasi ini dengan dalil kecukupan, kita mungkin dapat menyatakan bahwa jika kualifikasi kendala dipenuhi dan jika kondisi (a) dan (b) direalisasi, kondisi maksimum Kuhn-Tucker akan mencukupi dan diperlukan untuk suatu maksimum. Hal ini akan terjadi jika misalnya semua kendala merupakan pertidaksamaan linear, yang cukup untuk memenuhi kualifikasi kendala.
Masalah maksimisasi yang dihadapi oleh dalil kecukupan di atas sering kali disebut sebagai pemrograman cekung (concave programming). Nama ini muncul karena Kuhn dan Tucker mengadopsi pertidaksamaan ≥ dan bukan pertidaksamaan ≤ di setiap kendala, sehingga kondisi (b) akan mensyaratkan fungsi gi(x) untuk menjadi cekung, seperti fungsi f (x).
Akan tetapi, kita memodifikasi formula untuk menyebarkan ide bahwa dalam suatu masalah maksimisasi, suatu kendala dipaksa untuk "bergabung" (oleh karena itu, ≤ ) sebagai usaha untuk meningkat ke titik yang lebih tinggi dalam fungsi tujuan. Walau berbeda dalam bentuk, kedua formulasi sebenarnya ekuivalen dalam inti. Untuk mempersingkat, kami tidak mencantumkan pembuktian di sini.
Seperti dinyatakan di atas, dalil kecukupan hanya menghadapi masalah maksimisasi. Namun, adaptasi terhadap masalah minimisasi adalah sulit. Di samping perubahan yang sesuai dalam dalil untuk merefleksikan pembalikan dari masalah itu sendiri, yang harus kita lakukan adalah menukarkan dua kata cekung dan cembung dalam kondisi (a) dan (b) dan menggunakan kondisi minimum Kuhn-Tucker dalam kondisi (c).
