সেরা-অনুকূলকরণ (গণিত)

উইকিপিডিয়া, মুক্ত বিশ্বকোষ থেকে

গণিতে, কম্পিউটার বিজ্ঞানে এবং অর্থনীতিতে সেরা-অনুকূলকরণ (optimization) বা গাণিতিক প্রোগ্রামিং (mathematical programming) বলতে একটি সেটে বিদ্যমান অনেকগুলো বিকল্প থেকে সবচেয়ে অনুকূলটি বা সেরাটি বেছে নেয়া বোঝায়।

খুব সাধারণক্ষেত্রে এটা সেই ধরনের সমস্যা নিয়ে গবেষণা বোঝায় যেখানে একটি নির্দিষ্ট সেট থেকে কোন বাস্তব বা পূর্ণসংখ্যা চলকের মান নিয়মতান্ত্রিকভাবে পছন্দ করার মাধ্যমে কোন বাস্তব ফাংশনের সর্বোচ্চ বা সর্বনিম্ন মান বের করার চেষ্টা করা হয়।

ইতিহাস[সম্পাদনা]

সেরা-অনুকূলকরণ ব্যবহারের প্রথম কৌশল হল গাউসের ঢালুতম-অবতরণ পদ্ধতি। ঐতিহাসিকভাবে সেরা-অনুকূলকরণের গবেষণার অনেকটাই রৈখিক প্রোগ্রামিংয়ের (linear programming) গবেষণার সাথে জড়িত ছিল। ১৯৪৭-এ জর্জ ডানৎসিখের সিম্প্লেক্স অ্যালগরিদম রৈখিক প্রোগ্রামিং গবেষণার একটি মাইলফলক ধরা হয়।

নিচে সেরা-অনুকূলকরণ গবেষণার গুরুত্বপূর্ণ গণিতবিদদের তালিকা দেয়া হলঃ

প্রধান শাখাক্ষেত্রসমূহ[সম্পাদনা]

  • উত্তল প্রোগ্রামিংয়ের (বা উত্তল সেরা-অনুকূলকরণ) (convex programming) গবেষণার বিষয় হল উত্তল লক্ষ্য ফাংশন, যার সীমাবদ্ধতাগুলো (constraint) উত্তল সেট তৈরি করে। উত্তল প্রোগ্রামিংকে অরৈখিক প্রোগ্রামিংয়ের (nonlinear programming) একটি বিশেষ শাখা হিসেবে এবং রৈখিক সমস্যা এবং উত্তল দ্বিঘাত প্রোগ্রামিংয়ের (convex quadratic programming) সাধারণ শাখা হিসেবে দেখা যায়।
    • রৈখিক প্রোগ্রামিং হচ্ছে একধরনের উত্তল সমস্যা যেখানে লক্ষ্য ফাংশন রৈখিক হয় এবং সীমাবদ্ধতাগুলোর সেটকে কেবল রৈখিক সমতা বা অসমতা দ্বারা প্রকাশ করা হয়। এই সেট সীমিত হলে বহুতলকের (polyhedron) আকার ধারণ করে।
    • দ্বিতীয় ক্রমের কোণক প্রোগ্রামিংয়ে (second order cone programming) বিশেষ ধরনের দ্বিঘাত সমস্যা আলোচনা করা হয়।
    • প্রায়নির্ধারিত প্রোগ্রামিং (semidefinite programming) হচ্ছে উত্তল প্রোগ্রামিংয়ের একটি শাখা যেখানে চলকগুলো হল প্রায়নির্ধারিত ম্যাট্রিক্স
    • কোণক প্রোগ্রামিং (conic programming) হচ্ছে উত্তল প্রোগ্রামিংয়ের একটি সাধারণ শাখা। রৈখিক, দ্বিতীয় ক্রমের কোণক এবং প্রায়নির্ধারিত প্রোগ্রামিংয়ের প্রত্যেকটিকেই কোণক প্রোগ্রামিংয়ের বিশেষ ধরনের কোণকযুক্ত কোণক প্রোগ্রামিং হিসেবে দেখা যায়।
    • জ্যামিতিক প্রোগ্রামিং হচ্ছে একধরনের সেরা-অনুকূলকরণ কৌশল, যেখানে লক্ষ্য এবং অসমতা ফাংশনগুলো পসিনমিয়াল (posynomial) এবং সমতা ফাংশনগুলো মনমিয়াল (monomial)। জ্যামিতিক প্রোগ্রামিংকে উত্তল প্রোগ্রামিং আকারে সমাধান করা না হলেও উত্তল প্রোগ্রামিং সমস্যায় রূপান্তর করা যায়।
  • পূর্ণসংখ্যা প্রোগ্রামিং হচ্ছে এক ধরনের রৈখিক প্রোগ্রামিং যেখানে কিছু অথবা সবগুলো চলক কেবল পূর্ণসংখ্যায় মান গ্রহণ করে। এর ফলে সমস্যাটি আর উত্তল প্রোগ্রামিং থাকে না। সাধারণ রৈখিক প্রোগ্রামিংয়ের চেয়ে এটি সাধারণত বেশ কঠিন সমস্যা।
  • দ্বিঘাত প্রোগ্রামিংয়ে (quadratic programming) লক্ষ্য ফাংশন হয় দ্বিঘাতবিশিষ্ট এবং সমতা ও অসমতাগুলো হয় রৈখিক। দ্বিঘাত পদটির বিশেষ একটি আকারের ক্ষেত্রে সমস্যাটি একটি উত্তল প্রোগ্রামিং সমস্যায় পরিণত হয়।
  • অরৈখিক প্রোগ্রামিংয়ের গবেষণায় সেধরনের সমস্যা নিয়ে আলোচনা হয় যেখানে লক্ষ্য ফাংশন বা সীমাবদ্ধতা অথবা উভয়েই অরৈখিক অংশ থাকে।
  • অনির্ধারিত প্রোগ্রামিং (stochastic programming) গবেষণায় সে ধরনের সমস্যা বিবেচনা করা হয়, যেখানে সীমাবদ্ধতা বা প্যারামিটারগুলো দৈব চলকের উপর নির্ভর করে।
  • রোবাস্ট প্রোগ্রামিং অনির্ধারিত প্রোগ্রামিংয়ের মতই সেরা-অনকূলকরণ সমস্যার সাথে জড়িত উপাত্তের অনিশ্চয়তাকে নিয়ে কাজ করে। তবে এ কাজের জন্যে দৈব চলক বিবেচনা না করে উপাত্তের ত্রুটিকে বিবেচনায় নিয়ে সমস্যার সমাধান করা হয়।
  • কম্বিনেটোরিয়াল সেরাঅনুকুলকরণ is concerned with problems where the set of feasible solutions is discrete or can be reduced to a discrete one.
  • অসীমমাত্রিক সেরাঅনুকুলকরণ (infinite-dimensional optimization) studies the case when the set of feasible solutions is a subset of an infinite-dimensional space, such as a space of functions.
  • অধি-আবিষ্করণী (Metaheuristic) গবেষণায় সমস্যার ব্যাপারে যৎসামান্য অনুমান তৈরি করা হয় এবং এ ধরনের কৌশল সমাধান-ক্ষেত্রের বিশাল অঞ্চলে অনুসন্ধান চালাতে পারে। তবে অধি-আবিষ্করণী পদ্ধতি সেরা সমাধানের নিশ্চয়তা প্রদান করে না।

make few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions. However, metaheuristics do not guarantee an optimal solution is ever found.

In a number of subfields, the techniques are designed primarily for optimization in dynamic contexts (that is, decision making over time):

Multi-objective optimization[সম্পাদনা]

মূল নিবন্ধ: Multiobjective optimization

Adding more than one objective to an optimization problem adds complexity. For example, if you wanted to optimize a structural design, you would want a design that is both light and rigid. Because these two objectives conflict, a trade-off exists. There will be one lightest design, one stiffest design, and an infinite number of designs that are some compromise of weight and stiffness. This set of trade-off designs is known as a Pareto set. The curve created plotting weight against stiffness of the best designs is known as the Pareto frontier.

A design is judged to be Pareto optimal if it is not dominated by other designs: a Pareto optimal design must be better than another design in at least one aspect. If it is worse than another design in all respects, then it is dominated and is not Pareto optimal.

Multi-modal optimization[সম্পাদনা]

Optimization problems are often multi-modal, that is they possess multiple good solutions. They could all be globally good (same cost function value) or there could be a mix of globally good and locally good solutions. Obtaining all (or at least some of) the multiple solutions is the goal of a multi-modal optimizer.

Classical optimization techniques due to their iterative approach do not perform satisfactorily when they are used to obtain multiple solutions, since it is not guaranteed that different solutions will be obtained even with different starting points in multiple runs of the algorithm. Evolutionary Algorithms are however a very popular approach to obtain multiple solutions in a multi-modal optimization task. See Evolutionary multi-modal optimization.

গাণিতিক ধারণা[সম্পাদনা]

সমস্যাটিকে নিচের উপায়ে লেখা যায়

প্রদত্ত: একটি ফাংশন f : A R সেট A থেকে বাস্তব সংখ্যা-র সেট
নির্ণেয়: A-র একটি উপাদান x0 যেন A-র সমস্ত x-এর জন্য f(x0) ≤ f(x) হয় ("সর্বনিম্নকরণ"); অথবা A-র সমস্ত x-এর জন্য f(x0) ≥ f(x) ("সর্বোচ্চকরণ")।