ENID
Lensa ML

Cara Kerja Constrained Optimization

Langkah 1 dari 6: Tanpa Constraint vs Dengan Constraint

Apa yang terjadi kalau minimum sebenarnya tidak bisa dicapai

Radius constraint r1.50
-3-2-11234-3-2-11234xymin (2,2)(1.1,1.1)f(x,y) = (x−2)² + (y−2)²
Min tanpa constraint
0.0
Min dengan constraint
1.76
Selisih
1.76

Dengan radius kecil, lingkaran jauh dari minimum tanpa constraint, jadi titik feasible terbaik jauh lebih buruk.

Geser Radius constraint r dari 0,5 ke 3 dan perhatikan kartu Selisih. Fungsi objektifnya f = (x − 2)² + (y − 2)², dengan minimum bebas 0 di (2, 2), dan titiknya harus tetap berada pada lingkaran x² + y² = r². Titik terbaik pada lingkaran terletak pada garis menuju (2, 2), jadi minimum dengan constraint adalah (r − 2√2)². Pada r = 1.5, nilainya sekitar 1,76. Selisih itu adalah harga dari constraint, dan nilainya tidak pernah negatif.

Langkah 2 dari 6: Kurva Constraint

Menjelajahi feasible region untuk mencari solusi yang lebih baik

Radius constraint r1.50
Posisi t di sepanjang constraint0.79
-3-2-11234-3-2-11234xyf=1.76Geser t untuk menjelajahi lingkaran constraint
x
1.06
y
1.07
f(x,y)
1.76
f optimal
1.76

Titik ini tepat di atau sangat dekat dengan optimum dengan constraint, yaitu nilai f terbaik di seluruh lingkaran.

Atur radiusnya, lalu geser Posisi t di sepanjang constraint mengelilingi seluruh lingkaran dari 0 sampai 2π. Menulis titiknya sebagai (r·cos t, r·sin t) mengubah masalah dua variabel dengan constraint menjadi masalah satu variabel tanpa constraint. Inilah metode substitusi. Metode ini berhasil kalau constraint-nya mudah diparameterkan, seperti lingkaran. Untuk sebagian besar constraint sungguhan, rumus seperti itu tidak ada, jadi syarat gradient di langkah berikutnya lebih berguna.

Langkah 3 dari 6: Kesejajaran Gradient

Di titik optimum, gradient objektif dan gradient constraint sejajar

Posisi t di sepanjang constraint0.79
-3-2-11234-3-2-11234xy∇f∇g∇f = gradient objektif, ∇g = gradient constraint
|∇f|
2.66
|∇g|
3.00
Sudut
179.4°
f(x,y)
1.76

Kedua gradient hampir sejajar, dan itulah syarat optimalitas. Di minimum dengan constraint, ∇f dan ∇g menunjuk ke arah yang sama atau berlawanan.

Geser Posisi t di sepanjang constraint dan perhatikan kartu Sudut. Di sini r tetap 1.5. Bergerak di sepanjang lingkaran berarti bergerak ke arah garis singgung, dan f berubah dengan laju sebesar komponen ∇f pada garis singgung itu. Ketika ∇f tidak punya komponen pada garis singgung, ia tegak lurus terhadap lingkaran, jadi ia pasti searah dengan ∇g = (2x, 2y). Di optimum ini kedua panah menunjuk ke arah berlawanan, karena minimum bebas (2, 2) berada di luar lingkaran.

Langkah 4 dari 6: Lagrange Multiplier λ

Skalar yang membuat ∇f = λ∇g

Posisi t di sepanjang constraint0.79
Lagrange multiplier λ1.00
-3-2-11234-3-2-11234xy∇fλ∇gSyarat optimalitas: ∇f = λ∇g
λ
1.0
|∇f − λ∇g|
5.66
λ optimal
-0.89

Ketidakcocokannya besar: λ ini tidak memenuhi ∇f = λ∇g. Geser λ menuju nilai di kartu hijau.

Atur t di dekat π/4 ≈ 0.79 dan sesuaikan Lagrange multiplier λ sampai kartu ketidakcocokan berubah hijau. Menyelesaikan 2(x − 2) = λ·2x pada titik optimal menghasilkan λ = 1 − 2√2/r, sekitar −0,89 untuk r = 1.5. Multiplier ini punya arti: ia adalah laju perubahan nilai objektif terbaik ketika level constraint r² berubah. Melonggarkan constraint sebesar 0,1 di sini menurunkan f optimal sekitar 0,09.

Langkah 5 dari 6: Mencari Titik Optimum

Konvergen secara iteratif ke solusi dengan constraint

Langkah iterasi0
-3-2-11234-3-2-11234xytargetProjected gradient descent pada constraint (η = 0.08)
Langkah
0
x
-1.50
y
0.00
f(x,y)
16.25

Titik awal ada di sisi seberang lingkaran. Setiap iterasi menggeser titik di sepanjang lingkaran menuju optimum.

Geser slider Langkah iterasi dari 0 sampai 20 dan ikuti jejaknya dari t = π sampai optimum di t = π/4. Projected gradient descent adalah salah satu cara menyelesaikan masalah seperti ini: ambil langkah gradient biasa, lalu proyeksikan titiknya kembali ke feasible set. Pada lingkaran, proyeksi hanya menskalakan ulang titik ke panjang r. Di sini setiap langkah memakai learning rate 0,08, jadi titik menempuh sebagian besar busur dalam 7 iterasi pertama, lalu merayap di beberapa derajat terakhir. Metode lain mencakup penalty method, yang menambahkan biaya makin besar untuk setiap pelanggaran, dan interior-point method untuk masalah konveks dengan banyak constraint.

Langkah 6 dari 6: Regularization sebagai Constraint

Membatasi weight untuk mencegah overfitting

Anggaran constraint c = ||w||² ≤ c2.00
-3-2-11234-3-2-11234xy||w||² ≤ 2.0min tanpa reg.w*Kontur loss (biru) + constraint pada weight (fuchsia)
||w||²
2.00
Loss
3.06
Anggaran c
2.0
Loss reg.
5.06

Anggaran sedang menarik weight ke titik asal, tetapi weight masih bisa mengikuti data dengan cukup baik.

Naikkan Anggaran constraint c dari 0,5 ke 5. Pusat loss ada di (3, 1), yang berada di luar semua lingkaran dalam rentang ini, jadi constraint selalu aktif dan solusinya adalah titik pada lingkaran yang paling dekat ke (3, 1). Meminimalkan loss dengan syarat |w|² ≤ c memberi solusi yang sama dengan meminimalkan loss + λ|w|² untuk suatu λ ≥ 0. Anggaran yang lebih kecil sepadan dengan λ yang lebih besar. Syarat KKT menambahkan bahwa λ = 0 setiap kali constraint tidak aktif.

Apa itu constrained optimization?

Constrained optimization mencari minimum atau maksimum sebuah fungsi ketika input-nya harus memenuhi syarat tambahan, misalnya tetap berada pada sebuah kurva atau di dalam suatu anggaran. Alat klasiknya adalah metode Lagrange multiplier (pengali Lagrange): di optimum dengan constraint, gradient fungsi objektif merupakan kelipatan dari gradient constraint, ∇f = λ∇g. Untuk constraint berbentuk pertidaksamaan, metode ini diperluas menjadi syarat Karush–Kuhn–Tucker (KKT).

Dalam machine learning, constraint muncul di support vector machine (memaksimalkan margin dengan syarat setiap titik terklasifikasi benar), batas weight norm dan regularization L2, constraint keadilan dan keamanan, serta trust region berbasis KL divergence yang dipakai TRPO dan RLHF. Banyak suku penalty dalam loss function sebenarnya adalah constraint yang ditulis dalam bentuk Lagrangian.

Ide utama

  • Constraint membatasi posisi solusi, dan hanya bisa membuat nilai objektif terbaik menjadi lebih buruk atau tetap sama.
  • Di optimum dengan constraint, ∇f sejajar dengan gradient constraint ∇g.
  • Syarat Lagrange ∇f = λ∇g mengubah masalah dengan constraint menjadi sistem persamaan.
  • Multiplier λ adalah sensitivitas nilai optimal terhadap level constraint.
  • Constraint pertidaksamaan mengikuti syarat KKT, dengan λ bernilai nol kecuali constraint-nya aktif.
  • Regularization L2 adalah bentuk penalty dari constraint pada norm weight.

Pertanyaan umum

Apa itu Lagrangian?

Lagrangian menggabungkan fungsi objektif dan constraint menjadi satu fungsi: L(x, λ) = f(x) − λ·(g(x) − c). Menyamakan gradient-nya dengan nol terhadap x dan λ menghasilkan kembali ∇f = λ∇g dan constraint itu sendiri. Konvensi tanda berbeda antarbuku, jadi λ bisa muncul dengan tanda plus.

Apa itu syarat KKT?

Syarat KKT adalah syarat optimalitas untuk masalah dengan constraint pertidaksamaan. Isinya: Lagrangian harus stasioner, titiknya feasible, multiplier setiap pertidaksamaan non-negatif, dan complementary slackness, yaitu setiap multiplier dikali slack constraint-nya sama dengan nol. Untuk masalah konveks yang memenuhi syarat regularitas ringan, syarat KKT bersifat perlu sekaligus cukup.

Bagaimana support vector machine memakai constrained optimization?

Hard-margin SVM meminimalkan |w|²/2 dengan syarat setiap titik training berada di sisi margin yang benar. Lagrange dual-nya bergantung pada data hanya lewat dot product antartitik, dan inilah yang memungkinkan kernel trick. Titik dengan multiplier bukan nol adalah support vector.

Bagaimana constraint ditangani saat training neural network?

Biasanya lewat penalty yang ditambahkan ke loss, seperti weight decay, atau lewat proyeksi setelah setiap langkah, seperti clipping weight atau menormalkannya ulang ke norm maksimum. Metode seperti TRPO menerapkan trust-region constraint langsung pada perubahan policy. Solver constraint yang eksak jarang dipakai pada skala deep learning.

Penjelasan terkait

Referensi

  1. Boyd & Vandenberghe, "Convex Optimization", ch. 5 Duality (free PDF)
  2. Deisenroth, Faisal & Ong, "Mathematics for Machine Learning", ch. 7 Continuous Optimization
  3. Cortes & Vapnik (1995), "Support-vector networks", Machine Learning
  4. Schulman et al. (2015), "Trust Region Policy Optimization"

Terakhir diperbarui