Convergence to Second Order Stationary Points in Inequality Constrained Optimization.
We propose a new algorithm for the nonlinear inequality constrained minimization problem, and prove that it generates a sequence converging to points satisfying the KKT second order necessary conditions for optimality. The algorithm is a line search algorithm using directions of negative curvature and it can be viewed as a nontrivial extension of corresponding known techniques from unconstrained to constrained problems. The main tools employed in the definition and in the analysis of the algorithm are a differentiable exact penalty function and results from the theory of LC1 functions.
Introduction
We are concerned with the inequality constrained minimization problem (P)
min f(x)
are three times continuously differentiable.
Our aim is to develope an algorithm that generates sequences converging to points
x satisfying, together with a suitable multiplier - 2 IR m , both the KKT first order
necessary optimality conditions
(1)
and the KKT second order necessary optimality conditions
z - 0: (2)
In the sequel we will call a point x satisfying (1) a first order stationary point (or just
stationary point), while a point satisfying both (1) and (2) will be termed second order
stationary point.
In the unconstrained case the conditions (1) and (2) boil down to
respectively. Standard algorithms for unconstrained minimization usually
generate sequences converging to first order stationary points. In a landmark paper
[21] (see also [23, 22, 16, 20] and references therein for subsequent developments), McCormick
showed that, by using directions of negative curvature in an Armijo-type line
search procedure, it is possible to guarantee convergence to second order stationary
points. From a theoretical point of view, this is a very strong result, since it makes much
more likely that the limit points of the sequence generated by the algorithm are local
minimizers and not just saddle points. Furthermore, from a practical point of view, the
use of negative curvature directions turns out to be very helpful in the minimization of
problems with large non-convex regions [16, 20]. Convergence to second order stationary
points was later established also for trust-region algorithms [25, 24], and this constitute
one of the main reasons for the popularity of this class of methods. Trust-region algorithms
have been extended to equality constrained and box constrained problems so as
to mantain convergence to second order stationary points [2, 8, 13, 5, 25, 24, 26]; while
negative curvature line search algorithms have been proposed for the linearly inequality
constrained case [22, 17]. However, as far as we are aware of, no algorithm for the
solution of the more complex nonlinearly inequality constrained minimization Problem
(P) exists which generates sequences converging to second order stationary points. The
main purpose of this paper is to fill this gap by presenting a negative curvature line
search algorithm which enjoys this property.
The basic idea behind our approach can be easily explained as follows.
(a) Reduce the constrained minimization Problem (P) to an equivalent unconstrained
minimization problem by using a differentiable exact penalty function.
(b) Apply a negative curvature line search algorithm to the minimization of the
penalty function.
Although appealingly simple we have to tackle some difficulties to make this approach
viable. First of all we have to establish a connection between the unconstrained
stationary points of the penalty function provided by the unconstrained minimization
algorithm and the constrained second order stationary points of Problem (P). Secondly,
we must cope with the fact that differentiable exact penalty functions, although once
continuously differentiable, are never twice continuously differentiable everywhere, so
that we cannot use an off-the-shelf negative curvature algorithm for its minimization.
Furthermore, even in points where the second order derivatives exist, their explicit evaluation
would require the use of the third order derivatives of the functions f and g,
which we are not willing to calculate.
To overcome these difficulties we develop a negative curvature algorithm for the
unconstrained minimization of the penalty function which is based on the theory of LC 1
functions and on generalized Hessians. We show that by using a suitable approximation
to elements of the generalized Hessian of the penalty function we can guarantee that the
unconstrained minimization of the penalty function yields an unconstrained stationary
point where a matrix which approximates an element of the generalized Hessian is
positive semidefinite. This suffices to ensure that the point so found is also a second
order stationary point of Problem (P).
We believe that the algorithm proposed in this paper is of intereset because, for
the first time, we are able to prove convergence to second order stationary points for
general inequality constrained problems. We do so by a fairly natural extension of
negative curvature algorithms from unconstrained to constrained problems; we note
that the computation of the negative curvature direction can be performed in a manner
analogous to and at the same cost as in the unconstrained case. We also remark that
we never require the complementarity slackness assumption to establish our results.
Finally, we think that the use of some non trivial nonsmooth analysis results to analyze
the behavior of smooth algorithms is a novel feature that could be fruitfully applied
also in other cases.
The paper is organized as follows. In the next section we recall some few known
facts about LC 1 functions and generalized Hessians and on the asymptotic identification
of active constraints. Furthermore, we also introduce the penalty function along with
some of its relevant properties. In Section 3 we introduce and analyze the algorithm.
In the fourth section we give some hints on the practical realization of the algorithm.
Finally, in the last section we outline possible improvements and make some remarks.
We finally review the notation used in this paper. The gradient of a function h :
indicated by rh, while its Hessian matrix is denoted by r 2 h. If
then the matrix rH is given by I is an index set, with
I I is the vector obtained by considering the components of H in I. We
indicate by k \Delta k the Euclidean norm and the corresponding matrix norm. If S is a subset
of IR n , coS denotes its convex hull. If A is a square matrix, - min (A) denotes its smallest
eigenvalue. The Lagrangian of Problem (P) is L(x;
by L(x; -(x)) the Lagrangian of Problem (P) evaluated in -(x). Analogously, we
indicate by r x L(x; -(x)) (r 2
xx L(x; -(x))) the gradient (Hessian) of the Lagrangian with
respect to x evaluated in -(x).
Background material
In this section we review some results on differentiability of functions and on the identification
of active constraints. We also recall the definition and some basic facts about
a differentiable exact penalty function for Problem (P) and we establish some related
new results.
2.1 LC 1 functions.
is said to be an LC 1 function on an open set
O if
- h is continuously differentiable on O,
- rh is locally Lipschitz on O
functions were first systematically studied in [18], where the definition of generalized
Hessian and the theorem reported below where also given.
The gradient of h is locally Lipschitz on O; rh is therefore differentiable almost
everywhere in O so that its generalized Jacobian in Clarke's sense [3] can be defined.
This is precisely the generalized Hessian of h, whose definition is as follows.
be an LC 1 function on the open set O and let x belong
to O. We define the generalized Hessian of h at x to be the set @ 2 h(x) of matrices defined
as
differentiable at x k and r 2 h(x k
Note that @ 2 h(x) is a nonempty, convex, compact set of symmetric matrices. Further-
more, the point-to-set map x 7! @ 2 h(x) is bounded on bounded sets [18].
For LC 1 functions a second-order Taylor-like expansion is possible. This is the main
result on LC 1 function we shall need in this paper.
Theorem 2.1 Let h : be an LC 1 function on the open set O and let x and y
be two points in O such that [x; y] is contained in O. Then
2.2 Identification of active constraints
In this section we recall some results on the identification of active constraints at a
stationary point -
x of the nonlinear program (P).
We refer the interested reader to [14] and to references therein for a detailed discussion
of this issue. Here we recall only some results in order to stress the fact that, in a
neighborhood of a first order stationary point, it is possible, under mild assumptions,
to correctly identify those constraints that are active at the solution.
First of all we need some terminology. Given a stationary point -
x with a corresponding
multiplier -
-, which we suppose to be unique, we denote by I 0 (-x) the set of
active constraints
I 0 (-x) := fij g i
while I + (-x) denotes the index set of strongly active constraints
I
Our aim is to construct a rule which is able to assign to every point x an estimate
A(x) so that lies in a suitably small neighborhood of the
stationary point -
x.
Usually estimates of this kind are obtained by comparing the values of g i (x) with
the value of an estimate of the multiplier -. For example, it can be easily shown that
the set
I \Phi (x) :=
where c is a positive constant and - : is a multiplier function (i.e. a continuous
function such that
-) coincides with the set I 0 (-x) for all x in a sufficiently
small neighborhood of a stationary point -
x which satisfies the strict complementarity
condition (see the next section for an example of multiplier function). If this condition
is violated, then only the inclusions
I
hold [14]. If the stationary point -
x does not satisfy strict complementarity, the situation
is therefore more complex, and only recently it has been shown that it is nevertheless
possible to correctly estimate the set I 0 (-x) [14]. We will not go into details here, we only
point out that the identification of the active constraints when strict complementarity
does not hold is possible under very mild assumptions in a simple way. The identification
rule takes the following form:
where ae(x) is a function that can take different forms according to the assumptions
made on the stationary point - x. For example, if in a neighborhood of -
x both f and g
are analytic (an assumption which is met in most of the practical cases), one can define
ae(x) as
log(r(x))
where
With this choice the set A(x) defined by (4) will coincide with I 0 (-x) in a suitable
neighborhood of -
x.
2.3 Penalty function
In this section we consider a differentiable penalty function for Problem (P), we recall
some relevant known facts and prove some new results which are related to the
differentiability issues dealt with in Section 2.1.
In order to define the differentiable penalty function and to guarantee some of the
properties that will be needed we make the following two assumptions.
Assumption A. For any x 2 IR n , the gradients rg i (x), i 2 I 0 (x), are linearly independent

Assumption B. For any x 2 IR n , the following implication holds
Assumptions A and B, together with Assumption C, which will be stated in Section 3,
are the only assumptions used to establish the results of this paper. These assumptions,
or assumptions similar to them, are frequently encountered in the analysis of constrained
minimization algorithms. However, we point out that they can be considerably relaxed;
this will be discussed in Section 5. We chose to use this particular set of assumptions
in order to simplify the analysis and to concentrate on the issues related to the main
topic of the paper, i.e. convergence to second order stationary points.
We start by defining a multiplier function
where M(x) is the m \Theta m matrix defined by:
and G(x) := diag(g i (x)). The main property of this function is that it is continuously
differentiable (see below) and, if -
x is a first order stationary point, then -x) is the
corresponding multiplier (which, by Assumption A, is unique). Using this function we
can define the following penalty function
is the so-called penalty parameter.
Theorem 2.2 The following properties hold:
(a) For every ffl, the penalty function Z is continuously differentiable on IR n and its
gradient is given by
'-
where
e i is the i-th column of the m \Theta m identity matrix and  (x) := diag(- i (x)).
(b) For every ffl, the function Z is an LC 1 function on IR n .
(c) Let -
x be a first order stationary point for Problem (P) and let ffl be given. Then there
exists a
neighborhood\Omega of -
x such that, for every x
in\Omega , the following overestimate
of the generalized Hessian of Z evaluated at x holds
where
A
is matrix for which we can write kKA (x)k - ae(x) for a nonegative continuous
function ae such that
In particular, the following overstimate holds in - x
where
xx L(-x; -x)) +r-A (-x)rg A (-x) T
Proof. Point (a) is proved in [11].
Point (b) follows from the expression of the gradient given in (a) taking into account
the differentiability assumptions
The proof of point (c) can be derived from the very definition of generalized Hessian
in the following way. Let -
x be a stationary point of Problem (P). Consider a point
x in a
neighborhood\Omega of -
x and sequences of points fx k g converging to x with the
gradient of Z existing in x k . This will happen either if (a) for no i
or if (b) for all i for which g i
I \Phi (x)g. By recalling the expression of the gradient given
previously we can write
'-
'-
where I \Psi It is now easy to see that, both in case (a) and
(b), the Hessian of Z(x; ffl) in x k can be obtained by differentiating this expression and
this gives
rg I \Phi
where K I \Phi rapresents the sum of terms always containing as a factor either
I \Phi Taking into account the definition of @ 2 Z(x; ffl) and that, as
discussed in the previous section,
if\Omega is suitably small
I
we have that both g I \Phi
x. The assertion of point
(c) now follows from these facts and the definition of A.
The following theorem gives a sufficient condition, in terms of matrices in the overestimate
~
stationary point of Problem (P) to be a second order stationary
point.
Theorem 2.3 Let -
x be a first order stationary point of Problem (P) and let ffl be given.
Then, if a matrix H exists in ~
which is positive semidefinite, - x is a second
order stationary point of Problem (P).
Proof. Let H in ~
positive semidefinite and suppose by contradiction that
x does not satisfy the KKT second order necessary conditions (2). Then a vector z exists
such that
rg I 0
(recall that -x) equals the multiplier associated with -
x). On the other hand, by
Theorem 2.2 (c) and by Caratheodory theorem, we also have that, for some integer
where, for each i, fi i - 0,
A. Since, for each i, A i 2 A, we can
write, taking into account the definition of H(-x; ffl; A i ) and (9),
z T H(-x; ffl; A i
from which
z
immediately follows. But this contradict the assumption that H is positive semidefinite
and the proof is complete.
This result will turn out to be fundamental to our approach, since our algorithm will converge
to first order stationary stationary points where at least one element in ~
is positive semidefinite.
In the remining part of this section we consider some technical results about penalty
functions that will be used later on and that help illustrate the relation between the
function Z and Problem (P).
Proposition 2.4 (a) Let ffl ? 0 and x 2 IR n be given. If x is an unconstrained stationary
point of Z and then x is a first order stationary point of
Problem (P).
(b) Conversely, if x is a first order stationary point of Problem (P), then, for every
positive ffl, rZ(x;
Proof. See [11].
Proposition 2.5 Let D ae IR n be a compact set. Then, there exists an
for every x 2 D and for every ffl 2 (0; -ffl], we have
Proof. Let D 1 ae IR n be a compact subset such that D ae intD 1 . In the proof of
Proposition 14 in [12] it is shown that if - x is a feasible point in intD 1 , and therefore in
D, we can find positive ffl( -
x), oe(-x) and ae 0 (-x) such that
More precisely, (10) derives from formula (24) in [12] and the discussion which follows
that formula. Indicate by M the maximum of krg(x)k for x
note that, by Assumption A, M ? 0. Then, recalling that krg(x) T rZ(x; ffl)k -
krg(x)kkrZ(x; ffl)k, we can easily deduce from (10) that
where we set
Suppose now that the theorem is not true. Then, sequences fx k g and fffl k g exist,
such that
and
Since
recalling the expression of rZ, gives
Thus, by Assumption B we have that -
x is feasible. But then, we get a contradiction
between (12) and (11), and this concludes the proof.
Note that Proposition 2.4 and Proposition 2.5 imply that, given a compact set D, if ffl is
sufficiently small, then every stationary point of Problem (P) in D is an unconstrained
stationary point of Z and, vice versa, every unconstrained stationary point of Z in D is
a stationary point of Problem (P). We refer the interested reader to the review paper [9]
and references therein for a more detailed discussion of the properties of differentiable
penalty functions.
3 Convergence to second order stationary points
In this section we consider a line search algorithm for the minimization of Z(x; ffl) which
yields second order stationary points of Problem (P). For the sake of clarity we break
the exposition in three parts. In Section 3.1 we first consider a line search algorithm
(Algorithm M) which converges, for a fixed value of the penalty parameter ffl, to an
unconstrained stationary point of the penalty function Z. By Proposition 2.4 we know
that if the penalty parameter were sufficiently small, we would have thus obtained a
first order stationary point of Problem (P). Therefore, in Section 3.2, we introduce
an algorithm (Algorithm SOC) where Algorithm M is embedded in a simple updating
scheme for the penalty parameter based on Proposition 2.5. We show that after a
finite number of reductions the penalty parameter stays fixed and every limit point of
Algorithm SOC is a first order stationary point of Problem (P). Finally, in Section 3.3
we refine the analysis of Algorithm SOC and we show that every limit point is actually
a second order stationary point of Problem (P).
In order to establish the results of Sections 3.1, 3.2 and 3.3 we assume that the
directions used in Algorithm M satisfy certain conditions. In Section 4 we will illustrate
possible ways for generating directions which fulfil these conditions.
In order to simplify the analisys we shall assume, from now on, that the following
assumption is satisfied.
Assumption C. The sequence fx k g of points generated by the algorithms considered
below is bounded.
3.1 Convergence for fixed ffl to unconstrained stationary points
of Z: Algorithm M
We first consider a line search algorithm for the unconstrained minimization of the
penalty function Z which generates, for a fixed value ffl of the penalty parameter, sequences
converging to unconstrained stationary points of the penalty function. In all
this section, ffl is understood to be a fixed positive constant.
The algorithm generates a sequence fx k g according to the following rule:
Algorithm M
where
and where ff k is compute by the Linesearch procedure below.
Linesearch procedure
Step 2: If
set ff
Step 3: Choose ff 2 [oe 1 ff; oe 2 ff], and go to Step 2.
We assume that the matrices H k depend on the sequence fx k g and that the directions
and the matrices H k are bounded and satisfy the following conditions:
Condition 1. The directions s k are such that rZ(x k ; ffl) T s k - 0 and
0:
Condition 2. The directions d k are such that rZ(x k ; ffl) T d k - 0 and, together with the
matrices H k , they satisfy
ae d T
k is not positive semidefinite
0:
Condition 3. Let fx k g and fu k g be sequences converging to a first order stationary
point -
x of Problem (P). Then, for every sequence of matrices fQ k g, with
is a sequence of numbers converging to 0.
Algorithm M resembles classical line search algorithms using negative curvature
directions to force convergence to second order stationary points in unconstrained min-
imization. The only apparent difference is that we have the exponent t(x k ) defined by
while in corresponding unconstrained algorithms we usually have t(x k
every k. We need this change in order to be able to tackle the fact that the penalty
function is not everywhere twice continuously differentiable (see, for example, the proof
of Proposition 3.1).
We also assume that the directions s k , d k and the matrices H k satisfy Conditions
1-3. Conditions 1 and 2 are fairly standard and similar to those employed in the
unconstrained case. Condition 3, on the sequence of matrices H k , is, again, related
to the nondifferentiability of the gradient of Z. In fact, the matrix H k is supposed
to convey some second order information on the penalty function; therefore Condition
3 imposes a certain relation between the matrices H k and the generalized Hessians
of Z. Note that if the function Z were twice continuously differentiable the choice
would satisfy, by continuity, Condition 3.
The following proposition shows that the linesearch procedure described above is
well defined in all the cases that, we shall see, are of interest for us.
Proposition 3.1 The linesearch procedure is well defined, namely at each iteration the
test of Step 2 is satisfied for every ff sufficiently small if the point x k either (a) is not
an unconstrained stationary point of the function Z or (b) is a first order stationary
point of Problem (P) and H k is not positive semidefinite.
Proof. Assume by contradiction the assertion of the proposition is false. Then there
exists a sequence fff j g such that ff
Z
and either the condition (a) or the condition (b) hold. By Theorem 2.1 and taking
into account that rZ(x k ; ffl) T d k - 0 by Condition 2, we can find a point
Z
where Q(u k ) is a symmetric matrix belonging to @ 2 Z(u k ; ffl).
Therefore, by (14) and (15), we have:
Now we consider two cases. If condition (a) holds, then krZ(x k ; ffl)k 6= 0. We have
that dividing both sides
of (16) by ff 2
, by taking into account that by making the limit for
and by recalling that the sequence fQ(u k )g is bounded, we obtain the contradiction
If condition (b) holds, then x k is a first order stationary point of Problem (P) and
H k is not positive semidefinite. We have, by Proposition 2.4 (b), that rZ(x k ;
so that rZ(x k ; ffl) T s dividing both sides of (16)
by ff 2t(x k )
by making the limit for recalling that the sequence fQ(u k )g is
bounded, and by recalling that Condition 3 implies
with we obtain from (16)
which, recalling that H k is not positive semidefinite, contradicts Condition 2.
Proposition 3.1 shows that Algorithm M can possibly fail to produce a new point
only if, for some k, rZ(x k ; supposing that this trivial case does not
occur, the next theorem illustrates the behaviour of an infinite sequence generated by
Algorithm M.
Theorem 3.2 Let fx k g be an infinite sequence produced by Algorithm M. Then, every
limit point x   of fx k g is such that rZ(x
Proof. Since the sequence fZ(x k ; ffl)g is monotonically decreasing, Z is continuous
and fx k g is bounded by Assumption C, it follows that fZ(x k ; ffl)g converges. Hence
lim
Then, by recalling the acceptability criterion of the line search, Condition 1 and Condition
2, we have:
Therefore, (17), (18), Condition 1 and Condition 2 yield:
The boundness of s k and d k , Condition 1, Condition 2, (19) and (20) imply in turn:
Suppose now, by contradiction, that there exists a converging subsequence fx k gK 1
whose limit point x   is not a stationary point. For semplicity and without loss of
generality we can rename the subsequence fx k gK 1
by fx k g.
Condition 1, (19) and rZ(x   ; ffl) 6= 0 imply
By (23) we have that there exists an index -
k such that, for all k -
Z
for some oe k 2 [oe Theorem 2.1 and taking into account that rZ(x k ; ffl) T d k - 0
by Condition 2, we can find, for any k -
k, a point
Z
with From (24) and (25) It follows that
Dividing both sides by
and by simple manipulations we obtain
By (21) and (22) we have Condition 1,
and since the sequence fQ(u k )g is bounded,
we have by (27)
lim
Condition 1 now implies that rZ(x   ; which contradicts the fact the subsequence
does not converge to an unconstrained stationary point and this proves the theorem

In the next sections, given x k , we indicate by M(x k ) the new point produced by the
Algorithm M described above.
3.2 Updating ffl to guarantee convergence to stationary points
of Problem (P): Algorithm SOC
In this section we show that it is possible to update in a simple way the value of the
penalty parameter ffl while minimizing the penalty function Z by Algorithm M, so that
every limit point of the sequence of points generated is a first order stationary point of
Problem (P). This is accomplished by the Algorithm SOC below. In the next section we
shall show that actually, under some additional conditions, the limit points generated by
Algorithm SOC are also second order stationary points of Problem (P). This motivates
the name SOC, which stands for Second Order Convergence.
Algorithm SOC
Step 0: Select x 0 and ffl 0 . Set
to Step 2; else go to Step 3.
Step 2: If max[g(x k
and H k 6- 0 go to Step 4; otherwise if max[g(x k
Step 3: If krZ(x k go to Step 4; else go to Step 5.
Step 4: Compute to Step 1.
Step 5: Set x and go to Step 1.
Algorithm SOC is related to similar schemes already proposed in the literature (see,
e.g., the review paper [9] and references therein). The core step is Step 3, where, at
each iteration, the decision of whether to update ffl is taken. This Step is obviously
motivated by Propositions 2.5 and Proposition 2.4 (a).
Theorem 3.3 Algorithm SOC is well defined. Furthermore, let fx k g and fffl k g be the
sequences produced by Algorithm SOC. Then, either the algorithm terminates after p
iterations in a first order stationary point x p of Problem (P), or there exist an index -
and an -ffl ? 0 such that, for every k - k, ffl and every limit point of the sequence
is a first order stationary point of Problem (P).
Proof. The algorithm is well defined because every time we reach Step 4 Proposition
3.1 ensures the M(x k ) is well defined. If the algorithm stops after a finite number
of iterations, then, by the instructions of Steps 1 and 2, we have rZ(x
The thesis then follows by Proposition 2.4 (a). Therefore,
assume that an infinite sequence of points is generated. Assumption C and Theorem
2.5 guarantee that ffl is updated only a finite number of times. So, after a finite number
of times ffl Algorithm SOC reduces to the application of Algorithm M to
Z(x; -ffl). Then, by Theorem 3.2, every limit point -
x of fx k g is such that rZ(-x;
Since the test at Step 3 is eventually always satisfied, this implies, in turn, that
The thesis now follows by Theorem 2.4 (a).
3.3 Algorithm SOC: Second order convergence
In this section we prove that under additional suitable conditions, every limit point
of the sequence fx k g generated by Algorithm SOC actually satisfies the KKT second
order necessary conditions. To establish this result we need the two further conditions
below.
Condition 4. Let fx k g be a sequence converging to a first order stationary point of
Problem (P). Then the directions d k and the matrices H k satisfy
Condition 5. Let fx k g be a sequence converging to a first order stationary point -
x of
Problem (P), and let ffl ? 0 be given. Then
Condition 4 mimics similar standard conditions in the unconstrained case, where H k
is the Hessian of the objective function. Roughly speaking, it requires the direction d k
to be a sufficiently good approximation to an eigenvector corresponding to the smallest
eigenvalue of H k . Condition 5, similarly to Condition 3, imposes a connection between
the matrices H k and the generalized Hessian of Z.
The following theorem establishes the main result of this paper.
Theorem 3.4 Let fx k g be the sequence produced by Algorithm SOC. Then, either the
algorithm terminates at a second order stationary point x p of Problem (P) or it produces
an infinite sequence fx k g such that every limit point x   of fx k g is a second order
stationary point of Problem (P).
Proof. If Algorithm SOC terminates after a finite number of iterations we have, by
Theorem 3.3, that x p is a first order stationary point of Problem (P). On the other
hand, by the instructions of Step 2 and by Condition 5, we have that H p is positive
semidefinite and belongs to ~
Therefore, the assertion follows from Theorem
2.3. We then pass to the case in which an infinite sequence is generated.
We already know, by Theorem 3.3, that every limit point of the sequence is a
first order stationary point of Problem (P). We also know that eventually ffl k is not
updated, so that ffl Then, by Theorem 2.3 it will suffice to show that ~
contains a positive semidefinite element. Suppose the contrary. Let fx k g converge to
x   . Reasoning as in the beginning of the proof of Theorem 3.2, we have that (21) and
still hold. Then, we can assume, renumbering if necessary, that
0: (30)
In fact, if this is not the case, (22), Conditions 4 and 5 imply the contradiction that
tends to a positive semidefinite element in ~
Then, by (30) and by repeating again the arguments used in the proof of Theorem
3.2, we have that there exists an index - k such that, for all k - k, (26) holds. From (26)
we get, recalling Condition 3:
which, taking into account that, by Condition 1, rZ(x and the fact that
dividing both sides by
we have:
By (21) and (22) we have so that fQ(u k )g is bounded, while by Condition 5 we
have, renumbering if necessary, H
by Condition 2, (31) implies :
lim
and hence, by recalling Condition 4, we have that - min (H   Condition
5, contradicts the fact the subsequence fx k g converges to a KKT point where every
element in ~
-ffl) is not positive semidefinite.
4 Practical realization
In this section we show how we can calculate directions s k , d k and matrices H k satisfying
Conditions 1-5 required in the previous sections.
Let the matrix H k be defined as
and A(x) is any estimate of the active set with the
property that, in a neighborhood of a stationary point - x, In section 2.3
we discussed more in detail some possible choices for A(x) and gave adequate references.
Note also that, in a stationary point -
x, the matrix H k belongs to ~
Given
this matrix we have a wide range of choices for s k and d k .
theoretically sound option is to take s k to be \GammarZ(x k
(b) A more practical choice, however, could be that of taking s k as the solution
of the linear system
where D k is a diagonal matrix chosen so that the H k +D k is positive definite and
the smallest eigenvalue of the sequence fH k +D k g is bounded away from 0. The
matrix D k should be 0 if the matrix H k is positive definite with smallest eigenvalue
greator than a (small) positive threshold value. Methods for automatically
constructing the matrix D k while solving the system H k s are well
known and used in the unconstrained case.
(c) Another possible choice is to take s k as the direction employed in [10, 1, 15].
can be chosen to be to be an eigenvector associated to the smallest eigenvalue
of the matrix H k with the sign possibly changed, in order to ensure rZ(x k ; ffl) T d k -
(b) Suitable approximations of the direction of point (a) calculated as indicated,
for example, in [23] and [20] could also be employed.
The design of an algorithmically effective choice for s k and d k is beyond the scope
of this paper. Here we only wanted to illustrate the a wide range of options is available;
further choices are certainly possible.
In the sequel, for the sake of concreteness, we shall assume that both s k and d k are
chosen according to the options (a) listed above. With these choices, and since we are
supposing that fx k g remains in a bounded set, it is easy to see that also the sequences
are bounded. It is also standard to show that Conditions 1, 2 and
4 are satisfied. Furthermore, if we recall that, in a neighborhood of a stationary point -
x
of Problem (P), is easy to see that, by the very definition of ~
also Condition 5 is met by our choice for the matrix H k . In the next proposition we
show that also the more cumbersome Condition 3 is satisfied.
Proposition 4.1 The sequence of matrices defined by (32) satisfies Condition 3.
Proof. Let sequences fx k g and fu k g converging to a stationary point of Problem (P)
be given. Let fQ k g be any sequence such that Q k 2 @ 2 Z(u k ; ffl) for every k. By Theorem
2.2 (c) we know that we can assume, without loss of generality, that eventually, for x k
sufficiently close to the point -
x, the matrix Q k has the following form, for some integer
where fae k g is a sequence converging to 0 and where, for each i and for each k, fi k
A. Since, for each i, A k
sufficiently large. We also recall that if A and B are two s \Theta r matrices we can write:
r
a
where a j and b j are the j-th columns of A and B respectively. By employing Taylor
expansion we can write
r- A k
rg A k
r- I 0
rg I 0
r- A k
rg A k
r- I 0
rg I 0
fflB @
r- D k
. Now, if we take into account the previous
formula and we set
a k
we can write
From this relation the thesis of the proposition readily follows by setting
5 Remarks and conclusions
We have presented a negative curvature line search algorithm for the minimization of a
nonlinear function subject to nonlinear inequality constraints. The main novel feature
of this method is that every limit point of the sequence it generates satisfies both the
KKT first and second order necessary optimality conditions. The main tools employed
to obtain this result are a continuously differentiable penalty function and some results
from the theory of LC 1 functions.
For sake of simplicity we did not include equality constraints in our analysis, but
they can be easily handled. All the results of this paper go through if one considers
also equality constraints, it is sufficient to use an analogous of the penalty function Z
where equality constraints are included, see [12].
Another point which deserves attention are the Assumtions A, B and C that we
employ. These assumptions are mainly dictated by the penalty function considered;
however they can be relaxed if a more sophisticated choice is made for the penalty
function. We chose to use the (relatively) simple function Z to concentrate on the
main issues related to the second order convergence; however, if the continuously differentiable
function proposed in [7] is employed instead of Z, we can improve on the
assumptions A, B and C. For example, Assumption A can be relaxed to: For any feasible
x, the gradients rg i (x), i 2 I 0 (x) are linearly independent. More significantly,
also Assumptions B and C can be considerably relaxed, but to illustrate this point we
should introduce some technical notation and we prefere to omit this here and to refer
the reader to [7] for more details. We only point out that Assumption C can be replaced
by natural and mild assumptions on the problem data which guarantee that the levels
sets of the penalty function are compact.



--R

Constrained Optimization and Lagrange Multiplier Methods.
A trust region algorithm for nonlinearly constrained optimization.
Optimization and Nonsmooth Analysis.
An interior trust region approach for nonlinear minimization subject to bounds.
A new trust-region algorithm for equality constrained optimization
Global convergence of a class of trust region algorithms for optimization with simple bounds.
A continuously differentiable exact penalty function for nonlinear programming problems with unbounded feasible set.
On the convergence theory of trust-region- based algorithms for equality-constrained optimization
"Algorithms for continuous optimization"
"System Modelling and Optimization"
A continuously differentiable exact penalty function for nonlinear programming problems with inequalty constraints.
Exact penalty functions in constrained optimiza- tion
Convergence to a second-order point for a trust-region algorithm with a nonmonotonic penalty parameter for constrained optimization
"La Sapienza"
Globally and quadratically convergent exact penalty based methods for inequality constrained problems.
Nonmonotone curvilinear line search methods for unconstrained optimization.
Newton methods for large-scale linear inequality constrained minimization
Generalized Hessian matrix and second-order optimality conditions for problems with C 1
New results on a continuously differentiable exact penalty function.
"La Sapienza"
A modification of Armijo's step-size rule for negative curva- ture
Nonlinear Programming: Theory


Newton's method with a model trust region modification.

--TR

--CTR
Giovanni Fasano , Massimo Roma, Iterative computation of negative curvature directions in large scale optimization, Computational Optimization and Applications, v.38 n.1, p.81-104, September 2007
Immanuel M. Bomze , Laura Palagi, Quartic Formulation of Standard Quadratic Optimization Problems, Journal of Global Optimization, v.32 n.2, p.181-205, June      2005
X. Q. Yang , X. X. Huang, Partially Strictly Monotone and Nonlinear Penalty Functions for Constrained Mathematical Programs, Computational Optimization and Applications, v.25 n.1-3, p.293-311
inequality constrained optimization;penalty function;KKT second order necessary conditions;LC 1 function;negative curvature direction