forum.alglib.net
http://forum.alglib.net/

How can I limit step length of each variable?
http://forum.alglib.net/viewtopic.php?f=2&t=305
Page 1 of 1

Author:  ymsysu [ Sun Feb 20, 2011 8:12 am ]
Post subject:  How can I limit step length of each variable?

Hi, I'm using minasa subpackage to optimize a real 1d array x.
Now I want to limit step length of each element of x.
Of course, I can define the maximum step length StpMax.
However, this parameter seems only limit the step sum of the whole array but not a single variable.(Yes?)
So how can I limit step length of each element of x?

Author:  Sergey.Bochkanov [ Mon Feb 21, 2011 10:13 am ]
Post subject:  Re: How can I limit step length of each variable?

Current version of ALGLIB doesn't support different step limits for different coordinates. But why do you need such functionality? Are your variables have different scales?

Author:  ymsysu [ Tue Feb 22, 2011 3:40 am ]
Post subject:  Re: How can I limit step length of each variable?

Sergey.Bochkanov wrote:
Current version of ALGLIB doesn't support different step limits for different coordinates. But why do you need such functionality? Are your variables have different scales?


All variables have the same scale.
Suppose the vector to be optimized is v0 = [a0; b0; c0; d0].
After one iteration, v becomes v1 = [a1; b1; c1; d1].
Current version of ALGLIB can limit the step of v : ||v1 - v0|| < step,
but what I need is to limit the steps of each variable : ||a1 - a0|| < step, ||b1 - b0|| < step, ||c1 - c0|| < step, ||d1 - d0|| < step,
though all these step limits are the same.

Author:  Sergey.Bochkanov [ Tue Feb 22, 2011 8:10 am ]
Post subject:  Re: How can I limit step length of each variable?

It is possible to place such limit on step length, but it will require modification of the ALGLIB internals. Fortunately, you can do it yourself with only a little guidance from my side.

There are two places in the minasa subpackage where step can be limited: a) internal iterations of the gradient projection algorithm, and b) internal internal iterations of the nonlinear CG. You have to apply modifications to both places.

1. you should find "Two types of search are needed because we can't" in the source of the optimization package. You can find if/then block several lines below with ASAD1Norm(State)<=State.StpMax condition. You have to replace it by max(i=0..n-1 : abs(state.d[i]))<=State.StpMax. These lines correspond to unit step in the direction given by State.D.

2. after "alpha=1 is too large, try smaller values" you can find if/then block if State.StpMax>0 then State.Stp:=Min(State.Stp,State.StpMax). You should replace this if/then block by loop which calculates upper limit on State.Stp. You should make sure that Abs(State.D[])*State.Stp<=step_limit for all i=0..n-1. Be careful because State.D[] can be zero for some i (exactly zero, if we are at the boundary given by BndL or BndU).

3. finally, you should find two calls to MCSRCH() function below the "Make a CG step in direction given by DK[]" line. These calls use State.StpMax as upper limit on the step length. You should calculate your own step limit using same condition Abs(State.D[])*State.CurrentStepLimit<=step_limit. I recommend you to calculate it once before the first call to the MCSRCH(), and to store it as the member of the State object. Never use locals to store information because minasaiteration() function periodically returns to the calling subroutine and all information stored by you in the local variables will be lost.

Author:  ymsysu [ Wed Feb 23, 2011 4:01 am ]
Post subject:  Re: How can I limit step length of each variable?

Sergey.Bochkanov wrote:
It is possible to place such limit on step length, but it will require modification of the ALGLIB internals. Fortunately, you can do it yourself with only a little guidance from my side.

There are two places in the minasa subpackage where step can be limited: a) internal iterations of the gradient projection algorithm, and b) internal internal iterations of the nonlinear CG. You have to apply modifications to both places.

1. you should find "Two types of search are needed because we can't" in the source of the optimization package. You can find if/then block several lines below with ASAD1Norm(State)<=State.StpMax condition. You have to replace it by max(i=0..n-1 : abs(state.d[i]))<=State.StpMax. These lines correspond to unit step in the direction given by State.D.

2. after "alpha=1 is too large, try smaller values" you can find if/then block if State.StpMax>0 then State.Stp:=Min(State.Stp,State.StpMax). You should replace this if/then block by loop which calculates upper limit on State.Stp. You should make sure that Abs(State.D[])*State.Stp<=step_limit for all i=0..n-1. Be careful because State.D[] can be zero for some i (exactly zero, if we are at the boundary given by BndL or BndU).

3. finally, you should find two calls to MCSRCH() function below the "Make a CG step in direction given by DK[]" line. These calls use State.StpMax as upper limit on the step length. You should calculate your own step limit using same condition Abs(State.D[])*State.CurrentStepLimit<=step_limit. I recommend you to calculate it once before the first call to the MCSRCH(), and to store it as the member of the State object. Never use locals to store information because minasaiteration() function periodically returns to the calling subroutine and all information stored by you in the local variables will be lost.


It's so kind of you to help me like this.
Thanks for your answer very much :-)

Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/