Quickly finding optimal subset of pairs of numerator and denominator terms for special objective functions

Question

Given a multi-set of pairs $((a_i,b_i))_{i \in Y}$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the optimal combination of pairs defined by $I^* \subseteq Y$, which maximizes an objective of the form

$\max_{I \subseteq Y} F(\sum_{i \in I} a_i) / G(\sum_{i \in I} b_i)$

where $F,G$ are positive strictly increasing for positive inputs. I have some specific examples I've encountered in my past research. One is

$F(x) = x, G(x) = x + A$

where $A$ is positive. For this, it is very easy to show that there is a fast solution, namely sort all pairs $(a,b)$ according to $a/b$ in decreasing order, and then try all subsets of the first $k$ pairs in sorted order, for all $k$. Whatever $k$ gives the best solution gives the global optimal combination of pairs.

Interestingly, in another application I found that the exact same algorithm works for a more complicated case:

$F(x) = x, G(x) = \sqrt{x}$

and the proof is a bit harder, but not too bad, and it's surprising (at least to me) that you sort pairs $(a,b)$ according to $a/b$ even though the denominator function is non-linear (my original conjecture was that you sort according to $a/\sqrt{b}$ but this doesn't work). So this got me thinking, is there a general class of pairs of functions $F,G$ where this algorithm works when you sort according to $a/b$, or perhaps where you sort pairs according to $H(a,b)$ where $H$ depends on $F$ and $G$? I know that for arbitrary positive strictly increasing $F,G$ (i.e. $F,G$ are part of the input, even if given by a finite description instead of an oracle) the optimization problem is NP-hard because you can reduce the subset-sum problem to it. So I'm basically looking for as general of a class of pairs of functions $F,G$ as possible, where the sort-and-scan approach works.

Answer 1

One general class of functions I have just found, perhaps a hint as to an even more general class, where the sort-and-scan approach works, (sorting pairs $(a,b)$ decreasing by $a/b$) is $F(x) = x$, and $G(x) = x^\gamma$ for any power $0 < \gamma < 1$ (subsuming one of the given examples when $\gamma = 1/2$). Hopefully someone else can come up with an even more general class with a proof though.

Update: Requested proof (and note the claimed class of functions has been reduced to just a parametrized family because I realized a small gap in the original proof that just assumed $G'(x)/G(x) \leq \beta/x$ for some $\beta < 1$).

For $G = x^\gamma$, $0 < \gamma < 1$, and $F(x) = x$, let $A,B$ be positive, and consider a pair of terms $(a_i,b_i)$. Take the derivative of $F(A + \alpha a_i) / G(B + \alpha b_i)$ with respect to $\alpha$, this is $a_i/G(B + \alpha b_i) - b_i(A + \alpha a_i)G'(B + \alpha b_i)/(G(B + \alpha b_i))^2$, and since $b_i, G$ are positive we can multiply by $G$ and divide by $b_i$ to get the following term which has the same sign as the derivative: $H(\alpha) = a_i/b_i - \gamma (A + \alpha a_i)/(B + \alpha b_i)$, where recall $\gamma < 1$. $H(\alpha)$ is the expression we will work with to establish two facts that complete the proof. Suppose that we have a non-empty solution of pairs giving $A = \sum_{i \in I} a_i$ and $B = \sum_{i \in I} b_i$, and we have a pair $(a_i,b_i)$ not in the solution. Firstly, if $a_i/b_i \geq A/B$, then clearly $H(\alpha) > 0$ for all $\alpha > 0$, so adding $(a_i,b_i)$ to the solution will increase the objective. Alternatively, suppose $a_i/b_i < A/B$ and adding $(a_i,b_i)$ to the solution increases the objective, and suppose there is another pair $(a_j,b_j)$ ($j \neq i$) not included in the solution which satisfies $a_j/b_j \geq a_i/b_i$. Then if we add both pairs to the solution, the objective is greater than or equal to $F(A + \alpha_0 a_i) / G(B + \alpha_0 b_i)$ for $\alpha_0 = (b_i + b_j)/b_i > 1$. Note $H(\alpha)$ is increasing for $\alpha > 0$ because $A/B > a_i/b_i$. Furthermore $H(\alpha)$ must be positive for some positive $\alpha < 1$ because $F(A + a_i)/G(B + b_i) > F(A)/G(B)$ by assumption. Thus the derivative is positive for all $\alpha \in [1, \alpha_0]$, so additionally adding $(a_j,b_j)$ to the solution further increases the objective. These two facts prove that the optimal solution must have the property that when you sort pairs decreasing according to $a/b$, the optimal solution must be the first $k$ pairs for some $k$.

Answer 2

I found a paper by DB Neill, published in 2012, http://www.cs.cmu.edu/~neill/papers/jrssb2012.pdf‎, which claims that if $F(A,B)$ is a function defined for positive inputs which is weakly increasing in $A$ for fixed $B$, and quasi-convex as a function of $A$ and $B$, then the optimal solution for

$\hbox{argmax}_I F(\sum_{i\in I}a_i,\sum_{i\in I}b_i)$

(for positive $a_i,b_i$) is given by the subset of top $k$ pairs $(a_i,b_i)$ for some $k$ when pairs are sorted according to $a_i/b_i$ in descending order. However I believe I found a gap in the proof, and it seems that all subsets of size $1$ need to be considered in addition to all subsets of top $k$ pairs. The function $F(X,Y)=1/Y$ gives such an example. But it is still a very fast "linear time subset scan" even if all subsets of size $1$ need to also be checked. Anyway, this is the most general example I've been able to find and it satisfies my desire to find "general properties" of objective functions where the sort-and-scan approach or something very similar works.