# Efficient algorithm for solving a convex quadratic program [duplicate]

Let $A \in \mathbb{R}^{n \times m}$ and $b \in \mathbb{R}^n$. Suppose $m \ll n$. How to solve this quadratic program efficiently?

$$\min_{x \in \mathbb{R}^n} \frac{1}{2} x^\top AA^\top x + b^\top x$$

• If b is not orthogonal to the kernel of the transpose of A the quadratic expression can get arbitrarily small. On the other hand if b is orthogonal to the kernel you can choose a base of the orthogonal complement and solve the corresponding linear equation. – user35593 Apr 16 '18 at 17:11
• @user35593 Could you elaborate more on finding the base of the orthogonal complement? – O. Richard Apr 16 '18 at 17:49
• thats actually the image of A. If A has full rank you can set x=Ay and minimize over y – user35593 Apr 16 '18 at 17:52
• See my answer here mathoverflow.net/a/244126/39129 – Cristóbal Guzmán Apr 16 '18 at 18:18

Using an SVD $A=USV^T$, and setting $y=U^Tx$, $c=U^Tb$, you can reduce the problem to a diagonal one $$\min_{y\in\mathbb{R}^n} c^Ty + \frac12 y^T S^2 y = \min_{y\in\mathbb{R}^n} \sum_{i=1}^n c_i y_i + \frac12 \sigma_i^2 y_i^2,$$ which should be trivial because the variables are separated. The whole algorithm costs $O(nm^2)$, assuming you are careful in representing $U$ as a product of rotations (which is not completely trivial to do in Matlab/Python/whatever you are using: in Matlab, you'd have to start with a QR factorization of $A$ [c,R] = qr(A,b), for instance, and then do an SVD of $R$; in Python, I am afraid you need numpy.linalg.qr with option raw). Or you can get $O(n^2m)$ if you just ignore the issue and use library SVD which returns a full matrix $U$.
• @O.Richard No, it's not optimal, but almost, in practice. It can't be less than $O(mn)$ anyway, because that's the time you need to read the matrix $A$. I think that using for the SVD the various nontrivial (and very impractical) algorithms for fast matrix multiplication you can lower it to $O(nm^{1.37})$, and it's an open problem whether it can go down to $O(nm^{1+\varepsilon})$. But on a real-world problem, I doubt they will give any improvement. – Federico Poloni Apr 16 '18 at 17:06
• Since you square $S$, I assume you're using the economy SVD. However, shouldn't the quadratic terms be summed till $i=m$ only? After all, $A$ is tall. – Rodrigo de Azevedo Apr 17 '18 at 13:27
• @RodrigodeAzevedo Good point --- the $\sigma_i$ are defined up to $m$ only; the rest can be taken to be zeros. The $c_i$ go up to $n$, though, and in particular there is no minimum if $c_i \neq 0$ for some $i>m$ (or whenever $\sigma_i=0$). This is more or less equivalent to what user35593 said in a comment above: $b$ must be in the range of $A$ for the minimum to exist finite. – Federico Poloni Apr 17 '18 at 14:30