I have a quadratic program: $$\displaystyle\min_{\mathbf{X}} (\mathbf{X^TQX +C^TX}) \quad{} \text{subject to} \quad{} \mathbf{A X \leq Y}$$ $\mathbf{Q}$ is positive definite and is $N \times N$, $\mathbf{A}$ is $M \times N$ and $\mathbf{X}$ is an $N \times 1$ vector. I'm trying to compute the complexity in terms of multiplications, but can not figure out how to approach it. I'd appreciate it if anyone can provide help/guidance or any references I can check.
I'm using the interior point convex algorithm.
[Math] Complexity of a quadratic program
computational complexitylinear algebraoptimization
Best Answer
You asked for references...Convex Optimization by Boyd and Vandenberghe is a good jumping-off point. It's available online, at
http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
(be forewarned, it's a large PDF.) See in particular the start of section 11.8...what you do will partially depend whether Q is sparse.