I'm trying to find out some theoretical guarantees of time complexity for my problems.
My problem is to minimise a log-sum-exp function.
I found that the minimisation of log-sum-exp function can be transformed into a conic program with exponential cone as described in Mosek documentation.
Is the conic program with exponential cone solvable in polynomial time? If so, which algorithms can be used to solve the problem in polynomial time?
Is the minimisation of log-sum-exp function actually transformed into an equivalent conic program with exponential cone in real-world solvers? (e.g., cvxpy)
Sorry for my lack of background.
Best Answer
In a DCP (Disciplined Convex Programming) tool like CVXPY, CVX or similar, a function like log-sum-exp will be converted to conic form as in the modeling link you found, because that is the form accepted by the underlying solvers.
The algorithm used by MOSEK for exponential cone optimization is presented in this paper https://link.springer.com/article/10.1007/s10107-021-01631-4. There is no polynomial complexity proof like for SOCP known for this algorithm. The algorithm seems to perform well in practice though.