Optimisasi di Python: Teknik, Paket, dan Praktik Terbaik

Teknik Optimisasi di Python

Python menawarkan berbagai teknik kuat untuk menyelesaikan masalah optimisasi, mulai dari metode berbasis gradien sederhana hingga algoritme yang lebih kompleks. Teknik-teknik ini memungkinkan Anda menemukan minimum atau maksimum fungsi secara efisien, baik dalam machine learning, rekayasa, maupun riset operasi. 

Di bagian ini, kita akan membahas teknik optimisasi yang umum diimplementasikan di Python, termasuk gradient descent, metode Newton, metode gradien konjugat, metode quasi-Newton, metode Simplex, dan metode trust-region. 

Catatan: Lihat DataLab ini untuk melihat semua kode yang digunakan untuk menghasilkan visualisasi di bagian ini. 

Mari kita mulai!

Gradient descent

Gradient descent adalah salah satu teknik paling fundamental dalam optimisasi numerik. Ini adalah metode iteratif yang digunakan untuk menemukan minimum suatu fungsi dengan mengikuti negatif gradien (atau kemiringan) fungsi tersebut. 

Gagasan utamanya adalah memulai dengan tebakan awal dan memperbaruinya secara iteratif dengan bergerak menuju penurunan paling curam hingga konvergen tercapai. Ini adalah salah satu teknik optimisasi yang paling umum digunakan saat melatih model machine learning, di mana tujuannya adalah meminimalkan fungsi loss. 

Metode Newton

Metode Newton adalah teknik optimisasi yang menemukan minimum dengan menggunakan gradien dan turunan orde dua (matriks Hessian) dari fungsi objektif. Berbeda dengan gradient descent yang hanya mengandalkan turunan orde pertama, metode Newton memanfaatkan informasi kelengkungan, sehingga memungkinkan konvergensi lebih cepat, terutama untuk fungsi cembung.

Meskipun metode Newton berkongvergensi dengan cepat, metode ini memerlukan perhitungan matriks Hessian, yang dapat mahal secara komputasi dan tidak praktis untuk masalah skala besar. Namun, metode ini sangat efektif untuk masalah cembung yang kecil dan halus.

Metode gradien konjugat

Metode gradien konjugat adalah teknik optimisasi yang efisien untuk masalah skala besar, terutama ketika penyimpanan matriks Hessian tidak praktis. Metode ini secara iteratif membangun arah konjugat dan mengoptimasi sepanjang arah tersebut alih-alih membutuhkan Hessian penuh, sehingga cocok untuk masalah seperti meminimalkan fungsi kuadratik besar.

Metode ini bermanfaat dalam analisis elemen hingga atau aplikasi machine learning skala besar, di mana komputasi matriks menjadi memberatkan.

Metode quasi-Newton (BFGS)

Metode quasi-Newton, seperti algoritme Broyden–Fletcher–Goldfarb–Shanno (BFGS), mendekati matriks Hessian alih-alih menghitungnya secara langsung. Metode-metode ini mencapai konvergensi lebih cepat daripada gradient descent dengan memanfaatkan informasi orde dua tanpa beban komputasi menghitung Hessian penuh.

Metode Simplex

Metode Simplex adalah algoritme yang banyak digunakan untuk menyelesaikan masalah pemrograman linear (LP), di mana fungsi objektif dan kendalanya bersifat linear. Metode ini secara sistematis memeriksa titik-titik sudut wilayah feasible (sebuah polihedron) dan bergerak menuju titik optimal tempat fungsi objektif mencapai nilai maksimum atau minimum.

Metode trust-region

Metode trust-region adalah algoritme optimisasi yang membangun model lokal dari fungsi objektif dalam sebuah “trust region” di sekitar solusi saat ini. 

Alih-alih mengambil langkah dalam arah yang telah ditentukan (seperti pada gradient descent), algoritme mendefinisikan submasalah yang lebih sederhana dalam trust region. Submasalah ini diselesaikan secara iteratif untuk memperbaiki solusi. Metode ini sangat efektif untuk menangani masalah yang kompleks dan nonlinear serta menawarkan stabilitas yang lebih baik dibandingkan metode berbasis gradien tradisional.

Trust region dan radius saat meminimalkan fungsi Rosenbrock | Sumber: Trust Region Methods oleh Shivangi Khare

Paket Python Umum untuk Optimisasi

Ada berbagai pustaka dan paket yang dirancang untuk memfasilitasi optimisasi numerik. Masing-masing memiliki kekuatan dan penerapannya, namun apa pun masalah optimisasi yang Anda hadapi, biasanya ada alat andal untuk menanganinya di Python. 

Berikut empat paket optimisasi yang paling umum:  

Optimisasi SciPy (scipy.optimize)

Modul scipy.optimize adalah pustaka serbaguna dalam ekosistem SciPy, yang menawarkan beragam algoritme untuk masalah optimisasi tanpa kendala maupun dengan kendala. Ini mencakup fungsi untuk mencari minimum fungsi skalar dan multi-variabel, menyelesaikan masalah pencarian akar, dan fitting kurva ke data.

Fungsi-fungsi dalam modul ini meliputi: 

• minimize(): Fungsi untuk meminimalkan fungsi skalar dari satu atau lebih variabel.

from scipy.optimize import minimize

def objective_function(x):
    return x[0]**2 + x[1]**2
result = minimize(objective_function, [1, 1], method='BFGS')
print(result.x)  # Optimal solution

# >>> [-1.07505143e-08 -1.07505143e-08]Didukung oleh

• root(): Menemukan akar dari fungsi vektor – sangat berguna untuk menyelesaikan sistem persamaan nonlinear.

from scipy.optimize import root

def equations(vars):
    x, y = vars
    return [x + 2*y - 3, x - y - 1]
result = root(equations, [0, 0])
print(result.x)

# >>> [1.66666667 0.66666667]Didukung oleh

• curve_fit(): Fungsi ini melakukan fitting kurva ke sekumpulan titik data dan berguna untuk fitting data serta estimasi parameter.

from scipy.optimize import curve_fit
import numpy as np

def model(x, a, b):
    return a * np.exp(b * x)
x_data = np.array([1, 2, 3])
y_data = np.array([2.7, 7.4, 20.1])
params, covariance = curve_fit(model, x_data, y_data)
print(params)  # Fitted parameters

# >>> [0.9981286  1.00089935]Didukung oleh

CVXPY

CVXPY adalah pustaka Python yang dirancang untuk masalah optimisasi cembung. Pustaka ini memungkinkan pengguna mendefinisikan dan menyelesaikan masalah tersebut menggunakan sintaks deklaratif tingkat tinggi. CVXPY menyederhanakan perumusan masalah optimisasi kompleks dengan memungkinkan pengguna menentukan fungsi objektif dan kendala secara alami dan mudah dibaca.

CVXPY menawarkan fitur-fitur berikut:

• Sintaks deklaratif: CVXPY menyediakan cara intuitif untuk memodelkan masalah optimisasi menggunakan ekspresi matematis Python.
• Solver mutakhir: Terintegrasi dengan solver tingkat lanjut seperti ECOS, SCS, dan OSQP, yang secara efisien menangani masalah cembung.

import cvxpy as cp

# Define variables
x = cp.Variable()
y = cp.Variable()

# Define constraints
constraints = [x + y == 1, x - y >= 2]

# Define the objective function
objective = cp.Minimize(x**2 + y**2)

# Formulate the problem
prob = cp.Problem(objective, constraints)

# Solve the problem
result = prob.solve()
print(f"Optimal value: {result}")
print(f"x: {x.value}, y: {y.value}")

# >>> Optimal value: 2.5
# x: 1.5, y: -0.5000000000000001Didukung oleh

Pyomo

Pyomo adalah paket pemodelan optimisasi yang fleksibel dan komprehensif yang mendukung pemrograman linear, nonlinear, dan bilangan bulat campuran. Paket ini dirancang untuk masalah optimisasi yang kompleks dan terintegrasi mulus dengan solver seperti GLPK, CBC, dan CPLEX.

Fitur-fitur Pyomo meliputi:

• Fleksibilitas pemodelan: Pyomo memungkinkan pendefinisian masalah optimisasi dengan tingkat fleksibilitas tinggi, termasuk kendala dan tujuan yang kompleks.
• Integrasi solver: Mendukung berbagai solver, memberikan fleksibilitas dalam memilih alat terbaik untuk masalah tertentu.

Gurobi dan CPLEX (melalui Pyomo atau API langsung)

Gurobi dan CPLEX adalah solver berkinerja tinggi untuk masalah optimisasi skala besar. Keduanya umum digunakan di industri untuk tugas seperti optimisasi rantai pasok, manajemen portofolio, dan logistik. 

Mereka menawarkan algoritme canggih yang dirancang untuk menangani masalah kompleks dan skala besar secara efisien.

• Gurobi: Dapat diakses melalui Pyomo atau API langsungnya, Gurobi dikenal akan kecepatan dan keandalannya dalam menyelesaikan pemrograman linear, bilangan bulat, dan kuadratik.
• CPLEX: Demikian pula, CPLEX menyediakan kemampuan optimisasi yang kuat dan digunakan di berbagai sektor untuk menyelesaikan masalah operasional dan strategis yang kompleks. Dapat diakses melalui Pyomo atau langsung melalui API-nya.

Solver ini sering digunakan untuk masalah berskala industri, di mana efisiensi komputasi dan ketangguhan sangat penting.

Aplikasi Dunia Nyata Optimisasi Numerik di Python

Seperti yang saya sebutkan di pendahuluan, optimisasi numerik berperan penting di berbagai domain. Ini menyediakan teknik esensial untuk menyelesaikan masalah kompleks dan membuat keputusan berbasis data.

Sebagai contoh:  

• Machine learning: Model pada dasarnya dilatih menggunakan optimisasi numerik. Ini melibatkan pencarian parameter optimal yang meminimalkan fungsi loss dan mengukur seberapa baik model memprediksi variabel target. 
• Riset operasi: Teknik optimisasi membantu membuat keputusan strategis yang memaksimalkan atau meminimalkan berbagai metrik operasional. Dengan mengoptimalkan fungsi objektif yang tunduk pada kendala, peneliti operasi dapat meningkatkan efisiensi dalam proses seperti manajemen rantai pasok, penjadwalan tenaga kerja, dan perencanaan produksi. 
• Keuangan: Optimisasi numerik sangat penting di sektor keuangan untuk tugas seperti optimisasi portofolio. Teknik ini membantu menentukan alokasi aset terbaik untuk memaksimalkan imbal hasil atau meminimalkan risiko.
• Desain rekayasa: Optimisasi numerik diterapkan untuk merancang sistem dan struktur yang memenuhi kriteria kinerja tertentu sekaligus meminimalkan biaya. Proses ini membantu mencapai desain yang efisien untuk segala hal mulai dari jembatan dan pesawat hingga proses manufaktur dan sistem energi.

Praktik Terbaik untuk Optimisasi Numerik di Python

Beberapa faktor harus dipertimbangkan untuk memastikan hasil terbaik dari upaya optimisasi Anda di Python. Pastikan untuk mengikuti praktik terbaik berikut: 

Memilih algoritme yang tepat

Memilih algoritme optimisasi yang tepat sangat penting untuk mencapai hasil optimal. Pemilihan algoritme bergantung pada sifat masalah:

• Linear vs. nonlinear: Untuk masalah linear, teknik pemrograman linear seperti metode Simplex atau titik interior adalah pilihan yang tepat. Untuk masalah nonlinear, metode seperti gradient descent, metode Newton, atau metode quasi-Newton (misalnya, BFGS) mungkin lebih sesuai.
• Dengan kendala vs. tanpa kendala: Untuk masalah dengan kendala, diperlukan algoritme seperti Sequential Quadratic Programming (SQP) atau metode yang menangani kendala secara native (misalnya, metode titik interior). Masalah tanpa kendala dapat diselesaikan secara efisien menggunakan gradient descent atau metode Newton.

Memilih algoritme yang tepat berdasarkan karakteristik masalah membantu mencapai konvergensi lebih cepat dan solusi yang lebih akurat.

Menangani kendala

Kendala dalam masalah optimisasi dapat sangat memengaruhi pilihan algoritme dan strategi solusi. Berbagai pendekatan dapat digunakan untuk menangani kendala:

• Metode penalti: Memasukkan kendala ke dalam fungsi objektif dengan menambahkan suku penalti untuk pelanggaran kendala. Pendekatan ini mengubah masalah berkendala menjadi masalah tanpa kendala, sehingga memungkinkan penggunaan metode optimisasi tanpa kendala.
• Metode barrier: Menggunakan fungsi barrier untuk memastikan kendala tidak dilanggar. Metode barrier bekerja dengan menyertakan suku barrier dalam fungsi objektif yang menjadi tak hingga saat kendala didekati.
• Dukungan native: Memanfaatkan solver yang secara inheren mendukung kendala. Banyak solver optimisasi modern, seperti yang tersedia di scipy.optimize atau CVXPY, dirancang untuk menangani kendala secara langsung dan efisien.

Memilih metode yang tepat untuk menangani kendala memastikan solusi feasible dan memenuhi semua persyaratan yang ditentukan.

Skalasi dan prapemrosesan

Skalasi dan prapemrosesan data yang tepat dapat secara signifikan meningkatkan kinerja algoritme optimisasi:

• Skalasi: Normalisasi atau standarkan data masukan untuk memastikan fitur berkontribusi secara setara ke fungsi objektif. Ini dapat mencegah masalah terkait stabilitas numerik dan meningkatkan laju konvergensi.
• Prapemrosesan: Terapkan teknik seperti rekayasa fitur atau reduksi dimensi untuk menyederhanakan masalah. Prapemrosesan yang tepat mengurangi kompleksitas masalah optimisasi dan mempercepat proses penyelesaian.

Menafsirkan hasil

Menafsirkan hasil algoritme optimisasi melibatkan pemahaman beberapa aspek:

• Kualitas solusi: Evaluasi kualitas solusi dengan memeriksa apakah solusi memenuhi kondisi optimal dan kendala. Bandingkan hasil dengan tolok ukur yang diketahui atau validasi menggunakan teknik cross-validation.
• Kriteria konvergensi: Nilai apakah algoritme optimisasi telah berkongvergensi dengan memeriksa pesan konvergensi, jumlah iterasi, atau perubahan nilai fungsi objektif. Pastikan algoritme telah mencapai solusi yang dekat dengan optimum sebenarnya.
• Presisi numerik: Pertimbangkan dampak presisi numerik pada hasil. Kesalahan numerik kecil dapat terakumulasi dan memengaruhi solusi akhir, terutama pada masalah skala besar atau dengan toleransi yang ketat.

Kesimpulan

Optimisasi numerik adalah pilar pemecahan masalah modern. Ini menawarkan alat yang kuat untuk mengatasi tantangan kompleks di bidang seperti machine learning, rekayasa, keuangan, dan riset operasi. 

Ekosistem pustaka optimisasi Python—seperti SciPy, CVXPY, dan Pyomo—membuat teknik-teknik lanjutan ini lebih mudah diakses, memberdayakan peneliti, insinyur, dan data scientist untuk merancang sistem yang efisien, mengoptimalkan model, dan membuat keputusan yang lebih cerdas berbasis data. 

Dengan teknik dan praktik terbaik yang tepat, Anda kini siap untuk mendekati dan menyelesaikan bahkan masalah optimisasi paling menantang di Python. Namun, lihat sumber daya berikut untuk melanjutkan pembelajaran Anda:

• Introduction to Optimization in Python
• Introduction to Linear Modeling in Python
• SciPy Cheat Sheet: Linear Algebra in Python
• Data Structures: A Comprehensive Guide With Python Examples