                   *********************************
                   *                               *
                   *  USING CG_DESCENT WITH CUTEst *
                   *                               *
                   *********************************

              ( Last modified on 8 Apr 2014 at 11:30:00 )


WHAT IS CG_DESCENT?
-------------------

The CG_DESCENT package is a nonlinear congugate-gradient
method for large-scale unconstrained minimization designed 
by William Hager (U. Florida) and Hongchao Zhang (Louisiana State Univ.).

HOW DO I GET CG_DESCENT?
------------------------

See

  http://www.math.ufl.edu/~hager/papers/CG/

COMPILING THE OBJECT MODULE FOR CG_DESCENT
------------------------------------------

The CG_DESCENT file cg_descent.c should be compiled, and the resulting 
file cg_descent.o should be placed in either the user-defined directory 
$CG_DESCENT or in $CUTEST/objects/(architecture)/double/ for the architecture
you intend to use. This is done automatically by the script cg_cutest_install
in the cg_descent distribution.

There is no single-precision version.

USING THE CG_DESCENT INTERFACE TOOL
-----------------------------------

The command to solve a problem in SIF format contained in the file
probname.SIF is

runcutest -p cg_descent -D probname.SIF

See the man page for runcutest for more details or other options.

If no CG_DESCENT.SPC file is present in the current directory,
then the default parameter values specified in cg_default are used.
Optionally, new parameter values to overwrite the default values can
be stored in a file CG_DESCENT.SPC in the directory where the runcutest
command is executed.  The format of the file CG_DESCENT.SPC is the
parameter name starting in column 1 followed by 1 or more spaces and
then the parameter value. The parameter names are case sensitive.
If the parameter value is true or false, then use 1 for true and 0
for false. The default file is as follows:

grad_tol     1.e-6   (relative stopping tolerance--see doc for StopFac)
PrintFinal   0       (0 no print, 1 print error messages, final error)
PrintLevel   0       (0 no print, 1 intermediate results)
PrintParms   0       (0 no print, 1 display parameter values)
LBFGS        0       (0 use LBFGS when memory>=n, 1 always use LBFGS)
memory       11      (number of LBFGS vectors stored in memory)
SubCheck     8       (check subspace condition if SubCheck*mem)
SubSkip      4       (check subspace condition every Subskip*mem iterations)
eta0         0.001   (enter subspace if subsp.dimension=memory & grad<=eta0)
eta1         0.900   (enter subspace if subsp.dimension=memory & rel grad<=eta1)
eta2         1.e-10  (enter subspace if rel grad<=eta2)
AWolfe       0       (0 (Wolfe -- see AWolfeFac above) 1 (approx Wolfe)
AWolfeFac    1.e-3   (AWolfe = 0 => set AWolfe = 1 if |f-f0| < Awolfe_fac*Ck)
Qdecay       0.7     (used in Qk update: Qk = Qdecay*Qk + 1)
nslow        1000    (terminate if>nslow iterations without strict improvement)
StopRule     1       (1 |grad|_infty<=max(tol,|grad|_0*StopFact,0 <=tol*(1+|f|))
StopFac      0.e-12  (factor multiplying starting |grad|_infty in StopRule)
PertRule     1       (0 => eps, 1 => eps*Ck)
eps          1.e-6   (perturbation parameter for computing fpert)
egrow        10.0    (factor by which eps grows when line search fails)
QuadStep     1       (use initial quad interpolation in line search)
QuadCutOff   1.e-12  (QuadStep if relative change in f > QuadCutOff)
QuadSafe     1.e-10  (max factor by which a quad step can reduce the step size)
UseCubic 1   1       (use a cubic step when possible) 
CubicCutOff  1.e-12  (use cubic step when |f_k+1 - f_k|/|f_k| > CubicCutOff)
SmallCost    1.e-30  (|f| < SmallCost*starting cost => skip QuadStep)
debug 0      0       (no debugging) 1 (check for no increase in f)
debugtol     1.e-10  (check that f_k+1 - f_k <= debugtol*C_k when debug=1)
step 0       0       (no initial line search guess) 1 (guess in gnorm)
maxit        1000000 (abort cg after maxit iterations)
ntries       50      (max # times bracketing interval grows during expansion)
ExpandSafe   200.0   (max factor secant step increases step in expansion phase)
SecantAmp    1.05    (factor by which secant step is amplified during expansion)
RhoGrow      2.0     (factor by which rho grows during expansion phase)
neps         5       (maximum number of times that eps is updated)
nshrink      10      (maximum number of times the bracketing interval shrinks)
nline        50      (maximum number of iterations in line search)
restart_fac  6.0     (restart cg in restart_fac*n iterations)
feps         0.0     (stop when value change <= feps*|f|)
nan_rho      1.3     (growth fact when finding bracketing interval after NaN)
nan_decay    0.1     (decay factor for stepsize after NaN)
delta        0.1     (Wolfe line search parameter)
sigma        0.9     (Wolfe line search parameter)
gamma        0.66    (required decay factor in interval)
rho          5.0     (interval growth factor used to get bracketing interval)
psi0         0.01    (factor used in starting guess for iteration 1)
psi_lo       0.1     (evaluate in [psi_lo, psi_hi]*psi2*previous step 
psi_hi       10.0     during QuadStep))
psi1         1.0     (factor previous step multiplied by in QuadStep)
psi2         2.0     (factor previous step is multipled by for startup)
AdaptiveBeta 0       (T => choose beta adaptively, F => use theta)
BetaLower    0.4     (lower bound factor for beta)
theta        1.0     (parameter describing the cg_descent family)
qeps         1.e-12  (parameter in cost error for quadratic restart criterion)
qrule        1.e-8   (parameter used to decide if cost is quadratic)
qrestart     6       (# of its the function should be ~quadratic before restart)

The reader is referred to the paper quoted below and the code itself if he or 
she wishes to modify these parameters.

To use the BLAS, specify things like location and threading in both
$CUTEST/bin/sys/$MYARCH and $CUTEST/makefiles/$MYARCH. For example,
BLAS = "-L/data/GotoBLAS2 -lpthread"

To run with CUTEst, use the runcutest command with the -p cg_descent option.
See the man page for runcutest for more details of other options.

REFERENCES
----------

W. W. Hager and H. Zhang, 
  A new conjugate gradient method with guaranteed descent 
  and an efficient line search,
  SIAM Journal on Optimization, 16 (2005), 170-192.

W. W. Hager and H. Zhang, 
  Algorithm 851: CG_DESCENT, A conjugate gradient method with 
  guaranteed descent,
  ACM Transactions on Mathematical Software, 32 (2006), 113-137.

W. W. Hager and H. Zhang, 
  A survey of nonlinear conjugate gradient methods,
  Pacific Journal of Optimization, 2 (2006), pp. 35-58.

W. W. Hager and H. Zhang, 
  Limited memory conjugate gradients,
  SIAM Journal on Optimization, 23 (2013), 2150-2168.
