Challenge: expressing log(log(1/(1 - e^x))) in cvx

The function log log 1/(1 - e^x) = log (\sum_{k > 0} e^{kx}/k) is convex: it is a log-sum-exp with an infinite sum, in its natural domain x < 0, i.e. where the inner logarithm can be expressed as a power series.
Alternatively, instead of expressing this function f(x), it is possible to ask to express its epigraph f(x) <= t as a convex set in cvx rules.
I would prefer to avoid the infinite sum because of convergence issues. Is there any other way to express this problem in a canonical form? I tried various substitutions for the exponential cone, but no success.

This is essential for one combinatorial construction in our paper


At some point, one of the MOSEK staff members who read this forum should see this thread and be able to disposition this one way or another.

In the meantime, look at section 5.2 of the MOSEK Modeling Cookbook for some ideas.

Here is a somewhat similar, although concave expression, which no one of the forum has really figured out how to do. Log(log(1+exp(x)) objective function

Concerning the function presented by the link. The inverse function mentioned there, log(exp(exp(x)) - 1) is also of interest in our paper, it corresponds to another combinatorial construction that we would like to cover, i have no ideas about it neither.

The function log(exp(exp(x)) - 1) was already considered in this post, where (6e) is rewritten to (11) which is log-sum-exp + this function. Our conclusion in post #12 has unfortunately not changed, but we do try to keep track of the open questions.

1 Like

The other one
t \geq \log(\log(1/(1 - \exp(x))))

can be rewritten as
x \leq \log\left(1 - \frac{1}{\exp(\exp(t))}\right)

which is equivalent to
x \leq \log\left(1 - \frac{1}{r}\right),\quad r = \exp(\exp(t))

where the former is just a simple set. Unfortunately, the latter cannot be relaxed to r \geq \exp(\exp(t)) as r would just fly off to infinity relaxing the implications on x – i.e., the composition rules are violated :frowning:

This may be another one of those sets I don’t know how to represent…

Ok, in your last attempt you are substituting a convex function \exp(\exp(t)) > 1 into a concave increasing \log(1 - 1/r) which is not allowed by cvx. Alternatively, in the initial formulation it is also impossible because the resulting function cannot be represented as a composition of convex ones.

Well, I give up at this point. I personally believe that these two functions cannot be expressed using the exponential cones. But I am not sure that the rigorous proof of this statement can be useful somewhere. As you guys have said in a different thread somewhere, let us stop chasing unicorns and let’s try to go write some self-concordant barriers :smiley:


1 Like

If someone can come up with self concordant barriers then we at Mosek are very interested.

We have other interesting sets we do not know a barrier for as well.

According to my findings, a usual logarithmic barrier with self-concordance parameter m will cover the part x > -C m, (C around log 10 natural base?) this is just an empirical observation combined with some lemmas from Nesterov/Nemirovski. Using some additional knowledge about my specific problem I conclude that if I take m large enough, this is sufficient for me, but in general, I don’t know how to construct a self-concordant barrier for this one, covering all the ray R^{-}. I suspect that for the inverse function of log(exp(exp(x))-1) the situation should be similar.

Can someone snap a picture of this problem so that we can get the answer from the Microsoft Math Solver ?

Hi there

Following the discussion: we have uploaded a paper on arxiv that discusses the two functions (as a part of restricted CYC and SET combinatorial constructions).

I only give empirical treatment and justify it in the necessary range. I suspect that the second one, log exp exp -1 has a self-concordant logarithmic barrier in the full range (but we don’t give the proof of that). This information can be however useful to others.

Please tell me if this is relevant.


We will read it with great interest.