Partition of two sets for multi-line fitting, NP-hard?

Question

Given two sets of nonnegative numbers $X=\{x_1,...,x_n\}$ and $Y=\{y_1,...,y_n\}$, my problems consists in finding the partition $S \subseteq \{1,...,n\}$ and $\bar{S}=\{1,...,n\}\backslash S$ maximizing the following quantity: $$\frac{\displaystyle\left(\sum_{i\in S}x_iy_i\right)^2}{\displaystyle\sum_{i\in S}x_i^2}+\frac{\displaystyle\left(\sum_{i\in \bar{S}}x_iy_i\right)^2}{\displaystyle\sum_{i\in \bar{S}}x_i^2}.$$

Question: is this problem NP-hard ?

I tried many things, for example the particular case where $y_i=1-x_i$ which is easy because this amounts to sort the set X and testing the various possible partitions in that order.

And when I search the web, I only find references to the famous PARTITION problem, but I don't see how this problem could be related to mine.

Thanks for any help!

EDIT: (as requested in the comments, here is an explanation of the origin of the problem)

Let $\{(x_1,y_1),...,(x_n,y_n)\}$ be a set of $n$ points in the nonnegative orthant. I want to partition this set of points such that the first part is fitted by the equation $y=\beta_1x$ and the other part is fitted by the equation $y=\beta_2x$ using the ordinary least squares.

To paraphrase, I want to find the partition $S \subseteq \{1,...,n\}$ and $\bar{S}=\{1,...,n\}\backslash S$ (and the corresponding $\beta_1$ and $\beta_2$) minimizing $$\min \sum_{i\in S}(y_i-\beta_1x_i)^2+\sum_{i\in \bar{S}}(y_i-\beta_2x_i)^2.$$

Given $S$, the closed-form solution for $\beta_1$ is $\beta_1=\frac{\sum_{i\in S}x_iy_i}{\sum_{i\in S}x_i^2}$ (same for $\beta_2$ with $\bar{S}$) and by using these values and developping the objective function, we obtain the problem described above.

Answer 1

This problem can be solved in polynomial time in the manner alluded to by Yves Daoust in a comment. Specifically, I'll show that there exists an optimal solution in which every input point "above" some line through the origin can be placed in one part, and every other point in the other. This enables a simple algorithm involving $n-1$ steps, in each of which we guess the location of the threshold line to be between the $i$-th and $(i+1)$-th points taken in increasing order of angle from the $x$ axis, form the two parts accordingly, and optimise each part separately using least squares as usual; the solution with the lowest sum of costs is overall optimal. A slight wrinkle is that points on the $y$ axis can be assigned to either part without affecting the outcome, but this only makes it easier to find an optimal solution: We can ignore these points initially, then add them to either part at the end. This also conveniently avoids having to deal with infinite gradients.

What made the optimality of this algorithm challenging to show was actually the amount of "detail" in the objective function of the original problem statement, caused by the (usually desirable) fact that the $\beta_i$ parameters were "hidden" (replaced with their closed-form optimal solutions). I wasn't able to make progress on that original problem statement. Once I focused on the later expression explicitly involving $\beta_i$, the proof was much easier. The key is to treat $\beta_1$ and $\beta_2$ as being given, rather than being implicit quantities inferred from the data. What I in fact show below is that, for any fixed pair of distinct slopes $\beta_1$, $\beta_2$, all optimal solutions partition the input points on either side of the line through the origin with gradient $(\beta_1+\beta_2)/2$, with free choice of part for points lying exactly on this line. Any solution for given $\beta_1$, $\beta_2$ that violates this can be strictly improved by changing the part assignment of the erroneous points without changing $\beta_1$ or $\beta_2$, and this suffices to rule out such solutions from optimality (the fact that $\beta_1$ and $\beta_2$ can be reoptimised after "fixing" the partition to further improve the total cost is actually irrelevant to the proof). In particular, this rules out all "nonconvex" solutions -- that is, solutions in which the assigned partition changes more than once when considering points in increasing angular order.

Proof sketch

Assume w.l.o.g. that $\beta_1 < \beta_2$.

In the expression $$\min \sum_{i\in S}(y_i-\beta_1x_i)^2+\sum_{i\in \bar{S}}(y_i-\beta_2x_i)^2$$ each $(x_i, y_i)$ participates in exactly one of two ways: either as $(y_i-\beta_1x_i)^2$, or as $(y_i-\beta_2x_i)^2$. Choosing the smaller of these independently for each $i\in S$ is sufficient to minimise the entire expression. For simplicity I'll drop the subscripts on $x$ and $y$.

I'll now show that $y/x < (\beta_1+\beta_2)/2$ implies $(y-\beta_1x)^2 < (y-\beta_2x)^2$.

\begin{align} &y/x < (\beta_1+\beta_2)/2\\ \implies& 2y < (\beta_1+\beta_2)x\\ \implies& y-\beta_1x < \beta_2x-y\tag{1} \end{align}

The RHS must be positive:

\begin{align} &y/x < (\beta_1+\beta_2)/2 < (\beta_2+\beta_2)/2 = \beta_2\\ \implies& \beta_2x-y > 0\tag{2} \end{align}

The LHS could be $< 0$, or $\geq 0$.

Case 1: $y-\beta_1x < 0\qquad(3)$ \begin{align} \implies& \beta_2x-y > \beta_1x-y > 0\textrm{, with the first > because }x > 0\textrm{ and }\beta_2 > \beta_1\\ \implies& (\beta_2x-y)^2 > (\beta_1x-y)^2\textrm{ since both sides of }\beta_2x-y > \beta_1x-y\textrm{ are positive by }(2), (3)\\ \implies& (y-\beta_2x)^2 > (y-\beta_1x)^2\textrm{ and we are done for this case.} \end{align}

Case 2: $y-\beta_1x \geq 0\qquad(4)$ \begin{align} \implies& y-\beta_1x < \beta_2x-y\textrm{ from }(1)\textrm{ with both sides nonnegative by }(2), (4)\\ \implies& (y-\beta_1x)^2 < (\beta_2x-y)^2\\ \implies& (y-\beta_1x)^2 < (y-\beta_2x)^2\textrm{ and we are done for this case.} \end{align}

In both cases, we establish that $y/x < (\beta_1+\beta_2)/2$ implies $(y-\beta_1x)^2 < (y-\beta_2x)^2$. Similar reasoning shows that this claim also holds with the inequalities reversed. The two results together give a rule to decide which part to assign to each input point.