forum.alglib.net
http://forum.alglib.net/

BLEIC opt - how to obtain most evenly distributed solution
http://forum.alglib.net/viewtopic.php?f=2&t=1840
Page 1 of 1

Author:  m3lis [ Thu May 15, 2014 10:14 am ]
Post subject:  BLEIC opt - how to obtain most evenly distributed solution

Hello,

I am new to ALGLIB and I must say it is a great library to use.

My issue is that I have the following optimization problem (c#), and I am trying to obtain the most evenly distributed solution, i.e. I'm aiming to have a reduction in the weights that is as evenly distributed amongst them as possible. Is there a way to ensure that? My code is as follows:
Code:
        public static void createWeightsFunction(double[] w, ref double func, double[] grad, object obj)
        {
            //Create the function to minimise
            //In our case: - w[0] - w[1] - ... - w[n-1]
            func = 0;
            for (int i = 0; i < w.Length; i++)
            {
                func -= w[i];
                grad[i] = 1;
            }
        }

        public static double[] getOptimizedWeights(double[] totalAppliancePrices, double[] thresholds, double target)
        {
            double[] weights = new double[totalAppliancePrices.Length];
            for (int i = 0; i < weights.Length; i++)
            {
                weights[i] = 1;
            }

            double[,] constr = new double[1, weights.Length + 1];

            //Add total consumption condition
            for (int i = 0; i < weights.Length; i++)
            {
                constr[0, i] = totalAppliancePrices[i];
            }
            constr[0, weights.Length] = target;

            int[] ct = new int[1];
            ct[0] = 0;

            // Add boundary constraints
            double[] bndl = new double[weights.Length];
            double[] bndu = new double[weights.Length];

            for (int i = 0; i < weights.Length; i++)
            {
                bndl[i] = thresholds[i];
                bndu[i] = 1;
            }

            alglib.minbleicstate state;
            alglib.minbleicreport rep;

            //
            // These variables define stopping conditions for the optimizer.
            //
            // We use very simple condition - |g|<=epsg
            //
            double epsg = 0.000001;
            double epsf = 0;
            double epsx = 0;
            int maxits = 0;

            //
            // Now we are ready to actually optimize something:
            // * first we create optimizer
            // * we add linear constraint
            // * we add the boundary constraints
            // * we tune stopping conditions
            // * and, finally, optimize and obtain results...
            //
            try
            {
                alglib.minbleiccreate(weights, out state);
                alglib.minbleicsetlc(state, constr, ct);
                alglib.minbleicsetbc(state, bndl, bndu);
                alglib.minbleicsetcond(state, epsg, epsf, epsx, maxits);
                alglib.minbleicoptimize(state, createWeightsFunction, null, null);
                alglib.minbleicresults(state, out weights, out rep);
            }
            catch (Exception ex)
            {
            }

            return weights;
        }


Thank you in advance.

Author:  Sergey.Bochkanov [ Thu May 15, 2014 12:00 pm ]
Post subject:  Re: BLEIC opt - how to obtain most evenly distributed soluti

Hello!

1. you have small error in your gradient code. It should be "grad = -1;", and you set it to +1.

2. if you want to choose solution, one of several equally good solutions, which has approximately same weights, then there is no way to do so with BLEIC optimizer. You may add "regularizer-like" term which is SUM(w_i^2), but it will introduce suboptimality in your solution.

Author:  m3lis [ Thu May 15, 2014 12:03 pm ]
Post subject:  Re: BLEIC opt - how to obtain most evenly distributed soluti

Thank you for the swift response and correction in the gradient.

As per the issue, I think what you suggest is exactly what I need, however I am not sure where or how to add the 'regularizer-like' term, can you please elaborate?

Thank you

Author:  Sergey.Bochkanov [ Thu May 15, 2014 1:03 pm ]
Post subject:  Re: BLEIC opt - how to obtain most evenly distributed soluti

You may modify target function by addition of term which penalizes difference in weights. I think that my original proposal was incorrect, there is better penalty term: P = SCALE*SUM{ (w_i - mean(w))^2 }, here mean(w) is just a mean value of all weights at current point.

You have to modify your code in such way that a) it adds penalty term to your function, b) it calculates gradient for this penalty term. It is relatively easy, I think that you can do it yourself. What is really tricky is to find good value for SCALE parameter - it controls delicate balance between quality of the function being optimized - and inequality in weights. Too large SCALE will mean that algorithm will be focused on equalization of weights instead of minimizing underlying function. I think that you have to perform a lot of trials...

Author:  m3lis [ Thu May 15, 2014 1:33 pm ]
Post subject:  Re: BLEIC opt - how to obtain most evenly distributed soluti

Thank you for the details, I will try that out

Author:  m3lis [ Sat May 24, 2014 3:39 pm ]
Post subject:  Re: BLEIC opt - how to obtain most evenly distributed soluti

I have modified my target function and it is now as follows:

Code:
        public static void createWeightsFunction(double[] w, ref double func, double[] grad, object obj)
        {
            //Create the function to minimise
            //In our case: - w[0] - w[1] - ... - w[n-1]
            double SCALE = 100;
            func = 0;
            double leSum = w.Sum();
            for (int i = 0; i < w.Length; i++)
            {
                func = func - w[i] + SCALE * Math.Pow(w[i] - leSum/w.Length, 2);
                grad[i] = -1 + SCALE * 2 * (w[i] - leSum / w.Length);
            }
        }


The SCALE value of 100 seems to be working quite well. Can you please let me know your take on my code, especially in terms of correctness ?

Also, with this modification is it possible to lose any solutions?

Thanks

Author:  Sergey.Bochkanov [ Mon May 26, 2014 12:49 pm ]
Post subject:  Re: BLEIC opt - how to obtain most evenly distributed soluti

Hello!

Your gradient calculation code has an error. It assumes that leSum is constant with respect to w_i, so derivative of (w-sum_w)^2 is assumed to be just 2*(w-sum_w). However, leSum does depend on w_i, so your code should be more complex.

Regarding losing solutions... having this "smoothing" term distorts your function, so solutions found with such "smoothing" will generally differ from ones found without it. And it is possible that they will be slightly worse than "non-smoothed" solutions.

Author:  m3lis [ Mon May 26, 2014 4:23 pm ]
Post subject:  Re: BLEIC opt - how to obtain most evenly distributed soluti

Thank you for the reply. Do you have any suggestions as to how the gradient function could be reformed?

Also, regarding solutions, does this function affect the correctness of the result, i.e. is it possible to get invalid solutions?

With this code, the solutions were actually pretty good (and correct)

Author:  Sergey.Bochkanov [ Tue May 27, 2014 6:36 am ]
Post subject:  Re: BLEIC opt - how to obtain most evenly distributed soluti

1. in the general case such modification of the target function affects solution. It makes it more "even" at the cost of slight reduction of the solution quality.

It is possible for some special cases that such modification will leave solutions correct. I suppose that your situation is such one. However, I can not give you any guarantees that solution correctness will retain for different values of SCALE, or for different problems from the same family.

2. about modification of gradient. You should rewrite "smoothing" term as two nested sums: SUM( w_i*(n-1)/n - SUM(w_j | for j!=i) | for i=0..n-1 )

And then you should differentiate it. It is a bit complex differentiation, but not supernatural :)

Author:  Abraham12li [ Tue Mar 03, 2015 5:21 pm ]
Post subject:  Re: BLEIC opt - how to obtain most evenly distributed soluti

I have a matrix A of size M X N where M is greater than N. [Typical sizes are M = 15,000 while N =20]. We want to apply PCA on this matrix where variables are more than observations.[ I am aware that the results are not completely reliable but in our experiments with R, they made some sense

Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/