# Existence of Local Saddle Points for a New Augmented Lagrangian Function

Authors: Wenling Zhao; Jing Zhang; Jinchuan Zhou
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

We give a new class of augmented Lagrangian functions for nonlinear
programming problem with both equality and inequality constraints. The close relationship
between local saddle points of this new augmented Lagrangian and local optimal
solutions is discussed. In particular, we show that a local saddle point is a local optimal
solution and the converse is also true under rather mild conditions.


---

## Body

## 1. Introduction

Consider the nonlinear optimization problemPminf(x),s.t.gi(x)≤0,i=1,2,…,m,hj(x)=0,j=1,2,…,l,x∈X,
where f, gi:ℝn→ℝ for i=1,…,m and hj:ℝn→ℝ for j=1,2,…,l are twice continuously differentiable functions and X⊆ℝn is a nonempty closed subset.The classical Lagrangian function associated with (P) is defined as (1.1)L(x,λ,μ)=f(x)+∑i=1mλigi(x)+∑j=1lμjhj(x),
where λ=(λ1,λ2,…,λm)T∈ℝ+m and μ=(μ1,μ2,…,μl)T∈ℝl.The Lagrangian dual problem (D) is presented:Dmaxθ(λ,μ),s.t.λ≥0,
where
(1.2)θ(λ,μ)=infx∈XL(x,λ,μ).Lagrange multiplier theory not only plays a key role in many issues of mathematical programming such as sensitivity analysis, optimality conditions, and numerical algorithms, but also has important applications, for example, in scheduling, resource allocation, engineering design, and matching problems. According to both analysis and experiments, it performs substantially better than classical methods for solving some engineering projects, especially for medium-sized or large projects.Roughly speaking, the augmented Lagrangian method uses a sequence of iterate point of unconstrained optimization problems, which are constructed by utilizing the Lagrangian multipliers, to approximate the optimal solution of the original problem. Toward this end, we must ensure that the zero dual gap property holds between primal and dual problems. Therefore, saddle point theory received much attention, due to its equivalence with zero dual gap property. It is well known that, for convex programming problems, the zero dual gap holds by using the above classical Lagrangian function. However, the nonzero duality gap may appear for nonconvex optimization problems. The main reason is that the classical Lagrangian function is linear with respect to the Lagrangian multiplier. To overcome this drawback, various types of nonlinear Lagrangian functions and augmented Lagrangian functions have been developed in recent years. For example, Hestenes [1] and Powell [2] independently proposed augmented Lagrangian methods for solving equality constrained problems by incorporating the quadratic penalty term in the classical Lagrangian function. This was extended by Rockafellar [3] to the constrained optimization problem with both equality and inequality constraints. A convex augmented function and the corresponding augmented Lagrangian with zero duality gap property were introduced by Rockafellar and Wets in [4]. This was further extended by Huang and Yang by removing the convexity assumption imposed on the augmented functions as in [4]; see [5, 6] for the details. Wang et al. [7] proposed two classes of augmented Lagrangian functions, which are simpler than those given in [4, 5], and discussed the existence of saddle points. For other kinds of augmented Lagrangian methods refer to [8–16]; for saddle points theory and multiplier methods, refer to [17–20]. It should be noted that the sufficient conditions given in the above papers for the existence of local saddle points of augmented Lagrangian functions all require the standard second-order sufficient conditions. So, a natural question arises: whether we can exploit local saddle points under rather mild assumptions, other than the standard second-order sufficient conditions. Motivated by this, in this paper, we propose a new augmented Lagrangian function and establish the close relationship between local saddle points and local optimal solutions of the original problem. In particular, we show that this property holds under weak second-order sufficient conditions.The paper is organized as follows. After introducing some basic notation and definitions, we mainly present sufficient conditions for the existence of a local saddle point and discuss the close relationship between a local saddle point and a local optimal solution of the original problem. Finally, an example to illustrate our result is given.


## 2. Notation and Definition

We first introduce some basic notation and definitions, which will be used in the sequel. Letℝ+n be the nonnegative orthant. For notational simplification, let (2.1)G(x)=(g1(x),g2(x),…,gm(x))T,λ=(λ1,…,λm)T,t=(t1,…,tm)T,μ=(μ1,…,μl)T,u=(u1,…,um)T.Definition 2.1.
A pair(x*,λ*,μ*) is said to be a global saddle point of Lr(x,λ,μ) for some r>0, if
(2.2)Lr(x*,λ,μ)≤Lr(x*,λ*,μ*)≤Lr(x,λ*,μ*)
whenever (x,λ,μ)∈X×ℝ+m×ℝl. If there exists some positive scalar δ>0 such that the above inequality holds for all (x,λ,μ)∈(X∩N(x*,δ))×ℝ+m×ℝl, where N(x*,δ)={x∈ℝn∣∥x-x*∥≤δ}, then (x*,λ*,μ*) is said to be a local saddle point of Lr(x,λ,μ) for r>0.Definition 2.2 (weak second-order sufficient conditions).
Letx* be a feasible solution. (1)
Suppose that the KKT conditions hold atx*; that is, there exist scalars λi*≥0 for i=1,…,m and μj* for j=1,…,l such that
(2.3)∇f(x*)+∑i=1mλi*∇gi(x*)+∑i=1mμj*∇hj(x*)=0,(2.4)λi*gi(x*)=0,i=1,…,m.(2)
The Hessian matrix(2.5)∇xx2L(x*,λ*,μ*)=∇2f(x*)+∑i=1mλi*∇2gi(x*)+∑j=1lμj*∇2hj(x*)
is positive definite on the cone
(2.6)M(x*)={∇hj(x*)Td=0,j=1,…,l,d∈ℝn,d≠0∣∇gi(x*)Td=0,i∈J(x*),∇gi(x*)Td≤0,i∈I(x*)∖J(x*)},
where
(2.7)I(x*)={i∣gi(x*)=0,i=1,…,m},J(x*)={i∈I(x*)∣λi*>0,i=1,…,m}.Clearly, the above cone is included in the coneM′(x*)={d∈ℝn,d≠0∣∇hj(x*)Td=0,j=1,…,l;∇gi(x*)Td=0,i∈J(x*)}, which is involved in the second-order sufficient condition. Hence, we refer to above conditions as weak second-order sufficient conditions.


## 3. Existence of Local Saddle Points

For inequality constrained optimization, Sun et al. [21] introduced a class of the generalized augmented Lagrangian function Lr:ℝn×ℝ+m→ℝ,(3.1)Lr(x,λ)=f(x)+Pr(-G(x),λ),
where Pr(s,t):ℝm×ℝ+m→ℝ is defined as (3.2)Pr(s,t)=infu-s≤0{-uTt+rσ(u)}.
The function σ(u) satisfies the following assumptions:(A1)
σ(0)=0, and σ(u)>0 for all u≠0;(A2)
for eachi∈{1,2,…,m}, σ(u) is nondecreasing on ui≥0 and nonincreasing on ui<0;(A3)
σ(u) is continuously differentiable and ∇σ(0)=0;(A4)
σ(u) is twice continuously differentiable in a neighborhood of 0∈ℝm and hT∇2σ(0)h>0 for all nonzero h∈ℝm.We extend this function to treat the optimization problems with equality and inequality constraints. Consider a new augmented Lagrangian functionLr(x,λ,μ):ℝn×ℝ+m×ℝl→ℝ(3.3)Lr(x,λ,μ)=f(x)+∑j=1lμjhj(x)+r2∑j=1lhj2(x)+Pr(-G(x),λ),
where Pr(-G(x),λ) is defined as above and the function σ(u) satisfies (A1)–(A4). Several important augmented functions satisfy the above assumptions, as for example:Example 3.1.
σ(u)=∑i=1mui2.Example 3.2.
σ(u)=e∥u∥2-1.Under the weak second-order sufficient conditions (instead of the standard second-order sufficient conditions), we show that a local optimal solution is also a local saddle point of the augmented Lagrangian function.Theorem 3.3.
Letx* be a local optimal solution to problem (P). If the weak second-order sufficient conditions are satisfied at x*, then there exist r0>0 and δ>0 such that for any r≥r0,
(3.4)Lr(x*,λ,μ)≤Lr(x*,λ*,μ*)≤Lr(x,λ*,μ*),∀(x,λ,μ)∈(X∩N(x*,δ))×ℝ+m×ℝl.Proof.
Sincex* is a feasible solution to problem (P), then hj(x*)=0 and
(3.5)Pr(-G(x*),λ)=infu+G(x*)≤0{-uTλ+rσ(u)}≤0Tλ+rσ(0)=0,∀λ≥0.
It follows from (A1) and (2.4) that
(3.6)Pr(-G(x*),λ*)=infu+G(x*)≤0{-uTλ*+rσ(u)}≥infu+G(x*)≤0{-uTλ*}=∑i=1mgi(x*)λi*=0.
Combining the last two inequalities yields Pr(-G(x*),λ*)=0. Hence,
(3.7)Lr(x*,λ,μ)=f(x*)+∑j=1lμjhj(x*)+r2∑j=1lhj2(x*)+Pr(-G(x*),λ)≤f(x*)=Lr(x*,λ*,μ*).
We obtain the left inequality of (2.2) as desired.
To show the right inequality of (2.2), it suffices to prove that it holds for some r0 and δ, since Lr(x,λ,μ) is nondecreasing in r>0. Suppose the contrary that such r0 and δ do not exist. Then for each positive integer k, there must exist xk∈X such that xk→x* and (3.8)Lk(xk,λ*,μ*)<Lk(x*,λ*,μ*)=f(x*).
Define uGk=(uG1k,uG2k,…,uGmk) as follows:
(3.9)uGik={0,i∈{1,2,…,m}∖I(x*),0,i∈J1k(x*),-gi(xk),i∈J2k(x*),-gi(xk),i∈J(x*),
where
(3.10)J1k(x*)={I(x*)∖J(x*)}∩{i∣gi(xk)≤0},J2k(x*)={I(x*)∖J(x*)}∩{i∣gi(xk)≥0}.
For xk, we have
(3.11)Pr(-G(xk),λ*)=infui+gi(xk)≤0,1≤i≤m{∑i∈J(x*)-uiTλi*+kσ(u)}=∑i∈J(x*)gi(xk)λi*+kσ(uGk).
Three cases may be considered.
Case 1.
Wheni∈{{1,2,…,m}∖I(x*)}∪J1k(x*), take ui(i∈J2k(x*)∪J(x*)). Since λi*=0, then the original point is a minimizer of
(3.12)infui+gi(xk)≤0,i∈{{1,2,…,m}∖I(x*)}∪J1k(x*){∑i∈J(x*)-uiTλi*+kσ(u)}.Case 2.
Wheni∈J2k(x*), taking into account to the fact that the function ∑i∈J(x*)-uiTλi*+kσ(u) is decreasing on ui in (-∞,-gi(xk)], then ui=-gi(xk) is a minimizer of
(3.13)infui+gi(xk)≤0,i∈J2k(x*){∑i∈J(x*)-uiTλi*+kσ(u)}.Case 3.
Wheni∈J(x*), let ∇σ(u)i be the ith component of vector ∇σ(u), for any 0≤ui≤-gi(xk). We get from (A3) that
(3.14)∇σ(u)i≤λi*k,∀k∈N,
that is, -λi*+k∇σ(u)i≤0, and this implies that ∑i∈J(x*)-uiTλi*+kσ(u) is decreasing on ui in (0,-gi(xk)]. So ui=-gi(xk) is a minimizer of
(3.15)infui+gi(xk)≤0,i∈J(x*){∑i∈J(x*)-uiTλi*+kσ(u)}.
Therefore,
(3.16)0>f(xk)-f(x*)+∑j=1lμj*hj(xk)+k2∑j=1lhj2(xk)+∑i∈J(x*)gi(xk)λi*+kσ(uGk)=L(xk,λ*,μ*)-L(x*,λ*,μ*)+k2∑j=1l{hj(x*)+∇hj(x*)(xk-x*)+o(∥xk-x*∥)}2+kσ(0)+k∇σ(0)TuGk+k2uGk∇2σ(0)uGk+ko(∥uGk∥2).
Since ∇xL(x*,λ*,μ*)=0, then
(3.17)L(xk,λ*,μ*)-L(x*,λ*,μ*)=12(xk-x*)T∇xx2L(x*,λ*,μ*)(xk-x*)+o(∥xk-x*∥)2.
Hence
(3.18)0>12(xk-x*)T∇xx2L(x*,λ*,μ*)(xk-x*)+o(∥xk-x*∥)2+k2∑j=1l{∇hj(x*)(xk-x*)+o(∥xk-x*∥)}2+k2uGk∇2σ(0)uGk+ko(∥uGk∥2).
Set dk=(xk-x*)/∥xk-x*∥, which is bounded, we can assume without loss of generality that dk converges to d with ∥d∥=1. It follows from (3.18) that
(3.19)0>12dkT∇xx2L(x*,λ*,μ*)dk+o(∥xk-x*∥)2∥xk-x*∥2+k2∑j=1l{∇hj(x*)dk+o(∥xk-x*∥)∥xk-x*∥}2+k2(uGk∥xk-x*∥)T∇2σ(0)(uGk∥xk-x*∥)+ko(∥uGk∥2)∥xk-x*∥2.
Let l be the small eigenvalue of ∇2σ(0). Then l>0 by assumption. We claim that uGk/∥xk-x*∥ converges to zero. Suppose the contrary, that for xk→x*, we have
(3.20)k2(uGk∥xk-x*∥)T∇2σ(0)(uGk∥xk-x*∥)+ko(∥uGkxk-x*∥2)≥kl2∥uGkxk-x*∥2+ko(∥uGkxk-x*∥2).
Taking limits in the above inequality as k→+∞, the right hand converges to +∞, which contradicts (3.19). So uGk/∥xk-x*∥→0 as claimed.Noting that (3.9) amounts to
(3.21)uGik={0,i∈{1,2,…,m}∖I(x*),0,i∈J1k(x*),-∇gi(x*)T(xk-x*)+o(∥xk-x*∥),i∈J2k(x*),-∇gi(x*)T(xk-x*)+o(∥xk-x*∥),i∈J(x*),
then
(3.22)uGik∥xk-x*∥={0,i∈{1,2,…,m}∖I(x*),0,i∈J1k(x*),-∇gi(x*)Tdk+o(xk-x*)∥xk-x*∥,i∈J2k(x*),-∇gi(x*)Tdk+o(xk-x*)∥xk-x*∥,i∈J(x*).
So for any i∈J(x*)∪J2k(x*), taking limits in (3.19) with k approaches to +∞, we must have
(3.23)dT∇xx2L(x*,λ*,μ*)d≤0,(3.24)∇hj(x*)Td=0,j=1,…,l,(3.25)∇gi(x*)Td=0,i∈J(x*)∪J2k(x*).
For i∈I(x*)∖{J(x*)∪J2k(x*)}, there is an infinite index set N0⊆N such that gi(xk)≤0 for all k∈N0. So
(3.26)∇gi(x*)Td=limk→∞∇gi(ξik)dk=limk→∞gi(xk)-gi(x*)∥xk-x*∥≤0,
where ξik lies in the line segment between x* and xk. Putting (3.24)–(3.26) together implies that d∈M(x*). We get dT∇xx2L(x*,λ*,μ*)d>0 by Definition 2.2, which is a contradiction with (3.23). So the right inequality of (2.2) holds. The proof is complete.The converse of Theorem3.3 is given below.Theorem 3.4.
If(x*,λ*,μ*) is a local saddle point of Lr(x,λ,μ) for some r>0, then x* is a local optimal solution to the problem (P).Proof.
Let(x*,λ*,μ*) be a local saddle point of Lr(x,λ,μ) for some r>0. Then
(3.27)Lr(x*,λ,μ)≤Lr(x*,λ*,μ*)≤Lr(x,λ*,μ*)
whenever (x,λ,μ)∈(X∩N(x*,δ))×ℝ+m×ℝl. We first show that x* is a feasible solution. If not, there must exist gi0(x*)>0 for some i0 or hj0(x*)≠0 for some j0.Case 1.
There existsgi0(x*)>0 for some i0. Note that
(3.28)Lr(x*,λ,μ)=f(x*)+∑j=1lμjhj(x*)+r2∑j=1lhj2(x*)+Pr(-G(x*),λ).
Choose λi0>0 and λi=0 for all i≠i0. Then we get from (A1) that
(3.29)Pr(-G(x*),λ)=infu+G(x*)≤0{-uTλ+rσ(u)}≥infu+G(x*)≤0{-uTλ}≥gi0(x*)λi0.
Taking the limit as λi0→+∞ yields Pr(-G(x*),λ)→+∞, which is a contradiction with (2.2). So we have gi(x*)≤0 for all i=1,…,m.Case 2.
There existshj0(x*)≠0 for some j0. Choose μj0 and hj0(x*) with the same signal and let μj0 approach to +∞, which is a contradiction with (2.2). So we have hj(x*)=0 for all j∈{1,…,l}. Then x* is a feasible solution as claimed.Since x* is feasible, we have hj(x*)=0 and for u∈{u∈ℝm∣u+G(x*)≤0}. In particular for u=0, we have
(3.30)Pr(-G(x*),0)=infu+G(x*)≤0{-uT0+rσ(u)}=rσ(0)=0.
Substituting (3.30) into (2.2) yields
(3.31)Pr(-G(x*),λ*)≥0.
On the other hand, for any feasible x and λ≥0,
(3.32)Pr(-G(x*),λ)=infu+G(x*)≤0{-uTλ+rσ(u)}≤0Tλ+rσ(0)=0,
which, together with (3.31) and (3.32), implies that
(3.33)Pr(-G(x*),λ*)=0.
So
(3.34)Lr(x*,λ*,μ*)=f(x*).
Finally, for any feasible x∈X∩N(x*,δ), we have
(3.35)f(x*)=Lr(x*,λ*,μ*)≤Lr(x,λ*,μ*)=f(x)+∑j=1lμj*hj(x)+r2∑j=1lhj2(x)+Pr(-G(x),λ*)≤f(x),
which means that x* is a local optimal solution of (P).Example 3.5.
Consider the nonconvex programming problem(3.36)minf(x)=ex12-x22,s.t.g1(x)=1-x22≤0,g2(x)=e-x1-1≤0,h(x)=x1-2-x22+1=0,x∈X=R2.The optimal solutions of the above problem arex*,1=(0,1)T and x*,2=(0,-1)T with objective value e-1. Setting λ*=(e-1,0) and μ*=0, then we get from KKT conditions that (3.37)∇xL(x*,i,λ*,μ*)=∇f(x*,i)+∑i=12λi*∇gi(x*,i)+μ*∇h(x*,i)=(0-2x2*,ie-1)+e-1(02x2*,i)=0.
The Hessian matrix (3.38)∇xx2L(x*,i,λ*,μ*)=∇2f(x*,i)+∑i=12λi*∇2gi(x*,i)+μ*∇2h(x*,i)=(2e-1002e-1)+e-1(0002)=(2e-1004e-1)
is positive definite. The weak second-order sufficient conditions are satisfied at (x*,i,λ*,μ*),i=1,2. By Theorem 3.4, (x*,i,λ*,μ*)(i=1,2) is a local saddle point for Lr(x,λ,μ), and hence x*,1 and x*,2 are the optimal solutions to (P).Based on the above discussion, we know that, if(x*,λ*,μ*) is a saddle point of Lr, then (3.39)val(P)=Lr(x*,λ*,μ*)=supλ≥0,μ∈ℝlinfx∈ℝnLr(x,λ,μ),
where we denote by val(P) the optimal value of problem (P) and by (P′) the problem given in the right-hand side. Note that the problem (P′) has just the nonnegative constraints λ≥0 (rather simple constraints). Hence, we successful convert the original nonconvex problem to a simple constrained optimization problems by using the augmented Lagrangian function. Furthermore, many efficient algorithms for solving unconstrained optimization problems can be used to solve (P′), such as gradient-type algorithms. Therefore, our results, obtained with weaker conditions, provide a new insight and theoretical foundation for the use of augmented Lagrangian functions in constrained optimization problems.



---

*Source: 324812-2010-09-29.xml*