forum.alglib.net

ALGLIB forum
It is currently Thu Mar 28, 2024 4:02 pm

All times are UTC


Forum rules


1. This forum can be used for discussion of both ALGLIB-related and general numerical analysis questions
2. This forum is English-only - postings in other languages will be removed.



Post new topic Reply to topic  [ 12 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: BLEIC optimizer issue
PostPosted: Thu Jan 24, 2013 7:33 am 
Offline

Joined: Thu Jan 24, 2013 7:25 am
Posts: 8
Hello

I am trying to use the BLEIC optimization function of the ALGLIB library to solve the constrained minimization of a convex quadratic function in the form.

C = 1/2*xT*A *x + bT*x

A symmetric and positive definite.

I get different solutions when I include explicitly the gradient of the function:

grad(C) = A*x+b

and when I let the optimizer calculate it. But the latter takes several orders of magnitude longer to finish.


Top
 Profile  
 
 Post subject: Re: BLEIC optimizer issue
PostPosted: Thu Jan 24, 2013 5:14 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 903
1. What about function values? Are they significantly different? What is better - one obtained with analytic gradient or one obtained with numerical gradient?
2. Can you post your code here?


Top
 Profile  
 
 Post subject: Re: BLEIC optimizer issue
PostPosted: Fri Jan 25, 2013 7:09 am 
Offline

Joined: Thu Jan 24, 2013 7:25 am
Posts: 8
They are really different.

Its subjected to xi>=0 for all i.

Even the regions where the constraints are active are different.

With the analytical gradiente the values xi where the constraints are inactive are all the same, but with the numerical gradient they vary.


Top
 Profile  
 
 Post subject: Re: BLEIC optimizer issue
PostPosted: Fri Jan 25, 2013 9:28 am 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 903
Again - can you post actual code? :) I have to debug actual code to understand what is going on... In our tests we solved problems like your many times, and both methods gave same results.


Top
 Profile  
 
 Post subject: Re: BLEIC optimizer issue
PostPosted: Fri Jan 25, 2013 12:24 pm 
Offline

Joined: Thu Jan 24, 2013 7:25 am
Posts: 8
I've included an artificial gradient funtion, i.e. all zeros but one 1 in one of the rows and I get exactly the same solution than with the real gradient function.

The code to generate the matices is quite long but the optimization part is:

alglib.minbleicstate state;
alglib.minbleicreport rep;
double epsg = 0.000001;
double epsf = 0;
double epsx = 0;
double epso = 0.00001;
double epsi = 0.00001;
alglib.minbleiccreate(ndivX * ndivY, Press, out state);
alglib.minbleicsetlc(state, c, ct);
alglib.minbleicsetinnercond(state, epsg, epsf, epsx);
alglib.minbleicsetoutercond(state, epso, epsi);
alglib.minbleicoptimize(state, func_grad, null, null);
alglib.minbleicresults(state, out Press, out rep);

Where func_grad:

public void func_grad(double[] x, ref double func, double[] grad, object obj)
{
func = prodEsc(AB, x) + 0.5 * BilinealForm(x, T, x);
grad = sumVect(AB, ProdMatVect(T, x));
return;
}

prodEsc is a dot product funtion
BilinealForm makes the xT*A*x operations
and sumVect adds two vectors


Top
 Profile  
 
 Post subject: Re: BLEIC optimizer issue
PostPosted: Mon Jan 28, 2013 8:56 am 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 903
Can you post actual matrices and initial point? Maybe as attachment, or download link to some external file storage?

The problem may be caused by numerical properties of your matrices.


Top
 Profile  
 
 Post subject: Re: BLEIC optimizer issue
PostPosted: Thu Jan 31, 2013 8:47 am 
Offline

Joined: Thu Jan 24, 2013 7:25 am
Posts: 8
I forgot to mention another constraint that al xi must sum 187321 in this case.

I have attached a excel file with the matrices, the initial point and the solutions with analytical and numerical gradient.

Thank you for the interest by the way.


Attachments:
matrices.xlsb [222.83 KiB]
Downloaded 354 times
Top
 Profile  
 
 Post subject: Re: BLEIC optimizer issue
PostPosted: Thu Feb 07, 2013 10:50 am 
Offline

Joined: Thu Jan 24, 2013 7:25 am
Posts: 8
Have you been able to check it out?

Do you have any hint whether the problem is in my code or in the matrix?


Top
 Profile  
 
 Post subject: Re: BLEIC optimizer issue
PostPosted: Sun Feb 10, 2013 7:41 am 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 903
Your problem can be solved as follows:
1. upgrade to ALGLIB 3.7.0
2. change internal constant maxnonmonotoniclen at line 12723 of optimization.cs to 1.0E10

It should help. I did not tested your problem on 3.6.0, but on 3.7.0 it stalls because of numerical properties of the problem (high numerical noise). Proposed fix should make algorithm more tolerant to numerical noise in target function and it will be able to solve problem. I did not figured out exactly why numerical differentiation works, and analytic gradient is prone to noise, but I feel that it is not important question... maybe we have "close-to-limits" situation...


Top
 Profile  
 
 Post subject: Re: BLEIC optimizer issue
PostPosted: Mon Feb 11, 2013 8:09 am 
Offline

Joined: Thu Jan 24, 2013 7:25 am
Posts: 8
I've just tried and I keep getting exactly the same results.

I increased that constant up to 1E20 with no change in the results.

How can I see what the gradient the program calculates automatically?

Just to make myself sure I'm calculating the gradient properly.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ]  Go to page 1, 2  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 54 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group