DQED
Bounded Constrained Least Squares/Nonlinear Equations
Double precision version


DQED is a FORTRAN90 library which solves (square) systems of nonlinear equations, or minimizes the residual in a set of nonlinear equations, using least squares, by Richard Hanson and Fred Krogh.

The user may include simple bounds or linear constraints on variables.

DQED can solve, in the least squares sense, systems of linear or nonlinear equations, with inequality bounds or equality constraints.

DQED was written by Richard Hanson and Fred Krogh of Sandia National Laboratory.

The original FORTRAN77 source code is available through NETLIB at
http://www.netlib.org/opt/dqed.f.

Overview

DQED solves the constrained nonlinear least squares problem:

Minimize the sum of squares of MEQUA generally nonlinear equations,

f(1:MEQUA)(x) = 0, Equation (1)
where x is a set of NVARS unknowns. The vector function with these MEQUA components is called f(x) in the discussion that follows.

The components of x may have upper and lower bounds given by the user. In fact, all of the possible cases can be specified:

Linear constraints on the unknowns, more general than simple bounds, can also be given. These linear constraints can be of the equality or inequality type:

a(L,1) x(1)+ ... + a(L,NVARS) x(NVARS) = y(L), L = 1,...,MCON, Equation (2)
with bounds specified on the right hand side values y(L), again given by the user. The constraints can actually be slightly nonlinear. In this case the constraints can be described as:
g(L)(x) = y(L), L = 1,...,MCON, Equation (2')
where bounds are specified on each y(L). The functions g(L)(x) must be defined for all x in the set described by the simple bounds.

Experienced users may wish to turn directly to the examples before reading the subprogram documentation.

There is no size relation required for the problem dimensions MEQUA, NVARS, and MCON except that MEQUA and NVARS are both positive, and MCON is nonnegative.

DQED will do a decent job of solving most nonlinear least squares problems that can be expressed as Equations (1) and (2) above, provided that continuous derivatives of the functions with respect to the parameters can be computed. This can also include problems where the derivatives must be computed using some form of numerical differentiation. Numerical differentiation is not provided with this software for solving nonlinear least squares problems.

The authors also plan to develop methods that will do a much better job of coping with constraints more general than the essentially linear ones indicated above in Equations (2)-(2'). There are nonlinear least squares problems with innocent-looking but highly nonlinear constraints where this package will fail to work. The authors also hope to reduce the overhead required by the software. This high overhead is due primarily to the method used to solve the inner-loop quadratic model problem. The authors recommend that users consider using the option number 14, to suppress use of the quadratic model. The user may find that the software works quite well without the quadratic model. This may be important when the function and derivatives evaluations are not expensive but many individual problems are being solved.

There are two fundamental ways to use the subprogram DQED.

The most straightforward way is to make one call to DQED and obtain values for the unknowns, x. The user provides a subprogram DQEDEV that gives DQED the values of the functions f(x) and g(x), and the derivative or Jacobian matrices for f(x) and g(x) at each desired point x. This usage is called 'forward communication.'

An alternate way to use DQED is to provide an option that allows the user to communicate these values by 'reverse communication.' DQED returns to the user calling program and requests values for f(x) and g(x), and the Jacobian matrices for f(x) and g(x) for a given value of x. This framework is often required in applications that have complicated algorithmic requirements for evaluation of the functions.

Examples using both 'forward' and 'reverse' communication are provided.

Languages:

DQED is available in a FORTRAN77 version and a FORTRAN90 version.

Related Data and Programs:

BVLS, a FORTRAN90 library which applies least squares methods to solve a linear system for which lower and upper constraints may have been placed on every variable.

LAWSON, a FORTRAN77 library which contains routines for solving least squares problems and singular value decompositions, by Lawson and Hanson.

MINPACK, a FORTRAN90 library which solves systems of nonlinear equations, or the least squares minimization of the residual of a set of linear or nonlinear equations.

NL2SOL, a FORTRAN90 library which implements an adaptive nonlinear least-squares algorithm.

PRAXIS, a FORTRAN90 routine which minimizes a scalar function of several variables.

QR_SOLVE, a FORTRAN90 library which computes the least squares solution of a linear system A*x=b.

TEST_LS, a FORTRAN90 library which implements linear least squares test problems of the form A*x=b.

TEST_OPT, a FORTRAN90 library which defines test problems requiring the minimization of a scalar function of several variables.

TEST_OPT_CON, a FORTRAN90 library which defines test problems for the minimization of a scalar function of several variables, with the search constrained to lie within a specified hyper-rectangle.

TEST_OPTIMIZATION, a FORTRAN90 library which defines test problems for the minimization of a scalar function of several variables, as described by Molga and Smutnicki.

TOMS611, a FORTRAN90 library which can be used to seek the minimizer of a scalar functional of multiple variables.

XERROR, a FORTRAN90 library which handles error messages.

Author:

Richard Hanson and Fred Krogh.

Reference:

  1. Jack Dongarra, Jim Bunch, Cleve Moler, Pete Stewart,
    LINPACK User's Guide,
    SIAM, 1979,
    ISBN13: 978-0-898711-72-1,
    LC: QA214.L56.
  2. Richard Hanson,
    Least Squares with Bounds and Linear Constraints,
    SIAM Journal of Scientific and Statistical Computing,
    Volume 7, number 3, July 1986, pages 826-834.
  3. Ron Jones, David Kahaner,
    XERROR, The SLATEC Error Handling Package,
    Technical Report SAND82-0800,
    Sandia National Laboratories, 1982.
  4. Ron Jones, David Kahaner,
    XERROR, The SLATEC Error Handling Package,
    Software: Practice and Experience,
    Volume 13, Number 3, 1983, pages 251-257.
  5. Charles Lawson, Richard Hanson, David Kincaid, Fred Krogh,
    Algorithm 539: Basic Linear Algebra Subprograms for Fortran Usage,
    ACM Transactions on Mathematical Software,
    Volume 5, Number 3, September 1979, pages 308-323.
  6. Robert Schnabel, Paul Frank,
    Tensor Methods for Nonlinear Equations,
    SIAM Journal on Numerical Analysis,
    Volume 21, Number 5, October 1984, pages 815-843.
  7. dqed.txt, some online documentation.

Source Code:

Examples and Tests:

Problem 1 tries to fit data for a model of the heart. Several datasets are examined, exact and approximate jacobians are compared, and two equations are tried as constraints instead of equations. Files you may copy include:

Problem 2 tries to fit data. Files you may copy include:

Problem 3 tries to fit data. Files you may copy include:

Problem 4 is like problem 3, but is set up to solve a problem involving the absorption of carbon and nitrogen isotopes by an alligator from its prey.

Problem 5 shows how, if the nonlinear constrained system to be solved is actually a LINEAR constrained system, the user may call the DBOLS routine directly.

List of Routines:

You can go up one level to the FORTRAN90 source codes.


Last revised on 02 January 2011.