Why Feasibility Comes First
A design problem may have a carefully chosen objective function and still be unusable if its constraints contradict one another. Before searching for a best design, first ask whether any design satisfies all the stated requirements. Then determine which limits are reached at feasible designs, where boundary candidates may occur, and whether the model has left out a physical restriction that matters.
These checks are distinct. A constraint can be written correctly but make the model infeasible when combined with the others. A feasible point can satisfy every inequality strictly and lie away from the inequality boundary. Conversely, equality constraints can restrict feasible designs to a curve or surface, so their feasible points need not be interior points in the surrounding space.
Feasible Sets and Active Constraints
Let \(\mathbf{x}\in D\subseteq\mathbb{R}^n\) denote the design variables, where \(D\) is the domain on which the model is defined. Represent the equalities by \(h_j(\mathbf{x})=0\), for \(j=1,\ldots,r\), and the inequalities by \(g_i(\mathbf{x})\leq 0\), for \(i=1,\ldots,m\). A condition originally written \(q(\mathbf{x})\geq b\), for example, can be written in this form as \(b-q(\mathbf{x})\leq 0\).
Equalities are satisfied exactly at every feasible point. The active/inactive distinction applies to inequalities: an active inequality is a limit reached exactly, while an inactive one has slack. A point that meets one constraint is not necessarily feasible; it must satisfy all equalities, inequalities, and domain restrictions simultaneously.
The domain also matters. For example, an expression containing \(1/x\) is undefined at \(x=0\), so \(x=0\) cannot be an admissible design unless the model has been reformulated. Physical restrictions such as nonnegative dimensions may be represented either as inequalities or as part of the domain, but they must be included somewhere.
Testing Feasibility Systematically
A practical first check is to translate every condition into a clear mathematical statement, including units where relevant. Then check whether the conditions can hold together. Bounds on the same quantity are especially useful: if the model requires \(x\leq 4\) and \(x\geq 7\), there is no feasible value of \(x\). For coupled conditions, candidate points or intersections can help, but every proposed point must be substituted into every constraint.
Record restrictions such as positive dimensions and any places where the objective or constraints are undefined.
Keep track of inequality direction when converting to the convention \(g_i(\mathbf{x})\leq 0\).
Bounds can expose immediate contradictions. Otherwise, verify a proposed feasible point against every condition.
At a feasible point, evaluate each \(g_i\): zero means active and a negative value means inactive.
Worked Example: Finding Boundary Candidates in a Design Region
Worked Example: Finding Boundary Candidates in a Design Region
Suppose two nonnegative design quantities \(x\) and \(y\) must satisfy a total limit \(x+y\leq 6\) and a minimum requirement \(x+2y\geq 4\). Determine whether the model is feasible, classify the constraints at \((2,1)\), and find the corner candidates of the feasible region.
Write the inequalities in the \(g_i\leq 0\) form: $$ -x\leq 0,\qquad -y\leq 0,\qquad x+y-6\leq 0,\qquad 4-x-2y\leq 0. $$ At \((2,1)\), the four left sides are $$ -2,\qquad -1,\qquad 2+1-6=-3,\qquad 4-2-2=0. $$ All are nonpositive, so \((2,1)\) is feasible. Only the minimum requirement is active there.
The boundary lines are \(x=0\), \(y=0\), \(x+y=6\), and \(x+2y=4\). Intersecting pairs and checking feasibility gives: $$ \begin{aligned} x=0,\ x+2y=4&\ \Longrightarrow\ (0,2),\\ x=0,\ x+y=6&\ \Longrightarrow\ (0,6),\\ y=0,\ x+2y=4&\ \Longrightarrow\ (4,0),\\ y=0,\ x+y=6&\ \Longrightarrow\ (6,0). \end{aligned} $$ Each listed point satisfies all four inequalities. The intersection of \(x+y=6\) and \(x+2y=4\) gives \(y=-2,\ x=8\), which fails \(y\geq0\). The intersection \(x=0,\ y=0\) gives \((0,0)\), which fails \(x+2y\geq4\). Thus the feasible region has the four listed corner points. These are boundary candidates to inspect in an optimization problem; finding them alone does not determine an optimum.
As a check, at \((0,2)\), the left sides are \(0,-2,-4,0\), all nonpositive. At \((0,6)\), they are \(0,-6,0,-8\); at \((4,0)\), they are \(-4,0,-2,0\); and at \((6,0)\), they are \(-6,0,0,-2\). Each corner is indeed feasible.
Interior and Boundary: State the Setting
For a set \(F\subseteq\mathbb{R}^n\), an interior point is a point surrounded by some open ball contained in \(F\). A boundary point is a point such that every open ball around it meets both \(F\) and its complement. Under these definitions, boundary points need not belong to \(F\). When discussing design candidates, it is therefore important to say whether a point is a feasible boundary point, meaning a point in \(F\) that is also on the boundary.
Here is a useful result for inequalities alone. Suppose \(D\) is open, the finite collection of functions \(g_i:D\to\mathbb{R}\) is continuous, and $$ F=\{\mathbf{x}\in D:g_i(\mathbf{x})\leq0\text{ for all }i\}, $$ with no equality constraints. Then every feasible point at which all inequalities are strict is an interior point of \(F\). Consequently, a feasible boundary point in \(D\) must have at least one active inequality.
To justify the result, take a feasible point \(\mathbf{x}_0\) with \(g_i(\mathbf{x}_0)<0\) for every \(i\). Since \(D\) is open, a sufficiently small ball around \(\mathbf{x}_0\) lies in \(D\). For each \(i\), continuity and the strict inequality at \(\mathbf{x}_0\) give a possibly smaller ball on which \(g_i<0\). There are only finitely many inequalities, so the intersection of these neighborhoods contains a ball around \(\mathbf{x}_0\). Throughout that ball every constraint is satisfied, so the ball lies in \(F\). Thus \(\mathbf{x}_0\) is interior. The contrapositive gives the boundary conclusion, specifically for feasible boundary points in \(D\).
The qualifications are essential. If the domain itself has a boundary, a feasible boundary point can arise from that domain boundary even when no inequality is active. And if equality constraints are present, strict inequalities do not generally make a point interior in the full ambient space.
Worked Example: Equality Constraints Change the Boundary Picture
Worked Example: Equality Constraints Change the Boundary Picture
Consider the design conditions \(x+y=1\), \(x\geq0\), and \(y\geq0\), with domain \(D=\mathbb{R}^2\). Describe the feasible set and identify which points have active inequalities.
The feasible points satisfy \(y=1-x\). Substituting into \(x\geq0\) gives \(x\geq0\), and substituting into \(y\geq0\) gives \(1-x\geq0\), or \(x\leq1\). Therefore $$ F=\{(x,1-x):0\leq x\leq1\}. $$ At \((1/2,1/2)\), both inequalities are strict, since \(x=1/2>0\) and \(y=1/2>0\). Nevertheless, this point is not an interior point of \(F\) in \(\mathbb{R}^2\): every open ball around it contains points not on the line \(x+y=1\), and those points are outside \(F\). The equality itself has restricted the feasible set to a line segment.
At \((0,1)\), the inequality \(x\geq0\) is active and \(y\geq0\) is inactive. At \((1,0)\), \(y\geq0\) is active and \(x\geq0\) is inactive. At \((1/2,1/2)\), neither inequality is active. The endpoints are boundary points of the segment even though only one inequality is active at each endpoint; the segment’s entire ambient boundary picture is shaped by the equality.
For this example, consider the boundary relative to the equality-feasible line \(E=\{(x,y):x+y=1\}\). Within \(E\), the points with \(x>0\) and \(y>0\), such as \((1/2,1/2)\), are interior to the feasible segment. The endpoints are its relative boundary points and each has an active inequality. This is the appropriate viewpoint when equality constraints define the space of allowable designs.
Worked Example: Contradictory Limits
Worked Example: Contradictory Limits
A design model requires \(x,y\geq0\), \(x+y\leq4\), and \(x+y\geq7\). Determine whether it is feasible.
The first coupled inequality gives \(x+y\leq4\), while the second gives \(x+y\geq7\). Together they would require $$ 7\leq x+y\leq4, $$ which is impossible because \(7>4\). Therefore the feasible set is empty. The nonnegativity constraints cannot resolve this contradiction.
This is a complete infeasibility certificate: no candidate point can satisfy the two opposing bounds. A common diagnostic is to isolate a shared quantity this way before attempting to solve a larger system.
Omitted Limits and False Optima
A feasible model can still be a poor model. If a physically important restriction is omitted, the equations may permit designs that cannot actually be built, operated, or sold. Common omissions include finite production capacity, a demand limit, a maximum safe load, minimum wall thickness, available material, or a required operating range. The correct restriction depends on the application; it cannot be inferred from the objective function alone.
One warning sign is an unbounded feasible set in a direction in which the objective keeps improving. Another is a computed “best” point that violates a known physical or operational limit not represented in the model. A finite-looking answer is not automatically realistic: the omitted restriction may change the optimum even if the original model already has one.
Worked Example: An Omitted Capacity Limit
Suppose a simplified production model chooses daily output \(x\geq0\) and assigns profit \(P(x)=7x\), in thousands of dollars per day. Determine what the model predicts, then add a capacity limit of \(x\leq40\) units per day and solve again.
With only \(x\geq0\), the feasible set is \([0,\infty)\). For any feasible \(x\), choosing \(x+1\) is also feasible and $$ P(x+1)-P(x)=7(x+1)-7x=7>0. $$ Thus no \(x\) maximizes profit; the objective increases without bound. This prediction may indicate that a relevant limit, such as machine capacity or demand, is missing.
After adding \(x\leq40\), the feasible interval is \(0\leq x\leq40\). Since \(P(x)=7x\) increases as \(x\) increases, its maximum on this interval occurs at \(x=40\). The profit is $$ P(40)=7(40)=280 $$ thousand dollars per day. The capacity inequality is active because \(40-40=0\) when written as \(x-40\leq0\); nonnegativity is inactive because \(-40<0\). Substitution checks the answer: \(x=40\) satisfies \(x\geq0\), \(x\leq40\), and produces the stated profit. The model’s prediction now depends directly on the capacity assumption, which should be justified by the application.
Boundary Candidates Are Not Automatically Optima
Active constraints help locate points worth examining in constrained optimization, but “active” does not mean “optimal.” A boundary point may have a worse objective value than another feasible point. Nor does every feasible boundary point have to be identified by an inequality in the model: domain boundaries and equality constraints can also shape the feasible set.
For a continuous objective on a nonempty compact feasible set, the extreme value theorem guarantees that both a maximum and a minimum are attained. If the feasible set is not compact, an optimum may fail to exist, as in the unbounded production example. Even when existence is assured, the objective must still be evaluated or analyzed on the relevant candidates. Feasibility and boundary diagnostics clarify the search; they do not replace it.
Before optimizing, make a final model audit:
- Are all required physical and mathematical domain restrictions stated?
- Can one exhibit a point satisfying every constraint, or prove that none exists?
- Which inequalities are active at each feasible candidate being considered?
- Could an equality or domain boundary explain a boundary point with no active inequality?
- Would a realistic capacity, safety, demand, or resource limit change the answer?
Check Your Understanding
Answer each question by referring to the definitions and examples above.
- What must be checked before a point satisfying one design constraint can be called feasible?
- For \(g_i(\mathbf{x})\leq0\), what does it mean for an inequality to be active at a feasible point?
- Why does strict inequality slack imply an interior point for a finite system of continuous inequalities on an open domain, but not necessarily when equality constraints are included?
- Can every boundary point of a feasible set be assumed to satisfy an active inequality? Name two other sources of boundary points.
- Why might an unbounded feasible set be a clue that a design model has omitted an important restriction?