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.

1. Introduction

We consider the semi-infinite programming (SIP):

()

where X = {x ∈ Rⁿ∣g(x, s) ≤ 0, for all s ∈ Ω}, the functions f : Rⁿ → R and g : Rⁿ × R^m → R are continuously differentiable. Ω ⊂ R^m is a nonempty bounded and closed domain. In this paper, we assume that

()

This assumption is very mild, because the objective function f(x) can be replaced by e^f(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 given x ∈ Rⁿ and s ∈ Ω, let

()

Define φ : Rⁿ → R by

()

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:

()

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 l₁ 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 Section 3, 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:

()

Then R₀ is the feasible set of SIP (1.1). Let

be the set of optimal solutions of SIP (1.1). We assume that

in this paper.

The perturbation function is defined as follows:

()

Thus the optimal value of SIP (1.1) is

()

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

()

where λ is the Lagrangian multiplier and ρ is the penalty parameter. On base of it, we introduce a class of smooth augmented Lagrangian function:

()

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 any t > 0, ϕ(t) ≥ t;
(c)
lim _t→+∞ (ϕ(t)/t) = 1.

It is easy to check that there are many continuously differentiable functions satisfying conditions (a), (b), and (c). For example,

()

Using conditions (a) and (c), for any t ∈ R, we have

()

From the above equation, under conditions (a)–(c), the smooth function f_r(x, λ, ρ) approximates to the classical augmented Lagrangian function L(x, λ, ρ) as r approaches to zero, that is,

()

Based on the smooth augmented Lagrangian function f_ρ(x, β, r), we present the following smooth augmented Lagrangian algorithm.

Algorithm 2.1. Set x₀ ∈ Rⁿ, r₀ > 0, ε₀ > 0, ρ₀ > 0, , k : = 0.

Step 1. Compute

()

Otherwise, seek on inexact global optimal solution x_k satisfying

()

Step 2. Set r_k+1 = (1/2)r_k, ε_k+1 = (1/2)ε_k,

()

Step 3. Set k : = k + 1, go back step 1.

Since f(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 Algorithm 2.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}, Ω₀(x) = {s ∈ Ω∣g(x, s) = 0}, Ω₋(x) = {s ∈ Ω∣g(x, s) < 0}.

Lemma 3.1. Suppose that the point sequence {x_k} is generated by Algorithm 2.1. Then for any ε > 0, there exists a positive integer k₀ such that x_k ∈ R_ε, for all k > k₀.

Proof.

Case 1. When k → +∞, ρ_k tends to a finite number. From Algorithm 2.1, there exists a positive integer N₁ such that for all k > N₁. Notice that ε_k → 0, so for any ε > 0, there exists a positive integer N₂ such that ε_k < ε for all k > N₂. Therefore, when k > max {N₁, N₂}, we have .

Case 2. When k → +∞, ρ_k → +∞. We suppose that the conclusion does not hold. Then for , there exists an infinite subsequence K⊆N = {1,2, 3, …} such that for all k ∈ K, that is,

()

Since ε_k → 0, for the above

, there exists a positive integer N₃ such that

for all k > N₃. Then using (2.10) in Algorithm 2.1, we have

()

Therefore by (3.1), (3.2), and ϕ(t) satisfying (a)-(b), for any k ∈ K, k > N₃, we derive that

()

Note that {f(x_k)} is bounded below and ρ_k → +∞(k → +∞), then we can obtain that

()

that is,

. However, on the other hand, since R₀ ≠ ∅, we can choose

; by the choice of r_k, ρ_k, λ_k in Algorithm 2.1 and the properties of ϕ, we obtain that

()

This indicates that

has an upper bound. It is in contradiction with

By using Lemma 3.1, we have the following Lemma 3.2.

Lemma 3.2. Suppose that the point sequence {x_k} is generated by Algorithm 2.1. Then for every accumulation point x^* of {x_k}, one has x^* ∈ R₀.

Theorem 3.3. Suppose that the sequence {x_k} is generated by Algorithm 2.1, then

(i)
;
(ii)
;
(iii)
.

Proof. Since θ_f(ε) is monotonically decreasing with respect to ε > 0 and has below bound, we know exists and is finite. By Algorithm 2.1, we have ε_k ↓ 0. Then

()

Taking δ_k > 0 and δ_k → 0(k → +∞), by the definition of infimum, there exists

such that

()

Since

, that is, ∫_Ω [g(z_k, s)] ₊dμ(s) ≤ ε_k.

On the other hand, by Lemma 3.1, for any ε > 0, when k is sufficiently large, we have

()

Since ϕ(t) satisfies conditions (a) and (c), we obtain

()

Therefore, there exists M > 0 such that

()

for any t ≥ 0. As stated previously, by the choice of r_k, ε_k, ρ_k, and λ_k in Algorithm 2.1, (3.7), (3.8), and (3.10) derive that for any ε > 0,

()

From the above inequalities and (3.6), noticing that r_kε_k → 0(k → ∞), for any ε > 0, we have

()

Then

. So the conclusions (i)–(iii) hold.

Now, we prove the global convergence of Algorithm 2.1.

Corollary 3.4. Suppose that the point sequence {x_k} is generated by Algorithm 2.1. Then every accumulation point of {x_k} is the optimal solution of the problem (1.1).

Proof. Let x^* be an accumulation point of {x_k}; from Lemma 3.2, we have

()

By the conclusion (i) of Theorem 3.3 and (3.13), we obtain

()

Then we get f(x^*) = θ_f(0), because (3.14) and θ_f(ε) are upper semi-continuous at the point ε = 0.

By using Theorem 3.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;
x₀: starting point;
ϕ(t): smoothing function;
x_k: the final iteration point;
λ_k: the final Lagrangian multiplier;
f(x_k): the function value of f(x) at the final x_k.

Table 1. Numerical results of Example 4.1.

k	ϕ(t)	x_k	λ_k	f(x_k)
26	log (1 + e^t)	(−0.0968, 0.0938)	367.2453	2.1982
30		(−0.0959, 0.0947)	923.9.40	2.1993
19	e^t	(−0.0953, 0.0953)	6.1129	2.1999

Table 2. Numerical results of Example 4.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		(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		(−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		(−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.6158

The parameters used in the Algorithm 2.1 are specified as follows:

()

Example 4.1 (see [18].)Consider the following:

()

We choose the starting point x₀ = (0,0). This example has the optimal solution x^* = (−ln 1.1, ln 1.1).

Example 4.2 (see [18].)Consider the following:

()

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 Example 4.1 are summarized in Table 1. We test the three cases for ϕ(t) = log (1 + e^t), and ϕ(t) = e^t, 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 x_k and f(x_k) 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.

Acknowledgments

This work was supported by National Natural Science Foundation under Grants 10971118, 10901096, and 11271226, the Scientific Research Fund for the Excellent Middle-Aged and Youth Scientists of Shandong Province under Grant BS2012SF027, and the Natural Science Foundation of Shandong Province under Grant ZR2009AL019.

References

1 Bhattacharjee B., Lemonidis P., GreenW. H.Jr., and Barton P. I., Global solution of semi-infinite programs, Mathematical Programming. (2005) 103, no. 2, 283–307, https://doi.org/10.1007/s10107%2D005%2D0583%2D6, 2146381, ZBL1090.90188.
10.1007/s10107-005-0583-6
Web of Science® Google Scholar
2 Hettich R. and Kortanek K. O., Semi-infinite programming: theory, methods, and applications, SIAM Review. (1993) 35, no. 3, 380–429, https://doi.org/10.1137/1035089, 1234637, ZBL0784.90090.
10.1137/1035089
Web of Science® Google Scholar
3 Still G., Discretization in semi-infinite programming: the rate of convergence, Mathematical Programming. (2001) 91, no. 1, 53–69, https://doi.org/10.1080/023319340310001637387, 1865262, ZBL1051.90023.
10.1007/s101070100239
Web of Science® Google Scholar
4 Tanaka Y., Fukushima M., and Ibaraki T., A globally convergent SQP method for semi-infinite nonlinear optimization, Journal of Computational and Applied Mathematics. (1988) 23, no. 2, 141–153, https://doi.org/10.1016/0377%2D0427(88)90276%2D2, 959473, ZBL0685.90080.
10.1016/0377-0427(88)90276-2
Web of Science® Google Scholar
5 Hestenes M. R., Multiplier and gradient methods, Journal of Optimization Theory and Applications. (1969) 4, 303–320, 0271809, https://doi.org/10.1007/BF00927673, ZBL0208.18402.
10.1007/BF00927673
Google Scholar
6 Powell M. J. D., R. Fletcher, A method for nonlinear constraints in minimization problems, Optimization, 1969, Academic Press, London, UK, 283–298, 0272403, ZBL0194.47701.
Google Scholar
7 Rockafellar R. T., Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM Journal on Control and Optimization. (1974) 12, 268–285, 0384163, https://doi.org/10.1137/0312021, ZBL0257.90046.
10.1137/0312021
Web of Science® Google Scholar
8 Yang X. Q. and Teo K. L., Nonlinear Lagrangian functions and applications to semi-infinite programs, Annals of Operations Research. (2001) 103, 235–250, https://doi.org/10.1023/A:1012911307208, 1868453, ZBL1002.90074.
10.1023/A:1012911307208
Web of Science® Google Scholar
9 Rückmann J.-J. and Shapiro A., Augmented Lagrangians in semi-infinite programming, Mathematical Programming. (2009) 116, no. 1-2, 499–512, https://doi.org/10.1007/s10107%2D007%2D0115%2D7, 2421291, ZBL1165.90030.
10.1007/s10107-007-0115-7
Web of Science® Google Scholar
10 Li D.-H., Qi L., Tam J., and Wu S.-Y., A smoothing Newton method for semi-infinite programming, Journal of Global Optimization. (2004) 30, no. 2-3, 169–194, https://doi.org/10.1007/s10898%2D004%2D8266%2Dz, 2115699, ZBL1066.90131.
10.1007/s10898-004-8266-z
Web of Science® Google Scholar
11 Qi L., Ling C., Tong X., and Zhou G., A smoothing projected Newton-type algorithm for semi-infinite programming, Computational Optimization and Applications. (2009) 42, no. 1, 1–30, https://doi.org/10.1007/s10589%2D007%2D9117%2Dx, 2471184, ZBL1153.90556.
10.1007/s10589-007-9117-x
Web of Science® Google Scholar
12 Qi L., Shapiro A., and Ling C., Differentiability and semismoothness properties of integral functions and their applications, Mathematical Programming. (2005) 102, no. 2, 223–248, https://doi.org/10.1007/s10107%2D004%2D0523%2Dx, 2124444, ZBL1079.90143.
10.1007/s10107-004-0523-x
Web of Science® Google Scholar
13 Qi L., Wu S.-Y., and Zhou G., Semismooth Newton methods for solving semi-infinite programming problems, Journal of Global Optimization. (2003) 27, no. 2-3, 215–232, https://doi.org/10.1023/A:1024814401713, 2013673, ZBL1033.90137.
10.1023/A:1024814401713
Web of Science® Google Scholar
14 Gugat M. and Herty M., The smoothed-penalty algorithm for state constrained optimal control problems for partial differential equations, Optimization Methods & Software. (2010) 25, no. 4–6, 573–599, https://doi.org/10.1080/10556780903002750, 2724157, ZBL1201.90186.
10.1080/10556780903002750
Web of Science® Google Scholar
15 Birgin E. G., Castillo R. A., and Martínez J. M., Numerical comparison of augmented Lagrangian algorithms for nonconvex problems, Computational Optimization and Applications. (2005) 31, no. 1, 31–55, https://doi.org/10.1007/s10589%2D005%2D1066%2D7, 2143503, ZBL1101.90066.
10.1007/s10589-005-1066-7
Web of Science® Google Scholar
16 Conn A. R., Gould N. I. M., and Toint P. L., A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds, SIAM Journal on Numerical Analysis. (1991) 28, no. 2, 545–572, https://doi.org/10.1137/0728030, 1087519, ZBL0724.65067.
10.1137/0728030
Web of Science® Google Scholar
17 Tseng P. and Bertsekas D. P., On the convergence of the exponential multiplier method for convex programming, Mathematical Programming. (1993) 60, no. 1, 1–19, https://doi.org/10.1007/BF01580598, 1231274, ZBL0783.90101.
10.1007/BF01580598
Web of Science® Google Scholar
18 Conn A. R. and Gould N. I. M., An exact penalty function for semi-infinite programming, Mathematical Programming. (1987) 37, no. 1, 19–40, https://doi.org/10.1007/BF02591681, 881692, ZBL0623.90069.
10.1007/BF02591681
Web of Science® Google Scholar

Citing Literature

All articles

An Augmented Lagrangian Algorithm for Solving Semiinfinite Programming

Abstract

1. Introduction

2. Smooth Augmented Lagrangian Algorithm

3. Convergence Properties

4. Numerical Results

Acknowledgments

References

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

An Augmented Lagrangian Algorithm for Solving Semiinfinite Programming

Abstract

1. Introduction

2. Smooth Augmented Lagrangian Algorithm

3. Convergence Properties

4. Numerical Results

Acknowledgments

References

Citing Literature

References

Related

Information