High dimensional quadratic programming problem

ROOT
1

Hi,

I’m using the GondzioSolver to solve a high dimensional quadratic programming problem, with a number of variables between 5,000 and 10,000, and with 1 equality and 0 inequality equations
The problem is that takes a lot of time to solve the problem. I tested with smaller number of variables and got this times:
N_______________TIME
1000____________4 seconds
2000____________44 seconds
4000____________340 seconds

Is too much time. There are any way to do the solver execution faster? or maybe I’m doing something wrong?

Thanks in advance!!

2

Hi,

I think the ROOT quadratic programming solvers do not have special handling in case of large number of parameters, so since they are based on non-sparse matrices, it is probably expected to observe a quadratic behaviour in the CPU time.
There might exist some special packages on the Web, although probably the good one requires a commercial license (e.g. Nag).
See for example en.wikipedia.org/wiki/Quadratic … _languages

Best Regards

Lorenzo

3

Thank you so much Lorenzo, for your quick and helpfull answer :slight_smile:
If no one knows something more about this then I’ll try with some other libraries. If is possible to use this one, would be great, but of not I’ll continue looking for options :slight_smile:
Selmo

4

Hi Selmo,

Symmetric Sparse matrices are part of the Linear Algebra classes in ROOT : TMatrixDSparse
and yes the quadratric programming can handle them.

Have a look at this tutorial where it is shown for dense and sparse matrices.

root.cern.ch/root/html604/tutor … lio.C.html

The underlying quadratic package is based on:

pages.cs.wisc.edu/~swright/ooqp/ … rguide.pdf

  • Eddy
5

Hi Eddy!!
I followed that tutorial to write my class, and I think the library is working well. With 1,0001,000 matrices I have good results, but the time when I try with my real problem, between 5,0005,000 and 10,000*10,000, is too high. My matrices are dense.
Do you think it should take less time?
Thanks a lot!!

6

Hi Selmo,

If I understand it correctly your matrices has “dense entries” and therefore switching to a sparse matrix
has no benefits. The quadratic programming algo is the interior-point method which is supposed to
be quite optimal .

I think that given the size of your matrix you should expect bigger elapse times #-o .

-Eddy

7

Hi Eddy,

Thank for you reply, actually the matrix we have is a correlation matrix which have non-zero value for almost every entries. Those correlation values are significantly differ than 0, so a sparsification wont work. And the quadratic form is very standard with only linear constraint

Is primal dual interior-point based methods work effectively for this kind of problem?

We have tried NAG library for this problem as well, their library is very fast (could solve the problem in couple of seconds). I read their document their algorithm is so called two phase (primal) sequential quadratic programming (check sbsi-sol-optimize.com/asp/so … _lssol.htm). It is actually using a solver of least square problem.

Is there any function in ROOT that related to sequential quadratic programming problem in a similar sense?

8

Hi Selmo,

It sounds to me that the OOQP approach is an over kill for you problem, there are no
inequality constraints.

Why don’t you perform a least squares optimization with a Lagrangian multiplier that
takes your equality constrain into account. ROOT has several packages for that TMinuit(2)
and I believe RooFit.

-Eddy