# DQED Bounded Constrained Least Squares/Nonlinear Equations Double precision version

DQED is a FORTRAN77 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:

• no bounds on X;
• bounds at one end only;
• upper and lower bounds.

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:

COMPASS_SEARCH, a FORTRAN77 library which seeks the minimizer of a scalar function of several variables using compass search, a direct search algorithm that does not use derivatives.

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

MINPACK, a FORTRAN77 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 FORTRAN77 library which implements an adaptive nonlinear least-squares algorithm.

PRAXIS, a FORTRAN77 library which minimizes a scalar function of several variables.

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

TEST_LS, a FORTRAN77 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.

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

XERROR, a FORTRAN77 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:

• dqed.f, the source code.
• dqed.sh, commands to compile the 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 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:

• DIFCEN estimates a jacobian using central differences.
• DIFFOR estimates a jacobian using forward differences.
• IDAMAX finds the index of the vector element of maximum absolute value.
• IVOUT prints integer vectors.
• DAMAX returns the maximum absolute value of the entries in a vector.
• DASUM sums the absolute values of the entries of a vector.
• DAXPY adds a constant times one vector to another.
• DBOCLS solves a bounded and constrained least squares problem.
• DBOLS solves the linear system E*X = F in the least squares sense.
• DBOLSM solves E*X = F in the least squares sense with bounds on some X values.
• DCOPY copies one vector into another.
• DDOT forms the dot product of two vectors.
• DGECO factors a double precision matrix and estimates its condition.
• DGEFA factors a double precision matrix.
• DGESL solves a system factored by DGECO or DGEFA.
• DMOUT prints double precision matrices.
• DNRM2 computes the Euclidean norm of a vector.
• DPCHEK checks the user's jacobian routine.
• DQED solves bounded and constrained least squares and nonlinear equations.
• DQEDEV evaluates functions being treated by DQED.
• DQEDGN is a simplified version of the QED algorithm for the model problem.
• DQEDIP carries out the work of DQEDGN.
• DQEDMN is the main solution routine.
• DROT applies a plane rotation.
• DROTG constructs a Givens plane rotation.
• DSCAL scales a vector by a constant.
• DSWAP interchanges two vectors.
• DVOUT prints double precision vectors.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• XERRWV is an error output message routine.

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

Last revised on 03 September 2007.