User norouzi - MathOverflow

Convex upper bound on a linear-fractional function

2012-12-05T23:18:34Z

I have a function of the form $f(x,y) = \frac{x}{c+y}$ where $c$ is a positive constant, $c \ge x \ge 0$, and $y \ge 0$. I would like to find a convex upper-bound for this function. Is there a principled way for doing this? How about if the upper-bound has to be convex and piecewise linear? Is there a way to find the optimal upper-bound in terms of the number of linear pieces?

Update: Sorry I changed the boundary conditions on $x$ and $y$ so it suits my problem better.

Answer by Norouzi for Convex upper bound on a linear-fractional function

2012-12-06T16:29:47Z

Not exactly the answer, but I think $g(x,y) = \frac{x^2}{(c+y)^2}$ is a reasonable convex lower-bound for $f$. With the assumption that $c \ge x$, then $1 \ge f(x,y) \ge 0$, and so $f(x,y)^2 \le f(x,y)$.

Answer by Norouzi for Seeking a solution algorithm to the 3-partition problem

2011-12-01T15:31:43Z

There exists a pseudo-polynomial time dynamic programming solution to this problem, for which running time and storage complexity depend on the sum of costs of the pieces of jewelry, denoted $S$. If the sum of costs, $S$, is small then the algorithm would be practical as its storage is $O(S^2)$ and its running time is $O(S^2N)$, $N$ being the number of pieces (48 here).

To get a sense of the algorithm take a look at the Subset sum problem Wikipedia page--dynamic programming solution. This concerns finding a subset of items which sums to a particular cost. Clearly you can solve the 2-partition problem by using the subset sum solutions, i.e., by enumerating over all the potential subset sums, and choosing the one that you prefer for any reason.

Now generalizing to 3-partition is straightforward. You basically solve the double-subset sum problem. You store $Q(i,s, t)$ to be the value (true or false) of "whether there are two disjoint subsets of $x_1, \ldots, x_i$ which respectively sum to $s$ and $t$". You can easily update $Q(i, s, t)$ by adding new items. Again one can enumerate over the potential $Q(N, s, t)$'s and choose the one that is considered best.

Obviously even if $S$ is large, the costs can be quantized using larger cost units, which results in a measurable upper bound on the error. This also can be used combined with the solution of Brendan McKay to guide a local search algorithm.

An optimization problem involving sum of binomial coefficients upto some value

2011-11-20T03:16:20Z

I would like to minimize $f(s, n, \epsilon)$ with respect to $s$ where $$f(s,n,\epsilon) = \left( 1 + \frac{n}{2^s} \right)\frac{1}{s} \sum_{k=0}^{\lfloor s\epsilon \rfloor} {s \choose k}~.$$ Note that $0 < \epsilon < \frac{1}{2}$ and $n > 0$. Clearly optimal $s$ is going to be a function of $\epsilon$ and $n$, which might be ugly. However, I think $s^*$ should be close to $\log_2{n}$, based on the intuition from the problem giving rise to this, but I cannot find any rigorous argument for this choice of $s^*$. Any hint or idea is highly appreciated.

The following upper bound might be helpful: $$ \sum_{k=0}^{\lfloor s\epsilon \rfloor} {s \choose k} \le 2 ^ {H(\epsilon)s } $$ where $H(\epsilon) \equiv -\epsilon \log \epsilon -(1-\epsilon) \log(1-\epsilon)$; the entropy of a Bernoulli dist. with probability $\epsilon$.

I don't know of any clean lower bound. Any idea?

Thanks for your time in advance.

Comment by Norouzi

2012-12-06T03:17:52Z

The function f is quasiliner. It has convex parts eg. when one sets $x=1$ and only varies $y$, $f(x,y) = f(y) = \frac{1}{c+y}$, and concave parts, eg. when one sets $y = x$, and so $f(x,y) = f(x) = \frac{x}{c+x}$. I would like to find a convex upper-bound for $f$ if possible.

Comment by Norouzi

2011-11-21T02:49:24Z

Thanks! How about if n or s doesn't go to infinity. Can we still say something?

Comment by Norouzi

2011-11-21T01:03:51Z

Great! Let me know if you have some insight.