La complejidad de una ecuación cuadrática programa

Question

Tengo un cuadrática programa: $$\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. Estoy tratando de calcular la complejidad en términos de multiplicaciones, pero no puede averiguar cómo acercarse a él. Agradecería si alguien puede proporcionar ayuda/orientación o cualquier referencia que pueda comprobar. Estoy usando el punto interior convexo algoritmo.

Answer 1

Usted pidió referencias...de Optimización Convexa por Boyd y Vandenberghe es un buen punto de partida. Está disponible en línea, en

http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

(ten en cuenta, es un PDF de gran tamaño.) Véase, en particular, el inicio de la sección 11.8...lo que hacen parcialmente, depende si Q es escasa.