7 Introduction to Optimisation
231
7.2.1.2 Algorithms
In the last 50 years, a variety of approaches have been developed to solve NLP
problems, first tackling the most simple unconstrained NLP problem and then
expanding their application also to the constrained case. A starting point, denoted
by x 0 , is always provided to the algorithm by the knowledge of the user or
left to the optimiser. The optimisation process iterates exploiting information on
the objective, constraints, their derivatives and the previous iterates to terminate
whenever no further progress can be made or the optimal solution is approximated
with acceptable accuracy.
The algorithm for unconstrained NLP is presented first. They are divided into
two groups: line search based and trust region.
• Line search: the algorithm determines a search direction p k and searches along
this direction from the current iterate x k for a new iterate with a lower function
value. The step length to move along p k can be found by approximately solving
the minimisation problem
min
α>0
f (x k + αp k ).
At the new point, a new search direction and step length are computed, and the
process is repeated until convergence.
• Trust region: the algorithm constructs a model function m k whose behaviour
near the current iterate x k is similar to that of the actual objective function f .
The iteration direction of search p is found as the solution of the problem
min
p∈Ω
m k (x k + p),
where x k + p lies inside the trust region. If the solution does not produce a
sufficient decrease in f, it means that the trust region is too large. In this case the
trust region is shrunk and the minimisation problem is solved again. Usually the
trust region is the ball
p 2 ≤ Δ, where Δ is the trust region radius
and the model m k is usually a quadratic function of the form
m k (x k + p) = f (x k ) + p
T
∇f (x k ) +
1
2
p
T H (x k )p
where H is the Hessian matrix of the Lagrangian.
The two approaches differ in the way they choose the direction and the distance of
the move: line search based fixes the direction p k and optimises the length of the
step. Thrust region instead first chooses the maximum distance of the move, the trust
231
7.2.1.2 Algorithms
In the last 50 years, a variety of approaches have been developed to solve NLP
problems, first tackling the most simple unconstrained NLP problem and then
expanding their application also to the constrained case. A starting point, denoted
by x 0 , is always provided to the algorithm by the knowledge of the user or
left to the optimiser. The optimisation process iterates exploiting information on
the objective, constraints, their derivatives and the previous iterates to terminate
whenever no further progress can be made or the optimal solution is approximated
with acceptable accuracy.
The algorithm for unconstrained NLP is presented first. They are divided into
two groups: line search based and trust region.
• Line search: the algorithm determines a search direction p k and searches along
this direction from the current iterate x k for a new iterate with a lower function
value. The step length to move along p k can be found by approximately solving
the minimisation problem
min
α>0
f (x k + αp k ).
At the new point, a new search direction and step length are computed, and the
process is repeated until convergence.
• Trust region: the algorithm constructs a model function m k whose behaviour
near the current iterate x k is similar to that of the actual objective function f .
The iteration direction of search p is found as the solution of the problem
min
p∈Ω
m k (x k + p),
where x k + p lies inside the trust region. If the solution does not produce a
sufficient decrease in f, it means that the trust region is too large. In this case the
trust region is shrunk and the minimisation problem is solved again. Usually the
trust region is the ball
p 2 ≤ Δ, where Δ is the trust region radius
and the model m k is usually a quadratic function of the form
m k (x k + p) = f (x k ) + p
T
∇f (x k ) +
1
2
p
T H (x k )p
where H is the Hessian matrix of the Lagrangian.
The two approaches differ in the way they choose the direction and the distance of
the move: line search based fixes the direction p k and optimises the length of the
step. Thrust region instead first chooses the maximum distance of the move, the trust