# An Active Set Smoothing Method for Solving Unconstrained Minimax Problems

Authors: Zhengyong Zhou; Qi Yang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, an active set smoothing function based on the plus function is constructed for the maximum function. The active set strategy used in the smoothing function reduces the number of gradients and Hessians evaluations of the component functions in the optimization. Combing the active set smoothing function, a simple adjustment rule for the smoothing parameters, and an unconstrained minimization method, an active set smoothing method is proposed for solving unconstrained minimax problems. The active set smoothing function is continuously differentiable, and its gradient is locally Lipschitz continuous and strongly semismooth. Under the boundedness assumption on the level set of the objective function, the convergence of the proposed method is established. Numerical experiments show that the proposed method is feasible and efficient, particularly for the minimax problems with very many component functions.


---

## Body

## 1. Introduction

In this paper, we consider the following unconstrained minimax problem:(1)minx∈RnFx=maxj∈Qfjx,where the component functions fj:Rn⟶R, j∈Q=1,…,q, are twice continuously differentiable. Minimax problem (1) is a typical nonsmooth optimization problem and arises in many fields, such as engineering design ([1]), vehicle routing ([2, 3]), structural optimization ([4]), electronic circuit design ([5]), and game theory ([6, 7]).Many methods have been proposed for solving minimax problem (1), such as subgradient methods ([8]), bundle type methods ([9, 10]), cutting plane methods ([11]), sequential quadratic programming methods ([12–14]), interior point methods ([15–17]), conjugate gradient methods ([18]), and smoothing methods ([19–26]). The main advantage of smoothing methods is that the minimax problem is transformed into a sequence of simple, smooth, and unconstrained optimization problems, which can be solved by standard unconstrained minimization solvers.In [27], the following aggregate function (also called the exponential penalty function) induced from Jaynes’ maximum entropy principle was introduced:(2)Ftx=tln∑j∈Qexpfjxt,where t>0 is the smoothing parameter. It approaches Fx uniformly with respect to x∈Rn as the smoothing parameter goes to 0, and has been wildly used in the smoothing methods for solving the minimax problems. Its gradient can be written as follows:(3)∇Ftx=∑j∈Qμtjx∇fjx,with(4)μtjx=expfjx/t∑j∈Qexpfjx/t∈0,1,∑j∈Qμtjx=1,which is a convex combination of the gradients of all the component functions, and its Hessian(5)∇2Ftx=∑j∈Qμtjx∇2fjx+1t∑j∈Qμtjx∇fjx∇fjxT−1t∑j∈Qμtjx∇fjx∑j∈Qμtjx∇fjxT,is a complicated combination of the gradients and Hessians of all component functions. Therefore, for the maximum function with very many nonlinear component functions, the evaluations for the gradient and Hessian of the aggregate function always consume a large amount of computation.For the minimax problems with very many component functions, several active set strategies have been developed for the smoothing methods to reduce the number of gradients or Hessians evaluations of the component functions at each iteration. In [18], the following active set smoothing function for Fx,α=α+∑j∈Qmaxfjx−α,0 was presented:(6)Ftx,α=α+∑j∈Qφfjx−α;t,where t>0 is the smoothing parameter,(7)φz;t=0,z<−t,z+t36t2,−t≤z≤0,z+z−t36t2,0<z≤t,z,z>t.The active set used inFtx,α at x,α∈Rn×R can be written as follows:(8)Qtx,α=j∈Qfjx−α+t>0.In [28], a cubic spline smoothing function for Fx was presented. For any smoothing parameter t>0, the active set used in the cubic spline smoothing function at x∈Rn can be represented as follows:(9)Qtx=j∈QFx−fjx≤t.In [25], an active set strategy for the aggregate function was introduced. For a given ϵ>0, let(10)Qϵx=j∈QFx−fjx≤ϵ.Then, the active setQk used for the aggregate function at xk∈Rn is updated as(11)Q0=Qϵx0,Qk=Qk−1∪Qϵxk,k≥1.In [26], another active set strategy for the aggregate function was presented. For any smoothing parameter t>0, the active set used for the aggregate function at x∈Rn is defined as follows:(12)Qtx,q=j∈QFx−fjx≤ϵt,q,where ϵt,q>0 is a complicated combination of several parameters.In this paper, based on the plus function, an active set smoothing function for the maximum function is proposed, and the smoothing function only relates to a part of component functions, whose function values are close toFx. It is continuously differentiable, and its gradient is locally Lipschitz continuous and strongly semismooth. Combing the active set smoothing function, a geometric reduction rule for the smoothing parameters, the Armijo line search strategy, the steepest decent direction, and the Newton direction, an active set smoothing method is proposed for solving unconstrained minimax problems. Under the boundedness assumption on the level set of Fx, the convergence of the active set smoothing method is established. Numerical experiments show that the resulting method is stable and efficient, especially for the minimax problems with very many component functions.The following assumptions and results will be used in this paper:Assumption 1: the component functionsfj:Rn⟶R, j∈Q, are twice continuously differentiable, and ∇fj:Rn⟶Rn, j∈Q, is strongly semismoothAssumption 2: for anyM>0, the level set ΩM=x∈RnFx≤M is boundedDefinition 1 (see [29]).
Suppose thatΦ:Rn⟶Rm is locally Lipschitz continuous, if for any V∈∂Φx+h, h⟶0,(13)Vh−Φ′x;h=Oh2,where ∂Φx is the generalized Jacobian of Φ at x, Φj′x;h is the directional derivative of Φj at x in the direction h for j=1,…,m, and then Φ is said to be strongly semismooth at x.Lemma 1 (see [29]).
Suppose thatϕ:R⟶R and ψ:R⟶R are strongly semismooth, then(i)
For anya, b∈R, aϕ+bψ:R⟶R is strongly semismooth(ii)
ϕ⋅ψ:R⟶R is strongly semismooth(iii)
Ifψx≥c for the constant c>0, ϕ/ψ:R⟶R is strongly semismooth(iv)
ϕ°ψ:R⟶R is strongly semismoothLemma 2 (see [29]).
Suppose thatΦ:Rn⟶Rm is locally Lipschitz continuous, if all Φi:Rn⟶R, i=1,…,m, are strongly semismooth, then Φ is strongly semismooth.Lemma 3 (see [30]).
For the functionΦ:Rn⟶Rm, if Φ′ is locally Lipschitz continuous, then Φ is strongly semismooth.Theorem 1 (see [24]).
Suppose that the component functionsfj:Rn⟶R, j∈Q, are continuously differentiable. If x∗ is a local minimizer of problem (1), then(14)0∈∂Fx∗≔convj∈Ix∗∇fjx∗,where(15)Ix∗≔j∈Qfjx∗=Fx∗,and conv A denotes the convex hull of A.


## 2. An Active Set Smoothing Function for the Maximum Function

In this section, based on the plus functionz+:R⟶R+:(16)z+=z,z>0,0,z≤0,we construct the following function Ftc:Rn×R⟶R:(17)Ftcx,α=cα+t2∑j∈Q1+fjx−cαt+2,where t>0 is the smoothing parameter and c>0 is the scaling parameter. By the definition of the plus function, Assumption 1, and t>0, we have the following result.Lemma 4.
For anyt>0 and c>0, Ftc:Rn×R⟶R is continuously differentiable.For anyt>0, c>0, and x,α∈Rn×R, let(18)Qtcx,α=j∈Qfjx−cα+t>0,then we know that(19)Ftcx,α=cα+t2∑j∈Qtcx,α1+fjx−cαt2,only relates to the component functions fj for j∈Qtcx,α, whose function values are close to Fx. Therefore, Ftcx,α is called an active set smoothing function for the maximum function in this paper. By direct calculation, we can obtain the gradient of Ftcx,α:(20)∇Ftcx,α=∑j∈Q1+fjx−cαt+∇fjxc−c∑j∈Q1+fjx−cαt+,which can be also written as follows:(21)∇Ftcx,α=∑j∈Qtcx,α1+fjx−cαt∇fjxc−c∑j∈Qtcx,α1+fjx−cαt.Lemma 5.
For anyt>0, c>0, and x,α∈Rn×R,(22)Ftcx,α>Fx.Proof.
Ifcα>Fx, by t>0, we have(23)Ftcx,α=cα+t2∑j∈Q1+fjx−cαt+2≥cα>Fx.
Ifcα≤Fx, we know 1+Fx−cα/t+2=1+Fx−cα/t2 by t>0, then we have(24)Ftcx,α=cα+t2∑j∈Q1+fjx−cαt+2≥cα+t21+Fx−cαt2=cα+t21+2Fx−cαt+Fx−cα2t2=t2+Fx+Fx−cα22t>Fx.
By (23) and (24), the conclusion holds.Lemma 6.
For anyt>0, c>0, τ>0, and x,α∈Rn×R satisfying ∇αFtcx,α<τ≤c,(i)
Fx−τ/ct<cα<Fx+1−c−τ/cq¯t(ii)
Ftcx,α<Fx+1−c−τ/cq¯+c+τ2/2c2t, where q¯=♯Qtcx,α.Proof.
By (10) and ∇αFtcx,α<τ, we know(25)−τ<c−c∑j∈Qtcx,α1+fjx−cαt<τ.
Then, byc≥τ>0, we have Qtcx,α≠∅,(26)0≤1−τc<∑j∈Qtcx,α1+fjx−cαt<1+τc,and hence, maxj∈Qtcx,α1+fjx−cα/t>0. Therefore, by t>0 and Qtcx,α⊆Q, we have(27)1+Fx−cαt=maxj∈Q1+fjx−cαt>0.(i)
By (26) and (27), we have(28)q¯1+Fx−cαt≥∑j∈Qtcx,α1+fjx−cαt>1−τc,1+Fx−cαt≤∑j∈Qtcx,α1+fjx−cαt<1+τc.Then, byt>0, we have(29)Fx−τct<cα<Fx+1−c−τcq¯t.(ii)
By (26), (29) and t>0, we have(30)Ftcx,α=cα+t2∑j∈Qtcx,α1+fjx−cαt2≤cα+t2∑j∈Qtcx,α1+fjx−cαt2<Fx+1−c−τcq¯t+t21+τc2=Fx+1−c−τcq¯+c+τ22c2t.
According to Lemmas5 and 6 and c+τ2≤4c2 for c≥τ>0, we have the following approximation of Ftcx,α for Fx.Lemma 7.
For anyt>0, c>0, and x,α∈Rn×R satisfying ∇αFtcx,α<c,(i)
Fx−t<cα<Fx+t(ii)
Fx<Ftcx,α<Fx+3t
For convenience of discussion, for anyt>0, c>0, and x,α∈Rn×R, let(31)z+jx,α=1+fjx−cαt+,j∈Q,then the gradient of Ftcx,α in (20) can be rewritten as follows:(32)∇Ftcx,α=∑j∈Qz+jx,α∇fjxc−c∑j∈Qz+jx,α.Lemma 8.
Suppose that Assumption 1 holds, then for anyt>0 and c>0, z+jx,α:Rn×R⟶R, j∈Q, is locally Lipschitz continuous.Proof.
By Assumption 1, we know that1+fjx−cα/t:Rn×R⟶R, j∈Q, is locally Lipschitz continuous with respect to the variables x,α for any t>0 and c>0. By the definition of the plus function, for any z1,z2∈R, we know that(i)
Ifz1≤0, z2≤0, then we have z+1=z+2=0, and hence, z+1−z+2=0(ii)
Ifz1≤0, z2>0, then we have z+1=0, z+2=z2, and hence, z+1−z+2=0−z2≤z1−z2(iii)
Ifz1>0, z2>0, then we have z+1=z1, z+2=z2, and hence, z+1−z+2=z1−z2
Therefore, the plus function is Lipschitz continuous. Hence,z+jx,α:Rn×R⟶R, j∈Q, is locally Lipschitz continuous.Lemma 9.
Suppose that Assumption 1 holds, then for anyt>0 and c>0, ∇Ftcx,α:Rn×R⟶Rn+1 is locally Lipschitz continuous.Proof.
By Assumption 1,∇fjx:Rn⟶Rn, j∈Q, is locally Lipschitz continuous. Then, by Lemma 8, ∑j∈Qz+jx,α∇fjx:Rn×R⟶Rn and c−c∑j∈Qz+jx,α:Rn×R⟶R, are locally Lipschitz continuous, which implies that ∇Ftcx,α:Rn×R⟶Rn+1 is locally Lipschitz continuous.Lemma 10.
Suppose that Assumption 1 holds, then for anyt>0 and c>0, z+jx,α:Rn×R⟶R, j∈Q, is strongly semismooth.Proof.
By the proof of Lemma8, the plus function is Lipschitz continuous. For any h>0 and ξ>0, we know ξh>0 and h+ξh>0, and hence, h+=h, ξh+=ξh, h+ξh+=h+ξh; then, we have(33)∂0+h+=1,z+′0;h=limξ↓0ξh+−0ξ=h.
For anyh<0 and ξ>0, we know ξh<0 and h+ξh<0, and hence, h+=ξh+=h+ξh+=0; then, we have(34)∂0+h+=0,z+′0;h=limξ↓0ξh+−0ξ=0.
Therefore, for anyV∈∂0+h+ and h⟶0, we have(35)Vh−z+′x;h=Oh2,which implies that the plus function is strongly semismooth at z=0 by Definition 1. Since the plus function is sufficiently smooth on R\0, we know that the plus function is strongly semismooth on R.
By Assumption 1,∇fjx:Rn⟶Rn, j∈Q, is locally Lipschitz continuous. Then, by Lemma 3, the component functions fjx:Rn⟶R, j∈Q, are strongly semismooth, and hence, 1+fjx−cα/t:Rn×R⟶R, j∈Q, is strongly semismooth with respect to x,α for any t>0 and c>0. Therefore, by (iv) of Lemma 1, z+jx,α:Rn×R⟶R, j∈Q, is strongly semismooth.Lemma 11.
Suppose that Assumption 1 holds, then for anyt>0 and c>0, ∇Ftcx,α:Rn×R⟶Rn+1 is strongly semismooth.Proof.
By Lemma9, ∇Ftcx,α:Rn×R⟶Rn+1 is locally Lipschitz continuous. By Assumption 1, ∇fjx:Rn⟶Rn, j∈Q, is strongly semismooth. By Lemma 10, z+jx,α:Rn×R⟶R, j∈Q, is strongly semismooth. Then, by (i) and (ii) of Lemma 1, ∑j∈Qz+jx,α∇fjx:Rn×R⟶Rn and c−c∑j∈Qz+jx,α:Rn×R⟶R, are strongly semismooth. Therefore, ∇Ftcx,α:Rn×R⟶Rn+1 is strongly semismooth by Lemma 2.
For anyx,α∈Rn×R, let Q¯tcx,α=j∈Qfjx−cα+t=0,q¯=♯Qtcx,α. By (32) and the definition of the plus function, the Clarke generalized Jacobian of ∇Ftcx,α at x,α can be represented as follows:(36)∂∇Ftcx,α=H1x,αH2x,αH2x,αTH3x,αζj∈0,1,j∈Q¯tcx,α,where(37)H1x,α=∑j∈Qtcx,αz+jx,α∇2fjx+1t∑j∈Q¯tcx,αζj∇fjx∇fjxT+∑j∈Qtcx,α∇fjx∇fjxT,H2x,α=−ct∑j∈Q¯tcx,αζj∇fjx+∑j∈Qtcx,α∇fjx,H3x,α=c2t∑j∈Q¯tcx,αζj+q¯.
For efficient numerical evaluation of∂∇Ftcx,α, we can set ζj=0 for j∈Q¯tcx,α; then, we know(38)Vtcx,α=H1x,αH2x,αH2x,αTH3x,α∈∂∇Ftcx,α,where(39)H1x,α=∑j∈Qtcx,αz+jx,α∇2fjx+1t∇fjx∇fjxT,H2x,α=−ct∑j∈Qtcx,α∇fjx,H3x,α=c2q¯t.


## 3. An Active Set Smoothing Method and Its Convergence

In this section, based on the active set smoothing functionFtcx,α for Fx and the smoothing methods introduced in [24], an active set smoothing method is proposed to solve problem (1). For a starting point x0,α0∈Rn×R and an initial smoothing parameter t0>0, the initial scaling parameter c0>0 is chosen from a bounded region in Subroutine 1, which reduces the ill-conditioning of Vt0c0x0,α0/c0 caused by the scaling problem of the variable α∈R; then, α0,0 is set to be α0/c0. The Armijo line search strategy, the steepest decent direction, and the Newton direction, in which the selection of the search direction depends on the condition number of Vt0c0xk,0,αk,0 and two convergence conditions for k≥0, are used to compute an approximate solution xk0,0,αk0,0 of the smoothing problem Pt0c0:(40)minx,α∈Rn×RFt0c0x,α.Then, the smoothing parametert0 geometrically reduces to t1, the scaling parameter c1 is chosen from a bounded region in Subroutine 1, αk0,0 is updated to αk0+1,1 in two ways to balance the efficiency and convergence of the resulting algorithm in Subroutine 1, and the smoothing problem Pt1c1:(41)minx,α∈Rn×RFt1c1x,α,is solved with the starting point xk0,0,αk0+1,1. By repeating this process, a sequence of smooth, unconstrained optimization problems is solved. As the smoothing parameters ti go to 0, a solution of problem (1) can be obtained by the solutions of the smoothing problems Ptici.Algorithm 1.
An active set smoothing algorithm.
Data. Inputβ,γ∈0,1; Cl∈0,1, Cu>1, t^∈0,1; κ≫1, κ1P,κ2P,κ1,κ2,κ3>0; ωt,ωc∈0,1; τt:0,∞⟶0,∞ satisfying limt⟶0τt=0; x0∈Rn, α0∈R, t0>0.Step 0: seti=0, k=0, x0,0=x0, α0,0=α0, and c0=1, and go to Subroutine 1.Step 1: (compute the search direction) compute the condition numberCk,i of Vticixk,i,αk,i. If Ck,i<κ, compute the Newton direction dticixk,i,αk,i by solving(42)Vticixk,i,αk,idticixk,i,αk,i+∇Fticixk,i,αk,i=0.IfVticixk,i,αk,i is positive and the Newton direction dticixk,i,αk,i satisfies(43)dticixk,i,αk,i≤κ1P∇Fticixk,i,αk,i,(44)−∇Fticixk,i,αk,i,dticixk,i,αk,i≥κ2P∇Fticixk,i,αk,i2,go to Step 2.IfVticixk,i,αk,i is not positive and the Newton direction dticixk,i,αk,i satisfies(45)dticixk,i,αk,i≤κ1∇Fticixk,i,αk,i,(46)−∇Fticixk,i,αk,i,dticixk,i,αk,i≥κ2∇Fticixk,i,αk,i2,−∇Fticixk,i,αk,i,dticixk,i,αk,i≥κ3∇Fticixk,i,αk,idticixk,i,αk,i,go to Step 2.Else, compute the steepest decent direction(47)dticixk,i,αk,i=−∇Fticixk,i,αk,i,go to Step 2.Step 2: (compute the stepsize) letλticixk,i,αk,i=βl, where l is the smallest nonnegative integer satisfying(48)Fticixk,i,αk,i+βldticixk,i,αk,i−Fticixk,i,αk,i≤γβl∇Fticixk,i,αk,i,dticixk,i,αk,i,go to Step 3.Step 3: setxk+1,i,αk+1,i=xk,i,αk,i+λticixk,i,αk,idticixk,i,αk,i, replace k by k+1, and go to Step 4.Step 4: if∇Fticixk,i,αk,i<τti, go to Step 5; else, go to Step 1.Step 5: (adjustment of the smoothing parameter) setki=k, xk+1,i+1=xk,i, αk+1,i+1=αk,i, ti+1=ωtti, and ci+1=ci, replace i by i+1 and k by k+1, and go to Subroutine 1.Subroutine 1: adjustment of the scaling parameter.Substep 0: setx=xk,i, t=ti, cl=ωcci, and cu=ci/ωc. If i=0 or t≤t^, set α¯i=ciαk,i:(49)αlk,i=α¯icl,αuk,i=α¯icu;else, setα¯i=ciαk,i−1/ωt−1t:(50)αlk,i=α¯icl,αk,i=α¯ici,αuk,i=α¯icu.Compute the condition numbersCk,i of Vtcix,αk,i, Clk,i of Vtclx,αlk,i, and Cuk,i of Vtcux,αuk,i. If cl≥Cl and Clk,i<Ck,i, go to Substep 1; else, if cu≤Cu and Cuk,i<Ck,i, go to Substep 2; else, go to Step 4 of Algorithm 1 with ci, Ck,i, Vtcix,αk,i, and αk,i.Substep 1: setci=cl, Ck,i=Clk,i, Vtcix,αk,i=Vtclx,αlk,i, and αk,i=αlk,i, and go to Substep 3.Substep 2: setci=cu, Ck,i=Cuk,i, Vtcix,αk,i=Vtcux,αuk,i, and αk,i=αuk,i, and go to Substep 4.Substep 3: setcl=ωccl and αlk,i=α¯i/cl and compute the condition number Clk,i of Vtclx,αlk,i. If Clk,i<Ck,i and cl≥Cl, go to Substep 1; else, go to Step 4 of Algorithm 1 with ci, Ck,i, Vtcix,αk,i, and αk,i.Substep 4: setcu=cu/ωc and αuk,i=α¯i/cu and compute the condition number Cuk,i of Vtcux,αuk,i. If Cuk,i<Ck,i and cu≤Cu, go to Substep 2; else, go to Step 4 of Algorithm 1 with ci, Ck,i, Vtcix,αk,i, and αk,i.Remark 1.
In Subroutine 1 for adjusting the scaling parameterci, if ti>t^, αk,i is updated to satisfy(51)ci+1αki+1,i+1=ciαki,i−1−ωtti.
Then, byxki+1,i+1=xki,i and ti+1=ωtti, we have(52)fjxki+1,i+1−ci+1αki+1,i+1+ti+1=fjxki,i−ciαki,i+ti,j∈Q,Qti+1ci+1xki+1,i+1,αki+1,i+1=Qticixki,i,αki,i,z+jxki+1,i+1,αki+1,i+1=z+jxki,i,αki,iωt,j∈Q,∇xFti+1ci+1xki+1,i+1,αki+1,i+1=∇xFticixki,i,αki,iωt,∇αFti+1ci+1xki+1,i+1,αki+1,i+1=ci+11−1−∇αFticixki,i,αki,i/ciωt,Vti+1ci+1xki+1,i+1,αki+1,i+1=Vticixki,i,αki,iωt.
Ifti≤t^, αk,i is updated to satisfy(53)ci+1αki+1,i+1=ciαki,i,which keeps the monotonicity of Fticixk,i,αk,i with respect to k in Lemma 13.Theorem 2 (local convergence [31]).
For anyt>0 and c>0, suppose that x∗,α∗ is a stationary point of the problem Ptc. If all V∈∂∇Ftcx∗,α∗ are nonsingular, then there exist a neighborhood Nx∗,α∗ of x∗,α∗ and a constant M such that for any x,α∈Nx∗,α∗ and any V∈∂∇Ftcx,α, V is nonsingular and(54)V−1≤M.The sequencexk,αk produced by any initial point x0,α0∈Nx∗,α∗ and the semismooth Newton method xk+1,αk+1=xk,αk−Vk−1∇Ftcxk,αkVk∈∂∇Ftcxk,αk quadratically converges to x∗,α∗.Lemma 12.
Suppose that Assumption 1 holds, then for any bounded setS⊂Rn×R and parameters β, γ∈0,1, t>0, and c>0, there exists a λS<∞ such that for any x,α∈S, λtcx,α≥λS and(55)Ftcx,α+λtcx,αdtcx,α−Ftcx,α≤−λS∇Ftcx,α2,where λtcx,α is the stepsize computed in Step 2 of Algorithm 1.Proof.
Letκ1∗=maxκ1P,κ1,1 and κ2∗=minκ2P,κ2,1. By (43)–(47), the search direction dtcx,α satisfies(56)dtcx,α≤κ1∗∇Ftcx,α,(57)−∇Ftcx,α,dtcx,α≥κ2∗∇Ftcx,α2.
By Lemma9, ∇Ftcx,α:Rn×R⟶Rn+1 is locally Lipschitz continuous, and then, there exists a Lipschitz constant LS>0 such that for any x1,α1, x2,α2∈S,(58)∇Ftcx1,α1−∇Ftcx2,α2≤LSx1,α1−x2,α2.
For anyx,α∈S and λ∈0,1, by the mean value theorem, there exists a ξ∈0,1 such that(59)Ftcx,α+λdtcx,α−Ftcx,α−γλ∇Ftcx,α,dtcx,α=∇Ftcx,α+ξλdtcx,α,λdtcx,α−γλ∇Ftcx,α,dtcx,α=λ1−γ∇Ftcx,α,dtcx,α+∇Ftcx,α+ξλdtcx,α−∇Ftcx,α,λdtcx,α≤λ1−γ∇Ftcx,α,dtcx,α+λ∇Ftcx,α+ξλdtcx,α−∇Ftcx,αdtcx,α≤λ1−γ∇Ftcx,α,dtcx,α+λ2ξLSdtcx,α2≤−λκ2∗1−γ−κ1∗2λLS∇Ftcx,α2,where the second inequality comes from (58) and the last inequality comes from (56), (57), and ξ∈0,1. Let(60)λ∗=min1,κ2∗1−γκ1∗2LS,then it follows from (59) that for any λ∈0,λ∗,(61)Ftcx,α+λdtcx,α−Ftcx,α−γλ∇Ftcx,α,dtcx,α≤0,and hence, λtcx,α≥βλ∗. Therefore, by (57), we have(62)Ftcx,α+λtcx,αdtcx,α−Ftcx,α≤γλtcx,α∇Ftcx,α,dtcx,α≤−βγλ∗κ2∗∇Ftcx,α2.
Then, byγ, κ2∗∈0,1, the conclusion holds for(63)λS=minβγκ2∗,βγ1−γκ2∗2κ1∗2LS.Lemma 13.
Suppose that Assumptions 1 and 2 hold andτti≤ωtci, then for any x0,α0∈Rn×R, t0>0 and c0>0, the sequence xk,i,αk,i generated by Algorithm 1 satisfies the following:(i)
For anyi≥0, Fticixk,i,αk,i is monotone decreasing with respect to k(ii)
There exists ani^ such that the sequence Fticixk,i,αk,ii≥i^ is monotone decreasing with respect to k(iii)
The sequencexk,i is bounded(iv)
The sequenceαk,i is boundedProof.
(i)
For anyi≥0 and xk,i,αk,i∈Rn×R satisfying dticixk,i,αk,i≥τti, by Lemma 12, there exists a lk,i≥0 such that(64)Fticixk+1,i,αk+1,i−Fticixk,i,αk,i≤γβlk,i∇Fticixk,i,αk,i,dticixk,i,αk,i<0,then we know(65)Fticixk+1,i,αk+1,i<Fticixk,i,αk,i,which implies that the conclusion holds.(ii)
Byti+1=ωtti and ωt∈0,1, for any t0>0 and t^∈0,1, there exists an i^ such that for any i≥i^,(66)ti≤t^.For anyi≥i^, if ∇Fticixk,i,αk,i<τti, by the definition of ∇Ftcx,α in (20), we have(67)−τti<ci−ci∑j∈Q1+fjxk,i−ciαk,iti+<τti.Then, byτti≤ωtci<ci and ti>0, we have(68)1+Fxk,i−ciαk,iti=maxj∈Q1+fjxk,i−ciαk,iti+>0.Lett be the variable of the function Ftcx,α for given x,α∈Rn×R and c>0, which is redefined as Fx,αct, then by the mean value theorem, there exists a t¯∈ωtti,ti such that(69)Fxk,i,αk,iciti−Fxk,i,αk,iciωtti=Fxk,i,αk,ici′t¯ti−ωtti,with(70)Fx,αc′t=12∑j∈Q1+fjx−cαt+1−fjx−cαt.IfFxk,i≤ciαk,i, by t¯>0, we have(71)1−fjxk,i−ciαk,it¯>0,j∈Q,and henceFxk,i,αk,ici′t¯>0 by (68). If Fxk,i>ciαk,i, by (67) and (68) and τti≤ωtci, we have(72)ci−ci1+Fxk,i−ciαk,iti≥ci−ci∑j∈Q1+fjxk,i−ciαk,iti+>−τti≥−ωtci,which implies(73)Fxk,i−ciαk,iti<ωt.Byt¯>ωtti>0, we have(74)Fxk,i−ciαk,it¯<Fxk,i−ciαk,iωtti<1,fjxk,i−ciαk,it¯≤Fxk,i−ciαk,it¯<1,j∈Q.Then, we know that (71) also holds and hence Fxk,i,αk,ici′t¯>0 by (68). Therefore, for the case of ∇Fticixk,i,αk,i<τti, by (69), we have(75)Fxk,i,αk,iciti−Fxk,i,αk,iciωtti>0,which means(76)Fticixk,i,αk,i−Fωtticixk,i,αk,i>0.Byxk+1,i+1=xk,i and ci+1αk+1,i+1=ciαk,i according to (53) and (66), we have(77)Fti+1ci+1xk+1,i+1,αk+1,i+1=Fti+1cixk,i,αk,i.Then, by (76) and ti+1=ωtti, we know(78)Fti+1ci+1xk+1,i+1,αk+1,i+1<Fticixk,i,αk,i.Therefore, the sequenceFticixk,i,αk,ii≥i^ is monotone decreasing with respect to k by (65) and (78).(iii)
By (i), for any0≤k≤k0, we have(79)Ft0c0xk,0,αk,0≤Ft0c0x0,0,α0,0,and for any1≤i<i^, ki−1+1≤k≤ki, we have(80)Fticixk,i,αk,i≤Fticixki−1+1,i,αki−1+1,i.By (ii), for anyi≥i^ and ki−1+1≤k≤ki,(81)Fticixk,i,αk,i≤Fti^ci^xki^−1+1,i^,αki^−1+1,i^.By the finiteness ofi satisfying i<i^, (79), (80), and (81), there exists a constant F0∈R such that for any xk,i,αk,i,(82)xk,i,αk,i∈ΩF0=x,α∈Rn×RFtcx,α≤F0.Suppose that for anyM>0, there exists a point xk¯,i¯,αk¯,i¯∈ΩF0 satisfying Fxk¯,i¯>M. If ci¯αk¯,i¯≥M−ti¯, by the definition of the plus function and 0<ti¯≤t0, we have(83)Fti¯ci¯xk¯,i¯,αk¯,i¯≥ci¯αk¯,i¯≥M−ti¯≥M−t0.Ifci¯αk¯,i¯<M−ti¯, by Fxk¯,i¯>M and ti¯>0, we have(84)1+Fxk¯,i¯−ci¯αk¯,i¯ti¯>1+M−ci¯αk¯,i¯ti¯>2,and hence1+Fxk¯,i¯−ci¯αk¯,i¯/ti¯+=1+Fxk¯,i¯−ci¯αk¯,i¯/ti¯ and 1+M−ci¯αk¯,i¯/ti¯+=1+M−ci¯αk¯,i¯/ti¯. Then, we know(85)Fti¯ci¯xk¯,i¯,αk¯,i¯=ci¯αk¯,i¯+ti¯2∑j∈Q1+fjxk¯,i¯−ci¯αk¯,i¯ti¯+2≥ci¯αk¯,i¯+ti¯21+Fxk¯,i¯−ci¯αk¯,i¯ti¯2>ci¯αk¯,i¯+ti¯21+M−ci¯αk¯,i¯ti¯2>ci¯αk¯,i¯+ti¯1+M−ci¯αk¯,i¯ti¯>M.However, the arbitrariness ofM, (83), and (85) contradict xk¯,i¯∈ΩF0; then, there must exist a M∗>0 such that Fxk,i≤M∗ for any Fxk,i≤M∗ and i≥0. Therefore, we have that xk,i⊆ΩM∗, and hence, the sequence xk,i is bounded by Assumption 2.(iv)
For anyxk,i,αk,i with k≥0 and i≥0, if Qticixk,i,αk,i=∅, by the definition of Qtcx,α, we know 1+fjxk,i−ciαk,i/ti+=0 for any j∈Q by ti>0. Then, by xk,i,αk,i∈ΩF0, we have(86)Fticixk,i,αk,i=ciαk,i≤F0.
Hence, byci≥Cl>0, we know(87)αk,i≤F0ci≤F0Cl.
IfQticixk,i,αk,i≠∅, by Fxk,i≤M∗ from (iii), we have(88)ti+M∗−ciαk,i≥ti+Fxk,i−ciαk,i>0.
Then, by0<ti≤t0 and ci≥Cl>0, we know(89)αk,i<ti+M∗ci≤t0+M∗ci≤t0+M∗Cl.
Therefore, the sequenceαk,i is bounded by (87) and (89).Lemma 14.
Suppose that Assumptions 1 and 2 hold, then for anyx0,α0∈Rn×R and t0>0, the sequences xk,i,αk,i and ti generated by Algorithm 1 satisfy the following:(i)
For anyi≥0, there exists a ki∈N such that ∇Fticixki,i,αki,i<τti(ii)
The sequenceti is infinite and strictly monotone decreasing, ti⟶0 as k⟶∞Proof.
(i) If there exists ani¯≥0 such that the sequence xk,i¯,αk,i¯ is infinite, then we have ∇Fti¯ci¯xk,i¯,αk,i¯≥τti¯ and k⟶∞. By Lemma 12 and the boundedness of xk,i¯,αk,i¯ from Lemma 13, there exists a constant Ci¯>0 such that(90)Fti¯ci¯xk+1,i¯,αk+1,i¯−Fti¯ci¯xk,i¯,αk,i¯≤−Ci¯∇Fti¯ci¯xk,i¯,αk,i¯2≤−Ci¯τti¯2<0.Then, byk⟶∞, we have(91)limk⟶∞Fti¯ci¯xk,i¯,αk,i¯=−∞,which contradicts thatxk,i¯,αk,i¯ is bounded and Fti¯ci¯x,α is continuous on Rn×R. Therefore, for any i≥0, there exists a ki∈N such that ∇Fticixki,i,αki,i<τti.(ii)
By (i), for anyi≥0, there exists a ki∈N such that ∇Fticixki,i,αki,i<τti, then ti is updated to ti+1=ωtti. Therefore, by ωt∈0,1, we know that i⟶∞ as k⟶∞, and hence, the sequence ti is infinite and strictly monotone decreasing, ti⟶0 as k⟶∞.Theorem 3.
Suppose that Assumptions 1 and 2 hold,xk,i,αk,i is the sequence generated by Algorithm 1, then for any accumulation point x∗,α∗∈Rn×R of xki,i,αki,i, 0∈∂Fx∗, i.e., x∗ is a stationary point of problem (1).Proof.
By Lemmas13 and 14, the sequence xki,i,αki,i⊆xk,i,αk,i is infinite and bounded; then, there exists at least one accumulation point of xki,i,αki,i. For any accumulation point x∗,α∗ of xki,i,αki,i, there exists a subsequence of xki,i,αki,i (denoted also by xki,i,αki,i for convenience) converging to x∗,α∗. By Lemma 14, ∇Fticixki,i,αki,i<τti and limt⟶0τt=0, we have(92)limi⟶∞∇Fticixki,i,αki,i=0.
It follows from (32) and (92) that(93)limi⟶∞∑j∈Qz+jxki,i,αki,i∇fjxki,i=0,(94)limi⟶∞∑j∈Qz+jxki,i,αki,i=1.
By Lemma7, xki,i,αki,i⟶x∗,α∗, i⟶∞, and ti⟶0, we have(95)limi⟶∞Fxki,i=limi⟶∞ciαki,i=Fx∗.
Then, by Assumption 1, we have(96)limi⟶∞fjxki,i−ciαki,i=fjx∗−Fx∗<0,j∉Ix∗.
Hence, by the finiteness of indexes inQ∖Ix∗, there exists an i0>0 such that for any i>i0,(97)fjxki,i−ciαki,i<−ti,j∉Ix∗,which implies(98)limi⟶∞z+jxki,i,αki,i=0,j∉Ix∗.
By (94), z+jxki,i,αki,i≥0 for j∈Ix∗, and by the finiteness of indexes in Ix∗, there exists a subsequence of xki,i,αki,i (denoted also by xki,i,αki,i for convenience) and zj∗∈0,1 for j∈Ix∗, such that(99)∑j∈Ix∗zj∗=1,limi⟶∞z+jxki,i,αki,i=zj∗∈0,1,j∈Ix∗.
Therefore, byxki,i⟶x∗, (93), (98), (99), and Assumption 1, we have(100)∑j∈Ix∗zj∗∇fjx∗=0,∑j∈Ix∗zj∗=1,zj∗≥0,j∈Ix∗,which implies that x∗ is a stationary point of problem (1).


## 4. Numerical Experiments

In this section, we present the numerical results of Algorithm1 and several related algorithms for solving unconstrained minimax problems. Algorithm 1 is recorded as ASSF. Fminimax is the MATLAB algorithm “fminimax”. Fmincon is the MATLAB algorithm “fmincon” applied to(101)minx,α∈Rn+1αfjx−α≤0,j∈Q,which is equivalent to problem (1). To show the efficiency of the proposed active set smoothing function, we replace it by some other smoothing techniques in Algorithm 1 to obtain several smoothing methods. AF, SSF, and SPF are constructed by Algorithm 1 with aggregate function (2), cubic spline smoothing function introduced in [28], and exact penalty function technique introduced in [18], respectively. TAF and ASAF are constructed by Algorithm 1 and the aggregate function with the active set strategies introduced in [25, 26], respectively.The parameters in Algorithm1 are set as follows:(102)β=0.8,γ=0.5;Cl=10−2,Cu=102,t^=10−3;κ=1010,κ1P=κ1=105,κ2P=κ2=10−10,κ3=0.25;ωt=0.1,ωc=0.1,τti=10−3.For the moderately sized test problems,t0 and α0 are set as follows:(103)t0=∑j∈Qfjx0−qminj∈Qfjx0+1,α0=∑j∈Qfjx0c0q+t0c0−t0c0q,and then, we have(104)Qt0c0x0,α0=Q,∑j∈Q1+fjx0−c0α0t0+=1,which implies that ∇xFt0c0x0,α0 is a convex combination of the gradients of all the component functions. For the test problems with very many component functions, t0 is set as(105)t0=max1,qFx0−minj∈Qfjx010.α0∈Fx0−t0,Fx0+t0 is computed by the bisection method according to(106)1−∑j∈Q1+fjx0−c0α0t0+<0.1.For the algorithm ASAF, the parameterϵ in (10) is set as(107)ϵ=0.8Fx−minj∈Qfjx,for the moderately sized test problems, and(108)ϵ=0.4Fx−minj∈Qfjx,for the test examples with very many component functions. For the algorithm TAF, the parameter ϵt,q in (12) is set as(109)ϵt,q=tlnmax1,2ϵ1−ϵ2q−1ϵ2,2ϵ3+6ϵ12t−ϵ4q−1ϵ4,with ϵ1=0.1, ϵ2=0.01, ϵ3=0.01, and ϵ4=0.1. For the algorithms AF, ASAF, TAF, SSF, and SPF, the initial smoothing parameters are set to t0=1. The termination criterion for the algorithm AF is set as(110)t<10−3,∇Ftx≤10−3.The termination criteria for the algorithms ASSF, SSF, SPF, ASAF, and TAF are set as(111)t<10−3,∇ℱtx≤10−3,or(112)Fx≤FxAF∗,where ∇ℱtx represents the gradient of the smoothing function with respect to the variable x and xAF∗ is the approximation solution computed by the algorithm AF. The numerical results were obtained by running MATLAB R2014a on a laptop with Inter(R) Core(TM) i5-7300HQ CPU 2.50GHZ and 4.00 GB memory.We carry out a comparison on three categories of test problems described in the Appendix. The first category of problems, Examples1–10, emanates from the discretized semi-infinite minimax problems, and the number of the component functions is at least 1000. The second category of problems, Example 11, possesses many variables and many component functions. The third category of problems, Examples 12–45, is composed by various moderately sized test problems. Tables 1–3 list the CPU time; Tables 4–6 list the number of function evaluations and iterations; Tables 7 and 8 list the average proportion of the component functions used in the active set strategy; the word fail1 means that the stepsize cannot be computed in the region 10−10,1; the word fail2 means that the number of iterations in Fminimax or Fmincon reaches the upper limit; the word fail3 means that the CPU time exceeds 3600 seconds. In order to make the advantages of Algorithm 1 clearer and more explicit, the corresponding Dolan–Morée´ performance profiles proposed in [32] are shown in Figures 1–3 for three categories of examples above.Table 1
The CPU time for Examples1–10.
Ex.qASSFSSFSPFTAFASAFAFFminimaxFmincon11050.10350.75981.21530.32830.28720.292434.7621226.45731060.88007.53757.36123.27752.88213.03912204.3730fail310710.731875.345475.865632.612028.299931.4882fail3fail321050.08620.09650.12220.09540.24470.09097.1100116.84111060.56470.97652.89850.95763.13950.9704116.56741491.48051079.114910.762226.57949.782132.97369.49561487.9868fail331051.49024.458627.78354.46054.07617.7392122.9883fail210619.893759.5392839.376268.248255.0242103.42723044.0625fail2107203.0458514.44583569.5139676.4006501.4630926.5762fail3fail241050.32020.58364.54300.63962.11242.135569.3814fail21063.43667.985344.67788.845127.311527.67701545.7716fail210736.020671.4938645.177278.9203230.0224237.1365fail3fail251050.93962.64789.68033.71633.21873.7483230.2623fail110616.439531.177592.126345.287443.484345.5968fail3fail1107158.8988307.47911002.5981432.1560401.5995436.5213fail3fail161050.69663.72463.12384.48103.46864.520842.9713fail31067.261849.675446.534559.698946.158560.02912912.3607fail310774.8332478.8652455.7022561.2579425.4030566.2980fail3fail371051.10567.004813.45883.27909.32493.2450169.5213fail210626.344574.6292177.144635.255199.201234.5205fail3fail2107123.4221749.76561834.9277343.0618984.0483341.2569fail3fail281050.93611.85978.10731.35152.65221.5489157.1865fail210612.615125.183886.328819.508735.345820.1976fail3fail2107108.6392236.4630949.2546184.0629328.1475189.5273fail3fail291050.48631.564110.07221.45390.71621.494521.4071fail31068.017918.8813174.856218.44609.494518.7385283.0764fail310758.8060177.53522275.1924162.9317101.1354165.56423543.2556fail3101030.92731.90021.157214.533628.955030.51581.3285fail21040.641319.475810.909097.0372177.8060186.017314.5788fail21051.6718183.3566129.7202471.6195792.5688809.8969131.9020fail2Table 2
The CPU time for Example11.
nqASSFSSFSPFTAFASAFAFFminimaxFmincon1021020.52750.774712.26770.75560.77150.7928464.3152fail31021032.736915.884976.216514.466915.196315.2076fail3fail310210425.7550587.5630fail3533.8570615.3645665.1596fail3fail3101030.21272.41032.86462.30612.36952.43192.815920.21061021032.714112.048274.330110.722910.001311.2506fail3fail3103103806.92062286.4695fail32186.75362098.25692304.5143fail3fail3Table 3
The CPU time for Examples12–45.
Ex.ASSFSSFSPFTAFASAFAFFminimaxFmincon120.00180.00260.10700.00130.00230.00170.06360.0569130.00110.00120.01670.00210.00370.00450.09310.0578140.24680.46170.61720.24690.42130.00130.0959fail2150.01900.01320.12430.00870.01170.01251.4777fail2160.04370.03162.36750.02980.03530.02975.8776fail2170.00990.01930.38820.01290.01370.01930.84540.1955180.03760.04170.82570.08390.08490.07021.8279fail2190.18950.74420.52140.86140.97490.87500.51220.6373201.88283.66563.02553.57553.82573.58373.02083.0462210.00540.4821fail10.01780.02290.01980.08450.1491220.00740.13843.02350.01690.03120.02280.03210.0607230.01130.86150.39810.04320.05880.04810.08970.2281240.00260.08810.02480.00730.00920.00770.02110.0360251.794116.12896.07946.275511.246512.25016.12016.2704260.00060.00570.00960.01900.00880.00510.11650.0926270.09900.16681.73660.83201.10200.72010.44490.0894280.00180.00550.01470.00380.00440.00320.01260.0179290.00100.00220.01260.00110.00270.00070.01800.0247300.00150.00360.00930.00160.00400.00250.01010.0170310.00050.00100.00140.00090.00070.00060.01770.0185320.00180.00550.11080.00410.00550.00380.01010.0193330.00170.00890.01650.00380.00600.00400.01010.0174340.00040.00170.00310.00160.00190.00150.01060.0184350.00180.00610.02060.00510.00630.00470.00870.0184360.00080.00260.00930.00180.00280.00180.00820.0148370.00220.00600.02100.00760.00970.00730.01600.0310380.00300.00530.57160.00270.00370.00180.05430.1928390.00380.00900.02630.01060.00890.00640.03270.0910400.02280.02910.16520.06110.12290.11140.01130.9211410.00010.00530.00610.00470.00640.00510.01450.0203420.00180.00930.01270.00640.01760.00940.00680.8627430.00220.00460.05900.00500.00630.00470.01570.0216440.00450.01070.05050.01170.01570.01220.01680.0572450.0331fail12.63030.55940.164821.68740.0681fail1Table 4
The number of function evaluations and iterations for Examples1–10.
Ex.qASSFSSFSPFTAFASAFAF1105(34, 23)(67,14)(188, 77)(93, 15)(79,14)(84, 15)106(27, 20)(246, 22)(88, 34)(85, 15)(79,14)(84, 15)107(33, 23)(343, 21)(97, 40)(83,14)(79,14)(84, 15)2105(23, 18)(30, 13)(19, 19)(32,10)(55, 13)(32,10)106(23, 18)(34, 15)(60, 35)(32,10)(55, 13)(32,10)107(32, 22)(34, 13)(16, 16)(32,10)(55, 13)(32,10)3105(242, 101)(564, 118)(1381, 928)(737, 219)(580, 109)(812, 262)106(238, 103)(761, 137)(4852, 4518)(798, 245)(583, 108)(1039, 266)107(239, 103)(765, 141)(4852, 4518)(804, 249)(583, 108)(819, 262)4105(60, 50)(242, 53)(808, 385)(503,33)(466, 35)(610, 47)106(66, 58)(270, 59)(1008, 258)(657, 41)(550,38)(614, 48)107(71, 63)(296, 68)(1408, 271)(632, 46)(634,40)(599, 47)5105(84, 58)(76, 45)(407, 233)(281, 65)(277, 63)(284, 67)106(93, 61)(87, 50)(407, 233)(280, 65)(276, 63)(284, 68)107(89, 59)(98,55)(407, 233)(280, 65)(276, 63)(284, 68)6105(53, 39)(293, 216)(274, 95)(296, 229)(231, 231)(299, 231)106(53, 39)(293, 216)(396, 124)(296, 229)(231, 231)(299, 231)107(53, 39)(293, 216)(426, 123)(296, 229)(231, 231)(299, 231)7105(19, 16)(130, 28)(379, 111)(55, 17)(342, 68)(55, 17)106(67, 39)(128, 33)(498, 138)(55, 17)(362, 72)(55, 17)107(44, 19)(125, 31)(507, 137)(55,17)(364, 74)(55,17)8105(66, 39)(145, 57)(606, 180)(214,39)(550, 52)(215, 40)106(60, 38)(131, 61)(567, 180)(216, 40)(572, 54)(216, 40)107(54, 33)(137, 56)(801, 227)(215, 40)(593, 56)(215, 40)9105(79,14)(47, 21)(434, 152)(48, 18)(39, 15)(48, 18)106(79, 17)(59, 21)(677, 200)(48, 18)(39, 15)(48, 18)107(76,11)(49, 20)(935, 270)(48, 18)(39, 15)(48, 18)10103(745,63)(1071, 103)(243, 107)(107139, 4270)(111873, 4454)(135709, 5096)104(74, 53)(1094, 105)(278, 120)(134725, 5136)(137748, 5240)(136931, 5213)105(69, 49)(2477, 495)(423, 140)(122067, 4649)(112489, 4968)(122803, 4677)Table 5
The number of function evaluations and iterations for Example11.
nqASSFSSFSPFTAFASAFAF102102(212, 41)(196, 38)(1110, 919)(180,32)(174, 31)(175, 32)102103(245, 55)(561, 65)(1010, 378)(553, 62)(557, 64)(557, 64)102104(318, 85)(1952, 143)fail3(1707, 114)(1888, 139)(2857, 166)10103(208, 45)(392, 49)(5658, 249)(391, 49)(392, 49)(395, 48)102103(228, 47)(464, 59)(983, 381)(459, 56)(561, 62)(459, 56)103103(255, 59)(562, 63)fail3(563, 65)(559, 60)(559, 60)Table 6
The number of function evaluations and iterations for Examples12–45.
Ex.ASSFSSFSPFTAFASAFAF12(26, 19)(29, 13)(56, 41)(24, 11)(27, 12)(36, 16)13(9,5)(5, 5)(93, 48)(7,5)(6,5)(7,5)14(5054, 2352)(5024, 2342)(6058, 6052)(5195, 2341)(5027, 2335)(33, 9)15(12, 6)(5, 5)(135, 76)(7,5)(6,5)(7,5)16(14, 6)(6, 6)(494, 264)(7,5)(7, 6)(7,5)17(13, 6)(4, 4)(316, 143)(10, 5)(10, 5)(11, 6)18(14,6)(6, 6)(180, 92)(22, 9)(22, 7)(16,6)19(5466,213)(11827, 582)(664, 586)(23561, 649)(23700, 649)(24435, 671)20(41561,2428)(46979, 2844)(3103, 3056)(88377, 2981)(87642, 2846)(89606, 3016)21(69, 36)(3296, 3186)fail1(618, 40)(655, 42)(649, 47)22(121, 40)(2508, 353)(22442, 21961)(695, 55)(844, 61)(740, 58)23(68, 41)(12151, 694)(4623, 1197)(1277, 55)(1339, 81)(1181, 82)24(21, 19)(638, 279)(203, 116)(121, 27)(111, 26)(119, 30)25(26994,1525)(101048, 5186)(5215, 5126)(135661, 5598)(220821, 7685)(261684, 8977)26(9, 5)(22, 11)(65, 44)(151, 119)(145, 13)(145, 13)27(237, 237)(356, 239)(3691, 2763)(16060, 878)(15714, 852)(10800, 622)28(30, 18)(148, 21)(164, 135)(104, 19)(92, 19)(95, 19)29(13, 11)(26, 10)(105, 104)(11,8)(12, 10)(8, 8)30(31, 15)(104, 14)(84, 71)(45,10)(71, 16)(71, 16)31(8, 8)(8, 6)(7, 9)(7, 6)(6, 4)(10, 6)32(28, 18)(178,18)(1145, 1053)(119, 22)(115, 20)(119, 22)33(27, 18)(270, 22)(256, 117)(112, 19)(118, 25)(118, 25)34(4, 4)(19, 10)(33, 22)(30, 11)(44, 7)(39, 13)35(30, 17)(209, 19)(259, 175)(171, 20)(150, 21)(153, 24)36(12, 8)(42, 10)(39, 21)(56,7)(56, 10)(53, 10)37(25, 21)(158,18)(225, 163)(228, 26)(214, 25)(218, 29)38(21, 13)(64, 12)(2090, 2073)(38, 8)(33, 10)(20,7)39(31, 22)(142, 22)(174, 114)(262,17)(103, 22)(105, 24)40(966,45)(592, 90)(4612, 232)(2341, 192)(4278, 214)(4549, 213)41(18, 18)(165, 39)(53, 38)(97, 37)(107, 26)(119, 38)42(26, 15)(236, 36)(180, 78)(158, 44)(469, 52)(306, 41)43(23, 21)(165, 46)(601, 502)(175, 49)(175, 28)(167, 42)44(36, 28)(228, 52)(360, 228)(307, 53)(339, 32)(304, 46)45(195, 26)fail1(6172, 3109)(1145, 35)(4754, 174)(225933, 4256)Table 7
The proportion of the component functions used in the active set strategy for Examples1–10.
Ex.qASSFSSFSPFTAFASAF11050.49920.72920.65530.75820.96661060.42410.72800.64970.76660.96661070.49870.70010.61780.80560.966621050.42640.77370.89010.73700.89561060.42640.75280.88110.74970.89561070.53060.77930.88200.76160.895631050.80520.99650.72980.98480.99481060.80690.92040.51780.98700.99471070.80690.91290.51780.98800.994641050.19520.30620.79000.62620.95491060.16720.30200.70490.63340.95841070.15400.30090.70370.63010.954351050.46330.89630.93090.83920.98431060.48780.83250.93090.84290.98431070.47110.80220.93080.84680.984361050.65210.86930.90280.99170.99421060.65210.83560.90280.99190.99421070.65200.82600.86270.99200.994271050.66350.84540.86040.99350.96931060.64400.88300.80730.99320.97101070.64400.83230.83760.99140.969181050.71630.97960.90900.87750.99751060.70880.84780.90920.87600.99771070.39900.80840.85790.88500.997991050.49920.87450.86780.99970.51481060.40120.88030.85090.99950.51481070.39030.83530.83450.99950.5148101030.03820.59730.63950.02890.03351040.56120.61080.61910.02820.03371050.41250.60880.60910.02900.0329Table 8
The proportion of the component functions used in the active set strategy for Example11.
nqASSFSSFSPFTAFASAF1021020.27410.73440.53940.87650.92281021030.22120.72260.50870.80880.92271021040.30300.7951fail30.83640.9227101030.19690.81330.50970.80090.89981021030.25700.79750.51450.83710.89841031030.24770.7622fail30.85840.8977Figure 1
The Dolan–Morée´ performance profile of Examples 1–10.
(a)(b)Figure 2
The Dolan–Morée´ performance profile of Examples 11.
(a)(b)Figure 3
The Dolan–e´Moré performance profile of Examples 12–25.
(a)(b)For all the test problems with very many component functions, we see that Algorithm1 is predominantly faster than other algorithms from Tables 1 and 2 and Figures 1 and 2, the proposed active set strategy results in more significant reduction of gradient evaluations than the active set strategies in [18, 25, 26, 28] from Tables 7 and 8, and Fminimax and Fmincon have poor stability and low efficiency. For most moderately sized test problems, we see from Tables 3 and 6 and Figure 3 that Algorithm 1 requires fewer iterations and function evaluations and takes less CPU time than the other algorithms considered.


## 5. Conclusion

We have proposed an active set smoothing function for the maximum function by using the plus function and an active set smoothing method with convergence analysis for solving unconstrained minimax problems. The active smoothing function can be simply implemented in the smoothing methods. Compared with the similar smoothing algorithms based on other smoothing techniques, and the algorithms in the MATLAB environment, the proposed algorithm is competitive for wide moderately sized problems and dramatically efficient for the problems with very many component functions.



---

*Source: 9108150-2020-06-24.xml*