forum.alglib.net

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.

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?

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.

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.

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

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.

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.

Have you been able to check it out?

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

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...

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.