গাণিতিক কাম্যতমকরণ
গণিতে, কম্পিউটার বিজ্ঞানে এবং অর্থশাস্ত্রে কাম্যতমকরণ (optimization) বা গাণিতিক প্রোগ্রামিং (mathematical programming) বলতে একটি সেটে বিদ্যমান অনেকগুলো বিকল্প থেকে কাম্যতম বা সর্বোচ্চ সন্তুষ্টিবিধায়ক বিকল্পটি বেছে নেয়াকে বোঝায়।
সাধারণত এটি দিয়ে এমন সব সমস্যা নিয়ে গবেষণা বোঝায়, যেখানে একটি নির্দিষ্ট সেট থেকে কোন বাস্তব বা পূর্ণসংখ্যা চলকের মান প্রণালীবদ্ধভাবে পছন্দ করার মাধ্যমে কোন বাস্তব ফাংশনের সর্বোচ্চ বা সর্বনিম্ন মান বের করার চেষ্টা করা হয়।
ইতিহাস
কাম্যতমকরণের প্রথম কৌশল হল গাউসের ঢালুতম-অবতরণ পদ্ধতি। ঐতিহাসিকভাবে কাম্যতমকরণের গবেষণার অনেকটাই রৈখিক বিশ্লেষণ তথা রৈখিক প্রোগ্রামিংয়ের (linear programming) গবেষণার সাথে জড়িত ছিল। ১৯৪৭-এ জর্জ ডানৎসিখের সিম্প্লেক্স অ্যালগরিদম রৈখিক প্রোগ্রামিং গবেষণার একটি মাইলফলক ধরা হয়।
নিচে কাম্যতমকরণ গবেষণার গুরুত্বপূর্ণ গণিতবিদদের একটি নির্বাচিত তালিকা দেয়া হল: টেমপ্লেট:Col-begin টেমপ্লেট:Col-2
- রিচার্ড বেলম্যান
- রোনাল্ড এ. হাওয়ার্ড
- Leonid Kantorovich
- নরেন্দ্র কর্মকার
- William Karush
- লিওনিদ খাচিয়ান
- Bernard Koopman
- Harold Kuhn
- Joseph Louis Lagrange
- লাসলো লোভাশ
- Arkadii Nemirovskii
- Yurii Nesterov
- জন ভন নিউম্যান
- Boris Polyak
- Lev Pontryagin
- James Renegar
- R. Tyrrell Rockafellar
- Cornelis Roos
- Naum Z. Shor
- Michael J. Todd
- Albert Tucker
প্রধান শাখাক্ষেত্রসমূহ
- উত্তল প্রোগ্রামিংয়ের (বা উত্তল কাম্যতমকরণ) (convex programming) গবেষণার বিষয় হল উত্তল লক্ষ্য ফাংশন, যার সীমাবদ্ধতাগুলো (constraint) উত্তল সেট তৈরি করে। উত্তল প্রোগ্রামিংকে অরৈখিক প্রোগ্রামিংয়ের (nonlinear programming) একটি বিশেষ শাখা হিসেবে এবং রৈখিক সমস্যা এবং উত্তল দ্বিঘাত প্রোগ্রামিংয়ের (convex quadratic programming) সাধারণ শাখা হিসেবে দেখা যায়।
- রৈখিক প্রোগ্রামিং হচ্ছে একধরনের উত্তল সমস্যা যেখানে লক্ষ্য ফাংশন রৈখিক হয় এবং সীমাবদ্ধতাগুলোর সেটকে কেবল রৈখিক সমতা বা অসমতা দ্বারা প্রকাশ করা হয়। এই সেট সীমিত হলে বহুতলকের (polyhedron) আকার ধারণ করে।
- দ্বিতীয় ক্রমের কোণক প্রোগ্রামিংয়ে (second order cone programming) বিশেষ ধরনের দ্বিঘাত সমস্যা আলোচনা করা হয়।
- প্রায়নির্ধারিত প্রোগ্রামিং (semidefinite programming) হচ্ছে উত্তল প্রোগ্রামিংয়ের একটি শাখা যেখানে চলকগুলো হল প্রায়নির্ধারিত ম্যাট্রিক্স।
- কোণক প্রোগ্রামিং (conic programming) হচ্ছে উত্তল প্রোগ্রামিংয়ের একটি সাধারণ শাখা। রৈখিক, দ্বিতীয় ক্রমের কোণক এবং প্রায়নির্ধারিত প্রোগ্রামিংয়ের প্রত্যেকটিকেই কোণক প্রোগ্রামিংয়ের বিশেষ ধরনের কোণকযুক্ত কোণক প্রোগ্রামিং হিসেবে দেখা যায়।
- জ্যামিতিক প্রোগ্রামিং হচ্ছে একধরনের কাম্যতমকরণ কৌশল, যেখানে লক্ষ্য এবং অসমতা ফাংশনগুলো পসিনমিয়াল (posynomial) এবং সমতা ফাংশনগুলো মনমিয়াল (monomial)। জ্যামিতিক প্রোগ্রামিংকে উত্তল প্রোগ্রামিং আকারে সমাধান করা না হলেও উত্তল প্রোগ্রামিং সমস্যায় রূপান্তর করা যায়।
- পূর্ণসংখ্যা প্রোগ্রামিং হচ্ছে এক ধরনের রৈখিক প্রোগ্রামিং যেখানে কিছু অথবা সবগুলো চলক কেবল পূর্ণসংখ্যায় মান গ্রহণ করে। এর ফলে সমস্যাটি আর উত্তল প্রোগ্রামিং থাকে না। সাধারণ রৈখিক প্রোগ্রামিংয়ের চেয়ে এটি সাধারণত বেশ কঠিন সমস্যা।
- দ্বিঘাত প্রোগ্রামিংয়ে (quadratic programming) লক্ষ্য ফাংশন হয় দ্বিঘাতবিশিষ্ট এবং সমতা ও অসমতাগুলো হয় রৈখিক। দ্বিঘাত পদটির বিশেষ একটি আকারের ক্ষেত্রে সমস্যাটি একটি উত্তল প্রোগ্রামিং সমস্যায় পরিণত হয়।
- অরৈখিক প্রোগ্রামিংয়ের গবেষণায় সেধরনের সমস্যা নিয়ে আলোচনা হয় যেখানে লক্ষ্য ফাংশন বা সীমাবদ্ধতা অথবা উভয়েই অরৈখিক অংশ থাকে।
- অনির্ধারিত প্রোগ্রামিং (stochastic programming) গবেষণায় সে ধরনের সমস্যা বিবেচনা করা হয়, যেখানে সীমাবদ্ধতা বা প্যারামিটারগুলো দৈব চলকের উপর নির্ভর করে।
- রোবাস্ট প্রোগ্রামিং অনির্ধারিত প্রোগ্রামিংয়ের মতই কাম্যতমকরণ সমস্যার সাথে জড়িত উপাত্তের অনিশ্চয়তাকে নিয়ে কাজ করে। তবে এ কাজের জন্যে দৈব চলক বিবেচনা না করে উপাত্তের ত্রুটিকে বিবেচনায় নিয়ে সমস্যার সমাধান করা হয়।
- কম্বিনেটোরিয়াল সেরাঅনুকুলকরণ
- অসীমমাত্রিক সেরাঅনুকুলকরণ
- অধি-আবিষ্করণী (Metaheuristic) গবেষণায় সমস্যার ব্যাপারে যৎসামান্য অনুমান তৈরি করা হয় এবং এ ধরনের কৌশল সমাধান-ক্ষেত্রের বিশাল অঞ্চলে অনুসন্ধান চালাতে পারে। তবে অধি-আবিষ্করণী পদ্ধতি সেরা সমাধানের নিশ্চয়তা প্রদান করে না।
গাণিতিক ধারণা
সমস্যাটিকে নিচের উপায়ে লেখা যায়
- প্রদত্ত: একটি ফাংশন f : A R সেট A থেকে বাস্তব সংখ্যা-র সেট
- নির্ণেয়: A-র একটি উপাদান x0 যেন A-র সমস্ত x-এর জন্য f(x0) ≤ f(x) হয় ("সর্বনিম্নকরণ"); অথবা A-র সমস্ত x-এর জন্য f(x0) ≥ f(x) ("সর্বোচ্চকরণ")।