Optimization problem

In mathematics, engineering, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions.

Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete:

• An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.
• A problem with continuous variables is known as a continuous optimization, in which an optimal value from a continuous function must be found. They can include constrained problems and multimodal problems.

In the context of an optimization problem, the search space refers to the set of all possible points or solutions that satisfy the problem's constraints, targets, or goals.^[1] These points represent the feasible solutions that can be evaluated to find the optimal solution according to the objective function. The search space is often defined by the domain of the function being optimized, encompassing all valid inputs that meet the problem's requirements.^[2]

The search space can vary significantly in size and complexity depending on the problem. For example, in a continuous optimization problem, the search space might be a multidimensional real-valued domain defined by bounds or constraints. In a discrete optimization problem, such as combinatorial optimization, the search space could consist of a finite set of permutations, combinations, or configurations.

In some contexts, the term search space may also refer to the optimization of the domain itself, such as determining the most appropriate set of variables or parameters to define the problem. Understanding and effectively navigating the search space is crucial for designing efficient algorithms, as it directly influences the computational complexity and the likelihood of finding an optimal solution.

The standard form of a continuous optimization problem is^[3]$${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p\end{aligned}}}$$ where

• f  : ℝ ⁿ → ℝ هي دالة الهدف التي يجب تقليلها على المتجه x ذي n متغير،
• تُسمى القيود g _i ( x ) ≤ 0 قيودًا غير متباينة
• تُسمى القيود h _j ( x ) = 0 قيود المساواة ، و
• m ≥ 0 و p ≥ 0 .

إذا كانت m = p = 0 ، فإن المسألة تُعدّ مسألة تحسين غير مقيدة. وبحسب الاصطلاح، يُعرّف الشكل القياسي مسألة تصغير . ويمكن معالجة مسألة التعظيم بنفي دالة الهدف.

بصورة رسمية، تُعتبر مسألة التحسين التوافقي A رباعية ( I ، f ، m ، g ) ، حيث

• I عبارة عن مجموعة من الحالات؛
• بالنظر إلى مثال x ∈ I ، فإن f ( x ) هي مجموعة الحلول الممكنة؛
• بالنظر إلى مثال x وحل ممكن y لـ x ، فإن m ( x , y ) يشير إلى مقياس y ، وهو عادة ما يكون عددًا حقيقيًا موجبًا .
• g هي دالة الهدف، وهي إما قيمة دنيا أو قيمة عظمى .

الهدف إذن هو إيجاد حل أمثل لبعض الحالات x ، أي حل ممكن y مع $${\displaystyle m(x,y)=g\left\{m(x,y'):y'\in f(x)\right\}.}$$

لكل مسألة تحسين توافقي، توجد مسألة قرار مقابلة تسأل عما إذا كان هناك حل ممكن لمقياس معين m _{≥ 0.} على سبيل المثال، إذا كان لدينا رسم بياني G يحتوي على الرأسين u و v ، فقد تكون مسألة التحسين هي "إيجاد مسار من u إلى v يستخدم أقل عدد ممكن من الحواف". قد تكون إجابة هذه المسألة، على سبيل المثال، 4. أما مسألة القرار المقابلة فهي "هل يوجد مسار من u إلى v يستخدم 10 حواف أو أقل؟" ويمكن الإجابة على هذه المسألة ببساطة بـ "نعم" أو "لا".

في مجال خوارزميات التقريب ، تُصمَّم الخوارزميات لإيجاد حلول شبه مثالية للمسائل المعقدة. ولذلك، فإن صيغة القرار المعتادة تُعدّ تعريفًا غير كافٍ للمسألة، لأنها تُحدِّد فقط الحلول المقبولة. مع أنه يُمكننا طرح مسائل قرار مناسبة، إلا أن المسألة تُصنَّف بشكل طبيعي أكثر على أنها مسألة تحسين. ^{[ 4 ]}

• مشكلة العد (التعقيد) – نوع من أنواع المشاكل الحسابية 
• تحسين التصميم
• مبدأ إيكيلاند التبايني
• مشكلة الدوال – نوع من أنواع المسائل الحسابية 
• مشكلة القفاز – مشكلة تحسين في بحوث العمليات 
• بحوث العمليات – تخصص يتعلق بتطبيق الأساليب التحليلية المتقدمة 
• الاكتفاء – أسلوب استدلالي معرفي للبحث عن قرار مقبول – لا يلزم إيجاد الحل الأمثل، بل يكفي إيجاد حل "جيد بما فيه الكفاية". 
• مشكلة البحث – فئة من المشكلات الحسابية 
• البرمجة شبه اللانهائية

• "كيف يُحسّن تشكيل حركة البيانات عرض النطاق الترددي للشبكة" . IPC . 12 يوليو 2016. تم الاطلاع عليه بتاريخ 13 فبراير 2017 .