Feasible set

A feasible set in mathematical optimization is the set of all choices of decision variables that satisfy every constraint and belong to the specified domain. Its elements are called feasible points or feasible solutions. The feasible set describes which choices are permitted, while the objective function determines how those choices are ranked. A feasible point need not be optimal: optimality additionally requires the best attainable objective value among the permitted choices. (stanford.edu)

Mathematical definition

Consider the problem

Here $x$ is a vector of decision variables, $f$ is the objective, and $D$ specifies the underlying domain. The feasible set is

The domain must also respect any restrictions needed to define the functions. Thus, satisfying the displayed inequalities alone is insufficient if a function is undefined at the proposed point. (stanford.edu)

In finite-dimensional continuous optimization, $D$ is commonly a subset of the real vector space $\mathbb R^n$. In integer programming, some or all coordinates must instead be integers. The distinction changes the admissible points even when the algebraic constraints are otherwise identical. (mit.edu)

The set can equivalently be viewed as an intersection of the individual constraint sets. Consequently, adding a constraint can only reduce or preserve the feasible set. A redundant constraint leaves it unchanged because it is already implied by the remaining restrictions. These observations follow directly from the definition. (stanford.edu)

Feasibility and optimality

A problem is feasible when $F\neq\varnothing$ and infeasible when $F=\varnothing$. A feasibility problem asks only for a member of $F$, or a determination that no such member exists. It can be represented as an optimization problem with a constant objective, since all feasible points then have the same objective value. (docs.gurobi.com)

For minimization, the optimal value is

An optimizer $x^\star$ exists only if some feasible point actually attains this value. Three distinct situations must therefore be separated: inconsistent constraints, an objective unbounded below on the feasible set, and a finite infimum that is not attained. (stanford.edu)

An unbounded feasible set does not imply an unbounded objective. For example, on $F=\mathbb R$, minimizing $x^2$ gives the attained minimum $0$. Conversely, minimizing $x$ on $F=(0,1)$ has infimum $0$, but no optimizer. These examples illustrate why feasibility, boundedness, and attainment are different properties. (mit.edu)

Geometry and convexity

In linear programming, feasible sets are described by affine equalities and inequalities. A nontrivial affine equality defines a hyperplane, while an affine inequality defines a half-space. Their finite intersection is a polyhedron, which may be empty, bounded, unbounded, or lower-dimensional. In matrix notation, a typical description is

This representation connects constraint systems with their geometric interpretation. (courses.csail.mit.edu)

A convex set contains the entire line segment joining any two of its points. Accordingly, a feasible set is convex precisely when

for every $x,y\in F$ and $0\leq\theta\leq1$. The expression is a convex combination. Intersections of convex sets remain convex, explaining the convexity of polyhedral feasible regions. (courses.csail.mit.edu)

More generally, convex inequality functions and affine equality functions, imposed on a convex domain, produce a convex feasible set. If the objective is also a convex function, the problem is a convex optimization problem. Convexity of the feasible set alone does not establish convexity of the entire optimization problem. (stanford.edu)

Boundary and existence of solutions

An inequality $g_i(x)\leq0$ is active at a feasible point when $g_i(x)=0$; otherwise it is inactive. Active constraints identify restrictions that are tight at that point. Strict feasibility means that all inequality constraints hold strictly, while equality constraints remain satisfied. (courses.csail.mit.edu)

Strict feasibility should not be confused with having an interior in the full ambient space. For example, $x_1+x_2=1$, together with $x_1,x_2\geq0$, defines a line segment in $\mathbb R^2$. Points with both coordinates positive satisfy the inequalities strictly, yet the segment has no two-dimensional interior. Its relative interior is taken within its affine hull. (stanford.edu)

Topological properties are important for attainment. The extreme value theorem guarantees that a continuous real-valued objective attains its minimum on a nonempty compact feasible set. In $\mathbb R^n$, compactness is equivalent to being closed and bounded. These are sufficient conditions, not necessary ones: an unbounded feasible set may still contain an optimizer. (mit.edu)

Relaxation and numerical feasibility

A relaxation replaces $F$ by a larger set $R\supseteq F$. For minimization, the relaxed optimal value cannot exceed the original value, because more choices are available. Dropping integrality requirements is a common example; a relaxed solution need not satisfy the original constraints. (underactuated.csail.mit.edu)

Computational feasibility differs from exact mathematical membership. Solvers using floating-point arithmetic generally accept small constraint violations within specified tolerances. Thus, a solution reported as feasible may lie slightly outside the exact feasible set. Scaling and tolerances affect this numerical interpretation without changing the abstract definition. (docs.gurobi.com)