PDF version (NAG web site
, 64bit version, 64bit version)
NAG Toolbox Chapter Introduction
E04 — Minimizing or Maximizing a Function
Scope of the Chapter
An optimization problem involves minimizing a function (called the
objective function) of several variables, possibly subject to
restrictions on the values of the variables defined by a set of
constraint functions. Most functions in the Library are
concerned with function minimization only, since the problem of
maximizing a given objective function F(x) is equivalent to
minimizing
− F(x)$F\left(x\right)$.
Some functions allow you to specify whether you are solving a minimization or
maximization problem, carrying out the required transformation of the objective
function in the latter case.
In general functions in this chapter find a local minimum of a function f$f$, that is a point x^{*}${x}^{*}$ s.t. for all x$x$ near x^{*} f(x) ≥ f(x^{*})${x}^{*}\text{}f\left(x\right)\ge f\left({x}^{*}\right)$.
The
Chapter E05 contains functions to find the global minimum of a function
f$f$. At a global minimum
x^{*} f(x) ≥ f(x^{*})${x}^{*}\text{}f\left(x\right)\ge f\left({x}^{*}\right)$ for all
x$x$.
The
Chapter H contains functions typically regarded as belonging to the field of operations research.
This introduction is only a brief guide to the subject of optimization designed for the casual user. Anyone with a difficult or protracted problem to solve will find it beneficial to consult a more detailed text, such as
Gill et al. (1981) or
Fletcher (1987).
Background to the Problems
Types of Optimization Problems
The solution of optimization problems by a single, allpurpose, method is cumbersome and inefficient. Optimization problems are therefore classified into particular categories, where each category is defined by the properties of the objective and constraint functions, as illustrated by some examples below.
Properties of Objective Function 
Properties of Constraints 
Nonlinear 
Nonlinear 
Sums of squares of nonlinear functions 
Sparse linear 
Quadratic 
Linear 
Sums of squares of linear functions 
Bounds 
Linear 
None 
For instance, a specific problem category involves the minimization of a nonlinear objective function subject to bounds on the variables. In the following sections we define the particular categories of problems that can be solved by functions contained in this chapter. Not every category is given special treatment in the current version of the Library; however, the longterm objective is to provide a comprehensive set of functions to solve problems in all such categories.
Unconstrained minimization
In unconstrained minimization problems there are no constraints on the variables. The problem can be stated mathematically as follows:
where
x ∈ R^{n}$x\in {R}^{n}$, that is,
x
=
(x_{1},x_{2}, … ,x_{n})^{T}
$x={({x}_{1},{x}_{2},\dots ,{x}_{n})}^{\mathrm{T}}$.
Nonlinear least squares problems
Special consideration is given to the problem for which the function to be minimized can be expressed as a sum of squared functions. The least squares problem can be stated mathematically as follows:
where the
i$i$th element of the
m$m$vector
f$f$ is the function
f_{i}(x)${f}_{i}\left(x\right)$.
Minimization subject to bounds on the variables
These problems differ from the unconstrained problem in that at least one of the variables is subject to a simple bound (or restriction) on its value, e.g., x_{5} ≤ 10${x}_{5}\le 10$, but no constraints of a more general form are present.
The problem can be stated mathematically as follows:
subject to
l_{i} ≤ x_{i} ≤ u_{i}${l}_{\mathit{i}}\le {x}_{\mathit{i}}\le {u}_{\mathit{i}}$, for
i = 1,2, … ,n$\mathit{i}=1,2,\dots ,n$.
This format assumes that upper and lower bounds exist on all the variables. By conceptually allowing u_{i} = + ∞${u}_{i}=+\infty $ and l_{i} = − ∞${l}_{i}=\infty $ all the variables need not be restricted.
Minimization subject to linear constraints
A general linear constraint is defined as a constraint function that is linear in more than one of the variables, e.g.,
3x_{1} + 2x_{2} ≥ 4$3{x}_{1}+2{x}_{2}\ge 4$. The various types of linear constraint are reflected in the following mathematical statement of the problem:
subject to the
equality constraints: 
a_{i}^{T}
x = b_{i}
${a}_{i}^{\mathrm{T}}x={b}_{i}$ 
i = 1,2, … ,m_{1}$i=1,2,\dots ,{m}_{1}$; 
inequality constraints: 
a_{i}^{T}
x ≥ b_{i}
${a}_{i}^{\mathrm{T}}x\ge {b}_{i}$ 
i = m_{1} + 1,m_{1} + 2, … ,m_{2}$i={m}_{1}+1,{m}_{1}+2,\dots ,{m}_{2}$; 

a_{i}^{T}
x ≤ b_{i}
${a}_{i}^{\mathrm{T}}x\le {b}_{i}$ 
i = m_{2} + 1,m_{2} + 2, … ,m_{3}$i={m}_{2}+1,{m}_{2}+2,\dots ,{m}_{3}$; 
range constraints: 
s_{j}
≤
a_{i}^{T}
x ≤ t_{j}
${s}_{j}\le {a}_{i}^{\mathrm{T}}x\le {t}_{j}$ 
i = m_{3} + 1,m_{3} + 2, … ,m_{4};$i={m}_{3}+1,{m}_{3}+2,\dots ,{m}_{4}\text{;}$ 


j = 1,2, … ,m_{4} − m_{3};$j=1,2,\dots ,{m}_{4}{m}_{3}\text{;}$ 
bounds constraints: 
l_{i} ≤ x_{i} ≤ u_{i}${l}_{i}\le {x}_{i}\le {u}_{i}$ 
i = 1,2, … ,n$i=1,2,\dots ,n$ 
where each
a_{i}${a}_{i}$ is a vector of length
n$n$;
b_{i}${b}_{i}$,
s_{j}${s}_{j}$ and
t_{j}${t}_{j}$ are constant scalars; and any of the categories may be empty.
Although the bounds on x_{i}${x}_{i}$ could be included in the definition of general linear constraints, we prefer to distinguish between them for reasons of computational efficiency.
If
F(x)$F\left(x\right)$ is a linear function, the linearlyconstrained problem is termed a linear programming problem (LP); if
F(x)$F\left(x\right)$ is a quadratic function, the problem is termed a quadratic programming problem (QP). For further discussion of LP and QP problems, including the dual formulation of such problems, see
Dantzig (1963).
Minimization subject to nonlinear constraints
A problem is included in this category if at least one constraint function is nonlinear, e.g.,
x_{1}^{2} + x_{3} + x_{4} − 2 ≥ 0${x}_{1}^{2}+{x}_{3}+{x}_{4}2\ge 0$. The mathematical statement of the problem is identical to that for the linearlyconstrained case, except for the addition of the following constraints:
equality constraints: 
c_{i}(x) = 0${c}_{i}\left(x\right)=0$ 
i = 1,2, … ,m_{5}$i=1,2,\dots ,{m}_{5}$; 
inequality constraints: 
c_{i}(x) ≥ 0${c}_{i}\left(x\right)\ge 0$ 
i = m_{5} + 1,m_{5} + 2, … ,m_{6}$i={m}_{5}+1,{m}_{5}+2,\dots ,{m}_{6}$; 
range constraints: 
v_{j} ≤ c_{i}(x) ≤ w_{j}${v}_{j}\le {c}_{i}\left(x\right)\le {w}_{j}$ 
i = m_{6} + 1,m_{6} + 2, … ,m_{7}$i={m}_{6}+1,{m}_{6}+2,\dots ,{m}_{7}$, 


j = 1,2, … ,m_{7} − m_{6}$j=1,2,\dots ,{m}_{7}{m}_{6}$ 
where each
c_{i}${c}_{i}$ is a nonlinear function;
v_{j}${v}_{j}$ and
w_{j}${w}_{j}$ are constant scalars; and any category may be empty. Note that we do not include a separate category for constraints of the form
c_{i}(x) ≤ 0${c}_{i}\left(x\right)\le 0$, since this is equivalent to
− c_{i}(x) ≥ 0$\text{}{c}_{i}\left(x\right)\ge 0$.
Although the general linear constraints could be included in the definition of nonlinear constraints, again we prefer to distinguish between them for reasons of computational efficiency.
If
F(x)$F\left(x\right)$ is a nonlinear function, the nonlinearlyconstrained problem is termed a nonlinear programming problem (NLP). For further discussion of NLP problems, see
Gill et al. (1981) or
Fletcher (1987).
Minimization subject to bounds on the objective function
In all of the above problem categories it is assumed that
where
a = − ∞$a=\infty $ and
b = + ∞$b=+\infty $. Problems in which
a$a$ and/or
b$b$ are finite can be solved by adding an extra constraint of the appropriate type (i.e., linear or nonlinear) depending on the form of
F(x)$F\left(x\right)$. Further advice is given in
Section [Function Evaluations at Infeasible Points].
Multiobjective optimization
Sometimes a problem may have two or more objective functions which are to be optimized at the same time. Such problems are called multiobject, multicriteria or multiattribute optimization. If the constraints are linear and the objectives are all linear then the terminology ‘goal programming’ is also used.
Techniques used in this chapter and in
Chapter E05 may be employed to address such problems.
Geometric Representation and Terminology
To illustrate the nature of optimization problems it is useful to consider the following example in two dimensions:
(This function is used as the example function in the documentation for the unconstrained functions.)
Figure 1
Figure 1 is a contour diagram of
F(x)$F\left(x\right)$. The contours labelled
F_{0},F_{1}, … ,F_{4}${F}_{0},{F}_{1},\dots ,{F}_{4}$ are isovalue contours, or lines along which the function
F(x)$F\left(x\right)$ takes specific constant values. The point
x^{*} = ((1/2), − 1)^{T}${x}^{*}={(\frac{1}{2},1)}^{\mathrm{T}}$ is a
local unconstrained minimum, that is, the value of
F(x^{*})$F\left({x}^{*}\right)$ (
= 0$\text{}=0$) is less than at all the neighbouring points. A function may have several such minima. The lowest of the local minima is termed a
global minimum. In the problem illustrated in
Figure 1,
x^{*}${x}^{*}$ is the only local minimum. The point
x_{s}${x}_{s}$ is said to be a
saddle point because it is a minimum along the line AB, but a maximum along CD.
If we add the constraint
x_{1} ≥ 0${x}_{1}\ge 0$ (a simple bound) to the problem of minimizing
F(x)$F\left(x\right)$, the solution remains unaltered. In
Figure 1 this constraint is represented by the straight line passing through
x_{1} = 0${x}_{1}=0$, and the shading on the line indicates the unacceptable region (i.e.,
x_{1} < 0${x}_{1}<0$). The region in
R^{n}${R}^{n}$ satisfying the constraints of an optimization problem is termed the
feasible region. A point satisfying the constraints is defined as a
feasible point.
If we add the nonlinear constraint
c_{1}(x) : x_{1} + x_{2} − x_{1}x_{2} − (3/2) ≥ 0${c}_{1}\left(x\right):{x}_{1}+{x}_{2}{x}_{1}{x}_{2}\frac{3}{2}\ge 0$, represented by the curved shaded line in
Figure 1, then
x^{*}${x}^{*}$ is not a feasible point because
c_{1}(x^{*}) < 0${c}_{1}\left({x}^{*}\right)<0$. The solution of the new constrained problem is
x_{b} ≃ (1.1825, − 1.7397)^{T}${x}_{b}\simeq {(1.1825,1.7397)}^{\mathrm{T}}$, the feasible point with the smallest function value (where
F(x_{b}) ≃ 3.0607$F\left({x}_{b}\right)\simeq 3.0607$).
Gradient vector
The vector of first partial derivatives of
F(x)$F\left(x\right)$ is called the
gradient vector, and is denoted by
g(x)$g\left(x\right)$, i.e.,
For the function illustrated in
Figure 1,
The gradient vector is of importance in optimization because it must be zero at an unconstrained minimum of any function with continuous first derivatives.
Hessian matrix
The matrix of second partial derivatives of a function is termed its Hessian matrix. The Hessian matrix of F(x)$F\left(x\right)$ is denoted by G(x)$G\left(x\right)$, and its (i,j)$(i,j)$th element is given by ∂^{2}F(x) / ∂ x_{i} ∂ x_{j}${\partial}^{2}F\left(x\right)/\partial {x}_{i}\partial {x}_{j}$. If F(x)$F\left(x\right)$ has continuous second derivatives, then G(x)$G\left(x\right)$ must be positive definite at any unconstrained minimum of F$F$.
Jacobian matrix; matrix of constraint normals
In nonlinear least squares problems, the matrix of first partial derivatives of the vectorvalued function f(x)$f\left(x\right)$ is termed the Jacobian matrix of f(x)$f\left(x\right)$ and its (i,j)$(i,j)$th component is ∂ f_{i} / ∂ x_{j}$\partial {f}_{i}/\partial {x}_{j}$.
The vector of first partial derivatives of the constraint
c_{i}(x)${c}_{i}\left(x\right)$ is denoted by
The matrix whose columns are the vectors
{a_{i}}$\left\{{a}_{i}\right\}$ is termed the
matrix of constraint normals. At a point
x̂$\hat{x}$, the vector
a_{i}(x̂)${a}_{i}\left(\hat{x}\right)$ is orthogonal (normal) to the isovalue contour of
c_{i}(x)${c}_{i}\left(x\right)$ passing through
x̂$\hat{x}$; this relationship is illustrated for a twodimensional function in
Figure 2.
Figure 2
Note that if
c_{i}(x)${c}_{i}\left(x\right)$ is a linear constraint involving
a_{i}^{T}
x
${a}_{i}^{\mathrm{T}}x$, then its vector of first partial derivatives is simply the vector
a_{i}${a}_{i}$.
Sufficient Conditions for a Solution
All nonlinear functions will be assumed to have continuous second derivatives in the neighbourhood of the solution.
Unconstrained minimization
The following conditions are sufficient for the point
x^{*}${x}^{*}$ to be an unconstrained local minimum of
F(x)$F\left(x\right)$:
(i) 
‖g(x^{*})‖ = 0$\Vert g\left({x}^{*}\right)\Vert =0$; and 
(ii) 
G(x^{*})$G\left({x}^{*}\right)$ is positive definite, 
where
‖g‖$\Vert g\Vert $ denotes the Euclidean length of
g$g$Minimization subject to bounds on the variables
At the solution of a boundsconstrained problem, variables which are not on their bounds are termed free variables. If it is known in advance which variables are on their bounds at the solution, the problem can be solved as an unconstrained problem in just the free variables; thus, the sufficient conditions for a solution are similar to those for the unconstrained case, applied only to the free variables.
Sufficient conditions for a feasible point
x^{*}${x}^{*}$ to be the solution of a boundsconstrained problem are as follows:
(i) 
‖g(x^{*})‖ = 0$\Vert \stackrel{}{g}\left({x}^{*}\right)\Vert =0$; and 
(ii) 
G(x^{*})$\stackrel{}{G}\left({x}^{*}\right)$ is positive definite; and 
(iii) 
g_{j}(x^{*}) < 0,x_{j} = u_{j}${g}_{j}\left({x}^{*}\right)<0,{x}_{j}={u}_{j}$; g_{j}(x^{*}) > 0,x_{j} = l_{j}${g}_{j}\left({x}^{*}\right)>0,{x}_{j}={l}_{j}$, 
where
g(x)$\stackrel{}{g}\left(x\right)$ is the gradient of
F(x)$F\left(x\right)$ with respect to the free variables, and
G(x)$\stackrel{}{G}\left(x\right)$ is the Hessian matrix of
F(x)$F\left(x\right)$ with respect to the free variables. The extra condition (iii) ensures that
F(x)$F\left(x\right)$ cannot be reduced by moving off one or more of the bounds.
Linearlyconstrained minimization
For the sake of simplicity, the following description does not include a specific treatment of bounds or range constraints, since the results for general linear inequality constraints can be applied directly to these cases.
At a solution
x^{*}${x}^{*}$, of a linearlyconstrained problem, the constraints which hold as equalities are called the
active or
binding constraints. Assume that there are
t$t$ active constraints at the solution
x^{*}${x}^{*}$, and let
Â$\hat{A}$ denote the matrix whose columns are the columns of
A$A$ corresponding to the active constraints, with
b̂$\hat{b}$ the vector similarly obtained from
b$b$; then
The matrix
Z$Z$ is defined as an
n × (n − t)$n\times (nt)$ matrix satisfying:
The columns of
Z$Z$ form an orthogonal basis for the set of vectors orthogonal to the columns of
Â$\hat{A}$.
Define
 g_{Z}(x) = Z^{T}g(x)${g}_{Z}\left(x\right)={Z}^{\mathrm{T}}g\left(x\right)$, the projected gradient vector of F(x)$F\left(x\right)$;
 G_{Z}(x) = Z^{T}G(x)Z${G}_{Z}\left(x\right)={Z}^{\mathrm{T}}G\left(x\right)Z$, the projected Hessian matrix of F(x)$F\left(x\right)$.
At the solution of a linearlyconstrained problem, the projected gradient vector must be zero, which implies that the gradient vector
g(x^{*})$g\left({x}^{*}\right)$ can be written as a linear combination of the columns of
Â$\hat{A}$, i.e.,
g(x^{*}) = ∑ _{i = 1}^{t}λ_{i}^{ * }â_{i} = Âλ^{*}$g\left({x}^{*}\right)={\displaystyle \sum _{i=1}^{t}}{\lambda}_{i}^{*}{\hat{a}}_{i}=\hat{A}{\lambda}^{*}$. The scalar
λ_{i}^{ * }${\lambda}_{i}^{*}$ is defined as the
Lagrange multiplier corresponding to the
i$i$th active constraint. A simple interpretation of the
i$i$th Lagrange multiplier is that it gives the gradient of
F(x)$F\left(x\right)$ along the
i$i$th active constraint normal; a convenient definition of the Lagrange multiplier vector (although not a recommended method for computation) is:
Sufficient conditions for
x^{*}${x}^{*}$ to be the solution of a linearlyconstrained problem are:
(i) 
x^{*}${x}^{*}$ is feasible, and Â^{T}x^{*} = b̂${\hat{A}}^{\mathrm{T}}{x}^{*}=\hat{b}$; and 
(ii) 
‖g_{Z}(x^{*})‖ = 0$\Vert {g}_{Z}\left({x}^{*}\right)\Vert =0$, or equivalently, g(x^{*}) = Âλ^{*}$g\left({x}^{*}\right)=\hat{A}{\lambda}^{*}$; and 
(iii) 
G_{Z}(x^{*})${G}_{Z}\left({x}^{*}\right)$ is positive definite; and 
(iv) 
λ_{i}^{ * } > 0${\lambda}_{i}^{*}>0$ if λ_{i}^{ * }${\lambda}_{i}^{*}$ corresponds to a constraint
â_{i}^{T}
x^{*}
≥
b̂_{i}
${\hat{a}}_{i}^{\mathrm{T}}{x}^{*}\ge {\hat{b}}_{i}$;
λ_{i}^{ * } < 0${\lambda}_{i}^{*}<0$ if λ_{i}^{ * }${\lambda}_{i}^{*}$ corresponds to a constraint
â_{i}^{T}
x^{*}
≤
b̂_{i}
${\hat{a}}_{i}^{\mathrm{T}}{x}^{*}\le {\hat{b}}_{i}$.
The sign of λ_{i}^{ * }${\lambda}_{i}^{*}$ is immaterial for equality constraints, which by definition are always active. 
Nonlinearlyconstrained minimization
For nonlinearlyconstrained problems, much of the terminology is defined exactly as in the linearlyconstrained case. The set of active constraints at
x$x$ again means the set of constraints that hold as equalities at
x$x$, with corresponding definitions of
ĉ$\hat{c}$ and
Â$\hat{A}$: the vector
ĉ(x)$\hat{c}\left(x\right)$ contains the active constraint functions, and the columns of
Â(x)$\hat{A}\left(x\right)$ are the gradient vectors of the active constraints. As before,
Z$Z$ is defined in terms of
Â(x)$\hat{A}\left(x\right)$ as a matrix such that:
where the dependence on
x$x$ has been suppressed for compactness.
The projected gradient vector g_{Z}(x)${g}_{Z}\left(x\right)$ is the vector Z^{T}g(x)${Z}^{\mathrm{T}}g\left(x\right)$. At the solution x^{*}${x}^{*}$ of a nonlinearlyconstrained problem, the projected gradient must be zero, which implies the existence of Lagrange multipliers corresponding to the active constraints, i.e., g(x^{*}) = Â(x^{*})λ^{*}$g\left({x}^{*}\right)=\hat{A}\left({x}^{*}\right){\lambda}^{*}$.
The
Lagrangian function is given by:
We define
g_{L}(x)${g}_{L}\left(x\right)$ as the gradient of the Lagrangian function;
G_{L}(x)${G}_{L}\left(x\right)$ as its Hessian matrix, and
Ĝ_{L}(x)${\hat{G}}_{L}\left(x\right)$ as its projected Hessian matrix, i.e.,
Ĝ_{L} = Z^{T}G_{L}Z${\hat{G}}_{L}={Z}^{\mathrm{T}}{G}_{L}Z$.
Sufficient conditions for
x^{*}${x}^{*}$ to be the solution of a nonlinearlyconstrained problem are:
(i) 
x^{*}${x}^{*}$ is feasible, and ĉ(x^{*}) = 0$\hat{c}\left({x}^{*}\right)=0$; and 
(ii) 
‖g_{Z}(x^{*})‖ = 0$\Vert {g}_{Z}\left({x}^{*}\right)\Vert =0$, or, equivalently, g(x^{*}) = Â(x^{*})λ^{*}$g\left({x}^{*}\right)=\hat{A}\left({x}^{*}\right){\lambda}^{*}$; and 
(iii) 
Ĝ_{L}(x^{*})${\hat{G}}_{L}\left({x}^{*}\right)$ is positive definite; and 
(iv) 
λ_{i}^{ * } > 0${\lambda}_{i}^{*}>0$ if λ_{i}^{ * }${\lambda}_{i}^{*}$ corresponds to a constraint of the form ĉ_{i} ≥ 0${\hat{c}}_{i}\ge 0$.
The sign of λ_{i}^{ * }${\lambda}_{i}^{*}$ is immaterial for equality constraints, which by definition are always active. 
Note that condition (ii) implies that the projected gradient of the Lagrangian function must also be zero at x^{*}${x}^{*}$, since the application of Z^{T}${Z}^{\mathrm{T}}$ annihilates the matrix Â(x^{*})$\hat{A}\left({x}^{*}\right)$.
Background to Optimization Methods
All the algorithms contained in this chapter generate an iterative sequence
{x^{(k)}}$\left\{{x}^{\left(k\right)}\right\}$ that converges to the solution
x^{*}${x}^{*}$ in the limit, except for some special problem categories (i.e., linear and quadratic programming). To terminate computation of the sequence, a convergence test is performed to determine whether the current estimate of the solution is an adequate approximation. The convergence tests are discussed in
Section [Analysis of Computed Results].
Most of the methods construct a sequence
{x^{(k)}}$\left\{{x}^{\left(k\right)}\right\}$ satisfying:
where the vector
p^{(k)}${p}^{\left(k\right)}$ is termed the
direction of search, and
α^{(k)}${\alpha}^{\left(k\right)}$ is the
steplength. The steplength
α^{(k)}${\alpha}^{\left(k\right)}$ is chosen so that
F(x^{(k + 1)}) < F(x^{(k)})$F\left({x}^{(k+1)}\right)<F\left({x}^{\left(k\right)}\right)$ and is computed using one of the techniques for onedimensional optimization referred to in
Section [Onedimensional optimization].
Onedimensional optimization
The Library contains two special functions for minimizing a function of a single variable. Both functions are based on safeguarded polynomial approximation. One function requires function evaluations only and fits a quadratic polynomial whilst the other requires function and gradient evaluations and fits a cubic polynomial. See Section 4.1 of
Gill et al. (1981).
Methods for unconstrained optimization
The distinctions among methods arise primarily from the need to use varying levels of information about derivatives of
F(x)$F\left(x\right)$ in defining the search direction. We describe three basic approaches to unconstrained problems, which may be extended to other problem categories. Since a full description of the methods would fill several volumes, the discussion here can do little more than allude to the processes involved, and direct you to other sources for a full explanation.
(a) 
Newtontype Methods (Modified Newton Methods)
Newtontype methods use the Hessian matrix G(x^{(k)})$G\left({x}^{\left(k\right)}\right)$, or a finite difference approximation to G(x^{(k)})$G\left({x}^{\left(k\right)}\right)$, to define the search direction. The functions in the Library either require a function that computes the elements of G(x^{(k)})$G\left({x}^{\left(k\right)}\right)$ directly, or they approximate G(x^{(k)})$G\left({x}^{\left(k\right)}\right)$ by finite differences.
Newtontype methods are the most powerful methods available for general problems and will find the minimum of a quadratic function in one iteration. See Sections 4.4 and 4.5.1 of Gill et al. (1981). 
(b) 
QuasiNewton Methods
QuasiNewton methods approximate the Hessian G(x^{(k)})$G\left({x}^{\left(k\right)}\right)$ by a matrix B^{(k)}${B}^{\left(k\right)}$ which is modified at each iteration to include information obtained about the curvature of F$F$ along the current search direction p^{(k)}${p}^{\left(k\right)}$. Although not as robust as Newtontype methods, quasiNewton methods can be more efficient because G(x^{(k)})$G\left({x}^{\left(k\right)}\right)$ is not computed directly, or approximated by finite differences. QuasiNewton methods minimize a quadratic function in n$n$ iterations, where n$n$ is the number of variables. See Section 4.5.2 of Gill et al. (1981). 
(c) 
Conjugategradient Methods
Unlike Newtontype and quasiNewton methods, conjugategradient methods do not require the storage of an n$n$ by n$n$ matrix and so are ideally suited to solve large problems. Conjugategradient type methods are not usually as reliable or efficient as Newtontype, or quasiNewton methods. See Section 4.8.3 of Gill et al. (1981). 
Methods for nonlinear least squares problems
These methods are similar to those for unconstrained optimization, but exploit the special structure of the Hessian matrix to give improved computational efficiency.
Since
the Hessian matrix
G(x)$G\left(x\right)$ is of the form
where
J(x)$J\left(x\right)$ is the Jacobian matrix of
f(x)$f\left(x\right)$, and
G_{i}(x)${G}_{i}\left(x\right)$ is the Hessian matrix of
f_{i}(x)${f}_{i}\left(x\right)$.
In the neighbourhood of the solution,
‖f(x)‖$\Vert f\left(x\right)\Vert $ is often small compared to
‖J(x)^{T}J(x)‖
$\Vert J{\left(x\right)}^{\mathrm{T}}J\left(x\right)\Vert $ (for example, when
f(x)$f\left(x\right)$ represents the goodnessoffit of a nonlinear model to observed data). In such cases,
2
J(x)^{T}
J(x)
$2J{\left(x\right)}^{\mathrm{T}}J\left(x\right)$ may be an adequate approximation to
G(x)$G\left(x\right)$, thereby avoiding the need to compute or approximate second derivatives of
{f_{i}(x)}$\left\{{f}_{i}\left(x\right)\right\}$. See Section 4.7 of
Gill et al. (1981).
Methods for handling constraints
Bounds on the variables are dealt with by fixing some of the variables on their bounds and adjusting the remaining free variables to minimize the function. By examining estimates of the Lagrange multipliers it is possible to adjust the set of variables fixed on their bounds so that eventually the bounds active at the solution should be correctly identified. This type of method is called an active set method. One feature of such methods is that, given an initial feasible point, all approximations x^{(k)}${x}^{\left(k\right)}$ are feasible. This approach can be extended to general linear constraints. At a point, x$x$, the set of constraints which hold as equalities being used to predict, or approximate, the set of active constraints is called the working set.
Nonlinear constraints are more difficult to handle. If at all possible, it is usually beneficial to avoid including nonlinear constraints during the formulation of the problem. The methods currently implemented in the Library handle nonlinearly constrained problems by transforming them into a sequence of quadratic programming problems. A feature of such methods is that
x^{(k)}${x}^{\left(k\right)}$ is not guaranteed to be feasible except in the limit, and this is certainly true of the functions currently in the Library. See Chapter 6, particularly Sections 6.4 and 6.5, of
Gill et al. (1981).
Anyone interested in a detailed description of methods for optimization should consult the references.
Methods for handling multiobjective optimization
Suppose we have objective functions
f_{i}(x)${f}_{i}\left(x\right)$,
i > 1$i>1$, all of which we need to minimize at the same time. There are two main approaches to this problem:
(a) 
Combine the individual objectives into one composite objective. Typically this might be a weighted sum of the objectives, e.g.,
Here you choose the weights to express the relative importance of the corresponding objective. Ideally each of the f_{i}(x)${f}_{i}\left(x\right)$ should be of comparable size at a solution. 
(b) 
Order the objectives in order of importance. Suppose f_{i}${f}_{\mathit{i}}$ are ordered such that f_{i}(x)${f}_{\mathit{i}}\left(x\right)$ is more important than f_{i + 1}(x)${f}_{\mathit{i}+1}\left(x\right)$, for i = 1,2, … ,n − 1$\mathit{i}=1,2,\dots ,n1$. Then in the lexicographical approach to multiobjective optimization a sequence of subproblems are solved. Firstly solve the problem for objective function f_{1}(x)${f}_{1}\left(x\right)$ and denote by r_{1}${r}_{1}$ the value of this minimum. If (i − 1)$(\mathit{i}1)$ subproblems have been solved with results r_{i − 1}${r}_{\mathit{i}1}$ then subproblem i$\mathit{i}$ becomes min (f_{i}(x))$\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({f}_{\mathit{i}}\left(x\right)\right)$ subject to r_{k} ≤ f_{k}(x) ≤ r_{k}${r}_{k}\le {f}_{k}\left(x\right)\le {r}_{k}$, for k = 1,2, … ,i − 1$\mathit{k}=1,2,\dots ,i1$ plus the other constraints. 
Clearly the bounds on f_{k}${f}_{k}$ might be relaxed at your discretion.
In general, if NAG functions from the
Chapter E04 are used then only local minima are found. This means that a better solution to an individual objective might be found without worsening the optimal solutions to the other objectives. Ideally you seek a Pareto solution; one in which an improvement in one objective can only be achieved by a worsening of another objective.
To obtain a Pareto solution functions from
Chapter E05 might be used or, alternatively, a pragmatic attempt to derive a global minimum might be tried (see
nag_glopt_nlp_multistart_sqp (e05uc)). In this approach a variety of different minima are computed for each subproblem by starting from a range of different starting points. The best solution achieved is taken to be the global minimum. The more starting points chosen the greater confidence you might have in the computed global minimum.
Scaling
Scaling (in a broadly defined sense) often has a significant influence on the performance of optimization methods. Since convergence tolerances and other criteria are necessarily based on an implicit definition of ‘small’ and ‘large’, problems with unusual or unbalanced scaling may cause difficulties for some algorithms. Although there are currently no usercallable scaling functions in the Library, scaling is automatically performed by default in the functions which solve sparse LP, QP or NLP problems and in some newer dense solver functions. The following sections present some general comments on problem scaling.
Transformation of variables
One method of scaling is to transform the variables from their original representation, which may reflect the physical nature of the problem, to variables that have certain desirable properties in terms of optimization. It is generally helpful for the following conditions to be satisfied:
(i) 
the variables are all of similar magnitude in the region of interest; 
(ii) 
a fixed change in any of the variables results in similar changes in F(x)$F\left(x\right)$. Ideally, a unit change in any variable produces a unit change in F(x)$F\left(x\right)$; 
(iii) 
the variables are transformed so as to avoid cancellation error in the evaluation of F(x)$F\left(x\right)$. 
Normally, you should restrict yourself to linear transformations of variables, although occasionally nonlinear transformations are possible. The most common such transformation (and often the most appropriate) is of the form
where
D$D$ is a diagonal matrix with constant coefficients. Our experience suggests that more use should be made of the transformation
where
v$v$ is a constant vector.
Consider, for example, a problem in which the variable
x_{3}${x}_{3}$ represents the position of the peak of a Gaussian curve to be fitted to data for which the extreme values are
150$150$ and
170$170$; therefore
x_{3}${x}_{3}$ is known to lie in the range
150$150$–
170$170$. One possible scaling would be to define a new variable
x_{3}${\stackrel{}{x}}_{3}$, given by
A better transformation, however, is given by defining
x_{3}${\stackrel{}{x}}_{3}$ as
Frequently, an improvement in the accuracy of evaluation of
F(x)$F\left(x\right)$ can result if the variables are scaled before the functions to evaluate
F(x)$F\left(x\right)$ are coded. For instance, in the above problem just mentioned of Gaussian curvefitting,
x_{3}${x}_{3}$ may always occur in terms of the form
(x_{3} − x_{m})$({x}_{3}{x}_{m})$, where
x_{m}${x}_{m}$ is a constant representing the mean peak position.
Scaling the objective function
The objective function has already been mentioned in the discussion of scaling the variables. The solution of a given problem is unaltered if F(x)$F\left(x\right)$ is multiplied by a positive constant, or if a constant value is added to F(x)$F\left(x\right)$. It is generally preferable for the objective function to be of the order of unity in the region of interest; thus, if in the original formulation F(x)$F\left(x\right)$ is always of the order of 10^{ + 5}${10}^{+5}$ (say), then the value of F(x)$F\left(x\right)$ should be multiplied by 10^{ − 5}${10}^{5}$ when evaluating the function within an optimization function. If a constant is added or subtracted in the computation of F(x)$F\left(x\right)$, usually it should be omitted, i.e., it is better to formulate F(x)$F\left(x\right)$ as x_{1}^{2} + x_{2}^{2}${x}_{1}^{2}+{x}_{2}^{2}$ rather than as x_{1}^{2} + x_{2}^{2} + 1000${x}_{1}^{2}+{x}_{2}^{2}+1000$ or even x_{1}^{2} + x_{2}^{2} + 1${x}_{1}^{2}+{x}_{2}^{2}+1$. The inclusion of such a constant in the calculation of F(x)$F\left(x\right)$ can result in a loss of significant figures.
Scaling the constraints
A ‘well scaled’ set of constraints has two main properties. Firstly, each constraint should be wellconditioned with respect to perturbations of the variables. Secondly, the constraints should be balanced with respect to each other, i.e., all the constraints should have ‘equal weight’ in the solution process.
The solution of a linearly or nonlinearlyconstrained problem is unaltered if the
i$i$th constraint is multiplied by a positive weight
w_{i}${w}_{i}$. At the approximation of the solution determined by a Library function, any active linear constraints will (in general) be satisfied ‘exactly’ (i.e., to within the tolerance defined by
machine precision) if they have been properly scaled. This is in contrast to any active nonlinear constraints, which will not (in general) be satisfied ‘exactly’ but will have ‘small’ values (for example,
ĉ_{1}(x^{*}) = 10^{ − 8}${\hat{c}}_{1}\left({x}^{*}\right)={10}^{8}$,
ĉ_{2}(x^{*}) = − 10^{ − 6}${\hat{c}}_{2}\left({x}^{*}\right)={10}^{6}$, and so on). In general, this discrepancy will be minimized if the constraints are weighted so that a unit change in
x$x$ produces a similar change in each constraint.
A second reason for introducing weights is related to the effect of the size of the constraints on the Lagrange multiplier estimates and, consequently, on the active set strategy. This means that different sets of weights may cause an algorithm to produce different sequences of iterates. Additional discussion is given in
Gill et al. (1981).
Analysis of Computed Results
Convergence criteria
The convergence criteria inevitably vary from function to function, since in some cases more information is available to be checked (for example, is the Hessian matrix positive definite?), and different checks need to be made for different problem categories (for example, in constrained minimization it is necessary to verify whether a trial solution is feasible). Nonetheless, the underlying principles of the various criteria are the same; in nonmathematical terms, they are:
(i) 
is the sequence {x^{(k)}}$\left\{{x}^{\left(k\right)}\right\}$ converging? 
(ii) 
is the sequence {F^{(k)}}$\left\{{F}^{\left(k\right)}\right\}$ converging? 
(iii) 
are the necessary and sufficient conditions for the solution satisfied? 
The decision as to whether a sequence is converging is necessarily speculative. The criterion used in the present functions is to assume convergence if the relative change occurring between two successive iterations is less than some prescribed quantity. Criterion (iii) is the most reliable but often the conditions cannot be checked fully because not all the required information may be available.
Checking results
Little a priori guidance can be given as to the quality of the solution found by a nonlinear optimization algorithm, since no guarantees can be given that the methods will not fail. Therefore, you should always check the computed solution even if the function reports success. Frequently a ‘solution’ may have been found even when the function does not report a success. The reason for this apparent contradiction is that the function needs to assess the accuracy of the solution. This assessment is not an exact process and consequently may be unduly pessimistic. Any ‘solution’ is in general only an approximation to the exact solution, and it is possible that the accuracy you have specified is too stringent.
Further confirmation can be sought by trying to check whether or not convergence tests are almost satisfied, or whether or not some of the sufficient conditions are nearly satisfied. When it is thought that a function has returned a
nonzero value of ifail
only because the requirements for ‘success’ were too stringent it may be worth restarting with increased convergence tolerances.
For nonlinearlyconstrained problems, check whether the solution returned is feasible, or nearly feasible; if not, the solution returned is not an adequate solution.
Confidence in a solution may be increased by resolving the problem with a different initial approximation to the solution. See Section 8.3 of
Gill et al. (1981) for further information.
Monitoring progress
Many of the functions in the chapter have facilities to allow you to monitor the progress of the minimization process, and you are encouraged to make use of these facilities. Monitoring information can be a great aid in assessing whether or not a satisfactory solution has been obtained, and in indicating difficulties in the minimization problem or in the ability of the function to cope with the problem.
The behaviour of the function, the estimated solution and first derivatives can help in deciding whether a solution is acceptable and what to do in the event of a return with a
nonzero value of ifail.
Confidence intervals for least squares solutions
When estimates of the parameters in a nonlinear least squares problem have been found, it may be necessary to estimate the variances of the parameters and the fitted function. These can be calculated from the Hessian of F(x)$F\left(x\right)$ at the solution.
In many least squares problems, the Hessian is adequately approximated at the solution by
G = 2J^{T}J$G=2{J}^{\mathrm{T}}J$ (see
Section [Methods for nonlinear least squares problems]). The Jacobian,
J$J$, or a factorization of
J$J$ is returned by all the comprehensive least squares functions and, in addition, a function is available in the Library to estimate variances of the parameters following the use of most of the nonlinear least squares functions, in the case that
G = 2J^{T}J$G=2{J}^{\mathrm{T}}J$ is an adequate approximation.
Let
H$H$ be the inverse of
G$G$, and
S$S$ be the sum of squares, both calculated at the solution
x$\stackrel{}{x}$; an unbiased estimate of the
variance of the
i$i$th parameter
x_{i}${x}_{i}$ is
and an unbiased estimate of the covariance of
x_{i}${\stackrel{}{x}}_{i}$ and
x_{j}${\stackrel{}{x}}_{j}$ is
If
x^{*}${x}^{*}$ is the true solution, then the
100(1 − β)%$100(1\beta )\%\text{}$ confidence interval on
x$\stackrel{}{x}$ is
where
t_{(1 − β / 2,m − n)}${t}_{(1\beta /2,mn)}$ is the
100(1 − β) / 2$100(1\beta )/2$ percentage point of the
t$t$distribution with
m − n$mn$ degrees of freedom.
In the majority of problems, the residuals
f_{i}${f}_{\mathit{i}}$, for
i = 1,2, … ,m$\mathit{i}=1,2,\dots ,m$, contain the difference between the values of a model function
φ(z,x)$\varphi (z,x)$ calculated for
m$m$ different values of the independent variable
z$z$, and the corresponding observed values at these points. The minimization process determines the parameters, or constants
x$x$, of the fitted function
φ(z,x)$\varphi (z,x)$. For any value,
z$\stackrel{}{z}$, of the independent variable
z$z$, an unbiased estimate of the
variance of
φ$\varphi $ is
The
100(1 − β)%$100(1\beta )\%$ confidence interval on
F$F$ at the point
z$\stackrel{}{z}$ is
For further details on the analysis of least squares solutions see
Bard (1974) and
Wolberg (1967).
Recommendations on Choice and Use of Available Functions
The choice of function depends on several factors: the type of problem (unconstrained, etc.); the level of derivative information available (function values only, etc.); your experience (there are easytouse versions of some functions); whether or not storage is a problem; whether or not the function is to be used in a multithreaded environment; and whether computational time has a high priority. Not all choices are catered for in the current version of the Library.
Easytouse and Comprehensive Functions
Many functions appear in the Library in two forms: a comprehensive form and an easytouse form. The objective in the easytouse forms is to make the function simple to use by including in the calling sequence only those parameters absolutely essential to the definition of the problem, as opposed to parameters relevant to the solution method. If you are an experienced user the comprehensive functions have additional parameters which enable you to improve their efficiency by ‘tuning’ the method to a particular problem. If you are a casual or inexperienced user, this feature is of little value and may in some cases cause a failure because of a poor choice of some parameters.
In the easytouse functions, these extra parameters are determined either by fixing them at a known safe and reasonably efficient value, or by an auxiliary function which generates a ‘good’ value automatically.
For functions introduced since Mark 12 of the Library a different approach has been adopted towards the choice of easytouse and comprehensive functions. The optimization function has an easytouse parameter list, but additional parameters may be changed from their default values by calling an ‘option’ setting function before the call to the main optimization function. This approach has the advantages of allowing the options to be given in the form of keywords and requiring only those options that are to be different from their default values to be set.
Reverse Communication Functions
Most of the functions in this chapter are called just once in order to compute the minimum of a given objective function subject to a set of constraints on the variables. The objective function and nonlinear constraints (if any) are specified by you and written as functions to a very rigid format described in the relevant function document.
For the majority of applications this is the simplest and most convenient usage. Sometimes however this approach can be restrictive:
(i) 
when the required format of the function does not allow useful information to be passed conveniently to and from your calling program; 
(ii) 
when the minimization function is being called from another computer language, such as Visual Basic, which does not fully support procedure arguments in a way that is compatible with the Library. 
A way around these problems is to utilize reverse communication functions. Instead of performing complete optimizations, these functions perform one step in the solution process before returning to the calling program with an appropriate flag (irevcm) set. The value of irevcm determines whether the minimization process has finished or whether fresh information is required. In the latter case you calculate this information (in the form of a vector or as a scalar, as appropriate) and reenter the reverse communication function with the information contained in appropriate arguments. Thus you have the responsibility for providing the iterative loop in the minimization process, but as compensation, you have an extremely flexible and basic userinterface to the reverse communication function.
The only reverse communication functions in this chapter are
nag_opt_nlp1_rcomm (e04uf), which solve dense NLP problems using a sequential quadratic programming method.
Service Functions
One of the most common errors in the use of optimization functions is that usersupplied functions do not evaluate the relevant partial derivatives correctly. Because exact gradient information normally enhances efficiency in all areas of optimization, you are encouraged to provide analytical derivatives whenever possible. However, mistakes in the computation of derivatives can result in serious and obscure runtime errors. Consequently, service functions are provided to perform an elementary check on the gradients you supplied. These functions are inexpensive to use in terms of the number of calls they require to usersupplied functions.
The appropriate checking functions are as follows:
It should be noted that functions
nag_opt_nlp1_rcomm (e04uf),
nag_opt_lsq_gencon_deriv (e04us),
nag_opt_nlp2_sparse_solve (e04vh) and
nag_opt_nlp2_solve (e04wd)
each incorporate a check on the gradients being supplied. This involves verifying the gradients at the first point that satisfies the linear constraints and bounds. There is also an option to perform a more reliable (but more expensive) check on the individual gradient elements being supplied. Note that the checks are not infallible.
A second type of service function computes a set of finite differences to be used when approximating first derivatives. Such differences are required as input parameters by some functions that use only function evaluations.
nag_opt_lsq_uncon_covariance (e04yc) estimates selected elements of the variancecovariance matrix for the computed regression parameters following the use of a nonlinear least squares function.
nag_opt_estimate_deriv (e04xa) estimates the gradient and Hessian of a function at a point, given a function to calculate function values only, or estimates the Hessian of a function at a point, given a function to calculate function and gradient values.
Function Evaluations at Infeasible Points
All the functions for constrained problems will ensure that any evaluations of the objective function occur at points which approximately satisfy any simple bounds or linear constraints. Satisfaction of such constraints is only approximate because functions which estimate derivatives by finite differences may require function evaluations at points which just violate such constraints even though the current iteration just satisfies them.
There is no attempt to ensure that the current iteration satisfies any nonlinear constraints. If you wish to prevent your objective function being evaluated outside some known region (where it may be undefined or not practically computable), you may try to confine the iteration within this region by imposing suitable simple bounds or linear constraints (but beware as this may create new local minima where these constraints are active).
Note also that some functions allow you to return the parameter
(iflag or mode)
with a negative value to force an immediate clean exit from the minimization function when the objective function (or nonlinear constraints where appropriate) cannot be evaluated.
Related Problems
Apart from the standard types of optimization problem, there are other related problems which can be solved by functions in this or other chapters of the Library.
nag_mip_ilp_dense (h02bb) solves
dense integer LP problems,
nag_mip_iqp_dense (h02cb) solves
dense integer QP problems,
nag_mip_iqp_sparse (h02ce) solves
sparse integer QP problems and
nag_mip_transportation (h03ab) solves a special type of such problem known as a
‘transportation’ problem.
Several functions in
Chapters F04 and
F08 solve
linear least squares problems, i.e.,
minimize ∑ _{i = 1}^{m}r_{i}(x)^{2}$\mathrm{minimize}{\displaystyle \sum _{i=1}^{m}}{r}_{i}{\left(x\right)}^{2}$ where
r_{i}(x) = b_{i} − ∑ _{j = 1}^{n}a_{ij}x_{j}${r}_{i}\left(x\right)={b}_{i}{\displaystyle \sum _{j=1}^{n}}{a}_{ij}{x}_{j}$.
nag_fit_glin_l1sol (e02ga) solves an overdetermined system of linear equations in the
l_{1}${l}_{1}$ norm, i.e., minimizes
∑ _{i = 1}^{m}r_{i}(x)$\sum _{i=1}^{m}}\left{r}_{i}\left(x\right)\right$, with
r_{i}${r}_{i}$ as above, and
nag_fit_glinc_l1sol (e02gb) solves the same problem subject to linear inequality constraints.
nag_fit_glin_linf (e02gc) solves an overdetermined system of linear equations in the
l_{∞}${l}_{\infty}$ norm, i.e., minimizes
max_{i} r_{i}(x)$\underset{i}{\mathrm{max}}}\phantom{\rule{0.25em}{0ex}}\left{r}_{i}\left(x\right)\right$, with
r_{i}${r}_{i}$ as above.
Chapter E05 contains functions for global minimization.
Section [Methods for handling multiobjective optimization] describes how a multiobjective optimization problem might be addressed using functions from this chapter and from
Chapter E05.
Choosing Between Variant Functions for Some Problems
As evidenced by the wide variety of functions available in
Chapter E04, it is clear that no single algorithm can solve all optimization problems. It is important to try to match the problem to the most suitable function, and that is what the decision trees in
Section [Decision Trees] help to do.
Sometimes in
Chapter E04 more than one function is available to solve precisely the same minimization problem. Thus, for example, the general nonlinear programming functions
nag_opt_nlp1_solve (e04uc) and
nag_opt_nlp2_solve (e04wd) are based on similar methods. Experience shows that although both functions can usually solve the same problem and get similar results, sometimes one function will be faster, sometimes one might find a different local minimum to the other, or, in difficult cases, one function may obtain a solution when the other one fails.
After using one of these functions, if the results obtained are unacceptable for some reason, it may be worthwhile trying the other function instead. In the absence of any other information, in the first instance you are recommended to try using
nag_opt_nlp1_solve (e04uc), and if that proves unsatisfactory, try using
nag_opt_nlp2_solve (e04wd). Although the algorithms used are very similar, the two functions each have slightly different optional arguments which may allow the course of the computation to be altered in different ways.
Other pairs of functions which solve the same kind of problem are
nag_opt_qpconvex1_sparse_solve (e04nk) or
nag_opt_qpconvex2_sparse_solve (e04nq), for sparse quadratic or linear programming problems, and
nag_opt_nlp1_sparse_solve (e04ug) or
nag_opt_nlp2_sparse_solve (e04vh), for sparse nonlinear programming. In these cases the argument lists are not so similar as
nag_opt_nlp1_solve (e04uc) or
nag_opt_nlp2_solve (e04wd), but the same considerations apply.
Decision Trees
Tree 1: Selection chart for unconstrained problems
Tree 2: Selection chart for boundconstrained, linearlyconstrained and nonlinearlyconstrained problems
Tree 3: Linear programming
Tree 4: Quadratic programming
Functionality Index
Constrained minimum of a sum of squares, nonlinear constraints,   
using function values and optionally first derivatives, sequential QP method,   
Minimum, function of one variable,   
Minimum, function of several variables, nonlinear constraints,   
using function values and optionally first derivatives, sequential QP method,   
Minimum, function of several variables, nonlinear constraints (comprehensive),   
using function values and optionally first derivatives, sequential QP method,   
Minimum, function of several variables, simple bounds,   
Minimum, function of several variables, simple bounds (comprehensive),   
Minimum, function of several variables, simple bounds (easytouse),   
check user's function for calculating,   
initialization function for,   
retrieve integer optional parameter values used by,   
retrieve real optional parameter values used by,   
supply integer optional parameter values to,   
supply optional parameter values to,   
supply real optional parameter values to,   
Unconstrained minimum, function of several variables,   
Unconstrained minimum of a sum of squares (comprehensive):   
using function values only,   
using second derivatives,   
Unconstrained minimum of a sum of squares (easytouse):   
using function values only,   
using second derivatives,   
References
Bard Y (1974) Nonlinear Parameter Estimation Academic Press
Dantzig G B (1963) Linear Programming and Extensions Princeton University Press
Fletcher R (1987) Practical Methods of Optimization (2nd Edition) Wiley
Gill P E and Murray W (ed.) (1974) Numerical Methods for Constrained Optimization Academic Press
Gill P E, Murray W and Wright M H (1981) Practical Optimization Academic Press
Murray W (ed.) (1972) Numerical Methods for Unconstrained Optimization Academic Press
Wolberg J R (1967) Prediction Analysis Van Nostrand
PDF version (NAG web site
, 64bit version, 64bit version)
© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013