1
$\begingroup$

Given a list of vectors, I want to find whether there exists a vector such that its dot product with those in the list is all (semi)positive, or at least above a certain small negative value.

$\endgroup$
10
  • 1
    $\begingroup$ What is the dimension of the ambient space? In principle, one can compute the convex hull of the points and check whether the origin is contained in the interior. Mathematica provides ConvexHullMesh, but that works only in dimensions 2 and 3... $\endgroup$ Commented Mar 26, 2020 at 7:53
  • $\begingroup$ It's 7 dimensional. And the list is of 14 vectors. I was wondering whether Mathematica has some standard function for this sort of thing. I've searched the reference site for "convex cone" but haven't found anything. $\endgroup$ Commented Mar 26, 2020 at 7:59
  • 1
    $\begingroup$ Maybe you find this one interesting: sciencedirect.com/science/article/abs/pii/0305054893900803 $\endgroup$ Commented Mar 26, 2020 at 8:28
  • $\begingroup$ After reading your post, I figured I could probably get the code to work by using a constrained NMinimize for the "Nearest" function, where you have one parameter for each vector and the constraints explicitly describe the convex hull. $\endgroup$ Commented Mar 26, 2020 at 8:33
  • 1
    $\begingroup$ you get a function with (n-1) parameters describing the linear combination of the n vectors with the n'th parameter being equal to 1 minus the sum of the other parameters. Then you minimize its distance to 0 constrained by all parameters and their sum being between 0 and 1. Not the most elegant solution, but it might work for small data-sets. $\endgroup$ Commented Mar 26, 2020 at 8:48

1 Answer 1

0
$\begingroup$

I've made a "bare-bones" implementation of a function that calculates the dual cone of a given vector set. It's not fancy or efficient (plus, I'm pretty sure it goes against some code indentation rules), but it works.

dualCone[lis_] := Module[{l, crosLis, goodLis},
  l =  Length[lis[[1]]];
     crosLis = Apply[Join,
    Map [
     Function[subList,
      Module[{cross, val},
       cross = Apply[Cross, 4*subList];
       val = Complement[lis, subList].Normalize[cross] ;
       {{cross, Min[val]}, {-cross, Min[-val] }}]],
     Subsets[lis, {l - 1}]]
    ];
  goodLis = 
   Select[crosLis, 
    Function[x, (x[[2]] > 0) && (Norm[x[[1]]] > 0.000001)]];
  Sort[Map[Function[x, Normalize[x[[1]]]], goodLis]] 
]

Testing the function

The interior of a convex set includes zero if and only if the dualCone of that set is null. It probably doesn't work well for boundary cases, tweaking with the (x[[2]] > 0) && (Norm[x[[1]]] > 0.000001) constraints might help with that. Tough I'm not sure, I haven't studied the problem.

For a generic list vec1 of vectors, the set of vectors v which have the property of always giving semi-pozitive dot products with the vectors of vec1 can be generated by the conical combinations of the vectors given by dualCone[vec1].

If the list dualCone[vec1] is null, no such vectors exist.

If it is not, then it contains feasible vectors, which can be used to generate all other vectors that satisfy the constraint, by conical combination.

The given definition works well for "generic" vector lists, no so much for boundary conditions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.