0
$\begingroup$

I am solving the dual QP of an SVM, and using the RBF kernel. As you know, the objective function is of the form $$f(\alpha) = \alpha^T Q \alpha $$ where $\alpha$ is the optimization variable and $Q$ is some positive semidefinite matrix. When $Q$ is dense, I wish to see what cvx (or any other optimization packages if you can point me to one) uses as $Q^{-1}$ when solving the QP. Any ideas?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

Optimization software needs to find inverse of the Hessian of the objective function which, in this case, coincides with inverting $Q$. This is by far the most costly operation. Here few things which people tried in the past.

1) Assume that Hessian is diagonal. Inverting diagonal matrix is straightforward.

2) Recalculate Hessian only once every $n=10,15, 50,100$ iterations.

Approaches above do not guarantee that you will always be in a feasible set, thus are not used in a general-purpose convex solver like CVX. This brings the following solution: calculate inverse by the most efficient way possible.

3) Calculate inverse using LQ decomposition which has the same complexity as finding inverse but lower constants. If I remember correct CVX uses LAPACK to for such decomposition.

$\endgroup$
1
$\begingroup$

Matrix inverse is always avoided for numerical reasons. The most common use of a matrix inverse in linear algebra is solving a linear system, which can be solved by better suited techniques like Gaussian elimination.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.