অপ্টিমাইজেশনের জন্য নিউটনের মেথড

১ · আপডেট রুল — দ্বিতীয় ডেরিভেটিভ কেন প্রয়োজন

M2/L07-এ আমরা দেখেছিলাম নিউটন-রাফসন f(x) = 0-এর রুট খুঁজতে f'(x) ব্যবহার করে। অপ্টিমাইজেশনে আমরা f-এর মিনিমাম খুঁজি, এবং ক্যালকুলাস থেকে জানি মিনিমামে f'(x) = 0 হয় — তাই আমরা আসলে f'(x) = 0-এর রুট খুঁজছি! নিউটন-রাফসনকে সরাসরি f'-এর উপর প্রয়োগ করলে (যার ডেরিভেটিভ f'') পাওয়া যায়:

$$ x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)} $$

f''(x) (দ্বিতীয় ডেরিভেটিভ) ফাংশনের বক্রতা পরিমাপ করে — এটি জানা থাকলে মেথডটি প্রতি ধাপে ফাংশনটিকে স্থানীয়ভাবে একটি কোয়াড্রেটিক (প্যারাবোলা) দিয়ে আনুমানিক করে, এবং সরাসরি সেই প্যারাবোলার মিনিমামে লাফ দেয় — গ্র্যাডিয়েন্ট ডিসেন্টের ছোট ছোট ধাপের বদলে একটি বুদ্ধিদীপ্ত, বড় লাফ। বহু-চলক ক্ষেত্রে f''(x)-এর জায়গায় হেসিয়ান ম্যাট্রিক্স (দ্বিতীয়-ক্রম আংশিক ডেরিভেটিভের ম্যাট্রিক্স) এবং তার ইনভার্স ব্যবহার করা হয়: x_{n+1} = x_n - H^{-1} \nabla f(x_n)।

২ · ডেমো ১ — L43-এর একই কোয়াড্রেটিক ফাংশনে

L43-এর টেস্ট ফাংশন f(x, y) = (x-3)² + (y+2)² + 5-এর হেসিয়ান ম্যাট্রিক্স ধ্রুবক: H = [[2, 0], [0, 2]] (কারণ উভয় পদই খাঁটি কোয়াড্রেটিক)। এর ইনভার্স H⁻¹ = [[0.5, 0], [0, 0.5]] — যেহেতু বক্রতা ধ্রুবক, নিউটনের মেথডের কোয়াড্রেটিক-অ্যাপ্রক্সিমেশন এখানে নিখুঁতভাবে সঠিক, তাই তাত্ত্বিকভাবে মাত্র এক ধাপেই সঠিক মিনিমামে পৌঁছানোর কথা।

import math

def f(x, y):
    return (x - 3)**2 + (y + 2)**2 + 5

def grad_f(x, y):
    return (2*(x - 3), 2*(y + 2))

def hessian_inv_apply(gx, gy):
    # H = [[2,0],[0,2]]  ->  H_inverse = [[0.5,0],[0,0.5]]
    return (0.5 * gx, 0.5 * gy)

x, y = 0.0, 0.0
print(f"iter 0: x={x:.6f}  y={y:.6f}  f={f(x, y):.6f}")

gx, gy = grad_f(x, y)
dx, dy = hessian_inv_apply(gx, gy)
x, y = x - dx, y - dy
print(f"iter 1: x={x:.6f}  y={y:.6f}  f={f(x, y):.6f}")

gx2, gy2 = grad_f(x, y)
gnorm = math.sqrt(gx2**2 + gy2**2)
print(f"গ্র্যাডিয়েন্ট নর্ম iter 1-এ = {gnorm:.10f}  (কনভার্জ করেছে!)")

৩ · ডেমো ২ — একটি হার্ডার, নন-কোয়াড্রেটিক ফাংশনে

বাস্তব ফাংশন সাধারণত খাঁটি কোয়াড্রেটিক নয়, তাই নিউটনের মেথড সাধারণত এক ধাপে নয়, বরং কয়েক ধাপে কনভার্জ করে — কিন্তু তখনও এটি "কোয়াড্রেটিক কনভারজেন্স" দেখায় (প্রতি ধাপে এরর মোটামুটি স্কয়ার হয়ে যায়)। টেস্ট ফাংশন: g(x) = (x-3)⁴ + (x-3)² + 1, যার মিনিমাম x = 3-এ (g'(x) = 4(x-3)³ + 2(x-3), g''(x) = 12(x-3)² + 2)। শুরুর বিন্দু x₀ = 0।

def g(x):
    return (x - 3)**4 + (x - 3)**2 + 1

def gprime(x):
    return 4*(x - 3)**3 + 2*(x - 3)

def gdouble(x):
    return 12*(x - 3)**2 + 2

def newton_1d(x0, tol=1e-10, max_iter=100):
    x = x0
    for i in range(max_iter):
        err = abs(x - 3)
        print(f"iter {i}: x={x:.8f}  g(x)={g(x):.6f}  |x-3|={err:.10f}")
        gp = gprime(x)
        if abs(gp) < tol:
            return i, x
        x_new = x - gp / gdouble(x)
        if abs(x_new - x) < 1e-12:
            return i + 1, x_new
        x = x_new
    return max_iter, x

def gd_1d(x0, lr, tol=1e-6, max_iter=1000):
    x = x0
    for i in range(max_iter):
        gp = gprime(x)
        if abs(gp) < tol:
            return i, x
        x = x - lr * gp
    return max_iter, x

n_newton, x_newton = newton_1d(0.0)
print(f"\nNewton কনভার্জ করল {n_newton} ইটারেশনে, x = {x_newton:.10f}")

n_gd, x_gd = gd_1d(0.0, lr=0.05)
print(f"Gradient Descent (lr=0.05) কনভার্জ করল {n_gd} ইটারেশনে, x = {x_gd:.10f}")