Theoretical computation complexity of quadratic program

wang lingyi

unread,

Oct 4, 2022, 1:37:39 AM10/4/22

to mosek

Hi,

I am currently using Mosek within matlab to solve a quadratic program (QP). I am comparing the computation complexity of two optimization problems, denoted as A,B respectively. And the number of variables and constraints of the two problems are not the same. A have 20% more variables than B but 18% less constraint number then B. I am curious that is there any big O notation time complexity of QP, indicating whether the number of variables or constraint number are more important in deciding the computation time. I know that sparsity of the optimization problem is an important factor, but take this aside, I am just curious about the big O notation time complexity of QP, which decides whether number of variables or constraint are more important. Any advice would help. Thank u!

Erling D. Andersen

unread,

Oct 4, 2022, 1:42:07 AM10/4/22

to mosek

Let

v = number of linear inequalities + 2*(number of quadratic conic constraints)

then the number iterations is O(sqrt(v)). One iteration can be done in O(n^3) operations where n is the number of variables.

For a QP you should only have 1 quadratic conic constraint.

wang lingyi

unread,

Oct 4, 2022, 7:11:24 AM10/4/22

to mosek

Thank u for your reply. Then I could probably use the index "sqrt(v)*n^3" as a rough indicator of the computation complexity (iterations), put aside the sparsity of problem. Is that right?

Erling D. Andersen

unread,

Oct 4, 2022, 9:45:03 AM10/4/22

to mosek

Yes.

wang lingyi

unread,

Oct 11, 2022, 9:44:16 AM10/11/22

to mosek

Thank u

wang lingyi

unread,

Oct 11, 2022, 11:26:22 PM10/11/22

to mosek

Is there any reference paper or manual that discusses the above theoretical complexity (big O notation)? I just want to know more about it.

在2022年10月4日星期二 UTC+8 21:45:03<e.d.an...@mosek.com> 写道：

MOSEK No-Reply

unread,

Oct 12, 2022, 12:43:16 AM10/12/22

to mosek

Since you have a conic quadratic problem then you can read the original papers by Nesterov and Todd about algorithms for self-scaled cones.

Erling D. Andersen

unread,

Oct 12, 2022, 2:29:52 AM10/12/22

to mosek

I used Google scholar to look it up and got to

https://pubsonline.informs.org/doi/abs/10.1287/moor.22.1.1

Erling D. Andersen

unread,

Oct 12, 2022, 2:30:38 AM10/12/22

to mosek

Btw I know you have a QP, but there is no specialized QP alg. that will give a better result.

wang lingyi

unread,

Oct 12, 2022, 2:30:53 AM10/12/22

to mosek

Thank u for your reply. What's the full title of the mentioned paper?

wang lingyi

unread,

Oct 12, 2022, 6:57:09 AM10/12/22

to mosek

thank u for your reply. I have read through that paper, but it seems that I cannot find the " One iteration can be done in O(n^3) operations where n is the number of variables" since I am not familiar with optimization theory. May I trouble you to tell me which page mainly discuss it? Thank u

Erling D. Andersen

unread,

Oct 13, 2022, 12:28:02 AM10/13/22

to mosek

See

https://erlingdandersen.blogspot.com/2013/11/complexity-of-solving-conic-quadratic.html

ximeng fan

unread,

Dec 10, 2022, 2:21:14 AM12/10/22

to mosek

May I ask one more question? From your answer, it seems that equality constraints will not impact the complexity?

Thank you for your time, and look forward to your reply.

Erling D. Andersen

unread,

Dec 12, 2022, 1:37:12 AM12/12/22

to mosek

In practice, it will increase the work per iteration, but the number of iterations should be unchanged.

ximeng fan

unread,

Dec 28, 2022, 2:20:45 AM12/28/22

to mosek

Thank you so much for your reply! I even did not expect such a quick response.

Thus, can I say that the greater the number of iterations, the higher the computation complexity?

Thank you again!

Reply all

Reply to author

Forward