TWO ALGORITHM FRAMEWORKS BASED ON DISCRETIZATION METHOD AND LOCAL REDUCTION FOR SEMI-INFINITE PROGRAMMING

XU Qing-juan,JIAN Jin-bao

(1.College of Mathematical and Statistics Sciences,Guangxi Teachers Education University,Nanning 530001,China)

(2.College of Science,Guangxi University for Nationalities,Nanning 530006,China)

Abstract:In this paper,two algorithm frameworks for semi-in finite programming(SIP)are discussed.Using discretization method and local reduction method,we present two algorithm frameworks for SIP.Under some mild assumptions,the algorithm framework based on discretization method possesses weak global convergence.Numerical experiments show that the proposed algorithm frameworks are effective.

Keywords: semi-in finite programming;discretization method;local reduction method;global convergence

1 Introduction

In recent decades,semi in finite programming(SIP)attracted the attention and favor of many scholars at home and abroad,and the research results were abundant[1–4].A simple form of SIP is given as follows:

where f:Rn→ R is continuously differentiable and g:Rn×[a,b]→ R is continuously differentiable with respect to x.

Discretization method is a common method,and local reduction method is an intrinsic method for solving SIP.Refs.[1–3]made a analysis in detail.In view of the wide application of discretization method in engineering,many scholars studied the discretized problem from SIP[5–11].The discretized problem has the following form

For better analysis of how to solve SIP through solving SIPq,we attempt to present two algorithm frameworks based on discretization method and local reduction method,respectively.Of course,the two algorithm frameworks can be considered to be designed for the algorithms for SIPqin[8–11].In addition,under some necessary assumptions,the global convergence of the previous algorithm framework is proved.Finally,some preliminary numerical results are reported.

2 Algorithm Framework Based on Discretization Method

2.1 Description of Algorithm

In this section,inspired by the idea of discretization method[2],we present an algorithm framework for SIP on this basis of the algorithms for SIPqin[8–11].

For clarity,we denote the algorithm for SIPqin[8–11]as“Algorithm A”,which is taken as an inner iteration of Algorithm below.Define the distance of Hausdorffbetween? and ?qas dist(?q,?)=As to discretization method,the sequence of discretized set{?qi}i∈N0satisfies the following conditions:

Our algorithm framework based on discretization method is described as follows.

Algorithm 2.1 An algorithm framework based on discretization method for SIP.

Parameters {τi}i∈N0such that 0 ＜ τi+1＜ τi,?i∈ N0andand initialized parameters of Algorithm A.

Datax0=∈Rn,choose discretized set ?q0? ? such that|?q0|＜ ∞and dist(?q0,?)≤ τ0.

Step 0 Set i=0.

Step 1 Solve SIP(?qi)(i.e.,SIPqi)by applying Algorithm A to obtain a KKT pointqi.

Step 2 Choose discretized set ?qi+1? ? such that ?q0? ?qi+1,|?qi+1|＜ ∞ and dist(?qi+1,?)≤ τi+1.

Step 3 Set i=i+1,and go back to Step 1.

Discretization method is actually an outer approximation algorithm.The real solution is approximated by the exterior approximation of the feasible region of SIP.From a numerical viewpoint,only the conceptual discretization method is useful.The latest research on discretization method can be seen in refs.[12,13].

2.2 Global Convergence

In this part,we will discuss the global convergence of Algorithm 2.1 under mild assumptions.For the sake of convenience,we denote

Definition 2.1 For x0∈ Rnand discretized set ?qi? ?,i∈ N0in Algorithm 2.1,the level set is defined as

Assumption 2.1 Level set LV(x0,?q0,?)is bounded,thus is compact.

Remark 1 The assumption that{xk}is bounded in refs.[8–11]can be replaced by Assumption 2.1.

Assumption 2.2 Functions g(·,·)are Lipschitz continuous in the bounded set,i.e.,there exist Lipschitz constants Lgxand Lgωsuch that

Assumption 2.3 Suppose that linearly independent constraint qualification(LICQ)is satisfied by problem SIP at any∈?act,i.e.,the vectorsare linearly independent.

Lemma 2.1(see[3])Suppose that Assumption 2.3 holds,then the number of indices of ?act()is finite.

Definition 2.2(see[3])Suppose thatthenis the KKT point of SIP,if there existsuch that

Lemma 2.2 Suppose that iteration point sequence{}i∈N0is yielded by Algorithm 2.1,then there exists an accumulation pointof{}i∈N0.

Proof If x ∈ LV(x0,?qi,?),according to ?q0? ?qi,?i∈ N0{0},one can see that ?q0(x)≤ ?qi(x0)≤ ψ(x0).Thus,it follows that LV(x0,?qi)? LV(x0,?q0,?).Further,we can conclude that set LV(x0,?qi,?)is a closed subset of compact set LV(x0,?q0,?),and so it is compact.For iteration point sequence{}i∈N0,one has∈LV(x0,?qi,?),thus,there exists an accumulation pointof{}i∈N0,and the proof is finished.

Lemma 2.3 Suppose that iteration point sequence{}i∈N0is generated by Algorithm 2.1,and the subsetconverges to.Thenis convergent,and

Proof First,we prove that 0 ≤ ψ(x)??qi(x)≤ Lgωdist(?qi,?),?x ∈ LV(x0,?q0,?),i∈N0.

If ψ(x)=0,then the formula above hold obviously.

If ψ(x) ＞ 0,choosing ωg∈ ?g(x),then there exists ωqi∈ ?qisuch that ‖ωg? ωqi‖ ≤Lgωdist(?qi,?).Furthermore,it follows that

By Algorithm 2.1,one can see thatApplying(2.3),we can conclude thatThus,the proof of this lemma is finished.

Lemma 2.4 Suppose that the stated assumption of Lemma 2.3 holds.Then,forthere exists an iteration point sequence{ωqi}i∈Isuch thatand ωqi→holds for i∈I large enough.

Proof From Lemma 2.1,we haveFor anyone obtainswe can conclude that

Theorem 2.1 Suppose that Assumptions 2.1–2.3 hold,and{}i∈N0is yielded by Algorithm 2.1,there exists an accumulation pointof{}i∈N0which is a KKT point for SIP(1.1).In such sense,Algorithm 2.1 is said to possess weak global convergence.

Proof By Lemma 2.2,one knows that there exists an accumulation pointof{}i∈N0.Choose an subset{}i∈I,I?N0,|I|=∞that converges toFrom the structure of Algorithm 2.1,we can see thatis the KKT point of SIPqi.Further,taking into account the theorem of Caratheodory,for s=n+1,i∈I and ωqi∈ ?act,qi(),one can conclude that

In view of[10,Lemma 3.4]and[11,Lemma 3.5],we can conclude that1,2,···,s are bounded.Thus,there exists a subset that converges to,j=1,2,···,s.Without loss of generality,we regard the subset as original sequence.Denote Jact()as an index set of ?act().By Lemma 2.4,one knows that,forthere exists a sequencesuch thatandfor i∈I large enough.Furthermore,through putting in order,one can get that,the firstindices of S(=1,2,···,s)correspond toofandMoreover,note that|S|＜ ∞ and ? are compact,we know that sequence or its subsequence···,s converges to∈ ?,j=l+1,···,s.So,passing to the limit for i∈ I and i→ ∞ in(2.4)–(2.7),combining with Lemma 2.3,we have

3 Algorithm Framework Based on Local Reduction Method

Local reduction method originates from ref.[14],which studies how to convert SIP local reduction to optimization problem with finite constraints.Conditions for the establishment of local reduction lemma and related conclusions can be seen in[1,15].The essence of local reduction lemma is that,under certain conditions,the original SIP problem is locally equivalent to an implicit finite constrained programming in the optimal solution.

Note that the algorithms for SIPq[8–11]can obtain an approximate solution of SIP.Inspired by local reduction method[1,15],we present a two phase algorithm framework for SIP.In the first phase,we apply algorithms for SIPqto obtain an approximate solution of SIP.Then,taking the approximate solution as a initial point,we switch to the second stage,i.e.,solve the local reduction problem of SIP,which is based on the idea of local reduction.As to the iterative method solving for SIP,a sufficient condition for the local reduction is given below.

Assumption 3.1(see[15])Suppose that iteration point sequence{xk}k∈N0is yielded by some iteration method for SIP.For any iteration point xk,k∈N0,problem

is regular,i.e.,

(i)any critical point of problem P(xk)is non-degenerative;

(ii)LICQ is satisfied by problem P(xk)at any ω ∈ ?.

Remark 2 Originally,local reduction lemma(see[1])and the assumptions need to solve global maximum points of P(xk).However,it is difficult to solve the global solution.In practice,we would like to solve local maximum points of P(xk).Some scholars improve the assumptions of local reduction lemma,in which we need to solve the local maximum points.Assumption 3.1 implies the updated assumptions hold[15],i.e.,it is a sufficient condition for the local reduction lemma.Moreover,it is also the basis of Lemma 3.1 below.

Lemma 3.1 (see[15])Suppose that Assumption 3.1 holds.Then there exists an neighborhood U(xk)of xksuch that,for any x∈U(xk),problem SIP(1.1)is equivalent to the following local reduction problem

The lemma above is the corollary of local reduction lemma,which is the basis of Algorithm 3.1 below.

Algorithm 3.1 A two phase algorithm framework based on local reduction method for SIP

Phase 1(Approximate phase)Choose a proper positive integer q(depending on the length of[a,b]),and discretize ? into ?q.For any x ∈ Rn,applying Algorithm A(see[8–11])to solve SIPqand obtain an approximate solution.

Phase 2(see[1,15])(Global phase)

Step 0x0=.Set k=0;

Step 1 Solve P(xk)to obtain all local maximum points,j∈Jl(xk);

Step 3 Applying some iterative methods such as SQP to solve(xk).Suppose the ikiterations are performed,and let initial point be,then the inner iteration points are in turn,i=1,2,···,ik.If i∈ {1,2,···,ik?1},then local maximum points of P()are made local correction,and yield

Step 4 Set xk+1=,k=k+1,and go back to Step 1.

Although the hypothesis of local reduction method is strong,local reduction is intrinsic method for SIP.In recent years,it is still concerned and studied,such as ref.[16].

4 Numerical Experiments

In this section,some preliminary numerical results are reported.All the numerical experiments are implemented on MATLAB 2016a on a 64-bit PC with an Intel Core i7-4790 CPU and 32GB of RAM.The tested problem P1 from[17],and P2 through P3 are taken from[18],which have the following form

with g and ? as follows:

P1:g(x,ω)=(1?ω2)?(0.5x2?2xω),? =[?1,1],x0=1,f(x?)=1.

P2:g(x,ω)= ω2?(x1ω +x2exp(ω)), ? =[0,2],x0=(1,1),f(x?)=0.53825.

For the record,x0is the initial point used the same as that of algorithms[6,7],and f(x?)is the objective function value given in refs.[15,17,18].Moreover,the tested problems above can be equivalent to inequality constrained SIP such as(1.1),and can be solved by our algorithm framework.

From the viewpoint of discretization method,for the closed interval ?=[a,b]of variation ω,it can be discretized into the following set by

where q re flects the discretization level of SIP(1.1).

During the test experiments,the following parameters are used for all tested problems:

In addition,for a given discretization level q,the stopping criterion is‖dk‖≤ 1×10?4or|zk|≤ 10?4,which is the same as of refs.[7,8].

To test the validity of Algorithm 2.1,in view of the equivalence ofandwithout loss of generality,we can assume that qi+1=2qi.The algorithm[8]is selected as Algorithm A,and the partial iterative results of Algorithm 2.1 for P1–P3 are reported in Table 1.

Table 2:Numerical results for problems with different discretization level q

In Table 1,the column i is ith iteration;qiindicates the discretization level at ith iteration.At ith iteration,SIPqiis solved,which is an inner loop.Assume that k iterations are executed in the inner loop.The columns Ni(=k)and Nf are the number of iterations and objective function evaluations,respectively;Ng is the number of constraint function g(x,ω)evaluations for a given x and ω; Σ|?k|is the sum over all iterations of the size of?k;||means the average size of ?k,i.e.,||=Σ|?k|/Ni;|??|is the size of ?kat the end of ith iteration;is the value of zkat the end of the ith iteration.Finally,f()is the objective function value at the end of ith iteration.From the column of||,we find that the average number of constraints per iteration is small,which can reduce the computational cost of Algorithm 2.1.Compared with previous numerical results,our algorithm framework based on discretization method is effective.

In addition,in view of ref.[15]reported the theory and the numerical experimentation in detail on Phase 2 of Algorithm 3.1,we just need to further illustrate the efficiency of Algorithm A in Phase 1 of Algorithm 3.1.For this purpose,we select q=10,20,50,100,200,500,1000,2000,5000,10000,respectively.For a given discretization level q,we apply Algorithm A(may as well take Algorithm A of[8]as an example)to solve SIPq.The computational results are reported in Table 2.

In Table 2,the column q indicates the given discretization level.The meanings of Ni,Nf,Ng,Σ|?k|,||,|??|are similar to those above,but all of them are generated by solving SIPq.Moreover,z?is the value of zkat the final iterate,and f(x?)is the objective function value at the final iterate point.

Comparing the results of Table 2 with previous numerical results[6,7,15,17,18],we find that choosing an appropriately large q can reduce calculation cost greatly,and the solution of SIPqis usually a good approximate solution of SIP,which is exactly required in Phase 1 of Algorithm 3.1.Thus,Phase 1 of Algorithm 3.1 can be better implemented.

5 Conclusions

In this paper,based on discretization method and local reduction,we present two algorithm frameworks for SIP,and solve problem how to solve SIP by the proposed algorithm in[8–11].The two algorithm frameworks not only improve the theory of algorithms for[8–11],but also play an important role to achieve the real solution of SIP.Finally,some preliminary numerical results are reported,which show the proposed two algorithm frameworks are effective.