## Definition The **feasibility region** $\mathcal{F}$ is the set of all $x$ that satisfy every constraint of an optimisation problem: $ \mathcal{F} = \{x \mid g_i(x) \leq 0 \text{ for all } i, \, h_j(x) = 0 \text{ for all } j\} $ A solution must lie in $\mathcal{F}$; otherwise it doesn't *exist* as a candidate. ## Possible Shapes - **Unbounded** — extends infinitely in some directions. - **Bounded** — contained in a finite region. - **Empty** — no $x$ satisfies all constraints. Problem is *infeasible*. - **Convex** — line segments between feasible points stay feasible. - **Non-convex** — feasibility region has holes, disconnected components, or non-straight boundaries. ## Examples ### Linear Programming Feasibility region is a **polytope** — the intersection of finitely many half-spaces (defined by linear inequalities). Convex by construction. ### Quadratic Constraints Feasibility region may be an *ellipsoid*, a *paraboloid*, or more complex. Can be convex or non-convex depending on signs. ### Combinatorial Problems Discrete feasibility region. Examples: integer points satisfying constraints (Integer LP); permutations satisfying precedence (scheduling); vertex subsets of a graph (covering problems). ## Why It Matters The interplay of feasibility and objective shapes the difficulty: - **Convex feasibility + convex objective** → tractable. - **Convex feasibility + non-convex objective** → local optima possible. - **Non-convex feasibility** → much harder; even finding a feasible point can be NP-hard. ## Special Properties - **Active constraints** at a point $x \in \mathcal{F}$: those with $g_i(x) = 0$. They "matter" at $x$. - **Interior** of $\mathcal{F}$: points strictly inside (all $g_i(x) < 0$). Interior-point methods exploit this. - **Boundary** of $\mathcal{F}$: at least one constraint is active. Optimal solutions often lie on the boundary. ## Handling Infeasibility When constraints can't all be satisfied: - **Soft constraints.** Convert hard constraints to penalties in the objective. - **Phase 1 / Phase 2 algorithms.** First find any feasible point (Phase 1); then optimise (Phase 2). - **Constraint relaxation.** Drop or weaken constraints to find a near-feasible solution. - **Multi-objective formulation.** Minimise infeasibility alongside the original objective. ## Convex vs Non-Convex Feasibility A convex feasibility region: - Any feasible point can be reached by interior paths from any other. - Algorithms like interior-point methods work efficiently. A non-convex feasibility region: - May require combinatorial search. - Local methods can get trapped in suboptimal "feasible pockets". ## Related - [[Optimization Problem]] - [[Objective Function]] - [[Convex vs Non-Convex Optimization]] - [[Linear Programming]] - [[KKT Conditions]]