পর্ব ১৮ · অপ্টিমাইজেশন গণিত
অপ্টিমাইজেশন তত্ত্ব
KKT, duality ও constrained optimization
শেখার লক্ষ্য
- Lagrange multiplier
- KKT শর্ত
- Duality-র ধারণা
Constrained Optimization
Minimize f(x) subject to g(x) = 0 (equality) ও h(x) ≤ 0 (inequality)।
শুধু ∇f = 0 যথেষ্ট নয় — constraints মানতে হবে।
Lagrange Multiplier
Equality constraint-এর জন্য Lagrangian:
Stationary point: ∇ₓL = 0, ∂L/∂λ = 0।
KKT Conditions
Inequality সহ general সমস্যার জন্য Karush–Kuhn–Tucker শর্ত:
- Stationarity: ∇f + Σλᵢ∇gᵢ + Σμⱼ∇hⱼ = 0।
- Primal feasibility: gᵢ = 0, hⱼ ≤ 0।
- Dual feasibility: μⱼ ≥ 0।
- Complementary slackness: μⱼ hⱼ = 0।
Duality
Dual function: d(λ, μ) = inf_x L(x, λ, μ)। Dual problem: maximize d।
Weak duality: d* ≤ p* সর্বদা সত্য।
Strong duality: convex + Slater condition হলে d* = p* — duality gap শূন্য।
এআই-সংযোগ
SVM-এর dual formulation kernel trick সম্ভব করে।
Constrained policy optimization (Lagrangian PPO, CMDP) safe RL-এ ব্যবহৃত।
Adversarial training একটি min-max (saddle-point) সমস্যা — duality তত্ত্বের সরাসরি প্রয়োগ।
GAN: min_G max_D V(D, G) — দুই খেলোয়াড়ের অপ্টিমাইজেশন।
সারসংক্ষেপ
- Lagrangian = objective + λ·constraint।
- KKT = constrained optimum-এর প্রথম-ক্রম শর্ত।
- Duality: primal ↔ dual; convex-এ gap শূন্য।