I have a time series for which I want to find an approximation function consisting of piece-wise linear approximations which are derived by least square method but with the additional constraint to be continously fitted.
Given observation points 1...N and a set of segmentation points s1,....,sn with s1 = 1 sn = N and si > s(i-1), n < N: For each interval [si,s(i+1] I search a linear approximation which is continously fitted to its left and right neighbor.
For a given set [s1...sn] I was able to solve this problem analytically exactly and hence numerically as solution of a set of sn+1 linear equations for the sn gradients mi and the starting point b1 (b2-bn are not free due to the continuation constraint).
But now for a given number of segments I want to find the best segmentation points: For example with N = 20 and n = 5
I can calculate the total "cost" for a solution [1,5,10,15,20] and compare it to a solution [1,7,10,13,20] both having 4 line segments. Of all these possible segmentation with n = 5 I want to find the best one.
This is kind of a multidimensional minimization problem but with a combinatorical constraint. N typically is of magnitude 100 - 200, whereas n could be between 1 - 20.
Any ideas on approaching this problem are highly welcome.
Thanks, Stefan

I have a time series for which I want to find an approximation function consisting of piece-wise linear approximations which are derived by least square method but with the additional constraint to be continously fitted.
Given observation points 1...N and a set of segmentation points s1,....,sn with s1 = 1 sn = N and si > s(i-1), n < N: For each interval [si,s(i+1] I search a linear approximation which is continously fitted to its left and right neighbor.
For a given set [s1...sn] I was able to solve this problem analytically exactly and hence numerically as solution of a set of sn+1 linear equations for the sn gradients mi and the starting point b1 (b2-bn are not free due to the continuation constraint).
But now for a given number of segments I want to find the best segmentation points: For example with N = 20 and n = 5
I can calculate the total "cost" for a solution [1,5,10,15,20] and compare it to a solution [1,7,10,13,20] both having 4 line segments. Of all these possible segmentation with n = 5 I want to find the best one.
This is kind of a multidimensional minimization problem but with a combinatorical constraint. N typically is of magnitude 100 - 200, whereas n could be between 1 - 20.
Any ideas on approaching this problem are highly welcome.
Thanks, Stefan

Hello Comrade
I have the codes for for constructing an artificial function of one variable as shown below.But does not execute requiring some debugging especially for its initialisation as usual..This method uses an interface between multidimensional minimisation strategy and one dimensional minimization routine resulting in some unneccessary copying of vectors hither and yon,
though this should not hinder u for positive approach without disguising its inelegance atleast for concept formation.....
GoodLuck
Thanking You
As
C.R.Muthukumar(kutta)





#include "nr3.h"
#include <iostream>
#include <iomanip>
#include <fstream>
#include <math.h>
#include "brent.h"
#define brent
#define mnbrak
#define myRan
#include "ran.h"

using namespace std;

int ncom;
Doub(*nrfunc)(VecDoub&);
VecDoub *pcom_p,*xicom_p;



class Function{


public:
void linmin(VecDoub_I &p,VecDoub &xi,Doub fret,Doub func(VecDoub_I &));

Doub f1dim(const Doub x);

};
class beta{
float p;
public :
beta(float a)
{
cout << "\n betaconstructed";
}

void f1dim( Doub )
{



}
};

void linmin(VecDoub_I &p,VecDoub &xi,Doub fret,Doub func(VecDoub_I &))
{
int j;
const Doub TOL = 1.e-8;
Doub xx,xmin,fx,fb,fa,bx,ax,f1dim;
int n =p.size();
ncom = n;
pcom_p = new VecDoub(n);
xicom_p = new VecDoub(n);
// nrfunc = func;
VecDoub &pcom = *pcom_p, &xicom=*xicom_p;
for(j=0;j<n;j++)
{
pcom[j]= p[j];
xicom[j]=xi[j];
}
ax=0.0;
xx=1.0;
mnbrak(ax,xx,bx,fa,fx,fb,f1dim);
fret =brent(ax,xx,bx,f1dim,TOL,xmin);
for(j=0;j<n;j++)
{
xi[j] *= xmin;
// p[j] += xi[j];
cout << " p[j]" <<" " << p[j] << endl;
}
delete xicom_p;
delete pcom_p;
}
extern int ncom;
extern Doub (*func)(VecDoub_I &);
extern VecDoub *pcom_p, *xicom_p;
Doub f1dim(const Doub x)
{
int j;
VecDoub xt(ncom);
VecDoub &pcom = *pcom_p ,& xicom = *xicom_p;
for(j=0; j<ncom;j++)
xt[j] =pcom[j] +x*xicom[j];
return nrfunc(xt);
}



:)