Abstract

For nonconvex optimization problem with both equality and inequality constraints, we introduce a new augmented Lagrangian function and propose the corresponding multiplier algorithm. New iterative strategy on penalty parameter is presented. Different global convergence properties are established depending on whether the penalty parameter is bounded. Even if the iterative sequence is divergent, we present a necessary and sufficient condition for the convergence of to the optimal value. Finally, preliminary numerical experience is reported.

1. Introduction

This paper is concerned with the following nonlinear programming problem: where for and for are all continuously differentiable functions, and is a nonempty and closed subset in . Denoted by the feasible region and by the solution set.

The classical Lagrangian function for this problem is where . It is well known that the above classic Lagrangian function would fail to find out the optimal solution of primal problem because a nonzero duality gap may be arisen for nonconvex programming. Augmented Lagrangians were proposed to overcome this difficulty. It combines the advantage from Lagrangian duality methods and penalty function methods; for example, it does not need to make the penalty parameter infinitely large, and hence successfully avoid ill-conditioning effects. In fact, if the penalty parameter is very large, the Lagrangian relaxation subproblem would be very difficult in the sense that the stabilized Newton step is not regarded as a candidate to be a decreasing direction.

Global convergence properties of augmented Lagrangian methods have been studied by many researchers [1–8]. It should be noted that the multiplier sequence generated by the algorithm may be unbounded. Several strategies have proposed to deal with these questions, such as adding constraint qualifications [5, 6] or via safeguarding projection [1, 2, 9, 10].

In this paper, for the optimization problem () with both equality and inequality constraints, we introduce a new class of augmented Lagrangian functions, which include the well-known quadratic augmented Lagrangian function as special case [11–13]. It should be noted that this function class is more general since we do not restrict to be convex (see (2.1) below for the definition of ). Convergence properties of the corresponding multiplier algorithm are studied. Specially, a new updated strategy on penalty parameter is proposed, that is, the penalty parameter is improved only when the multipliers are too large, and the iterative point is far away from the feasible region. This strategy guarantees that the penalty parameter remains unchanged, provided that measure of infeasibility of iterative point and bounding of multipliers have enough progress (see (2.4)). Furthermore, we study the performance of the multiplier sequences generated by our algorithm. Finally, compared with [4, 9, 10], we further consider the case when is divergent, in which a necessary and sufficient condition for converging to the optimal value is given as well.

The organization of this paper is as follows. In the next section, we propose the multiplier algorithm and study the global convergence properties. Preliminary numerical results are reported in Section 3. Conclusion is drawn in Section 4.

2. Multiplier Algorithms

A new generalized quadratic augmented Lagrangian function for () is defined as follows: where , and denotes the all positive real scalars, that is, . The function involved in (2.1) satisfies the following properties:continuously differentiable and strictly increasing on with and for .

Particularly, if for , then reduces to the quadratic augmented Lagrangian function. Compared with [9, 14, 15], an important point made above is that is not required to be convex. Hence, it makes the augmented Lagrangian we introduce here more general.

Given , the Lagrangian relaxation subproblem associated with the augmented Lagrangian is defined as: Its solution set is denoted by . We always assume throughout this paper that the set is nonempty, which is ensured if is compact, since , , and are all continuous. In addition, we assume that: is bounded from below, that is, .

It is a rather mild assumption in optimization problem because otherwise the objective function can be replaced by . Recall that a vector is said to be a stationary point of () if it is a feasible point and there exist for all and for such that the following system holds: where denotes the normal cone of at [16, Chapter 6]. Let denote the collection of multipliers satisfying (2.2). The set of is larger than that of R-multiplier defined in [17], which reduces to the well-known Karush-Kuhn-Tucker (KKT) point of () when , since the complementarity condition is required for KKT point. The following is the multiplier algorithm based on the generalized quadratic augmented Lagrangian . One of its main feature is that the Lagrangian multipliers associated with equality and inequality constraints are not restricted to be bounded.

Algorithm 2.1 (multiplier algorithm based on ). Step 1. (initialization)
Let and be an arbitrary positive sequence with zero as limit i.e., . Select an initial point , , , and . Set .
Step 2. (estimating multipliers)
Compute
Step 3. (updating penalty parameter)
Let
Step 4. (solving lagrangian relaxation subproblem)
Find .
Step 5. (cycling)
If and , then stop; otherwise, let and go back to Step 2.

Consider the perturbation of (); precisely, for any fixed , define the perturbation value function as follows: where It is clear that . In practical implementation of the previous algorithm, we always choose the constant large enough to strictly include , the set of subdifferential of at origin, since according to the strong duality theory, the optimal Lagrangian multipliers belong to ; see [18] for the detailed discussion. In [5, 6], the authors require the convergence of to zero. It follows from (2.5) that this nice property holds automatically in our new strategy. In addition, (2.4) and (2.5) indicate that Lagrangian relaxation subproblem needs to place more emphasis on decreasing the constraint violations via increasing the penalty parameter, provided that the current point is far away from feasible region.

Lemma 2.2. Let be the iterative sequence generated by Algorithm 2.1, and let be one of its accumulate points. If is bounded, then is a stationary point of ().

Proof. If the algorithm is terminated finitely, then the result follows immediately according to the stop criterion in Step 5. On the other hand, if the condition (2.5) occurs infinitely, then , and hence must be unbounded. Therefore, by hypothesis we knew that only condition (2.4) occurs when is large enough. Because and by (2.4), taking the limit yields and , since converges to zero. This shows the feasibility of . Meanwhile, we know from (2.4) that and are bounded. Hence, we can assume without loss of generality that and . Since is an optimal solution of minimizing over by Step 4, then according to the well-known optimality conditions we have which together with the formula of (2.3) and (2.4) yields Taking limits gives us where we have used the upper semicontinuity of normal cone [16, Chapter 6]. This completes the proof.

Now, we turn our main concern to the case when is unbounded.

Theorem 2.3. Let be the iterative sequence generated by Algorithm 2.1, and let be one of its accumulate points. If is unbounded, then is an optimal solution of ().

Proof. It is clear that if is unbounded, then the iteration formula (2.5) occurs infinitely. Hence, for simplification, we assume that (2.5) always happens as sufficiently large, and that converges to (not resorting to a subsequence). Taking into account of (2.5), the terms are all converges to zero. This fact will be used in the following analysis.
Let us first show that is a feasible point of (). We argue it by contradiction. Note first that where the third and fourth steps are due to the feasibility of . This implies that
Now, let us consider the following two cases.Case 1. There exists an index such that . Due to the continuity of , we must have for is large enough. Therefore, Noticing that as mentioned above and , we know that as is large enough which further implying This, together with (2.13), yields since approaches to , which contradicts (2.12).
Case 2. There exists an index such that . Similarly, due to the continuity of , we know that as is sufficiently large. Therefore, where the second inequality comes from the fact for all by , and the last inequality follows from the nonnegativity of by (2.3), since for all due to the monotonicity of . Invoking (2.5) and taking limits in the above inequality yields , which contradicts (2.12). So far, we have established the feasibility of .
It remains to show that is an optimal solution. In fact, notice that where the second inequality is due to (2.11). Taking limits in the above yields where the last step comes from the fact that and converge to zero (see (2.5)). This means that must be an optimal solution of (). The proof is complete.

Finally, let us deal with the performance of multiplier sequences and generated by our proposed algorithm.

Theorem 2.4. Let be an iterative sequence generated by Algorithm 2.1, and let be one of its accumulate points. The following statements hold:(i)if both and are bounded, then we have where and are accumulate points of and ;(ii)if either or is unbounded, then we have where and are accumulate points of and with

Proof. The proof is divided into the following two cases.
Case 1. Both and are bounded. In this case, we can obtain that is a stationary point of () by following almost the same argument as in Lemma 2.2.
Case 2. Either or is divergent. According to the updated strategy on penalty parameter , we know that (2.5) must occur as sufficiently large. Hence, is unbounded in this case. Since is a global optimal solution of over by Step 4 in Algorithm 2.1, applying the optimality condition to the augmented Lagrangian relaxation problem yields that is,
Since and are bounded, we can assume without loss of generality that Clearly, and are not all zeros. Dividing by in both sides of (2.23) and using the fact that is cone, we have Taking limits in the above yields This establishes the result as desired.

Now, a natural question arises: how does the algorithm perform if is divergent? The following theorem gives the answer.

Theorem 2.5. Let be an iterative sequence generated by Algorithm 2.1. If is unbounded, then the following statements are equivalent:(a) converges to the optimal value, that is, (b) is lower semicontinuous at from right, that is, ;(c) is continuous at from right, that is, .

Proof. . Suppose on the contrary that is not lower semicontinuous at zero from right, then there must exist and such that For any given , since we can choose a subsequence satisfying which together with the continuity of implies that
In addition, pick with . Then by (2.28).
Therefore, where the last step is due to the fact and since and is nondecreasing by . Taking the limits in both sides of (2.31) and using (2.27) and (2.30) yield which leads to a contradiction.
. Since converges to , it then follows from Theorem 2.3 that is an optimal solution of (). Hence, for any arbitrary , we have and (since and as is sufficiently large). The latter further implies that by definition (2.6), that is, Since is lower semicontinuous at from right by hypothesis, taking the lower limitation in (2.33) yields that is,
. It is clear.
. It follows by invoking the fact that , since for all . Then , that is, is upper semicontinuous at origin from right. This together with the lower semicontinuous of at origin by hypothesis yields the desired result.