1. Definition and Intuition

A feasible set is the collection of all points (decision variables) that satisfy a prescribed collection of constraints. When an optimization model specifies what actions are allowed, the feasible set represents the “allowed region” of the decision space; any candidate solution outside it violates at least one requirement.

1.1 Constraints and admissible points

Constraints are mathematical statements that restrict the decision variables. A point is admissible, or feasible, if every constraint is satisfied simultaneously. For example, a bound like \(x \ge 0\) rules out negative values, while an equation such as \(x+y=1\) restricts the pair \((x,y)\) to a specific relation.

1.2 Relation to optimization problems

In optimization, one typically chooses a point from the feasible set to optimize an objective function. The feasible set therefore determines which objective values are attainable and plays a major role in whether an optimum exists and how difficult it is to compute.

1.3 Feasibility and infeasibility concepts

If the feasible set is nonempty, the model is feasible, meaning at least one admissible solution exists. If it is empty, the model is infeasible and no solution can satisfy all constraints at once. In practice, infeasibility often indicates that the model’s requirements are mutually inconsistent or overly restrictive.

1.4 Geometry of allowed regions

The constraints induce a geometric region (or collection of regions) in the decision space. Inequalities often carve out half-spaces, while equalities reduce dimension by forcing variables to lie on a lower-dimensional surface. The resulting shape—flat, curved, disconnected, or intricate—reflects the structure of the constraints and strongly influences algorithm performance.

2. Mathematical Formulations

Feasible sets can be specified in many equivalent-looking ways: directly through inequalities and equalities, through standard optimization formalisms, or as the preimage of a mapping under a constraint function.

2.1 Explicit constraint descriptions

A common definition uses a list of constraint expressions and declares the feasible set to be all variable values that satisfy them.

2.1.1 Equalities, inequalities, and bounds

Constraints may include:

  • Equalities, such as \(g(x)=0\), requiring exact satisfaction.
  • Inequalities, such as \(h(x)\le 0\) or \(h(x)\ge 0\).
  • Simple bounds, such as \(l \le x \le u\), applying coordinate-wise limits.

Together these form a system whose simultaneous solutions define the feasible set.

2.1.2 Domains and variable restrictions

Often, constraints also describe where variables are allowed to live. Examples include requiring \(x\) to lie in a certain interval, restricting variables to integers, or imposing nonnegativity. These domain restrictions can be treated as additional constraints and incorporated into the feasible set definition.

2.2 Standard optimization representations

Optimization literature frequently uses a standardized syntax to describe models, but the feasible set remains the same conceptual object.

2.2.1 Formulating feasible sets from models

Given a model like “minimize \(f(x)\) subject to constraints \(c_i(x)\le 0\),” the feasible set is \[ \{x : c_i(x)\le 0 \text{ for all } i\} \] (and similarly for equalities and bounds). Many derivations then focus on properties of this set rather than on the objective.

2.2.2 Feasible set as an intersection of sets

If each constraint defines a subset of the decision space, the feasible region is the intersection of those subsets. This viewpoint is useful because it separates the role of each constraint: feasibility requires that all individual “allowed” sets overlap at the chosen point.

2.3 Preimages under mappings

Another formulation defines feasibility through a mapping and a set of acceptable outputs.

2.3.1 Feasible sets via constraint functions

Suppose there is a constraint function \(c(x)\) mapping decision variables to some space of constraint values, and a set \(C\) of acceptable constraint values. The feasible set can be written as a preimage: \[ \{x : c(x)\in C\}. \] This abstraction helps unify constraints that look different at the expression level but share the same underlying acceptance region in the constraint-value space.

3. Classification by Constraint Type

The shape and structure of feasible sets depend on what kinds of constraints are present. Classification is often based on algebraic form and on whether variables are continuous or discrete.

3.1 Linear feasible sets

When all constraints are linear (equalities and inequalities in variables with constant coefficients), the feasible set is a polyhedron; in bounded cases, it becomes a polytope.

3.1.1 Polyhedra and polytope feasibility regions

A linear inequality like \(a^\top x \le b\) defines a half-space. Intersecting finitely many half-spaces and equalities yields a polyhedron. If the resulting region is bounded, it is a polytope, a finite-volume “cornered” shape that can be described using vertices and faces.

3.2 Convex feasible sets

A feasible set is convex if any line segment joining two feasible points stays entirely inside the set. Convexity often allows efficient optimization and strong theoretical guarantees.

3.2.1 Convexity from inequality constraints

Convexity can arise when inequality constraints are convex functions in the standard sense: sets of the form \(\{x : h(x)\le 0\}\) with \(h\) convex. Intersections of convex sets are convex, so many models built from convex inequalities remain convex overall.

3.3 Nonconvex feasible sets

If the feasible region is not convex, the optimization landscape can include multiple disjoint pieces or “holes,” complicating both existence and computation of global optima.

3.3.1 Sources of nonconvexity

Nonconvexity can come from nonconvex constraints (e.g., constraints like \(x^2+y^2 \ge 1\) which create outside-of-a-ball regions), nonlinear equality constraints, or combinations that destroy convexity. Sometimes nonconvexity is introduced indirectly, such as through products of variables or absolute value expressions combined with additional restrictions.

3.4 Discrete and mixed-integer feasible sets

When variables are restricted to be discrete (commonly integers or binaries), the feasible set becomes a set of isolated points or a lattice-like subset. Many problems then become combinatorial.

3.4.1 Combinatorial feasibility regions

With mixed-integer structure, some variables are continuous and others are integer. The feasible set may look like a collection of polyhedra (one per integer assignment) stitched together across the discrete decisions. This structure often drives hardness: determining feasibility can require searching over many integer configurations.

4. Key Properties of Feasible Sets

Several geometric and topological properties affect both theoretical results and numerical behavior.

4.1 Closedness and boundary behavior

A set is closed if it contains its boundary limit points. For feasible sets defined by “\(\le\)” inequalities of continuous functions, the region is often closed, whereas “\(<\)” constraints typically yield open sets. Closedness matters because optima for continuous objectives frequently occur on boundaries.

4.2 Openness and limit points

Open feasible sets exclude boundary points. In optimization, an open constraint region can prevent attainment of an optimum even if objective values can approach the infimum. The distinction between strict and non-strict inequalities can therefore change whether a solution is actually reached.

4.3 Boundedness and unbounded feasible regions

A feasible set is bounded if all its points remain within some finite region of the decision space. Unbounded feasible regions can still have optima, but they can also allow objective values to diverge, depending on how the objective behaves far away.

4.4 Feasibility with empty sets

An empty feasible set indicates no admissible solution exists. Many algorithms detect infeasibility through certificates (in specific problem classes) or through iterative methods that demonstrate that no point can satisfy all constraints simultaneously.

4.5 Dimension and manifold structure

Feasible sets can have different effective dimensions. Equalities reduce dimension and may create manifolds (smooth surfaces) in the differentiable case. For example, a single nontrivial equality in \(\mathbb{R}^n\) typically reduces the feasible set dimension by one, while multiple independent equalities can reduce it further.

5. Feasible Set Operations and Transformations

Feasible sets can be combined, modified, and transformed while preserving or relating feasibility.

5.1 Intersections of constraints

Adding constraints corresponds to intersecting feasible regions. Because feasibility requires all constraints at once, the feasible set shrinks as more restrictions are imposed (or stays the same if new constraints are redundant).

5.2 Unions of feasible regions

Removing a constraint or allowing multiple alternative constraint systems may lead to a union of feasible regions. Unions often destroy convexity and may introduce disconnected components, which can influence algorithmic strategies.

5.3 Minkowski sums and scaling (set operations)

The Minkowski sum of sets \(A\) and \(B\) is \(A+B=\{a+b : a\in A, b\in B\}\). Such operations appear in robust optimization and in modeling combined effects of uncertain quantities. Scaling a feasible set by a factor changes bounds and can preserve convexity while altering size and location.

5.4 Projection and elimination of variables

Projection maps a higher-dimensional feasible set onto a lower-dimensional subspace by “forgetting” some variables. This is central in variable elimination and can be used to derive equivalent reduced constraints, though the resulting projected set may become more complex than the original.

5.5 Reformulations that preserve feasibility

Different algebraic reformulations can represent the same feasible set. Examples include introducing auxiliary variables with additional constraints, transforming between equivalent constraint representations, or rewriting constraints to match a solver’s standard input form. Preservation of feasibility means there is a one-to-one correspondence between feasible assignments in the original and reformulated models (possibly with different variable sets).

6. Existence, Optimality, and Feasibility Interplay

The feasibility structure determines whether optimization problems have meaningful solutions and how optima relate to boundaries.

6.1 Conditions for existence of optimal solutions

Existence of an optimum typically depends on both the feasible set properties and the objective function’s behavior. Common themes include having a nonempty feasible set, ensuring the objective does not decrease without limit, and often requiring some form of compactness (or coercivity) in continuous settings.

6.2 How feasibility affects attainable objective values

If feasibility is narrow, the objective may have only limited range. If the feasible set is empty, there is no attainable objective value corresponding to a feasible decision. If feasible points exist but only allow objective values approaching a limit, the infimum may be unattained.

6.3 Boundary solutions and constraint activity

Optimal solutions frequently lie on the boundary of the feasible set, especially when the objective encourages movement toward constraint limits. In such cases, certain constraints are “active” at the optimum, meaning they hold with equality (or, in inequality cases, at the threshold of satisfaction).

6.4 Slater-type conditions (conceptual role)

Some optimization frameworks use conditions ensuring the presence of strictly feasible points (points satisfying inequalities with slack). These assumptions, often called Slater-type conditions in convex optimization contexts, help guarantee strong duality and improved regularity, linking feasibility geometry to analytic conclusions.

6.5 Sensitivity to constraint perturbations

Small changes in constraints can alter feasibility dramatically, especially near the boundary between feasible and infeasible regions. Sensitivity analysis studies how optimal solutions and objective values vary when constraints are perturbed, providing guidance on modeling robustness and numerical stability.

7. Computational Aspects

Feasible sets influence algorithm design: checking feasibility, finding feasible points, and handling numerical issues all depend on the constraints’ structure.

7.1 Feasibility checking

Feasibility checking asks whether at least one feasible point exists.

7.1.1 Algorithms for satisfiability of constraints

For linear constraints, dedicated linear programming feasibility checks and related certificate methods are used. For convex constraints, feasibility may be addressed through convex programming tools. For nonconvex or mixed-integer constraints, methods range from branch-and-bound and cutting planes to heuristic searches and constraint propagation.

7.2 Finding a feasible point

Sometimes it is necessary not merely to decide feasibility but to construct an explicit admissible solution.

7.2.1 Initialization and repair strategies

Common approaches include:

  • Using a dedicated phase to search for feasibility before optimizing.
  • Projection or correction methods that iteratively move a candidate into the allowed region.
  • Repair heuristics in discrete settings that adjust invalid assignments into feasible ones with minimal changes.

7.3 Constraint qualification and numerical stability

Constraint qualification refers to regularity assumptions that ensure certain theoretical results apply and that algorithms behave predictably. In numerical practice, poorly conditioned constraints can cause instability, leading to slow convergence or inaccurate feasibility assessments.

7.4 Complexity considerations

The computational difficulty of feasibility depends on constraint type.

7.4.1 Hard vs. easier feasible-set structures

Linear feasibility can often be solved efficiently in polynomial-time frameworks, while general nonlinear nonconvex feasibility can be computationally hard. Mixed-integer feasibility inherits combinatorial complexity due to the discrete search space, though special structure (such as network flow patterns or sparse constraints) can make problems more tractable.

8. Examples and Toy Models (Applied Mathematics Context)

Illustrative models show how feasible sets appear in familiar optimization settings.

8.1 Feasible sets in linear programming

Linear programming constrains variables with linear equalities and inequalities, producing polyhedral feasible regions.

8.1.1 Simple half-space intersections

In two dimensions, constraints like \(x\ge 0\), \(y\ge 0\), and \(x+y\le 1\) define a triangular feasible region. Each inequality cuts the plane by a line, and the feasible set is the common overlap of the half-planes.

8.2 Feasible sets in quadratic or second-order settings

Quadratic inequalities and norm constraints generate curved feasible regions, often with convex structure.

8.2.1 Ellipsoids and norm constraints

A constraint such as \(\|Ax-b\|_2\le r\) defines an ellipsoid (after transformation by \(A\)). Such sets can be convex, enabling efficient methods, and they frequently represent resource limits or confidence regions.

8.3 Feasible sets for logical-style constraints (lightweight illustration)

Some toy models interpret logical conditions as constraints on variables.

8.3.1 Boolean variable constraints as sets

If a variable \(z\) is Boolean, then its feasible values are \(\{0,1\}\). A constraint like “\(z=1\)” yields the singleton feasible set \(\{1\}\). When multiple Boolean variables are used, feasibility corresponds to a subset of the hypercube of all \(0/1\) assignments.

8.4 Small mixed-integer feasible regions

Consider \(x\) continuous and \(y\in\{0,1\}\) with a constraint like \(x\ge y\) and \(x\le 2\). The feasible set becomes two segments in the \((x,y)\)-plane: one for \(y=0\) where \(x\in[0,2]\), and one for \(y=1\) where \(x\in[1,2]\). The union captures the discrete branching.

9. Common Visualizations

Visualization helps interpret the feasible set’s structure and its relationship to constraints.

9.1 1D feasible intervals

In one dimension, constraints typically yield an interval such as \([l,u]\), a ray, or an empty set. Inequality direction determines whether endpoints are included.

9.2 2D regions and constraint sketches

In two dimensions, each inequality is represented by a line (boundary) and a shaded side (allowed side). The feasible region is the overlap of shaded areas, which may be polygonal or curved depending on the constraints.

9.3 3D polyhedra and surfaces

In three dimensions, half-spaces bound polyhedra, and equalities produce planes that slice the space. Curved constraints produce surfaces like spheres or ellipsoids, and feasibility corresponds to the intersection region.

9.4 Coloring and partitioning feasible space (conceptual)

A conceptual technique is to color feasible regions by which constraints are active or which discrete decisions define the region. This makes it easier to understand how the allowed set changes across different parameter regimes.

Several closely related concepts describe different aspects of constraint satisfaction and optimization.

10.1 Constraint sets vs. feasible sets

A constraint set is the set of points that satisfy a single constraint, while the feasible set is the set satisfying all constraints at once. The feasible set is the intersection of constraint sets.

10.2 Active set and constraint slack

Given a feasible solution, an active set identifies which inequalities are tight at that point (and which equalities are satisfied exactly, by definition). Slack quantifies how far an inequality is from becoming active.

Feasible directions describe how one can move from a feasible point without immediately violating constraints, often used in local analysis. This concept links the global geometry of the feasible set to local behavior near candidate solutions.

10.4 Projection of feasible sets onto subspaces

Projecting onto a subspace yields the set of possible values of selected variables that can occur in some feasible completion of the others. This creates a reduced feasible description, useful in decomposition and elimination strategies.

10.5 Dual perspectives: primal feasibility counterparts

Many optimization frameworks pair primal feasibility (feasible decisions) with dual feasibility (feasible multipliers or certificates). While dual variables are not decisions themselves, they offer a complementary view on whether and how primal constraints can be satisfied and what objective bounds are implied.