Pemrograman Nonlinear
- Diperkenalkan oleh
- Jorge Nocedal & Stephen Wright
- Tahun
- 2006
- Jenis
- Continuous mathematical optimization
- Keluarga
- Mathematical programming
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman nonlinear (NLP) adalah cabang optimasi matematis yang berkaitan dengan masalah di mana fungsi tujuan atau setidaknya satu kendala bersifat nonlinear.
Diformalkan secara komprehensif oleh Jorge Nocedal dan Stephen Wright dalam teks seminal mereka tahun 2006, NLP mencakup algoritma berbasis gradien — termasuk pemrograman kuadratik sekuensial (SQP), metode titik interior, dan pendekatan kuasi-Newton — untuk menemukan solusi optimal lokal atau global untuk masalah keputusan kontinu yang muncul di bidang teknik, ekonomi, dan ilmu fisika.
Intuisi di balik metode
Bayangkan menuruni lanskap berkabut yang berbukit sambil tetap berada di dalam wilayah berpagar. Anda tidak dapat melihat seluruh medan, jadi Anda merasakan kemiringan di bawah kaki Anda (gradien), menyesuaikan arah langkah Anda untuk menuruni bukit, dan memeriksa di setiap gerakan bahwa Anda tidak melintasi pagar (kendala). Jika pagar melengkung atau bukit tumpang tindih, jalur garis lurus sederhana tidak akan berhasil — Anda harus melengkungkan jalur Anda. Pemrograman nonlinear memformalkan proses ini persis, mengganti pendakian bukit intuitif dengan aturan ukuran langkah dan arah yang ketat secara matematis.
Sejarah
Dasar teoritis pemrograman nonlinear berakar pada kondisi KKT yang diturunkan oleh Karush (1939) dan Kuhn serta Tucker (1951). Algoritma praktis dipercepat selama tahun 1960-an–1980-an dengan pengembangan metode SQP, pendekatan Lagrangian yang diperluas, dan pembaruan kuasi-Newton termasuk BFGS (1970). Edisi kedua Numerical Optimization karya Nocedal dan Wright tahun 2006 menjadi referensi definitif, menyintesis teori konvergensi, kerangka kerja pencarian garis dan wilayah kepercayaan, serta metode titik interior ke dalam perlakuan modern yang koheren.
Kapan digunakan
Gunakan pemrograman nonlinear ketika tujuan atau kendala tidak dapat dilinearisasi tanpa kehilangan akurasi yang material dan variabel keputusan bersifat kontinu. Pengaturan tipikal meliputi desain teknik dengan kendala hukum fisika, optimasi portofolio dengan ukuran risiko nonlinear, dan regresi dengan bentuk model nonlinear. Asumsi utama adalah bahwa f dan c setidaknya dua kali terdiferensiasi secara kontinu (untuk solver berbasis gradien) dan bahwa kualifikasi kendala berlaku. Ketika variabel bernilai integer, ekstensi pemrograman nonlinear campuran integer (MINLP) berlaku. Untuk masalah konveks, metode titik interior menjamin optimasi global; untuk masalah non-konveks, hanya jaminan lokal yang ada.
Batasan dan pertimbangan
- Masalah non-konveks hanya menawarkan jaminan optimasi lokal; solusi global memerlukan strategi pencarian global tambahan.
- Memerlukan tujuan dan kendala untuk mulus (setidaknya terdiferensiasi); masalah non-mulus memerlukan metode subgradien khusus.
- Biaya komputasi tumbuh secara substansial dengan ukuran masalah ketika evaluasi Hessian yang tepat diperlukan.
- Kualifikasi kendala mungkin gagal (misalnya, pada titik layak yang degeneratif), menyebabkan kondisi KKT kehilangan dasar teoritisnya.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menangani kelas masalah dunia nyata yang luas di mana aproksimasi linear atau kuadratik tidak mencukupi.
- Teori algoritma yang matang dengan jaminan konvergensi yang dipelajari dengan baik untuk kasus konveks.
- Solver berbasis gradien yang efisien (SQP, titik interior) berskala hingga ribuan variabel dalam praktik.
- Kerangka kerja Lagrangian terpadu mengakomodasi kendala kesamaan dan ketidaksetaraan campuran secara alami.
Penerapan
- Teknik sipil dan kedirgantaraan: meminimalkan berat tunduk pada kendala tegangan dan defleksi.
- Manajemen portofolio: memaksimalkan imbal hasil yang diharapkan tunduk pada anggaran varians (risiko) nonlinear.
- Desain proses kimia: mengoptimalkan hasil reaktor tunduk pada kendala termodinamika dan keselamatan.
- Pembelajaran mesin: melatih jaringan saraf dan model kernel melalui solver NLP tanpa kendala atau dengan kendala.
- Sistem energi: masalah aliran daya optimal dalam pengiriman jaringan listrik dengan kendala fisika nonlinear.
Cara kerjanya
Cara kerjanya
Analis mendefinisikan fungsi skalar f(x) untuk diminimalkan atau dimaksimalkan atas variabel keputusan x di R^n, bersama dengan kendala kesamaan c_i(x) = 0 dan kendala ketidaksetaraan c_j(x) >= 0. Mengidentifikasi kendala mana yang aktif pada solusi kandidat dan apakah kondisi keteraturan (kualifikasi kendala) berlaku sangat penting pada tahap ini dan menentukan teori optimasi apa yang berlaku.
Rumus
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}Kondisi Karush-Kuhn-Tucker (KKT) memberikan kondisi perlu orde pertama untuk optimum lokal. Kondisi ini memerlukan stasioneritas Lagrangian, kelonggaran komplementer untuk pengali ketidaksetaraan (lambda_j c_j = 0), kelayakan dual (lambda_j >= 0), dan kelayakan primal. Algoritma secara iteratif membangun iterasi yang memenuhi kondisi ini semakin ketat, dengan kondisi kecukupan orde kedua mengonfirmasi bahwa titik stasioner memang merupakan minimum lokal.
Rumus
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}Pada setiap iterasi k, algoritma menghitung arah pencarian p_k — biasanya melalui aproksimasi kuasi-Newton B_k dari Hessian (misalnya, BFGS) atau sistem turunan kedua yang tepat — dan panjang langkah alpha_k yang memenuhi kondisi Wolfe atau Armijo. Metode SQP menyelesaikan submasalah kuadratik untuk p_k, sementara metode titik interior menambahkan suku penghalang untuk menangani kendala ketidaksetaraan dan mendorong iterasi menuju interior yang layak.
Rumus
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)Penghentian terjadi ketika norma gradien Lagrangian dan pelanggaran kendala maksimum jatuh di bawah toleransi yang ditentukan (epsilon dan delta). Karena NLP umumnya non-konveks, algoritma dapat konvergen ke optimum lokal; beberapa kali restart dari titik awal yang berbeda atau strategi pencarian global (branch-and-bound, multistart) direkomendasikan ketika optimasi global diperlukan.
Rumus
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \deltaKesalahan umum
- Mengabaikan kualifikasi kendala dan menerapkan kondisi KKT secara membabi buta pada titik degeneratif atau tidak layak mengarah pada solusi palsu.
- Menggunakan variabel yang diskalakan dengan buruk menyebabkan aproksimasi Hessian yang buruk kondisinya dan konvergensi yang lambat atau gagal.
- Menerima minimum lokal pertama yang ditemukan tanpa beberapa kali restart dalam pengaturan non-konveks dapat secara signifikan melewatkan optimum global.
- Aproksimasi gradien beda hingga memperkenalkan kesalahan numerik; diferensiasi analitik atau otomatis sangat disukai.
Pertanyaan yang sering diajukan
Apakah setiap program linear juga merupakan program nonlinear?
Ya. Pemrograman linear adalah kasus khusus NLP di mana baik tujuan maupun semua kendala adalah affine. Namun, LP mengakomodasi algoritma simpleks dan titik interior yang memanfaatkan linearitas dan jauh lebih efisien daripada solver NLP umum; menggunakan solver NLP umum untuk LP adalah pemborosan tetapi valid secara matematis.
Kapan saya dapat yakin bahwa titik KKT adalah minimum global?
Ketika NLP bersifat konveks — yang berarti f adalah konveks dan himpunan yang layak adalah himpunan konveks — setiap titik KKT adalah minimum global. Untuk masalah non-konveks, jaminan ini tidak berlaku, dan titik KKT hanyalah minimum lokal (di bawah kondisi kecukupan orde kedua). Metode optimasi global seperti branch-and-bound atau relaksasi konveks diperlukan sebaliknya.
Apa perbedaan antara metode SQP dan titik interior?
SQP secara iteratif menyelesaikan submasalah pemrograman kuadratik yang mendekati NLP secara lokal dan sering kali lebih disukai untuk masalah kecil hingga menengah dengan banyak kendala aktif. Metode titik interior (penghalang) tetap berada di dalam wilayah yang layak dan cenderung berskala lebih baik untuk masalah besar yang jarang. Keduanya konvergen superlinear di bawah kondisi keteraturan yang sesuai.
Metode terkait
Sumber
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
ISBN: 978-0-387-30303-1Disalin.