Ellipsoid method
গাণিতিক অপ্টিমাইজেশনে, উপবৃত্তাকার পদ্ধতিটি উত্তল ফাংশনগুলিকে হ্রাস করার জন্য একটি পুনরাবৃত্তিমূলক পদ্ধতি। যখন যুক্তিসঙ্গত তথ্য দিয়ে সম্ভাব্য রৈখিক অপ্টিমাইজেশান সমস্যা সমাধানে বিশেষজ্ঞ হয়, তখন উপবৃত্তাকার পদ্ধতি হল একটি অ্যালগরিদম যা ইনপুট আকারে বহুপদী অনেক ধাপে একটি সর্বোত্তম সমাধান খুঁজে পায়। উপবৃত্তাকার পদ্ধতিটি উপবৃত্তাকারগুলির একটি ক্রম তৈরি করে যার আয়তন প্রতিটি পদক্ষেপে সমানভাবে হ্রাস পায়, এইভাবে একটি উত্তল ফাংশনের একটি মিনিমাইজারকে আবদ্ধ করে। উপবৃত্তাকার পদ্ধতির একটি দীর্ঘ ইতিহাস রয়েছে। একটি পুনরাবৃত্তিমূলক পদ্ধতি হিসাবে, নাওম জেড শোর একটি প্রাথমিক সংস্করণ চালু করেছিলেন। 1972 সালে আরকাডি নেমিরোভস্কি এবং ডেভিড বি ইউডিন (জুডিন) প্রকৃত উত্তল হ্রাসকরণের জন্য একটি আনুমানিক অ্যালগরিদম অধ্যয়ন করেছিলেন। যুক্তিসঙ্গত তথ্য দিয়ে রৈখিক প্রোগ্রামিং সমস্যা সমাধানের জন্য একটি অ্যালগরিদম হিসাবে, উপবৃত্তাকার অ্যালগরিদম লিওনিড খাচিয়ান দ্বারা অধ্যয়ন করা হয়েছিল; খাচিয়ানের কৃতিত্ব ছিল রৈখিক প্রোগ্রামগুলির বহুপদী-সময় সমাধানযোগ্যতা প্রমাণ করা। তাত্ত্বিক দৃষ্টিকোণ থেকে এটি একটি উল্লেখযোগ্য পদক্ষেপ ছিলঃ সেই সময়ে রৈখিক সমস্যা সমাধানের জন্য স্ট্যান্ডার্ড অ্যালগরিদম ছিল সিম্প্লেক্স অ্যালগরিদম, যার একটি রান টাইম থাকে যা সাধারণত সমস্যার আকারে রৈখিক হয়, তবে যে উদাহরণগুলির জন্য এটি বিদ্যমান যার জন্য এটি সমস্যার আকারে সূচকীয়। এইভাবে, সমস্ত ক্ষেত্রে বহুপদী হওয়ার নিশ্চয়তা দেওয়া একটি অ্যালগরিদম থাকা একটি তাত্ত্বিক অগ্রগতির মতো মনে হয়েছিল। খাচিয়ানের কাজ প্রথমবারের মতো দেখিয়েছে যে, রৈখিক প্রোগ্রামগুলি সমাধান করার জন্য অ্যালগরিদম থাকতে পারে যার রানটাইম বহুপদী হিসাবে প্রমাণিত হতে পারে। বাস্তবে, অ্যালগরিদমটি মোটামুটি ধীর এবং ব্যবহারিক আগ্রহের সামান্য, যদিও এটি পরবর্তী কাজের জন্য অনুপ্রেরণা প্রদান করেছিল যা অনেক বেশি ব্যবহারিক কাজে পরিণত হয়েছিল। বিশেষত, কর্মকারের অ্যালগরিদম, একটি অভ্যন্তরীণ-বিন্দু পদ্ধতি, বাস্তবে উপবৃত্তাকার পদ্ধতির তুলনায় অনেক দ্রুত। কর্মকারের অ্যালগরিদম সবচেয়ে খারাপ ক্ষেত্রেও দ্রুততর। উপবৃত্তাকার অ্যালগরিদম জটিলতা তাত্ত্বিকদের (সবচেয়ে খারাপ ক্ষেত্রে) সীমা অর্জন করতে দেয় যা সমস্যার মাত্রা এবং তথ্যের আকারের উপর নির্ভর করে, তবে সারির সংখ্যার উপর নয়, তাই এটি বহু বছর ধরে সমন্বয়মূলক অপ্টিমাইজেশন তত্ত্বে গুরুত্বপূর্ণ ছিল। শুধুমাত্র একবিংশ শতাব্দীতে অনুরূপ জটিলতা বৈশিষ্ট্য সহ অভ্যন্তরীণ-বিন্দু অ্যালগরিদম আবির্ভূত হয়েছে। বর্ণনা একটি উত্তল ন্যূনতমকরণ সমস্যা নিম্নলিখিত উপাদানগুলি নিয়ে গঠিত। ভেক্টরের উপর একটি উত্তল ফাংশনকে ন্যূনতম করতে হবে (যার মধ্যে n ভেরিয়েবল রয়েছে); রূপের উত্তল বৈষম্যের সীমাবদ্ধতা, যেখানে ফাংশনগুলি উত্তল; এই সীমাবদ্ধতাগুলি একটি উত্তল সেটকে সংজ্ঞায়িত করে। ফর্মের রৈখিক সমতা সীমাবদ্ধতা। আমাদের একটি প্রাথমিক উপবৃত্তাকারও দেওয়া হয়েছে যা একটি মিনিমাইজার ধারণকারী হিসাবে সংজ্ঞায়িত করা হয়েছে, যেখানে এবং এর কেন্দ্র। পরিশেষে, আমাদের উত্তল সেটের জন্য একটি পৃথকীকরণ ওরাকলের অস্তিত্ব প্রয়োজন। একটি বিন্দু দেওয়া হলে, ওরাকলকে দুটি উত্তরের মধ্যে একটি উত্তর দিতে হবেঃ "বিন্দুটি ভিতরে রয়েছে", অথবা-"বিন্দুটি ভিতরে নেই, এবং উপরন্তু, এখানে একটি হাইপারপ্লেন রয়েছে যা থেকে পৃথক হয়", অর্থাৎ, একটি ভেক্টর যা সকলের জন্য। উপবৃত্তাকার পদ্ধতির আউটপুট হয়ঃ পলিটোপের যে কোনও বিন্দু (অর্থাৎ, যে কোনও সম্ভাব্য বিন্দু), বা-একটি প্রমাণ যা খালি। সর্বত্র শূন্য একটি ফাংশনের অসমতা-সীমাবদ্ধ ন্যূনতমকরণ কেবল কোনও সম্ভাব্য বিন্দু চিহ্নিত করার সমস্যার সাথে মিলে যায়। দেখা যাচ্ছে যে কোনও রৈখিক প্রোগ্রামিং সমস্যাকে একটি রৈখিক সম্ভাব্যতা সমস্যায় হ্রাস করা যেতে পারে (যেমন। কিছু রৈখিক বৈষম্য এবং সমতার সীমাবদ্ধতা সাপেক্ষে শূন্য ফাংশনকে হ্রাস করুন)। এটি করার একটি উপায় হল মৌলিক এবং দ্বৈত রৈখিক প্রোগ্রামগুলিকে একটি প্রোগ্রামে একত্রিত করা এবং অতিরিক্ত (রৈখিক) সীমাবদ্ধতা যোগ করা যে প্রাথমিক সমাধানের মান দ্বৈত সমাধানের মানের চেয়ে খারাপ নয়। আরেকটি উপায় হল রৈখিক প্রোগ্রামের উদ্দেশ্যকে একটি অতিরিক্ত সীমাবদ্ধতা হিসাবে বিবেচনা করা এবং সর্বোত্তম মান খুঁজে পেতে বাইনারি অনুসন্ধান ব্যবহার করা। অনিয়ন্ত্রিত ন্যূনতমকরণ অ্যালগরিদমের কে-তম পুনরাবৃত্তিতে, আমাদের একটি উপবৃত্তাকার কেন্দ্রে একটি বিন্দু থাকে আমরা একটি ভেক্টর পাওয়ার জন্য কাটিং-প্লেন ওরাকলকে প্রশ্ন করি যাতে আমরা তাই উপসংহারে আসি যে আমরা উপরে বর্ণিত অর্ধ-উপবৃত্তাকার ধারণকারী ন্যূনতম আয়তনের উপবৃত্তাকার হিসাবে সেট করি এবং গণনা করি। আপডেটটি দেওয়া হয় যেখানে স্টপিং ক্রাইটেরিয়ানটি সেই বৈশিষ্ট্য দ্বারা দেওয়া হয় যে অসমতা-সীমাবদ্ধ মিনিমাইজেশন সীমাবদ্ধ মিনিমাইজেশনের জন্য অ্যালগরিদমের কে-তম পুনরাবৃত্তিতে, আমাদের আগের মতো একটি উপবৃত্তাকার কেন্দ্রে একটি বিন্দু রয়েছে। আমাদের অবশ্যই এখন পর্যন্ত সম্ভাব্য পুনরাবৃত্তির ক্ষুদ্রতম উদ্দেশ্যমূলক মান রেকর্ড করা মানগুলির একটি তালিকা বজায় রাখতে হবে। পয়েন্টটি সম্ভব কিনা তার উপর নির্ভর করে, আমরা দুটি কাজের মধ্যে একটি সম্পাদন করিঃ যদি সম্ভব হয়, তবে মূলত অনিয়ন্ত্রিত ক্ষেত্রে একই আপডেট সম্পাদন করুন, এমন একটি উপ-গ্রেডিয়েন্ট বেছে নিন যা সন্তুষ্ট করে যদি অসম্ভব হয় এবং জে-তম সীমাবদ্ধতা লঙ্ঘন করে, সম্ভাব্যতা কাট দিয়ে উপবৃত্তাকার আপডেট করুন। আমাদের সম্ভাব্যতা হ্রাস একটি উপ-গ্রেডিয়েন্ট হতে পারে যা সমস্ত সম্ভাব্য z-এর জন্য অবশ্যই সন্তুষ্ট করতে হবে। কর্মক্ষমতা উপবৃত্তাকার পদ্ধতিটি নিম্ন-মাত্রিক সমস্যাগুলিতে ব্যবহৃত হয়, যেমন সমতলীয় অবস্থান সমস্যা, যেখানে এটি সংখ্যার দিক থেকে স্থিতিশীল। এমনকি "ছোট" আকারের সমস্যাগুলিতেও, এটি সংখ্যাসূচক অস্থিতিশীলতা এবং অনুশীলনে দুর্বল পারফরম্যান্সে ভুগছে। যাইহোক, উপবৃত্তাকার পদ্ধতিটি কম্বিনেটোরিয়াল অপ্টিমাইজেশনের একটি গুরুত্বপূর্ণ তাত্ত্বিক কৌশল। গণনামূলক জটিলতা তত্ত্বে, উপবৃত্তাকার অ্যালগরিদম আকর্ষণীয় কারণ এর জটিলতা কলামের সংখ্যা এবং সহগের ডিজিটাল আকারের উপর নির্ভর করে, তবে সারির সংখ্যার উপর নয়। একবিংশ শতাব্দীতে, অনুরূপ বৈশিষ্ট্য সহ অভ্যন্তরীণ-বিন্দু অ্যালগরিদম আবির্ভূত হয়েছে। ডিমিট্রিস আলেভ্রাস এবং ম্যানফ্রেড ডব্লিউ প্যাডবার্গ, লিনিয়ার অপ্টিমাইজেশন অ্যান্ড এক্সটেনশনসঃ প্রবলেম অ্যান্ড এক্সটেনশনস, ইউনিভার্সিটেক্সট, স্প্রিংগার-ভার্লাগ, 2001। (সমাধান নিয়ে প্যাডবার্গের সমস্যা।) ভি. চন্দ্রু এবং M.R.Rao, লিনিয়ার প্রোগ্রামিং, অধ্যায় 31 ইন অ্যালগরিদমস অ্যান্ড থিওরি অফ কম্পিউটশন হ্যান্ডবুক, সম্পাদনা করেছেন M.J.Atallah, সিআরসি প্রেস 1999,31-1 থেকে 31-37। ভি. চন্দ্রু এবং M.R.Rao, পূর্ণসংখ্যা প্রোগ্রামিং, অ্যালগরিদমের অধ্যায় 32 এবং গণনা হ্যান্ডবুকের তত্ত্ব, M.J.Atallah দ্বারা সম্পাদিত, সিআরসি প্রেস 1999,32-1 থেকে 32-45। জর্জ বি. ড্যান্টজিগ এবং মুকুন্দ এন. থাপা। 1997 সালে। রৈখিক প্রোগ্রামিং 1: ভূমিকা। স্প্রিংগার-ভার্লাগ। জর্জ বি. ড্যান্টজিগ এবং মুকুন্দ এন. থাপা। 2003 সালে। রৈখিক প্রোগ্রামিং 2: তত্ত্ব এবং সম্প্রসারণ। স্প্রিংগার-ভার্লাগ। এল. লোভাসঃ অ্যান অ্যালগরিদমিক থিওরি অফ নাম্বারস, গ্রাফস অ্যান্ড কনভেক্সিটি, সিবিএমএস-এনএসএফ রিজিওনাল কনফারেন্স সিরিজ ইন অ্যাপ্লায়েড ম্যাথমেটিক্স 50, সিয়াম, ফিলাডেলফিয়া, পেনসিলভেনিয়া, 1986 কাটা জি. মূর্তি, লিনিয়ার প্রোগ্রামিং, উইলি, 1983। এম. প্যাডবার্গ, লিনিয়ার অপ্টিমাইজেশন অ্যান্ড এক্সটেনশনস, দ্বিতীয় সংস্করণ, স্প্রিংগার-ভারল্যাগ, 1999। ক্রিস্টোস এইচ. পাপাডিমিত্রিউ এবং কেনেথ স্টেইগলিটস, কম্বিনেটোরিয়াল অপ্টিমাইজেশানঃ অ্যালগরিদমস অ্যান্ড কমপ্লেক্সিটি, করেক্টেড রিপাবলিকেশান উইথ এ নিউ প্রফেস, ডোভার। আলেকজান্ডার শ্রিজভার, লিনিয়ার এবং ইন্টিজার প্রোগ্রামিংয়ের তত্ত্ব। জন উইলি অ্যান্ড সন্স, 1998, এক্সটার্নাল লিঙ্ক EE364b, একটি স্ট্যানফোর্ড কোর্সের হোমপেজ কম্বিনেটোরিয়াল অপ্টিমাইজেশন কনভেক্স অপ্টিমাইজেশন লিনিয়ার প্রোগ্রামিং