# forum.alglib.net

ALGLIB forum
 It is currently Fri Sep 22, 2023 9:56 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.

 Page 1 of 1 [ 10 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: BLEIC opt - how to obtain most evenly distributed solutionPosted: Thu May 15, 2014 10:14 am

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];
}
}

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

 Post subject: Re: BLEIC opt - how to obtain most evenly distributed solutiPosted: Thu May 15, 2014 12:00 pm

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

 Post subject: Re: BLEIC opt - how to obtain most evenly distributed solutiPosted: Thu May 15, 2014 12:03 pm

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

 Post subject: Re: BLEIC opt - how to obtain most evenly distributed solutiPosted: Thu May 15, 2014 1:03 pm

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

 Post subject: Re: BLEIC opt - how to obtain most evenly distributed solutiPosted: Thu May 15, 2014 1:33 pm

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

Top

 Post subject: Re: BLEIC opt - how to obtain most evenly distributed solutiPosted: Sat May 24, 2014 3:39 pm

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

 Post subject: Re: BLEIC opt - how to obtain most evenly distributed solutiPosted: Mon May 26, 2014 12:49 pm

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

 Post subject: Re: BLEIC opt - how to obtain most evenly distributed solutiPosted: Mon May 26, 2014 4:23 pm

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

 Post subject: Re: BLEIC opt - how to obtain most evenly distributed solutiPosted: Tue May 27, 2014 6:36 am

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

 Post subject: Re: BLEIC opt - how to obtain most evenly distributed solutiPosted: Tue Mar 03, 2015 5:21 pm

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 10 posts ]

 All times are UTC

#### Who is online

Users browsing this forum: No registered users and 7 guests

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

Search for:
 Jump to:  Select a forum ------------------ ALGLIB forum    ALGLIB-discuss
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group