readme

数学计算程序

asa_cg is an active set algorithm for solving a bound constrained
optimization problem of the form:

    min f (x)  subject to  lo <= x <= hi

asa_cg utilizes both the gradient projection algorithm and
the conjugate gradient algorithm, as implemented in
the code cg_descent, to approximately solve the active set
subproblems. The active set algorithm was developed in the
following papers (see www.math.ufl.edu/~hager/papers/CG):

[1] W. W. Hager and H. Zhang, A new active set algorithm
    for box constrained optimization, SIAM Journal on
    Optimization, 17 (2006), pp. 526-557.

[2] W. W. Hager and H. Zhang, Recent advances in bound
    constrained optimization, in System Modeling and Optimization,
    F. Ceragioli, A. Dontchev, H. Furuta, K. Marti, and
    L. Pandolfi, eds., Springer, 2006, pp. 67-82. (22nd IFIP
    TC 7 Conference on System Modeling and Optimization,
    Turin, Italy, July 18-22, 2005). 

The cg_descent algorithm is developed in the papers:

[3] 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.

[4] 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.

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

This directory provides a C implementation of asa_cg and
the codes needed to run asa_cg in the CUTEr testing
environment (http://hsl.rl.ac.uk/cuter-www/).  The program
which calls asa_cg should include the header file cg_user.h.
An example showing how to call asa_cg is given in driver1.c.
For additional related examples, see the drivers in the
cg_descent distribution (www.math.ufl.edu/~hager/paper/CG).
The user must provide routines to evaluate the objective
function and its gradient.  Performance is often improved
if the user also provides a routine to simultaneously
evaluate the objective function and its gradient (see drive1.c).
In the simplest case, asa_cg is invoked with a statement
of the form:

asa_cg (x, lo, hi, n, NULL, NULL, NULL, tol, myvalue, mygrad, NULL, NULL) ;

where x is a pointer to an array which contains the starting
guess on input and the solution on output, lo and hi are pointers
to arrays containing the upper and lower bounds, n is the problem
dimension, tol is the computing tolerance (max norm of the
projected gradient), myvalue is a routine to evaluate
the user's objective function, and mygrad is a routine to evaluate
the gradient of the user's objective function. The 5 NULL
arguments could be replaced by the following (in order):
a structure to store execution statistics, a structure containing
algorithm parameters for the conjugate gradient routine,
a structure containing algorithm parameters for the gradient project
algorithm, a pointer to a routine which evaluates the
objective function and its gradient, and a pointer to a work
array. It the work array is not provided, then the code
allocates and frees memory. If the routine to simultaneously evaluate
the objective function and its gradient is not provided, then the
code will use myvalue and mygrad to compute the value and
gradient independently. When the algorithm parameters are not
provided, then the default parameter values will be used
(see asa_default and asa_cg_default for their values).

We also provide codes to interface asa_cg to the CUTEr
testing environment. The procedure for incorporating asa_cg
in CUTEr is as follows:

1. Put asa_user.h into $CUTER/common/include
2. Put asa_cgma.c into $CUTER/common/src/tools
3. In $CUTER/common/src/tools, "gcc -lm -O3 -c asa_cgma.c"
4. "cp asa_cgma.o $MYCUTER/double/bin"
5. In the directory where you put asa_cg, type "make" and then
   "cp asa_cg.o $MYCUTER/double/bin"
6. "cp asa_cg.pro $CUTER/build/prototypes"
   "cp sdasa_cg.pro $CUTER/build/prototypes"
7. "cd $MYCUTER/bin"
8. type the following command twice:

sed -f $MYCUTER/double/config/script.sed $CUTER/build/prototypes/pack.pro > pack

where "pack" is first "asa_cg" and then "sdasa_cg"

9. "chmod a+x asa_cg" and "chmod a+x sdasa_cg"

You can run a problem by cd'ing to the directory where the sif files
are stored and typing, for example, "sdasa_cg ALLINIT"

NOTE: to run valgrind with the code, edit the program "runpackage"
found in "$MYCUTER/bin" as follows:
near the end of the program, change "$EXEC/${PAC}min" to
"valgrind $EXEC/${PAC}min"