🚀 go-pugleaf

Note cross-posting.  Followup-To: sci.math.num-analysis

As part of a statistical estimation problem I need to solve the 
following computational problem.  Perhaps one of you will recognize 
something familiar in what follows and point me in a useful direction. 

Working in some Euclidean space R^J, define the J+1 closed sets:

        S_j = { t in R^J: (G_j)*t .ge. 0 },  j = 0,...,J

where the square JxJ matrices G_j are defined as follows:

     G_0 is the JxJ identity matrix.

     For j = 1,...,J:  G_j equals the JxJ identity matrix,
     except for its j'th column, which contains only -1's.

When J = 2 the three sets look roughly like:

            |
            |
     S_1    |      S_0
            |
            |
            |______________________
           /
         /         S_2
       / 
     /  <--- 45 degree line
   / 

The three sets include their boundaries and meet at the origin.  (In 
case it helps, each of the matrices G_j has unit Jacobian and is its 
own inverse.)  For each point t in R^J let t+S_j be defined as the set 
S_j translated by the point t. 

Now we are given a set of points {v_i, i = 1,...,n} in R^J (n>>J).  
Associated with each point is one of the sets S_j.  This association 
can be represented by a list {c_i, i = 1,...,n} where each of the c_i 
is an integer in {0,...,J}, such that the set associated with v_i is 
S_(c_i).  Finally define the sets:

        Q_i = v_i + S_(c_i),   i = 1,...,n.

Each of these is a (different) translation of one of the sets S_j.


Problem 1:  Efficiently identify the partition of R^J obtained by 
considering all possible intersections of the form:

         intersect{i=1,...,n} Q^*_i

where Q^*_i is the same as either Q_i or the complement of Q_i.

Actually, all I need is one point from each non-empty set in the 
partition, plus an enumeration of whether the set is included in Q_i 
or the complement of Q_i for each i.


Problem 2:  Do problem one, but only find those members of the 
partition that are non-empty, _closed_ sets. 


Problem 3 (bonus!):  Efficiently update the solution to problem 2 as 
the v_i points are varied as a smooth function of some underlying 
parameter theta.  

(For this step I just need the enumeration of whether each set is 
included in Q_i or its complement.  I don't actually need a point in 
each set until a "final" value for theta is determined.) 

Any suggestions, pointers, or references would be greatly appreciated.  

---------------------------------------------------
Background for the problem:

A particular econometric model of discrete choice has the following 
structure.  A set of consumers i = 1,...,n are faced with a common 
choice among J+1 alternatives {0,...,J}.  Consumer i derives 
(unobserved) utility U_{i,j} from alternative j.  Suppose that 
consumers maximize utility and that there are never ties.  Then 
consumer i is observed to choose alternative j (c_i = j) if and only 
if 

(1)     -V_i in S_j

where V_i is the Jx1 vector of utility differences: 

        V_{i,j} = U_{i,j} - U_{i,0},  j = 1,...,J 

Now suppose that V_i = v_i - e_i where v_i is an observed Jx1 vector 
of determinants of utility and e_i is an unobserved Jx1 vector of 
"error" terms independently and identically distributed across the 
population of consumers according to some probability distribution F.  
Then condition (1) can be restated as

(2)     e_i in Q_i

The game is to estimate the distribution F from data on 
{v_i,c_i: i = 1,...,n} = 1, ..., J.  If we assume a particular 
parametric model for F this reduces to something like a multinomial 
logit or probit model.  A non-parametric estimate of the distribution 
can be obtained, however, by direct maximum likelihood over the set of 
all probability distributions on R^J.  It is easy to establish that 
there is no loss of generality from restricting attention to the set 
of all discrete probability distributions with support on the set of 
points identified in problem 1.  (By "no loss of generality" I mean 
that this set of distributions always includes at least one solution 
to the unrestricted nonparametric ML problem.)  Perhaps less obvious 
is that a further reduction to the set of points identified in problem 
2 is also possible. 

In problem 3 we add the further complication of assuming that v_i is 
not known directly, but instead depends (in a known way) on a 
parameter theta that is also to be estimated.

I have proof that the ML estimators are consistent.  I am now trying 
to implement them in software (at least for fairly small values of J 
and n).


--
T. Scott Thompson              email:  thompson@atlas.socsci.umn.edu
Department of Economics        phone:  (612) 625-0119
University of Minnesota        fax:    (612) 624-0209