Frank–Wolfe algorithm
ফ্র্যাঙ্ক-ওল্ফ অ্যালগরিদম হল সীমাবদ্ধ উত্তল অপ্টিমাইজেশনের জন্য একটি পুনরাবৃত্তিমূলক প্রথম-ক্রম অপ্টিমাইজেশন অ্যালগরিদম। শর্তাধীন গ্রেডিয়েন্ট পদ্ধতি, হ্রাসকৃত গ্রেডিয়েন্ট অ্যালগরিদম এবং উত্তল সমন্বয় অ্যালগরিদম নামেও পরিচিত, পদ্ধতিটি মূলত 1956 সালে মার্গারেট ফ্রাঙ্ক এবং ফিলিপ ওল্ফ দ্বারা প্রস্তাবিত হয়েছিল। প্রতিটি পুনরাবৃত্তিতে, ফ্রাঙ্ক-ওল্ফ অ্যালগরিদম উদ্দেশ্যমূলক ফাংশনের একটি রৈখিক অনুমান বিবেচনা করে এবং এই রৈখিক ফাংশনের একটি মিনিমাইজারের দিকে অগ্রসর হয় (একই ডোমেনের উপর নেওয়া)। সমস্যা বিবৃতি ধরুন একটি ভেক্টর স্পেসে একটি কম্প্যাক্ট উত্তল সেট এবং এটি একটি উত্তল, ডিফারেনশিয়েবল বাস্তব-মূল্যবান ফাংশন। ফ্র্যাঙ্ক-ওল্ফ অ্যালগরিদম মিনিমাইজ সাপেক্ষে অপ্টিমাইজেশান সমস্যার সমাধান করে। অ্যালগরিদম ইনিশিয়ালাইজেশনঃ আসুন, এবং যে কোনও বিন্দু হতে দিন। ধাপ 1। দিকনির্দেশ-সন্ধানের উপ-সমস্যাঃ বিষয়টির সাপেক্ষে ন্যূনতম সমাধান খুঁজে বের করুন (ব্যাখ্যাঃ প্রথম-ক্রমের টেলর আনুমানিক দ্বারা প্রদত্ত সমস্যার রৈখিক আনুমানিককে ন্যূনতম করুন যা সীমাবদ্ধ থাকার জন্য সীমাবদ্ধ।) ধাপ 2। ধাপের আকার নির্ধারণঃ সেট করুন, বা বিকল্পভাবে সন্ধান করুন যা সাপেক্ষে ন্যূনতম করে। ধাপ 3। হালনাগাদ করুনঃ যাক, যাক এবং ধাপ 1-এ যান। বৈশিষ্ট্য যেখানে সীমাবদ্ধ অপ্টিমাইজেশনের জন্য গ্রেডিয়েন্ট ডিসেন্টের মতো প্রতিযোগিতামূলক পদ্ধতির জন্য প্রতিটি পুনরাবৃত্তির সম্ভাব্য সেটের দিকে একটি অভিক্ষেপ পদক্ষেপের প্রয়োজন হয়, ফ্রাঙ্ক-ওল্ফ অ্যালগরিদমের প্রতিটি পুনরাবৃত্তির একই সেটের উপর শুধুমাত্র একটি রৈখিক সমস্যার সমাধান প্রয়োজন, এবং স্বয়ংক্রিয়ভাবে সম্ভাব্য সেটের মধ্যে থাকে। ফ্রাঙ্ক-ওল্ফ অ্যালগরিদমের অভিসরণ সাধারণভাবে সাবলিনিয়ারঃ সর্বোত্তম উদ্দেশ্যমূলক ফাংশনে ত্রুটিটি k পুনরাবৃত্তির পরে হয়, যতক্ষণ না গ্রেডিয়েন্টটি কিছু আদর্শের সাপেক্ষে ক্রমাগত থাকে। একই অভিসারের হারও দেখানো যেতে পারে যদি উপ-সমস্যাগুলি কেবল আনুমানিকভাবে সমাধান করা হয়। অ্যালগরিদমের পুনরাবৃত্তিকে সর্বদা সম্ভাব্য সেটের চরম পয়েন্টগুলির একটি বিরল উত্তল সংমিশ্রণ হিসাবে উপস্থাপন করা যেতে পারে, যা মেশিন লার্নিং এবং সিগন্যাল প্রসেসিং সমস্যাগুলিতে বিরল লোভী অপ্টিমাইজেশনের জন্য অ্যালগরিদমের জনপ্রিয়তায় সহায়তা করেছে, পাশাপাশি উদাহরণস্বরূপ পরিবহন নেটওয়ার্কে ন্যূনতম ব্যয়ের প্রবাহের অপ্টিমাইজেশান। যদি সম্ভাব্য সেটটি রৈখিক সীমাবদ্ধতার একটি সেট দ্বারা দেওয়া হয়, তবে প্রতিটি পুনরাবৃত্তিতে সমাধান করা উপ-সমস্যাটি একটি রৈখিক প্রোগ্রামে পরিণত হয়। যদিও সবচেয়ে খারাপ ক্ষেত্রে সংমিশ্রণের হার সাধারণভাবে উন্নত করা যায় না, তবে বিশেষ সমস্যা শ্রেণীর জন্য দ্রুত সংমিশ্রণ পাওয়া যেতে পারে, যেমন কিছু দৃঢ়ভাবে উত্তল সমস্যা। যেহেতু উত্তল, তাই আমাদের যে কোনও দুটি বিন্দুর জন্যঃ এটি (অজানা) সর্বোত্তম সমাধানের জন্যও প্রযোজ্য। অর্থাৎ,। পরবর্তী অপ্টিমাইজেশান সমস্যাটি ফ্রাঙ্ক-ওল্ফ অ্যালগরিদমের প্রতিটি পুনরাবৃত্তিতে সমাধান করা হয়, তাই-তম পুনরাবৃত্তির দিক-সন্ধানকারী উপ-সমস্যার সমাধানটি সেটিং দ্বারা প্রতিটি পুনরাবৃত্তির সময় ক্রমবর্ধমান নিম্ন সীমা নির্ধারণ করতে ব্যবহার করা যেতে পারে এবং অজানা সর্বোত্তম মানের উপর এই ধরনের নিম্ন সীমা অনুশীলনে গুরুত্বপূর্ণ কারণ এগুলি একটি স্টপিং মানদণ্ড হিসাবে ব্যবহার করা যেতে পারে এবং সর্বদা থেকে প্রতিটি পুনরাবৃত্তিতে আনুমানিক মানের একটি দক্ষ শংসাপত্র দেয়। এটি দেখানো হয়েছে যে এই সংশ্লিষ্ট দ্বৈততা ব্যবধান, যা নিম্ন সীমা এবং এর মধ্যে পার্থক্য, একই অভিসারের হারের সাথে হ্রাস পায়, অর্থাৎ। নোটস বিব্লিওগ্রাফি (ওভারভিউ পেপার) ফ্রাঙ্ক-ওল্ফ অ্যালগরিদম বর্ণনা। বাহ্যিক লিঙ্ক https://conditional-gradients.org: ফ্রাঙ্ক-ওল্ফ অ্যালগরিদমের একটি সমীক্ষা। মার্গারেট ফ্রাঙ্ক অ্যালগরিদমের ইতিহাসের একটি ব্যক্তিগত বিবরণ দিচ্ছেন আরও দেখুন প্রক্সিমাল গ্রেডিয়েন্ট পদ্ধতি অপ্টিমাইজেশন অ্যালগরিদম এবং পদ্ধতি পুনরাবৃত্তিমূলক পদ্ধতি প্রথম ক্রম পদ্ধতি গ্রেডিয়েন্ট পদ্ধতি