I am trying to solve problem as follows: \begin{equation} \begin{split} &\mathop{min} \limits_{\textbf{x}_1...\textbf{x}_k} \ \frac{1}{2}\textbf{x}_1^T\textbf{Q}_1\textbf{x}_1+\textbf{q}_1^T\textbf{x}_1+...+\frac{1}{2}\textbf{x}_k^T\textbf{Q}_k\textbf{x}_k+\textbf{q}_k^T\textbf{x}_k \\ &s.t. \textbf{A}_i\textbf{x}_i \le \textbf{b}_i \end{split},\ \ (1) \end{equation} where $\textbf{x}_i \in \mathbb{R}^n,\textbf{Q}_i \in \mathbb{R}^{n \times n}$ is diagonal and positive definite matrix, $\textbf{A}_i \in \mathbb{R}^{m \times n}$ is sparse matrix.
Problem (1) can be also rewritten as follows:
\begin{equation} \begin{split} &\mathop{min} \limits_{\textbf{x}_1...\textbf{x}_k} \ \frac{1}{2}\begin{bmatrix} \textbf{x}_1^T ... \textbf{x}_k^T\end{bmatrix} \begin{bmatrix} \textbf{Q}_1 & & \\ & ... & \\ & & \textbf{Q}_k \end{bmatrix} \begin{bmatrix} \textbf{x}_1\\ ...\\ \textbf{x}_k\end{bmatrix} + \begin{bmatrix} \textbf{q}_1^T ... \textbf{q}_k^T\end{bmatrix}\begin{bmatrix} \textbf{x}_1\\ ...\\ \textbf{x}_k\end{bmatrix}\\ &s.t. \begin{bmatrix} \textbf{A}_1 & & \\ & ... & \\ & & \textbf{A}_k \end{bmatrix}\begin{bmatrix} \textbf{x}_1\\ ...\\ \textbf{x}_k\end{bmatrix} \le \begin{bmatrix} \textbf{b}_1\\ ...\\ \textbf{b}_k\end{bmatrix} \end{split}.\ \ (2) \end{equation}
Since matrices in problem (2) are too large, and saving them usually leads to problem of out of memory, then I tend to solve k sub-problems as follows: \begin{equation} \begin{split} &\mathop{min} \limits_{\textbf{x}_i} \ \frac{1}{2}\textbf{x}_i^T\textbf{Q}_i\textbf{x}_i+\textbf{q}_i^T\textbf{x}_i \\ &s.t. \textbf{A}_i\textbf{x}_i \le \textbf{b}_i \end{split},\ \ (3) \end{equation} problem (3) can be solved by Augmented Lagrangian Method, whose algorithm can be roughly described as repreating the following three steps until convergence.
1.$\textbf{x}_i^{k+1}=\mathop{argmin} \limits_{\textbf{x}_i} \ L_{C_i}(\textbf{x}_i, \lambda_i)$
2.update $\lambda_i$
3.update $C_i$
However, for each sub-problem, if newton method is applied in step1 ($\textbf{x}_i^{k+1}=\mathop{argmin} \limits_{\textbf{x}_i} \ L_{C_i}(\textbf{x}_i, \lambda_i)$), in each iteration, it takes $O(n^3)$ to calculate the inverse of $L_c$'s Hessian matrix ($\textbf{Q}_i+C_i\textbf{A}_i^T\textbf{D}_i\textbf{A}_i$, where $\textbf{D}_i$ is a diagonal matrix). Therefore, solving problem (1) is very time consuming.
I guess problem (1) is frequently seen, and is there a faster way to solve it? Any help is appreciated.