Augmented Lagrangian method
অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতিগুলি সীমাবদ্ধ অপ্টিমাইজেশান সমস্যা সমাধানের জন্য একটি নির্দিষ্ট শ্রেণীর অ্যালগরিদম। তাদের পেনাল্টি পদ্ধতির সাথে মিল রয়েছে যে তারা একটি সীমাবদ্ধ অপ্টিমাইজেশান সমস্যাকে অনিয়ন্ত্রিত সমস্যার একটি সিরিজ দ্বারা প্রতিস্থাপন করে এবং উদ্দেশ্যটিতে একটি পেনাল্টি শব্দ যোগ করে, তবে অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতি একটি ল্যাগ্রাঞ্জ গুণক অনুকরণ করার জন্য ডিজাইন করা আরও একটি শব্দ যোগ করে। অগমেন্টেড ল্যাগ্রাঞ্জিয়ান ল্যাগ্রাঞ্জ মাল্টিপ্লায়ার পদ্ধতির সাথে সম্পর্কিত, তবে অভিন্ন নয়। ভিন্নভাবে দেখলে, অনিয়ন্ত্রিত উদ্দেশ্য হল সীমাবদ্ধ সমস্যার ল্যাগ্রাঞ্জিয়ান, একটি অতিরিক্ত পেনাল্টি মেয়াদ (বৃদ্ধি) সহ। পদ্ধতিটি মূলত গুণক পদ্ধতি হিসাবে পরিচিত ছিল এবং 1970 এবং 1980-এর দশকে পেনাল্টি পদ্ধতির সম্ভাব্য বিকল্প হিসাবে অধ্যয়ন করা হয়েছিল। ম্যাগনাস হেস্টেনেস এবং তারপর 1969 সালে মাইকেল পাওয়েল এটি নিয়ে প্রথম আলোচনা করেন। পদ্ধতিটি আর. টাইরেল রকাফেলার দ্বারা ফেনচেল দ্বৈততার ক্ষেত্রে অধ্যয়ন করা হয়েছিল, বিশেষত প্রক্সিমাল-পয়েন্ট পদ্ধতি, মোরেউ-ইয়োসিডা নিয়মিতকরণ এবং সর্বাধিক মনোটোন অপারেটরের ক্ষেত্রে; এই পদ্ধতিগুলি কাঠামোগত অপ্টিমাইজেশনে ব্যবহৃত হয়েছিল। পদ্ধতিটি দিমিত্রি বার্টসেকাস দ্বারাও অধ্যয়ন করা হয়েছিল, বিশেষত তাঁর 1982 সালের বইয়ে, অ-চতুর্ভুজ নিয়মিতকরণ ফাংশন (যেমন, এনট্রপিক নিয়মিতকরণ) জড়িত এক্সটেনশনগুলির সাথে। এই সম্মিলিত গবেষণা "গুণকের সূচকীয় পদ্ধতির" জন্ম দেয় যা দ্বিগুণ-পার্থক্যযোগ্য বর্ধিত ল্যাগ্রাঞ্জিয়ান ফাংশনের সাথে বৈষম্যের সীমাবদ্ধতাগুলি পরিচালনা করে। 1970-এর দশক থেকে, ক্রমিক চতুর্ভুজ প্রোগ্রামিং (এসকিউপি) এবং অভ্যন্তরীণ বিন্দু পদ্ধতি (আইপিএম)-কে আরও বেশি মনোযোগ দেওয়া হয়েছে, কারণ তারা সংখ্যাসূচক সফ্টওয়্যার লাইব্রেরি থেকে স্পার্স ম্যাট্রিক্স সাবরুটিনগুলি আরও সহজেই ব্যবহার করে এবং আংশিকভাবে কারণ আইপিএমগুলি স্ব-সমন্বয়মূলক ফাংশনের তত্ত্বের মাধ্যমে প্রমাণিত জটিলতার ফলাফল ধারণ করে। অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতিটি LANCELOT, ALGENCAN এবং AMPL অপ্টিমাইজেশন সিস্টেম দ্বারা পুনরুজ্জীবিত হয়েছিল, যা আপাতদৃষ্টিতে ঘন কিন্তু "আংশিকভাবে-বিচ্ছিন্ন" সমস্যাগুলিতে বিরল ম্যাট্রিক্স কৌশলগুলি ব্যবহার করার অনুমতি দেয়। পদ্ধতিটি এখনও কিছু সমস্যার জন্য কার্যকর। 2007 সালের দিকে, টোটাল ভ্যারিয়েশন ডিনোইজিং এবং কম্প্রেসড সেন্সিংয়ের মতো ক্ষেত্রে অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতির পুনরুত্থান ঘটে। বিশেষত, স্ট্যান্ডার্ড অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতির একটি রূপ যা আংশিক আপডেট ব্যবহার করে (রৈখিক সমীকরণ সমাধানের জন্য গাউস-সিডেল পদ্ধতির অনুরূপ) যা মাল্টিপ্লায়ার বা এ. ডি. এম. এম-এর বিকল্প দিক পদ্ধতি হিসাবে পরিচিত, কিছুটা মনোযোগ আকর্ষণ করে। সাধারণ পদ্ধতি নিম্নলিখিত সীমাবদ্ধ অপ্টিমাইজেশান সমস্যা সমাধানের কথা বিবেচনা করুনঃ যেখানে সমতা সীমাবদ্ধতার জন্য সূচকগুলি বোঝায়। এই সমস্যাটি অনিয়ন্ত্রিত ন্যূনতম সমস্যাগুলির একটি সিরিজ হিসাবে সমাধান করা যেতে পারে। রেফারেন্সের জন্য, আমরা প্রথমে পেনাল্টি পদ্ধতির পদ্ধতির কে-তম ধাপটি তালিকাভুক্ত করিঃ পেনাল্টি পদ্ধতিটি এই সমস্যার সমাধান করে, তারপর পরবর্তী পুনরাবৃত্তিতে এটি একটি বৃহত্তর মান ব্যবহার করে এবং পুরানো সমাধানটিকে প্রাথমিক অনুমান বা "ওয়ার্ম স্টার্ট" হিসাবে ব্যবহার করে সমস্যার সমাধান করে। অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতিটি নিম্নলিখিত অনিয়ন্ত্রিত উদ্দেশ্য ব্যবহার করেঃ এবং প্রতিটি পুনরাবৃত্তির পরে, আপডেট করার পাশাপাশি, পরিবর্তনশীলটিও নিয়ম অনুসারে আপডেট করা হয় যেখানে kth ধাপে অনিয়ন্ত্রিত সমস্যার সমাধান রয়েছে (অর্থাৎ। )। পরিবর্তনশীল হল ল্যাগ্রাঞ্জ গুণকের একটি অনুমান, এবং এই অনুমানের নির্ভুলতা প্রতিটি পদক্ষেপে উন্নত হয়। পদ্ধতির প্রধান সুবিধা হল যে পেনাল্টি পদ্ধতির বিপরীতে, মূল সীমাবদ্ধ সমস্যা সমাধানের জন্য এটি গ্রহণ করার প্রয়োজন নেই। ল্যাগ্রাঞ্জ মাল্টিপ্লায়ার শব্দের উপস্থিতির কারণে, এটি অনেক ছোট থাকতে পারে এবং এইভাবে খারাপ অবস্থা এড়াতে পারে। তবুও, একটি বড় সীমাবদ্ধ সেট (সুরক্ষা)-এ প্রকল্প গুণক অনুমানের ব্যবহারিক বাস্তবায়নে এটি সাধারণ যা সংখ্যাসূচক অস্থিরতা এড়ায় এবং শক্তিশালী তাত্ত্বিক সম্মিলনের দিকে পরিচালিত করে। বৈষম্যের সীমাবদ্ধতা সামলানোর জন্য পদ্ধতিটি প্রসারিত করা যেতে পারে। ব্যবহারিক উন্নতির আলোচনার জন্য, রেফ দেখুন। মাল্টিপ্লায়ারের বিকল্প দিকনির্দেশ পদ্ধতি মাল্টিপ্লায়ারের বিকল্প দিকনির্দেশ পদ্ধতি (এ. ডি. এম. এম) হল অগমেন্টেড ল্যাগ্রাঞ্জিয়ান স্কিমের একটি রূপ যা দ্বৈত চলকের জন্য আংশিক আপডেট ব্যবহার করে। এই পদ্ধতিটি প্রায়শই সমস্যা সমাধানের জন্য প্রয়োগ করা হয় যেমন, এটি সীমাবদ্ধ সমস্যার সমতুল্য, যদিও এই পরিবর্তনটি তুচ্ছ বলে মনে হতে পারে, সমস্যাটি এখন সীমাবদ্ধ অপ্টিমাইজেশনের পদ্ধতি ব্যবহার করে আক্রমণ করা যেতে পারে (বিশেষত, অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতি), এবং উদ্দেশ্যমূলক ফাংশনটি x এবং y তে পৃথকযোগ্য। দ্বৈত আপডেটের জন্য একই সময়ে x এবং y-তে একটি প্রক্সিমিটি ফাংশন সমাধান করা প্রয়োজন; এ. ডি. এম. এম কৌশলটি প্রথমে x-এর জন্য y স্থির করে এবং তারপর x স্থির করে y-এর জন্য সমাধান করে এই সমস্যাটি সমাধান করার অনুমতি দেয়। রূপান্তর না হওয়া পর্যন্ত পুনরাবৃত্তি করার পরিবর্তে (জ্যাকোবি পদ্ধতির মতো), অ্যালগরিদম সরাসরি দ্বৈত পরিবর্তনশীল আপডেট করতে এবং তারপর প্রক্রিয়াটি পুনরাবৃত্তি করতে এগিয়ে যায়। এটি সঠিক ন্যূনতমকরণের সমতুল্য নয়, তবে পদ্ধতিটি এখনও কিছু অনুমানের অধীনে সঠিক সমাধানে একত্রিত হয়। এই আনুমানিকতার কারণে, অ্যালগরিদমটি বিশুদ্ধ অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতি থেকে আলাদা। এ. ডি. এম. এম-কে ডগলাস-র্যাকফোর্ড বিভাজন অ্যালগরিদমের প্রয়োগ হিসাবে দেখা যেতে পারে এবং ডগলাস-র্যাকফোর্ড অ্যালগরিদমটি প্রক্সিমাল পয়েন্ট অ্যালগরিদমের একটি উদাহরণ; বিশদ বিবরণ রেফারে পাওয়া যায়। YALL1 (2009), SPARSA (2009) এবং SALSA (2009) সহ বেশ কয়েকটি আধুনিক সফ্টওয়্যার প্যাকেজ রয়েছে, যা ভিত্তি অনুসরণ এবং রূপগুলি সমাধান করে এবং ADMM ব্যবহার করে। এমন প্যাকেজও রয়েছে যা আরও সাধারণ সমস্যা সমাধানের জন্য এ. ডি. এম. এম ব্যবহার করে, যার মধ্যে কয়েকটি একাধিক কম্পিউটিং কোর (যেমন, এস. এন. এ. পি. ভি. এক্স (2015), প্যারা. এ. ডি. এম. এম (2016)) কাজে লাগাতে পারে। স্টোকাস্টিক অপ্টিমাইজেশন (এর গ্রেডিয়েন্ট) ফাংশনের শোরগোলের নমুনাগুলিতে অ্যাক্সেসের সাথে একটি ক্ষতি ফাংশনকে হ্রাস করার সমস্যা বিবেচনা করে। লক্ষ্য হল নতুন নমুনা প্রতি সর্বোত্তম পরামিতি (মিনিমাইজার)-এর একটি অনুমান করা। কিছু পরিবর্তন সহ, এ. ডি. এম. এম স্টোকাস্টিক অপ্টিমাইজেশনের জন্য ব্যবহার করা যেতে পারে। একটি স্টোকাস্টিক পরিবেশে, শুধুমাত্র একটি গ্রেডিয়েন্টের কোলাহলপূর্ণ নমুনাগুলি অ্যাক্সেসযোগ্য, তাই ল্যাগ্রাঞ্জিয়ানের একটি সঠিক অনুমান ব্যবহার করা হয়ঃ যেখানে একটি সময়-পরিবর্তিত ধাপের আকার। নিয়মিত সমস্যা সমাধানের জন্য এ. ডি. এম. এম প্রয়োগ করা হয়েছে, যেখানে ফাংশন অপ্টিমাইজেশন এবং নিয়মিতকরণ স্থানীয়ভাবে করা যেতে পারে এবং তারপরে সীমাবদ্ধতার মাধ্যমে বিশ্বব্যাপী সমন্বয় করা যেতে পারে। নিয়মিত অপ্টিমাইজেশান সমস্যাগুলি উচ্চ-মাত্রিক ব্যবস্থায় বিশেষভাবে প্রাসঙ্গিক কারণ নিয়মিতকরণ একটি প্রাকৃতিক প্রক্রিয়া যা দুর্বলতা কাটিয়ে উঠতে এবং সর্বোত্তম সমাধানে পার্সিমোনিকে উৎসাহিত করতে পারে (যেমন, স্পার্সিটি এবং নিম্ন পদমর্যাদা)। নিয়মিত সমস্যা সমাধানের জন্য এ. ডি. এম. এম-এর কার্যকারিতার অর্থ হতে পারে এটি লুকানো-মাত্রিক স্টোকাস্টিক অপ্টিমাইজেশান সমস্যা সমাধানের জন্য কার্যকর হতে পারে। বিকল্প পন্থা ক্রমিক চতুর্ভুজ প্রোগ্রামিং ক্রমিক রৈখিক প্রোগ্রামিং সফ্টওয়্যার অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতির মুক্ত উৎস এবং অ-মুক্ত/বাণিজ্যিক বাস্তবায়নঃ Accord.NET (অগমেন্টেড ল্যাগ্রাঞ্জিয়ান অপ্টিমাইজারের C #বাস্তবায়ন) ALGLIB (পূর্বশর্তযুক্ত অগমেন্টেড ল্যাগ্রাঞ্জিয়ান সমাধানকারীর C #এবং C + + বাস্তবায়ন) PENN (GPL 3, বাণিজ্যিক লাইসেন্স উপলব্ধ) LANCELOT (বিনামূল্যে "অভ্যন্তরীণ ব্যবহার" লাইসেন্স, প্রদত্ত বাণিজ্যিক বিকল্প) MINOS (কিছু ধরণের সমস্যার জন্য একটি অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতিও ব্যবহার করে)। অ্যাপাচি 2 লাইসেন্সকৃত কারণের কোডটি অনলাইনে পাওয়া যায়। ALGENCAN (সুরক্ষার সাথে অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতির ফোরট্রান বাস্তবায়ন)। অনলাইনে পাওয়া যায়। এনএলওপিটি (অগমেন্টেড ল্যাগ্রাঞ্জিয়ান অপ্টিমাইজারের সি + + বাস্তবায়ন, বিভিন্ন প্রোগ্রামিং ভাষা থেকে অ্যাক্সেসযোগ্য) পাইপ্রক্সিমাল (অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতির পাইথন বাস্তবায়ন)। আরও দেখুন ব্যারিয়ার ফাংশন অভ্যন্তরীণ-বিন্দু পদ্ধতি ল্যাগ্রাঞ্জ গুণক পেনাল্টি পদ্ধতি রেফারেন্স গ্রন্থপঞ্জি অপ্টিমাইজেশন অ্যালগরিদম এবং পদ্ধতি