0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ One of the reasons people study convex optimization problems so extensively is be cause we have fast algorithms for solving them. $\endgroup$
    – CyclotomicField
    Mar 11, 2022 at 1:35
  • $\begingroup$ @CyclotomicField I agree with you. That's why I study convex optimisation. But obviously not all convex optimisation problems can be solvable in polynomial time complexity. I'd like to know the specific problem (the minimisation of log-sum-exp function) is also in the category that we can say "we have fast algorithms for this", and "which algorithms are fast enough for this". $\endgroup$
    – Jinrae Kim
    Mar 11, 2022 at 1:41
  • $\begingroup$ You say that they obviously can't when I just told you we can. Convexity is a strong property and essentially turns every problem into linear regression. It's super fast. $\endgroup$
    – CyclotomicField
    Mar 11, 2022 at 1:51
  • $\begingroup$ @CyclotomicField If you don't mind, could you share any references for that? $\endgroup$
    – Jinrae Kim
    Mar 11, 2022 at 1:54
  • $\begingroup$ web.stanford.edu/~boyd/cvxbook is a good start and there are a series of video lectures by Boyd as well that covers the material extensively. Also, if you find it defies intuition I would simply say that convexity and lines are intimately linked from a geometric standpoint. This should at least hint as to why we can linearize these problems. $\endgroup$
    – CyclotomicField
    Mar 11, 2022 at 2:21

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .