关于具有不确定性凸半无限规划的近似解.pdf

应用数学MATHEMATICA APPLICATA2024,37(1):200-213On Approximate Solutions for ConvexSemi-infinite Programming withUncertaintySU Ke(苏珂)1,2,YU Mengyao(于梦瑶)1,2,LIN Yumeng(林雨萌)1,2(1.College of Mathematics and Information Science,Hebei University,Baoding 071000,China;2.Hebei Key Laboratory of Machine Learning andComputational Intelligence,Baoding 071000,China)Abstract:In this paper,we consider the approximate solutions(also called-solutions)for semi-infinite optimization problems that objective function and constraint functionswith uncertain data are all convex,then the robust counterpart of convex semi-infiniteprogram is established and the approximate solutions are considered.Moreover,the robustnecessary condition and robust sufficient theorems are obtained.Additional,the Lagrangianduality results in the sense of the approximate solution are given by the robust optimizationapproach under the proposed cone constraint qualification.Key words:Convex function;Approximate solution;Dual theorem;Semi-infinite;UncertaintyCLC Number:O224AMS(2010)Subject Classification:90C30;65K05Document code:AArticle ID:1001-9847(2024)01-0200-141.IntroductionFocus on the following convex semi-infinite programming(CSIP):(CSIP)minw(x)s.t.ht(x)0,t T,(1.1)where w(x):Rn R and ht(x):Rn R(t T)are convex and continuous functions,and Tis an infinite set.We call the problem(CSIP)linear semi-infinite programming,if w(x),ht(x)are all linear functions.Dual theory plays an important role in the study of semi-infinite programming problems.Goberna1summarized the publications on semi-infinite linear programming(SILP),whichaims to identify the most active research areas and the major trends in applications.Detailedbibliographical introduction on(SILP)and their extensions are contained in 2.The dualproblems of convex semi-infinite programming are discussed in 3-4.All the above semi-infinite programming assume the data in the model are determinate.But in real life,theReceived date:2023-01-02Foundation item:Supported by the Natural Science Foundation of Hebei Province(A2022201002),the Innovative Funding Program of Hebei Province(CXZZSS2023008)Biography:SU Ke,female,Han,Hebei,professor,major in mathematics.No.1SU Ke,et al.：On Approximate Solutions for Convex Semi-infinite Programming201information of optimization problems sometimes are uncertain,wrong or lacking,so it isimportant to discuss the dual problem under uncertain set5.Ben-Tal and Nemirovski et al.6proposed a deterministic framework for the mathematicalprogramming under uncertain data.The robust optimization methods for linear programmingproblems and convex optimization problems under uncertain data are discussed successfullyby Ghaoui7.In consideration of the uncertain data,Goberna8used robust duality theoryto deal with the convex programming problems.The research on the robust correspondencebetween dual problems and uncertain convex programming9shows that the value of therobust counterpart of primal problem is equal to the value of the optimistic counterpart ofthe dual primal(i.e.,primal worst equals dual best).Convex programming,in which the constraint functions are finite with uncertain data,can be summarized as follows10:(UCP)minw(x)s.t.hi(x,ui)0,i=1,m,(1.2)where hi(x,ui):Rn Rm R(i=1,m)are convex and ui Ui Rm(i=1,m)are uncertain parameters.In recent years,many scholars have studied the robust convex optimization problem withdata uncertainty11.Several selected topics in robust convex optimization are overviewed in12.Jeyakumar and LI13proved Lagrangian strong duality theorem,then defined a newrobust characteristic cone,and gave the necessary and sufficient conditions for the existenceof strong duality.The optimistic correspondence is proposed by 6.SUN et al.14studied therobust quasi-approximate optimal solution for a class of nonsmooth semi-infinite programmingwith uncertain data.Lee and Lee15focused on the approximate solution to robust convex optimization prob-lem,and established the duality theorem of Wolfe type dual problem with finite constraintfunction.Then Lee and Lee16defined the-solution of the robust semi-infinite optimiza-tion problem.Based on the closed convex cone,an approximate weak duality theorem and astrong duality theorem for the original problem and its Wolfe dual problem are established.Then,ZENG et al.17presented some modified robust solutions for fractional semi-infiniteprogramming with uncertain information.Lagrangian dual with finite constraints is studiedin 13.It shows strong dual property holds(i.e.,=0)under the robust characteristic coneas follows:M=uiUi,i0epi(mi=1ihi(,ui),where M is closed and convex,and(mi=1ihi(,ui)denotes the conjugate function of(mi=1ihi(,ui).With uncertain constraint conditions,(CSIP)can be summarized as follows:(UCSIP)minw(x)s.t.ht(x,ut)0,t T,(1.3)where ht(x,ut):RnRm R(for any t T)are continuous convex functions,and ut Rm(for any t T)are uncertain parameters,which belong to some convex compact sets Ut Rm.202MATHEMATICA APPLICATA2024Define the uncertain set-valued mapping U(t):T Rmas U(t):=Ut(for all t T).And u U implies that u is an element of U,i.e.,u(t):T Rmand u(t):=ut Ut(for allt T).The Lagrangian dual of(UCSIP)is given by(LDUCSIP)maxtinfxRnw(x)+tTtht(x,ut)s.t.t 0.(1.4)The robust counterpart of(UCSIP)can be summarized as follows:(RCSIP)minw(x)s.t.ht(x,ut)0,t T,ut Ut.(1.5)The best possible robust feasible solution is the one that solves the optimization problem(RCSIP).(RCSIP)is called the robust counterpart of the original uncertain problem(UCSIP).Motivated by the above,in this paper,we consider the approximate solutions(i.e.,0)for robust semi-infinite convex programming.By using the robust optimization method,therobust necessary condition and sufficient conclusions of(RCSIP)under the closed convex coneconstraints are established,denote the cone as follows:=utUt,t0,tTepi(tTtht(,ut),(1.6)where(tTtht(,ut)is the conjugate function of(tTtht(,ut).Moreover,under the closedconvex cone constraint qualification,between the primal problem and Lagrangian dualproblem,we prove that an approximate weak duality result and a strong duality theorem.Denote the optimistic counterpart of(LDUCSIP)as follows:(OLDCSIP)maxtinfxw(x)+tTtht(x,ut)s.t.t 0,t T,ut Ut,x Rn.(1.7)Denote the Lagrangian dual of the robust counterpart(RCSIP)as follows:(LDRCSIP)maxtinfxsuputw(x)+tTtht(x,ut)s.t.t 0,t T,ut Ut,x Rn.(1.8)We present the approximate weak dual theorem and strong dual theorem of(LDRCSIP)in Section 4.Given the feasible set of(UCSIP)as follows:F:=x Rn|ht(x,ut)0,t T,ut Ut.(1.9)Let 0.We call b x an-solution of(RCSIP),if b x satisfiesw(x)w(b x),for any x F.The rest of the paper is organized as following.We introduce some preliminaries andnotations in Section 2.Some conditions for the existence are discussed in Section 3.Ap-proximate weak and strong theorems are given in Section 4.In Section 5,we summarize thecontent of this article.No.1SU Ke,et al.：On Approximate Solutions for Convex Semi-infinite Programming2032.Notations and PreliminariesIn order to show our conclusions,we recall some symbols and preliminaries.Rnis repre-sented as the n-dimension Euclidean space,R+as the nonnegative quadrant of R,the graphof set U as gphU:=(t,ut)|ut Ut,t T,clA,coA,and coneA as the closure,the convexhull,and the conical hull severally.Let w(x):RneR,whereeR is an extended real set,denoted aseR=,+.If for all x Rn,w(x)and exists x Rnsuch thatw(x)R,then w(x)is said to be proper.Definition 2.1Let A be a closed and convex set in Rn.Call A:Rn R+theindicator function of A if A=0 as x A and A=+as x/A,i.e.,A(x):=0,if x A,+,otherwise.(2.1)Definition 2.2Define the domain of the function w(x):Rn R +as follows:domw:=x Rn|w(x)0,there exists 0 such that for all s T,Us Ut+B,where B is a unit ball in Rmand d(s,t)where d is the distance on U,then the set-valuedmapping U:T Rmis called the upper semi-continuous at t T,where(T,d)is a metricspace.If for any 0,there exists 0 such that for all s,t T,Us Ut+B with d(s,t),then U is called uniformly upper semi-continuous on T.In order to describe the relationship between the-sub-differential and the epigraph of aconjugate function,we give the following lemma,which plays a key role in the main results.204MATHEMATICA APPLICATA2024Lemma 2.1If w(x):Rn R +is proper,domw=x Rn|w(x)+=.Let w(x)be a proper lower semi-continuous convex function.Thenepiw=0(u,u,+w():w(),(2.8)where domw.Lemma 2.2If domw domh=,let w(x),h(x):Rn R +be proper lowersemi-continuous convex functions,thenepi(w+h)=cl(epiw+epih),(2.9)andepi(w+h)=epiw+epih,(2.10)where w(x)and h(x)are continuous.Lemma 2.3Let I be an arbitrary index set,hi(x):Rn R+(i I)be properlower semi-continuous convex functions.If there exists x Rnsuch that supiIhi(x)0 and(a,b)TutUt,t0,tTepi(tTtht(,ut).Then,there exist ut Ut,t 0,t T,such that(a,b)T epi(tTtht(,ut).Let t=t 0.Then(a,b)T epi(tTtht(,ut)=epi(tTtht(,ut)utUt,t0,tTepi(tTtht(,ut).Hence,utUt,t0,tTepi(tTtht(,ut)is a cone.Generally speaking,without the convexity of the functions ht(x,ut),most robust char-acteristic cones are not convex cones.We next illustrate that convexity of the robust characteristic cone under the concavityof h(x,)and the convexity of Ut.Lemma 2.5Let ht(x,ut):RnRm R(t T)be continuous functions.Assume thatfor every convex set Ut Rm,every ut Rm,t T,ht(,ut)are convex,ht(x,)are concaveon Ut(for any x Rn),then=utUt,t0,tTepi(tTtht(,ut)(2.13)No.1SU Ke,et al.：On Approximate Solutions for Convex Semi-infinite Programming205is convex.ProofIn order to prove its convexity,let(ai,bi)T,i=1,2,and 0,1.Inorder to illustrate is convex,we need to prove that(a1+(1)a2,b1+(1)b2)T.Obviously,is a cone,(a1,b1)T and(1 )(a2,b2)T.Therefore,for each i=1,2,there exist u1t Ut(t T)and 1t,2t 0 such that(a1,b1)T epi(tT1tht(,u1t),(1 )(a2,b2)T epi(tT2tht(,u2t).(2.14)According to the definition of epiw,we have(tT1tht(,u1t)(a1)+(tT2tht(,u2t)(1 )a2)b1+(1 )b2.(2.15)For t T,t:=1t+(1 )2t,(2.16)ut:=u1t,if t=0,1ttu1t+(1 )2ttu2t,if t 0.(2.17)If t=0,i.e.,1t=2t=0,hence,1tht(x,u1t)+(1 )2tht(x,u2t)=tht(x,ut).(2.18)If t=0,i.e.,t 0,then1tht(x,u1t)+(1 )2tht(x,u2t)=t(1ttht(x,u1t)+(1 )2ttht(x,u2t)tht(x,1ttu1t+(1 )2ttu2t)=tht(x,ut),t T.(2.19)Actually,according to the definition of concave function,the second inequality in(2.19)holds.By(2.15),we haveb1+(1 )b2(tT1tht(,u1t)(a1)+(tT2tht(,u2t)(1 )a2)=supxRna1,x tT1tht(x,u1t)+supxRn(1 )a2,x tT2tht(x,u2t)supxRna1+(1 )a2,x tT(1tht(x,u1t)+2tht(x,u2t)supxRna1+(1 )a2,x tT(1tht(x,ut)=(tTtht(,ut)(a1+(1 )a2).(2.20)Because of Definition 2.3,the second equality in(2.20)holds,and the fourth inequality in(2.20)holds by(2.15).Hence,(a1+(1 )a2,b1+(1 )b2)T.206MATHEMATICA APPLICATA2024Lemma 2.6Let ht(x,ut):Rn Rm R(t T)be continuous convex functions,suchthat for any ut Rm,ht(,ut)is convex.Suppose that each Utis convex and compact,thereexists x Rnsuch thatht(x,ut)0,since U is uniformly upper semi-continuous,there exists 0 such thatUt Uti+B,where B is a closed unit ball in Rnfor any t T with d(t,ti).Since ti tias ,there exists i N such that for all i,d(ti,ti).Hence,for all i,it holdsUti Uti+B.Since uti Uti,there exists ti Utisuch that uti ti+B,i.e.,uti ti .No.1SU Ke,et al.：On Approximate Solutions for Convex Semi-infinite Programming207Therefore,infltiUtiuti lti .That means,there exists i N such that for all i,d(uti,Uti).Hence,d(uti,Uti)0 as ,i.e.,uti Uti,then there exists lti Uti(=1,2,)suchthatd(uti,Uti)=uti lti 0as .Since Utiis compact,we have zti uti Utias .Thenlimuti uti=lim(uti lti)+(lti uti)limuti lti+limzti uti=0.(2.27)If ,we have uti uti.Next,we prove that z:=n+1i=1ti+tis bounded.By the contract,let z.Assume thattiz i R+(i=1,.,n+1)andtz 0 R+withn+1i=1i+0=1.Thenaccording to(2.26)and Definition 2.3,for any x Rn,we have(s)Tx n+1i=1tihti(x,uti)(n+1i=1tihti(x,uti)(s)r t r.(2.28)Divided by zon both sides of the last inequality and taking the limit,we haven+1i=1ihti(x,uti)0,x Rn.If i=0,i=1,n+1,then we get0=n+1i=1ihti(x,uti)1.This is contrary to the assumption.Also,if i=0,for some i,thenn+1i=1ihti(x,uti)0.The assumption is contrary to(2.21)as 0 n+1i=1i 1.Hence,zis bounded.Because of theboundness of z,we have ti tiand t t.For each x Rn,it holds(s)Tx n+1i=1tihti(x,uti)r t.(2.29)Taking the limit on both side,because htare continuous,we have(x)Txn+1i=1tihti(x,uti)r t,x Rn,and it follows that(x,r t)T epi(n+1i=1tihti(,uti),208MATHEMATICA APPLICATA2024(x,r)T epi(n+1i=1tihti(,uti)+t(0,1)epitTt(ht(,ut)+0 R+utUt,t0,tTepi(tTtht(,ut)=.(2.30)Therefore,is closed.3.Necessary Conditions for Dual TheoremSome main necessary optimality conditions for a robust approximate optimal solution of(UCSIP)are discussed in this section.In order to show necessary conditions for dual theorem,we give the following Robust Farkas lemma of convex function.Lemma 3.1Let w(x):Rn R and ht(x,ut):Rn Rm R be convex functions.Let Ut Rm(t T)be compact and F:=x Rn:ht(x,ut)0,for all ut Ut,t T benonempty.Then the following relationships are equivalent:(i)x Rn|ht(x,ut)0,ut Ut,t T x Rn|w(x)0;(ii)(0,0)T epiw+cl coutUt,t0,tTepi(tTtht(,ut).(3.1)ProofBy the definition of F,we need to prove thatepiF=cl coutUt,t0,tTepi(tTtht(,ut).For any x Rn,F(x)=suputUt,t0,tTtTtht(x,ut).Thus we haveepiF=cl(epiF)=clutUt,t0,tTepi(tTtht(,ut)=clcl coutUt,t0,tTepi(tTtht(,ut)=cl coutUt,t0,tTepi(tTtht(,ut),(3.2)where the third equality in(3.2)holds by Lemma 2.3.Hence,we get(ii)(0,0)T epiw+epiF(according to(3.1)(0,0)T epi(w+F)(invokes Lemma 2.2)(w+F)(0)0(follows from Definition 2.3)(w+F)(0)=supx,0 (w+F)(x):x Rn=sup0 (w+F)(x)(w+F)(x)0,x Rn(by Definition 2.4)w(x)0,x F(i).(3.3)No.1SU Ke,et al.：On Approximate Solutions for Convex Semi-infinite Programming209According to Lemma 3.1,the following theorem holds:Theorem 3.1Let w(x):Rn R be a convex function,and ht(x,ut):Rn Rm Rbe continuous for any t T,ht(,ut)is convex on Rnfor each ut Rm.Let b x F and defineUt Rm(t T)is compact.Assume that be closed and convex,then b x is an approximatesolution(-solution)of(RCSIP)if and only if there exist(bt)0 and b ut Ut(t T),suchthat for any x Rn,it holdsw(x)+tTbtht(x,b ut)w(b x).(3.4)Proof(Sufficiency)Suppose that b x is an-solution of(RCSIP),i.e.,for any x F,b xsatisfies w(x)w(b x).Then F x Rn:w(x)w(b x)+0.By Lemma 3.1,(0,w(b x)T epiw+cl coutUt,t0,tTepi(tTtht(,ut).(3.5)And coneutUt,t0,tTepi(tTtht(,ut)is closed and convex,hence(3.5)is equivalentto(0,w(b x)T epiw+utUt,t0,tTepi(tTtht(,ut).(3.6)Therefore letbt 0,ut Ut,we have(0,w(b x)T epiw+epi(tTbtht(,b ut).(3.7)Because ht(x,ut):Rn Rm R(t T)are continuous andbt 0,together with Lemma2.2,we have,(0,w(b x)T epiw+(tTepi(btht(,b ut).(3.8)That is Rn,p 0,st Rn,and qt 0(t T)such that(0,w(b x)T(,w()+p)+tT(st,(btht(,b ut)(st)+qt).(3.9)Therefore,0=+tTst,w(b x)=w()+p+tT(btht(,b ut)(st)+qt).(3.10)Hence,according to(3.10),for any x Rn,tTst,x w(x)=s,x w(x)w(s)=w(b x)p tT(btht(,b ut)(st)+qt),(3.11)where the second inequality in(3.11)holds by w(s)=sups,s w(s),s Rn.Thus,for any x Rn,w(b x)tTst,x+w(x)p tT(btht(,b ut)(st)tTqt210MATHEMATICA APPLICATA2024tTst,x+w(x)tT(btht(,b ut)(st)w(x)+tTbtht(x,b ut).(3.12)According to the definition of conjugate function of ht(,b ut),the th