# An Augmented Lagrangian Algorithm for Solving Semiinfinite

Authors: Qian Liu; Changyu Wang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

We present a smooth augmented Lagrangian algorithm for semiinfinite programming (SIP). For this algorithm, we establish a perturbation theorem under mild conditions. As a corollary of the perturbation theorem, we obtain the global convergence result, that is, any accumulation point of the sequence generated by the algorithm is the solution of SIP. We get this global convergence result without any boundedness condition or coercive condition. Another corollary of the perturbation theorem shows that the perturbation function at zero point is lower semi-continuous if and only if the algorithm forces the sequence of objective function convergence to the optimal value of SIP. Finally, numerical results are given.


---

## Body

## 1. Introduction

We consider the semi-infinite programming (SIP):(1.1)inf{f(x)∣x∈X},
where X={x∈Rn∣g(x,s)≤0,foralls∈Ω}, the functions f:Rn→R and g:Rn×Rm→R are continuously differentiable. Ω⊂Rm is a nonempty bounded and closed domain. In this paper, we assume that
(1.2)infx∈Rnf(x)>-∞.
This assumption is very mild, because the objective function f(x) can be replaced by ef(x) if the assumption is not satisfied.Semi-infinite programming has wide applications such as engineering technology, optimal control, characteristic value calculation, and statistical design. Many methods have been proposed to solve semi-infinite programming (see [1–4]). As we know, the main difficulty for solving SIP is that it has infinite constraints. If transforming the infinite constraints into an integral function, SIP (1.1) is equivalent to a nonlinear programming with finite constraints.For any givenx∈Rn and s∈Ω, let
(1.3)[g(x,s)]+=max{g(x,s),0}.
Define φ:Rn→R by
(1.4)φ(x)=∫Ω‍[g(x,s)]+dμ(s),
where μ≥0 is a given probability measure on Ω, that is, ∫Ω‍dμ(s)=μ(Ω)=1. Thus SIP (1.1) can be reformulated as the following nonlinear programming (NP) with one equality constraint:
(1.5)infx∈Rn{f(x)∣φ(x)=0}.
Then nonlinear programming (1.5) has the same optimal solution and optimal value with SIP (1.1).For nonlinear programming with finite equality constraints, Hestenes [5] and Powell [6] independently proposed an augmented Lagrangian function by incorporating a quadratic penalty term in the conventional Lagrangian function. This augmented Lagrangian function avoids the shortcoming that the conventional Lagrangian function is only suitable for convex function. So the augmented Lagrangian function can be applied to nonconvex optimization problem. Later, the augmented Lagrangian function was extended to inequality constrained optimization problems and thoroughly investigated by Rockafellar [7]. Recently, Yang and Teo [8] and Rückmann and Shapiro [9] introduced the augmented Lagrangian function for SIP (1.1). In [9], necessary and sufficient conditions for the existence of corresponding augmented Lagrange multipliers were presented. [8] proposed a nonlinear Lagrangian method and established that the sequence of optimal values of nonlinear penalty problems converges to that of SIP (1.1), under the assumption that the level set of objective function is bounded. In this paper, using the equivalent relation of semi-infinite programming (1.1) and nonlinear programming (1.5), without any boundness condition, we present an augmented Lagrangian algorithm for SIP (1.1).We notice that although the constraints of NP (1.5) are finite, but the constraint function is nonsmooth. Therefore, existing gradient-based optimization methods cannot be used to solve NP (1.5) directly. To overcome this inconvenience, we have to smooth the constraint function. For SIP (1.1), [10–13] presented semismooth Newton methods and smoothing Newton methods. They proved that each accumulation point is a generalized stationary point of SIP (1.1). However, at each iteration of these methods, a Hessian matrix needs to be computed. When the size of the problem is large, computing a Hessian matrix is very expensive. Based on exact l1 penalty function that is approximated by a family of smoothing functions, a smoothed-penalty algorithm for solving NP (1.5) was proposed by [14]. They proved that if the constrained set is bounded or the objective function is coercive, the algorithm generates a sequence whose accumulation points are solutions of SIP (1.1).In this paper, for SIP (1.1), we present a smooth augmented Lagrangian algorithm by smoothing the classical augmented Lagrangian function [7]. In this algorithm, we need not have to get an exact global optimal solution of unconstraint subproblem at each iteration. It is sufficient to search an inexact solution. It is not difficult to obtain an inexact solution, whenever the evaluation of the integral function is not very expensive. For this algorithm, we establish a perturbation theorem under mild conditions. As a corollary of the perturbation theorem, we obtain the global convergence result, that is, any accumulation point of the sequence generated by the algorithm is the solution of SIP (1.1). We get this global convergence result without any boundedness condition or coercive condition. It is noteworthy that the boundedness of the multiplier sequence is a sufficient condition in many literatures about Lagrangian method (see [15–17]). However, in our algorithm, the multiplier sequence can be unbounded. Another corollary of the perturbation theorem shows that the perturbation function at zero point is lower semi-continuous if and only if the algorithm forces the sequence of objective function convergence to the optimal value of SIP (1.1).The paper is organized as follows. In the next section, we present a smooth augmented Lagrangian algorithm. In Section3, we establish the perturbation theorem of the algorithm. By this theorem, we obtain a global convergence property and a sufficient and necessary condition in which the algorithm forces the sequence of objective functions convergence to the optimal value of SIP (1.1). Finally, we give some numerical results in Section 4.


## 2. Smooth Augmented Lagrangian Algorithm

Before we introduce the algorithm, some definitions and symbols need to be given. Forε≥0, we define the relaxed feasible set of SIP (1.1) as follows:
(2.1)Rε={x∈Rn∣∫Ω‍[g(x,s)]+dμ(s)≤ε}.
Then R0 is the feasible set of SIP (1.1). Let R0* be the set of optimal solutions of SIP (1.1). We assume that R0*≠∅ in this paper.The perturbation function is defined as follows:(2.2)θf(ε)=infx∈Rεf(x).
Thus the optimal value of SIP (1.1) is
(2.3)θf(0)=infx∈R0f(x).
It is easy to show that θf(·) is upper semi-continuous at the point ε=0.For problem (1.5), the corresponding classical augmented Lagrangian function [7] is
(2.4)L(x,λ,ρ)=f(x)+ρ2[φ(x)+λρ]2-λ22ρ,
where λ is the Lagrangian multiplier and ρ is the penalty parameter. On base of it, we introduce a class of smooth augmented Lagrangian function:
(2.5)fr(x,λ,ρ)=f(x)+ρ2[r∫Ω‍ϕ(g(x,s)r)dμ(s)+λρ]2-λ22ρ.
Here r is the approximate parameter.In the following, we suppose that the continuously differentiable functionϕ:R→R satisfies(a)
ϕ(·) is nonnegative and monotone increasing;(b)
for anyt>0, ϕ(t)≥t;(c)
limt→+∞(ϕ(t)/t)=1.It is easy to check that there are many continuously differentiable functions satisfying conditions (a), (b), and (c). For example,(2.6)ϕ1(t)=log(1+et).ϕ2(t)={2et,t<0,t+log(1+t)+2,t≥0.ϕ3(t)={et,t<0,t+1,t≥0.ϕ4(t)=12(t+t2+4).
Using conditions (a) and (c), for any t∈R, we have
(2.7)limr→0+rϕ(tr)=max{0,t}.
From the above equation, under conditions (a)–(c), the smooth function fr(x,λ,ρ) approximates to the classical augmented Lagrangian function L(x,λ,ρ) as r approaches to zero, that is,
(2.8)limr→0+fr(x,λ,ρ)=L(x,λ,ρ)=f(x)+ρ2[φ(x)+λρ]2-λ22ρ.Based on the smooth augmented Lagrangian functionfρ(x,β,r), we present the following smooth augmented Lagrangian algorithm.Algorithm 2.1.
Setx0∈Rn,  r0>0,  ε0>0,  ρ0>0,  λ0∈(0,min{1/r0,1/ε0}],  k:=0.
Step  1. Compute
(2.9)xk∈argminx∈Rnfrk(x,λk,ρk).
Otherwise, seek on inexact global optimal solution xk satisfying
(2.10)frk(xk,λk,ρk)≤infx∈Rnfrk(x,λk,ρk)+εk.Step  2.  Set rk+1=(1/2)rk, εk+1=(1/2)εk,
(2.11)ρk+1={ρk,xk∈Rεk;2ρk,xk∉Rεk,λk+1∈(0,min{1rk+1,1εk+1}].Step  3.  Set k:=k+1, go back step 1.Sincef(x) is bounded below and ϕ(·) is nonnegative, an inexact solution satisfying (2.10) always exists. Thus Algorithm 2.1 is feasible.


## 3. Convergence Properties

In this section, by using a perturbation theorem of Algorithm2.1, we will obtain a global convergence property, a sufficient and necessary condition that Algorithm 2.1 forces the sequence of objective functions convergence to the optimal value of SIP (1.1). To prove the perturbation theorem, we first give the following two lemmas.LetΩ+(x)={s∈Ω∣g(x,s)>0}, Ω0(x)={s∈Ω∣g(x,s)=0}, Ω-(x)={s∈Ω∣g(x,s)<0}.Lemma 3.1.
Suppose that the point sequence{xk} is generated by Algorithm 2.1. Then for any ε>0, there exists a positive integer k0 such that xk∈Rε, for all k>k0.Proof.
Case  1. When k→+∞, ρk tends to a finite number. From Algorithm 2.1, there exists a positive integer N1 such that xk∈Rεk for all k>N1. Notice that εk→0, so for any ε>0, there exists a positive integer N2 such that εk<ε for all k>N2. Therefore, when k>max{N1,N2}, we have xk∈Rεk⊆Rε.
Case  2. When k→+∞, ρk→+∞. We suppose that the conclusion does not hold. Then for ε¯>0, there exists an infinite subsequence K⊆N={1,2,3,…} such that xk∉Rε¯ for all k∈K, that is,
(3.1)∫Ω‍[g(xk,s)]+dμ(s)>ε¯.
Since εk→0, for the above ε¯>0, there exists a positive integer N3 such that εk<ε¯ for all k>N3. Then using (2.10) in Algorithm 2.1, we have
(3.2)frk(xk,λk,ρk)≤infx∈Rnfrk(x,λk,ρk)+ε¯.
Therefore by (3.1), (3.2), and ϕ(t) satisfying (a)-(b), for any k∈K, k>N3, we derive that
(3.3)infx∈Rnfrk(x,λk,ρk)+ε¯≥frk(xk,λk,ρk)=f(xk)+ρk2[rk∫Ω‍ϕ(g(xk,s)rk)dμ(s)+λkρk]2-λk22ρk≥f(xk)+ρk2[rk∫Ω+(xk)‍ϕ(g(xk,s)rk)dμ(s)+λkρk]2-λk22ρk≥f(xk)+ρk2[∫Ω+(xk)‍g(xk,s)dμ(s)+λkρk]2-λk22ρk≥f(xk)+ρk2[ε¯+λkρk]2-λk22ρk≥f(xk)+ρk2ε¯2.
Note that {f(xk)} is bounded below and ρk→+∞(k→+∞), then we can obtain that
(3.4)f(xk)+ρk2ε¯2⟶+∞,(k∈K,k⟶+∞),
that is, infx∈Rnfrk(x,λk,ρk)→+∞(k∈K,k→+∞). However, on the other hand, since R0≠∅, we can choose x¯∈R0; by the choice of rk, ρk, λk in Algorithm 2.1 and the properties of ϕ, we obtain that
(3.5)infx∈Rnfrk(x,λk,ρk)≤frk(x¯,λk,ρk)=f(x¯)+ρk2[rk∫Ω‍ϕ(g(x¯,s)rk)dμ(s)+λkρk]2-λk22ρk≤f(x¯)+ρk2[rk∫Ω‍ϕ(0)dμ(s)+λkρk]2-λk22ρk=f(x¯)+ρk2rk2(ϕ(0)μ(Ω))2+λkrkϕ(0)μ(Ω)≤f(x¯)+ρ0r02(ϕ(0)μ(Ω))2+r0ϕ(0)μ(Ω).
This indicates that infx∈Rnfrk(x,λk,ρk) has an upper bound. It is in contradiction with infx∈Rnfrk(x,λk,ρk)→+∞(k∈K,k→+∞).By using Lemma3.1, we have the following Lemma 3.2.Lemma 3.2.
Suppose that the point sequence{xk} is generated by Algorithm 2.1. Then for every accumulation point x* of {xk}, one has x*∈R0.Theorem 3.3.
Suppose that the sequence{xk} is generated by Algorithm 2.1, then(i)
limk→∞f(xk)=limε→0+θf(ε);(ii)
limk→∞frk(xk,λk,ρk)=limε→0+θf(ε);(iii)
limk→∞(ρk/2)[rk∫Ω‍ϕ(g(xk,s)/rk)dμ(s)+λk/ρk]2-λk2/2ρk=0.Proof.
Sinceθf(ε) is monotonically decreasing with respect to ε>0 and has below bound, we know limε→0+θf(ε) exists and is finite. By Algorithm 2.1, we have εk↓0. Then
(3.6)limk→+∞θf(εk)=limε→0+θf(ε).
Taking δk>0 and δk→0(k→+∞), by the definition of infimum, there exists zk∈Rεk such that
(3.7)f(zk)≤θf(εk)+δk.
Since zk∈Rεk, that is, ∫Ω‍[g(zk,s)]+dμ(s)≤εk.
On the other hand, by Lemma3.1, for any ε>0, when k is sufficiently large, we have
(3.8)xk∈Rε.
Since ϕ(t) satisfies conditions (a) and (c), we obtain
(3.9)limt→+∞ϕ(t)-ϕ(0)t=limt→+∞ϕ(t)t=1,limt→0+ϕ(t)-ϕ(0)t=limt→0+ϕ′(t)=ϕ′(0).
Therefore, there exists M>0 such that
(3.10)ϕ(t)≤Mt+ϕ(0),
for any t≥0. As stated previously, by the choice of rk, εk, ρk, and λk in Algorithm 2.1, (3.7), (3.8), and (3.10) derive that for any ε>0,
(3.11)θf(ε)≤f(xk)≤f(xk)+ρk2[rk∫Ω‍ϕ(g(xk,s)rk)dμ(s)+λkρk]2-λk22ρk≤infx∈Rnfrk(x,λk,ρk)+εk≤f(zk)+ρk2[rk∫Ω‍ϕ(g(zk,s)rk)dμ(s)+λkρk]2-λk22ρk+εk≤θf(εk)+δk+ρk2[rk∫Ω‍ϕ(g(zk,s)rk)dμ(s)+λkρk]2-λk22ρk+εk≤θf(εk)+δk+ρk2[Mεk+rkϕ(0)μ(Ω)+λkρk]2-λk22ρk+εk≤θf(εk)+δk+ρk2(max{rk,εk}(M+ϕ(0)μ(Ω)))2+λkmax{rk,εk}(M+ϕ(0)μ(Ω))+εk≤θf(εk)+δk+ρ02max{r0,ε0}(M+ϕ(0)μ(Ω))2max{rk,εk}+(M+ϕ(0)μ(Ω))max{rk,εk}+εk.
From the above inequalities and (3.6), noticing that rkεk→0(k→∞), for any ε>0, we have
(3.12)θf(ε)≤liminfk→+∞f(xk)≤limsupk→+∞f(xk)≤limsupk→+∞{f(xk)+ρk2[rk∫Ω‍ϕ(g(xk,s)rk)dμ(s)+λkρk]2-λk22ρk}≤limk→+∞θf(εk)=limε→0+θf(ε).
Then limε→0+θf(ε)=limk→+∞f(xk)=limsupk→+∞{f(xk)+ρk2[rk∫Ω‍ϕ(g(xk,s)/rk)dμ(s)+λk/ρk]2-λk2/2ρk}. So the conclusions (i)–(iii) hold.Now, we prove the global convergence of Algorithm2.1.Corollary 3.4.
Suppose that the point sequence{xk} is generated by Algorithm 2.1. Then every accumulation point of {xk} is the optimal solution of the problem (1.1).Proof.
Letx* be an accumulation point of {xk}; from Lemma 3.2, we have
(3.13)x*∈R0.
By the conclusion (i) of Theorem 3.3 and (3.13), we obtain
(3.14)limε→0+θf(ε)=limk→∞f(xk)=f(x*)≥θf(0).
Then we get f(x*)=θf(0), because (3.14) and θf(ε) are upper semi-continuous at the point ε=0.By using Theorem3.3, we have the following Corollary 3.5.Corollary 3.5.
lim
k
→
∞
f
(
x
k
)
=
θ
f
(
0
) if and only if θf(ε) is lower semi-continuous at the point ε=0.


## 4. Numerical Results

To give some insight into the behavior of the algorithm presented in this paper. It is implemented in Matlab 7.0.4 and runs are made on AMD Athlon(tm)64×2 Dual Core Processor 4800+ with CPU 2.50 GHz and 1.87 GB memory. Tables 1 and 2 show the computational results of the corresponding problems with the following items: k: number  of  iterations;x0: starting  point;ϕ(t): smoothing  function;xk: the  final  iteration  point;λk: the  final  Lagrangian  multiplier;f(xk): the  function  value  of f(x) at  the  final xk.Table 1
Numerical results of Example4.1.
k
ϕ
(
t
)
x
k
λ
k
f
(
x
k
)
26
log
(
1
+
e
t
)
(−0.0968, 0.0938)
367.2453
2.1982
30
(
1
/
2
)
(
t
+
t
2
+
4
)
(−0.0959, 0.0947)
923.9.40
2.1993
19
e
t
(−0.0953, 0.0953)
6.1129
2.1999Table 2
Numerical results of Example4.2.
n
k
ϕ
(
t
)
x
k
λ
k
f
(
x
k
)
3
17
log
(
1
+
e
t
)
(0.0839, 0.4494, 1.0105)
18.5016
0.6472
3
16
(
1
/
2
)
(
t
+
t
2
+
4
)
(0.0839, 0.4494, 1.0108)
18.5869
0.6472
3
16
e
t
(0.0873, 0.4248, 1.0460)
12.3942
0.6484
6
16
log
(
1
+
e
t
)
(0.00, 1.03, −0.25, 1.24, −1.39, 0.94)
5.3234
0.6161
6
17
(
1
/
2
)
(
t
+
t
2
+
4
)
(−0.00, 1.03, −0.25, 1.23, −1.39, 0.94)
7.5705
0.6161
6
16
e
t
(−0.00, 1.02, −0.25, 1.24, −1.41, 0.95)
4.1742
0.6161
8
17
log
(
1
+
e
t
)
(−0.00, 1.00, −0.06, 0.77, −1.49, 2.77, −2.41, 0.96)
4.3033
0.6157
8
18
(
1
/
2
)
(
t
+
t
2
+
4
)
(−0.00, 1.00, −0.06, 0.77, −1.47, 2.78, −2.40, 0.96)
7.0902
0.6157
8
16
e
t
(0.00, 1.00, −0.06, 0.78, −1.49, 2.78, −2.42, 0.97)
3.3116
0.6158The parameters used in the Algorithm2.1 are specified as follows:
(4.1)r0=1,ε0=1,ρ0=1,λ0=1,λk+1=min{λk+ρkrk∫Ω‍ϕ(g(xk,s)rk)dμ(s),103}.Example 4.1 (see [18]).
Consider the following:(4.2)min1.21exp(x1)+exp(x2)s.t.s-exp(x1+x2)≤0,∀s∈[0,1].
We choose the starting point x0=(0,0). This example has the optimal solution x*=(-ln1.1,ln1.1).Example 4.2 (see [18]).
Consider the following:(4.3)min∑i=1n‍xi/is.t.tans-∑i=1n‍xisi-1≤0,∀s∈[0,1],
for n=3, 6, and 8. We choose zero vectors as the starting points.Throughout the computational experiments, we use trust region method for solving an unconstrained optimization subproblem at each step. For the corresponding trust region subproblem, we directly use the trust function in Matlab toolbox. The test results of Example4.1 are summarized in Table 1. We test the three cases for ϕ(t)=log(1+et), ϕ(t)=(1/2)(t+t2+4) and ϕ(t)=et, which are, respectively, used as the smoothing approximation functions. k denotes the number of the iteration, λk denotes the approximate Lagrangian multiplier at the final iteration, and xk and f(xk) are the approximate solution and the objective function at the final iteration. For Example 4.2, we test the results when n=3, n=6, and n=8 in Table 2. Numerical results demonstrate that augmented Lagrangian algorithm established in this paper is a practical and effective method for solving semi-infinite programming problem.



---

*Source: 145083-2012-10-11.xml*