Sum-of-squares optimization
একটি সাম-অফ-স্কোয়ার অপ্টিমাইজেশন প্রোগ্রাম একটি রৈখিক ব্যয় ফাংশন এবং সিদ্ধান্তের ভেরিয়েবলের উপর একটি নির্দিষ্ট ধরনের সীমাবদ্ধতার সাথে একটি অপ্টিমাইজেশন সমস্যা। এই সীমাবদ্ধতাগুলি এমন যে যখন সিদ্ধান্তের চলকগুলি নির্দিষ্ট পলিনোমিয়ালগুলিতে সহগ হিসাবে ব্যবহৃত হয়, তখন সেই পলিনোমিয়ালগুলির পলিনোমিয়াল এস. ও. এস বৈশিষ্ট্য থাকা উচিত। জড়িত বহুপদীগুলির সর্বাধিক মাত্রা নির্ধারণ করার সময়, সমষ্টি-বর্গ অপ্টিমাইজেশান সেমিডিফাইনাইট প্রোগ্রামিং-এ শিথিলকরণের ল্যাসেরে শ্রেণিবিন্যাস হিসাবেও পরিচিত। কন্ট্রোল থিওরি (বিশেষত, পলিনোমিয়াল ভেক্টর ক্ষেত্র দ্বারা বর্ণিত গতিশীল সিস্টেমের জন্য পলিনোমিয়াল লাইয়াপুনভ ফাংশন অনুসন্ধানের জন্য), পরিসংখ্যান, অর্থ এবং মেশিন লার্নিং সহ বিভিন্ন ক্ষেত্রে সাম-অফ-স্কোয়ার অপ্টিমাইজেশন কৌশল প্রয়োগ করা হয়েছে। "স্কোয়ার প্রোগ্রামিংয়ের সমষ্টি ব্যবহার করে নিয়ন্ত্রণ লিয়াপুনভ ফাংশনগুলির জন্য অনুসন্ধান করা হচ্ছে।" মধ্যেঃ অ্যালার্টন কনফ। কমিউনিকেশন, কন্ট্রোল অ্যান্ড কম্পিউটিং। পিপি। 210-219. </রেফ> এ। চক্রবর্তী, পি. সিলার এবং জি. বালাস, "ফলিং-লিফ মোডে এফ/এ-18 ফ্লাইট কন্ট্রোলারদের সংবেদনশীলতাঃ অরৈখিক বিশ্লেষণ", এ. আই. এ. এ জার্নাল অফ গাইডেন্স, কন্ট্রোল অ্যান্ড ডায়নামিক্স, খণ্ড। 34 নং। 1 (2011), পৃ. 73-85। অপ্টিমাইজেশান সমস্যা একটি ভেক্টর এবং পলিনোমিয়ালের জন্য, একটি সমষ্টি-বর্গ অপ্টিমাইজেশান সমস্যা হিসাবে লেখা হয় এখানে "এস. ও. এস" সমষ্টি-বর্গ (এস. ও. এস) পলিনোমিয়ালের শ্রেণীকে উপস্থাপন করে। পরিমাণগুলি হল সিদ্ধান্তের পরিবর্তনশীল। এস. ও. এস প্রোগ্রামগুলিকে এস. ও. এস পলিনোমিয়াল প্রোগ্রামের দ্বৈততা এবং পজিটিভ-সেমিডিফাইনাইট ম্যাট্রিক্স ব্যবহার করে সীমাবদ্ধ পলিনোমিয়াল অপ্টিমাইজেশনের জন্য একটি শিথিলতা ব্যবহার করে সেমিডিফাইনাইট প্রোগ্রামে (এস. ডি. পি) রূপান্তরিত করা যেতে পারে, নিম্নলিখিত বিভাগটি দেখুন। দ্বৈত সমস্যাঃ সীমাবদ্ধ পলিনোমিয়াল অপ্টিমাইজেশন ধরুন আমাদের একটি-ভেরিয়েট পলিনোমিয়াল আছে, এবং ধরুন আমরা একটি উপসেটে এই পলিনোমিয়ালটিকে হ্রাস করতে চাই। উপরন্তু মনে করুন যে উপসেটটির সীমাবদ্ধতাগুলি সর্বাধিক ডিগ্রির বহুপদী সমতা ব্যবহার করে এনকোড করা যেতে পারে, প্রতিটি ফর্ম যেখানে সর্বাধিক ডিগ্রির একটি বহুপদী। এই অপ্টিমাইজেশান সমস্যার জন্য একটি স্বাভাবিক, যদিও সাধারণত নন-কনভেক্স প্রোগ্রাম নিম্নরূপঃ সর্বাধিক মাত্রায় প্রতিটি মনোমিয়ালের জন্য একটি এন্ট্রি সহ-মাত্রিক ভেক্টর কোথায়, যাতে প্রতিটি মাল্টিসেটের জন্য, পলিনোমিয়ালের সহগের একটি ম্যাট্রিক্স যা আমরা হ্রাস করতে চাই, এবং এটি পলিনোমিয়ালের সহগের একটি ম্যাট্রিক্স যা উপসেটে-তম সীমাবদ্ধতা এনকোডিং করে। আমাদের সার্চ স্পেসে অতিরিক্ত, স্থির ধ্রুবক সূচক, বহুপদী লেখার সুবিধার জন্য এবং একটি ম্যাট্রিক্স উপস্থাপনায় যোগ করা হয়। এই প্রোগ্রামটি সাধারণত অ-উত্তল, কারণ সীমাবদ্ধতাগুলি () উত্তল নয়। এই মিনিমাইজেশন সমস্যার জন্য একটি সম্ভাব্য উত্তল শিথিলকরণ একটি পজিটিভ-সেমিডিফাইনাইট ম্যাট্রিক্সের সাথে ভেরিয়েবলের র্যাঙ্ক-ওয়ান ম্যাট্রিক্স প্রতিস্থাপন করতে সেমিডিফাইনাইট প্রোগ্রামিং ব্যবহার করেঃ আমরা বেশিরভাগ সূচকের মাল্টিসেট দ্বারা সর্বাধিক আকারের প্রতিটি মনোমিয়ালকে সূচীভুক্ত করি। এই ধরনের প্রতিটি মনোমিয়ালের জন্য, আমরা প্রোগ্রামে একটি পরিবর্তনশীল তৈরি করি, এবং আমরা ম্যাট্রিক্স গঠনের জন্য পরিবর্তনশীলগুলিকে সাজাই, যেখানে বাস্তব ম্যাট্রিক্সের সেট রয়েছে যার সারি এবং কলামগুলি সর্বাধিক আকারের উপাদানগুলির মাল্টিসেটের সাথে চিহ্নিত করা হয়। তারপরে আমরা ভেরিয়েবলগুলিতে নিম্নলিখিত সেমিডিফাইনাইট প্রোগ্রামটি লিখিঃ সাপেক্ষেঃ যেখানে আবার পলিনোমিয়ালের সহগের ম্যাট্রিক্স যা আমরা হ্রাস করতে চাই, এবং এটি পলিনোমিয়াল এনকোডিং-এর সহগের ম্যাট্রিক্স যা উপসেটে-তম সীমাবদ্ধতা। তৃতীয় সীমাবদ্ধতা নিশ্চিত করে যে ম্যাট্রিক্সের মধ্যে বেশ কয়েকবার প্রদর্শিত একটি মনোমিয়ালের মান ম্যাট্রিক্স জুড়ে সমান, এবং দ্বিঘাত আকারে উপস্থিত প্রতিসাম্যগুলির সম্মান করতে যোগ করা হয়। দ্বৈততা একজন উপরের সেমিডিফাইনাইট প্রোগ্রামের দ্বৈতটি নিতে পারে এবং নিম্নলিখিত প্রোগ্রামটি পেতে পারেঃ আমাদের সীমাবদ্ধতার সাথে সম্পর্কিত একটি পরিবর্তনশীল রয়েছে (যেখানে সমস্ত এন্ট্রি সহ ম্যাট্রিক্সটি দ্বারা সূচীভুক্ত এন্ট্রির জন্য শূন্য সংরক্ষণ করে), প্রতিটি বহুপদী সীমাবদ্ধতার জন্য একটি বাস্তব পরিবর্তনশীল এবং মাল্টিসেটের প্রতিটি গোষ্ঠীর জন্য, আমাদের প্রতিসাম্য সীমাবদ্ধতার জন্য একটি দ্বৈত পরিবর্তনশীল রয়েছে। ধনাত্মক-সমপরিমিত সীমাবদ্ধতার সীমাবদ্ধতা নিশ্চিত করে যে এটি বহুপদগুলির সমষ্টিঃ ধনাত্মক-সমপরিমিত ম্যাট্রিক্সের বৈশিষ্ট্য দ্বারা, যে কোনও ধনাত্মক-সমপরিমিত ম্যাট্রিক্সের জন্য, আমরা ভেক্টরের জন্য লিখতে পারি। এইভাবে যে কোনও ক্ষেত্রে, যেখানে আমরা সর্বাধিক মাত্রার একটি বহুপদের সহগগুলির সঙ্গে ভেক্টরগুলিকে চিহ্নিত করেছি। এটি একটি সমষ্টি-বর্গ প্রমাণ দেয় যে মানটি শেষ হয়ে গেছে। উপরের বিষয়গুলি বহুপদী বৈষম্য দ্বারা সংজ্ঞায়িত অঞ্চলগুলিতেও প্রসারিত করা যেতে পারে। সমষ্টি-বর্গ শ্রেণিবিন্যাস সমষ্টি-বর্গ শ্রেণিবিন্যাস (এস. ও. এস. শ্রেণিবিন্যাস), যা ল্যাসেরে শ্রেণিবিন্যাস নামেও পরিচিত, হল ক্রমবর্ধমান শক্তি এবং ক্রমবর্ধমান গণনামূলক ব্যয়ের উত্তল শিথিলকরণের একটি শ্রেণিবিন্যাস। প্রতিটি প্রাকৃতিক সংখ্যার জন্য সংশ্লিষ্ট উত্তল শিথিলকরণ এস. ও. এস শ্রেণিবিন্যাসের তম স্তর বা-তম বৃত্ত হিসাবে পরিচিত। প্রথম রাউন্ড, যখন, একটি মৌলিক সেমিডিফাইনাইট প্রোগ্রামের সাথে মিলে যায়, বা সর্বাধিক মাত্রার বহুপদের উপর সমষ্টি-বর্গ অপ্টিমাইজেশনের সাথে মিলে যায়। শ্রেণিবিন্যাসের প্রথম স্তরে মৌলিক উত্তল প্রোগ্রামকে-তম স্তরে উন্নীত করার জন্য, প্রোগ্রামে অতিরিক্ত পরিবর্তনশীল এবং সীমাবদ্ধতাগুলি যুক্ত করা হয় যাতে প্রোগ্রামটি সর্বাধিক মাত্রার বহুপদ বিবেচনা করতে পারে। এস. ও. এস শ্রেণিবিন্যাসের নামটি এই সত্য থেকে এসেছে যে-তম স্তরে উদ্দেশ্যমূলক ফাংশনের মানটি দ্বৈতের মাধ্যমে সর্বাধিক মাত্রার বহুপদী ব্যবহার করে একটি সমষ্টি-বর্গ প্রমাণের সাথে আবদ্ধ (উপরে "দ্বৈততা" দেখুন)। ফলস্বরূপ, যে কোনও সমষ্টি-বর্গ প্রমাণ যা সর্বাধিক মাত্রার বহুপদী ব্যবহার করে তা বস্তুনিষ্ঠ মানকে আবদ্ধ করতে ব্যবহার করা যেতে পারে, যার ফলে কেউ শিথিলতার আঁটসাঁটতার নিশ্চয়তা প্রমাণ করতে পারে। বার্গের একটি উপপাদ্যের সাথে একত্রে, এটি আরও বোঝায় যে পর্যাপ্ত সংখ্যক রাউন্ড দেওয়া হলে, যে কোনও নির্দিষ্ট বিরতিতে শিথিলতা নির্বিচারে শক্ত হয়ে যায়। বার্গের ফলাফলে বলা হয়েছে যে, একটি সীমাবদ্ধ ব্যবধানের মধ্যে প্রতিটি অ-ঋণাত্মক বাস্তব বহুপদকে পর্যাপ্ত উচ্চ মাত্রার বাস্তব বহুপদগুলির সমষ্টি-বর্গ দিয়ে সেই ব্যবধানের নির্ভুলতার মধ্যে অনুমান করা যেতে পারে এবং এইভাবে যদি পলিনোমিয়াল অবজেক্টিভ মানটি বিন্দুর একটি ফাংশন হিসাবে হয়, যদি অসমতা আগ্রহের অঞ্চলে সকলের জন্য থাকে, তবে অবশ্যই এই সত্যের একটি সমষ্টি-বর্গ প্রমাণ থাকতে হবে। সম্ভাব্য অঞ্চলের উপর ন্যূনতম উদ্দেশ্যমূলক ফাংশন হিসাবে বেছে নেওয়ার ফলে আমাদের ফলাফল রয়েছে। গণনামূলক খরচ যখন চলকের মধ্যে একটি ফাংশনের উপর অনুকূলকরণ করা হয়, তখন শ্রেণিবিন্যাসের-তম স্তরটিকে চলকের উপর একটি সেমিডিফাইনাইট প্রোগ্রাম হিসাবে লেখা যেতে পারে এবং উপবৃত্তাকার পদ্ধতি ব্যবহার করে সময়মতো সমাধান করা যেতে পারে। সমষ্টি-বর্গ পটভূমি একটি বহুপদী হল বর্গের সমষ্টি (এস. ও. এস) যদি এমন বহুপদী থাকে। উদাহরণস্বরূপ, এটি বর্গের যোগফল যেখানে লক্ষ্য করুন যে যদি বর্গের যোগফল হয় তবে সকলের জন্য। বহুপদী এস. ও. এস-এর বিস্তারিত বিবরণ হল <আই. ডি1>, পি. (2003) "সেমি-বীজগাণিতিক সমস্যার জন্য সেমিডিফাইনাইট প্রোগ্রামিং শিথিলকরণ"। গাণিতিক প্রোগ্রামিং সার্। বি 96 (2), 293-320। চতুর্ভুজ রূপগুলি যেখানে একটি প্রতিসম ম্যাট্রিক্স হিসাবে প্রকাশ করা যেতে পারে। একইভাবে, ≤2d "মাত্রার বহুপদগুলিকে এমনভাবে প্রকাশ করা যেতে পারে যেখানে ভেক্টরটি মাত্রার সমস্ত একশব্দ ধারণ করে। এটি গ্রাম ম্যাট্রিক্স ফর্ম নামে পরিচিত। একটি গুরুত্বপূর্ণ বিষয় হল যে এস. ও. এস যদি এবং শুধুমাত্র যদি এমন একটি প্রতিসম এবং ধনাত্মক-সমপরিমিত ম্যাট্রিক্স বিদ্যমান থাকে। এটি এস. ও. এস পলিনোমিয়াল এবং পজিটিভ-সেমিডিফাইনাইট ম্যাট্রিক্সের মধ্যে একটি সংযোগ প্রদান করে। সফ্টওয়্যার সরঞ্জামগুলি জি. এন. ইউ. জি. পি. এল-এর অধীনে লাইসেন্সপ্রাপ্ত। রেফারেন্স গাইডটি arXiv: 1310.4716 [math.OC] এ পাওয়া যায় এবং এর অভ্যন্তরীণ বিষয়গুলি সম্পর্কে একটি উপস্থাপনা এখানে পাওয়া যায়। সি. ডি. সি. এস-এস. ও. এস, সি. ডি. সি. এস-এর একটি প্যাকেজ, একটি অগমেন্টেড ল্যাগ্রাঞ্জিয়ান পদ্ধতি সমাধানকারী, বড় আকারের এস. ও. এস প্রোগ্রামগুলির সাথে মোকাবিলা করার জন্য। জুলিয়ার জন্য জে. ইউ. এম. পি-এর সুম অফ স্কোয়ার সম্প্রসারণ। জুলিয়ার জন্য টি. এস. এস. ও. এস, স্পার্সিটি অভিযোজিত মুহূর্ত-এস. ও. এস শ্রেণিবিন্যাসের উপর ভিত্তি করে একটি বহুপদী অপ্টিমাইজেশান টুল। সীমাবদ্ধ বহুপদী অপ্টিমাইজেশনের দ্বৈত সমস্যার জন্য, ম্যাটল্যাব/অক্টেভের জন্য গ্লোপটিপলি, পাইথনের জন্য এনসিপোল2এসডিপিএ এবং জুলিয়ার জন্য মোমেন্টঅপ্ট। তথ্যসূত্র গাণিতিক অনুকূলকরণ বাস্তব বীজগাণিতিক জ্যামিতি