1 Feasible region fundamentals
1.1 Definition and notation
A feasible region is the collection of all points in a decision space (commonly a real vector space \(\mathbb{R}^n\)) that satisfy a specified set of constraints. In optimization, the feasible region is often denoted by \( \mathcal{F}\) and the problem statement is framed as optimizing an objective over \(x \in \mathcal{F}\). When constraints depend on parameters, the feasible region may be written as \(\mathcal{F}(p)\) to indicate that its shape changes with the data.
1.2 Constraint types
1.2.1 Equality constraints
Equality constraints require exact satisfaction of equations, typically written as \[ g(x)=0 \] for some function \(g\). In linear settings, this becomes \(Ax=b\). Equality constraints restrict the feasible region to a lower-dimensional subset, such as an affine subspace, unless the constraints are redundant.
1.2.2 Inequality constraints
Inequality constraints restrict points to lie on one side of a condition, commonly expressed as \[ h(x)\le 0 \quad \text{or} \quad h(x)\ge 0. \] In linear programming, inequalities like \(Ax\le b\) describe half-spaces; their intersection yields a polyhedral feasible region.
1.2.3 Bound constraints
Variable bounds impose simple limits componentwise, often written as \[ \ell \le x \le u, \] where \(\ell\) and \(u\) may include infinite values. Bound constraints are ubiquitous in practice because they encode engineering limits, physical ranges, or numeric safeguards.
1.2.4 Implicit domain restrictions
Some constraints arise not from explicit formulas but from domain requirements, such as requiring \(x\) to be nonnegative, restricting \(\log(\cdot)\) arguments, or ensuring square roots have nonnegative inputs. These restrictions are part of feasibility even if they are not written as separate inequalities.
1.3 Feasibility and feasibility sets
1.3.1 Feasible points
A feasible point is any decision vector \(x\) that simultaneously satisfies all constraints. Feasibility is a prerequisite for evaluating an objective; without feasibility, the objective may be undefined or irrelevant.
1.3.2 Infeasibility and empty feasible regions
If no point satisfies the full collection of constraints, the feasible region is empty, denoted \( \mathcal{F}=\varnothing\). In that case, the optimization problem has no solution because there is no admissible candidate to optimize over.
1.3.3 Unbounded feasible regions
A feasible region can extend indefinitely in one or more directions. Unboundedness means there exist feasible points with arbitrarily large norms or coordinates. Whether this prevents an optimum depends on the objective; an optimum can still exist if the objective grows sufficiently fast, but it may fail to exist if the objective can decrease without limit over feasible directions.
2 Geometry and structure
2.1 Dimension and shape
2.1.1 Vertices, edges, and faces (polyhedral case)
When constraints are linear inequalities and equalities, the feasible region is a polyhedron. Its combinatorial features—vertices (corner points), edges (line segments), and faces (higher-dimensional facets)—determine how feasible candidates are organized. In many linear or piecewise-linear optimization problems, optimal solutions frequently occur at extreme points such as vertices.
2.1.2 Interior vs. boundary points
Feasible regions have an interior consisting of points that satisfy inequality constraints strictly (when possible), and a boundary where one or more inequalities are tight. The distinction matters because algorithmic behavior often changes near boundaries; gradients or curvature can behave differently, and constraints may become “active” there.
2.1.3 Dimensionality reduction and affine hull
Equality constraints frequently reduce the dimension of the feasible set relative to the ambient space. The affine hull describes the smallest affine subspace containing the feasible region. Even for inequality-constrained problems, if equality constraints dominate, feasibility may concentrate on a slice of the full space rather than occupying a full \(n\)-dimensional volume.
2.2 Convexity properties
2.2.1 Convex feasible regions
A set \(\mathcal{F}\) is convex if for any two feasible points \(x,y\in\mathcal{F}\), the entire line segment \(\theta x+(1-\theta)y\) for \(\theta\in[0,1]\) is feasible. Convex feasible regions are central because many optimization algorithms gain reliability: local optimality conditions often imply global optimality, and many methods avoid being trapped by nonconvex “holes.”
2.2.2 Non-convex feasible regions
If the set fails convexity, line segments between feasible points may pass through infeasible territory. Non-convex feasible regions can contain disjoint components or cavities, complicating both analysis and computation. In such cases, the location of the optimum can depend strongly on initialization and the structure of the objective.
2.2.3 Star-shaped and other common geometries
Some sets are not convex but still satisfy weaker geometric properties. For instance, a set is star-shaped if there exists a point from which every point in the set is visible via line segments that remain within the set. Star-shaped regions can support certain algorithms more effectively than arbitrary nonconvex sets.
2.3 Closedness and boundaries
2.3.1 Open vs. closed constraints
Whether constraints use strict inequalities matters. For example, \(h(x)<0\) defines an open condition, while \(h(x)\le 0\) defines a closed one (under typical continuity assumptions). A feasible region defined by open constraints may lack boundary points that are limit points of feasible sequences.
2.3.2 Boundary behavior and limit points
Even if a point is not feasible, it may be approached by feasible points. Limit points help determine existence results for optima, particularly when maximizing or minimizing continuous objectives over sets that may not be compact. Boundary behavior can also influence dual formulations and stationarity conditions.
2.4 Representations and descriptions
2.4.1 Half-space intersection form
In linear problems, a common representation is as the intersection of half-spaces: \[ \mathcal{F}=\{x: a_i^\top x\le b_i,\ i=1,\dots,m\}. \] This form emphasizes geometry and yields polyhedral structure, enabling direct reasoning about vertices, edges, and feasibility certificates.
2.4.2 Constraint qualification perspective
In nonlinear optimization, feasibility geometry is linked to assumptions about constraints that allow optimality conditions to be expressed cleanly. These “qualification” conditions regulate whether constraints behave regularly near candidate points, affecting whether multipliers and stationarity relationships are valid.
2.4.3 Implicit vs. explicit descriptions
| Some feasible regions are described explicitly as constraints, while others are characterized implicitly by membership in a level set or transformation of variables. For example, requiring \(x\) to satisfy a norm constraint \(\|Ax-b\|\le r\) is implicit in the sense that the inequality defines the set geometrically rather than as simple coordinate bounds. |
|---|
3 Feasible regions in optimization problems
3.1 Role in objective minimization/maximization
3.1.1 Where optimal solutions can lie
In many settings, the optimum occurs at points that are boundary-adjacent: those where constraints become tight. For convex problems, boundary points can still host global optima, and for linear programs the optimum typically aligns with extreme points due to linearity of both objective and constraints.
3.1.2 Existence of optimal solutions
Whether an optimum exists depends on feasibility and the objective’s behavior. A feasible region must be nonempty, and additional properties such as compactness (closed and bounded) or coercivity-like growth of the objective may be required to prevent “escape to infinity.”
3.1.3 Boundedness implications
Unbounded feasible regions can still yield solutions if the objective restricts motion—for instance, if it increases strongly along every unbounded feasible direction. Conversely, if an objective can decrease indefinitely while maintaining feasibility, the problem may have no optimum value even though feasible points exist.
3.2 Feasible sets for common problem classes
3.2.1 Linear programming feasible regions
For linear programs, feasible regions are polyhedra defined by linear equalities and inequalities. Their geometry is determined by the coefficient matrix and right-hand side vectors. Feasibility analysis and algorithmic progress often leverage polyhedral structure.
3.2.2 Quadratic programming feasible regions
Quadratic programming may involve linear constraints defining a polyhedral region, but the objective is quadratic. In some variants, the constraints themselves can be quadratic as well, producing feasible sets with curved boundaries and potentially nonconvex shapes.
3.2.3 Convex optimization feasible regions
In convex optimization, feasible regions are convex sets, often described through convex inequalities and equalities. This structure supports strong theoretical guarantees and enables efficient computational methods, especially when constraints admit tractable evaluations.
3.2.4 Nonlinear programming feasible regions
For general nonlinear programming, feasible regions can be irregular, nonconvex, and sensitive to numerical perturbations. Feasibility is still the foundational requirement, but geometry may not support simple global reasoning without additional assumptions.
3.3 KKT and optimality relationships
3.3.1 Active constraints
A constraint is active at a point if it holds with equality among its inequality representation (e.g., \(h(x)=0\) for constraints written as \(h(x)\le 0\)). Active constraints influence optimality conditions because they determine local feasible directions; only constraints that bind can affect stationarity.
3.3.2 Lagrange multipliers overview
KKT theory introduces multipliers associated with constraints to combine them into a Lagrangian function. These multipliers quantify how sensitive the objective is to movements that violate or relax constraints. While multipliers do not always exist under every scenario, when they do, they provide a systematic stationarity characterization.
3.3.3 Complementary slackness interpretation
Complementary slackness couples inequality constraint tightness with the corresponding multiplier sign. Roughly, if an inequality constraint is not tight, its multiplier should be zero; if it is tight, the multiplier may be positive (under common sign conventions). This relationship links feasibility geometry to the algebra of optimality.
4 Computational aspects
4.1 Membership testing (feasible or not)
4.1.1 Direct substitution checks
Given a candidate point \(x\), feasibility can be tested by evaluating each constraint. For linear constraints, this reduces to matrix-vector products and comparisons. For differentiable nonlinear constraints, this becomes a sequence of function evaluations plus inequality checks.
4.1.2 Numerical tolerances and robustness
Computers operate with finite precision. As a result, constraints that are theoretically equalities may appear slightly off, and inequalities may be nearly tight. Robust implementations use tolerances to decide whether a point is “close enough” to satisfy constraints, balancing correctness against practical stability.
4.2 Finding feasible points
4.2.1 Feasibility search strategies
Finding any feasible point may require solving a separate feasibility problem or embedding feasibility into a larger algorithm. Common strategies include alternating between constraint satisfaction steps, using penalty or barrier techniques, or applying projection-like corrections iteratively.
4.2.2 Projection methods (high level)
Projection methods adjust a candidate point toward feasibility by solving, at each iteration, a nearest-point problem relative to a constraint set. Exact projection can be expensive; approximate projections may be used when constraints are structured or when only partial satisfaction is enforced per step.
4.2.3 Constraint relaxation and recovery
When the feasible region is difficult to hit directly, algorithms may relax constraints temporarily (e.g., allow small violations) to navigate toward a feasible neighborhood. Later stages attempt to recover strict feasibility by tightening tolerances or re-centering the iterate.
4.3 Sampling and exploration of feasible regions
4.3.1 Grid-based approaches
For low-dimensional cases, gridding can provide an intuitive map of feasible points. Each grid point is tested for feasibility, and the region can be visualized by marking accepted points. This approach scales poorly with dimension but is useful for teaching and debugging.
4.3.2 Random sampling intuition
Random sampling methods generate candidate points according to some distribution, then retain those that satisfy the constraints. For convex sets, hit-and-try schemes can reflect geometry, but efficiency depends heavily on how much of the space is feasible.
4.3.3 Coverage vs. computational cost
There is a trade-off between coverage of the feasible set and computational effort. Dense exploration can improve insight but requires many feasibility evaluations. Conversely, sparse sampling can miss narrow feasible corridors or small feasible components.
4.4 Scalability considerations
4.4.1 High-dimensional feasibility
In high dimensions, volume concentrates in unintuitive ways, and naive sampling often becomes inefficient. Optimization methods typically exploit gradients, constraint structure, or convexity to navigate toward feasible regions without exhaustive search.
4.4.2 Sparse constraints and structure
When constraints are sparse or decomposable, computation can be accelerated. Techniques may take advantage of sparsity in constraint Jacobians or exploit separable structure in feasible sets, reducing both memory and arithmetic cost.
4.4.3 Conditioning and algorithm stability
Feasibility can be numerically delicate when constraints are nearly dependent or when boundaries intersect at shallow angles. Poor conditioning can cause iterative methods to oscillate or converge slowly, so stability considerations often shape algorithm choices and tolerance settings.
5 Examples and illustrative cases
5.1 Two-dimensional linear constraints
5.1.1 Half-planes and intersections
Consider constraints \(a_i x_1 + b_i x_2 \le c_i\) in \(\mathbb{R}^2\). Each inequality defines a half-plane, and the feasible region is their intersection. Visual inspection reveals how constraints carve the plane and which inequalities actually limit the region.
5.1.2 Bounded vs. unbounded polygons
With enough inequalities, the intersection can form a bounded polygon (a compact feasible region). If some directions remain unconstrained, the feasible region becomes unbounded, extending to infinity along rays that satisfy every inequality.
5.2 Three-dimensional polyhedral examples
5.2.1 Faces and polytope intuition
In \(\mathbb{R}^3\), linear constraints intersect half-spaces to form a polyhedron. Constraints correspond to planes that cut the space, and the feasible region’s facets are polygonal faces. Even when the number of constraints is large, only a subset can determine the visible faces.
5.2.2 Degeneracy and lower-dimensional feasible sets
Sometimes constraints lead to a feasible set that lies in a plane or line within \(\mathbb{R}^3\), rather than occupying a full 3D volume. Such degeneracy changes the geometry: vertices may merge, edges may collapse, and the notion of an “interior point” may be replaced by interior relative to a lower-dimensional manifold.
5.3 Nonlinear constraint examples
5.3.1 Circular/elliptic feasible regions (conceptual)
| Constraints involving norms or quadratic forms create curved boundaries. For example, requiring \(\|x\|\le r\) yields a disk in two dimensions, while \(\|Ax-b\|\le r\) produces ellipsoidal sets. Intersections of such regions can yield lens-shaped or more complex shapes. |
|---|
5.3.2 Curved boundaries and intersections
Nonlinear inequalities can intersect in ways that produce smooth arcs, corners, or cusp-like features depending on curvature and constraint alignment. The resulting feasible region may be convex or nonconvex, affecting how algorithms locate optima and how multipliers interpret active constraints.
5.4 Degenerate and special cases
5.4.1 Singleton feasible sets
A feasible region can contain exactly one point. This can happen when equality constraints fix all degrees of freedom, and inequality constraints hold automatically at that point. Optimization over a singleton is trivial, though the structure is informative for feasibility diagnostics.
5.4.2 Empty feasible sets
Conflicting constraints can make feasibility impossible. Geometrically, the feasible region disappears when half-spaces or curved constraints do not overlap. Detecting emptiness is often a key subtask, even when the ultimate goal is optimality.
5.4.3 Redundant and conflicting constraints
Redundancy occurs when some constraints do not further restrict the region, while conflicting constraints prevent any solution. In computation, redundancy can increase evaluation cost without changing feasibility, whereas conflicts may surface as algorithmic failure or infeasibility certificates.
6 Related concepts
6.1 Constraint satisfaction problem perspective
Feasibility can be studied as a constraint satisfaction problem: the task is to determine whether any assignment satisfies all constraints, independent of an objective. Many optimization workflows implicitly perform feasibility reasoning even when an objective guides the search.
6.2 Feasibility vs. optimality
Feasibility asks whether a candidate exists; optimality asks which feasible candidate is best according to the objective. A problem may be feasible but lack an optimum (e.g., due to unbounded descent), and it may have an optimum even when feasibility is complicated to establish.
6.3 Dual feasible sets (overview)
Dual formulations introduce variables associated with constraints and produce dual feasible sets for those multipliers. The geometry of dual feasibility parallels primal feasibility in that it constrains which multiplier values correspond to meaningful bounds on the objective.
6.4 Active set methods connection (overview)
Active set methods iteratively guess which inequality constraints are active and solve a subproblem based on that guess. This leverages the link between active constraints and optimality structure, updating the active set until consistency with feasibility and stationarity is achieved.
6.5 Measure-theoretic intuition (optional high level)
From a high-level perspective, probabilistic views relate feasibility rarity to “volume” in the decision space. In high dimensions, sets of feasible points may have small measure, making random methods less effective. Measure-theoretic intuition helps explain why specialized algorithms that use geometry and derivatives are often preferred.