On Approximate Solutions for Convex Semi-infinite Programming with Uncertainty

SU Ke(苏珂) ,YU Mengyao(于梦瑶) ,LIN Yumeng(林雨萌)

(1. College of Mathematics and Information Science, Hebei University,Baoding 071000, China; 2. Hebei Key Laboratory of Machine Learning and Computational 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 functions with uncertain data are all convex,then the robust counterpart of convex semi-infinite program is established and the approximate solutions are considered.Moreover,the robust necessary condition and robust sufficient theorems are obtained.Additional,the Lagrangian duality results in the sense of the approximate solution are given by the robust optimization approach under the proposed cone constraint qualification.

Key words: Convex function;Approximate solution;Dual theorem;Semi-infinite;Uncertainty

1.Introduction

Focus on the following convex semi-infinite programming (CSIP):

wherew(x):Rn →R and:Rn →R(t ∈T)are convex and continuous functions,andTis an infinite set.We call the problem(CSIP)linear semi-infinite programming,ifw(x),are all linear functions.

Dual theory plays an important role in the study of semi-infinite programming problems.Goberna[1]summarized the publications on semi-infinite linear programming (SILP),which aims to identify the most active research areas and the major trends in applications.Detailed bibliographical introduction on (SILP) and their extensions are contained in [2].The dual problems of convex semi-infinite programming are discussed in [3-4].All the above semiinfinite programming assume the data in the model are determinate.But in real life,the information of optimization problems sometimes are uncertain,wrong or lacking,so it is important to discuss the dual problem under uncertain set[5].

Ben-Tal and Nemirovski et al.[6]proposed a deterministic framework for the mathematical programming under uncertain data.The robust optimization methods for linear programming problems and convex optimization problems under uncertain data are discussed successfully by Ghaoui[7].In consideration of the uncertain data,Goberna[8]used robust duality theory to deal with the convex programming problems.The research on the robust correspondence between dual problems and uncertain convex programming[9]shows that the value of the robust counterpart of primal problem is equal to the value of the optimistic counterpart of the 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 follows[10]:

In recent years,many scholars have studied the robust convex optimization problem with data uncertainty[11].Several selected topics in robust convex optimization are overviewed in[12].Jeyakumar and LI[13]proved Lagrangian strong duality theorem,then defined a new robust characteristic cone,and gave the necessary and sufficient conditions for the existence of strong duality.The optimistic correspondence is proposed by[6].SUN et al.[14]studied the robust quasi-approximate optimal solution for a class of nonsmooth semi-infinite programming with uncertain data.

Lee and Lee[15]focused on the approximate solution to robust convex optimization problem,and established the duality theorem of Wolfe type dual problem with finite constraint function.Then Lee and Lee[16]defined theε-solution of the robust semi-infinite optimization problem.Based on the closed convex cone,an approximate weak duality theorem and a strong duality theorem for the original problem and its Wolfe dual problem are established.Then,ZENG et al.[17]presented some modified robust solutions for fractional semi-infinite programming with uncertain information.Lagrangian dual with finite constraints is studied in [13].It shows strong dual property holds (i.e.,ε=0) under the robust characteristic cone as follows:

With uncertain constraint conditions,(CSIP) can be summarized as follows:

whereht(x,ut):Rn×Rm →R (for anyt ∈T) are continuous convex functions,andut ∈Rm(for anyt ∈T)are uncertain parameters,which belong to some convex compact setsUt ⊂Rm.

Define the uncertain set-valued mappingU(t) :T →RmasU(t) :=Ut(for allt ∈T).Andu ∈Uimplies thatuis an element ofU,i.e.,u(t):T →Rmandu(t):=ut ∈Ut(for allt ∈T).

The Lagrangian dual of (UCSIP) is given by

The robust counterpart of (UCSIP) can be summarized as follows:

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,the robust necessary condition and sufficient conclusions of(RCSIP)under the closed convex cone constraints are established,denote the coneΓas follows:

Denote the optimistic counterpart of (LDUCSIP) as follows:

Denote the Lagrangian dual of the robust counterpart (RCSIP) as follows:

We present the approximate weak dual theorem and strong dual theorem of (LDRCSIP)in Section 4.Given the feasible set of (UCSIP) as follows:

Letε ≥0.We callanε-solution of (RCSIP),ifsatisfies

for anyx ∈F.

The rest of the paper is organized as following.We introduce some preliminaries and notations in Section 2.Some conditions for the existence are discussed in Section 3.Approximate weak and strong theorems are given in Section 4.In Section 5,we summarize the content of this article.

2.Notations and Preliminaries

In order to show our conclusions,we recall some symbols and preliminaries.Rnis represented as then-dimension Euclidean space,R+as the nonnegative quadrant of R,the graph of setUas gphU:={(t,ut)|ut ∈Ut,t ∈T},clA,coA,and coneAas the closure,the convex hull,and the conical hull severally.Letw(x) : Rn →whereis an extended real set,denoted as=[-∞,+∞].If for allx ∈Rn,w(x)>-∞and existsx′∈Rnsuch thatw(x′)∈R,thenw(x) is said to be proper.

Definition 2.1LetAbe a closed and convex set in Rn.CallδA:Rn →R∪{+∞}the indicator function ofAifδA=0 asx ∈AandδA=+∞asx/∈A,i.e.,

Definition 2.2Define the domain of the functionw(x):Rn →R∪{+∞}as follows:

Definition 2.3Define the epigraph of the functionw(x):Rn →R∪{+∞}as follows:

Definition 2.4Define the conjugate function ofw(x) asw∗(x∗):Rn →R∪{+∞},for any proper convex functionw(x) on Rn,and for anyx∗∈Rn,

Definition 2.5Callw(x) a convex function,if for anyµ∈[0,1],x,y ∈Rn,it holds

It is easy to show that epiwis convex according to Definition 2.5.Since-w(x) is a convex function,the functionw(x) is a concave function.

The sub-differential of domwatx ∈domwis defined by

Ifxdomw,∂xw(x) is empty.More generally,forε ≥0,define theε-sub-differential ofw(x) atx ∈domwas follows:

Forxdomw,∂εw(x) is empty.We callwbe a lower semi-continuous function if

for allx ∈Rn.

Definition 2.6[15]For anyε>0,there existsρ>0 such that for alls ∈T,Us ⊂Ut+εB,whereBis a unit ball in Rmandd(s,t)≤ρwheredis the distance onU,then the set-valued mappingU:T →Rmis called the upper semi-continuous att ∈T,where (T,d) is a metric space.

If for anyε>0,there existsρ>0 such that for alls,t ∈T,Us ⊂Ut+εBwithd(s,t)≤ρ,thenUis called uniformly upper semi-continuous onT.

In order to describe the relationship between theε-sub-differential and the epigraph of a conjugate function,we give the following lemma,which plays a key role in the main results.

Lemma 2.1Ifw(x):Rn →R∪{+∞}is proper,domw={x ∈Rn|w(x)<+∞}=∅.Letw(x) be a proper lower semi-continuous convex function.Then

whereξ ∈domw.

Lemma 2.2If domw ∩domh∅,letw(x),h(x) : Rn →R∪{+∞}be proper lower semi-continuous convex functions,thenwherew(x) andh(x) are continuous.

Lemma 2.3LetIbe an arbitrary index set,hi(x):Rn →R∪{+∞}(i ∈I) be proper lower semi-continuous convex functions.If there existsx′∈Rnsuch that supi∈Ihi(x′)<+∞.Then

Lemma 2.4Letut ∈Rm,for any vectorx,ht(x,ut):Rn×Rm →R(t ∈T) be convex functions andht(x,ut) be continuous functions,then

is called the robust characteristic cone,and the cone is convex and closed.

ProofLetλt=0(t ∈T),it holds

Generally speaking,without the convexity of the functionsht(x,ut),most robust characteristic cones are not convex cones.

We next illustrate that convexity of the robust characteristic cone under the concavity ofh(x,·) and the convexity ofUt.

Lemma 2.5Letht(x,ut):Rn×Rm →R(t ∈T)be continuous functions.Assume that for every convex setUt ⊆Rm,everyut ∈Rm,t ∈T,ht(·,ut) are convex,ht(x,·) are concave onUt(for anyx ∈Rn),then

is convex.

According to the definition of epiw,we have

Ifλt=0,i.e.,λt>0,then

Actually,according to the definition of concave function,the second inequality in(2.19)holds.

By (2.15),we have

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∈Γ.

Lemma 2.6Letht(x,ut): Rn×Rm →R(t ∈T) be continuous convex functions,such that for anyut ∈Rm,ht(·,ut) is convex.Suppose that eachUtis convex and compact,there exists∈Rnsuch that

is closed.

ProofWe define that

According to the proposition of proper lower semi-continuous convex functions and functionsht(·,ut) are continuous,it holds

Together with (2.23),it can be obtained that

BecauseTis compact,we have→ti ∈Tasκ →∞,i=1,···,n+1.

Fori=1,···,n+1 andε>0,sinceUis uniformly upper semi-continuous,there existsρ>0 such that

whereBis a closed unit ball in Rnfor anyt ∈Twithd(t,ti)≤ρ.Since→tiasκ →∞,there existsκi ∈N such that for allκ ≥κi,

Hence,for allκ ≥κi,it holds

Therefore,

That means,there existsκi ∈N such that for allκ ≥κi,

Ifσi=0,∀i=1,···,n+1,then we get

This is contrary to the assumption.Also,ifσi=0,for somei,then

Therefore,Γis closed.

3.Necessary Conditions for Dual Theorem

Some 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.1Letw(x) : Rn →R andht(x,ut) : Rn×Rm →R be convex functions.LetUt ⊆Rm(t ∈T) be compact andF:={x ∈Rn:ht(x,ut)≤0,for allut ∈Ut,t ∈T}be nonempty.Then the following relationships are equivalent:

ProofBy the definition ofF,we need to prove that

where the third equality in (3.2) holds by Lemma 2.3.

Hence,we get

According to Lemma 3.1,the following theorem holds:

Becauseht(x,ut) : Rn×Rm →R(t ∈T) are continuous and≥0,together with Lemma 2.2,we have,

Hence,according to (3.10),for anyx ∈Rn,

where the second inequality in (3.11) holds byw∗(s∗)=sup{〈s∗,s〉-w(s),s ∈Rn}.Thus,for anyx ∈Rn,

According to the definition of conjugate function ofht(·,),the third inequality in (3.12) is true.

For anyx ∈F,we have

It impliesw(x)≥w-ε.Henceis an approximate solution of (RCSIP).

Theorem 3.2(εoptimality theorem) Letw(x) : Rn →R be a convex function,andht(x,ut) : Rn×Rm →R (for anyt ∈T) be continuous such that for eachut ∈Rm,ht(·,ut)is convex on Rn.LetUt ⊆Rm(t ∈T) be compact.Assume thatΓis closed and convex.Let∈F,then the following (i),(ii),(iii) are equivalent:

and by Lemma 3.1,it holds that (i)⇔(ii).

LetF:={x ∈Rn:ht(x,ut)≤0,∀ut ∈Ut,t ∈T},thenF∅.

According to(ii),we get

By Lemma 2.1,there existε0≥0,εt ≥0,t ∈T,thenw(x) andut ∈Rm,ht(·,ut) are convex,such that

which is equivalent to (iii).

4. ε-Duality Theorem of Lagrangian Dual

Next,using the approximate solution to(RCSIP),we consider a Lagrangian dual problem(LDRCSIP)εas follows:

Theorem 4.1Supposexand(z,u,λ)are feasible solutions of(RCSIP)and(LDRCSIP)ε,respectively.If

thenxsatisfies the approximate weak duality theorem.

The conclusion holds.

Then according to Theorem 4.1,

5.Conclusion

A convex semi-infinite optimization problem with uncertain information in the constraint function is established in this paper.Based on the robust optimization approach,some approximate optimality qualifications and approximate dual theorem are all established under a closed and convex coneΓ.Then a Lagrangian dual problem is established,and the approximate weak dual and strong dual theorem with uncertain data are also given in this paper.In the future research,it is worth considering that,under more generalized convexity and weaker constraint specifications,whether the dual theory and approximate solution of this kind of uncertain semi-infinite optimization can be established.