Teori Komplementaritas

Problem komplementaritas merupakan suatu problem di bidang optimisasi matematis. Termasuk dalam problem ini adalah masalah minimisasi dan maksimalisasi suatu fungsi yang terdiri atas dua variabel vektor, dengan syarat bahwa internal produk dari kedua variabel tersebut adalah nol, atau dalam bahasa matematisnya, <X, Y> = 0.

Misalnya, jika dalam suatu ruang vektor riil berdimensi terbatas terdapat dua vektor X dan Y yang memiliki komponen-komponen non-negatif (x_i ≥ 0 dan y_i ≥ 0 untuk semua $i$: komponen-kompenen tersebut terletak di kuadran pertama untuk ruangan 2-dimensi, atau di oktan pertama untuk ruangan 3-dimensi), maka, untuk setiap pasangan komponen x_i dan y_i, salah satu komponennya harus bernilai nol. Itulah sebabnya problem ini disebut komplementaritas. Contoh matematisnya X = (1, 0) dan Y = (0, 2) adalah komplementer, tapi X = (1, 1) dan Y = (2, 0) bukan komplementer. Problem komplementaritas adalah suatu kasus khusus dari problem inequalitas variasional.

Asal Usul

Problem komplementaritas pada awalnya dipelajari karena Kondisi-kondisi Karush-Kuhn-Tucker (di bidang pemrograman linier dan pemrograman kuadratik) memunculkan Problem Komplementaritas Linier (LCP) dan Problem Komplementaritas Campuran (MCP). Pada tahun 1963 Lemke dan Howson membuktikan bahwa penghitungan Keseimbangan Nash untuk game 2 pelaku adalah identik dengan problem LCP. Pada tahun 1968 Cottle dan Dantzig menyatukan masalah pemrograman linier, kuadratik dan bimatriks game. Sejak saat itulah penelitian di bidang komplementaritas dan inequalitas variasional berkembang dengan pesat.

Referensi Lanjut

• Richard W. Cottle, Jong-Shi Pang, Richard E. Stone (1992). The Linear Complementarity Problem. Academic Press. ISBN 978-0121923501. Pemeliharaan CS1: Banyak nama: authors list (link)
• George Isac (1992). Complementarity Problems. Springer. ISBN 978-3540562511. 
• George Isac (2000). Topological Methods in Complementarity Theory. Springer. ISBN 978-0792362746. 
• Francisco Facchinei, Jong-Shi Pang (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems: v.1 and v.2. Springer. ISBN 978-0387955803. 
• Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. 3. Berlin: Heldermann Verlag. hlm. xlviii+629 pp. ISBN 3-88538-403-5.  (Available for download at the website of Professor Katta G. Murty.) MR949214

Bibliografi

• Richard Cottle, F. Giannessi, Jacques Louis Lions, ed. (1980). Variational Inequalities and Complementarity Problems: Theory and Applications. John Wiley & Sons. ISBN 978-0471276104. Pemeliharaan CS1: Banyak nama: editors list (link)
• Michael C. Ferris, Jong-Shi Pang, ed. (1997). Complementarity and Variational Problems: State of the Art. SIAM. ISBN 978-0898713916. 

Pranala Luar

• CPNET:Complementarity Problem Net