Conic formulation for this concave beast involving log?


(Mark L. Stone) #1

Here is a challenge problem. I have no personal interest in it, but this was posted at https://mathoverflow.net/questions/303936/concavity-of-log-1-fracx-11x-1x-2-2x-3-4-1-fracx-21x-1-4x-2/303948#303947

\log \left[ \prod_{k=1}^{n}\left(1+\frac{x_k}{1+\sum_{j=0}^{n-1}q^jx_{k+j}}\right) \right], 0 \le x \le 1, 0 < q < 1

This appears to be concave for any n, and is concave for particular values of n per Maple. Is there a conic formulation? It seems tough. Note that if formulated as a sum of log terms, each log term is NOT concave individually, so it seems especially tricky.


(Mark L. Stone) #2

For n = 1, this can be formulated using the approach by @Michal_Adamaszek in Can CVX solve this kind of function {x-log(1+x/(x+1))} , resulting in log(2-inv_pos(1+x1))

If this can be extended to n >= 2, it looks tricky, if possible at all, because each additive log term is not concave, so it seems the whole function will have to be dealt with at once. Also, for high enough values of x (some amount greater than 1), the whole function is not concave, so it seems that will be a complicating matter in the formulation. Also, I believe for n >= 2, the argument of log is not concave, which suggests to me the approach in the 1st paragraph is a dead end for n >= 2.


(Michael C. Grant) #3

This is not the kind of problem I have any interest in whatsoever. It makes no sense to try and convert this to a comic form. This is one of those times when we need to resurrect a smooth convex solver, like Mosek’s original.