1
$\begingroup$

I have a QP problem of the following kind:

$\min_{\alpha\in\mathbb{R}^n}\frac{1}{2}\alpha^T M \alpha - p^T\alpha$
s.t. $l\leq \alpha \leq u$

The matrix $M$ is symmetric and positive definite and of a special structure, such that for each submatrix M_{I,I}, $I \subset \{1,...,n\}$ I can calculate both $M_{I,I} x$ and $M_{I,I}^{-1}x$ in $\mathcal{O}(\#I)$ operations on a single core. Which algorithm will probably be most efficient to solve this until a given epsilon precision, and scales well with increasing $n$.

So far I have a coordinate descent that scales $n^2$ which is probably pretty inefficient.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Why using coordinate descent when you have the full gradient with similar cost? Try Nesterov's accelerated gradient and also check out projected Newton methods. If you want to use available toolboxes, search for "bound constrained convex quadratic" or "box" instead of "bound". $\endgroup$
    – Dirk
    Commented Apr 29, 2016 at 8:24

0

Reset to default

You must log in to answer this question.