Feasibleset

The feasible set, often called the feasible region, is the collection of all decision variable vectors that satisfy every constraint of a problem. In a constrained optimization problem such as minimize f(x) subject to h_i(x) = 0 for i = 1,...,p and g_j(x) ≤ 0 for j = 1,...,m, the feasible set is F = { x ∈ R^n | h_i(x) = 0 and g_j(x) ≤ 0 for all i,j }. It represents the domain within which feasible solutions may lie and where the objective is optimized.

For example, if x ∈ R^2 with x1 ≥ 0, x2 ≥ 0, and x1 + x2 ≤ 1, the feasible set is the closed triangle in the first quadrant bounded by the axes and the line x1 + x2 = 1. The structure of the feasible set is determined by the constraints: linear constraints yield a polyhedron, while convex constraints yield a convex feasible set.

Key properties include convexity and feasibility. If all constraints are convex, the feasible set is convex, which often simplifies optimization. If the constraints are linear, the feasible set is a polyhedron and may be unbounded. A feasible set may be empty, in which case the problem is infeasible. In optimization, the problem is to find the best point in the feasible set; in feasibility problems, one only asks whether the feasible set is nonempty.

Computationally, the feasible set guides algorithm design. Methods may search within F directly, enforce feasibility via projections or penalties, or reformulate the problem to incorporate slack or barrier terms.