= Feasibility problem
A <feasibility problem> asks whether any point satisfies a specified collection of <optimization constraints>, and seeks such a point when one exists. There need not be a preference among satisfying points. If the <feasible set> is $F$, the mathematical questions are whether $F$ is empty and, if not, how to produce a <feasible point>. A <feasibility problem> can be represented as <mathematical optimization> with a constant zero <objective function>.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[Section4.1.1, printed pp128–129, feasibility problems]{ref}
For an original linear example, consider
$$
x\geq1,\qquad y\geq0,\qquad x+y\leq1.5.
$$
The pair $(1,0)$ is a directly checkable witness. Replacing the last bound by $x+y\leq0.5$ makes the constraints inconsistent: adding $-x\leq-1$, $-y\leq0$ and $x+y\leq0.5$ gives $0\leq-0.5$. This short contradiction certifies infeasibility without enumerating candidate points.
More generally, for a real linear system $Ax\leq b$, a vector $\lambda\geq0$ satisfying
$$
\lambda^TA=0,\qquad \lambda^Tb<0
$$
is an infeasibility certificate: multiplying and adding the assumed inequalities would force $0\leq\lambda^Tb<0$. This is the certificate side of <Farkas' lemma>. A failed numerical search or a timeout is different from such a proof; it need not imply that the <feasible set> is empty.
The allowed variable set is part of the question. The equation $2x=1$ is feasible over the real numbers, with $x=1/2$, but infeasible when $x$ must be an <integer>. Thus replacing <integer programming> constraints by a real relaxation changes the <feasibility problem>.
<Quasiconvex optimization> supplies a useful connection: for each threshold $t$, test whether the original constraints and $f(x)\leq t$ admit a <feasible point>. Such decisions can bracket the optimal value, while a retained witness gives an actual decision attaining the tested bound.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[Section4.2.5, printed pp145–146, Algorithm4.1]{ref} Numerical tolerances should be stated: a small constraint residual can support approximate feasibility without proving exact satisfaction.
Back to article page
