I'm trying to solve the following bounded quadratic optimization problem.
\begin{equation} \min_{x} \frac{1}{2}x^TAx+b^Tx \end{equation} \begin{equation} \textrm{s.t. }\\ x \geq 0 \end{equation}
Where $A$ and $b$ are block matrices given by:
\begin{equation*} A = \frac{1}{2}\begin{bmatrix} GD^{-1}(GD^{-1})^T & -GD^{-1}(GD^{-1})^T \\ -GD^{-1}(GD^{-1})^T & GD^{-1}(GD^{-1})^T \\ \end{bmatrix} \end{equation*} \begin{equation*} b = \begin{bmatrix} GD^{-1}p \\ c-GD^{-1}p \\ \end{bmatrix} \end{equation*}
$G \in \mathbb{R^{m\times n}}$ is a sparse matrix.
$D \in \mathbb{R^{n\times n}}$ is a circulant and symmetric matrix.
$p \in \mathbb{R^{n\times 1}}$ is a vector with elements all between $0$ and $1$.
$c \in \mathbb{R^{m\times 1}}$ is a vector consisting entirely of $1$'s.
$x \in \mathbb{R^{2m\times 1}}$ is the vector that i'm trying to find.
At the moment I'm solving this numerically, but it's extremely slow because $G$ and $D$ are large matrices. However, I'm sure I can exploit the fact that $D$ is symmetric and circulant by using fast Fourier transforms (FFT's) somehow. I can't figure out how.
-------------- EDIT -------------
I've just discovered that $A$ is positive definite and circulant and symmetric! This means I can rapidly calculate $Ax$ using FFTs. What algorithm can I use to exploit this feature?