MATLAB >> quadprog too slow

by hicham bouchnaif » Tue, 27 May 2008 19:14:02 GMT

Hi there
I am trying to solve a quadratic problem with linear
constraints using quadprog function. I get the solution but
it's just too slow .it takes about 10min to get the problem
solved.
the problem consists of 1000 (one thousand variables) and
the hessian matrix is a sparse matrix thus I guess the
problem should be solved much faster.
is it possible to make it faster by changing the options.I
tried suitching on the LargeScale option,but nothing
changed. does anyone have any idea?
thanx a lot in advance.


MATLAB >> quadprog too slow

by Johan Löfberg » Tue, 27 May 2008 20:58:02 GMT


Are the constraints sparse too?

Have you tried an alternative solver, such as clpmex,
bpmpdmex, ooqp

http://control.ee.ethz.ch/ ~joloef/wiki/pmwiki.php?n=Solvers.Solvers

Sparse problems of size 1000 is solved in ~10 seconds using
clp when I tried it


<g1gqdq$ns6$ XXXX@XXXXX.COM >...

MATLAB >> quadprog too slow

by hicham bouchnaif » Wed, 28 May 2008 09:29:02 GMT


yes the constraints are aparse too.


haven'tried yet but I d like to make the tool 100%matlab
for some technical reasons.

MATLAB >> quadprog too slow

by Johan Löfberg » Wed, 28 May 2008 17:25:05 GMT


<g1icgu$b2a$ XXXX@XXXXX.COM >...

The alternatives are interfaced to MATLAB, or do you mean
that you won't accept mex?

MATLAB >> quadprog too slow

by Stefan » Wed, 28 May 2008 19:07:02 GMT

Hi there,

maybe this helps:

http://sigpromu.org/quadprog/index.html

Regards,
Stefan

"Johan L?fberg" < XXXX@XXXXX.COM > wrote in
message <g1j8dh$nbj$ XXXX@XXXXX.COM >...

100%matlab

MATLAB >> quadprog too slow

by hicham bouchnaif » Thu, 29 May 2008 08:50:18 GMT

Hi Stefan
thanx for the link.
I think that QPC supports only dense matrices which means
that it doesn't suit large scale problems.

Regards


message
clpmex,
mean

MATLAB >> quadprog too slow

by hicham bouchnaif » Thu, 29 May 2008 08:55:04 GMT


no it's just a matter of accuracy, I ll try this OOQP stuff
and see how it works.

Regards

MATLAB >> quadprog too slow

by Johan Löfberg » Thu, 29 May 2008 20:32:01 GMT


<g1kut8$g50$ XXXX@XXXXX.COM >...

Correct, QPC is not applicable due to sparsity. clpmex
should work straight out of the box, so will bpmpdmex. I
think I had problems obtaining compiled versions of ooqp
last time I tried.

MATLAB >> quadprog too slow

by hicham bouchnaif » Mon, 02 Jun 2008 14:55:04 GMT

I tried clpmex, it's realy fast, quite impressing.
I ll try to test it for a higher scale.
by the way do you happen to know any other free soft that
you recommand for solving problems of type QP with
quadratic and linear constraints?

thanx alot.


mean
stuff

MATLAB >> quadprog too slow

by Johan Löfberg » Mon, 02 Jun 2008 17:21:02 GMT

Those listed on the page I referenced are the ones with
MATLAB interfaces that I am aware of


<g205g8$kam$ XXXX@XXXXX.COM >...

MATLAB >> quadprog too slow

by Min » Tue, 07 Oct 2008 02:35:06 GMT

Hi All,

I'm facing almost exactly the same problem.
Therefore I would like to try out clpmex as well.
I wonder should I download the file from
" http://control.ee.ethz.ch/ ~hybrid/cplexint.msql"?
And do I need to download the cplex library from http://www.ilog.com/ as well?
I tried to use the mex file directly but failed (libstdc++.so.5: cannot open shared object file: No such file or directory).
Any suggestions and pointers will be a great help for me.

Best,
MS

MATLAB >> quadprog too slow

by Min » Tue, 07 Oct 2008 03:00:27 GMT

Hi Johan,

Clpmex seems to need a license. Therefore, bpmpdmex might be the only free option for large-scale sparse QP problems.
However, the bpmpdmex that I downloaded only has a pre-compiled 32bit linux version.
Do you know how to compile bpmpdmex for a 64bit linux machine? The reason I can'y compile it is because I do not find the source code of bpmpd and any documents on using bpmpdlib.

Best,
-MS

Similar Threads

1. QuadProg very slow! - MATLAB

2. gui standalone gets slower and slower

Hi everybody,

I have compiled a matlab fig-file to a standalone with mcc -B sgl
name.fig. The standalone *.exe file works, but it gets slower and
slower. I have functions implemented, that take the visible off some
gui-handles on and off. After a few times making that, the guis
appear slower and slower. Where is the problem?

Thanks for your answer.

3. Axes on GUI Getting Slower and Slower - MATLAB

4. How to calculate the hessian matrix H for quadprog

Hi, 

I have a quadratic objective function like this:

y=a_0+a_1*x_1+a_2*x_2+...+a_n*x_n
  +a_12*x_1*x_2+.....a_n-1,n*x_(n-1)*x_n+
  +a_11*x_1^2+...+a_nn*x_n^2

Now I want to optimize this objective function by using 
quadratic programming. However, as described in the help 
file for this function, I have to input matrix H as the 
standard form of this function has to be:

y=1/2*x'Hx+f'x

So the question that I have is that: is there way to know 
the H matrix for the above objective function? 


5. Which to use (quadprog or fmincon)? - MATLAB

6. Optimzation Options Problem: Quadprog

I am having problems with the quadprog function in the 
optimization toolbox.  Below is my code:%Abunance at age 
from 1978-2004. 
origpop=[10522600, 6831010, 5506280, 2812580, 1209810, 
651957, 268240, 114552, 47032, 17696, 6285, 8826; 14868100, 
7764340, 4785890, 2892790, 1431290, 596668, 318576, 129875, 
55007, 22437, 8403, 7144; 11665300, 10781100, 5267360, 
2344800, 1332980, 613628, 243571, 123684, 48197, 19696, 
7830, 5308; 16551700, 8377890, 7159430, 2423150, 1001080, 
521482, 223665, 82554, 39266, 14528, 5720, 3699; 10126100, 
11796900, 5578130, 3575080, 1091650, 399091, 190292, 74539, 
25356, 11305, 3993, 2491; 10552000, 9249540, 5358220, 
3934970, 977988, 544329, 149467, 50908, 22577, 8286, 2677, 
1790; 12499000, 7273070, 7691140, 2264030, 1325300, 363994, 
123976, 54982, 20178, 6518, 25800, 1558; 10804900, 7809770, 
6813200, 2072290, 1194120, 277982, 154676, 42472, 14466, 
6416, 2354, 1269; 7508180, 7996000, 5753610, 3053760, 
749010, 404048, 94032, 52322, 14367, 4893, 2170, 1226; 
7357640, 5555400, 5892310, 3157060, 1416550, 326495, 176078, 
40978, 22801, 6261, 2132, 1480; 8882310, 5446010, 4095710, 
3025630, 1381460, 593723, 136818, 73786, 17172, 9555, 2624, 
1514; 7306930, 6571630, 4008240, 1626650, 921627, 389671, 
167415, 38579, 20806, 4842, 2694, 1167; 8057600, 5402470, 
4829010, 1508230, 434058, 216488,	91482, 39304, 9057, 4885, 
1137, 906; 5067850, 5950930, 3964520, 2099770, 425026, 
98588, 49125, 20759, 8919, 2055, 1108, 464; 5100770, 
3743210, 4369840, 1510300, 492937, 76764, 17786, 8862, 3745, 
1609, 371, 284; 4851310, 3768190, 2751620, 1844580, 406186, 
102961, 16016, 3711, 1849, 781, 336, 137; 9863940, 3583960, 
2771730, 1197230, 527273, 95101, 24085, 3747, 868, 433, 183, 
110; 6581610, 7279250, 2629800, 934009, 223835, 72705, 
13096, 3317, 516, 120, 60, 40; 8149480, 4853550, 5329740, 
723985, 124426, 20421, 6622, 1193, 302, 47, 11, 9; 5431190, 
6013300, 3560890, 1922820, 115531, 10844, 1775, 576, 104, 
26, 4, 2; 5366830, 4009420, 4416400, 1437290, 430531, 17521, 
1642, 269, 87, 16, 4,	1; 5720080, 3966710, 2952760, 2215380, 
472113, 103962, 4225, 396, 65, 21, 4, 1; 4394370, 4237510, 
2925510, 2023300, 498939, 32119, 7017, 285, 27, 4, 1, 0; 
6578780, 3255410, 3128770, 2035590, 519873, 71735, 4602, 
1005, 41, 4, 1, 0; 5590490, 4873640, 2399370, 2110440, 
238402, 29360, 4035, 259, 57, 2, 0, 0; 6099440, 4141520, 
3598230, 1658530, 459731, 16295, 1991, 274, 18, 4, 0, 0; 
6406360, 4518540, 3053150, 2418930, 207048, 24407, 861, 105, 
14, 1, 0, 0]; 
original=origpop';

%Generating the data vector
z=original(:, 2:27);
z=z(:);


%The non-zero entires in the parameter vector
nonzero=[2; 13; 15; 25; 28; 37; 41; 49; 54; 61; 67; 73; 80; 
85; 93; 97; 106; 109; 119; 121; 132; 133]; 

%Generating matrix M
M=[];
for i=1:26
  N=kron(original(:,i)', eye(12));
  m=N(:,nonzero);
  M=[M;m];
end;


%Generating the H and f vectors
H=M'*M;
f=-M'*z;

%Generating the inequality constraint matrix A such that 
A*f<=b 
A=zeros(33,22);
for r=1:22;
   A(r,r)=-1;
end

A(23,1)=1;
A(24,3)=1;
A(25,5)=1;
A(26,7)=1;
A(27,9)=1;
A(28,11)=1;
A(29,13)=1;
A(30,15)=1;
A(31,17)=1;
A(32,19)=1;
A(33,21)=1;

%Generating the inequality vector b such that A*f<=b
b=zeros(33,1);
for q=23:33;
    b(q,1)=1;
end

options=optimset('LargeScale', 'off');
%Calling MATLAB's quadratic programming function
phat=quadprog(H,f,A,b,options);


This returns the error "QUADPROG only accepts inputs of data 
type double."  However, when I query H, f, A, and b, they 
are all data type double. 

If I run the function as 
phat=quadprog(H,f,A,b);
I receive an error message "Warning: Large-scale method does 
not currently solve this problem formulation, 
using medium-scale method instead."
Dose anyone know why including options in the input causes 
the error, and how to avoid it? 

Thanks!

7. Optimization toolbox: quadprog returns an error - MATLAB

8. Optimization toolbox - Quadprog

Hi,

I want to know if quadprog in optimization toolbox uses any
C code (mex files). I have checked that the main function is
an m-file but what about internal function calls. 

I have looked at the optimization toolbox folder and there
are only m-files.

I would be grateful for your help