Pemrograman Nonlinier

Pemrograman Nonlinear (NLP) — adalah cabang dari pemrograman matematis dan riset operasi yang menangani masalah optimasi, di mana fungsi tujuan dan/atau setidaknya satu dari kendala merupakan fungsi nonlinear dari variabel keputusan.

NLP merupakan generalisasi dari pemrograman linear dan memungkinkan pemodelan kelas sistem dan proses nyata yang lebih luas, di mana hubungan antar variabel tidak bersifat proporsional secara ketat (yaitu digambarkan oleh kurva, bukan garis lurus).

Subjek dan Tujuan

Pemrograman Nonlinear digunakan untuk menemukan solusi optimal dalam situasi ketika:

• Ketergantungan indikator tujuan (keuntungan, biaya, efisiensi, dll.) terhadap parameter yang dikendalikan bersifat nonlinear (misalnya, hasil yang semakin menurun terhadap skala, biaya kuadratik).
• Kendala pada sumber daya atau proses teknologi dijelaskan oleh hubungan nonlinear (misalnya, reaksi kimia, hukum fisika, ketergantungan ekonomi).

Masalah NLP muncul di banyak bidang:

• Perancangan teknik (optimasi struktur, proses).
• Ekonomi dan keuangan (optimasi portofolio dengan mempertimbangkan risiko, pemodelan pasar).
• Teknologi kimia (optimasi mode operasi reaktor).
• Machine Learning (pelatihan Neural Network, metode support vector).
• Pengelolaan proses produksi. Logistik (dengan mempertimbangkan biaya nonlinear).

Formulasi Matematis Masalah NLP

Masalah umum pemrograman nonlinear dirumuskan sebagai berikut:

Diperlukan untuk menemukan sekumpulan nilai variabel keputusan yang memaksimalkan atau meminimalkan fungsi tujuan nonlinear. Nilai-nilai variabel tersebut harus memenuhi sistem kendala, yang dapat dinyatakan baik dalam bentuk pertidaksamaan (misalnya, "nilai A harus kurang dari atau sama dengan B") maupun dalam bentuk persamaan (misalnya, "nilai C harus tepat sama dengan D"). Yang penting, setidaknya satu dari fungsi yang menggambarkan tujuan atau kendala bersifat nonlinear. Seringkali ditambahkan kondisi ketidaknegatifan variabel, yaitu persyaratan agar nilainya lebih besar dari atau sama dengan nol.

Himpunan semua sekumpulan nilai variabel yang memenuhi kendala membentuk daerah solusi yang layak (DSL).

Perbedaan dari Pemrograman Linear

Pemrograman Nonlinear berbeda secara signifikan dari pemrograman linear (PL):

• Nonlinearitas: Fungsi tujuan atau kendala (atau keduanya) mengandung ketergantungan nonlinear.
• Sifat DSL: Daerah solusi yang layak dalam NLP dapat bersifat tidak konveks (berbeda dengan PL, di mana DSL selalu merupakan polihedron konveks).
• Sifat optimum: Solusi optimal dalam NLP tidak harus berada di titik sudut DSL; solusi tersebut dapat terletak di batas atau di dalam daerah. Dalam NLP dapat terdapat optimum lokal yang bukan merupakan optimum global.
• Kompleksitas penyelesaian: Masalah NLP umumnya jauh lebih sulit diselesaikan daripada masalah PL. Tidak ada satu algoritma universal yang setara dengan metode simpleks untuk semua masalah NLP.

Kesulitan dan Tantangan Utama NLP

Penyelesaian masalah pemrograman nonlinear disertai sejumlah kesulitan:

• Keberadaan ekstrem lokal: Sebagian besar metode NLP hanya menjamin ditemukannya optimum lokal (solusi terbaik dalam suatu lingkungan tertentu). Pencarian optimum global (solusi terbaik di seluruh DSL) merupakan masalah yang sulit, terutama untuk masalah tidak konveks.
• Ketidakkonveksan: Jika masalah tidak bersifat konveks (fungsi tujuan atau DSL tidak konveks), maka dapat terdapat banyak optimum lokal, dan metode gradien standar dapat "terjebak" pada salah satunya.
• Kompleksitas komputasi: Algoritma penyelesaian NLP seringkali membutuhkan sumber daya komputasi yang jauh lebih besar dibandingkan dengan PL.

Kelas Penting Masalah NLP

Meski secara umum kompleks, terdapat subkelas penting dari masalah NLP yang telah dikembangkan metode penyelesaian efektifnya:

• Pemrograman konveks: Masalah meminimalkan fungsi konveks pada himpunan solusi yang layak yang konveks (atau memaksimalkan fungsi konkaf). Sifat utama: setiap minimum lokal juga merupakan minimum global. Hal ini secara signifikan menyederhanakan pencarian solusi optimal.
• Pemrograman kuadratik: Fungsi tujuan bersifat kuadratik, dan semua kendala bersifat linear.
• Pemrograman terpisahkan: Fungsi tujuan dan kendala dapat direpresentasikan sebagai jumlah fungsi-fungsi yang masing-masing hanya bergantung pada satu variabel.

Metode Penyelesaian Masalah NLP

Metode penyelesaian masalah pemrograman nonlinear (NLP)

I. Metode optimasi tanpa kendala (optimasi bebas):

• Metode gradien (metode penurunan tercepat, metode gradien konjugat);
• Metode Newton dan metode kuasi-Newton (misalnya, BFGS);
• Metode dengan penggunaan aproksimasi Hessian.

II. Metode optimasi bersyarat (optimasi dengan kendala):

• Metode transformasi:
  • Metode fungsi penalti (penalty methods);
  • Metode fungsi penghalang (barrier methods).
• Metode pencarian arah langsung:
  • Metode arah yang layak.
• Metode berdasarkan kondisi optimalitas:
  • Metode Karush-Kuhn-Tucker (kondisi KKT);
  • Metode pengali Lagrange.
• Metode iteratif:
  • Sequential Quadratic Programming (SQP);
  • Metode titik interior.

III. Metode optimasi global:

• Metode heuristik dan metaheuristik:
  • Algoritma genetika;
  • Simulated annealing;
  • Tabu search.
• Metode deterministik:
  • Branch and bound;
  • Algoritma optimasi global untuk masalah dengan struktur khusus.

Literatur

• Bazara M., Shetty C. Pemrograman Nonlinear. Teori dan Algoritma. — Moskow: Mir, 1982.
• Fiacco A., McCormick G. Pemrograman Nonlinear. Metode Minimisasi Tanpa Kendala Berurutan. — Moskow: Mir, 1972.
• Himmelblau D. Pemrograman Nonlinear Terapan. — Moskow: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)

Lihat Juga

• Riset operasi
• Optimasi
• Pemrograman linear
• Pemrograman konveks
• Fungsi tujuan
• Kendala
• Daerah solusi yang layak