Coordinate descent for box-constrained quadratic program

259 Views Asked by At

Given the vector ${\bf b} \in \Bbb R^n$ and the symmetric positive definite matrix ${\bf Q} \in \Bbb R^{n \times n}$, $$\begin{array}{ll} \text{minimize} & \frac12 {\bf x}^T {\bf Q} \, {\bf x} - {\bf b}^T {\bf x}\\ \text{subject to} & \bf 1 \le x \le u\end{array}$$ Applying a coordinate descent algorithm, assume that the current solution is $\hat{x}$ and the next coordinate to update in the algorithm is $i$. Give an expression for the next iterate.