232
A. Riccardi et al.
region radius, and then seeks for the best move to attain the best improvement of the
objective function.
As an example for line search methods, there are (refer to [2] for the details about
the methods):
• Steepest descent method: it chooses as search direction the descent one p SD
k =
−∇f (x k ).
• Newton methods: the search direction is the solution of the Newton equation
p N
k = −H (x k ) −1 ∇f (x k ).
• Non-linear conjugate gradient methods: where the search direction is defined
as p CG
k
= −∇f (x k ) + β k p k−1 with β k ∈ R.
• Quasi-Newton methods: they don’t require the computation of the secondorder derivatives but use an approximation of it (B), p
QN
k
= −B(x k ) −1 ∇f (x k );
quasi-Newton methods significantly increase convergence speed compared with
Newton ones.
Newton and quasi-Newton methods are the ones that attain a superlinear rate of
convergence, but they require the computation (or approximation) and the storage
of the Hessian matrix. On the other hand, the methods that rely just on the gradient
information are slower at convergence.
Most of the methods have a counterpart for the thrust region approach. In
the quadratic model, the Hessian matrix is substituted by the one used by each
method (identity matrix for the steepest descent, H k for the Newton method and
its approximation B k for quasi-Newton methods). It is possible to prove that the
resulting search direction is defined as in the line search methods and its length
constrained by the trust region radius.
The presentation of the algorithms for the unconstrained case was necessary
to introduce the techniques for solving constrained NLP problems as parts of
them rely on the idea of converging to the solution of the constrained problem by
approximating it with a sequence of unconstrained problems.
The algorithms for constrained NLP problems can be grouped in:
• Penalty, barrier, augmented Lagrangian methods and sequential linearly
constrained methods: they solve a sequence of simpler subproblems (unconstrained or with simple linearised constraints) related to the original one. The
solutions of the subproblems converge to the solution of the primal one either in
a finite number of steps or at the limit.
• Newton-like methods: they try to find a point satisfying the necessary conditions
of optimality (KKT conditions in general). The sequential quadratic programming (SQP) method is part of this class.
The penalty methods combine the objective function and constraints into a penalty
function α(x) which is null for feasible points and positive otherwise. The problem
to be minimised is the unconstrained problem
min
x∈Ω
f (x) + μα(x)
A. Riccardi et al.
region radius, and then seeks for the best move to attain the best improvement of the
objective function.
As an example for line search methods, there are (refer to [2] for the details about
the methods):
• Steepest descent method: it chooses as search direction the descent one p SD
k =
−∇f (x k ).
• Newton methods: the search direction is the solution of the Newton equation
p N
k = −H (x k ) −1 ∇f (x k ).
• Non-linear conjugate gradient methods: where the search direction is defined
as p CG
k
= −∇f (x k ) + β k p k−1 with β k ∈ R.
• Quasi-Newton methods: they don’t require the computation of the secondorder derivatives but use an approximation of it (B), p
QN
k
= −B(x k ) −1 ∇f (x k );
quasi-Newton methods significantly increase convergence speed compared with
Newton ones.
Newton and quasi-Newton methods are the ones that attain a superlinear rate of
convergence, but they require the computation (or approximation) and the storage
of the Hessian matrix. On the other hand, the methods that rely just on the gradient
information are slower at convergence.
Most of the methods have a counterpart for the thrust region approach. In
the quadratic model, the Hessian matrix is substituted by the one used by each
method (identity matrix for the steepest descent, H k for the Newton method and
its approximation B k for quasi-Newton methods). It is possible to prove that the
resulting search direction is defined as in the line search methods and its length
constrained by the trust region radius.
The presentation of the algorithms for the unconstrained case was necessary
to introduce the techniques for solving constrained NLP problems as parts of
them rely on the idea of converging to the solution of the constrained problem by
approximating it with a sequence of unconstrained problems.
The algorithms for constrained NLP problems can be grouped in:
• Penalty, barrier, augmented Lagrangian methods and sequential linearly
constrained methods: they solve a sequence of simpler subproblems (unconstrained or with simple linearised constraints) related to the original one. The
solutions of the subproblems converge to the solution of the primal one either in
a finite number of steps or at the limit.
• Newton-like methods: they try to find a point satisfying the necessary conditions
of optimality (KKT conditions in general). The sequential quadratic programming (SQP) method is part of this class.
The penalty methods combine the objective function and constraints into a penalty
function α(x) which is null for feasible points and positive otherwise. The problem
to be minimised is the unconstrained problem
min
x∈Ω
f (x) + μα(x)