Ergodic Approach to Robust Optimization and Infinite Programming Problems
Pedro Pérez-Aros











Instituto de Ciencias de la Ingeniería,
	Universidad de O'Higgins  Libertador Bernardo O'Higgins 611, Rancagua, Región del Libertador Gral. Bernardo O’Higgins, Chile 

              pedro.perez@uoh.cl           







Ergodic Approach to Robust Optimization  and Infinite Programming Problems  



    Pedro Pérez-ArosThis work was partially supported by CONICYT Chile under grants Fondecyt Regular 1190110 and Fondecyt Regular 1200283.

    Received: date / Accepted: date
===========================================================================================================================================




In this work, we show the consistency of an approach for solving robust optimization problems using sequences of sub-problems generated by ergodic measure preserving transformations. 

The main result of this paper is that the minimizers and the optimal value of the sub-problems converge, in some sense, to the minimizers and the optimal value of the initial problem, respectively. Our result particularly implies the consistency of the scenario approach for nonconvex optimization problems.  Finally, we show that our method can also be used to solve infinite programming problems.



MSC 90C15 90C26  90C90 60B11




§ INTRODUCTION

Robust optimization (RO)  corresponds to a field of mathematical programming dedicated to the study of problems with uncertainty. In this class of models, the constraint set is given by the set of points, which satisfy all (or in the presence of measurability, almost all) possible cases.   Roughly speaking, an RO problem corresponds to the following mathematical optimization model 

    min g(x)   
    s.t.    x∈ M(ξ),    almost surely ξ∈Ξ,

where  X is a Polish space, (Ξ, 𝒜,ℙ) is a probability space,  M: Ξ X is a measurable multifunction with closed values and  g: X → is  a lower semicontinuous   function.  We refer to  <cit.> and the references therein for more details and applications.

When the number of possible scenarios ξ∈Ξ is  infinite in Problem (<ref>), the computation of necessary and sufficient optimality conditions presents difficulties and requires a more delicate analysis than a simpler optimization problem. As far as we know, only  works related to infinite programming deal directly with infinite-many constraints (see, e.g., <cit.> and the references therein). For that reason, it is necessary to solve an approximation of  Problem (<ref>). In this regard, the so-called scenario approach emerges as a possible solution. The  scenario approach corresponds to a min-max approximation of the original robust optimization problem using a sequence of samples.   It has used to provide an approximate solution to convex and nonconvex optimization problems (see, e.g., <cit.>). Furthermore,  the consistency of this method has been recently  provided in <cit.> for convex optimization problems.

The intention of this work is to provide the consistency of the following method used to solve RO problems: Consider an  ergodic measure preserving transformation  T: Ξ→Ξ, then one can systematically  solve the  sequence of optimization problems

    min g_n(x)
    
    s.t.       x ∈ M(T^k(ξ));   k=1,…,n,

where g_n is a sequence of functions, which converge continuously to the objective function g, and  T^k represents the k-times composition  of T. Here, the desired conclusion is that the optimal value and the minimizers of  (<ref>)  converge, in some sense, to the optimal value and the minimizers of  (<ref>) for almost all possible  choices of ξ∈Ξ. This conclusion is established in Corollary <ref>, which follows directly from our main result Theorem <ref>. 

The key point in our results is to make a connection among three topics: (i)  the ideas of scenario approach, (ii) an  ergodic theorem for random lower semicontinuous functions established in  <cit.>, and (iii) the theory of epigraphical convergence of functions.  After that, and due to the enormous developments in the theory of epi-convergence (see, e.g., <cit.>), we can quickly establish some link between  the minimizers and the optimal value of the robust optimization problem (<ref>) and its corresponding approximation (<ref>).




As a consequence of this method,  we obtain the   consistency of the scenario approach  for nonconvex optimization problems. More precisely, in this method one considers a drawing of independent and ℙ-distributed random function ξ_1,ξ_2,…, and systematically  solves the sequence of optimizations problems.

    min g_n(x)
    
    s.t.       x ∈ M(ξ_k);   k=1,…,n.
 
Again, the  conclusion relies on showing that the optimal value and the minimizers of  (<ref>) converges to the solution of (<ref>) for almost all possible 
sequences (ξ_1,ξ_2,…).

It is worth mentioning that our method allows us to  solve nonconvex optimization problems and to consider a perturbation of the objective function g in (<ref>) and (<ref>), which is not guaranteed by the results of <cit.>. Here, it has not escaped our notice   that the perturbation of  g could be useful to ensure smoothness of the objective function in (<ref>) and (<ref>). On the other hand, the functions g_n could be used to guarantee the existence and uniqueness of the numerical solutions of  (<ref>) and (<ref>).


The rest of the paper is organized as follows:  In Section <ref>, we summarize the main definitions and notions using in the presented manuscript.  Next, in   Section <ref>, we provide our main result, which is the consistency of the method presented in (<ref>). In Section  <ref>, first, we show that our result can be used to provide direct proof of the consistency of the scenario approach for (even) nonconvex optimization problems, second, we show that our ergodic approach  can  be applied to problems related to infinite programming. In Section <ref>, we show some simple numerical examples of our results. Finally,  the paper ends with some conclusions and perspectives for future investigations.
 



§ NOTATION AND PRELIMINARY

In the following, we consider that (X,d) is a Polish space, that is to say, a complete  separable metric space and (Ξ,𝒜,ℙ)  is a complete probability space. The Borel σ-algebra on X is denoted by ℬ(X), which we recall  is the smallest σ-algebra containing all open sets of X. 

For a function f:X →, a set C⊆ X  and α∈ℝ,  we define the α-sublevel set of f on C as 
    lev_≤α (f,C):={  x∈  C: f(x) ≤α},

when C=X, we omit the symbol C. We say that f is lower semicontinuous  (lsc) if for all α∈ℝ the α-sublevel set of f on X is closed. 

Following <cit.>, let us consider a set C ⊆ X and ϵ≥ 0. We define the ϵ-infimal value of f on C by

    v_ϵ(f,C):={[    inf_C f + ϵ,  ifinf_C f >-∞,;          - 1/ϵ, if inf_C f =-∞. ].

with the convention 1/0=+∞. We omit the symbol   C, or ϵ when C=X, or when ϵ=0, respectively. Furthermore, we define the ϵ- of f on C by 

    ϵ-_C f := { x∈ C:  f(x) ≤ v_ϵ(f,C)      },

again we omit the symbol   C, or ϵ when C=X or when ϵ=0, respectively.

For a set A ⊆ X, we define the indicator function of A, given by,

    δ_A(x):={[        0, if  x∈ A,;       +∞, if  x∉ A. ].



A function f: Ξ× X → is called a random lower semicontinuous function  (also called a normal integrand function) if 

	
  * the function (ξ, x) → f(ξ, x) is 𝒜⊗ℬ(X)-measurable, and 
	
  * for every ξ∈Ξ the function f_ξ :=f(ξ, ·) is  lsc.




Let us consider a set-valued map (also called a multifunction) M: Ξ X. We  say that M is measurable  if for every open set U ⊆  X the set 

    M^-1(U):={  x ∈ X : M(x) ∩ U≠∅}∈𝒜.

For more details about the theory of normal integrand  and measurable multifunctions we refer to <cit.>.

Consider a sequence of sets S_n ⊆ X. We set lim inf_n→∞  S_n  and lim sup_n→∞ S_n as the inner-limit and the outer-limit, in the sense of  Painlevé-Kuratowski, of the sequence S_n, respectively,  that is to say,

    lim inf_n→∞ S_n    := {  x ∈ X:lim sup_n→∞ d(x,S_n) =0}
    lim sup_n→∞ S_n   :={  x ∈ X:lim inf_n→∞ d(x,S_n) =0},

where d(x,S_n):=inf{ 	d(x,y) : y ∈ S_n			}.

Now, let us recall  some  notations about the convergence of functions. 

	Let  f_n:X→ be a sequence of functions. The functions f_n are said to epi-converge to f, denoted by f_n f,  if for every x∈ X
	
		
  * lim inf_n→∞ f_n(x_n) ≥ f(x) for all x_n → x.
		
  * lim sup_n→∞ f_n(x_n) ≤ f(x) for some x_n → x. 
	

We refer to <cit.> for more details about the theory of epi-graphical convergence. 


Also, we will need the following notation, which is equivalent to uniform convergence over compact sets for continuous functions (see, e.g., <cit.>).


	We say that a sequence of functions f_n:X→ℝ∪{ +∞} converges continuously to f, if for every x∈ X and every x_n → x
	
    lim_n→∞ f_n(x_n) =f(x).







The following definition is an extension of the notation  eventually level-bounded  used in finite-dimension setting, which can be found in <cit.>. We extend this notation as follows: Consider a sequence of functions (f_n)_n∈ℕ and a sequence of sets (C_n)_n∈ℕ, we say that a sequence of functions f_n is eventually level-compact on C_n, if for each α∈ℝ  there exists n_α∈ℕ such that  
    ⋃_n ≥ n_αlev_≤α(f_n,C_n)   is relatively compact.
 
In particular, if C_n =X, we simply say that f_n is eventually level-compact.

Now, we present two results. The first lemma shows that the sum of an epi-convergent sequence and a continuously convergent sequence   epi-convergences to the sum of limits.  The second proposition corresponds to a slight generalization of <cit.> (see also <cit.>), where only sequences ϵ_n → 0 were considered. For the sake of brevity we shall omit the proves.
 



	Consider sequences of functions p_n,q_n: X → such that p_n converges continuously to p and q_n epi-converges to q. Then,
	p_n+q_n  p+q.

 
 

	Let f_n  f and ϵ_n ≥ 0 be a  sequence such that  ϵ =lim supϵ_n<+∞. Then,
	
		
  * lim sup v_ϵ_n(f_n) ≤ v_ϵ(f).
		
  * lim supϵ_n- f_n  ⊆ϵ- f.
	

 



§ CONSISTENCY OF  THE  APPROACH TO ROBUST OPTIMIZATION PROBLEMS

In this section we consider the following  optimization problem


    ℛ     min g(x)
    
    s.t.      x ∈M,

where M:={  x∈ X: x ∈ M(ξ)  a.s.},  g: X→ is an lsc function and M: Ξ X is a measurable multifunction with closed values. We study  an approach using  ergodic measure preserving transformation. Particularly,  we show the consistency of this method. 



Now, we consider the following approach using ergodic measure  preserving transformation. First, let us formally introduce this notion.
Consider a (complete) probability space  (Ξ,𝒜,ℙ ) and a measurable function T: Ξ→Ξ. We say that T preserves measure if

    ℙ( T^-1(A) )= ℙ(A),   for all A∈𝒜.

Furthermore, we say that T is ergodic provided that for all A∈𝒜

    A=T^-1(A) ⇒ℙ(A)=0,  or ℙ(A^c) =0.

Consequently, we say that T is an  ergodic measure  preserving transformation provided that  T satisfies (<ref>) and (<ref>) .


We consider a sequence of lsc functions g_n, which converge continuously to g,  let us consider an  ergodic measure preserving transformation  T: Ξ→Ξ.  With this setting, we define the following family of optimization problems: For a point ξ∈Ξ we define

    ℰ_n(ξ)         min g_n(x)
    
    s.t.       x ∈ E_n(ξ):=⋂_k=1^n M(T^k(ξ)),

where T^k denotes the k-times composition of T.  In order to show  more clearly the link of epigraphical convergence and the relation  between (<ref>) and (<ref>), let us define the functions 
f_n : Ξ× X → and f: Ξ× X → by

    f_n(ξ, x)   := g_n(x) + 1/n∑_k=1^nδ_M(T^k(ξ))(x),
    
    f(x)   := g(x) + δ_M(x).

With this notation we can write the relationship  between (<ref>) and (<ref>) in a functional formulation.

	Under the above setting we have that f_n(ξ,·)  f, ℙ-a.s. Consequently for any measurable sequence ϵ_n :Ξ^∞→ (0,+∞) with ϵ(ξ) :=lim supϵ_n(ξ)<+∞,  ℙ-a.s.  we have that:
	
		
  * lim sup_n→∞v_ϵ_n(ξ)  (f_n(ξ,·) ) ≤  v_ϵ(ξ) (f), ℙ-a.s.
		
  * lim sup_n→∞ϵ_n(ξ)- f_n(ξ,·) ⊆ϵ(ξ)- f, ℙ-a.s.
	



	Let us consider the sequence of functions 
    p_n(x):=g_n(x)   and   q_n(ξ, x):=1/n∑_k=1^nδ_M( T^k(ξ))(x)
. 
	
	It is not difficult to see that  the function (ξ, x) →δ_M(ξ)(x) is a random lsc function and the function ξ→infδ_M(ξ)(x) is integrable. Then, by <cit.>, we have that 
    q_n(ξ,·) 𝔼_ξ(δ_M(ξ)(·))=δ_M(·),  ℙ-a.s.

	Now, define Ξ̂:={ξ∈Ξ : q_n(ξ,·) δ_M}, it follows that ℙ(Ξ̂)=1. Thus for all ξ∈Ξ̂ we apply Lemma <ref>, which implies that  for all ξ∈Ξ̂,   we have p_n + q_n(ξ, ·) e→ f, that is to say, 
	f_n(ξ, · ) e→ f for all  ξ∈Ξ̂.
	
	Now, by Proposition <ref> we have that for all ξ∈Ξ̂,
	
    lim sup_n→∞v_ϵ_n(ξ)  (f_n(ξ,·) ) ≤  v_ϵ(ξ) (f),  and
    lim sup_n→∞ϵ_n(ξ)- f_n(ξ,·) ⊆ϵ(ξ)- f,

	which concludes the proof.


 When there are additional assumptions about  the feasibility and compactness of the optimization problems  (<ref>) and (<ref>) we can establish  a tighter conclusion. We translate the hypothesis into notation of the problems (<ref>) and (<ref>), respectively.

	Let us assume that  (<ref>) is feasible, and  the sequence of function g_n  is eventually level compact on E_n(ξ)   ℙ-a.s. ξ∈Ξ.	Then,
	
		
  * lim_n→∞v( g_n, E_n(ξ) ) =  v(g,M_as), ℙ-a.s.
		
  * For any measurable sequence ϵ_n :Ξ→ (0,+∞) with ϵ_n(ξ) → 0, ℙ-a.s. we have that 
		
    ∅≠lim sup_n→∞ϵ_n(ξ)-_ E_n(ξ) g_n ⊆_M_as g  , ℙ-a.s.

		
  * ⋂_ϵ >0 lim inf_n→∞ϵ-_E_n(ξ) g_n  = _M_as  g  = ⋂_ϵ >0 lim sup_n→∞ϵ-_E_n(ξ) g_n , ℙ-a.s.
	


	Consider the notation given  in (<ref>). Let us define α:=max{inf  f +1,1}, we have that α< +∞ due to the feasibility of    (<ref>).  Consider a set Ξ̂ of full measure such that  for all ξ∈Ξ̂
	
		
  * (f_n(ξ,·))_n∈ℕ  is eventually level compact,
		
  * ϵ_n(ξ) → 0,

		
  * lim sup_n→∞ϵ_n(ξ)- f_n(ξ, ·) ⊆ f.
	
	Fix  ξ∈Ξ̂ and a sequence x_k(ξ) ∈ϵ_n_k( ξ)- f_n_k(ξ, ·), so there exists some n_ξ∈ℕ such that for all n ≥ n_ξ
	
    ϵ_n(ξ) ≤ 1, and ⋃_n ≥ n_ξlev_≤α f_n  is relativelly compact.
 This implies that the sequence (x_k(ξ))_k≥ n_ξ^∞ belongs to a compact set, so it has an accumulation point.	Consequently, we have that   lim sup_n→∞ϵ_n- f_n(ξ, ·)≠∅, which proves  <ref>.
	
		Now, by  <cit.> we conclude that
	lim_n→∞v( f_n(ξ, ·))  =  v( f) for all ξ∈Ξ̂, which concludes the proof of <ref>. Finally, using <cit.> we get that  c) holds.
	





§ APPLICATIONS

    In this section, we present applications of the result found in Section <ref>. The first application, given in Subsection <ref>, corresponds to prove the consistency of the  nonconvex scenario approach  (see, e.g., <cit.>). The second application, given in Subsection  <ref>, shows that our ergodic approach can be used to solve infinite programming problems.




 §.§ Consistency of Nonconvex Scenario Approach


In this section we consider  (Ξ^∞, 𝒜^∞,ℙ^∞) as the  denumerable product of the probability  space (Ξ,𝒜,ℙ). 


As in the previous section, we consider a sequence of lsc functions g_n, which converge continuously to g, let us define the following family of optimization problems: For each ω=(ξ_k)_k=1^∞∈Ξ^∞ we set

    𝒮_n(ω)         min g_n(x)
    
    s.t.       x ∈ S_n(ω):=⋂_k=1^n  M(ξ_k),
 
Let us define
f_n : Ξ^∞× X → given by 

    f_n(ω, x)   := g_n(x) + 1/n∑_k=1^nδ_M(ξ_k)(x),
    
    f(x)   := g(x) + δ_M(x).

The following results corresponds to the scenario approach version of Theorem <ref>.

	Under the above setting we have that f_n(ω ,·)  f, ℙ^∞-a.s. Consequently for any measurable sequence ϵ_n :Ξ^∞→ (0,+∞) with ϵ(ω) :=lim supϵ_n(ω)<+∞,  ℙ^∞-a.s.  we have that:
	
		
  * lim sup_n→∞v_ϵ_n(ω)  (f_n(ω,·) ) ≤  v_ϵ(ω) (f), ℙ^∞-a.s.
		
  * lim sup_n→∞ϵ_n(ω)- f_n(ω,·) ⊆ϵ(ω)- f, ℙ^∞-a.s.
	
	


	Consider the shift on Ξ^∞, that is, T: Ξ^∞→Ξ^∞  given by
	
    T( (ξ_i)_i=1^∞) =(ξ_i+1)_i=1^∞,

	by <cit.> T is an  ergodic measure preserving  transformation (For more details we refer to <cit.>).
	Furthermore, we extend the measurable multifunction M to Ξ^∞ just by defining M̃ : Ξ^∞ X by  M̃(ω )=M(ξ_1), where ω =(ξ_i)_i=1^∞.  Using  notation  (<ref>) we get 
	
    f_n(ω, x)   := g_n(x) + 1/n∑_k=1^nδ_M̃(T^k(ω))(x)=g_n(x) + 1/n∑_k=1^nδ_M(ξ_k)(x),
    
    	f(x)   := g(x) + δ_M̃(x)=g(x) + δ_M(x)..

	Then, Theorem <ref> gives us that for almost all ω=(ξ_i) _i=1^∞∈Ξ^∞
	
		
  * f_n (ω, ·) → f,
		
  * lim sup_n→∞v_ϵ_n( ω )  (f_n( ω ,·) ) ≤  v_ϵ(ω)  (f), 
		
  * lim sup_n→∞ϵ_n(ω)- f_n( ω,·) ⊆ϵ( ω )- f
	


	It is worth mentioning that Theorem <ref> can be proved using the same proof given in Theorem <ref>,  copied step by step, but  using <cit.> instead of <cit.>. 


Similar to the previous section, we can get more precise estimations under some compactness assumptions. The proof of this result follows considering the  representation of (<ref>) given in (<ref>) using the shift transformation defined in (<ref>).  Also, it can follow mimicking the proof of the Corollary step by step, and using Theorem <ref> instead of Theorem <ref>.

	Let us assume that  (<ref>) is feasible, and the  sequence of functions g_n  is eventually level compact on S_n(ω)  ℙ^∞-a.s. ω∈Ξ^∞. Then,
	
		
  * 	lim_n→∞v ( g_n ,S_n(ω)) =  v(g,M_as), ℙ^∞-a.s. ω∈Ξ^∞.
		
  * For any measurable sequence ϵ_n :Ξ^∞→ (0,+∞) with ϵ_n → 0, ℙ^∞-a.s. we have that 
		
    ∅≠lim sup_n→∞ϵ_n(ω)-_ S_n(ω)  g_n  ⊆_M_as g , ℙ^∞-a.s. ω∈Ξ^∞.

		
  * ⋂_ϵ >0 lim inf_n→∞ϵ-_ S_n(ω)  g_n= _M_as g    = ⋂_ϵ >0 lim sup_n→∞ϵ-_ S_n(ω)  g_n, ℙ^∞-a.s. ω∈Ξ^∞.
	




	It has not escaped our notice that in <cit.> the authors did not show the consistency of the scenario approach with a perturbation over the objective function g as in (<ref>). Furthermore, only linear objective function and convex constraint sets were considered in <cit.>.  

 
 In the next result, we provide a concrete application of the above corollary using a  Moreau envelope of the objective function. Following <cit.>, we recall that  given a function g and λ>0, the Moreau envelope function gλ is defined by

    gλ(x):=inf{ 	f(u) + 1/2λ x -u^2	 : u ∈ℝ^d		}.

A function g is said to be prox-bounded if there exists λ >0 such that gλ(x)>-∞ for some x∈ℝ^n. In that case the supremum of all such λ is the threshold λ_g of prox-boundeness for g.


	Let g: ℝ^d → be a proper, lsc and prox-bounded function with threshold λ_g >0, let h :Ξ×ℝ^d → be a normal integrand function and C ⊆ℝ^d be a bounded closed set, and defined the optimization problem
	
    min g(x)
    
    s.t.      φ(ω,x)≤ 0,  a.s.
          x∈ C.

Consider  λ_n  ↘ 0 with λ_n   ∈ (0, λ_g). For each  ω=(ξ_k)_k=1^∞∈Ξ^∞ we defined the sequence of optimization problems 
	
    mingλ_n(x)
    
    s.t.      φ(ξ_i,x)≤ 0,  for i=1,…, n
          x∈ C.

 Let x_n(ω) be a (measurable) selection of the minimizers of Problem (<ref>). Then, if Problem (<ref>) is feasible, we have
 
 	
  * gλ_n(x_n(ω)) converges to the optimal value of Problem (<ref>),  ℙ^∞-a.s. ω∈Ξ^∞.
 	
  * Any cluster point of (x_n(ω))_n∈ℕ is a minimizer of Problem (<ref>), ℙ^∞-a.s. ω∈Ξ^∞.
   
	

Let us define the  multifunction M: Ξ C  given by M(ξ):={ x∈ C: φ(ξ,x) ≤0}, which is measurable due to  <cit.>. Moreover, 
by theorem <cit.>, gλ_n converges continuously g. Finally, since C ⊆ℝ^d is bounded and closed,   we have that the sequence of function  gλ_n  is eventually level compact on the sets ∩_k=1^n M(ξ_k). Therefore, applying Corollary <ref> we get the result.
	



 §.§ Application to Infinite Programming Problems

In this part of the work, we use the result of Section  <ref> to show that  a sequence of sub-problems can be used to give an approach for infinite programming problems.

Consider the following problem of infinite programming (semi-infinite programming, if X is  a finite dimensional vector space)

    ℐ       min g(x)
    
    s.t.      x ∈ M_a:=⋂_s ∈ S M(s),

where S is a topological space, and M:S  X is an  outer-semicontinuous set-valued map, that is to say, for every net s_ν→ s and every net x_ν∈ M(s_ν) with x_ν→ x we have x∈ M(s).  We denote by 𝒜  any σ-algebra, which contains all open subsets on S, and consider μ: 𝒜→ℝ a strictly positive finite measure, that is to say,   μ(S)<+∞ and 

    μ(U) >0,  for every open set  U ⊆ S,

let us consider an ergodic measure preserving transformation  T: S → S. With this framework, we define the sequence of optimization problems

    ℐ_n(s)          min g_n(x)
    
    s.t.       x ∈ I_n(s):=⋂_k=1^n M(T^k(s)),

where g_n converges continuously to g. As a simple application of  Theorem <ref> we get the following result, which give us a relation between Problems (<ref>) and   (<ref>).

	Let us assume that (S,𝒜,μ) is complete,   (<ref>) is feasible, and   the  sequence of functions g_n  is eventually level compact on I_n(s)  μ-a.e.	Then,
	
		
  * lim_n→∞v(g_n,I_n(s))  =  v(g,M_a), μ-a.e.
		
  * For any measurable sequence ϵ_n :S → (0,+∞) with ϵ_n(s) → 0, μ-a.e. we have that 
		
    ∅≠lim sup_n→∞ϵ_n(s)-_I_n(s) g_n  ⊆_M_a g , μ-a.e.

		
  * ⋂_ϵ >0 lim inf_n→∞ϵ-_I_n(s) g_n = _M_a g   = ⋂_ϵ >0 lim sup_n→∞ϵ-_I_n(s) g_n , μ-a.e.
	



	First, by  the outer-semicontinuous of M we have that the optimization problem (<ref>) is equivalent to 
	
    min g(x)
    
    	s.t.      x ∈ M(s),  μ-a.e.

	Indeed, let x ∈  M(s) for almost all s∈ S. Then, the set D_x :={ s∈ S: x∈ M(s)		} is dense due to the fact that μ is a strictly positive  measure. Consequently, for every s ∈ S\ D there exists s_ν→ s, so by the  outer-semicontinuous of M we get that x ∈ M(s), and consequently x∈ M(s) for all s∈ S.
	
	Next, consider the probability measure ℙ(·)= μ(S)^-1μ (·). Then, applying  Corollary <ref> to (<ref>) we get that a), b) and c) hold with  (<ref>), and by the equivalency with  (<ref>) we conclude the proof.


To end this section, we present a result that considers a sequence of functions mollified by convolution. Consider a  sequence mollifiers, that is, a sequence of  measurable functions e_n :  ℝ ^d → [0,+∞)  with ∫_ℝ^d e_n  (z) dz=1, such that the sets { z : e_n(z) >0} decrease to { 0}. Given a continuous function g:  ℝ ^n → R, we define its mollification, g_n :  ℝ ^d → ℝ, by

    g_n( x) = ∫_ ℝ ^d  e_n(x-z)g(z) dz,   for all x∈ ℝ ^d.


 Let g: ℝ^d →ℝ and  φ :S×ℝ^d → ℝ be continuous functions, and C ⊆ℝ^d be a bounded closed set. Consider the following semi-infinite programming problem
	
    min g(x)
    
    	s.t.      φ(S,x)≤ 0,  for all s∈ S,
          x∈ C.

Given  a measure preserving transformation T: S → S and    s ∈ S, we defined the sequence of optimization problems 
	
    min g_n(x)
    
    	s.t.      φ(T^i(s),x)≤ 0,  for i=1,…, n
          x∈ C,

	where   g_n are given by (<ref>). 
	Let x_n(s) be a (measurable) selection of the minimizers of Problem (<ref>). Then, if Problem (<ref>) is feasible, we have
	
		
  * g_n(x_n(z)) converges to the optimal value of Problem (<ref>),  μ-a.e. s∈ S.
		
  * Any cluster point of (x_n(z))_n∈ℕ is a minimizer of Problem (<ref>), μ-a.e. s ∈ S.
	  


Define the multifunction M : S ℝ ^d given by M(s):={ x∈ C : φ(s,x) ≤ 0}, which is measurable and outer-semicontinuous due to the continuity of φ. Now, by <cit.>, we have that g_n converges continuously to g. Finally, since C is bounded, we have that g_n is eventually level compact on ∩_i=1^n M(T^i(s)). Therefore, by Corollary <ref>, we get the result.
	



§ NUMERICAL EXAMPLES

Now, let us illustrate the above result with two different   examples.  The first one consider a best polynomial approximation, which in particular can be expressed as a convex optimization problem. The second one consider a non-convex optimization problem. 



 §.§ Best  Functional Approximation

In this subsection we focus on the following optimization problem. Consider a (measurable) absolutely bounded function f:[0,1] →ℝ and a (finite) family of linearly independent absolutely bounded  functions e_j : [0,1] →ℝ with j=0,…,q. We want to find the best approximation of  f in the linear space spanned by { e_j}_j=0 ^q. In order to solve this problems we follow   <cit.>. Let us consider the following optimization problem:


    min  β
     s.t.            f - ∑_ j=0 ^q x_i · e_j _∞ ≤β.

It can be equivalently expressed as


    ℬ          min   g(x) 
     s.t.             x ∈ M(t)  a.e.  t∈ [0,1].

where the (measurable) set-valued map M: [0,1] →ℝ^q+2 is given by
 
    M(t):={  (x,β) 	∈ℝ^q+1×ℝ : 
    -β≤  f(t) - ∑_ j=0^q x_i · e_j (t)   ≤β}
 and  g: ℝ^q+2→ℝ is given by g(x,β)=β.

To illustrate our results let us solve numerically (<ref>)  for the particular function    
    f(t)= 10^2 t(2t-1)(t -1)(4t -1)(4t -3)
 and e_j the canonical base of polynomials, that is, e_j(t):=t^i. We use an ergodic measure preserving transformation T(t)=t + α 1, with some α∉ℚ, and systematically, we solve the sequence of optimization problems for a fixed point t̅∈ [0,1]

    ℬ_n(t̅)          min   g(x) 
     s.t.             x ∈ M(T^k(t̅)),  k=1,...,n.

In Figure <ref> we show the results of the polynomial approximation found solving Problem (<ref>) for different values of n and for point t̅=0  and α=√(7).
	

	




 §.§ Rotation on the  2-dimensional Unit Sphere


Let us consider the following optimization problem

    min g(x,y)   
    s.t.    α x + β y  ≤ 6     for all  (α,β) ∈𝕊^1,

where g is a non-convex polynomial function with several local-minima  (see Figure <ref>), more precisely  we choose

    g(x,y)= (x+5)(x+2)  (x-1) (x-9) +y(y+11)( y-4) ( y-5)  + xy.
 and 𝕊^1 is the 2-dimensional unit sphere, that is to say, 𝕊^1:={ (α,β) ∈ℝ^2	: α^2 + β^2=1	}.
It is not difficult to see that the above problem is noting more than

    min g(x,y)
    s.t.    x^2 +  y^2  ≤ 36.

To solve this problem, we use an irrational rotation  T: 𝕊^1 →𝕊^1, that is, T(ξ)=ξ· e^2πθ i with θ∈ [0,1] \ℚ. Here the multiplication is in the sense of complex numbers. Therefore, we have to numerically solve  the following optimization problems


    𝒰_n(ξ)   min g(x,y)   
    s.t.    x ∈ U_n(ξ)

where U_n(ξ): ={  (x,y) ∈ℝ^
	2 :  ⟨  T^k(ξ)  , (x,y)⟩≤ 6,  ∀ k=1,…,n }.


First, we have that the global minimum of g is attained at (x_u,y_u)=(6.3442 ,  -7.6398) and the minimum is g(x_u,y_u)=-5490.9.  On the other hand the optimal value  of  (<ref>)  is attained at (x_c,y_c)=( 3.2004 ,  -5.0752) with value g(x_c,y_c)=-3519.1. In Table <ref> we can compare different numerical solutions to Problem (<ref>).





	

	








§ CONCLUSION AND PERSPECTIVES

In this paper, we have studied the consistency of a new method for solving robust optimization problems. In counterpart to classical methods in stochastic programming, it is based on ergodic measure preserving transformation instead of sample approximation.

In particular, our approach is more general, because we can recover the results based on samples using the  shift on the denumerable product of the probability space.  Moreover, our results allow us to apply the technique to infinite programming problems under reasonable assumptions, and without any compactness assumption on the index set, as classical results in this field.


We believe that our analysis represents a first step in the understanding of a new approach based on ergodicity instead of a sequence of samples. A natural question relies on to understand the relation between the choice of the measure preserving transformation and the rate of convergence of the approximate sequence of minimizers.
 

It is important to mention that in our result a regularization of the objective function is considered in each step, that is the role of the sequence g_n in Theorem <ref> and its corollaries.  In most important applications, constraints are given by systems of possible nonsmooth inequalities. Commonly, this nonsmoothness is handled by using smooth regularizations, for instance, Moreau envelopes and regularization via mollifiers (see, e.g., <cit.>). Therefore, it will be necessary the study of the consistency of a method which in each step use both a regularization of the constraints and our ergodic approach.


Therefore, we plan to investigate these possible  extensions of our presented method in a future paper.

Acknowledgements First, the author would like to acknowledge the helpful discussions and great comments about this work given by  Professor  Marco A. López Cérda, which improved notably the quality of the presented manuscript. Second, the author is grateful to the anonymous reviewers for their valuable suggestions and comments about the work, which increases the presentation of the current version of the manuscript.


plain

