This bugzilla service is closed. All entries have been migrated to https://gitlab.com/libeigen/eigen

Bug 733

Summary: CG: Documentation proposes degeneration to Gradient Descent
Product: Eigen Reporter: waechter.mi
Component: SparseAssignee: Nobody <eigen.nobody>
Status: RESOLVED FIXED    
Severity: minor CC: gael.guennebaud, waechter.mi
Priority: Normal    
Version: 3.2   
Hardware: All   
OS: All   
Whiteboard:

Description waechter.mi 2014-01-30 16:08:11 UTC
The documentation of ConjugateGradient gives an example of how CG can be run step by step:

"Here is a step by step execution example starting with a random guess and printing the evolution of the estimated error:
* x = VectorXd::Random(n);
* cg.setMaxIterations(1);
* int i = 0;
* do {
*   x = cg.solveWithGuess(b,x);
*   std::cout << i << " : " << cg.error() << std::endl;
*   ++i;
* } while (cg.info()!=Success && i<100);
Note that such a step by step excution is slightly slower."


With this my optimization problem took ~1400 iterations and later I found out that it only takes ~180 if not done step wise.

As I see it, every time solveWithGuess is called CG is restarted. CG's first iteration is identical to gradient descent and thus the whole optimization effectively degenerates to gradient descent. The note "that such a step by step excution is slightly slower." does not really capture it. Also the evolution of the estimated errors that are being printed to std::cout are not the true CG errors because real CG would converge quicker.

Maybe the documentation can be changed such that it
1. suggests to use much more than 1 iteration in each solveWithGuess step.
2. mentions that too small maxIteration numbers make CG degenerate?
Comment 1 Gael Guennebaud 2015-02-10 22:30:49 UTC
https://bitbucket.org/eigen/eigen/commits/a482ead8ccbf/
https://bitbucket.org/eigen/eigen/commits/e77df591e0b9/
User:        blechta
Summary:     Fix bug 733: step by step solving is not a good example for solveWithGuess
Comment 2 Nobody 2019-12-04 12:58:04 UTC
-- GitLab Migration Automatic Message --

This bug has been migrated to gitlab.com's GitLab instance and has been closed from further activity.

You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.com/libeigen/eigen/issues/733.