Time complexity of MOSEK solver in CVX

1

Hi there,

I am using CVX with MOSEK as the main solver. I am a bit confused about time complexity of interior point in the MOSEK. I think when I increase the number of constraints (not variables) from 10^4 to 10^5, the needed time for solving the optimisation problems grows exponentially. Is it correct? Where can I find the find something about time complexity of interior point method and its relation with increasing number of constraints?

Best

2

See

1 Like
3

Thanks for the to-the-point answer.

I read the text carefully. The obtained complexity is for the case, in which d <= n, i.e., number of constraints are less than or equal to the degree of the problem (number of decision variables). It means that A is a row rank matrix.

Now, I just have a question:
If d >= n (It means that number of constraints are bigger than decision variables), we can have the same argument but for the dual problem. Then, we can suppose that complexity of both of them are the same. Am I right?
If not, how can I deduce the complexity for the case where d>=n?

Best,
Ali

4

You convert your problem to my form by adding slack variables or you can form the dual if you like that.
It should lead to more or less the same iteration complexity.

1 Like