MATLAB Central Newsreader - Is it possible to optimize a spline function?

Is it possible to optimize a spline function?

Hailey Yang — Wed, 01 Oct 2008 00:29:02 -0400

As an example, if I use function csapi to approximate the space which are defined by some sample points and I let cs=csapi(...), then after I get this, is it possible to use some of the optimization functions, such as fmincon, to optimize this function and get the optimum? Or, if not using those optimization functions, are there other ways to optimize the spline function cs?

Thank you very much for your help!

Hailey

Re: Is it possible to optimize a spline function?

John D'Errico — Wed, 01 Oct 2008 10:40:04 -0400

"Hailey Yang" <haileyyang@hotmail.com> wrote in message <gbug8e$2ae$1@fred.mathworks.com>...
> As an example, if I use function csapi to approximate the space which are defined by some sample points and I let cs=csapi(...), then after I get this, is it possible to use some of the optimization functions, such as fmincon, to optimize this function and get the optimum? Or, if not using those optimization functions, are there other ways to optimize the spline function cs?

Why not? Try it!

x = sort(randn(20,1));
y = -cos(x);

Obviously, a local minimum will occur at x = 0.

Can an optimizer find that point, off of an
interpolated spline? Remember that the spline
is actually only an approximation to the true
curve, so it might not always be perfect.

spl = csapi(x,y);
fun = @(X) fnval(spl,X);

LB = min(x);
UB = max(x);
Xstart = 0.5;
opts = optimset('Largescale','off','Display','off');
Xmin = fmincon(fun,Xstart,[],[],[],[],LB,UB,[],opts)

Xmin =
-5.1909e-06

HTH,
John

Re: Is it possible to optimize a spline function?

Stuart Kozola — Wed, 01 Oct 2008 19:13:36 -0400

fmincon will get you a local minima. If your surface is highly nonlinear
(has many local minima, or no true global minima) you need to take that into
account when you run the optimizer. Your choice of starting point can be
important in getting you to the global minima if there is one. You might
want to run fmincon with multiple start points to ensure that you find the
true global and don't get stuck in a local minima. You could also try
Genetic Algorithm or Simulated Annealing which are better at getting out of
local minima.

"John D'Errico" <woodchips@rochester.rr.com> wrote in message
news:gbvk24$a2m$1@fred.mathworks.com...
> "Hailey Yang" <haileyyang@hotmail.com> wrote in message
> <gbug8e$2ae$1@fred.mathworks.com>...
>> As an example, if I use function csapi to approximate the space which are
>> defined by some sample points and I let cs=csapi(...), then after I get
>> this, is it possible to use some of the optimization functions, such as
>> fmincon, to optimize this function and get the optimum? Or, if not using
>> those optimization functions, are there other ways to optimize the spline
>> function cs?
>
>
> Why not? Try it!
>
> x = sort(randn(20,1));
> y = -cos(x);
>
> Obviously, a local minimum will occur at x = 0.
>
> Can an optimizer find that point, off of an
> interpolated spline? Remember that the spline
> is actually only an approximation to the true
> curve, so it might not always be perfect.
>
> spl = csapi(x,y);
> fun = @(X) fnval(spl,X);
>
> LB = min(x);
> UB = max(x);
> Xstart = 0.5;
> opts = optimset('Largescale','off','Display','off');
> Xmin = fmincon(fun,Xstart,[],[],[],[],LB,UB,[],opts)
>
> Xmin =
> -5.1909e-06
>
> HTH,
> John
>
>

Re: Is it possible to optimize a spline function?

Hailey Yang — Fri, 03 Oct 2008 21:57:01 -0400

Thank you for your reply. My understanding for the spline approximation, which might be wrong, is that the whole region, if necessary, is seperated into different regions and each region is represented by a polynomial function. In that case, will there be any problem with optimizing each region and then comparing the optimums to get the global optimum? I guess there is a question sort of embeded in this question, which is whether the polynomial function is always convex at the positive variable region (since variables are positive in my problem).

Another seperate question is that: is it possible to do so for multivariate spline approximation?

Thank you very much!
Hailey

"Stuart Kozola" <skozola@mathworks.com> wrote in message <gc0i54$5c6$1@fred.mathworks.com>...
> fmincon will get you a local minima. If your surface is highly nonlinear
> (has many local minima, or no true global minima) you need to take that into
> account when you run the optimizer. Your choice of starting point can be
> important in getting you to the global minima if there is one. You might
> want to run fmincon with multiple start points to ensure that you find the
> true global and don't get stuck in a local minima. You could also try
> Genetic Algorithm or Simulated Annealing which are better at getting out of
> local minima.
>
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message
> news:gbvk24$a2m$1@fred.mathworks.com...
> > "Hailey Yang" <haileyyang@hotmail.com> wrote in message
> > <gbug8e$2ae$1@fred.mathworks.com>...
> >> As an example, if I use function csapi to approximate the space which are
> >> defined by some sample points and I let cs=csapi(...), then after I get
> >> this, is it possible to use some of the optimization functions, such as
> >> fmincon, to optimize this function and get the optimum? Or, if not using
> >> those optimization functions, are there other ways to optimize the spline
> >> function cs?
> >
> >
> > Why not? Try it!
> >
> > x = sort(randn(20,1));
> > y = -cos(x);
> >
> > Obviously, a local minimum will occur at x = 0.
> >
> > Can an optimizer find that point, off of an
> > interpolated spline? Remember that the spline
> > is actually only an approximation to the true
> > curve, so it might not always be perfect.
> >
> > spl = csapi(x,y);
> > fun = @(X) fnval(spl,X);
> >
> > LB = min(x);
> > UB = max(x);
> > Xstart = 0.5;
> > opts = optimset('Largescale','off','Display','off');
> > Xmin = fmincon(fun,Xstart,[],[],[],[],LB,UB,[],opts)
> >
> > Xmin =
> > -5.1909e-06
> >
> > HTH,
> > John
> >
> >
>

Re: Is it possible to optimize a spline function?

John D'Errico — Fri, 03 Oct 2008 22:48:02 -0400

"Hailey Yang" <haileyyang@hotmail.com> wrote in message <gc64fd$i3k$1@fred.mathworks.com>...
> Thank you for your reply. My understanding for the spline approximation, which might be wrong, is that the whole region, if necessary, is seperated into different regions and each region is represented by a polynomial function.

Yes. A spline is a piecewise polynomial model,
that approximates your function from your
data points. The knots or break points specify
the locations where the pieces are tied together.

> In that case, will there be any problem with optimizing each region and then comparing the optimums to get the global optimum?

Why should there be a problem?

> I guess there is a question sort of embeded in this question, which is whether the polynomial function is always convex at the positive variable region (since variables are positive in my problem).

There is no such constraint on a spline such
that it satisfies any convexity constraints, at
least unless you have constructed the spline
such that this is true.

> Another seperate question is that: is it possible to do so for multivariate spline approximation?

Yes.

John

Re: Is it possible to optimize a spline function?

Vincent Morio — Sat, 04 Oct 2008 23:55:03 -0400

"Hailey Yang" <haileyyang@hotmail.com> wrote in message <gbug8e$2ae$1@fred.mathworks.com>...
> As an example, if I use function csapi to approximate the space which are defined by some sample points and I let cs=csapi(...), then after I get this, is it possible to use some of the optimization functions, such as fmincon, to optimize this function and get the optimum? Or, if not using those optimization functions, are there other ways to optimize the spline function cs?
>
> Thank you very much for your help!
>
> Hailey

Hi,

I think that you can find some answers by looking at the work conducted by Richard Murray at Caltech university for real-time trajectory optimization by flatness approach. B-splines are used to parameterized the optimization variables (flat outputs), and the B-splines control points are then optimized by an efficient NLP solver (NPSOL by Stanford laboratory), better than fmincon!

Cheers,

V. Morio
PhD student in Automatic Control
IMS lab./University of Bordeaux, France

Re: Is it possible to optimize a spline function?

Hailey Yang — Mon, 06 Oct 2008 21:17:03 -0400

Thanks again for your reply. As for the multivariate spline approximation, I looked into the help file for spline toolbox by searching "multivariate spline", but didn't find much helpful information on what command I am supposed to do it.

I tried to use csapi, but it doesn't work once my variables x becomes a matrix, which seems suggesting that it only works for univariate approximation.

In the help file, the only relevant command to do multivariate spline is "stform", but I don't quite understand how this works even after I read the help file. Also it is said in the help file that: "At present, the toolbox works with just one kind of stform, namely a bivariate thin-plate spline and its first partial derivatives. ". Does this mean that it won't work if my function is determined by more than two variables?

Will there be other functions/commands that can do multivariate spline approximation that I missed?

Hailey

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <gc67f2$pnu$1@fred.mathworks.com>...
> "Hailey Yang" <haileyyang@hotmail.com> wrote in message <gc64fd$i3k$1@fred.mathworks.com>...
> > Thank you for your reply. My understanding for the spline approximation, which might be wrong, is that the whole region, if necessary, is seperated into different regions and each region is represented by a polynomial function.
>
> Yes. A spline is a piecewise polynomial model,
> that approximates your function from your
> data points. The knots or break points specify
> the locations where the pieces are tied together.
>
>
> > In that case, will there be any problem with optimizing each region and then comparing the optimums to get the global optimum?
>
> Why should there be a problem?
>
>
> > I guess there is a question sort of embeded in this question, which is whether the polynomial function is always convex at the positive variable region (since variables are positive in my problem).
>
> There is no such constraint on a spline such
> that it satisfies any convexity constraints, at
> least unless you have constructed the spline
> such that this is true.
>
>
> > Another seperate question is that: is it possible to do so for multivariate spline approximation?
>
> Yes.
>
> John

Re: Is it possible to optimize a spline function?

Hailey Yang — Mon, 06 Oct 2008 21:25:03 -0400

Hi, Vincent

Thank you for the information. Can I ask if the solver that they developed is publicly available?

Hailey

"Vincent Morio" <vincent.morio@mathworks.com> wrote in message <gc8von$irn$1@fred.mathworks.com>...
> "Hailey Yang" <haileyyang@hotmail.com> wrote in message <gbug8e$2ae$1@fred.mathworks.com>...
> > As an example, if I use function csapi to approximate the space which are defined by some sample points and I let cs=csapi(...), then after I get this, is it possible to use some of the optimization functions, such as fmincon, to optimize this function and get the optimum? Or, if not using those optimization functions, are there other ways to optimize the spline function cs?
> >
> > Thank you very much for your help!
> >
> > Hailey
>
> Hi,
>
> I think that you can find some answers by looking at the work conducted by Richard Murray at Caltech university for real-time trajectory optimization by flatness approach. B-splines are used to parameterized the optimization variables (flat outputs), and the B-splines control points are then optimized by an efficient NLP solver (NPSOL by Stanford laboratory), better than fmincon!
>
> Cheers,
>
> V. Morio
> PhD student in Automatic Control
> IMS lab./University of Bordeaux, France