Here is another idea.

Key observation:

Let $O$ be the origin in $\mathbb{R}^4$. Let $H$ be the convex hull of the set $\{O\} \cup \{l_i : 1 \leq i \leq n\}$. Then one may only consider those $l_i$ which are vertices of $H$. Same for those $r_j$.

Finding convex hulls can be done in $O(n \log n)$ time, c.f. wiki page.

The problem is then: how many vectors still remain after this procedure.

Under certain assumptions, e.g. the vectors are uniformly distributed, this reduction could be good enough to allow a brute force on the remaining vectors.

Here is another idea.

Key observation:

Let $O$ be the origin in $\mathbb{R}^4$. Let $H$ be the convex hull of the set $\{O\} \cup \{l_i : 1 \leq i \leq n\}$. Then one may only consider those $l_i$ which are vertices of $H$. Same for those $r_j$.

Finding convex hulls can be done in $O(n \log n)$ time, c.f. wiki page.

The problem is then: how many vectors still remain after this procedure.

Under certain assumptions, e.g. the vectors are uniformly distributed, this reduction could be good enough to allow a brute force on the remaining vectors.

More precisely, if the vectors are uniformly distributed, then it is known e.g. from this paper that the number of remaining vectors is, in average, $O((\log n)^3)$, which is quite small.

I have the following simple observation:

If, for two different $l_i$ and $l_j$, the projection of $l_i$ on the line of $l_j$ is longer than $l_j$, then one can remove $l_j$ from the list of $l$'s, since $l_i$ will always be a better choice. Same for the $r$'s.

Under certain heuristic assumptions (e.g. the vectors are uniformly distributed in $[0, 1]^n$), this could remove a lot of vectors, so that brute force might be applicable to the remaining. This gives a heuristic algorithm, which may or may not solve your practical problem, depending on the nature of your vectors.

The worst case would be when your vectors are almost all on a sphere.

Here is another idea.

Key observation:

Let $O$ be the origin in $\mathbb{R}^4$. Let $H$ be the convex hull of the set $\{O\} \cup \{l_i : 1 \leq i \leq n\}$. Then one may only consider those $l_i$ which are vertices of $H$. Same for those $r_j$.

Finding convex hulls can be done in $O(n \log n)$ time, c.f. wiki page.

The problem is then: how many vectors still remain after this procedure.

Under certain assumptions, e.g. the vectors are uniformly distributed, this reduction could be good enough to allow a brute force on the remaining vectors.