7 Introduction to Optimisation
233
for a series of increasing values of the penalty parameter μ, such that μα(x) → 0 as
μ → ∞, until the solution of the constrained optimisation problem is identified with
sufficient accuracy. From a computational point of view, superlinear convergence
rates might be achieved, in principle, by applying Newton’s method to solve
the minimisation problem (or its variants such as quasi-Newton methods). The
algorithmic behaviour is strictly related to the choice of the penalty parameter. If μ is
large, more importance is given to the feasibility than the optimality, and the iterates
could move to feasible regions far from the optimum, causing slow convergence and
premature termination.
The barrier methods or interior-point methods add terms to the objective function
that act as a barrier and prevent the iterates from leaving the feasible region. For
example, in the case of inequality constrained problems, a barrier problem can be
formulated as
min
x∈Ω
θ(μ),
where μ ≥ 0 and θ(μ) = inf{f (x) + μb(x) : c i (x) < 0, ∀i ∈ I }. The barrier
function b should be non-negative and continuous on the feasible region and go
to infinity as the boundary is approached from the interior. This would guarantee
that the iterates do not leave the domain. The starting point must be chosen in the
interior of the feasible region, and the Newton or quasi-Newton methods can solve
the successive barrier problem.
In the augmented Lagrangian methods, a penalty functions is added to the
Lagrangian:
L A (x, λ, μ) = f (x) − λ
T c(x) +
1
2μ
c(x)
2
2
Fixing λ to some estimate of the optimal Lagrange multipliers and μ > 0 to some
positive value, it is possible to find a value of x that approximately minimises
L A (·, λ, μ). Then the process is repeated updating λ and μ with the information
from the previous x-iterate.
In sequential linearly constrained methods, at every iteration, a Lagrangian is
minimised subject to a linearisation of the constraints.
The sequential quadratic programming has instead a completely different
approach. It employs Newton-like methods to solve directly the KKT conditions
of the original problem. The problem turns out to be a minimisation problem of
a quadratic approximation of the Lagrangian subject to a linear approximation of
the constraints. The search direction p k at the iterate (x k , λ k ) is the solution of the
problem
min
p
1
2 p T ∇ 2
xx L (x k , λ k )p + ∇f (x k ) · p
s.t. ∇c i (x k ) · p + c i (x k ) ≤ 0, i ∈ I .
233
for a series of increasing values of the penalty parameter μ, such that μα(x) → 0 as
μ → ∞, until the solution of the constrained optimisation problem is identified with
sufficient accuracy. From a computational point of view, superlinear convergence
rates might be achieved, in principle, by applying Newton’s method to solve
the minimisation problem (or its variants such as quasi-Newton methods). The
algorithmic behaviour is strictly related to the choice of the penalty parameter. If μ is
large, more importance is given to the feasibility than the optimality, and the iterates
could move to feasible regions far from the optimum, causing slow convergence and
premature termination.
The barrier methods or interior-point methods add terms to the objective function
that act as a barrier and prevent the iterates from leaving the feasible region. For
example, in the case of inequality constrained problems, a barrier problem can be
formulated as
min
x∈Ω
θ(μ),
where μ ≥ 0 and θ(μ) = inf{f (x) + μb(x) : c i (x) < 0, ∀i ∈ I }. The barrier
function b should be non-negative and continuous on the feasible region and go
to infinity as the boundary is approached from the interior. This would guarantee
that the iterates do not leave the domain. The starting point must be chosen in the
interior of the feasible region, and the Newton or quasi-Newton methods can solve
the successive barrier problem.
In the augmented Lagrangian methods, a penalty functions is added to the
Lagrangian:
L A (x, λ, μ) = f (x) − λ
T c(x) +
1
2μ
c(x)
2
2
Fixing λ to some estimate of the optimal Lagrange multipliers and μ > 0 to some
positive value, it is possible to find a value of x that approximately minimises
L A (·, λ, μ). Then the process is repeated updating λ and μ with the information
from the previous x-iterate.
In sequential linearly constrained methods, at every iteration, a Lagrangian is
minimised subject to a linearisation of the constraints.
The sequential quadratic programming has instead a completely different
approach. It employs Newton-like methods to solve directly the KKT conditions
of the original problem. The problem turns out to be a minimisation problem of
a quadratic approximation of the Lagrangian subject to a linear approximation of
the constraints. The search direction p k at the iterate (x k , λ k ) is the solution of the
problem
min
p
1
2 p T ∇ 2
xx L (x k , λ k )p + ∇f (x k ) · p
s.t. ∇c i (x k ) · p + c i (x k ) ≤ 0, i ∈ I .