Hubbry Logo
Optimization problemOptimization problemMain
Open search
Optimization problem
Community hub
Optimization problem
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Optimization problem
Optimization problem
Optimization problem
View on Wikipedia
from Wikipedia

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:

Search space

[edit]

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.

Continuous optimization problem

[edit]

The standard form of a continuous optimization problem is[3] where

  • f : ℝn → ℝ is the objective function to be minimized over the n-variable vector x,
  • gi(x) ≤ 0 are called inequality constraints
  • hj(x) = 0 are called equality constraints, and
  • m ≥ 0 and p ≥ 0.

If m = p = 0, the problem is an unconstrained optimization problem. By convention, the standard form defines a minimization problem. A maximization problem can be treated by negating the objective function.

Combinatorial optimization problem

[edit]
Main article: Combinatorial optimization

Formally, a combinatorial optimization problem A is a quadruple[citation needed] (I, f, m, g), where

  • I is a set of instances;
  • given an instance x ∈ I, f(x) is the set of feasible solutions;
  • given an instance x and a feasible solution y of x, m(x, y) denotes the measure of y, which is usually a positive real.
  • g is the goal function, and is either min or max.

The goal is then to find for some instance x an optimal solution, that is, a feasible solution y with

For each combinatorial optimization problem, there is a corresponding decision problem that asks whether there is a feasible solution for some particular measure m0. For example, if there is a graph G which contains vertices u and v, an optimization problem might be "find a path from u to v that uses the fewest edges". This problem might have an answer of, say, 4. A corresponding decision problem would be "is there a path from u to v that uses 10 or fewer edges?" This problem can be answered with a simple 'yes' or 'no'.

In the field of approximation algorithms, algorithms are designed to find near-optimal solutions to hard problems. The usual decision version is then an inadequate definition of the problem since it only specifies acceptable solutions. Even though we could introduce suitable decision problems, the problem is more naturally characterized as an optimization problem.[4]

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Optimization problem

View on Grokipedia
from Grokipedia
An optimization problem, also referred to as a mathematical programming problem, is the task of selecting the best solution from a finite or infinite set of feasible alternatives, typically by minimizing or maximizing a specified objective function subject to given constraints. This process involves decision variables that represent the choices to be made, an objective function that quantifies the performance or cost of those choices, and constraints that define the allowable region for the variables, ensuring the solution remains practical and feasible. Optimization problems arise across diverse fields, from and to , where they enable efficient , design improvement, and under limitations. The core components of an optimization problem include the objective function, which is a mathematical expression (often linear or nonlinear) to be optimized; the decision variables, which are the unknowns adjusted to achieve optimality; and the constraints, which can be equality or inequality conditions bounding the variables. Problems are classified as constrained if restrictions apply or unconstrained if variables can take any value in their domain, with the latter often focusing on continuous real-valued functions. Maximization tasks can be reformulated as minimization by negating the objective function, a standard technique that unifies the framework. Optimization problems encompass several major types, including linear programming, where both the objective and constraints are linear, solvable via methods like the simplex algorithm developed by George Dantzig in 1947; nonlinear programming, addressing curved relationships; integer programming, restricting variables to whole numbers for discrete scenarios like scheduling; and convex optimization, which guarantees global optima for convex functions and includes applications in least-squares fitting. Discrete or combinatorial optimization deals with finite, often computationally challenging sets of options. These categories highlight the field's breadth, with convex problems being particularly tractable and widely used in engineering design and data analysis. Historically, systematic optimization emerged in the mid-20th century with linear programming's resolution in the late , but roots trace to earlier calculus-based methods for unconstrained problems. Today, optimization drives advancements in fields like network design, , and , where algorithms minimize errors in models or maximize efficiency in systems. Despite its power, many problems—especially nonconvex or large-scale ones—remain computationally intensive, spurring ongoing research into approximation techniques and specialized solvers.

Definition and Formulation

Basic Definition

In mathematics and engineering, an optimization problem is fundamentally a decision-making process that involves selecting inputs, known as decision variables, from a predefined set to extremize—either minimize or maximize—an objective function that quantifies the performance or desirability of those inputs. The objective function can be scalar, providing a single measure of outcome, or vector-valued in cases involving multiple conflicting goals. This formal approach contrasts with everyday usage of "optimization," where the term often describes informal efforts to improve efficiency in personal routines, business operations, or resource allocation without the structured analysis of mathematical models. Central to any optimization problem are the concepts of feasible solutions and optimal solutions. A feasible solution consists of values for the decision variables that satisfy all specified conditions, such as resource limits or operational requirements, forming the allowable domain from which selections are made. An optimal solution, in turn, is the feasible solution that yields the best possible value of the objective function, representing the "extremum" sought in the problem. The search space outlines the overall domain for these variables, while constraints delineate the subset of feasible options within it. The roots of optimization problems as a formal field trace back to the 1940s in , emerging from efforts to solve logistical challenges during and after , with George Dantzig's 1947 invention of the simplex method for marking a pivotal advancement in systematizing such problems. This conceptual framework establishes the abstract structure essential for exploring specific instances, such as those in various domains or under particular constraints, without delving into algorithmic resolutions.

Standard Formulation

An optimization problem is generally formulated as the task of finding a point xx in a set XX that minimizes (or maximizes) an objective function f:X→Rf: X \to \mathbb{R}. This standard structure encompasses both minimization and maximization problems, where maximization of ff is equivalent to minimization of −f-f. The objective function ff maps elements from the domain XX (often Rn\mathbb{R}^n) to numbers, representing the quantity to be optimized. In the multi-objective case, the objective is a F:X→RkF: X \to \mathbb{R}^k, where trade-offs between objectives are analyzed via the —the set of nondominated points where no feasible point improves all components of FF without worsening at least one. Constraints define the feasible set within XX and are classified as equality constraints hj(x)=0h_j(x) = 0 for j=1,…,pj = 1, \dots, p, inequality constraints gi(x)≤0g_i(x) \leq 0 for i=1,…,mi = 1, \dots, m, or simple bounds l≤x≤ul \leq x \leq u. The full standard formulation for a constrained minimization problem is thus min⁡x∈Xf(x)subject togi(x)≤0,i=1,…,m,hj(x)=0,j=1,…,p.\begin{align*} \min_{x \in X} \quad & f(x) \\ \text{subject to} \quad & g_i(x) \leq 0, \quad i = 1, \dots, m, \\ & h_j(x) = 0, \quad j = 1, \dots, p. \end{align*} Unconstrained problems arise as a special case when m=p=0m = p = 0, reducing to min⁡x∈Xf(x)\min_{x \in X} f(x). Solutions are denoted using arg⁡min⁡\arg\min or for the optimizing point(s), which may not exist if the infimum (or supremum) is not attained; in such cases, the optimal value is the infimum inf⁡x∈Xf(x)\inf_{x \in X} f(x) (or supremum sup⁡x∈Xf(x)\sup_{x \in X} f(x)).

Search Space

General Search Space

In an optimization problem, the search space, also referred to as the domain, is defined as the set XX comprising all possible values that the decision variables xx can assume. This set XX serves as the universal collection of candidate solutions over which the objective function is evaluated, independent of any specific constraints that might further restrict feasible choices. For instance, in , X=RnX = \mathbb{R}^n represents the nn-dimensional real , allowing decision variables to take any real-valued coordinates. In discrete settings, XX might be the Zn\mathbb{Z}^n or the binary {0,1}n\{0,1\}^n, where variables are restricted to or binary values, respectively. The properties of the search space significantly influence the nature of optimization. It can be bounded, such as when confined to a compact like a box [xmin⁡,xmax⁡]⊂Rn[x_{\min}, x_{\max}] \subset \mathbb{R}^n, or unbounded, as in the full Rn\mathbb{R}^n or Zn\mathbb{Z}^n. Connectivity varies: continuous spaces like Rn\mathbb{R}^n are path-connected, enabling smooth traversals, while discrete spaces like Zn\mathbb{Z}^n are disconnected, consisting of isolated points. Many search spaces possess a metric structure to quantify distances between points; for example, the Euclidean metric d(x,y)=∥x−y∥2d(x, y) = \|x - y\|_2 applies naturally in Rn\mathbb{R}^n, facilitating measures of proximity during exploration. The search space provides the foundational "universe" for optimization algorithms to explore potential solutions. Its size and complexity directly impact solvability: in high-dimensional settings, the of the space leads to the curse of dimensionality, where the volume increases dramatically with dimension nn, making exhaustive search computationally infeasible even for simple uniform sampling. This phenomenon, first articulated by Bellman, arises because the number of points needed to cover the space adequately scales exponentially, complicating convergence and increasing sensitivity to initial conditions. Examples of search spaces abound across problem types. Real vector spaces Rn\mathbb{R}^n are common in engineering design, where variables represent continuous parameters like material densities. lattices Zn\mathbb{Z}^n appear in scheduling tasks with whole-number allocations. More abstract sets include the space of all permutations of nn elements for problems like the traveling salesman, where solutions are orderings of cities, or the set of all subgraphs of a given graph for optimization, encompassing all connected acyclic subsets of edges. Distinguishing between infinite and finite search spaces has profound implications for solution methods. Finite spaces, such as the n!n! permutations in combinatorial problems, allow in principle for complete enumeration, though this is impractical for large nn due to exponential growth. Infinite spaces, like Rn\mathbb{R}^n, preclude enumeration entirely, necessitating approximation techniques or convergence guarantees based on the space's topology and metric properties.

Feasible Search Space

In optimization problems, the feasible set, also referred to as the , is the subset of the overall search space that consists of all points satisfying the given constraints. It is formally defined as the set {x∈X∣gi(x)≤0 ∀i=1,…,m, hj(x)=0 ∀j=1,…,p}\{ x \in X \mid g_i(x) \leq 0 \ \forall i = 1, \dots, m, \ h_j(x) = 0 \ \forall j = 1, \dots, p \}, where XX is the search space, gig_i represent inequality constraint functions, and hjh_j represent equality constraint functions. This set delineates the valid solutions, excluding any points that violate the problem's restrictions. The properties of the feasible set depend on the form of the constraints. If the inequality constraints gig_i are convex functions and the equality constraints hjh_j are affine, the feasible set is convex, meaning the between any two feasible points lies entirely within the set. Convexity ensures desirable geometric properties, such as the absence of local distinct from global ones in convex problems. The feasible set is compact if it is closed and bounded, guaranteeing the existence of optimal solutions for continuous objective functions over it, as per the . If the feasible set is empty, the problem is deemed infeasible, indicating no valid solution exists that meets all constraints simultaneously. Constraints shaping the feasible set are categorized as hard or soft. Hard constraints must be strictly satisfied, directly defining the boundaries of the feasible set, while soft constraints allow violations but incorporate penalties into the objective function to encourage compliance. They further divide into simple bounds, such as l≤x≤ul \leq x \leq u on individual variables, and general constraints involving nonlinear or multivariable relations. The feasible set plays a central role in optimization, as candidate solutions are evaluated for optimality solely within its confines; can arise at interior points or on the boundary. Detecting whether the feasible set is nonempty is a preliminary step in solving constrained problems; for instance, in , a conceptual Phase I approach introduces auxiliary variables to ascertain feasibility without optimizing the original objective. In settings with , such as parameter variations, robust feasibility extends the by requiring solutions to satisfy constraints across an entire uncertainty set, often via worst-case formulations to ensure reliability. This approach, prominent in , addresses real-world variability absent in deterministic models.

Continuous Optimization Problem

Definition and Features

Continuous optimization involves finding values for real-valued decision variables that minimize or maximize a continuous objective function, subject to constraints defining a , typically over real numbers in Rn\mathbb{R}^n. Unlike , the search space is infinite and continuous, allowing variables to take any value within their domain, often enabling the use of derivative-based methods for solution. Key features include the objective function f(x)f(x), which is often smooth (differentiable) and may be linear, quadratic, or nonlinear; equality or inequality constraints like ci(x)=0c_i(x) = 0 or ci(x)≥0c_i(x) \geq 0; and bounds on variables. Problems can be unconstrained (no restrictions beyond the domain) or constrained, with convex formulations—where the objective is convex and the feasible set is convex—guaranteeing global optima via local searches. Algorithms exploit gradients or Hessians for efficiency, contrasting with enumeration in discrete cases, and include interior-point methods for large-scale problems. Common subtypes are linear programming (linear functions), quadratic programming (quadratic objectives with linear constraints), and nonlinear programming (general smooth functions). Challenges arise in nonconvex problems, where multiple local optima exist, requiring techniques like branch-and-bound or heuristics. The field emphasizes scalability for high-dimensional applications, with regularization terms often added to prevent in data-driven contexts.

Common Examples

Continuous optimization problems often model real-world scenarios with smooth relationships, such as or parameter estimation. Least squares regression minimizes the sum of squared residuals min⁡x12m∥Ax−y∥22\min_x \frac{1}{2m} \|Ax - y\|_2^2 to fit a to data points (aj,yj)(a_j, y_j), widely used in and for . Ridge regression extends least squares by adding a penalty min⁡x12m∥Ax−y∥22+λ∥x∥22\min_x \frac{1}{2m} \|Ax - y\|_2^2 + \lambda \|x\|_2^2, where λ>0\lambda > 0 regularizes to handle in applications like predictive modeling. Portfolio optimization, as in Markowitz's mean-variance model, minimizes risk min⁡wwTΣw\min_w w^T \Sigma w subject to expected return constraints and wT1=1w^T 1 = 1, balancing return and volatility in . Support vector machines (SVM) solve min⁡x,β1m∑jmax⁡(1−yj(ajTx−β),0)+λ2∥x∥22\min_{x, \beta} \frac{1}{m} \sum_j \max(1 - y_j (a_j^T x - \beta), 0) + \frac{\lambda}{2} \|x\|_2^2 for , maximizing margins in tasks. Nonlinear examples include minimizing in design via aerodynamic simulations or optimizing control systems in , where objectives involve nonlinear dynamics.

Combinatorial Optimization Problem

Definition and Features

constitutes a subfield of focused on selecting the best element from a of discrete objects, where the feasible solutions correspond to structures such as subsets, permutations, or graphs. The search space XX is inherently finite and discrete, often comprising configurations that grow exponentially in with the problem size nn, such as ∣X∣=n!|X| = n! for permutations or 2n2^n for subsets. Many canonical problems in this domain, including the traveling salesman problem and , are NP-hard, implying that exact solutions cannot be guaranteed in polynomial time unless P=NP. Key features of combinatorial optimization include the absence of differentiability in the objective function, necessitating algorithms that avoid gradient-based methods and instead employ exact techniques like for small instances or branch-and-bound for structured problems. Approximations and heuristics, such as metaheuristics or relaxations, are commonly used for scalability, with integrality constraints implicitly enforced by the discrete domain rather than explicit continuous bounds. The field draws from , algorithms, and to navigate these challenges. Prominent subtypes encompass , where decision variables are constrained to integers x∈Znx \in \mathbb{Z}^n to model discrete choices; the set covering problem, which minimizes the number of selected sets to cover a ; and the matching problem, which maximizes pairings in a graph while avoiding shared vertices. These formulations highlight the reliance on finite enumerative structures, with the feasible set often representing discrete polyhedra that admit continuous relaxations for bounding purposes. Central challenges arise from the exponential growth of ∣X∣|X|, rendering exact solutions intractable for large nn, a difficulty underscored by the P versus NP implications for decision versions of these problems. Solution concepts center on identifying an optimal subset, permutation, or graph configuration that extremizes the objective, while for NP-hard cases, approximation algorithms guarantee solutions within a bounded ratio of optimality, such as the 2-approximation for vertex cover, a covering problem. Emerging quantum-inspired approaches, like the Quantum Approximate Optimization Algorithm (QAOA), leverage variational quantum circuits to approximate solutions for combinatorial instances on near-term quantum devices. Understanding these requires familiarity with basic combinatorics, including measures like binomial coefficients (nk)\binom{n}{k} to quantify search space scales.

Common Examples

Combinatorial optimization problems frequently arise in discrete settings where decisions involve selecting or arranging finite sets of elements. Classic examples illustrate the challenge of optimizing over combinatorial structures, such as permutations, subsets, or assignments, within finite search spaces. These problems are typically NP-hard, highlighting their computational complexity. The Traveling Salesman Problem (TSP) requires finding a minimum-cost Hamiltonian cycle in a complete graph, where the vertices represent cities and the edge weights denote travel distances or costs, such that each city is visited exactly once before returning to the starting point. The decision variables correspond to permutations of the cities, emphasizing the discrete nature of sequencing in a finite set of possible tours. This problem exemplifies routing challenges in logistics and manufacturing. The 0-1 involves selecting a of items, each with a value viv_i and weight wiw_i, to maximize the total value ∑vixi\sum v_i x_i subject to the capacity constraint ∑wixi≤W\sum w_i x_i \leq W, where xi∈{0,1}x_i \in \{0,1\} indicates whether item ii is included. The binary decisions reflect the combinatorial choice of packing resources without fractions, common in applications like and budgeting. Graph Coloring seeks the minimum number of colors needed to assign to the vertices of a graph such that no two adjacent vertices share the same color, with the decision space consisting of color assignments to vertices under adjacency constraints. This discrete captures scheduling and resource partitioning tasks, where the finite palette of colors limits feasible configurations. The Maximum Matching Problem in a aims to select the largest possible set of edges with no two edges sharing a vertex, often applied to assignment scenarios like pairing workers to tasks. The objective is to maximize the of the edge set, with the search space exploring subsets of edges that respect vertex disjointness in the discrete graph structure. The (VRP) generalizes TSP to multiple serving a set of from a depot, minimizing total travel cost while satisfying capacity and time constraints; variants include the capacitated VRP where loads are limited. In , post-2020 demand surges have amplified VRP's relevance for last-mile delivery, involving discrete route assignments across customer locations and fleets.

References

  1. https://www.sciencedirect.com/topics/computer-science/mathematical-optimization
  2. https://link.springer.com/chapter/10.1007/978-3-031-52459-2_1
  3. https://web.stanford.edu/group/sisl/k12/optimization/MO-unit1-pdfs/1.1optimization.pdf
  4. https://tutorial.math.lamar.edu/classes/calci/optimization.aspx
  5. https://people.math.carleton.ca/~kcheung/math/notes/MATH5801/01/1_3_lin_prog_def.html
  6. https://www.nku.edu/~longa/haiti/kids/optimization.html
  7. https://sites.math.washington.edu/~burke/crs/515/notes/nt_1.pdf
  8. https://www.uky.edu/~dsianita/300/online/LP.pdf
  9. https://docs.analytica.com/index.php/Optimization_Characteristics
  10. https://engineering.berkeley.edu/george-dantzig-operations-research-phenom/
  11. https://mathshistory.st-andrews.ac.uk/Biographies/Dantzig_George/
  12. https://sites.gatech.edu/omscs7641/2024/02/19/navigating-the-optimization-landscape-the-dos-and-donts-of-choosing-an-optimization-problem/
  13. https://mathematics.ucsd.edu/research/optimization
  14. https://www.ime.unicamp.br/~pulino/MT404/TextosOnline/NocedalJ.pdf
  15. https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
  16. https://liacs.leidenuniv.nl/~emmerichmtm/modapage/Reader/MCOReader-Chaper1%2B2.pdf
  17. https://personal.utdallas.edu/~dxd056000/cs6363/LectureNotes.pdf
  18. https://www.isye.gatech.edu/~sahmed/isye6669/notes/fund.pdf
  19. https://www.math.uci.edu/~qnie/Publications/NumericalOptimization.pdf
  20. https://www.cs.cornell.edu/selman/papers/pdf/maxsat.pdf
  21. https://web.mit.edu/15.053/www/AMP-Chapter-02.pdf
  22. https://arxiv.org/pdf/1501.02634
  23. https://pubsonline.informs.org/doi/pdf/10.1287/educ.1063.0022
  24. https://pages.cs.wisc.edu/~swright/papers/wright_continuous.pdf
  25. https://people.eecs.berkeley.edu/~brecht/opt4ml_book/O4MD_01_Introduction.pdf
  26. https://www.utdallas.edu/~dxd056000/cs6363/LectureNotes.pdf
  27. https://perso.limos.fr/~palafour/PAPERS/PDF/Garey-Johnson79.pdf
  28. http://www-math.mit.edu/~goemans/18433-FALL05.html
  29. https://www2.isye.gatech.edu/~wcook/papers/cobook_select.pdf
  30. https://ocw.mit.edu/courses/15-083j-integer-programming-and-combinatorial-optimization-fall-2009/
  31. https://optimization.cbe.cornell.edu/index.php?title=Set_covering_problem
  32. https://math.mit.edu/~goemans/18433S13/matching-notes.pdf
  33. https://arxiv.org/abs/1207.1794
  34. https://www.sciencedirect.com/science/article/pii/S0022000074800449
  35. https://www.cs.umd.edu/class/fall2018/cmsc858E/pdfs/651/vc.pdf
  36. https://arxiv.org/abs/1411.4028
  37. https://www.sciencedirect.com/science/article/pii/S0377221725004862
  38. http://web.ist.utl.pt/~ist11038/CD_Casquilho/TSP1992EJOR_Laporte.pdf
  39. https://www.researchgate.net/publication/220694474_Knapsack_Problems
  40. https://onlinelibrary.wiley.com/doi/book/10.1002/9781118032497
  41. https://pubsonline.informs.org/doi/10.1287/mnsc.6.1.80
  42. https://www.researchgate.net/publication/389263532_Optimized_Vehicle_Routing_Problem_for_The_Last_Mile_E-Commerce_Parcels_Delivery_Using_E-Cargo_Bikes
Add your contribution
Related Hubs
User Avatar
No comments yet.