আনকনস্ট্রেইনড অপ্টিমাইজেশন — গোল্ডেন সেকশন সার্চ

১ · আনকনস্ট্রেইনড অপ্টিমাইজেশন সমস্যা

আনকনস্ট্রেইনড অপ্টিমাইজেশনUnconstrained optimizationএমন একটি সমস্যা যেখানে একটি ফাংশন f(x)-এর মিনিমাম বা ম্যাক্সিমাম খুঁজে বের করতে হয়, ইনপুট x-এর উপর কোনো অতিরিক্ত সীমাবদ্ধতা (constraint) ছাড়াই। হলো — একটি ফাংশন f(x) দেওয়া থাকলে, এমন x খুঁজে বের করা যেখানে f(x) সর্বনিম্ন (বা সর্বোচ্চ) হয়, এবং x-এর উপর কোনো অতিরিক্ত শর্ত নেই (যেমন "x ≥ 0" বা "x + y = 10" — এগুলো L45-এর কনস্ট্রেইনড কেস)। ক্যালকুলাসে আমরা শিখি f'(x) = 0 সমাধান করে ক্রিটিক্যাল পয়েন্ট বের করতে হয় — কিন্তু M2-এর মতোই, বেশিরভাগ বাস্তব ফাংশনের জন্য f'(x) = 0-এর কোনো ক্লোজড-ফর্ম সমাধান নেই। তাই আমরা M2-এর মতোই ইটারেটিভ নিউমেরিক্যাল মেথড ব্যবহার করি — পার্থক্য শুধু এই যে এখানে আমরা f(x) = 0 খুঁজছি না, বরং f(x)-এর সবচেয়ে ছোট মান কোথায় তা খুঁজছি।

২ · গোল্ডেন সেকশন সার্চ কীভাবে কাজ করে

একটি ইন্টারভাল [a, b] দিয়ে শুরু করি যেখানে আমরা জানি মিনিমাম আছে। এই ইন্টারভালের ভেতরে দুটি টেস্ট-পয়েন্ট c ও d বসানো হয় গোল্ডেন রেশিওর ভিত্তিতে:

$$ c = b - \varphi (b - a), \qquad d = a + \varphi (b - a), \qquad \varphi = \frac{\sqrt{5}-1}{2} \approx 0.618 $$

এরপর f(c) ও f(d) তুলনা করা হয়: যদি f(c) < f(d) হয়, তাহলে মিনিমামটি অবশ্যই [a, d]-এর মধ্যে আছে (তাই b-কে d-তে সরিয়ে আনা হয়); নয়তো মিনিমামটি [c, b]-এর মধ্যে আছে (তাই a-কে c-তে সরিয়ে আনা হয়)। গোল্ডেন রেশিওর বিশেষ গণিতীয় বৈশিষ্ট্যের কারণে, নতুন ইন্টারভালের একটি টেস্ট-পয়েন্ট আগের ধাপের একটি টেস্ট-পয়েন্টের সাথে মিলে যায় — তাই প্রতি ধাপে মাত্র একটি নতুন ফাংশন-মূল্যায়ন প্রয়োজন হয়।

import math

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

def golden_section_search(f, a, b, tol=1e-5, max_iter=100):
    gr = (math.sqrt(5) - 1) / 2   # golden ratio ~ 0.618
    c = b - gr * (b - a)
    d = a + gr * (b - a)
    fc, fd = f(c), f(d)

    for i in range(1, max_iter + 1):
        mid = (a + b) / 2
        width = b - a
        print(f"ইটারেশন {i:2d}: a={a:.6f}  b={b:.6f}  মধ্যবিন্দু={mid:.6f}  প্রস্থ={width:.8f}")
        if width < tol:
            break
        if fc < fd:
            b, d, fd = d, c, fc
            c = b - gr * (b - a)
            fc = f(c)
        else:
            a, c, fc = c, d, fd
            d = a + gr * (b - a)
            fd = f(d)
    return (a + b) / 2, i

final_x, n_iter = golden_section_search(f, 0.0, 5.0)
print()
print(f"চূড়ান্ত আনুমানিক মিনিমাম x = {final_x:.6f}  (প্রকৃত মিনিমাম x = 3)")
print(f"f(final_x) = {f(final_x):.8f}  (প্রকৃত মিনিমাম মান = 1)")
print(f"মোট ইটারেশন = {n_iter},  এরর = {abs(final_x - 3):.8f}")