GPAV is a monotonic regression algorithm. It provides a high-accuracy
approximate solution to the monotonic regression problem which admits
the following equivalent formulations.

Formulation 1:

Given a set of N observations X={(X(i,1),...,X(i,p)), i=1..N},
a corresponding response vector Y={Y(i), i=1..N} and a vector of
weights W={W(i), i=1..N}, find a vector YFit={YFit(i), i=1..N} which is
as close as possible, in the least-squares sense, to the response
vector Y and nondecreasing with respect to X. This means that YFit
solves the problem:

     min norm(W'*(f-Y)).^2 subject to f(i)<=f(j) whenever X(i,:)<=X(j,:)
      f       

Formulation 2:

For a set of N observations i=1..N, a binary [N x N] adjacency matrix
adj is supposed to be given. adj represents a partial order
'observation j dominates observation i' so that adj(i,j)=1 if j
dominates i. The observations should be enumerated so that adj(i,j)=1
implies i<j, i.e. adj is upper triangular. Given adj, a response vector
Y={Y(i), i=1..N} and a vector of weights W={W(i), i=1..N}, find a
vector YFit={YFit(i), i=1..N} which is as close as possible, in the
least-squares sense, to the response vector Y and whose components are
partially ordered in accordance with the matrix adj. In other words,
YFit must solve the problem:

     min norm(W'*(f-Y)).^2 subject to f(i)<=f(j) whenever adj(i,j)=1
      f   

GPAV algorithm treats observations sequentially (in accordance with the
increase of X or partial order) and merges some adjacent observations
into sets which are called blocks. The fitted values for the
observations of the same block are equal to the weighted average value
of their response values.

For the details, see:

O. Burdakov, O. Sysoev, A. Grimvall and M. Hussian. An O(n2) algorithm
for isotonic regression. In: G. Di Pillo and M. Roma (Eds) "Large-Scale
Nonlinear Optimization". Series: "Nonconvex Optimization and Its
Applications", Springer-Verlag, (2006) 83, pp. 25-33.
    
O. Burdakov, A. Grimvall and O. Sysoev. Data preordering in generalized
PAV algorithm for monotonic regression. Journal of Computational
Mathematics. (2006) 24, No. 6, pp. 771-790.


Files description:

GPAV.m         GPAV algorithm for Formulation 2.
monreggpav.m   GPAV algorithm for Formulation 1. Implemented as automatic
               transformation into Formulation 2 and running GPAV.m.
example.m      A simple example of how to use monreggpav.m.
Simulation.xls A data set in the Excel format used in example.m.


Example

Given X=((0,1); (1,0); (1,1)), Y= (4,1,0)' and W=(1,1,1)'. These are
input parameters for monreggpav.m.

GPAV.m can be used instead, if to define the partial order as follows:
observation 3 dominates observation 1, observation 3 dominates
observation 2, which implies adj(1,3)=1, adj(2,3)=1, and adj(i,j)=0 for
all other cases.

Obviously, Y violates monotonicity requirements, because Y(1)>Y(3) and
Y(2)>Y(3). The GPAV algorithm produces the set Blocks={[0], [2], [1,3]}
which means that the resulting vector is YFit(1)=YFit(3)=2, YFit(2)=1.
This vector is nondecreasing with respect to X and consistent with adj.

Version: 09-09-2008