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

N.B. These are notes for the Fortran 77 version of the package.

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,
vol. 27, pp. 340-9, 2001.

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
