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$ Mar 11 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 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$ Mar 11 at 1:51
  • $\begingroup$ @CyclotomicField If you don't mind, could you share any references for that? $\endgroup$
    – Jinrae Kim
    Mar 11 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$ Mar 11 at 2:21

1 Answer 1

1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.