Subgradient method
অধোগমন পদ্ধতিগুলি উত্তল ন্যূনতমকরণ সমস্যা সমাধানের জন্য পুনরাবৃত্তিমূলক পদ্ধতি। মূলত 1960 এবং 1970-এর দশকে নাওম জেড শোর এবং অন্যান্যদের দ্বারা বিকশিত, একটি অ-পার্থক্যযোগ্য উদ্দেশ্যমূলক ফাংশনে প্রয়োগ করা হলে উপ-গ্রেডিয়েন্ট পদ্ধতিগুলি অভিসারী হয়। যখন অবজেক্টিভ ফাংশনটি ডিফারেনশিয়েবল হয়, তখন অনিয়ন্ত্রিত সমস্যার জন্য সাব-গ্রেডিয়েন্ট পদ্ধতিগুলি স্টিপেস্ট ডিসেন্ট পদ্ধতির মতো একই অনুসন্ধানের দিক ব্যবহার করে। নিউটনের পদ্ধতির তুলনায় অধোগমন পদ্ধতিগুলি ধীর হয় যখন প্রয়োগ করা হয় দ্বিগুণ অবিচ্ছিন্নভাবে ডিফারেনশিয়েবল উত্তল ফাংশনকে হ্রাস করার জন্য। যাইহোক, নিউটনের পদ্ধতিটি অ-পার্থক্যযোগ্য সংযোগযুক্ত সমস্যাগুলির সাথে একত্রিত হতে ব্যর্থ হয়। সাম্প্রতিক বছরগুলিতে, উত্তল ন্যূনতমকরণ সমস্যার জন্য কিছু অভ্যন্তরীণ-বিন্দু পদ্ধতির পরামর্শ দেওয়া হয়েছে, তবে অবরোহী অভিক্ষেপ পদ্ধতি এবং অবরোহী সম্পর্কিত বান্ডিল পদ্ধতি প্রতিযোগিতামূলক রয়ে গেছে। খুব বড় সংখ্যক মাত্রা সহ উত্তল ন্যূনতমকরণ সমস্যার জন্য, উপ-গ্রেডিয়েন্ট-প্রজেকশন পদ্ধতি উপযুক্ত, কারণ তাদের সামান্য সংরক্ষণের প্রয়োজন হয়। অধোগামী অভিক্ষেপ পদ্ধতিগুলি প্রায়শই পচন কৌশলগুলির সাথে বড় আকারের সমস্যাগুলিতে প্রয়োগ করা হয়। এই ধরনের পচন পদ্ধতিগুলি প্রায়শই কোনও সমস্যার জন্য একটি সহজ বিতরণ পদ্ধতির অনুমতি দেয়। ধ্রুপদী অধোগতির নিয়মগুলি ডোমেন সহ একটি উত্তল ফাংশন হতে দিন। একটি ধ্রুপদী উপ-গ্রেডিয়েন্ট পদ্ধতি পুনরাবৃত্তি করে যেখানে অ্যাটের যে কোনও উপ-গ্রেডিয়েন্টকে বোঝায় এবং এটি এর পুনরাবৃত্তি। যদি ডিফারেনশিয়েবল হয়, তবে এর একমাত্র উপ-গ্রেডিয়েন্ট হল গ্রেডিয়েন্ট ভেক্টর নিজেই। এটি এমন হতে পারে যা এট-এর জন্য অবতরণের দিক নয়। তাই আমরা এমন একটি তালিকা বজায় রাখি যা এখন পর্যন্ত পাওয়া সর্বনিম্ন উদ্দেশ্যমূলক ফাংশন মানের উপর নজর রাখে, অর্থাৎ। ধাপের আকারের নিয়ম বিভিন্ন ধরনের ধাপের আকারের নিয়মগুলি উপ-গ্রেডিয়েন্ট পদ্ধতি দ্বারা ব্যবহৃত হয়। এই নিবন্ধে পাঁচটি ধ্রুপদী ধাপ-আকারের নিয়ম উল্লেখ করা হয়েছে যার জন্য অভিসরণ প্রমাণ জানা যায়ঃ ধ্রুবক ধাপের আকার, ধ্রুবক ধাপের দৈর্ঘ্য, যা বর্গক্ষেত্রের যোগফল দেয় তবে যোগফলের আকার দেয় না, অর্থাৎ। যেকোনও ধাপের মাপ যা অসম্পূর্ণ হ্রাসকে সন্তুষ্ট করে, অর্থাৎ। যেকোনও ধাপের মাপ যা অসম্পূর্ণ হ্রাসমান ধাপের দৈর্ঘ্যকে সন্তুষ্ট করে, অর্থাৎ যেখানে পাঁচটি নিয়মের জন্য, পদ্ধতিটি পুনরাবৃত্ত হওয়ার আগে ধাপ-আকারগুলি "অফ-লাইন" নির্ধারণ করা হয়; ধাপ-আকারগুলি পূর্ববর্তী পুনরাবৃত্তির উপর নির্ভর করে না। সাবগ্রেডিএন্ট পদ্ধতির এই "অফ-লাইন" বৈশিষ্ট্যটি ডিফারেনশিয়েবল ফাংশনের জন্য অবতরণ পদ্ধতির জন্য ব্যবহৃত "অন-লাইন" ধাপ-আকারের নিয়মগুলির থেকে আলাদাঃ ডিফারেনশিয়েবল ফাংশনগুলিকে হ্রাস করার জন্য অনেক পদ্ধতি সংমিশ্রণের জন্য ওল্ফের পর্যাপ্ত শর্তগুলি সন্তুষ্ট করে, যেখানে ধাপ-আকার সাধারণত বর্তমান বিন্দু এবং বর্তমান অনুসন্ধান-দিকের উপর নির্ভর করে। বার্টসেকাস এবং বার্টসেকাস, নেডিক এবং ওজডাগলারের বইগুলিতে ক্রমবর্ধমান সংস্করণ সহ অধোগামী পদ্ধতির জন্য ধাপের আকারের নিয়মগুলির একটি বিস্তৃত আলোচনা দেওয়া হয়েছে। ধ্রুবক ধাপ-দৈর্ঘ্য এবং স্কেল করা উপ-গ্রেডিয়েন্টগুলির জন্য ইউক্লিডীয় মান একটির সমান, উপ-গ্রেডিয়েন্ট পদ্ধতিটি সর্বনিম্ন মানের একটি নির্বিচারে কাছাকাছি আনুমানিকতায় রূপান্তরিত হয়, যা শোরের ফলস্বরূপ। এই ধ্রুপদী অধোগমন পদ্ধতিগুলির কার্যকারিতা দুর্বল এবং সাধারণ ব্যবহারের জন্য আর সুপারিশ করা হয় না। যাইহোক, এগুলি এখনও বিশেষ প্রয়োগগুলিতে ব্যাপকভাবে ব্যবহৃত হয় কারণ এগুলি সহজ এবং হাতে থাকা সমস্যার বিশেষ কাঠামোর সুবিধা নেওয়ার জন্য এগুলি সহজেই মানিয়ে নেওয়া যেতে পারে। সাবগ্রেডিএন্ট-প্রজেকশন এবং বান্ডিল পদ্ধতি 1970-এর দশকে, ক্লড লেমারেচাল এবং ফিল ওল্ফ উত্তল হ্রাসকরণের সমস্যার জন্য অবতরণের "বান্ডিল পদ্ধতি" প্রস্তাব করেছিলেন। সেই সময় থেকে "বান্ডিল পদ্ধতি" শব্দের অর্থ উল্লেখযোগ্যভাবে পরিবর্তিত হয়েছে। আধুনিক সংস্করণ এবং সম্পূর্ণ অভিসরণ বিশ্লেষণ কিউয়েল দ্বারা সরবরাহ করা হয়েছিল। সমসাময়িক বান্ডিল-পদ্ধতিগুলি প্রায়শই ধাপ-আকার বেছে নেওয়ার জন্য "স্তর নিয়ন্ত্রণ" নিয়ম ব্যবহার করে, বরিস টি. পলিয়াকের (1969) "সাবগ্রেডিএন্ট-প্রজেকশন" পদ্ধতি থেকে কৌশলগুলি বিকাশ করে। যাইহোক, এমন কিছু সমস্যা রয়েছে যার উপর বান্ডিল পদ্ধতিগুলি উপ-গ্রেডিয়েন্ট-প্রজেকশন পদ্ধতির তুলনায় সামান্য সুবিধা দেয়। সীমাবদ্ধ অপ্টিমাইজেশন প্রজেক্টেড সাবগ্র্যাডিয়েন্ট সাবগ্র্যাডিয়েন্ট পদ্ধতির একটি এক্সটেনশন হল প্রজেক্টেড সাবগ্র্যাডিয়েন্ট পদ্ধতি, যা একটি উত্তল সেটের সাপেক্ষে সীমাবদ্ধ অপ্টিমাইজেশন সমস্যার সমাধান করে। অভিক্ষিপ্ত অধোগমন পদ্ধতিটি পুনরাবৃত্তি ব্যবহার করে যেখানে অভিক্ষেপ চালু থাকে এবং সাধারণ সীমাবদ্ধতার যে কোনও অধোগমন হয় অধোগমন পদ্ধতিটি অসমতা সীমাবদ্ধ সমস্যা সমাধানের জন্য প্রসারিত করা যেতে পারে যেখানে উত্তল হয়। অ্যালগরিদমটি অনিয়ন্ত্রিত কেসের মতো একই রূপ নেয় যেখানে একটি ধাপের আকার, এবং উদ্দেশ্যটির একটি উপ-গ্রেডিয়েন্ট বা টেকের সীমাবদ্ধ ফাংশনগুলির মধ্যে একটি যেখানে এর উপ-পার্থক্যকে বোঝায়। যদি বর্তমান বিন্দুটি সম্ভব হয়, তবে অ্যালগরিদম একটি উদ্দেশ্যমূলক উপ-গ্রেডিয়েন্ট ব্যবহার করে; যদি বর্তমান বিন্দুটি অসম্ভব হয়, তবে অ্যালগরিদম যে কোনও লঙ্ঘিত সীমাবদ্ধতার একটি উপ-গ্রেডিয়েন্ট বেছে নেয়। রেফারেন্স আরও পড়ার বাহ্যিক লিঙ্ক EE364A এবং EE364B, স্ট্যানফোর্ডের উত্তল অপ্টিমাইজেশন কোর্স ক্রম। অপ্টিমাইজেশন অ্যালগরিদম এবং পদ্ধতি কনভেক্স অপ্টিমাইজেশন