# Error Bounds and Finite Termination for Constrained Optimization Problems

Authors: Wenling Zhao; Daojin Song; Bingzhuang Liu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We present a global error bound for the projected gradient of nonconvex constrained optimization problems and a local error bound for the distance from a feasible solution to the optimal solution set of convex constrained optimization problems, by using the merit function involved in the sequential quadratic programming (SQP) method. For the solution sets (stationary points set andKKT points set) of nonconvex constrained optimization problems, we establish the definitions of generalized nondegeneration and generalized weak sharp minima. Based on the above, the necessary and sufficient conditions for a feasible solution of the nonconvex constrained optimization problems to terminate finitely at the two solutions are given, respectively. Accordingly, the results in this paper improve and popularize existing results known in the literature. Further, we utilize the global error bound for the projected gradient with the merit function being computed easily to describe these necessary and sufficient conditions.


---

## Body

## 1. Introduction

This paper is concerned with the following constrained optimization problem:(NP)min⁡{f(x)∣x∈S},
where f:Rn→R is a continuously differentiable function
(1)S={x∈Rn∣ci(x)≤0,i=1,2,…,m},
and ci:Rn→R, for i=1,2,…,m, are continuously differentiable convex functions.It is well known that SQP is an important method for solving the problem(NP). Its essential idea is to approximate the solutions of the problem (NP) by using the optimal solutions of a series of quadratic programming. Thesolutions here may be referred to as the stationary points, KKT points, or optimal solutions of the problem (NP).Suppose thatx∈S is a current iterate point of the problem (NP). Generally, during the iterative process of the SQP method, the next iterate point is generated by solving a subproblem as follows:
(SP(x))max⁡y∈S(x){-12〈B(x)(y-x),y-x〉〈∇f(x),x-y〉mmm-12〈B(x)(y-x),y-x〉},
where
(2)S(x)={y∈Rn∣〈∇ci(x),y-x〉≤0,i∈IS(x)},IS(x)={1≤i≤m∣ci(x)=0},∇f and ∇ci are gradients of f and ci, respectively, and B(x) is a symmetric positive definite matrix. The matrix B(x) is modified and selected again along with the iterative process.For the matrixB(x), we assume in this paper that there exist positive numbers λmin⁡ and λmax⁡ such that
(3)λmin⁡≤∥B(x)∥≤λmax⁡,∀x∈S,
where ∥·∥ stands for the Euclidean norm.Due to the convexity ofci(·) and IS(x)⊆{1,2,…,m}, it is easy to see that S⊆S(x) for all x∈S.Consider the following function:(4)ϕ(x)=max⁡y∈S(x){12〈∇f(x),x-y〉mmm-12〈B(x)(y-x),y-x〉},
which is referred to as a merit function.It is well known that the SQP method has wide and valid application for solving optimization problems (see [1–7]). However, the aim of this paper is not to propose more algorithms or computing skills for SQP methods but to study the global error bounds of projected gradient for nonconvex problems (NP) and the local error bounds of the distance from a feasible solution to the optimal solution set for convex problems (NP), with these error bounds by means of the merit function ϕ(x) being provided. This is one of the main contents of this paper.The theory of error bounds has attracted a lot of attention and many good results have been obtained. In particular, [8, 9] established many types of global error bounds for monotone affine variational inequality problems; [10–12] developed global S-type error bounds and global error bounds in Rn for strongly monotone variational inequality problems; [13, 14] obtained global S-type error bounds for generalized linear complementarity problems and monotone variational inequality problems. However, to the best of our knowledge, there is not much work concerning the error bounds in SQP methods. This motivates us to do this research.It should be noted that the merit functionϕ(x) considered here is different from the regular gap function (another kind of merit function) discussed in [10, 11, 15, 16], since ϕ(x) is generated over a polyhedral set obtaining S, rather than over S itself. The main advantage of this modification is that the KKT point of the problem (NP) is equivalent to ϕ(x)=0. In addition, the computation of ϕ(x) is easier than the regular gap function.Another main contribution of this paper is the finite termination of a feasible solution sequence; that is, the feasible solution sequence converges finitely to the solution sets (stationary points set andKKT point set) of problem (NP). This research has received considerable attention (see [17–25]). Among these, under the assumption that the solution set is weak sharp minima or nondegeneration, [20–25] studied the finite termination, respectively; [17–19] discussed, under the stronger condition, finite termination for some new efficient algorithms. It is worth mentioning that Burke and Ferris (see [20]), under the solution set satisfying the condition of weak sharp minima and other hypotheses for convex optimization problems, put forward the necessary and sufficient condition by which a feasible solution sequence converges finitely to the solution set (see [20, Theorem 4.7]). Afterwards, under the same conditions, [21] verified the conclusion in Pseudomonotone+ variational inequality problems. Recently, [25, Theorem 2] simplified the conditions of [20, Theorem 4.7] and confirmed that [20, Theorem 4.7] is efficacious only under the solution set satisfying the condition of weak sharp minima. However, for nonconvex optimization problems (NP), when its solution set satisfies the condition of weak sharp minima or nondegeneration, establishing the necessary and sufficient condition of a feasible solution sequence to converge finitely to the solution set is undoubtedly of great significance to solve this problem, but up to now we have not seen the research literature on this issue.In this paper, inspired by [25, Theorem 2], we solve this problem. We firstly extend the concepts of nondegeneration and weak sharp minima and, for the solution set of the problem (NP), establish the definitions of generalized nondegeneration and generalized weak sharp minima. Based on these two generalized concepts, we prove the following main results:(1) the necessary and sufficient condition of a feasible solution sequence to converge finitely to the solution set for the problem(NP) is that the corresponding sequence of projected gradient converges to zero.When the feasible solution setS of (NP) is general closed convex, the calculation of gradient projection is very difficult. However, the calculation of a merit function is much easier, and ϕ(x)=0 equivalent to x being a KKT point. Based on this feature of ϕ(x), we characterize the necessary and sufficient condition for the sequence terminating finitely to generalized a nondegeneration KKT point set by global error bound of projected gradient using merit function ϕ(x); that is,(2) for the problem(NP), the necessary and sufficient condition for the feasible solution sequence terminating finitely to generalized nondegeneration KKT point set is that the corresponding sequence of merit function converges to zero.For generalized weak sharp minima, we(3) suppose the stationary point set of the nonconvex optimization problem(NP) is convex; then the necessary and sufficient condition for the feasible solution sequence terminating finitely to a generalized weak sharp minima stationary point set is that the corresponding sequence of projected gradient converges to zero. As a straightforward corollary of the result, we obtain [16, Theorem 2]; therefore, we extend [20, Theorem 4.7] to nonconvex optimization problems.The rest of this paper is organized as follows. In Section2, we introduce some concepts and symbols which shall be used in the following discussion. In Section 3, we develop some basic properties of ϕ(x) and obtain a global error bound for the projected gradient and a local error bound for the distance from a feasible solution to the optimal solution set of problem (NP) by using ϕ(x). Finally, in Section 4, we give the necessary and sufficient condition for the feasible solution sequence terminating finitely to the sets of generalized nondegenerate and weak sharp minima, respectively, and give a number of meaningful conclusions.


## 2. Definitions and Notation

Let∥·∥ and 〈·,·〉 stand for the standard Euclidean norm and inner product in Rn, respectively. Denote by S¯,S^, and S* the stationary points set, KKT points set, and (global) optimal solutions set of problem (NP), respectively. In view of the assumption given in the matrix B(x), we know that the optimal solution of the subproblem (SP(x)) is unique; say y*(x). For simplicity, we denote this optimal solution by y*, and the confusion can be eliminated from the context.Given a nonempty subsetA of Rn, its closure set is denoted by clA and thepolar cone is defined as
(5)A∘={y∈Rn∣〈y,x〉≤0,∀x∈A}.
Thetangent cone of A at x∈clA is given by
(6)TA(x)={d∈Rn∣∃λk↓0,dk⟶d,such thatx+λkdk∈A,∀k}.
Thenormal cone of A at x∈A is defined as NA(x)=TA(x)∘. In particular, if A is convex, then the tangent and normal cone of A at x∈A take the following form, respectively:
(7)TA(x)=cl{λ(y-x)∣λ≥0,y∈S};NA(x)={y∈Rn∣〈y,z-x〉≤0,∀z∈A}.Theprojection of a point x∈Rn onto a closed set A is defined by
(8)P(x∣A)=argmin⁡{∥y-x∥∣y∈A},
and the distance from x∈Rn to A is given by
(9)dist⁡(x,A)=∥x-P(x∣A)∥.
Fixed vector a∈Rn and a nonnegative scalar t, we use notation a+tB to mean that {x∈Rn∣∥x-a∥≤t}, where B stands for the unit ball in Rn.A mapping∇Af(·):Rn→Rn is said to be aprojected gradient of f(·) with respect to a set A if
(10)∇Af(x)=P(-∇f(x)∣TA(x)),∀x∈A.
Clearly, x∈S is a stationary point of (NP) if and only if -∇f(x)∈NS(x) or, equivalently, ∇Sf(x)=0. Since ci(x) is convex, it is easy to see that S^⊆S¯ and S*⊆S¯. Clearly, we have S*=S¯ for convex optimization problem.For the solution setS* of optimization problem (NP), Burke and Ferris [20] extended the concept of strong singleton minima point to weak sharp minima, which can be used to deal with the case where the solution set is a nonsingleton point set. More precisely, a set S* is said to beweak sharp minima if there exists a positive α* which depends only on f, S*, and S, such that
(11)f(x)-f(x*)≥α*dist⁡(x,S*),∀x*∈S*,x∈S.We call that a sequence{xk}terminates finitely to A if there exists k0 such that xk∈A for all k≥k0. Given α∈R, thelevel set of ϕ(x) is defined as
(12)Lϕ(α)={x∈S∣ϕ(x)≤α}.


## 3. Error Bound

### 3.1. Properties ofϕ(x)

This subsection mainly deals with the basic properties of the merit functionϕ(x). From the definition of subproblem (SP(x)), we know that ϕ(x)≥0 for all x∈S. Since S(x) is polyhedral, we have the following.Lemma 1.
Givenx∈S, a point y*∈S(x) is the unique solution of the subproblem (SP(x)) if and only if there exist KKT multipliers λi*≥0 for i∈IS(x) such that
(13)∇f(x)+B(x)(y*-x)+∑i∈IS(x)‍λi*∇ci(x)=0,(14)λi*〈∇ci(x),y*-x〉=0,∀i∈IS(x),
where, for simplicity, one uses λi* to denote KKT multipliers λi*(x) associated with the unique optimal solution to the problem (SP(x)).Lemma 2.
For anyx∈S, one has
(15)ϕ(x)=12〈B(x)(y*-x),y*-x〉.Proof.
Left-multiplying the two sides of (13) by (x-y*)T and using (14), we have
(16)〈∇f(x),x-y*〉-〈B(x)(y*-x),y*-x〉=0.
By the definition of ϕ(x), we obtain
(17)ϕ(x)=〈∇f(x),x-y*〉-12〈B(x)(y*-x),y*-x〉=12〈B(x)(y*-x),y*-x〉.Lemma 3.
For anyx∈S, one has
(18)ϕ(x)≥12λmin⁡∥y*-x∥2.With the preparation of these lemmas, we obtain the following result.Theorem 4.
The following conclusions are equivalent:(1)
xis a KKT point of the problem (NP);(2)
x∈S and ϕ(x)=0;(3)
x∈S and x=y*(x).From conclusions (1) and (2) of Theorem4 and the nonnegativity of ϕ(x), it is immediate to verify the following result.Corollary 5.
Suppose that theKKT point of (NP) is nonempty. Then, x* is a KKT point of problem (NP) if and only if x* is an optimal solution of problem
(19)min⁡{ϕ(x)∣x∈S}.
In this case, ϕ(x*)=0 and x*=y*(x*).Lemma 6.
For anyx∈S and z∈S(x), one has
(20)〈∇f(x)+B(x)(y*-x),z-y*〉≥0.Proof.
Clearly, the optimal solutions of problem(SP(x)) is the same to that of the following programming problem:
(21)min⁡y∈S(x){〈∇f(x),y-x〉+12〈B(x)(y-x),y-x〉}.
Since this is a convex programming, its optimal solutions must be stationary points as well; that is,
(22)〈∇f(x)+B(x)(y*-x),z-y*〉≥0.


### 3.2. Error Bound

The following result provides an estimation for∥∇S(x)f(x)∥.Theorem 7.
For anyx∈S, one has
(23)β2ϕ(x)1/2≤∥∇S(x)f(x)∥≤β1ϕ(x)1/2,
where β1=λmax⁡(2/λmin⁡)1/2 and β2=(λmin⁡/2)1/2.Proof.
SinceS(x) is a polyhedral set, it is easy to see that the tangent cone of S(x) at x takes the form as follows:
(24)TS(x)(x)={d∈Rn∣〈∇ci(x),d〉≤0,i∈IS(x)(x)}={d∈Rn∣〈∇ci(x),d〉≤0,i∈IS(x)},
where we have used the fact that IS(x)=IS(x)(x). Take d∈TS(x)(x) with ∥d∥≤1. Left-multiplying both sides of (13) by dT and using Lemma 3, we obtain
(25)〈-∇f(x),d〉=〈B(x)(y*-x),d〉+∑i∈IS(x)‍λi*〈∇ci(x),d〉≤〈B(x)(y*-x),d〉≤λmax⁡∥y*-x∥≤λmax⁡(2λmin⁡)1/2ϕ(x)1/2.
In other words, we obtain(26)〈-∇f(x),d〉≤β1ϕ(x)1/2,∀d∈TS(x)(x)with∥d∥≤1,
where β1=λmax⁡(2/λmin⁡)1/2. This, together with the properties of projected gradient by Calamai and Moré [26], implies that
(27)∥∇S(x)f(x)∥=max⁡{〈-∇f(x),d〉∣d∈TS(x)(x),∥d∥≤1}≤β1ϕ(x)1/2.
Thus, the right inequality is proved.
On the other hand, Lemma3 implies that
(28)(λmin⁡2)1/2∥y*-x∥≤ϕ(x)1/2,
from which we obtain
(29)(λmin⁡2)1/2ϕ(x)1/2≤1∥y*-x∥ϕ(x).
Let β2=(λmin⁡/2)1/2. Note that
(30)y*-x∥y*-x∥∈TS(x)(x),∥y*-x∥y*-x∥∥=1.
From (29) and (30), we obtain
(31)β2ϕ(x)1/2≤ϕ(x)∥y*-x∥=〈-∇f(x),y*-x∥y*-x∥〉-12〈B(x)(y*-x),y*-x∥y*-x∥〉≤〈-∇f(x),y*-x∥y*-x∥〉≤max⁡⁡{〈-∇f(x),d〉∣d∈TS(x)(x),∥d∥≤1}=∥∇S(x)f(x)∥.
So, the left inequality is valid.The following result can be obtained by Theorems4 and 7.Corollary 8.
The following conclusions are equivalent:(1)
x is a KKT point of the problem (NP);(2)
x∈S and ∇S(x)f(x)=0.A global error bound for∇Sf(x) is given below.Theorem 9.
For anyx∈S, one has
(32)∥∇Sf(x)∥≤β1ϕ(x)1/2.
If S is polyhedral, then
(33)β2ϕ(x)1/2≤∥∇Sf(x)∥≤β1ϕ(x)1/2,
where β1=λmax⁡(2/λmin⁡)1/2 and β2=(λmin⁡/2)1/2.Proof.
SinceS⊆S(x) and x∈S, it follows from the definition of tangent cone that
(34)TS(x)⊆TS(x)(x).
Taking into account of the properties of the projected gradient and Theorem 7, we obtain
(35)∥∇Sf(x)∥=max⁡{〈-∇f(x),d〉∣d∈TS(x),∥d∥≤1}≤max⁡{〈-∇f(x),d〉∣d∈TS(x)(x),∥d∥≤1}=∥∇S(x)f(x)∥≤β1ϕ(x)1/2.
If S is polyhedral, then TS(x)=TS(x)(x); that is, ∇Sf(x)=∇S(x)f(x). Thus, the result is established by invoking Theorem 7.Now, we consider the case where the problem(NP) is convex; that is, the functions involved in (NP) are all convex. Obviously, in this case, S* is a closed convex set. Under condition (11), we use ϕ(x) to give a local error bound for dist⁡(x,S*).Theorem 10.
Suppose that(NP) is a convex programming. If S* is a set of weak sharp minima; that is, (11) holds, then there exist positive constants α, β, and γ such that
(36)βdist⁡(x,S*)≤γϕ(x),∀x∈Lϕ(α).Proof.
Given anyx∈S, let z=P(x∣S*). Taking into account Lemma 6, we have
(37)〈∇f(x),P(x∣S*)-y*〉≥〈B(x)(y*-x),y*-P(x∣S*)〉.
By (11), (37), the convexity of f(·), and the assumption of B(x), we have
(38)ϕ(x)=〈∇f(x),x-y*〉-12〈B(x)(y*-x),y*-x〉≥〈∇f(x),x-y*〉-12λmax⁡∥y*-x∥2=〈∇f(x),x-P(x∣S*)〉+〈∇f(x),P(x∣S*)-y*〉-12λmax⁡∥y*-x∥2≥f(x)-f(P(x∣S*))+〈B(x)(y*-x),y*-P(x∣S*)〉-12λmax⁡∥y*-x∥2≥α*dist⁡(x,S*)-λmax⁡∥y*-x∥·∥y*-P(x∣S*)∥-12λmax⁡∥y*-x∥2≥α*dist⁡(x,S*)-λmax⁡∥y*-x∥dist⁡(x,S*)-32λmax⁡∥y*-x∥2.
According to the last inequality above and Lemma 3,
(39)ϕ(x)≥α*dist⁡(x,S*)-λmax⁡∥y*-x∥dist⁡(x,S*)-32λmax⁡∥y*-x∥2≥α*dist⁡(x,S*)-λmax⁡(2λmin⁡)1/2ϕ(x)1/2dist⁡(x,S*)-3λmax⁡λmin⁡ϕ(x),
which in turn implies that
(40)[α*-λmax⁡(2λmin⁡)1/2ϕ(x)1/2]dist⁡(x,S*)mml≤(3λmax⁡λmin⁡+1)ϕ(x).
Let α1/2=(α*/2)[λmax⁡(2/λmin⁡)1/2]-1, β=(1/2)α* and γ=3λmax⁡/λmin⁡+1. When x∈Lϕ(α), it follows from (40) that
(41)βdist⁡(x,S*)=[α*-(λmax⁡(2λmin⁡)1/2)α1/2]dist⁡(x,S*)≤[α*-λmax⁡(2λmin⁡)1/2ϕ(x)1/2]dist⁡(x,S*)≤γϕ(x).Corollary 11.
Suppose that(NP) is a convex programming. If (11) holds and {xk} satisfies lim⁡k→∞ϕ(xk)=0, then
(42)lim⁡k→∞dist⁡(xk,S*)=0.Proof.
For the positiveα given in Theorem 10, it follows from lim⁡k→∞ϕ(xk)=0 that there exists k0 such that ϕ(xk)≤α for all k≥k0; that is, xk∈Lϕ(α). The result then follows readily from Theorem 10.


## 3.1. Properties ofϕ(x)

This subsection mainly deals with the basic properties of the merit functionϕ(x). From the definition of subproblem (SP(x)), we know that ϕ(x)≥0 for all x∈S. Since S(x) is polyhedral, we have the following.Lemma 1.
Givenx∈S, a point y*∈S(x) is the unique solution of the subproblem (SP(x)) if and only if there exist KKT multipliers λi*≥0 for i∈IS(x) such that
(13)∇f(x)+B(x)(y*-x)+∑i∈IS(x)‍λi*∇ci(x)=0,(14)λi*〈∇ci(x),y*-x〉=0,∀i∈IS(x),
where, for simplicity, one uses λi* to denote KKT multipliers λi*(x) associated with the unique optimal solution to the problem (SP(x)).Lemma 2.
For anyx∈S, one has
(15)ϕ(x)=12〈B(x)(y*-x),y*-x〉.Proof.
Left-multiplying the two sides of (13) by (x-y*)T and using (14), we have
(16)〈∇f(x),x-y*〉-〈B(x)(y*-x),y*-x〉=0.
By the definition of ϕ(x), we obtain
(17)ϕ(x)=〈∇f(x),x-y*〉-12〈B(x)(y*-x),y*-x〉=12〈B(x)(y*-x),y*-x〉.Lemma 3.
For anyx∈S, one has
(18)ϕ(x)≥12λmin⁡∥y*-x∥2.With the preparation of these lemmas, we obtain the following result.Theorem 4.
The following conclusions are equivalent:(1)
xis a KKT point of the problem (NP);(2)
x∈S and ϕ(x)=0;(3)
x∈S and x=y*(x).From conclusions (1) and (2) of Theorem4 and the nonnegativity of ϕ(x), it is immediate to verify the following result.Corollary 5.
Suppose that theKKT point of (NP) is nonempty. Then, x* is a KKT point of problem (NP) if and only if x* is an optimal solution of problem
(19)min⁡{ϕ(x)∣x∈S}.
In this case, ϕ(x*)=0 and x*=y*(x*).Lemma 6.
For anyx∈S and z∈S(x), one has
(20)〈∇f(x)+B(x)(y*-x),z-y*〉≥0.Proof.
Clearly, the optimal solutions of problem(SP(x)) is the same to that of the following programming problem:
(21)min⁡y∈S(x){〈∇f(x),y-x〉+12〈B(x)(y-x),y-x〉}.
Since this is a convex programming, its optimal solutions must be stationary points as well; that is,
(22)〈∇f(x)+B(x)(y*-x),z-y*〉≥0.


## 3.2. Error Bound

The following result provides an estimation for∥∇S(x)f(x)∥.Theorem 7.
For anyx∈S, one has
(23)β2ϕ(x)1/2≤∥∇S(x)f(x)∥≤β1ϕ(x)1/2,
where β1=λmax⁡(2/λmin⁡)1/2 and β2=(λmin⁡/2)1/2.Proof.
SinceS(x) is a polyhedral set, it is easy to see that the tangent cone of S(x) at x takes the form as follows:
(24)TS(x)(x)={d∈Rn∣〈∇ci(x),d〉≤0,i∈IS(x)(x)}={d∈Rn∣〈∇ci(x),d〉≤0,i∈IS(x)},
where we have used the fact that IS(x)=IS(x)(x). Take d∈TS(x)(x) with ∥d∥≤1. Left-multiplying both sides of (13) by dT and using Lemma 3, we obtain
(25)〈-∇f(x),d〉=〈B(x)(y*-x),d〉+∑i∈IS(x)‍λi*〈∇ci(x),d〉≤〈B(x)(y*-x),d〉≤λmax⁡∥y*-x∥≤λmax⁡(2λmin⁡)1/2ϕ(x)1/2.
In other words, we obtain(26)〈-∇f(x),d〉≤β1ϕ(x)1/2,∀d∈TS(x)(x)with∥d∥≤1,
where β1=λmax⁡(2/λmin⁡)1/2. This, together with the properties of projected gradient by Calamai and Moré [26], implies that
(27)∥∇S(x)f(x)∥=max⁡{〈-∇f(x),d〉∣d∈TS(x)(x),∥d∥≤1}≤β1ϕ(x)1/2.
Thus, the right inequality is proved.
On the other hand, Lemma3 implies that
(28)(λmin⁡2)1/2∥y*-x∥≤ϕ(x)1/2,
from which we obtain
(29)(λmin⁡2)1/2ϕ(x)1/2≤1∥y*-x∥ϕ(x).
Let β2=(λmin⁡/2)1/2. Note that
(30)y*-x∥y*-x∥∈TS(x)(x),∥y*-x∥y*-x∥∥=1.
From (29) and (30), we obtain
(31)β2ϕ(x)1/2≤ϕ(x)∥y*-x∥=〈-∇f(x),y*-x∥y*-x∥〉-12〈B(x)(y*-x),y*-x∥y*-x∥〉≤〈-∇f(x),y*-x∥y*-x∥〉≤max⁡⁡{〈-∇f(x),d〉∣d∈TS(x)(x),∥d∥≤1}=∥∇S(x)f(x)∥.
So, the left inequality is valid.The following result can be obtained by Theorems4 and 7.Corollary 8.
The following conclusions are equivalent:(1)
x is a KKT point of the problem (NP);(2)
x∈S and ∇S(x)f(x)=0.A global error bound for∇Sf(x) is given below.Theorem 9.
For anyx∈S, one has
(32)∥∇Sf(x)∥≤β1ϕ(x)1/2.
If S is polyhedral, then
(33)β2ϕ(x)1/2≤∥∇Sf(x)∥≤β1ϕ(x)1/2,
where β1=λmax⁡(2/λmin⁡)1/2 and β2=(λmin⁡/2)1/2.Proof.
SinceS⊆S(x) and x∈S, it follows from the definition of tangent cone that
(34)TS(x)⊆TS(x)(x).
Taking into account of the properties of the projected gradient and Theorem 7, we obtain
(35)∥∇Sf(x)∥=max⁡{〈-∇f(x),d〉∣d∈TS(x),∥d∥≤1}≤max⁡{〈-∇f(x),d〉∣d∈TS(x)(x),∥d∥≤1}=∥∇S(x)f(x)∥≤β1ϕ(x)1/2.
If S is polyhedral, then TS(x)=TS(x)(x); that is, ∇Sf(x)=∇S(x)f(x). Thus, the result is established by invoking Theorem 7.Now, we consider the case where the problem(NP) is convex; that is, the functions involved in (NP) are all convex. Obviously, in this case, S* is a closed convex set. Under condition (11), we use ϕ(x) to give a local error bound for dist⁡(x,S*).Theorem 10.
Suppose that(NP) is a convex programming. If S* is a set of weak sharp minima; that is, (11) holds, then there exist positive constants α, β, and γ such that
(36)βdist⁡(x,S*)≤γϕ(x),∀x∈Lϕ(α).Proof.
Given anyx∈S, let z=P(x∣S*). Taking into account Lemma 6, we have
(37)〈∇f(x),P(x∣S*)-y*〉≥〈B(x)(y*-x),y*-P(x∣S*)〉.
By (11), (37), the convexity of f(·), and the assumption of B(x), we have
(38)ϕ(x)=〈∇f(x),x-y*〉-12〈B(x)(y*-x),y*-x〉≥〈∇f(x),x-y*〉-12λmax⁡∥y*-x∥2=〈∇f(x),x-P(x∣S*)〉+〈∇f(x),P(x∣S*)-y*〉-12λmax⁡∥y*-x∥2≥f(x)-f(P(x∣S*))+〈B(x)(y*-x),y*-P(x∣S*)〉-12λmax⁡∥y*-x∥2≥α*dist⁡(x,S*)-λmax⁡∥y*-x∥·∥y*-P(x∣S*)∥-12λmax⁡∥y*-x∥2≥α*dist⁡(x,S*)-λmax⁡∥y*-x∥dist⁡(x,S*)-32λmax⁡∥y*-x∥2.
According to the last inequality above and Lemma 3,
(39)ϕ(x)≥α*dist⁡(x,S*)-λmax⁡∥y*-x∥dist⁡(x,S*)-32λmax⁡∥y*-x∥2≥α*dist⁡(x,S*)-λmax⁡(2λmin⁡)1/2ϕ(x)1/2dist⁡(x,S*)-3λmax⁡λmin⁡ϕ(x),
which in turn implies that
(40)[α*-λmax⁡(2λmin⁡)1/2ϕ(x)1/2]dist⁡(x,S*)mml≤(3λmax⁡λmin⁡+1)ϕ(x).
Let α1/2=(α*/2)[λmax⁡(2/λmin⁡)1/2]-1, β=(1/2)α* and γ=3λmax⁡/λmin⁡+1. When x∈Lϕ(α), it follows from (40) that
(41)βdist⁡(x,S*)=[α*-(λmax⁡(2λmin⁡)1/2)α1/2]dist⁡(x,S*)≤[α*-λmax⁡(2λmin⁡)1/2ϕ(x)1/2]dist⁡(x,S*)≤γϕ(x).Corollary 11.
Suppose that(NP) is a convex programming. If (11) holds and {xk} satisfies lim⁡k→∞ϕ(xk)=0, then
(42)lim⁡k→∞dist⁡(xk,S*)=0.Proof.
For the positiveα given in Theorem 10, it follows from lim⁡k→∞ϕ(xk)=0 that there exists k0 such that ϕ(xk)≤α for all k≥k0; that is, xk∈Lϕ(α). The result then follows readily from Theorem 10.


## 4. Finite Termination

In this section, we will study the necessary and sufficient conditions for the feasible solution sequence of nonconvex optimization problems(NP) terminating finitely to their solution sets (stationary points set and KKT points set).


### 4.1. Generalized Nondegenerate Set

First we introduce the concept of nondegenerate set.Definition 12.
LetS∘⊂S; if
(43)-∇f(x)∈int⁡NS(x),∀x∈S∘,S∘ is said to be a nondegenerate set.Now, we further extend the definition of the nondegeneration. LetN⊆{1,2,…} be an infinite subset.Definition 13.
LetS∘⊂S and {xk}⊂Rn. S∘ is said to be a generalized nondegenerate set for {xk}, if, for every subsequence {xk}k∈N, there exists xN∈S∘ and PN∈Rn such that(i)
-PN∈int⁡NS(xN);(ii)
lim⁡sup⁡k∈N,k→∞(1/∥xk-xN∥)〈∇f(xk)-PN,xk-xN〉≥0.It is easy to verify that the following several propositions expressed are special cases of generalized nondegenerate set.Proposition 14.
LetS∘⊂S be a nondegenerate set, and let {xk}⊂Rn be a bounded sequence, with its every accumulation point x*∈S∘. Then, S∘ is a generalized nondegenerate set for {xk}.Proposition 15.
LetS∘⊂S,{xk}⊂Rn, and {∇f(xk)} be bounded. If, for every accumulation point ∇f* of {∇f(xk)}, there exists x*∈S∘ such that
(44)-∇f*∈int⁡NS(x*).
then S∘ is a generalized nondegenerate set for {xk}.From [20, Theorem 3.1], we know that gradient ∇f(·) is always constant vector in the optimal solution set of a convex optimization problems. So, according to the monotonicity of ∇f(·), we get the following.Proposition 16.
LetS*, the optimal solution set of a convex optimization problems (NP), be a nondegenerate set. Then, for any {xk}⊂Rn, S* is a generalized nondegenerate set for {xk}.Here, we give the necessary and sufficient condition for the feasible solution sequence of the nonconvex optimization problems(NP) terminating finitely to its generalized nondegenerate solution set.Theorem 17.
For the nonconvex optimization problem(NP), let {xk}⊂S, the solution set (S¯ or S^), be a generalized nondegenerate set. Then, {xk} terminates finitely to solution set, if and only if
(45)lim⁡k→∞∇Sf(xk)=0.Proof.
Consider the following.
Necessity. If xk∈S¯, by the definition of stationary point, we have ∇Sf(xk)=0. If xk⊆S^, for S^⊂S¯, we also have ∇Sf(xk)=0.
Sufficiency. We only give the proof for S¯. The proof for S^ is the same as that for S¯. Suppose (45) holds. We prove the result by contradiction. Suppose on the contrary that there exists an infinite subsequence N⊆{1,2,…} such that
(46)xk∉S¯,∀k∈N.
Since S¯ is a generalized nondegenerate for {xk}, so, according to Definition 13, for subsequence {xk}k∈N,∃xN∈S¯ and PN∈Rn, such that
(47)-PN∈int⁡NS(xN),(48)lim⁡sup⁡k∈N,k→∞1∥xk-xN∥〈∇f(xk)-PN,xk-xN〉≥0.
From (47), we know that ∃α>0 such that
(49)-PN+αB⊂NS(xN),
where B stands for the unit ball in Rn. By (49), for ∀g∈TS(xN),g≠0, we have
(50)〈-PN+αg∥g∥,g〉≤0;
that is,
(51)α≤〈PN,g∥g∥〉.
Let gk=xk-xN(∀k∈N), and by (46) we have gk≠0. Since S is convex, we have
(52)gk∈TS(xN),-gk∈TS(xk)(∀k∈N).
Then, according to (51), (52), and the property of gradient projection, we have for all k∈N(53)α≤〈PN,gk∥gk∥〉=〈-PN,-gk∥gk∥〉=〈-∇f(xk),-gk∥gk∥〉-〈∇f(xk)-PN,gk∥gk∥〉≤max⁡⁡{〈-∇f(xk),d〉∣d∈TS(xk),∥d∥≤1}-〈∇f(xk)-PN,gk∥gk∥〉=∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉.
It follows that
(54)α≤∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉,(∀k∈N).
Since gk=xk-xN, according to (45) (48), we have
(55)α≤lim⁡inf⁡k∈N,k→∞{∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉}≤-lim⁡sup⁡k∈N,k→∞〈∇f(xk)-PN,gk∥gk∥〉≤0,
which is a contradiction with α>0.Corollary 18.
For the the nonconvex optimization problems(NP), let {xk}⊂S be a bounded sequence and let S¯ be a nondegenerate set. Then, {xk} terminates finitely to S¯, if and only if (45) holds.Proof.
The Necessity is obvious. We only need to prove the Sufficiency. Suppose (45) holds; that is,
(56)lim⁡k→∞∇Sf(xk)=0.
According to the lower semicontinuity of ∇Sf(·) and the boundedness of {xk}, we have that every accumulation point x* of {xk} is in S¯. Therefore, from Proposition 14, we know that S¯ is a generalized nondegenerate set for {xk}. Then, according to (45), by Theorem 17, sufficiency holds.Corollary 19.
For the nonconvex optimization problem(NP), let {xk}⊂S, and {∇f(xk)} is a bounded sequence, and, for each of its accumulation point ∇f*, there exists x*∈S¯ (or x*∈S^) such that
(57)-∇f*∈int⁡NS(x*).
Then, {xk} terminates finitely to the solution set S¯ (or S^) if and only if (45) holds.Proof.
By Proposition15 and Theorem 17, we can get it.Corollary 20.
For the nonconvex optimization problem(NP), let {xk}⊂S, and S¯ is a nondegenerate set. Then, {xk} terminates finitely to S*, if and only if (45) holds.Proof.
Here, we haveS*=S¯. Then, by Proposition 16 and Theorem 17, we can get it.In the following, we will use the global error bounds of projected gradient, which resulted from last section, to characterize the necessary and sufficient condition of feasible solution sequence terminating finitely by the merit functionϕ(·) which is easy to calculate.Theorem 21.
For the nonconvex optimization problem(NP), {xk}⊂S, and KKT points set S^ is a generalized nondegenerate set for {xk}. Then, {xk} terminates finitely to S^, if and only if
(58)lim⁡k→∞ϕ(xk)=0.Proof.
Consider the following.
Necessity. If xk∈S^, then, according to Theorem 4, we have ϕ(xk)=0.
Sufficiency. Suppose (58) holds, and according to Theorem 9, we have lim⁡k→∞∇Sf(xk)=0; that is, (45) holds. From Theorem 17, we get the sufficiency.Lemma 22.
For the nonconvex optimization problem(NP), let {xk}⊂S, and (58) holds. If x* is an accumulation point of {xk} satisfying the Mangasarian-Fromovitz constraint qualification, then x* is a KKT point of (NP).Proof.
Without loss of generality, we assume that(59)lim⁡k→∞xk=x*.
Then, there exists an index set IS⊂{1,2,…,m} and an infinite subsequence N⊆{1,2,…} such that
(60)IS(xk)=IS⊆IS(x*),∀k∈N.
The tangent cone of S(x) at x∈S is
(61)TS(x)(x)={d∈Rn∣〈∇ci(x),d〉≤0,i∈IS(x)},
and its normal cone is
(62)NS(x)(x)={∑i∈IS(x)‍αi∇ci(x)∣αi≥0,i∈IS(x)}.
Therefore, by (60) and (62), when k∈N, there exists λi(k)≥0 for i∈IS such that
(63)P(-∇f(xk)∣NS(xk)(xk))=∑i∈IS‍λi(k)∇ci(xk),
from which, and using the orthogonal projection decomposition, for all k∈N, we get
(64)-∇f(xk)=P(-∇f(xk)∣TS(xk)(xk))+P(-∇f(xk)∣NS(xk)(xk))=∇S(xk)f(xk)+∑i∈IS‍λi(k)∇ci(xk).
We now show that the sequence{∑i∈ISλi(k)}k∈N must be bounded. Suppose on the contrary that
(65)lim⁡k∈N,k→∞∑i∈IS‍λi(k)=+∞,
Let us suppose
(66)lim⁡k∈N,k→∞λi(k)∑i∈ISλi(k)=αi*,i∈IS.
Dividing the two sides of (64) by ∑i∈ISλi(k) and taking limit, due to (65) and (66), with the continuity of ∇ci(·), we obtain
(67)∑i∈IS‍αi*∇ci(x*)=0,
and, according to (66), we have
(68)∑i∈IS‍αi*=1,αi*≥0,i∈IS.
According to the assumption,x* satisfies the M-F constraint qualification; that is, there is h∈Rn such that
(69)〈∇ci(x*),h〉<0,∀i∈IS(x*).
Since IS⊆IS(x*), so (69), (67), and (68) are contradictory. So we assume that lim⁡k∈N,k→∞λi(k)=λi* for i∈IS. By (58) and Theorem 7, we know that lim⁡k→∞∇S(xk)f(xk)=0. Then, by (64) and the continuity of ∇f(·), we obtain
(70)-∇f(x*)=lim⁡k∈N,k→∞-∇f(xk)=lim⁡k∈N,k→∞∇S(xk)f(xk)+lim⁡k∈N,k→∞∑i∈IS‍λi(k)∇ci(xk)=∑i∈IS‍λi*∇ci(x*),
which means that x* is a KKT point of the (NP).Corollary 23.
For the nonconvex optimization problem(NP), suppose S^ is a nondegenerate set, {xk}⊂S is bounded, and each of its accumulation point x* is satisfying the Mangasarian-Fromovitz constraint qualification. Then, {xk} terminates finitely to S^ if and only if the sequence satisfies (58).Proof.
According to Lemma22 and Proposition 14, by Theorem 21 we can get it.Corollary 24.
For the nonconvex optimization problem(NP), suppose {xk}⊂S, and {∇f(xk)} is a bounded sequence, and, for each of its accumulation point ∇f*, there exists x*∈S^ such that
(71)-∇f*∈int⁡NS(x*).
Then, {xk} terminates finitely to S^ if and only if the sequence satisfies (58).Proof.
According to Proposition15, by Theorem 21 we can get it.


### 4.2. Generalized Weak Sharp Minima

In [20], Burke and Ferris gave an equivalent condition for weak sharp minima for a convex optimization problem; that is, the optimal solution set S* of the convex optimization problem is a set of weak sharp minima if and only if for every x¯∈S*(72)-∇f(x¯)∈int⁡⋂x∈S*‍[TS(x)∩NS*(x)]∘.Generally speaking, for a nonconvex optimization problem, (72) is only a necessary condition for weak sharp minima condition (11); that is, (72) is weaker than (11). However, considering its importance in analyzing the finite termination of algorithms, some previous studies, for example, [21, 22], directly use (72) as the definition of weak sharp minima for the optimal solution set. In this paper, we will use the weaker condition (72) to define the set of weak sharp minima.Definition 25.
LetS∘⊂S, and S∘ is said to be a set of weak sharp minima if and only if (72) holds.Now, we further extend the definition of weak sharp minima as follows.Definition 26.
LetS∘⊂S and {xk}⊂Rn. S∘ is said to be a set of generalized weak sharp minima for {xk}, if, for every subsequence {xk}k∈N, there exists PN∈Rn such that(i)
-PN∈int⁡⋂x∈S∘‍[TS(x)∩NS∘(x)]∘;(ii)
limsup⁡k∈N,k→∞(1/∥xk-P(xk∣S∘)∥)〈∇f(xk)-PN,xk-P(xk∣S∘)〉≥0.With the same as the set of generalized nondegeneration, it is easy to verify that the following several propositions expressed are special cases of generalized weak sharp minima.Proposition 27.
LetS∘⊂S be a set of weak sharp minima, and let {xk}⊂Rn be a bounded sequence, with its every accumulation point x*∈S∘. Then, S∘ is a set of generalized weak sharp minima for {xk}.Proposition 28.
LetS∘⊂S,{xk}⊂Rn, and {∇f(xk)} be bounded. If, for every accumulation point ∇f* of {∇f(xk)},
(73)-∇f*∈int⋂x∈S∘‍[TS(x)∩NS∘(x)]∘,
then, S∘ is a set of generalized weak sharp minima for {xk}.Proposition 29.
Let the optimal solution setS* of a convex optimization problem (NP) be a set of weak sharp minima. Then, for any {xk}⊂Rn, S* is a set of generalized weak sharp minima for {xk}.Here, we give the necessary and sufficient condition for the feasible solution sequence of a nonconvex optimization problem(NP) terminating finitely to its solution set of generalized weak sharp minima.Theorem 30.
For the nonconvex optimization problem(NP), let {xk}⊂S, and its stationary point set S¯ is convex and is a set of generalized weak sharp minima for {xk}. Then, {xk} terminates finitely to S¯, if and only if (45) holds.Proof.
Consider the following.
Necessity. If xk∈S¯, by the definition of stationary point, we have ∇Sf(xk)=0.
Sufficiency. Suppose (45) holds. We prove the result by contradiction. Suppose on the contrary that there exists an infinite subsequence N⊆{1,2,…} such that
(74)xk∉S¯,∀k∈N.
So, according to Definition 26 (i), we know that, for subsequence {xk}k∈N,∃PN∈Rn and α>0, such that, for ∀x∈S¯, we have
(75)-PN+αB⊂[TS(x)∩NS¯(x)]∘.
By (74), for ∀g∈TS(x)∩NS¯(x) and ∀x∈S¯, we have
(76)α≤〈PN,g∥g∥〉.
Let zk=P(xk∣S¯) and gk=xk-zk. By (74), we have ∀k∈N, gk≠0. Since S is convex, we have
(77)gk∈TS(zk),-gk∈TS(xk).
Since S¯ is convex, according to the property of projection and the definition of NS¯(·), we have gk∈NS¯(zk), so by (77), we have
(78)gk∈TS(zk)∩NS¯(zk).
Then, according to (76), (77), (78), and the property of gradient projection, we have
(79)α≤〈PN,gk∥gk∥〉=〈-PN,-gk∥gk∥〉=〈-∇f(xk),-gk∥gk∥〉-〈∇f(xk)-PN,gk∥gk∥〉≤max⁡⁡{〈-∇f(xk),d〉∣d∈TS(xk),∥d∥≤1}-〈∇f(xk)-PN,gk∥gk∥〉=∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉.
It follows that
(80)α≤∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉.
Since gk=xk-P(xk∣S¯), according to (45) and Definition 26 (ii), we have
(81)α≤lim⁡inf⁡k∈N,k→∞{∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉}≤-lim⁡sup⁡k∈N,k→∞〈∇f(xk)-PN,gk∥gk∥〉≤0,
which is a contradiction with α>0.With the same as generalized nondegeneration, according to Propositions27, 28, and 29 and by Theorem 30, we can get the following corollaries.Corollary 31.
For the nonconvex optimization problem(NP), suppose S¯ is convex and weak sharp minima, and {xk}⊂S is an bounded sequence. Then, {xk} terminates finitely to S¯, if and only if (45) holds.Corollary 32.
For the nonconvex optimization problem(NP), suppose S¯ is convex and {xk}⊂S; {∇f(xk)} is a bounded sequence, and for each of its accumulation point ∇f*, we have
(82)-∇f*∈int⋂x∈S¯‍[TS(x)∩NS¯(x)]∘.
Then, {xk} terminates finitely to S¯, if and only if (45) holds.Corollary 33.
For the nonconvex optimization problem(NP), the optimal solution set S* is weak sharp minima, {xk}⊂S. Then, {xk} terminates finitely to S*, if and only if (45) holds.Notation.Corollary 33 is [25, Theorem 2], which simplifies Theorem 4.7 in Burke and Ferris [20] (which removes two assumptions of [20, Theorem 4.7]; that is, lim⁡k→∞dist⁡(xk,S*)=0 and ∇f(·) is uniformly continuous on an open set containing {xk}); therefore, our Theorem 30 extends [20, Theorem 4.7] to nonconvex optimization problems.


## 4.1. Generalized Nondegenerate Set

First we introduce the concept of nondegenerate set.Definition 12.
LetS∘⊂S; if
(43)-∇f(x)∈int⁡NS(x),∀x∈S∘,S∘ is said to be a nondegenerate set.Now, we further extend the definition of the nondegeneration. LetN⊆{1,2,…} be an infinite subset.Definition 13.
LetS∘⊂S and {xk}⊂Rn. S∘ is said to be a generalized nondegenerate set for {xk}, if, for every subsequence {xk}k∈N, there exists xN∈S∘ and PN∈Rn such that(i)
-PN∈int⁡NS(xN);(ii)
lim⁡sup⁡k∈N,k→∞(1/∥xk-xN∥)〈∇f(xk)-PN,xk-xN〉≥0.It is easy to verify that the following several propositions expressed are special cases of generalized nondegenerate set.Proposition 14.
LetS∘⊂S be a nondegenerate set, and let {xk}⊂Rn be a bounded sequence, with its every accumulation point x*∈S∘. Then, S∘ is a generalized nondegenerate set for {xk}.Proposition 15.
LetS∘⊂S,{xk}⊂Rn, and {∇f(xk)} be bounded. If, for every accumulation point ∇f* of {∇f(xk)}, there exists x*∈S∘ such that
(44)-∇f*∈int⁡NS(x*).
then S∘ is a generalized nondegenerate set for {xk}.From [20, Theorem 3.1], we know that gradient ∇f(·) is always constant vector in the optimal solution set of a convex optimization problems. So, according to the monotonicity of ∇f(·), we get the following.Proposition 16.
LetS*, the optimal solution set of a convex optimization problems (NP), be a nondegenerate set. Then, for any {xk}⊂Rn, S* is a generalized nondegenerate set for {xk}.Here, we give the necessary and sufficient condition for the feasible solution sequence of the nonconvex optimization problems(NP) terminating finitely to its generalized nondegenerate solution set.Theorem 17.
For the nonconvex optimization problem(NP), let {xk}⊂S, the solution set (S¯ or S^), be a generalized nondegenerate set. Then, {xk} terminates finitely to solution set, if and only if
(45)lim⁡k→∞∇Sf(xk)=0.Proof.
Consider the following.
Necessity. If xk∈S¯, by the definition of stationary point, we have ∇Sf(xk)=0. If xk⊆S^, for S^⊂S¯, we also have ∇Sf(xk)=0.
Sufficiency. We only give the proof for S¯. The proof for S^ is the same as that for S¯. Suppose (45) holds. We prove the result by contradiction. Suppose on the contrary that there exists an infinite subsequence N⊆{1,2,…} such that
(46)xk∉S¯,∀k∈N.
Since S¯ is a generalized nondegenerate for {xk}, so, according to Definition 13, for subsequence {xk}k∈N,∃xN∈S¯ and PN∈Rn, such that
(47)-PN∈int⁡NS(xN),(48)lim⁡sup⁡k∈N,k→∞1∥xk-xN∥〈∇f(xk)-PN,xk-xN〉≥0.
From (47), we know that ∃α>0 such that
(49)-PN+αB⊂NS(xN),
where B stands for the unit ball in Rn. By (49), for ∀g∈TS(xN),g≠0, we have
(50)〈-PN+αg∥g∥,g〉≤0;
that is,
(51)α≤〈PN,g∥g∥〉.
Let gk=xk-xN(∀k∈N), and by (46) we have gk≠0. Since S is convex, we have
(52)gk∈TS(xN),-gk∈TS(xk)(∀k∈N).
Then, according to (51), (52), and the property of gradient projection, we have for all k∈N(53)α≤〈PN,gk∥gk∥〉=〈-PN,-gk∥gk∥〉=〈-∇f(xk),-gk∥gk∥〉-〈∇f(xk)-PN,gk∥gk∥〉≤max⁡⁡{〈-∇f(xk),d〉∣d∈TS(xk),∥d∥≤1}-〈∇f(xk)-PN,gk∥gk∥〉=∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉.
It follows that
(54)α≤∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉,(∀k∈N).
Since gk=xk-xN, according to (45) (48), we have
(55)α≤lim⁡inf⁡k∈N,k→∞{∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉}≤-lim⁡sup⁡k∈N,k→∞〈∇f(xk)-PN,gk∥gk∥〉≤0,
which is a contradiction with α>0.Corollary 18.
For the the nonconvex optimization problems(NP), let {xk}⊂S be a bounded sequence and let S¯ be a nondegenerate set. Then, {xk} terminates finitely to S¯, if and only if (45) holds.Proof.
The Necessity is obvious. We only need to prove the Sufficiency. Suppose (45) holds; that is,
(56)lim⁡k→∞∇Sf(xk)=0.
According to the lower semicontinuity of ∇Sf(·) and the boundedness of {xk}, we have that every accumulation point x* of {xk} is in S¯. Therefore, from Proposition 14, we know that S¯ is a generalized nondegenerate set for {xk}. Then, according to (45), by Theorem 17, sufficiency holds.Corollary 19.
For the nonconvex optimization problem(NP), let {xk}⊂S, and {∇f(xk)} is a bounded sequence, and, for each of its accumulation point ∇f*, there exists x*∈S¯ (or x*∈S^) such that
(57)-∇f*∈int⁡NS(x*).
Then, {xk} terminates finitely to the solution set S¯ (or S^) if and only if (45) holds.Proof.
By Proposition15 and Theorem 17, we can get it.Corollary 20.
For the nonconvex optimization problem(NP), let {xk}⊂S, and S¯ is a nondegenerate set. Then, {xk} terminates finitely to S*, if and only if (45) holds.Proof.
Here, we haveS*=S¯. Then, by Proposition 16 and Theorem 17, we can get it.In the following, we will use the global error bounds of projected gradient, which resulted from last section, to characterize the necessary and sufficient condition of feasible solution sequence terminating finitely by the merit functionϕ(·) which is easy to calculate.Theorem 21.
For the nonconvex optimization problem(NP), {xk}⊂S, and KKT points set S^ is a generalized nondegenerate set for {xk}. Then, {xk} terminates finitely to S^, if and only if
(58)lim⁡k→∞ϕ(xk)=0.Proof.
Consider the following.
Necessity. If xk∈S^, then, according to Theorem 4, we have ϕ(xk)=0.
Sufficiency. Suppose (58) holds, and according to Theorem 9, we have lim⁡k→∞∇Sf(xk)=0; that is, (45) holds. From Theorem 17, we get the sufficiency.Lemma 22.
For the nonconvex optimization problem(NP), let {xk}⊂S, and (58) holds. If x* is an accumulation point of {xk} satisfying the Mangasarian-Fromovitz constraint qualification, then x* is a KKT point of (NP).Proof.
Without loss of generality, we assume that(59)lim⁡k→∞xk=x*.
Then, there exists an index set IS⊂{1,2,…,m} and an infinite subsequence N⊆{1,2,…} such that
(60)IS(xk)=IS⊆IS(x*),∀k∈N.
The tangent cone of S(x) at x∈S is
(61)TS(x)(x)={d∈Rn∣〈∇ci(x),d〉≤0,i∈IS(x)},
and its normal cone is
(62)NS(x)(x)={∑i∈IS(x)‍αi∇ci(x)∣αi≥0,i∈IS(x)}.
Therefore, by (60) and (62), when k∈N, there exists λi(k)≥0 for i∈IS such that
(63)P(-∇f(xk)∣NS(xk)(xk))=∑i∈IS‍λi(k)∇ci(xk),
from which, and using the orthogonal projection decomposition, for all k∈N, we get
(64)-∇f(xk)=P(-∇f(xk)∣TS(xk)(xk))+P(-∇f(xk)∣NS(xk)(xk))=∇S(xk)f(xk)+∑i∈IS‍λi(k)∇ci(xk).
We now show that the sequence{∑i∈ISλi(k)}k∈N must be bounded. Suppose on the contrary that
(65)lim⁡k∈N,k→∞∑i∈IS‍λi(k)=+∞,
Let us suppose
(66)lim⁡k∈N,k→∞λi(k)∑i∈ISλi(k)=αi*,i∈IS.
Dividing the two sides of (64) by ∑i∈ISλi(k) and taking limit, due to (65) and (66), with the continuity of ∇ci(·), we obtain
(67)∑i∈IS‍αi*∇ci(x*)=0,
and, according to (66), we have
(68)∑i∈IS‍αi*=1,αi*≥0,i∈IS.
According to the assumption,x* satisfies the M-F constraint qualification; that is, there is h∈Rn such that
(69)〈∇ci(x*),h〉<0,∀i∈IS(x*).
Since IS⊆IS(x*), so (69), (67), and (68) are contradictory. So we assume that lim⁡k∈N,k→∞λi(k)=λi* for i∈IS. By (58) and Theorem 7, we know that lim⁡k→∞∇S(xk)f(xk)=0. Then, by (64) and the continuity of ∇f(·), we obtain
(70)-∇f(x*)=lim⁡k∈N,k→∞-∇f(xk)=lim⁡k∈N,k→∞∇S(xk)f(xk)+lim⁡k∈N,k→∞∑i∈IS‍λi(k)∇ci(xk)=∑i∈IS‍λi*∇ci(x*),
which means that x* is a KKT point of the (NP).Corollary 23.
For the nonconvex optimization problem(NP), suppose S^ is a nondegenerate set, {xk}⊂S is bounded, and each of its accumulation point x* is satisfying the Mangasarian-Fromovitz constraint qualification. Then, {xk} terminates finitely to S^ if and only if the sequence satisfies (58).Proof.
According to Lemma22 and Proposition 14, by Theorem 21 we can get it.Corollary 24.
For the nonconvex optimization problem(NP), suppose {xk}⊂S, and {∇f(xk)} is a bounded sequence, and, for each of its accumulation point ∇f*, there exists x*∈S^ such that
(71)-∇f*∈int⁡NS(x*).
Then, {xk} terminates finitely to S^ if and only if the sequence satisfies (58).Proof.
According to Proposition15, by Theorem 21 we can get it.


## 4.2. Generalized Weak Sharp Minima

In [20], Burke and Ferris gave an equivalent condition for weak sharp minima for a convex optimization problem; that is, the optimal solution set S* of the convex optimization problem is a set of weak sharp minima if and only if for every x¯∈S*(72)-∇f(x¯)∈int⁡⋂x∈S*‍[TS(x)∩NS*(x)]∘.Generally speaking, for a nonconvex optimization problem, (72) is only a necessary condition for weak sharp minima condition (11); that is, (72) is weaker than (11). However, considering its importance in analyzing the finite termination of algorithms, some previous studies, for example, [21, 22], directly use (72) as the definition of weak sharp minima for the optimal solution set. In this paper, we will use the weaker condition (72) to define the set of weak sharp minima.Definition 25.
LetS∘⊂S, and S∘ is said to be a set of weak sharp minima if and only if (72) holds.Now, we further extend the definition of weak sharp minima as follows.Definition 26.
LetS∘⊂S and {xk}⊂Rn. S∘ is said to be a set of generalized weak sharp minima for {xk}, if, for every subsequence {xk}k∈N, there exists PN∈Rn such that(i)
-PN∈int⁡⋂x∈S∘‍[TS(x)∩NS∘(x)]∘;(ii)
limsup⁡k∈N,k→∞(1/∥xk-P(xk∣S∘)∥)〈∇f(xk)-PN,xk-P(xk∣S∘)〉≥0.With the same as the set of generalized nondegeneration, it is easy to verify that the following several propositions expressed are special cases of generalized weak sharp minima.Proposition 27.
LetS∘⊂S be a set of weak sharp minima, and let {xk}⊂Rn be a bounded sequence, with its every accumulation point x*∈S∘. Then, S∘ is a set of generalized weak sharp minima for {xk}.Proposition 28.
LetS∘⊂S,{xk}⊂Rn, and {∇f(xk)} be bounded. If, for every accumulation point ∇f* of {∇f(xk)},
(73)-∇f*∈int⋂x∈S∘‍[TS(x)∩NS∘(x)]∘,
then, S∘ is a set of generalized weak sharp minima for {xk}.Proposition 29.
Let the optimal solution setS* of a convex optimization problem (NP) be a set of weak sharp minima. Then, for any {xk}⊂Rn, S* is a set of generalized weak sharp minima for {xk}.Here, we give the necessary and sufficient condition for the feasible solution sequence of a nonconvex optimization problem(NP) terminating finitely to its solution set of generalized weak sharp minima.Theorem 30.
For the nonconvex optimization problem(NP), let {xk}⊂S, and its stationary point set S¯ is convex and is a set of generalized weak sharp minima for {xk}. Then, {xk} terminates finitely to S¯, if and only if (45) holds.Proof.
Consider the following.
Necessity. If xk∈S¯, by the definition of stationary point, we have ∇Sf(xk)=0.
Sufficiency. Suppose (45) holds. We prove the result by contradiction. Suppose on the contrary that there exists an infinite subsequence N⊆{1,2,…} such that
(74)xk∉S¯,∀k∈N.
So, according to Definition 26 (i), we know that, for subsequence {xk}k∈N,∃PN∈Rn and α>0, such that, for ∀x∈S¯, we have
(75)-PN+αB⊂[TS(x)∩NS¯(x)]∘.
By (74), for ∀g∈TS(x)∩NS¯(x) and ∀x∈S¯, we have
(76)α≤〈PN,g∥g∥〉.
Let zk=P(xk∣S¯) and gk=xk-zk. By (74), we have ∀k∈N, gk≠0. Since S is convex, we have
(77)gk∈TS(zk),-gk∈TS(xk).
Since S¯ is convex, according to the property of projection and the definition of NS¯(·), we have gk∈NS¯(zk), so by (77), we have
(78)gk∈TS(zk)∩NS¯(zk).
Then, according to (76), (77), (78), and the property of gradient projection, we have
(79)α≤〈PN,gk∥gk∥〉=〈-PN,-gk∥gk∥〉=〈-∇f(xk),-gk∥gk∥〉-〈∇f(xk)-PN,gk∥gk∥〉≤max⁡⁡{〈-∇f(xk),d〉∣d∈TS(xk),∥d∥≤1}-〈∇f(xk)-PN,gk∥gk∥〉=∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉.
It follows that
(80)α≤∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉.
Since gk=xk-P(xk∣S¯), according to (45) and Definition 26 (ii), we have
(81)α≤lim⁡inf⁡k∈N,k→∞{∥∇Sf(xk)∥-〈∇f(xk)-PN,gk∥gk∥〉}≤-lim⁡sup⁡k∈N,k→∞〈∇f(xk)-PN,gk∥gk∥〉≤0,
which is a contradiction with α>0.With the same as generalized nondegeneration, according to Propositions27, 28, and 29 and by Theorem 30, we can get the following corollaries.Corollary 31.
For the nonconvex optimization problem(NP), suppose S¯ is convex and weak sharp minima, and {xk}⊂S is an bounded sequence. Then, {xk} terminates finitely to S¯, if and only if (45) holds.Corollary 32.
For the nonconvex optimization problem(NP), suppose S¯ is convex and {xk}⊂S; {∇f(xk)} is a bounded sequence, and for each of its accumulation point ∇f*, we have
(82)-∇f*∈int⋂x∈S¯‍[TS(x)∩NS¯(x)]∘.
Then, {xk} terminates finitely to S¯, if and only if (45) holds.Corollary 33.
For the nonconvex optimization problem(NP), the optimal solution set S* is weak sharp minima, {xk}⊂S. Then, {xk} terminates finitely to S*, if and only if (45) holds.Notation.Corollary 33 is [25, Theorem 2], which simplifies Theorem 4.7 in Burke and Ferris [20] (which removes two assumptions of [20, Theorem 4.7]; that is, lim⁡k→∞dist⁡(xk,S*)=0 and ∇f(·) is uniformly continuous on an open set containing {xk}); therefore, our Theorem 30 extends [20, Theorem 4.7] to nonconvex optimization problems.



---

*Source: 158780-2014-04-30.xml*