   SPG: NONMONOTONE SPECTRAL PROJECTED GRADIENT METHOD
   ---------------------------------------------------

This file briefly describes Fortran 77 software that implements the
nonmonotone spectral projected gradient (SPG) algorithm. The SPG method
applies to constrained optimization problems of the form

                 min f(x) subject to x in Omega,

where Omega is a closed convex set in R^n. It is assumed that f is
defined and has continuous partial derivatives on an open set that
contains Omega. Users of the software must supply subroutines to compute
the function f(x), its gradient g(x), and projections of an arbitrary
point x onto Omega. Information about the Hessian matrix is not
required and the storage requirements are minimal. Hence the algorithm
is appropriate for large-scale convex-constrained optimization problems
with affordable projections onto the feasible set. Note that the
algorithm is also suitable for unconstrained optimization problems.
(In such cases, Omega = R^n and the projection routine does nothing.)

The algorithm is fully described in

E. G. Birgin, J. M. Martinez, and M. Raydan, "Nonmonotone spectral
projected gradient methods on convex sets", SIAM Journal on Optimization
10, pp. 1196-1211, 2000.

and

E. G. Birgin, J. M. Martinez, and M. Raydan, "SPG: software for
convex-constrained optimization", ACM Transactions on Mathematical
Software, 2001 (to appear).

It combines the projected gradient method with two new features in
optimization. First, it extends the typical globalization strategies
associated with these methods to the nonmonotone line search scheme
developed by Grippo, Lampariello and Lucidi. Second, it uses the
spectral steplength introduced by Barzilai and Borwein and analyzed by
Raydan. This choice of steplength requires little computational work and
greatly speeds up the convergence of gradient methods for unconstrained
problems.


USAGE OF THE SPG PACKAGE
------------------------

The distribution of the software has 3 source files called spg.f,
spgma1.f and spgma2.f. The first one contains the most important
subroutine of the package, which implements the SPG method itself. The
other two files are main programs to test the SPG method in examples 1
and 2 described below.


Example 1:
----------

This uses SPG to solve an easy (very easy) bound-constrained problem. The
aim of this example is not to show the capabilities of the method but to
be useful as an easy master file that could be modified to solve your
own problem.

The compilation process uses the Fortran compiler f77 or any other
compatible compiler. To compile this example on a Unix or Linux system,
type
   f77 spgma1.f spg.f -o spgma1
to generate an executable file called spgma1. Then type
   spgma1   (or  ./spgma1)
to see the results, which will appear on the screen.

To test SPG on your own problem you will need to modify subroutines
EvalF, EvalG and Proj in file spgma1.f. These subroutines evaluate the
objective function and its gradient and project an arbitrary point
onto the feasible region, respectively.


Example 2:
----------

This uses SPG to solve a location problem described in the ACM TOMS paper.
The master file of this example (spgma2.f) generates the problems,
calls the optimizer to solve them, and writes some reports (tables).

Brief description of the problem:

A regular grid is considered. This grid is the space at which a set
of cities (represented by polygons) will be built. Beforehand, a reserved
area (rectangle) is defined, where almost nothing can be done.
This reserved area will contain a hydro generation plant to supply energy
to the cities.  In the remaining space, the cities are built. At each point
of the grid (excluding the central region) a city (represented by a polygon)
will be built with a previously defined probability. To transmit energy from
the plant to the cities, a tower inside each city and a tower inside the
central region must be constructed. The objective of the problem is to
determine the location of these towers in order to minimize the sum of the
distances from each city tower to the central one.

To compile this example on a Unix or Linux system, type

  f77 spgma2.f spg.f -o spgma2

to generate an executable file called spgma2. Then type spgma2 and
follow the instructions on the screen. You will be asked for the number
of horizontal and vertical points in the grid, the probability of having
a polygon (city) at a grid point, and the minimum and maximum number of
vertices of the polygons. If you enter the values

   1  100  100  0.01  3  5

you will be generating and solving the first problem given in the paper.
These numbers mean that you are generating problem number 1, with 100
horizontal and 100 vertical points in the grid, that the probability of
having a polygon at a grid point is 0.01, and that the polygons will
have between 3 and 5 vertices or sides.

The data for the whole set of 45 problems is given below. Each column
means: identifier of the problem, number of horizontal and vertical
points in the grid, the probability of having a polygon (city) at a grid
point, and the minimum and maximum number of vertices of the polygons,
respectively. The characteristics of each of these problems (dimension
and number of constraints) as well as some information on the solutions
are given in the paper. For each problem, spgma2.f also generates an
output file with the optimal location of the city towers, the central
tower, and the distances from each city tower to the central one.

  1  100  100 0.01 3   5
  2  100  100 0.01 3  13
  3  100  100 0.01 3  21
  4  100  100 0.02 3   5
  5  100  100 0.02 3  13
  6  100  100 0.02 3  21
  7  100  100 0.03 3   5
  8  100  100 0.03 3  13
  9  100  100 0.03 3  21
 10  100  100 0.04 3   5
 11  100  100 0.04 3  13
 12  100  100 0.04 3  21
 13  100  100 0.05 3   5
 14  100  100 0.05 3  13
 15  100  100 0.05 3  21
 16  100 1000 0.01 3   5
 17  100 1000 0.01 3  13
 18  100 1000 0.01 3  21
 19  100 1000 0.02 3   5
 20  100 1000 0.02 3  13
 21  100 1000 0.02 3  21
 22  100 1000 0.03 3   5
 23  100 1000 0.03 3  13
 24  100 1000 0.03 3  21
 25  100 1000 0.04 3   5
 26  100 1000 0.04 3  13
 27  100 1000 0.04 3  21
 28  100 1000 0.05 3   5
 29  100 1000 0.05 3  13
 30  100 1000 0.05 3  21
 31 1000 1000 0.01 3   5
 32 1000 1000 0.01 3  13
 33 1000 1000 0.01 3  21
 34 1000 1000 0.02 3   5
 35 1000 1000 0.02 3  13
 36 1000 1000 0.02 3  21
 37 1000 1000 0.03 3   5
 38 1000 1000 0.03 3  13
 39 1000 1000 0.03 3  21
 40 1000 1000 0.04 3   5
 41 1000 1000 0.04 3  13
 42 1000 1000 0.04 3  21
 43 1000 1000 0.05 3   5
 44 1000 1000 0.05 3  13
 45 1000 1000 0.05 3  21

Observation:
------------

As the aim of this README file is not to reproduce the information in
the above publications, please read the numerical results section of the
papers for details. If, after reading it, you continue having problems
to run the programs, please do not hesitate in contact any of the authors.


AUTHORS INFORMATION
-------------------

Ernesto G. Birgin (egbirgin@ime.usp.br)
Department of Computer Science, 
Institute of Mathematics and Statistics, 
University of Sao Paulo,
Rua do Matao 1010, Cidade Universitaria, 
05508-900 Sao Paulo SP, Brazil

Jose Mario Martinez (martinez@ime.unicamp.br)
Department of Applied Mathematics, 
IMECC-UNICAMP, CP 6065, 
13081-970 Campinas SP, Brazil

Marcos Raydan (mraydan@reacciun.ve)
Departamento de Computacion, 
Facultad de Ciencias, 
Universidad Central de Venezuela, 
Ap. 47002, Caracas 1041-A,
Venezuela 

