Recipe

Check whether a point lies in a conic hull

Use when: you have finitely many generating vectors and a target point, and want to know whether the target is some nonnegative combination of the generators

Goal: explicit weights \lambda_i\ge0 exhibiting the target as \sum\lambda_ix_i, or confirmation that none exist

Taught in The convex hull and conic hull

1. 1

   Write the target as a weighted sum of the generators, with the weights as unknowns, then expand one equation per coordinate.

   Example

   For u=(2,1), v=(1,3), target (8,9): \lambda u+\mu v=(8,9) gives 2\lambda+\mu=8 and \lambda+3\mu=9.

   Why: \operatorname{cone}(S) is exactly the set reachable by some choice of nonnegative weights, so finding the target reduces to solving for those weights.

2. 2

   Solve by substitution or elimination, the same as any two-equation system.

   Example

   From 2\lambda+\mu=8, \mu=8-2\lambda. Substituting: \lambda+3(8-2\lambda)=9\implies-5\lambda=-15\implies\lambda=3, so \mu=8-2(3)=2.

   Why: the system's solution is the only candidate weight pair -- if none exists, or the candidate fails the next check, the point isn't in the conic hull.

3. 3

   A conic hull only allows nonnegative weights. Verify \lambda_i\ge0 for each one solved in Step 2.

   Example

   \lambda=3\ge0, \mu=2\ge0, so (8,9)\in\operatorname{cone}(\{u,v\}); check: 3(2,1)+2(1,3)=(6,3)+(2,6)=(8,9). ✓

   • every weight is \ge0 — the point IS in \operatorname{cone}(S); report the weights as the certificate.
   • at least one weight is negative — the point is NOT in \operatorname{cone}(S), even though the linear system had a solution.

   Why: \operatorname{cone}(S)'s own definition requires every weight nonnegative -- a solution with a negative weight solves the SPAN, not the cone.