# A Spline Smoothing Newton Method for Semi-Infinite Minimax Problems

Authors: Li Dong; Bo Yu; Yu Xiao
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Based on discretization methods for solving semi-infinite programming problems, this paper presents a spline smoothing Newton method for semi-infinite minimax problems. The spline smoothing technique uses a smooth cubic spline instead of max function and only few components in the max function are computed; that is, it introduces  an active set technique, so it is more efficient for solving large-scale minimax problems arising from the discretization of semi-infinite minimax problems. Numerical tests show that the new method is very efficient.


---

## Body

## 1. Introduction

In this paper, we consider the following semi-infinite minimax problems:(1)(P)min⁡x∈Rnmax⁡y∈Y⁡ψ(x,y),
where ψ:Rn×Rm→R. We assume (as in Assumption  3.4.1 in [1]) that both ψ(·,·) and ∇xψ(·,·) are Lipschtiz continuous on bounded sets. Such a semi-infinite minimax problem P is an exciting part of mathematical programming. It has very widespread application backgrounds in optimal electronic circuit design, linear Chebyshev approximation, minimization of floor area, optimal control, computer-aided design, numerous engineering problems, and so forth (see [1–8]). Over the past decade, many researchers had done a lot of works on it and proposed some algorithms (see [9–14]). However, efficient algorithms for solving the problem P are few, because it is difficult to design an algorithm to deal with the nondifferentiability of objective function and the infinite set Y. A common approach for solving P is the discretization method. Generally, discretization of multidimensional domains gives rise to minimax problems with thousands of component functions. Computation cost is increased; efficiency of the discretization method is affected. To overcome these problems, Polak et al. proposed algorithms with smoothing techniques for solving finite and semi-infinite minimax problems (see [15, 16]). In [16], an active set strategy which can be used in conjunction with exponential (entropic) smoothing for solving large-scale minimax problems arising from the discretization of semi-infinite minimax problems had been proposed. But the active set grew monotonically. In this paper, using the feedback precision-adjustment smoothing parameter rule which was proposed by Polak et al. in [15], we propose a new discretization smoothing algorithm for solving P. The smoothing function is cubic spline function not exponential function in our algorithm. The spline smoothing technique uses a smooth spline function instead of thousands of component functions and acts also as an active set technique, so only few components in the max function are computed at each iteration. And the active set does not grow monotonically; hence the number of gradients and Hessian calculations is dramatically reduced, and the computation cost is greatly reduced. Numerical tests show that the new method is very efficient for semi-infinite minimax problems with complicated component functions.We assume that the problemP can be approximated by a sequence of finite minimax problems of the form
(2)(PYN)min⁡x∈Rnmax⁡y∈YN⁡ψ(x,y),
where the sets YN, N=1,2,3,… have finite cardinality. In practice, we can expect that YN⊂YN+1, that is, that they grow monotonically, and that the closure of ∪N=1∞YN is equal to Y. However, it suffices to assume, as in Assumption  3.4.2 in [1].Assumption 1.
There exist a strictly positive valued, strictly monotone decreasing functionΘ:N→R and constants K>0 and N0>0, such that for every N>N0 and y∈Y, there exists a y′∈YN such that
(3)∥y-y′∥≤KΘ(N).
It is easy to satisify with Assumption1. For example, let Y=[a,b],YN=[a,a+(b-a)/2N,a+2((b-a)/2N),…,a+(2N-1)((b-a)/2N),b],Θ(N)=1/(2N-1),K=1/2∥Y∥=(1/2)(b-a).
We assume thatYN={yN1,…,yNqN}.
Next, we let(4)fNj(x)≜ψ(x,yNj),j∈QN={1,2,…,qN},
and define
(5)ϕ(x)=max⁡y∈Y⁡ψ(x,y),ϕN(x)=max⁡j∈QN⁡fNj(x),
and with this notation, the problems PYN assume the form
(6)(PN)min⁡x∈Rn⁡ϕN(x).
The optimality functionsρN for the problems PN are defined by
(7)ρN(x)≜-min⁡λ∈Σ⁡{∑j∈QNλj[ϕN(x)-fNj(x)]mmmmi+12∥∑j∈QNλj∇fNj(x)∥2},
where Σ≜{λ∈RQN∣λj≥0,∑j∈QNλj=1}.
In [1], we find the following result.Theorem 2.
Suppose thatx^ is an optimal solution to problems PN; then, ρN(x^)=0.The corresponding optimality function forP is defined (see Theorem  3.1.6 in [1]) by
(8)ρ(x)=-min⁡η∈F¯ϕ(x)⁡{η0+12∥η∥2},
where
(9)F¯ϕ(x)=convy∈Y{(ϕ(x)-ψ(x,y)∇xψ(x,y))}.Referring to Lemma  3.4.3 in [1], we see that, under Assumption 1, the following result must hold.Theorem 3.
Suppose that{xN}N=0∞ is a sequence in Rn converging to a point x^. Then, ϕN(xN)→ϕ(x^) and ρN(xN)→ρ(x^) as N→∞.In this paper, we consider to approximate uniformlyϕN(x) by the smooth spline introduced in [17].Let us first recall the formulation of multivariate spline. LetD be a polyhedral domain of RqN which is partitioned with irreducible algebraic surfaces into cells Δ={Δi∣i=1,…,N}. A function s(z) defined on D is called a k-spline function with rth order smoothness, expressed for short as s(z)∈Skr(D,Δ), if s(z)∈Cr(D) and s(z)|Δi=pi∈Pk, where Pk is the set of all polynomials of degree k or less in qN variables. Similar to the smooth spline which approximates uniformly min⁡{z1,z2,…,zqN} given in [17], we can construct a spline function s32(z;ɛ)∈S32(RqN,ΔMS2) to approximate uniformly max⁡{z1,z2,…,zqN} (as ɛ→+0), where ΔMS2 is the homogenous Morgan-Scott partition of type two in [17], as follows:
(10)s32(z1,z2,…,zqN;ɛ)=zi1+∑l=1k-1cl(lzil+1-∑j=1l‍zij+ɛ)3,mmmmmimforz∈Δi1,…,ik(ɛ),
where c1=1/(6ɛ2),ck/ck+1=(k+2)/k, 1≤k≤qN, and the cell Δi1,…,ik(ɛ) is the region defined by the following inequalities:
(11)zil-zil+1≥0,when1≤l<k,(k-1)zik-∑j=1k-1‍zij+ɛ≥0,kzil-∑j=1k‍zij+ɛ≤0,whenk+1≤l≤qN.
The composite function γqN,tN(x) approximates uniformly ϕN(x) as tN→+0, where
(12)γqN,tN(x)=s32(f1(x),f2(x),…,fqN(x);tN),forxsuchthat(f1(x),f2(x),…,fqN(x))∈Δi1,…,ik(tN).Proposition 4.
Suppose thattN>0. For any x∈Rn, we define
(13)Ω^(x)≜{j∈QN∣fNj(x)=ϕN(x)}.
If the function fj(·)is continuous, then γqN,tN(·) is continuous and is increasing with respect to tN. Furthermore,
(14)ϕN(x)+tN3(1-1|Ω^(x)|)≤γqN,tN(x)≤ϕN(x)+tN3(1-1k),
where |Ω^(x)| denotes the cardinality of Ω^(x).Proof.
s
3
2
(
z
1
,
z
2
,
…
,
z
q
N
;
ɛ
) is twice continuously differentiable and if the functions fj(·),j∈QN are continuous, it is easy to know that γqN,tN(·) is continuous. From Lemma  1.1 in [18], we know γqN,tN(·) is increasing with respect to tN.
According to (12), we have
(15)γqN,tN(x)=fNi1(x)+c1(fNi1(x)-fNi2(x)+tN)3+⋯+c|Ω^(x)|(|Ω^(x)|fNi|Ω^(x)|+1(x)mmmi-(fNi1(x)+⋯+fNi|Ω^(x)|(x))+tN)3+⋯+ck-1((k-1)fNik(x)mmmmimim-(fNi1(x)+⋯+fNik-1(x))+tN)3.
From the definition of Ω^(x), we know (l-1)fNil(x)-(fNi1(x)+⋯+fNil-1(x))+tN=tN,1≤l≤|Ω^(x)|. From the definition of Δi1,…,ik(tN), we know tN≥(l-1)fNil(x)-(fNi1(x)+⋯+fNil-1(x))+tN≥0,1≤l<k. Then, we have
(16)fNi1(x)+∑l=1|Ω^(x)|-1cltN3≤γqN,tN(x)≤fNi1(x)+∑l=1k-1cltN3.
By cl/cl+1=(l+2)/l, we can obtain cl=(2/(l(l+1)))c1=1/(3l(l+1)tN2). Thus ∑l=1|Ω^(x)|-1cltN3=(tN/3)(1-(1/|Ω^(x)|)) and ∑l=1k-1‍cltN3=(tN/3)(1-(1/k)) and fNi1(x)=ϕN(x). Hence the desired result follows.The following proposition is proved in [19].Proposition 5.
(1) If all the functionsfNj(·),j∈QN are continuously differentiable, then γqN,tN(·) is continuously differentiable and
(17)∇xγqN,tN(x)=∑i=1qN‍λqN,tNi(x)∇xfNi(x)=∑j=1k‍λqN,tNij(x)∇xfNij(x),
where
(18)λqN,tNij(x)={1-3∑l=1k-1‍cl(hl(x,tN))2,forj=1,3(j-1)cj-1(hj-1(x,tN))2-3∑l=jk-1‍cl(hl(x,tN))2,for2≤j<k,3(k-1)ck-1(hk-1(x,tN))2,forj=k,0,fork<j≤qN,
and hl(x,tN)=lfNil+1(x)-∑r=1lfNir(x)+tN.
(2) For anyx∈Rn and tN>0, λqN,tNij(x)∈[0,1), ij∈QN and ∑ij∈QNλqN,tNij(x)=1.
(3) If all the functions,fNj(·),j∈QN, are twice continuously differentiable, then γqN,tN(·) is twice continuously differentiable and
(19)∇xx2γqN,tN(x)=∑j=1k‍λqN,tNij(x)∇xx2fNij(x)+∑j=1k‍(∑ȷ˘=1k‍λqN,tNij,ȷ˘(x)∇xfNiȷ˘(x))×(∇xfNij(x))T,
where
(20)λqN,tNi1,ȷ˘(x)={6∑l=1k-1‍cl(hl(x,tN))mwhenȷ˘=1,-6(ȷ˘-1)cȷ˘-1(hȷ˘-1(x,tN))+6∑l=ȷ˘k-1‍cl(hl(x,tN))when2≤ȷ˘<k,-6(k-1)ck-1(hk-1(x,tN))whenȷ˘=k,λqN,tNij,ȷ˘(x)={-6(j-1)cj-1(hj-1(x,tN))+6∑l=jk-1‍cl(hl(x,tN))when1≤ȷ˘<j,-6(ȷ˘-1)cȷ˘-1(hȷ˘-1(x,tN))+6∑l=ȷ˘k-1‍cl(hl(x,tN))whenj<ȷ˘<k,6(ȷ˘-1)2cȷ˘-1(hȷ˘-1(x,tN))+6∑l=ȷ˘k-1‍cl(hl(x,tN))whenȷ˘=j,-6(k-1)ck-1(hk-1(x,tN))mmmmmmmmmmmwhenȷ˘=k,for2≤j<k,λqN,tNik,ȷ˘(x)={-6(k-1)ck-1(hk-1(x,tN))when1≤ȷ˘<k,6(k-1)2ck-1(hk-1(x,tN))whenȷ˘=k.From Proposition5, we obtain the following results.Corollary 6.
For anyx∈Rn and ij∈QN,
(21)lim⁡tN→0λqN,tNij(x)={1|Ω^(x)|,ifij∈Ω^(x),0,mimifij∉Ω^(x),lim⁡tN→0∇xγqN,tN(x)=∑j∈Ω^(x)‍1|Ω^(x)|∇xfj(x).Proof.
According to the definition ofΔi1,…,ik(tN), we know that k→|Ω^(x)| as tN→0. From Proposition 5 (1), we know
(22)lim⁡tN→0λqN,tNi1(x)=1-3∑l=1|Ω^(x)|-1‍cltN2=1-3∑l=1|Ω^(x)|-1‍13l(l+1)tN2tN2=1|Ω^(x)|.
If ij∈Ω^(x),(1<j<k), then
(23)lim⁡tN→0λqN,tNij(x)=3(j-1)cj-1tN2-3∑l=j|Ω^(x)|-1‍cltN2=3(j-1)13(j-1)jtN2tN2-3∑l=j|Ω^(x)|-1‍13tN2(1l-1l+1)tN2=1|Ω^(x)|.
If ik∈Ω^(x), then k=|Ω^(x)|. That is
(24)lim⁡tN→0λqN,tNik(x)=3(|Ω^(x)|-1)c|Ω^(x)|-1tN2=1|Ω^(x)|.
Then, lim⁡tN→0λqN,tNij(x)=1/|Ω^(x)|,ij∈Ω^(x).
Ifij∉Ω^(x),(1<j<k), then lim⁡tN→0λqN,tNij(x)=0.
It now follows from (21) and (17) that (21) holds. The proof is completed.Next, let{tN}N=1∞ be an infinite sequence such that tN→0, as N→∞, and consider the sequence of approximating problems
(25)(PqN,tN)min⁡x∈Rn⁡γqN,tN(x),N=1,2,3,…,
with γqN,tN(x) defined as in (12).Theorem 7.
The problems(PqN,tN) epiconverge to the problem P.Proof.
Referring to Theorem  3.3.2 in [1], we see that to prove the theorem it is sufficient to show that if {xN}N=1∞ is a sequence in Rn converging to a point x^, then γqN,tN(x)→ϕ(x^).
Thus, suppose thatxN→x^ as N→∞. Then,
(26)|γqN,tN(xN)-ϕ(x^)|≤|γqN,tN(xN)-ϕN(xN)|+|ϕN(xN)-ϕ(x^)|.
Now, by Theorem 2, ϕN(xN)-ϕ(x^)→0 as N→∞, and, since by assumption of tN→0, as N→∞, it follows from (14) that γqN,tN(xN)-ϕN(xN)→0 as N→∞, which completes our proof.


## 2. Spline Smoothing Newton Method and Its Convergence

We combine Algorithm  3.1 in [18] with a discretization precision test to produce an algorithm for solving the semi-infinite minimax problems P. The Hessian ∇xx2γqN,tN(x) of the smoothing spline function γqN,tN(x) can be modified by adding a multiple of the identity introduced in [20]; that is,
(27)BqN,tN(x)=θ(x)I+∇xx2γqN,tN(x),
where θ(x)=max⁡{0,ϑ-e(x)} with e(x) denoting the minimum eigenvalue of ∇xx2γqN,tN(x) and ϑ>0.Algorithm 8.
Data.Given x(0)∈Rn, a monotone increasing sequence of sets {YN}N=0∞, YN={y1,y2,…,yqN}, of cardinality qN, with qN→∞ as N→∞, satisfying Assumption 1, and defining the functions fNj(x)=ψ(x,yNj),j=1,2,…,qN, a sequence of monotone decreasing parameters {πN}N=0∞>0, such that πN→0 as N→∞, ϑ>0, and δ>0. Functions ϵa(t),ϵb(t),τ(t): (0,∞)→(0,∞), satisfying ϵb(t)≥ϵa(t)>τ(t), for all t>0, t^≫1, κ1∈(0,1),κ2≫1,0<κ3≪1.Parameter. Set α,β∈(0,1).Step
0. Set N=0.Step
1. Set i=0,t0=πN,k=0,s=1,l=9,xk,i=x(0).Step
2. Let I¯={j∣max⁡{fN1(xk,i),…,fNqN(xk,i)}-fNj(xk,i)<tk}; let k¯ be the cardinality of I¯, and I¯={i1,i2,…,ik¯}. Range {fNij(xk,i)}j=1k¯ according to fNi1(xk,i)≥fNi2(xk,i)≥⋯≥fNik¯(xk,i).Ifk¯=1, the cell is Δi1(tk).Else if(k~-1)fNik~(x(k,i))-∑j=1k~-1‍fNij(x(k,i))+tk≥0, for every k~∈{k¯,k¯-1,…,2}, we have k~∈I⊆{k¯,k¯-1,…,2}. Let k^ be the maximum element of I; then the cell is Δi1,…,ik^(tk).Step
3. Compute ∇xγqN,tk(xk,i). If ∥∇xγqN,tk(xk,i)∥2>τ(tk), go to Step  4. Else go to Step  9.Step
4. Compute BqN,tk(xk,i) according to (27); then compute Cholesky factor R such that BqN,tk(xk,i)=RRT and the reciprocal condition number c(R) of R.Ifc(R)≥κ1 and tk≥κ3, go to Step  5.Else ifc(R)≥κ1 and the largest eigenvalue σtk,max⁡(xk,i) of BqN,tk(xk,i) satisfies σtk,max⁡(xk,i)≤κ2, go to Step  5.Else go to Step  6.Step
5. Compute the search direction
(28)hk,i=-BqN,tk(xk,i)-1∇xγqN,tk(xk,i);
go to Step  7.Step
6. Compute the search direction
(29)hk,i=-∇xγqN,tk(xk,i).Step
7. Compute the step length λk,i=βl, where l≥0 is the smallest integer satisfying
(30)γqN,tk(xk,i+βlhk,i)-γqN,tk(xk,i)≤αβl〈∇xγqN,tk(xk,i),hk,i〉.Step
8. Set xk,i+1=xk,i+λk,ihk,i, i=i+1. Go to Step  2.Step
9. If s=1, compute t* such that
(31)ϵa(tk)≤∥∇xγqN,t*(xk,i)∥2≤ϵb(tk);
go to Step  10.Else settk+1=1/s(k+2), k=k+1, and i=0; go to Step  2.Step
10. If t*≥t^, set tk+1=min⁡{t*,tk/(tk+1)}, k=k+1, and i=0; go to Step  2. Else set s=max⁡{2,((1/t^)+2)/(k+1)}, tk+1=1/s(k+2), k=k+1, and i=0; go to Step  2.Step
11. If
(32)12∥∇xγqN,tk(xk,i)∥2≤δ,∑j=1qN‍λqN,tkj(xk,i)[ϕN(xk,i)-fNj(xk,i)]≤δ,
where the λqN,tkj(xk,i) are defined by (17), set ξN=xk,i, tN=tk, replace N by N+1, δ by δ/2, and go to Step  1.Else go to Step  1.Theorem 9.
Suppose that{ξN}N=0∞ is a sequence constructed by Algorithm 8. Then, any accumulation point ξ^ of this sequence satisfies θ(ξ^)=0.Proof.
First note that it follows from Corollary6 that condition (32) will be eventually satisfied, since Algorithm 8 keeps abating tk. Next, note that
(33)-∑j=1qN‍λqN,tNj[ϕN(ξN)-fNj(ξN)]mn-12∥∇xγqN,tN(ξN)∥2≤ρN(ξN)≤0.
Since by construction
(34)-∑j=1qN‍λqN,tNj[ϕN(ξN)-fNj(ξN)]mm-12∥∇xγqN,tN(ξN)∥2⟶0,asN⟶∞,
and ρN(ξN)→kρ(ξ^) on any infinite subsequence {ξN}N∈K that converges to ξ^, the desired result follows.


## 3. Numerical Experiment

We have implemented Algorithm8 using Matlab. In order to show the efficiency of the algorithm, we also have implemented algorithm in [16] (denote PWY) using similar procedures. Algorithm PWY was proposed by Polak et al. in [16], which has been introduced in Section 1.The test results were obtained by running Matlab R2011a on a desktop with Windows XP Professional operation system, Intel(R) Core (TM) i3-370 2.40 GHz processor, and 2.92 GB of memory.In Algorithm8, parameters are chosen as follows: α=0.8, β=0.77, t^=105ln⁡qN, κ1=10-7, κ2=1030, κ3=1000t^, τ(t)=min⁡{0.1,1000t/(N+1)2}, (ϵa,ϵb)=(0.01,0.2), ϑ=0.1, δ=1, qN=100·2N+1, and πN=1/(N2+(1/pN)). In the PWY algorithm, parameters are chosen as follows: ɛ=0.1, τ(p)=min⁡{0.1,1000/((N+1)2p)}. The results are listed in Tables 1, 2, 3, 4, and 5. x* denotes the final approximate solution point and ϕ* is the value of the objective function of discretized problems PYN at x*. m is the maximum number of discrete points. Time is the CPU time in seconds.Table 1
Test results for Example1.
m
Method
ϕ
*
Time
x
*
1638401
Algorithm8
2.000062
9.4203
(1.1065,  1.0071,  1.1483,  1.0785,  0.0022,  1.0000)
819201
PWY
2.000056
51.4509
(0.9586,  1.0027,  1.1604,  1.0501,  −0.0023,  0.9999)Table 2
Test results for Example2.
m
Method
ϕ
*
Time
x
*
1
638401
Algorithm8
0.948184
5.8026
(−4.9016, 0.0002, 1.0046, −0.1800)
1638401
PWY
0.948046
14.8421
(−4.7261, −0.0000, 1.0000, −0.1472)Table 3
Test results for Example3.
m
Method
ϕ
*
Time
x
*
8
19201
Algorithm8
4.999999
1.5466
(2.0363, 1.9958, 0.0095, 1.5724)
819201
PWY
5.000483
18.2670
(1.4796, 1.3277, 0.62892, 1.5704)Table 4
Test results for Example4.
m
Method
ϕ
*
Time
x
*
6
553601
Algorithm8
-
0.999999
3.6721
(0.0000, −44.0111)
3276801
PWY
-
0.999986
86.8183
(−0.0036, −44.0000)Table 5
Test results for Example5.
m
Method
ϕ
*
Time
x
*
2
560000
Algorithm8
1.828804
2.8550
(0.5548, 0.6475, 0.5946, 0.7662)
640000
PWY
1.828698
4.1854
(0.5556, 0.6497, 0.5971, 0.7684)Example 1 (see [21]).
Letx=(x1,x2,x3,x4,x5,x6)∈R6(35)ϕ(x,y)=x12exp⁡(-x2y)cos⁡2(x3y+x4)-cos⁡(y)+x22x32exp⁡(-x1y)sin2(x2y)+exp⁡((1-x6)2y)+x52,Y=[0,10].Example 2 (see [21]).
Letx=(x1,x2,x3,x4)∈R4(36)ϕ(x,y)=(x1+x12+cos⁡⁡(y)+4)×ln⁡(siny+exp⁡(cos⁡x1+x22))+(exp⁡(-y)-x3+yx41+x32)2,Y=[0,10].Example 3.
Letx=(x1,x2,x3,x4)∈R4(37)ϕ(x,y)=x22x32exp⁡(-x1y)sin2(x2y)-x1cos⁡(y)-x4sin(y)+5,Y=[0,2π].Example 4.
Letx=(x1,x2)∈R2(38)ϕ(x,y)=x12+2x1y2+ex1+x2-ey,Y=[0,10].Example 5.
Letx=(x1,x2,x3,x4)∈R4(39)ϕ(x,y)=(y1-x1)2x32+(y2-x2)2x42-1,Y=[0,1]×[0,1].


## 4. Conclusion

We have developed a spline smoothing Newton method for the solution of semi-infinite minimax problems using smooth cubic spline and discretization strategy. At each iteration, only few components in the max function are computed; hence, the computation cost is greatly reduced. For semi-infinite minimax problems with complicated component functions, numerical tests show that the new method is very efficient.



---

*Source: 852074-2014-07-17.xml*