random generation of constrained portfolio allocation weights

[Ferdinando Ametrano-3]

Hi all

I need to generate random weights for a portfolio allocation, with max
constraints on the weights, no short sale allowed (e.g. 3 assets, each one
in the [0%, 40%] range)

I have no problem for the unconstrained generation, using (quasi)random
sequences of dimension 3 that I normalize so that their sum is 100%. I'm
not sure this approach is on solid theoretical ground, but it works.

Anyway when it comes to constrained generation many problems arise, and I
haven't found an efficient generation algorithm. Rejection of the
unconstrained portfolio is inefficient, of course.

Hints, suggestions, thoughts?

Even better would be a ready to be coded algorithm ;-)

ciao -- Nando

[Hurd, Matthew]

The below distribution will not be uniformly random (depending on what
this means to you), but neither will rejecting illegal cases.

Using your [0-40] example:

1. Random first number 20-40.  Has to be at least 20 otherwise no viable
solution.

2.  Next random number to give a sum of at least 60, so the last number
may be valid (it has to be <= 40).  That is, if the first number is 35,
then the second number must be [25-40] to make a viable triple.

3.  Obviously, the third number is 100 - sum of the first two.

Trivial to generalise.

Is that what you're after?

Regards,

Matt Hurd.
_________________

Matt Hurd
+61.2.8226.5029
[hidden email]
Susquehanna
_________________
 
> -----Original Message-----
> From: [hidden email]
[mailto:quantlib-users-

> [hidden email]] On Behalf Of Ferdinando Ametrano
> Sent: Tuesday, 7 September 2004 12:53 AM
> To: QuantLib-users
> Subject: [Quantlib-users] random generation of constrained portfolio
> allocation weights
>
> Hi all
>
> I need to generate random weights for a portfolio allocation, with max
> constraints on the weights, no short sale allowed (e.g. 3 assets, each

one
> in the [0%, 40%] range)
>
> I have no problem for the unconstrained generation, using
(quasi)random
> sequences of dimension 3 that I normalize so that their sum is 100%.
I'm
> not sure this approach is on solid theoretical ground, but it works.
>
> Anyway when it comes to constrained generation many problems arise,
and I

> haven't found an efficient generation algorithm. Rejection of the
> unconstrained portfolio is inefficient, of course.
>
> Hints, suggestions, thoughts?
>
> Even better would be a ready to be coded algorithm ;-)
>
> ciao -- Nando
>
>
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by BEA Weblogic Workshop
> FREE Java Enterprise J2EE developer tools!
> Get your free copy of BEA WebLogic Workshop 8.1 today.
> http://ads.osdn.com/?ad_id=5047&alloc_id=10808&op=click
> _______________________________________________
> Quantlib-users mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/quantlib-users

IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments.  Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited.  Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument.  Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

[Ferdinando Ametrano-3]

Hi Matt,

>Using your [0-40] example:
>1. Random first number 20-40.  Has to be at least 20 otherwise no viable
>solution.
>2.  Next random number to give a sum of at least 60, so the last number
>may be valid (it has to be <= 40).  That is, if the first number is 35,
>then the second number must be [25-40] to make a viable triple.
>3.  Obviously, the third number is 100 - sum of the first two.

thank you for your suggestion, it pointed out my error. While I realized
that I had to correct the input constraints so to make minima and maxima
each other "compatible" before start drawing the weights, I was missing to
update the constraints dynamically conditional to the previous weights, as
you do in step 2.

Now the algorithm seems to work and I've created the example spreadsheet
AAconstrained.xls which implements it for 4 assets (MC dimension 3). This
spreadsheet along with the following other examples can be downloaded from
http://quantlib.org/RandomWeights.zip

Anyway I still have some doubts.

If you look at AAconstrained.xls you will see that row statistics applied
to the random weights are reasonable: the observed minimum and maximum are
correct, and the average is in the middle as one might expect.

Then if you apply the same algorithm to unconstrained random weights things
look worse. Take a look at AAunconstrained.xls: the average for the four
assets is not equal, but decreasing with the asset number. This looks very
suspicious to me.

I get a confirmation about my doubts if I go back to my "vanilla" algorithm
for unconstrained weights (MC dimension 4): draw a 4-element sequence and
normalize it.
Take a look at AAunconstrained2.xls: the statistics for the "vanilla"
algorithm seems more reasonable. The average for each asset is always 25%
(as I might expect for a 4 assets problem), the minima reach down to zero,
while the maxima reach up toward 100% as I increase the number of draws.

Why your constrained algorithm seems to perform poorly in the unconstrained
case? I know I'm probably missing some key point here, and would love to be
enlightened.

ciao -- Nando

PS just in case one wonders: in the spreadsheets I'm using (2^10)-1=4095
draws from a Sobol sequence of dimension 3 or 4

[ML-21]

> I need to generate random weights for a
> portfolio allocation, with max constraints
> on the weights, no short sale allowed (e.g.
> 3 assets, each one in the [0%, 40%] range)

Generally you have 2N+1 inequalities:

0 <= x_i, i=1..N
x_i <= M_i, i=1..N
Sum[x_i, {i,1,N}] = 1

These inequalities define 2N+1 hyperplanes in the N-dimensional space. The volume enclosed by these hyperplanes is called a polytope (polygone in the planar case N=2).

Generating uniformly distributed random numbers on a multidimensional polytope is a rather difficult problem. See for instance http://citeseer.ist.psu.edu/leydold98sweepplane.html

If there is interest, I'm happy to work on this issue and eventually contribute a good algorithm. For the time being, however, I guess the rejection method is a moderately good solution.

-Mario

[Ferdinando Ametrano-3]

Mario,

>Generating uniformly distributed random numbers on a multidimensional
>polytope is a rather difficult problem. See for instance [Leydold,
>Hormann] http://citeseer.ist.psu.edu/leydold98sweepplane.html
thank you for the setting the problem and for the paper. I've fast-read it,
and I hoped to be able to use (1) in [Leydold, Hormann], but I haven't been
able to compute the vertex using the packages available on the web. It
seems like this problem needs more than 15 minutes... :)

>If there is interest, I'm happy to work on this issue and eventually
>contribute a good algorithm.
I am very interested! Please go ahead, and let me know how can I help you.

>  For the time being, however, I guess the rejection method is a
> moderately good solution.
Hmmm... what do you mean exactly? With strict constraints I had to reject
up all but 3 tuples out of 4097 Sobol tuples. It's too inefficient in my book.

I look forward to your contribution.

ciao -- Nando

[Hurd, Matthew]

> -----Original Message-----
> From: [hidden email]
[mailto:quantlib-users-
> [hidden email]] On Behalf Of ML
> Sent: Tuesday, 7 September 2004 8:58 PM
> To: [hidden email]
> Subject: [Quantlib-users] RE: random generation of constrained
portfolio

> allocation weights
>
> > I need to generate random weights for a
> > portfolio allocation, with max constraints
> > on the weights, no short sale allowed (e.g.
> > 3 assets, each one in the [0%, 40%] range)
>
> Generally you have 2N+1 inequalities:
>
> 0 <= x_i, i=1..N
> x_i <= M_i, i=1..N
> Sum[x_i, {i,1,N}] = 1
>
> These inequalities define 2N+1 hyperplanes in the N-dimensional space.

The
> volume enclosed by these hyperplanes is called a polytope (polygone in
the
> planar case N=2).
>
> Generating uniformly distributed random numbers on a multidimensional
polytope
> is a rather difficult problem. See for instance
> http://citeseer.ist.psu.edu/leydold98sweepplane.html
>
> If there is interest, I'm happy to work on this issue and eventually
> contribute a good algorithm. For the time being, however, I guess the
> rejection method is a moderately good solution.
>
> -Mario
>

Intuitively you can see why as the final measure is likely to be a
biased number as it has to fit into the initial choices.  A simple way
of improving the randomness is to shuffle the tuple, i.e. randomly
select the axes to constrain, before allocating the weights.  That way
the bias is randomly distributed and hopefully a little nicer.

Regards,

Matt Hurd.
_________________

Matt Hurd
+61.2.8226.5029
[hidden email]
Susquehanna
_________________



IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments.  Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited.  Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument.  Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

[ML-21]

> thank you for the setting the problem and for the paper.

Actually, I made a little mistake: I incorrectly wrote there were 2N+1
inequalities, but of course there are 2 inequalities and 1 equation.
However, that doesn't make a difference to the fundamental problem of having
to generate uniformly distributed variates on/in a multidimensional
polytope.


> >If there is interest, I'm happy to work on this issue and eventually
> >contribute a good algorithm.
> I am very interested! Please go ahead, and let me know how can I help you.

I wrote a short (and unverified!) program that lists the vertices of the
polytope (http://luoni.net/junk.Rs9qq8xWa/rng.tar.gz). Generally speaking,
the number of vertices grows with N!, so the polytope becomes quickly very
complex. However, my guess/hope is that there will be a feasible solution
thanks to the simplicity of the underlying (in)equalities.

I am wondering whether the limits for the individual positions of the
portfolio are necessarily identical?


> >  For the time being, however, I guess the rejection method is a
> > moderately good solution.
> Hmmm... what do you mean exactly?

Due to my mistake mentioned above I think I have to withdraw that statement
:-)


-Mario

[ML-21]

> Actually, I made a little mistake: I incorrectly wrote there were 2N+1
> inequalities, but of course there are 2 inequalities and 1 equation.

2 --> 2N

(early morning syndrome :) )

[Hurd, Matthew]

Mario,

As I mentioned to "randomize the bias" you can shuffle an indirection.

This is what I mentioned in a later mail:  
  "Intuitively, you can see why as the final measure is likely to be a
   biased number as it has to fit into the initial choices.  A simple way
   of improving the randomness is to shuffle the tuple, i.e. randomly
   select the axes to constrain, before allocating the weights.  That way
   the bias is randomly distributed and hopefully a little nicer."

Code below produces:

    0.333351/0.333322/0.333327
    Press any key to continue . . .

On my machine, YMMV.

Probably good enough for what you're after.  Though disguising bias and eliminating bias aren't necessarily the same thing ;-)

Hope this helps,

Matt.
[hidden email]
+61.419.602148
__________________________________________

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>


const int nn = 10000000;

int main() {

    std::vector<double> ss(3,0.0);
    std::vector<std::size_t> axis(3);
    std::vector<double> uu(3);

    axis[0] = 0;
    axis[1] = 1;
    axis[2] = 2;

    std::vector<std::size_t>::iterator b = axis.begin();
    std::vector<std::size_t>::iterator e = axis.end();

    for(int j=0; j<nn; j++) {

        // shuffle the indirection, as the rules are the same you could just
        // shuffle the values instead which would be quicker

        std::random_shuffle( b, e);

        uu[axis[0]] = 0.2 + 0.2*(double)(rand()/(RAND_MAX+1.0));
        uu[axis[1]] = (0.6-uu[axis[0]])
                        +(uu[axis[0]]-0.2)
                        *(double)(rand()/(RAND_MAX+1.0));
        uu[axis[2]] = 1.0-(uu[axis[0]] + uu[axis[1]] );
       
        ss[0] += uu[0];
        ss[1] += uu[1];
        ss[2] += uu[2];
    }

    std::cout << "\n"
        << ss[0]/nn
        << "/" << ss[1]/nn
        << "/" << ss[2]/nn
        << "\n";

    system("pause");
}

> -----Original Message-----
> From: ML [mailto:[hidden email]]
> Sent: Wednesday, 8 September 2004 7:23 PM
> To: Hurd, Matthew
> Cc: Ferdinando Ametrano
> Subject: Re: [Quantlib-users] random generation of constrained portfolio
> allocation weights
>
> Matthew,
>
> I wrote a small piece of code (cf below) to test your suggestion. After 1
> million runs the first moments of the generated numbers are:
>
> 0.30 / 0.35 / 0.35
>
> However, the problem being symmetrical, the first moments should be equal
> (to 1/3).
>
> -Mario
>
> ===========================================================
> #include <iostream>
> #include <stdlib.h>
>
> using namespace std;
>
> const int nn = 1000000;
>
> int main() {
>   double ss11 = 0.0;
>   double ss21 = 0.0;
>   double ss31 = 0.0;
>   for(int j=0; j<nn; j++) {
>     double uu1 = 0.2+0.2*(double)(random()/(RAND_MAX+1.0));
>     double uu2 = (0.6-uu1)+(uu1-0.2)*(double)(random()/(RAND_MAX+1.0));
>     double uu3 = 1.0-uu1-uu2;
>     //    cout << uu1 << "/" << uu2 << "/" << uu3 << endl;
>     ss11 += uu1;
>     ss21 += uu2;
>     ss31 += uu3;
>   }
>   cout << endl << ss11/nn << "/" << ss21/nn << "/" << ss31/nn << endl;
> }
>
> ========================================================
> ----- Original Message -----
> From: "Hurd, Matthew" <[hidden email]>
> To: "Ferdinando Ametrano" <[hidden email]>;
> <[hidden email]>
> Sent: Tuesday, September 07, 2004 9:05 AM
> Subject: RE: [Quantlib-users] random generation of constrained portfolio
> allocation weights
>
>
> > The below distribution will not be uniformly random (depending on what
> > this means to you), but neither will rejecting illegal cases.
> >
> > Using your [0-40] example:
> >
> > 1. Random first number 20-40.  Has to be at least 20 otherwise no viable
> > solution.
> >
> > 2.  Next random number to give a sum of at least 60, so the last number
> > may be valid (it has to be <= 40).  That is, if the first number is 35,
> > then the second number must be [25-40] to make a viable triple.
> >
> > 3.  Obviously, the third number is 100 - sum of the first two.
> >
> > Trivial to generalise.
> >
> > Is that what you're after?
> >
> > Regards,
> >
> > Matt Hurd.
> > _________________
> >
> > Matt Hurd
> > +61.2.8226.5029
> > [hidden email]
> > Susquehanna
> > _________________
> >
> > > -----Original Message-----
> > > From: [hidden email]
> > [mailto:quantlib-users-
> > > [hidden email]] On Behalf Of Ferdinando Ametrano
> > > Sent: Tuesday, 7 September 2004 12:53 AM
> > > To: QuantLib-users
> > > Subject: [Quantlib-users] random generation of constrained portfolio
> > > allocation weights
> > >
> > > Hi all
> > >
> > > I need to generate random weights for a portfolio allocation, with max
> > > constraints on the weights, no short sale allowed (e.g. 3 assets, each
> > one
> > > in the [0%, 40%] range)
> > >
> > > I have no problem for the unconstrained generation, using
> > (quasi)random
> > > sequences of dimension 3 that I normalize so that their sum is 100%.
> > I'm
> > > not sure this approach is on solid theoretical ground, but it works.
> > >
> > > Anyway when it comes to constrained generation many problems arise,
> > and I
> > > haven't found an efficient generation algorithm. Rejection of the
> > > unconstrained portfolio is inefficient, of course.
> > >
> > > Hints, suggestions, thoughts?
> > >
> > > Even better would be a ready to be coded algorithm ;-)
> > >
> > > ciao -- Nando
> > >
> > >
> > >
> > >
> > > -------------------------------------------------------
> > > This SF.Net email is sponsored by BEA Weblogic Workshop
> > > FREE Java Enterprise J2EE developer tools!
> > > Get your free copy of BEA WebLogic Workshop 8.1 today.
> > > http://ads.osdn.com/?ad_id=5047&alloc_id=10808&op=click
> > > _______________________________________________
> > > Quantlib-users mailing list
> > > [hidden email]
> > > https://lists.sourceforge.net/lists/listinfo/quantlib-users
> >
> >
> >
> > IMPORTANT: The information contained in this email and/or its attachments
> is confidential. If you are not the intended recipient, please notify the
> sender immediately by reply and immediately delete this message and all its
> attachments.  Any review, use, reproduction, disclosure or dissemination of
> this message or any attachment by an unintended recipient is strictly
> prohibited.  Neither this message nor any attachment is intended as or
> should be construed as an offer, solicitation or recommendation to buy or
> sell any security or other financial instrument.  Neither the sender, his or
> her employer nor any of their respective affiliates makes any warranties as
> to the completeness or accuracy of any of the information contained herein
> or that this message or any of its attachments is free of viruses.
> >
> >
> >
> > -------------------------------------------------------
> > This SF.Net email is sponsored by BEA Weblogic Workshop
> > FREE Java Enterprise J2EE developer tools!
> > Get your free copy of BEA WebLogic Workshop 8.1 today.
> > <a href="http://ads.osdn.com/?ad_idP47&alloc_id808&opÌk">http://ads.osdn.com/?ad_idP47&alloc_id808&opÌk
> > _______________________________________________
> > Quantlib-users mailing list
> > [hidden email]
> > https://lists.sourceforge.net/lists/listinfo/quantlib-users
>

[ML-21]

Sorry Matthew I overlooked the shuffling part :-)

I agree, your method seems to be OK for the original example {0.4, 0.4, 0.4}
or the general symmetrical  problem {M, M,..., M}, 1/N<=M<=1, although I
would suggest some more testing, especially in higher dimensions.

I'm wondering how many random portfolios Nando wants to generate, and in
what dimension, and whether the positions always have symmetrical weights.
If the number of portfolios to be generated is small, and the dimension
relatively high, the shuffling might not work very well.

How can your idea be generalized to the asymmetrical problem {M1, M2, M3}? I
know that wasn't asked for in Nando's original mail, but wouldn't it occur
as well sooner or later?

-Mario

----- Original Message -----
From: "Hurd, Matthew" <[hidden email]>
To: "ML" <[hidden email]>; "Hurd, Matthew" <[hidden email]>;
<[hidden email]>
Cc: "Ferdinando Ametrano" <[hidden email]>
Sent: Thursday, September 09, 2004 12:38 AM
Subject: RE: [Quantlib-users] random generation of constrained portfolio
allocation weights

> Mario,
>
> As I mentioned to "randomize the bias" you can shuffle an indirection.
>
> This is what I mentioned in a later mail:
>   "Intuitively, you can see why as the final measure is likely to be a
>    biased number as it has to fit into the initial choices.  A simple way
>    of improving the randomness is to shuffle the tuple, i.e. randomly
>    select the axes to constrain, before allocating the weights.  That way
>    the bias is randomly distributed and hopefully a little nicer."
>
> Code below produces:
>
>     0.333351/0.333322/0.333327
>     Press any key to continue . . .
>
> On my machine, YMMV.
>
> Probably good enough for what you're after.  Though disguising bias and

eliminating bias aren't necessarily the same thing ;-)

>
> Hope this helps,
>
> Matt.
> [hidden email]
> +61.419.602148
> __________________________________________
>
> #include <iostream>
> #include <stdlib.h>
> #include <vector>
> #include <algorithm>
>
>
> const int nn = 10000000;
>
> int main() {
>
>     std::vector<double> ss(3,0.0);
>     std::vector<std::size_t> axis(3);
>     std::vector<double> uu(3);
>
>     axis[0] = 0;
>     axis[1] = 1;
>     axis[2] = 2;
>
>     std::vector<std::size_t>::iterator b = axis.begin();
>     std::vector<std::size_t>::iterator e = axis.end();
>
>     for(int j=0; j<nn; j++) {
>
>         // shuffle the indirection, as the rules are the same you could

just

>         // shuffle the values instead which would be quicker
>
>         std::random_shuffle( b, e);
>
>         uu[axis[0]] = 0.2 + 0.2*(double)(rand()/(RAND_MAX+1.0));
>         uu[axis[1]] = (0.6-uu[axis[0]])
>                         +(uu[axis[0]]-0.2)
>                         *(double)(rand()/(RAND_MAX+1.0));
>         uu[axis[2]] = 1.0-(uu[axis[0]] + uu[axis[1]] );
>
>         ss[0] += uu[0];
>         ss[1] += uu[1];
>         ss[2] += uu[2];
>     }
>
>     std::cout << "\n"
>         << ss[0]/nn
>         << "/" << ss[1]/nn
>         << "/" << ss[2]/nn
>         << "\n";
>
>     system("pause");
> }
>
>
>
>
> > -----Original Message-----
> > From: ML [mailto:[hidden email]]
> > Sent: Wednesday, 8 September 2004 7:23 PM
> > To: Hurd, Matthew
> > Cc: Ferdinando Ametrano
> > Subject: Re: [Quantlib-users] random generation of constrained portfolio
> > allocation weights
> >
> > Matthew,
> >
> > I wrote a small piece of code (cf below) to test your suggestion. After

1
> > million runs the first moments of the generated numbers are:
> >
> > 0.30 / 0.35 / 0.35
> >
> > However, the problem being symmetrical, the first moments should be
equal

> > (to 1/3).
> >
> > -Mario
> >
> > ===========================================================
> > #include <iostream>
> > #include <stdlib.h>
> >
> > using namespace std;
> >
> > const int nn = 1000000;
> >
> > int main() {
> >   double ss11 = 0.0;
> >   double ss21 = 0.0;
> >   double ss31 = 0.0;
> >   for(int j=0; j<nn; j++) {
> >     double uu1 = 0.2+0.2*(double)(random()/(RAND_MAX+1.0));
> >     double uu2 = (0.6-uu1)+(uu1-0.2)*(double)(random()/(RAND_MAX+1.0));
> >     double uu3 = 1.0-uu1-uu2;
> >     //    cout << uu1 << "/" << uu2 << "/" << uu3 << endl;
> >     ss11 += uu1;
> >     ss21 += uu2;
> >     ss31 += uu3;
> >   }
> >   cout << endl << ss11/nn << "/" << ss21/nn << "/" << ss31/nn << endl;
> > }
> >
> > ========================================================
> > ----- Original Message -----
> > From: "Hurd, Matthew" <[hidden email]>
> > To: "Ferdinando Ametrano" <[hidden email]>;
> > <[hidden email]>
> > Sent: Tuesday, September 07, 2004 9:05 AM
> > Subject: RE: [Quantlib-users] random generation of constrained portfolio
> > allocation weights
> >
> >
> > > The below distribution will not be uniformly random (depending on what
> > > this means to you), but neither will rejecting illegal cases.
> > >
> > > Using your [0-40] example:
> > >
> > > 1. Random first number 20-40.  Has to be at least 20 otherwise no

viable
> > > solution.
> > >
> > > 2.  Next random number to give a sum of at least 60, so the last
number
> > > may be valid (it has to be <= 40).  That is, if the first number is
35,

> > > then the second number must be [25-40] to make a viable triple.
> > >
> > > 3.  Obviously, the third number is 100 - sum of the first two.
> > >
> > > Trivial to generalise.
> > >
> > > Is that what you're after?
> > >
> > > Regards,
> > >
> > > Matt Hurd.
> > > _________________
> > >
> > > Matt Hurd
> > > +61.2.8226.5029
> > > [hidden email]
> > > Susquehanna
> > > _________________
> > >
> > > > -----Original Message-----
> > > > From: [hidden email]
> > > [mailto:quantlib-users-
> > > > [hidden email]] On Behalf Of Ferdinando Ametrano
> > > > Sent: Tuesday, 7 September 2004 12:53 AM
> > > > To: QuantLib-users
> > > > Subject: [Quantlib-users] random generation of constrained portfolio
> > > > allocation weights
> > > >
> > > > Hi all
> > > >
> > > > I need to generate random weights for a portfolio allocation, with

max
> > > > constraints on the weights, no short sale allowed (e.g. 3 assets,
each

> > > one
> > > > in the [0%, 40%] range)
> > > >
> > > > I have no problem for the unconstrained generation, using
> > > (quasi)random
> > > > sequences of dimension 3 that I normalize so that their sum is 100%.
> > > I'm
> > > > not sure this approach is on solid theoretical ground, but it works.
> > > >
> > > > Anyway when it comes to constrained generation many problems arise,
> > > and I
> > > > haven't found an efficient generation algorithm. Rejection of the
> > > > unconstrained portfolio is inefficient, of course.
> > > >
> > > > Hints, suggestions, thoughts?
> > > >
> > > > Even better would be a ready to be coded algorithm ;-)
> > > >
> > > > ciao -- Nando
> > > >
> > > >
> > > >
> > > >
> > > > -------------------------------------------------------
> > > > This SF.Net email is sponsored by BEA Weblogic Workshop
> > > > FREE Java Enterprise J2EE developer tools!
> > > > Get your free copy of BEA WebLogic Workshop 8.1 today.
> > > > http://ads.osdn.com/?ad_id=5047&alloc_id=10808&op=click
> > > > _______________________________________________
> > > > Quantlib-users mailing list
> > > > [hidden email]
> > > > https://lists.sourceforge.net/lists/listinfo/quantlib-users
> > >
> > >
> > >
> > > IMPORTANT: The information contained in this email and/or its

attachments
> > is confidential. If you are not the intended recipient, please notify
the
> > sender immediately by reply and immediately delete this message and all
its
> > attachments.  Any review, use, reproduction, disclosure or dissemination
of
> > this message or any attachment by an unintended recipient is strictly
> > prohibited.  Neither this message nor any attachment is intended as or
> > should be construed as an offer, solicitation or recommendation to buy
or
> > sell any security or other financial instrument.  Neither the sender,
his or
> > her employer nor any of their respective affiliates makes any warranties
as
> > to the completeness or accuracy of any of the information contained
herein

> > or that this message or any of its attachments is free of viruses.
> > >
> > >
> > >
> > > -------------------------------------------------------
> > > This SF.Net email is sponsored by BEA Weblogic Workshop
> > > FREE Java Enterprise J2EE developer tools!
> > > Get your free copy of BEA WebLogic Workshop 8.1 today.
> > > <a href="http://ads.osdn.com/?ad_idP47&alloc_id808&opÌk">http://ads.osdn.com/?ad_idP47&alloc_id808&opÌk
> > > _______________________________________________
> > > Quantlib-users mailing list
> > > [hidden email]
> > > https://lists.sourceforge.net/lists/listinfo/quantlib-users
> >
>

[Hurd, Matthew]

> Sorry Matthew I overlooked the shuffling part :-)

What's the old quote about most things in computer science can be solved with a level of indirection :-)  Strikes again.
 
> I agree, your method seems to be OK for the original example {0.4, 0.4, 0.4}
> or the general symmetrical  problem {M, M,..., M}, 1/N<=M<=1, although I
> would suggest some more testing, especially in higher dimensions.

I too am unsure of the biases due to the nature of the conditional generation.  I'm not sure if the shuffling is masking or solving the bias problem.  A correct way would be to sample each variate from a correct conditional distribution... but that sounds like hard work and is not in the spirit of a lazy Monte Marlo whilst you brew the coffee ;-)
 
> I'm wondering how many random portfolios Nando wants to generate, and in
> what dimension, and whether the positions always have symmetrical weights.
> If the number of portfolios to be generated is small, and the dimension
> relatively high, the shuffling might not work very well.

Indeed.  If the number of portfolios to be generated is small, raw Monte Carlo will be less powerful than other methods anyway.  You'd want to start thinking about a monte carlo grid method or some such.

> How can your idea be generalized to the asymmetrical problem {M1, M2, M3}? I
> know that wasn't asked for in Nando's original mail, but wouldn't it occur
> as well sooner or later?

Yep, it can.  You can shuffle, or redirect to, functional constraints for the each variate as well.  That is, if you may have a vector of functions that takes the sum so far, or whatever other conditions are required, then this can be used for the generation of each variate.

But I'm just making this up as I go along.  Sounds plausible enough though.

Hoping there is a bit more light than heat in my suggestions...

Matt

> -Mario
>
> ----- Original Message -----
> From: "Hurd, Matthew" <[hidden email]>
> To: "ML" <[hidden email]>; "Hurd, Matthew" <[hidden email]>;
> <[hidden email]>
> Cc: "Ferdinando Ametrano" <[hidden email]>
> Sent: Thursday, September 09, 2004 12:38 AM
> Subject: RE: [Quantlib-users] random generation of constrained portfolio
> allocation weights
>
>
> > Mario,
> >
> > As I mentioned to "randomize the bias" you can shuffle an indirection.
> >
> > This is what I mentioned in a later mail:
> >   "Intuitively, you can see why as the final measure is likely to be a
> >    biased number as it has to fit into the initial choices.  A simple way
> >    of improving the randomness is to shuffle the tuple, i.e. randomly
> >    select the axes to constrain, before allocating the weights.  That way
> >    the bias is randomly distributed and hopefully a little nicer."
> >
> > Code below produces:
> >
> >     0.333351/0.333322/0.333327
> >     Press any key to continue . . .
> >
> > On my machine, YMMV.
> >
> > Probably good enough for what you're after.  Though disguising bias and
> eliminating bias aren't necessarily the same thing ;-)
> >
> > Hope this helps,
> >
> > Matt.
> > [hidden email]
> > +61.419.602148
> > __________________________________________
> >
> > #include <iostream>
> > #include <stdlib.h>
> > #include <vector>
> > #include <algorithm>
> >
> >
> > const int nn = 10000000;
> >
> > int main() {
> >
> >     std::vector<double> ss(3,0.0);
> >     std::vector<std::size_t> axis(3);
> >     std::vector<double> uu(3);
> >
> >     axis[0] = 0;
> >     axis[1] = 1;
> >     axis[2] = 2;
> >
> >     std::vector<std::size_t>::iterator b = axis.begin();
> >     std::vector<std::size_t>::iterator e = axis.end();
> >
> >     for(int j=0; j<nn; j++) {
> >
> >         // shuffle the indirection, as the rules are the same you could
> just
> >         // shuffle the values instead which would be quicker
> >
> >         std::random_shuffle( b, e);
> >
> >         uu[axis[0]] = 0.2 + 0.2*(double)(rand()/(RAND_MAX+1.0));
> >         uu[axis[1]] = (0.6-uu[axis[0]])
> >                         +(uu[axis[0]]-0.2)
> >                         *(double)(rand()/(RAND_MAX+1.0));
> >         uu[axis[2]] = 1.0-(uu[axis[0]] + uu[axis[1]] );
> >
> >         ss[0] += uu[0];
> >         ss[1] += uu[1];
> >         ss[2] += uu[2];
> >     }
> >
> >     std::cout << "\n"
> >         << ss[0]/nn
> >         << "/" << ss[1]/nn
> >         << "/" << ss[2]/nn
> >         << "\n";
> >
> >     system("pause");
> > }
> >
> >
> >
> >
> > > -----Original Message-----
> > > From: ML [mailto:[hidden email]]
> > > Sent: Wednesday, 8 September 2004 7:23 PM
> > > To: Hurd, Matthew
> > > Cc: Ferdinando Ametrano
> > > Subject: Re: [Quantlib-users] random generation of constrained portfolio
> > > allocation weights
> > >
> > > Matthew,
> > >
> > > I wrote a small piece of code (cf below) to test your suggestion. After
> 1
> > > million runs the first moments of the generated numbers are:
> > >
> > > 0.30 / 0.35 / 0.35
> > >
> > > However, the problem being symmetrical, the first moments should be
> equal
> > > (to 1/3).
> > >
> > > -Mario
> > >
> > > ===========================================================
> > > #include <iostream>
> > > #include <stdlib.h>
> > >
> > > using namespace std;
> > >
> > > const int nn = 1000000;
> > >
> > > int main() {
> > >   double ss11 = 0.0;
> > >   double ss21 = 0.0;
> > >   double ss31 = 0.0;
> > >   for(int j=0; j<nn; j++) {
> > >     double uu1 = 0.2+0.2*(double)(random()/(RAND_MAX+1.0));
> > >     double uu2 = (0.6-uu1)+(uu1-0.2)*(double)(random()/(RAND_MAX+1.0));
> > >     double uu3 = 1.0-uu1-uu2;
> > >     //    cout << uu1 << "/" << uu2 << "/" << uu3 << endl;
> > >     ss11 += uu1;
> > >     ss21 += uu2;
> > >     ss31 += uu3;
> > >   }
> > >   cout << endl << ss11/nn << "/" << ss21/nn << "/" << ss31/nn << endl;
> > > }
> > >
> > > ========================================================
> > > ----- Original Message -----
> > > From: "Hurd, Matthew" <[hidden email]>
> > > To: "Ferdinando Ametrano" <[hidden email]>;
> > > <[hidden email]>
> > > Sent: Tuesday, September 07, 2004 9:05 AM
> > > Subject: RE: [Quantlib-users] random generation of constrained portfolio
> > > allocation weights
> > >
> > >
> > > > The below distribution will not be uniformly random (depending on what
> > > > this means to you), but neither will rejecting illegal cases.
> > > >
> > > > Using your [0-40] example:
> > > >
> > > > 1. Random first number 20-40.  Has to be at least 20 otherwise no
> viable
> > > > solution.
> > > >
> > > > 2.  Next random number to give a sum of at least 60, so the last
> number
> > > > may be valid (it has to be <= 40).  That is, if the first number is
> 35,
> > > > then the second number must be [25-40] to make a viable triple.
> > > >
> > > > 3.  Obviously, the third number is 100 - sum of the first two.
> > > >
> > > > Trivial to generalise.
> > > >
> > > > Is that what you're after?
> > > >
> > > > Regards,
> > > >
> > > > Matt Hurd.
> > > > _________________
> > > >
> > > > Matt Hurd
> > > > +61.2.8226.5029
> > > > [hidden email]
> > > > Susquehanna
> > > > _________________
> > > >
> > > > > -----Original Message-----
> > > > > From: [hidden email]
> > > > [mailto:quantlib-users-
> > > > > [hidden email]] On Behalf Of Ferdinando Ametrano
> > > > > Sent: Tuesday, 7 September 2004 12:53 AM
> > > > > To: QuantLib-users
> > > > > Subject: [Quantlib-users] random generation of constrained portfolio
> > > > > allocation weights
> > > > >
> > > > > Hi all
> > > > >
> > > > > I need to generate random weights for a portfolio allocation, with
> max
> > > > > constraints on the weights, no short sale allowed (e.g. 3 assets,
> each
> > > > one
> > > > > in the [0%, 40%] range)
> > > > >
> > > > > I have no problem for the unconstrained generation, using
> > > > (quasi)random
> > > > > sequences of dimension 3 that I normalize so that their sum is 100%.
> > > > I'm
> > > > > not sure this approach is on solid theoretical ground, but it works.
> > > > >
> > > > > Anyway when it comes to constrained generation many problems arise,
> > > > and I
> > > > > haven't found an efficient generation algorithm. Rejection of the
> > > > > unconstrained portfolio is inefficient, of course.
> > > > >
> > > > > Hints, suggestions, thoughts?
> > > > >
> > > > > Even better would be a ready to be coded algorithm ;-)
> > > > >
> > > > > ciao -- Nando
> > > > >
> > > > >
> > > > >
> > > > >
> > > > > -------------------------------------------------------
> > > > > This SF.Net email is sponsored by BEA Weblogic Workshop
> > > > > FREE Java Enterprise J2EE developer tools!
> > > > > Get your free copy of BEA WebLogic Workshop 8.1 today.
> > > > > http://ads.osdn.com/?ad_id=5047&alloc_id=10808&op=click
> > > > > _______________________________________________
> > > > > Quantlib-users mailing list
> > > > > [hidden email]
> > > > > https://lists.sourceforge.net/lists/listinfo/quantlib-users
> > > >
> > > >
> > > >
> > > > IMPORTANT: The information contained in this email and/or its
> attachments
> > > is confidential. If you are not the intended recipient, please notify
> the
> > > sender immediately by reply and immediately delete this message and all
> its
> > > attachments.  Any review, use, reproduction, disclosure or dissemination
> of
> > > this message or any attachment by an unintended recipient is strictly
> > > prohibited.  Neither this message nor any attachment is intended as or
> > > should be construed as an offer, solicitation or recommendation to buy
> or
> > > sell any security or other financial instrument.  Neither the sender,
> his or
> > > her employer nor any of their respective affiliates makes any warranties
> as
> > > to the completeness or accuracy of any of the information contained
> herein
> > > or that this message or any of its attachments is free of viruses.
> > > >
> > > >
> > > >
> > > > -------------------------------------------------------
> > > > This SF.Net email is sponsored by BEA Weblogic Workshop
> > > > FREE Java Enterprise J2EE developer tools!
> > > > Get your free copy of BEA WebLogic Workshop 8.1 today.
> > > > <a href="http://ads.osdn.com/?ad_idP47&alloc_id808&opÌk">http://ads.osdn.com/?ad_idP47&alloc_id808&opÌk
> > > > _______________________________________________
> > > > Quantlib-users mailing list
> > > > [hidden email]
> > > > https://lists.sourceforge.net/lists/listinfo/quantlib-users
> > >
> >
>

[Hurd, Matthew]

> I agree, your method seems to be OK for the original example {0.4,
0.4, 0.4}
> or the general symmetrical  problem {M, M,..., M}, 1/N<=M<=1, although
I
> would suggest some more testing, especially in higher dimensions.

Also, perhaps the question is wrong.  For example, if you have
constraints of 0-20% for 500 stocks in an index, attacking with a
uniform distribution for each variate will result in the first few being
allocated reasonable numbers followed by practically nothing for the
rest as the weights available for allocation will, essentially, be
consumed.  This will result in a result set where there are a few spikes
and lots of zero values, which is probably not what you're after.  You
need more satisfactory constraints to satisfactorily satisfy or a better
than uniform distribution :-)

$0.02

Matt.



IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments.  Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited.  Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument.  Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.