Re: [Vxl-maintainers] Bug in conjugate gradient algorithm

[Ian S. <sc...@im...>]

David,

Thanks for the bug report.

Amazingly, given that the f2c-ed netlib code is usually impenetrable, 
poorly documented, etc, I did work out what is going on. Your 
inconsistent function appeared to be causing two max_count problems in 
the optimiser, as it tries to bracket the minimum, and establish a 
sensible step size. The y and z__ arrays which stored all the results 
during these loops were not quite large enough to keep all the results 
when the first loop and then the second ran to max_iterations.

Your band-aid is a perfectly valid fix, and has now been committed along 
with your test case, and some marginally better diagnostics.

Thanks again,
Ian.

On 02/12/2010 15:35, David Ryan wrote:
> Hi all,
>
> I believe there's a bug in the conjugate gradients algorithm. It occurs
> when the algorithm is "unable to satisfy the armijo condition" (ie. when
> the current line search is unable to sufficiently minimise the
> function). The error occurs in v3p\netlib\napack\cg.c when exiting
> function cg_. The error message in VS is: "Run-Time Check Failure #2 -
> Stack around the variable z__ was corrupted", which usually means z__
> was accessed out of bounds. On line 120 of cg.c it is declared as
> z__[50], however line 1356 accesses z__[*j] where *j=2,3,...,53 at
> run-time. (N.B: In this subroutine the pointer z__ has been locally
> decremented so it is safe to access indices 1-50 instead of 0-49).
>
> The following code reproduces the error. The function to be minimized is
> intentionally bad, but it should not crash the program:
>
> class func : public vnl_cost_function
> {
> public:
>      func() : vnl_cost_function(1) {}
>      double f(vnl_vector<double> const& x)
>      {
>          return 0;
>      }
>      void gradf(vnl_vector<double> const& x, vnl_vector<double>& gradient)
>      {
>          gradient[0] = 1;
>      }
> };
>
> int main()
> {
>      vnl_vector<double> guess(1, 0);
> func f;
> vnl_conjugate_gradient minimizer(f);
> minimizer.minimize(guess);
> }
>
>
> A band-aid solution is to change the declaration of z__[50] to z__[53],
> and similarly y[50] to y[53].
>
> David.
>
>
>
> ------------------------------------------------------------------------------
> Increase Visibility of Your 3D Game App&  Earn a Chance To Win $500!
> Tap into the largest installed PC base&  get more eyes on your game by
> optimizing for Intel(R) Graphics Technology. Get started today with the
> Intel(R) Software Partner Program. Five $500 cash prizes are up for grabs.
> http://p.sf.net/sfu/intelisp-dev2dev
>
>
>
> _______________________________________________
> Vxl-maintainers mailing list
> Vxl...@li...
> https://lists.sourceforge.net/lists/listinfo/vxl-maintainers