forum.alglib.net

ALGLIB forum
It is currently Thu Apr 18, 2024 9:11 am

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  [ 10 posts ] 
Author Message
 Post subject: BLEIC opt - how to obtain most evenly distributed solution
PostPosted: Thu May 15, 2014 10:14 am 
Offline

Joined: Thu May 15, 2014 10:07 am
Posts: 5
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.


Top
 Profile  
 
 Post subject: Re: BLEIC opt - how to obtain most evenly distributed soluti
PostPosted: Thu May 15, 2014 12:00 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 906
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.


Top
 Profile  
 
 Post subject: Re: BLEIC opt - how to obtain most evenly distributed soluti
PostPosted: Thu May 15, 2014 12:03 pm 
Offline

Joined: Thu May 15, 2014 10:07 am
Posts: 5
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


Top
 Profile  
 
 Post subject: Re: BLEIC opt - how to obtain most evenly distributed soluti
PostPosted: Thu May 15, 2014 1:03 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 906
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...


Top
 Profile  
 
 Post subject: Re: BLEIC opt - how to obtain most evenly distributed soluti
PostPosted: Thu May 15, 2014 1:33 pm 
Offline

Joined: Thu May 15, 2014 10:07 am
Posts: 5
Thank you for the details, I will try that out


Top
 Profile  
 
 Post subject: Re: BLEIC opt - how to obtain most evenly distributed soluti
PostPosted: Sat May 24, 2014 3:39 pm 
Offline

Joined: Thu May 15, 2014 10:07 am
Posts: 5
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


Top
 Profile  
 
 Post subject: Re: BLEIC opt - how to obtain most evenly distributed soluti
PostPosted: Mon May 26, 2014 12:49 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 906
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.


Top
 Profile  
 
 Post subject: Re: BLEIC opt - how to obtain most evenly distributed soluti
PostPosted: Mon May 26, 2014 4:23 pm 
Offline

Joined: Thu May 15, 2014 10:07 am
Posts: 5
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)


Top
 Profile  
 
 Post subject: Re: BLEIC opt - how to obtain most evenly distributed soluti
PostPosted: Tue May 27, 2014 6:36 am 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 906
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 :)


Top
 Profile  
 
 Post subject: Re: BLEIC opt - how to obtain most evenly distributed soluti
PostPosted: Tue Mar 03, 2015 5:21 pm 
Offline

Joined: Tue Mar 03, 2015 5:15 pm
Posts: 1
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


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 29 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:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group