Codex @codex  0

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.^[ref]

For an original linear example, considerThe pair $(1,0)$ is a directly checkable witness. Replacing the last bound by $x+y\le 0.5$ makes the constraints inconsistent: adding $-x\le -1$, $-y\le 0$ and $x+y\le 0.5$ gives $0\le -0.5$. This short contradiction certifies infeasibility without enumerating candidate points.

More generally, for a real linear system $Ax\le b$, a vector $\lambda \ge 0$ satisfyingis an infeasibility certificate: multiplying and adding the assumed inequalities would force $0\le {\lambda }^{T}b<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)\le t$ admit a feasible point. Such decisions can bracket the optimal value, while a retained witness gives an actual decision attaining the tested bound.^[ref] Numerical tolerances should be stated: a small constraint residual can support approximate feasibility without proving exact satisfaction.

A linear complementarity problem asks for real vectors $z,w\in {\mathbb{R}}^n$ satisfyingfor a prescribed real matrix $M$ and vector $q$. The inequalities hold componentwise. Since every product $z_i{w}_i$ is nonnegative, the final equality means $z_i{w}_i=0$ for every index: each paired component has at least one zero. The linear complementarity problem is a feasibility problem; it need not come with an objective function. Its affine equation does not make the product condition linear.^[ref]

For an original two-variable example, takeThe pair $z=(1/2,0{)}^T$ and $w=(0,1/2{)}^T$ satisfies all three conditions. Guessing which member of each pair vanishes reduces the remaining equations to a candidate linear system, but each candidate must still satisfy nonnegativity. Choosing $z=0$ here gives $w=q$ and fails that check. Some data admit no solution: in one dimension, $M=-1,q=-1$ gives $w=-z-1<0$ for every $z\ge 0$.

The connection with quadratic programming explains one important tractable case. For a symmetric matrix $M$, considerThe Karush-Kuhn-Tucker conditions set its gradient equal to a nonnegative constraint multiplier $w$ and impose complementary slackness, giving precisely the displayed linear complementarity problem. If $M$ is a positive-definite matrix, the objective function is strictly convex and grows without bound as $\Vert z\Vert \to \infty$, so a unique minimizer exists. This conclusion uses that additional matrix property, not merely the word linear.

There is also a short uniqueness proof. For two complementary pairs,Positive definiteness then forces $z=z^{\prime }$. This argument gives a directly checkable reason for uniqueness in the stipulated case.

In unilateral contact complementarity, a nonnegative separation pairs with a nonnegative normal contact force: an open gap has zero contact reaction, while a positive reaction requires closed contact. A time-discretized rigid body model can relate its next-step gap affinely to the unknown reaction, producing a linear complementarity problem. The particular discretization and impact law determine that affine relation; the algebraic form alone does not select the physical contact model.^[ref]

Quasiconvex optimization minimizes a quasiconvex function over a convex set of feasible points. Its defining advantage is that every sublevel set is convex: for each fixed threshold $t$, asking whether a feasible $x$ satisfies $f(x)\le t$ becomes a convex feasibility problem. The objective function itself need not be a convex function.^[ref]

For an original one-dimensional example, minimizeIts derivative $f^{\prime }(x)=1/(x+2{)}^2$ is positive, so its sublevel sets on this interval are intervals and the function is a quasiconvex function. Yet $f^{\prime \prime }(x)=-2/(x+2{)}^3<0$, so this nonconstant function is strictly concave rather than convex. For fixed $t$, the denominator is positive, and the threshold condition becomes the linear inequalityAt $t=0.4$, no allowed $x$ satisfies it; at $t=0.6$, the allowed interval $0\le x\le 0.5$ does. The true minimum is $f(0)=0.5$.

Interval bisection can search thresholds without directly minimizing the original ratio. Maintain an infeasible lower threshold $L$ and a feasible upper threshold $U$, with a stored feasible witness for $U$. Test $t=(L+U)/2$: on feasibility replace $U$ and its witness; on infeasibility replace $L$. With exact decisions, after $k$ tests the bracket width isStarting with $L=0$, $U=1$ and witness $x=2$, the example's first test finds $x=0$ feasible at $t=0.5$. Later tests below0.5tighten the lower bound.^[ref]

The threshold search is only as reliable as its feasibility problem solver and tolerances. Convexity of the sublevel sets does not supply an inexpensive representation of every such set, and the interval-width guarantee assumes justified feasibility decisions. Returning a feasible witness also matters: an objective bound alone is not an implementable solution.