# Proximal Point Algorithms for Vector DC Programming with Applications to Probabilistic Lot Sizing with Service Levels

Authors: Ying Ji; Shaojian Qu
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

We present a new algorithm for solving vector DC programming, where the vector function is a function of the difference ofC-convex functions. Because of the nonconvexity of the objective function, it is difficult to solve this class of problems. We propose several proximal point algorithms to address this class of problems, which make use of the special structure of the problems (i.e., the DC structure). The well-posedness and the global convergence of the proposed algorithms are developed. The efficiency of the proposed algorithm is shown by an application to a multicriteria model stemming from lot sizing problems.


---

## Body

## 1. Introduction

Vector-valued optimization arises from multiobjective programming, multicriteria decision-making, statistics, and cooperative game theory [1]. This class of problems has been widely applied and studied in various decision-making contexts and many methods have been developed to address such problems [2–4]. Denote C as a convex, closed, and pointed cone with int(C)≠∅. The partial order ⪯ can be defined as follows: for any u,v∈Rm,u⪯v⇔v-u∈C. The relation ≺ is defined as u≺v⇔v-u∈int(C). This paper studies the following vector DC optimization problems with linear constraints:(1)minC⁡fx≔ψx-φx:s.t.x∈S,where functions φ and ψ: Rn→Rm are C-convex (see the definition in Section 2); S⊂Rn is a closed and convex set. Note that “minC” implies the multiobjective minimization over the cone C, that is, the weak Pareto efficiency or Pareto efficiency with respect to the cone C. When C≔R+m, the objective function f reduces to the multiobjective DC function and problem (1) is the multiobjective DC program which is studied by Qu et al. [5]. Similar to the adoption in [5], we utilize the following convention: ∞-∞=∞.Though many researchers have widely studied vector DC program, they analyze mainly the theoretical aspects. For example, the duality theories and optimal conditions for multiobjective optimization were presented by Qu et al. [5]; the optimal conditions for DC vector optimization were also studied by Gadhi et al. [6]. However, to the best of our knowledge, there are few studies on how to efficiently solve this class of problems. This paper presents several proximal point algorithms for solving this class of problems.Proximal point algorithms have an extensive application in solving scalar optimization problems [7], which originates from the work of [8]. It has been shown that proximal point algorithms can efficiently solve scalar optimization problems [9, 10]. As an extension, recently, the proximal point algorithm has been utilized to solve multicriteria convex optimization problems [11, 12]. However, to the best of our knowledge, few studies have been paid on extending proximal point algorithms to multicriteria optimization problems with DC objective functions. This paper proposes the exact and inexact proximal point algorithms to solve vector DC optimization, where the special structure, the DC structure of this class of problems, has been considered.Our contributions can be concluded as follows. The proximal point methods in both exact and inexact forms are extended to address the vector DC optimization. The well-definedness of the proposed methods is presented. The global convergence of the proposed algorithms is proved. An application in lot sizing problems is presented to show the efficiency of the proposed algorithms.We organize the rest of this paper as follows. Preliminaries are presented in Section2. The algorithms are proposed in Section 3. The theoretical analysis of the well-definedness and global convergence are also discussed in Section 3. An application of the algorithms to probabilistic lot sizing with service levels is presented in Section 4. The conclusion is given in Section 5.


## 2. Preliminaries

Functionϕ:Rn→Rm is denoted as C-convex iff, for any x,y∈Rn and any λ∈[0,1], (2)ϕλx+1-λy⪯λϕx+1-λϕy.Function ϕ is denoted as strictly C-convex iff, for any x,y∈Rn and any λ∈(0,1), (3)ϕλx+1-λy≺λϕx+1-λϕy.Given ϵ≥0, the ϵ-subdifferential ∂ϵϕ(x¯) of ϕ at x¯∈domϕ is a possibly empty, closed, and convex set and can be defined as (4)∂ϵϕx≔V∈Rm×n:ϕx+Vy-x⪯ϕy+ϵe,∀y∈Rn,ϵ≥0,where e≔(1,…,1)T∈Rm. We denote ∂ϵϕ(x¯)≔∅ for x¯∉dom⁡ϕ and ∂ϕϵ(x¯) is nonempty convex and compact (see Theorem 4.12 of [13]) if x∈dom⁡ϕ. When m=1, ϵ=0, and C=R+, ∂ϕ0(x¯) reduces to the usual classical subdifferential [14]. The indicator function of a set S⊂Rn can be named as δ(x;S)≔0 if x∈S and δ(x;S)≔+∞, if x∉S. We denote x¯∈S as the normal cone to the set S which can be described as (5)Nx¯;S≔∂δx¯;S=x∗∈Rn∣x-x¯Tx∗≤0,∀x∈S.To facilitate the discussion in this paper, we need the following information about refined epigraphical and subdifferential rules in convex analysis presented in [15].Lemma 1.
Assume thatϕi:Ω→R¯,i=1,2, are l.s.c. and proper. If dom⁡ϕ1∩dom⁡ϕ2≠∅, then the following conclusions are equivalent:(i)
The setepiϕ1∗+epiϕ2∗ is weak∗ closed in Ω∗×R.(ii)
The refined conjugate epigraphical rule holds:epi(ϕ1+ϕ2)∗=epiϕ1∗+epiϕ2∗.Throughout of this paper, the equivalent conditions in Lemma1 are supposed to hold which means that the following subdifferential sum rule holds, ∂(ϕ1+ϕ2)(x¯)=∂ϕ1(x¯)+∂ϕ2(x¯),∀x∈dom⁡ϕ1∩dom⁡ϕ2 [15].In multiobjective problem, no unique solution can minimize all of objective functions simultaneously; therefore, the decision-maker has to trade-off solutions. That is, if he wants to improve some objectives, he has to give up other objectives. So the optimal concept has to be replaced by the Pareto optimal concept, which can be defined as follows:x∗∈S is called a Pareto optimum (PO) or a weak Pareto optimum (WPO) of (1) if there is no strategy x∈S such that (6)fx⪯fx∗,fx≠fx∗orfx≺fx∗.x∗ is named as a local PO or a local WPO of (1) if and only if ∃N(x∗) as a neighborhood of x∗ such that x∗ is a PO or a WPO in N(x∗)∩S.To analyze the optimization conditions of (1), we put forward the following assumption.(A1) Assume that functionsφ and ψ: Rn→Rm are C-convex. Assume that x¯ is a locally Pareto efficient solution of (1) and is limited to S∩dom⁡ψ≠∅.Under the assumption thatS∩dom⁡ψ≠∅, it is guaranteed that ∂ψ(x¯)≠∅. Assumption (A1) will be used to prove Theorem 2.Theorem 2 (necessary optimality conditions for (1)).
Suppose that the assumption (A1) holds andx¯ is a locally WPO to (1), then ∃u∈C∗, such that(7)∂φx¯Tu⊂∂ψx¯Tu+Nx¯;S,u=1.Proof.
This theorem can be proved by considering the two cases aboutx¯∈S∩dom⁡ψ: either x¯∉dom⁡φ or x¯∈dom⁡φ. The first one means that ∂φ(x¯)=∅, which leads to (7). For the other, define Fu(x)≔uTf(x), ∀u∈C∗ with u=1 and ∀x∈S. Given u¯∈C∗ with u¯=1, then we can prove that x¯ is a local optimal solution to the following scalar optimization problem:(8)minx∈SFu¯x.We prove it by contradiction; that is, the conclusion does not hold. Then Fu(x¯)>Fu(x~) holds for at least one x~∈S∩Bε(x¯) with any given neighborhood Bε(x¯)⊂S of x¯, ε>0, and any u∈C∗ with u=1. It is easy to show that f(x~)≺f(x¯) for the choice of u, which contradicts the assumption about x¯ and this implies that x¯ is also a local optimum to (8). To show that (7) is true, we only need to prove that VTu¯∈∂ψ(x¯)Tu¯+N(x¯;S) holds ∀V∈∂φ(x¯)⊆Rm×n. According to the definition of subdifferential in x¯, it is easy to learn that x¯ is also globally solving the following convex optimization problem:(9)min⁡F¯x≔u¯Tψx-φx¯-u¯TVx-x¯:x∈S.Then, from the necessary optimal conditions of (9), the assertion of this theorem can be followed directly.Usually, it is difficult to utilize the necessary condition in the above theorem to design the solution algorithms for (1). Hence, the other optimal condition should be presented and this paper looks for finding a critical point of (1), that is, finding a point x¯, such that (10)x¯∈X≔x∈Rn:∃u∈C∗,s.t.,0∈∂ψxTu-∂φxTu,u=1.Define U≔{u∈C∗:u=1}. Then, an alternative characterization of criticality is given in the following results which is useful in the following discussions.Theorem 3.
x
¯ is a critical point to (1) if and only if there is V¯∈∂φ(x¯) such that x¯ globally solves the following problem:(11)minx∈Smaxu∈UuTψx-uTV¯x-x¯.Proof.
It is obvious that problem (11) is convex. Hence, the proof can be reduced to prove that x¯ is a critical point if and only if x¯ is an optimum of (11). We first prove that x¯∈X iff ∃V¯∈∂φ(x¯) such that x¯ is a (globally) WPO to the following convex vector optimization problem:(12)minx∈Sψx-V¯x-x¯.According to the necessary optimal conditions that if x¯∈S is a WPO of (12), there exists some u∈C∗ with u=1, such that 0∈∂ψ(x¯)Tu-V¯Tu. This implies that the above conclusion is true. Moreover, it follows from the definition of U that the cone generated by its convex hull is C∗, which means that there are a integer q>0, ui∈U, and λi>0 with i=1,…,q such that u=∑i=1qλiui and ∑i=1qλi=1. Hence, a WPO x¯∈S satisfies(13)0∈∑i=1qλi∂ψx¯Tui-V¯Tui,∑i=1qλi=1,ui∈U,λi>0,i=1,…,q.Now the necessary optimality of (11) is analyzed. According to the formula about the subdifferential of a maximum of convex functions and the assumption about U that if x¯ is an optimal solution to (11), there are a positive integer q¯ and u¯k∈U and λ¯k>0 with 1≤k≤q¯ such that(14)u¯kTψx-u¯kTV¯x-x¯=maxu∈U⁡uTψx-uTV¯x-x¯,k=1,…,q¯,0∈∑k=1q¯λ¯k∂ψx¯Tu¯k-V¯Tu¯k,∑k=1q¯λ¯k=1.The above result together with (13) leads to the assertion of this theorem.According to the results of Theorem3, the solution of a critical point to (1) can be equivalently transformed into solving a min–max problem. Therefore from this point, proximal point algorithms are presented for solving (1) in the following section.


## 3. Main Results

### 3.1. Algorithm4

First, the algorithm for solving (1) is proposed which is globally convergent and well-defined.Algorithm 4.
Step 0. A small enough constant ε>0 and an initial point x0∈S are chosen, respectively. Select a positive constant θ0>0. Let k≔0.
Step 1. At the kth iteration, calculate Vk∈∂φ(xk). Solve the following problem and let xk+1 be an optimum:(15)minx∈Smaxu∈UuTψx-uTVkx-xk+θk2x-xk2.Step 2. If xk+1-xk≤ε, then stop; else, update θk as θk+1, set k≔k+1, and go to Step 1.
In Step1, the subproblem is convex and is solved at every iteration. We present the optimality conditions of this subproblem as follows: (16)xk+1=PkVkTuk+θkxk,xk+1∈S,where uk∈U and Pk≔(∂ψTuk+θkI)-1. We note that the algorithm does not rely on scalarization approaches which are usually used in solving vector optimization; that is, the algorithm does not use a priori chosen weighting parameters for the vector in different objective function.We note that Algorithm4 aims at obtaining one Pareto optimal solution. In recent years, the classical iteration methods (e.g., decent-direction-type and proximal point-type methods) for scalar optimization have been extended to address the vector problems to obtain one solution [16–18]. In this respect, the method proposed in this paper is similar to these ideas. However, when a need to obtain the Pareto surface (the Pareto optimal solution set) is necessary, this method may fail. It can be proved by the following example given in Antoni and Giannessi [19].Example 5.
Consider the following bilevel optimization problem (upper level):(17)minxx1-22+x2-562,s.t.x∈K0,where K0 is the Pareto optimal solution set of the following vector optimization problem:(18)minR+2fx,s.t.x∈K≔x∈R2:gx≥0,with(19)fx≔f1x≔2x1-x2f2x≔-x1+2x2,gx≔g1x≔2x1+x2-1g2x≔x1+2x2-1.“minR+2” marks the Pareto optimum with respect to R+2. By Theorem 2.1 of [12] and Proposition 13 of [20], the Pareto optimum x∗ of the lower level problem satisfies x∗=(1/3,1/3), or x1∗=1-2x2∗, 0≤x2∗<1/3, or x2∗=1-2x1∗, 0≤x1∗<1/3. Then, the optimal solution to the corresponding bilevel problem (17) is x∗=(1,0) and the optimal value is 61/36. When we use Algorithm 4 to obtain K0, it can be found that K0={(0.3333,0.3333)}. Therefore, the optimal solution to the corresponding bilevel problem (17) is x∗=(0.3333,0.3333) and the corresponding optimal value is 3.0279, which is larger than 61/36. Since Algorithm 4 can not obtain the entire solution set K0, the method fails to get the optimum of the bilevel problem.For Algorithm4, we have the following conclusion.Theorem 6.
Assume that{xk} is generated by Algorithm 4. If one sets ε=0, then the following conclusions about {xk} hold:(i)
either Algorithm4 stops at a critical point of problem (1)(ii)
or there isuk∈U such that ukT(f(xk+1)-f(xk))<0.Proof.
Ifxk+1=xk, then it follows that xk is a critical point of (1) from the definition for criticality. According to the generation of xk+1, the following inequality holds:(20)maxu∈UuTψxk+1-uTVkxk+1-xk+θk2xk+1-xk2≤maxu∈U⁡uTψxkwhich together with the assumption about U implies that ∃uk∈U such that(21)ukTψxk+1-ukTVkxk+1-xk+θk2xk+1-xk2≤ukTψxk.The subgradient that, for any Vk∈∂φ(xk),(22)φxk+Vkxk+1-xk⪯φxk+1.Summing (21) and ukT (22) leads to(23)ukTfxk+1-fxk≤-θk2xk+1-xk2.The above result together with xk+1≠xk and the positivity of θk implies that the assertion is true.Theorem6 means that Algorithm 4 either generates a descent sequence satisfying the second conclusion or stops at a critical point. For proving the global convergence, the following assumptions are proposed:(A2) The setS⊂Rn is bounded and the iterations do not stop finitely.(A3) For a large enoughk, ∃u∈U such that (24)xk+1=P^kVkTu+θkxk,xk+1∈S,where P^k≔(∂ψTu+θkI)-1.Actually, under assumption (A2), the setS is compact and convex. ϕ and ψ being C-convex imply that (25)∀u∈C∗:∅≠argmin⁡uTfx:x∈S⊆argminw⁡fx:x∈S,where argminw denotes WPO set. So, to find a WPO for this problem at this case, it is sufficient to resolve min⁡{uTf(x):x∈S}, for any u∈C∗. Therefore, at each iteration of Algorithm 4, we can replace subproblem (15) with the following problem with fixed u∈C∗: (26)minx∈S⁡uTψx-uTVkx-xk+θk2x-xk2,which means that assumption (A3) holds at this case.Assumption (A3) means that a descent sequence for functionuTf(x) on S is generated by Algorithm 4 after finite iterations. Hence, the proof of global convergence of Algorithm 4 is equivalent to showing that the sequence generated by Algorithm 4 is global convergence to a critical point of function uTf(x). For this purpose, from the conclusion of [20], it is sufficient to show that the sequence generated by Algorithm 4 satisfies three properties: descent, closedness, and boundedness. First, assumption (A3) implies that the sequence generated by Algorithm 4 is the descent directions for function uTf(x). Second, the compactness of S means the boundedness of {xk}. Finally, we prove that the map (∂φTu+θkI)-1∘(∑i∈Iuj∂ψi+θkI) of the algorithm is closed. The conclusion can be derived by the theorem on the composition of closed point-to-set maps proposed by Zangwill [21] and the assumption on functions φ and ψ. Then this implies that the following theorem is true.Theorem 7.
Assume that{xk} is generated by Algorithm 4. If assumptions (A2) and (A3) are true, then any accumulation point of {xk} is a critical point of problem (1).


### 3.2. Algorithm8

We now present another algorithm for solving (1). Both the well-definedness and global convergence of Algorithm 8 are also established.Algorithm 8.
Step 0. A sufficiently small constant ε>0 and an initial point x0∈S are presented, respectively. Choose a constant r0∈C∖{0}. Let k≔0.
Step 1. At kth iteration, calculate Vk∈∂φ(xk). Solve the following problem and let xk+1 be an optimum:(27)minx∈Smaxu∈UuTψx-uTVkx-xk+rkTu2x-xk2.Step 2. If xk+1-xk≤ε, then stop; else, update rk, set k≔k+1, and go to Step 1.
At every iteration of Algorithm8, similar to Algorithm 4, a convex subproblem is presented and the enclosed form expression for the optimum can be computed as (28)xk+1=PkVkTuk+rkTukxk,xk+1∈S,where uk∈U and Pk≔(∂φTuk+(rkTuk)I)-1. The following two conclusions hold for Algorithm 8.Theorem 9.
If one setsε=0 and choose rk with rkTu>0, ∀u∈U, then the sequence {xk} generated by Algorithm 8 satisfies(i)
either the algorithm stops at a critical point of problem (1)(ii)
or there isuk∈U such that ukT(f(xk+1)-f(xk))<0.Proof.
Ifxk+1=xk, from Theorem 2, it follows that xk is a critical point of (1). According to the generation of xk+1, the following inequality holds:(29)maxu∈UuTψxk+1-uTVkxk+1-xk+rkTu2xk+1-xk2≤maxu∈U⁡uTψxk.The above inequality means that ∃uk∈U such that(30)ukTψxk+1-ukTVkxk+1-xk+rkTu2xk+1-xk2≤ukTψxk.The subgradient definition leads to that, for any Vk∈∂φ(xk),(31)φxk+xk+1-xkTVk⪯φxk+1.The following inequality comes from summing (30) and uT (31):(32)ukTfxk+1-fxk≤-rkTu2xk+1-xk2.This together with rkTuk>0 and xk+1≠xk implies that the assertion is true.Theorem9 implies that the sequence generated by Algorithm 8 either satisfies the second conclusion or stops at a critical point. The following assumption is proposed for proving the global convergence:(A4) For large enoughk, ∃u∈U such that (33)xk+1=P~kVkTu+rkTuxk,xk+1∈S,where P~k≔((∂φTu+rkTuI))-1.Similar to the proof of the globally convergence analysis for Algorithm4, Algorithm 8 is also globally convergent.Theorem 10.
Assume that{xk} is generated by Algorithm 8. If one supposes that assumptions (A2) and (A4) hold, then any accumulation point of {xk} is a critical point of problem (1).


### 3.3.ϵ-Proximal Algorithm

We propose an inexact version for the above algorithms, that is, anϵ-proximal algorithm for obtaining an ϵ-critical point of problem (1) by utilizing the ϵ-subdifferential. For this purpose we define the ϵ-critical point of (1) as follows: find a point x¯ such that (34)x¯∈Xϵ≔x∈Rn:∃u∈U,s.t.,0∈∂ϵψxTu-∂ϵφxTu,where ∂ϵ is the ϵ-subdifferential defined above. This algorithm is in connection with inexact proximal point algorithms proposed in [22].ϵ
-Proximal AlgorithmStep 0. A small enough constant ε>0 and an initial point x0∈S are chosen, respectively. Let ϵ0,θ0>0 be constants. Set k≔0.Step 1. At the kth iteration, calculate Vϵkk∈∂ϵkφ(xk). xk+1∈S satisfies the following equation:(35)xk+1=PϵkkVϵkkTuk+θkxk,where uk∈U and Pϵkk≔(∂ϵkψTuk+θkI)-1.Step 2. Stop if xk+1-xk≤ε; else, update θk, set k≔k+1, and go to Step 1.This is an approximate algorithm to Algorithm4 by using the ϵ-subdifferential instead of the subdifferential. We can similarly propose an approximate algorithm for Algorithm 8 by replacing the subdifferential with the ϵ-subdifferential and the corresponding properties can also be found. The next two theorems present the descent and globally convergent properties of the approximate algorithm, respectively.Theorem 11.
Assume that{xk} is generated by ϵ-proximal algorithm, ε=0 and ϵk≤ϵ, ∀k. If the algorithm do not stop finitely, then {f(xk)} is a 2ϵ-descent sequnece, which implies that ∃uk∈U such that (36)fxk+1-fxkTuk<2ϵ,∀k.Proof.
The conclusion comes from Theorem5.4 in [23] and Theorem 6.To show the global convergent, the following assumptions are presented:(A5) For large enoughk, ∃u∈U such that (37)xk+1=P^ϵkkVϵkkTu+θkxk,xk+1∈S,where P^ϵkk≔(∂ϵkφTu+θkI)-1;(A6) For anyu∈U, uTf(x) is bounded below for any x∈S; there is 0<θ_≤θ¯<+∞ such that θk∈[θ_,θ¯],∀k; the parameters ϵk,∀k, satisfy ∑k=0+∞ϵk<+∞.Hence, similar to Theorem2.1 in [24], we can prove the approximate algorithm has the following convergent results.Theorem 12.
Suppose that{xk} is generated by the ϵk-proximal algorithm. If assumptions (A2), (A5), and (A6) hold, then any accumulation point of {xk} is a critical point of problem (1) and {xk} is asymptotically regular in the following sense: limk→+∞θkxk-xk+1=0.


## 3.1. Algorithm4

First, the algorithm for solving (1) is proposed which is globally convergent and well-defined.Algorithm 4.
Step 0. A small enough constant ε>0 and an initial point x0∈S are chosen, respectively. Select a positive constant θ0>0. Let k≔0.
Step 1. At the kth iteration, calculate Vk∈∂φ(xk). Solve the following problem and let xk+1 be an optimum:(15)minx∈Smaxu∈UuTψx-uTVkx-xk+θk2x-xk2.Step 2. If xk+1-xk≤ε, then stop; else, update θk as θk+1, set k≔k+1, and go to Step 1.
In Step1, the subproblem is convex and is solved at every iteration. We present the optimality conditions of this subproblem as follows: (16)xk+1=PkVkTuk+θkxk,xk+1∈S,where uk∈U and Pk≔(∂ψTuk+θkI)-1. We note that the algorithm does not rely on scalarization approaches which are usually used in solving vector optimization; that is, the algorithm does not use a priori chosen weighting parameters for the vector in different objective function.We note that Algorithm4 aims at obtaining one Pareto optimal solution. In recent years, the classical iteration methods (e.g., decent-direction-type and proximal point-type methods) for scalar optimization have been extended to address the vector problems to obtain one solution [16–18]. In this respect, the method proposed in this paper is similar to these ideas. However, when a need to obtain the Pareto surface (the Pareto optimal solution set) is necessary, this method may fail. It can be proved by the following example given in Antoni and Giannessi [19].Example 5.
Consider the following bilevel optimization problem (upper level):(17)minxx1-22+x2-562,s.t.x∈K0,where K0 is the Pareto optimal solution set of the following vector optimization problem:(18)minR+2fx,s.t.x∈K≔x∈R2:gx≥0,with(19)fx≔f1x≔2x1-x2f2x≔-x1+2x2,gx≔g1x≔2x1+x2-1g2x≔x1+2x2-1.“minR+2” marks the Pareto optimum with respect to R+2. By Theorem 2.1 of [12] and Proposition 13 of [20], the Pareto optimum x∗ of the lower level problem satisfies x∗=(1/3,1/3), or x1∗=1-2x2∗, 0≤x2∗<1/3, or x2∗=1-2x1∗, 0≤x1∗<1/3. Then, the optimal solution to the corresponding bilevel problem (17) is x∗=(1,0) and the optimal value is 61/36. When we use Algorithm 4 to obtain K0, it can be found that K0={(0.3333,0.3333)}. Therefore, the optimal solution to the corresponding bilevel problem (17) is x∗=(0.3333,0.3333) and the corresponding optimal value is 3.0279, which is larger than 61/36. Since Algorithm 4 can not obtain the entire solution set K0, the method fails to get the optimum of the bilevel problem.For Algorithm4, we have the following conclusion.Theorem 6.
Assume that{xk} is generated by Algorithm 4. If one sets ε=0, then the following conclusions about {xk} hold:(i)
either Algorithm4 stops at a critical point of problem (1)(ii)
or there isuk∈U such that ukT(f(xk+1)-f(xk))<0.Proof.
Ifxk+1=xk, then it follows that xk is a critical point of (1) from the definition for criticality. According to the generation of xk+1, the following inequality holds:(20)maxu∈UuTψxk+1-uTVkxk+1-xk+θk2xk+1-xk2≤maxu∈U⁡uTψxkwhich together with the assumption about U implies that ∃uk∈U such that(21)ukTψxk+1-ukTVkxk+1-xk+θk2xk+1-xk2≤ukTψxk.The subgradient that, for any Vk∈∂φ(xk),(22)φxk+Vkxk+1-xk⪯φxk+1.Summing (21) and ukT (22) leads to(23)ukTfxk+1-fxk≤-θk2xk+1-xk2.The above result together with xk+1≠xk and the positivity of θk implies that the assertion is true.Theorem6 means that Algorithm 4 either generates a descent sequence satisfying the second conclusion or stops at a critical point. For proving the global convergence, the following assumptions are proposed:(A2) The setS⊂Rn is bounded and the iterations do not stop finitely.(A3) For a large enoughk, ∃u∈U such that (24)xk+1=P^kVkTu+θkxk,xk+1∈S,where P^k≔(∂ψTu+θkI)-1.Actually, under assumption (A2), the setS is compact and convex. ϕ and ψ being C-convex imply that (25)∀u∈C∗:∅≠argmin⁡uTfx:x∈S⊆argminw⁡fx:x∈S,where argminw denotes WPO set. So, to find a WPO for this problem at this case, it is sufficient to resolve min⁡{uTf(x):x∈S}, for any u∈C∗. Therefore, at each iteration of Algorithm 4, we can replace subproblem (15) with the following problem with fixed u∈C∗: (26)minx∈S⁡uTψx-uTVkx-xk+θk2x-xk2,which means that assumption (A3) holds at this case.Assumption (A3) means that a descent sequence for functionuTf(x) on S is generated by Algorithm 4 after finite iterations. Hence, the proof of global convergence of Algorithm 4 is equivalent to showing that the sequence generated by Algorithm 4 is global convergence to a critical point of function uTf(x). For this purpose, from the conclusion of [20], it is sufficient to show that the sequence generated by Algorithm 4 satisfies three properties: descent, closedness, and boundedness. First, assumption (A3) implies that the sequence generated by Algorithm 4 is the descent directions for function uTf(x). Second, the compactness of S means the boundedness of {xk}. Finally, we prove that the map (∂φTu+θkI)-1∘(∑i∈Iuj∂ψi+θkI) of the algorithm is closed. The conclusion can be derived by the theorem on the composition of closed point-to-set maps proposed by Zangwill [21] and the assumption on functions φ and ψ. Then this implies that the following theorem is true.Theorem 7.
Assume that{xk} is generated by Algorithm 4. If assumptions (A2) and (A3) are true, then any accumulation point of {xk} is a critical point of problem (1).


## 3.2. Algorithm8

We now present another algorithm for solving (1). Both the well-definedness and global convergence of Algorithm 8 are also established.Algorithm 8.
Step 0. A sufficiently small constant ε>0 and an initial point x0∈S are presented, respectively. Choose a constant r0∈C∖{0}. Let k≔0.
Step 1. At kth iteration, calculate Vk∈∂φ(xk). Solve the following problem and let xk+1 be an optimum:(27)minx∈Smaxu∈UuTψx-uTVkx-xk+rkTu2x-xk2.Step 2. If xk+1-xk≤ε, then stop; else, update rk, set k≔k+1, and go to Step 1.
At every iteration of Algorithm8, similar to Algorithm 4, a convex subproblem is presented and the enclosed form expression for the optimum can be computed as (28)xk+1=PkVkTuk+rkTukxk,xk+1∈S,where uk∈U and Pk≔(∂φTuk+(rkTuk)I)-1. The following two conclusions hold for Algorithm 8.Theorem 9.
If one setsε=0 and choose rk with rkTu>0, ∀u∈U, then the sequence {xk} generated by Algorithm 8 satisfies(i)
either the algorithm stops at a critical point of problem (1)(ii)
or there isuk∈U such that ukT(f(xk+1)-f(xk))<0.Proof.
Ifxk+1=xk, from Theorem 2, it follows that xk is a critical point of (1). According to the generation of xk+1, the following inequality holds:(29)maxu∈UuTψxk+1-uTVkxk+1-xk+rkTu2xk+1-xk2≤maxu∈U⁡uTψxk.The above inequality means that ∃uk∈U such that(30)ukTψxk+1-ukTVkxk+1-xk+rkTu2xk+1-xk2≤ukTψxk.The subgradient definition leads to that, for any Vk∈∂φ(xk),(31)φxk+xk+1-xkTVk⪯φxk+1.The following inequality comes from summing (30) and uT (31):(32)ukTfxk+1-fxk≤-rkTu2xk+1-xk2.This together with rkTuk>0 and xk+1≠xk implies that the assertion is true.Theorem9 implies that the sequence generated by Algorithm 8 either satisfies the second conclusion or stops at a critical point. The following assumption is proposed for proving the global convergence:(A4) For large enoughk, ∃u∈U such that (33)xk+1=P~kVkTu+rkTuxk,xk+1∈S,where P~k≔((∂φTu+rkTuI))-1.Similar to the proof of the globally convergence analysis for Algorithm4, Algorithm 8 is also globally convergent.Theorem 10.
Assume that{xk} is generated by Algorithm 8. If one supposes that assumptions (A2) and (A4) hold, then any accumulation point of {xk} is a critical point of problem (1).


## 3.3.ϵ-Proximal Algorithm

We propose an inexact version for the above algorithms, that is, anϵ-proximal algorithm for obtaining an ϵ-critical point of problem (1) by utilizing the ϵ-subdifferential. For this purpose we define the ϵ-critical point of (1) as follows: find a point x¯ such that (34)x¯∈Xϵ≔x∈Rn:∃u∈U,s.t.,0∈∂ϵψxTu-∂ϵφxTu,where ∂ϵ is the ϵ-subdifferential defined above. This algorithm is in connection with inexact proximal point algorithms proposed in [22].ϵ
-Proximal AlgorithmStep 0. A small enough constant ε>0 and an initial point x0∈S are chosen, respectively. Let ϵ0,θ0>0 be constants. Set k≔0.Step 1. At the kth iteration, calculate Vϵkk∈∂ϵkφ(xk). xk+1∈S satisfies the following equation:(35)xk+1=PϵkkVϵkkTuk+θkxk,where uk∈U and Pϵkk≔(∂ϵkψTuk+θkI)-1.Step 2. Stop if xk+1-xk≤ε; else, update θk, set k≔k+1, and go to Step 1.This is an approximate algorithm to Algorithm4 by using the ϵ-subdifferential instead of the subdifferential. We can similarly propose an approximate algorithm for Algorithm 8 by replacing the subdifferential with the ϵ-subdifferential and the corresponding properties can also be found. The next two theorems present the descent and globally convergent properties of the approximate algorithm, respectively.Theorem 11.
Assume that{xk} is generated by ϵ-proximal algorithm, ε=0 and ϵk≤ϵ, ∀k. If the algorithm do not stop finitely, then {f(xk)} is a 2ϵ-descent sequnece, which implies that ∃uk∈U such that (36)fxk+1-fxkTuk<2ϵ,∀k.Proof.
The conclusion comes from Theorem5.4 in [23] and Theorem 6.To show the global convergent, the following assumptions are presented:(A5) For large enoughk, ∃u∈U such that (37)xk+1=P^ϵkkVϵkkTu+θkxk,xk+1∈S,where P^ϵkk≔(∂ϵkφTu+θkI)-1;(A6) For anyu∈U, uTf(x) is bounded below for any x∈S; there is 0<θ_≤θ¯<+∞ such that θk∈[θ_,θ¯],∀k; the parameters ϵk,∀k, satisfy ∑k=0+∞ϵk<+∞.Hence, similar to Theorem2.1 in [24], we can prove the approximate algorithm has the following convergent results.Theorem 12.
Suppose that{xk} is generated by the ϵk-proximal algorithm. If assumptions (A2), (A5), and (A6) hold, then any accumulation point of {xk} is a critical point of problem (1) and {xk} is asymptotically regular in the following sense: limk→+∞θkxk-xk+1=0.


## 4. Numerical Tests

### 4.1. Probabilistic Lot Sizing with Service Levels

In probabilistic lot sizing with service levels, the order quantities,xt,t=1,…,n, are determined at the beginning of the planning horizon by considering to simultaneously minimize the expected total cost and maximize the guarantee of both the inventory balance and service levels. The model can be described as follows [25]:(38)minE∑j=1nμjxj+νjsjξj+γjwjmaxPx1≥ξ1x1+x2≥ξ2⋮x1+x2+x3+⋯+xn≥ξns.t.0≤xt≤Mtwt,t∈1,n,stξt≥∑j=1txj-ξt,t∈1,n-1,snξn=∑t=1nxt-ξn,stξt≥0,wt2+1-wt2=1,t∈1,n,where μj,νj, and γj are parameters, xj,sj, and wj are decision variables, and ξt, t=1,…,n are stochastic variables.Definegt(x,ξ)≔ξt-(x1+⋯+xt), t=1,…,n. A fundamental difficulty in solving (38) is that the evaluation of function P[g(x,ξ)≤0] is nontrival and it is difficult to have its closed form, where g≔(g1,…,gn). Therefore, many approximate methods have been proposed. CVaR approximation presented by Rockafellar and Uryasev is one of those methods, which is the best convex conservative approximation [26]. However, Hong et al. point out that the CVaR approximation is not a good approximation [27]. Therefore, Hong et al. present a DC approach, which can approximate p(x) better than CVaR approximation [27]. Define p(x)≔1-P[g(x,ξ)≤0]. The DC approximation of p(x) can be stated as follows:(39)p~x,t≔π1x,t-π2xt,where π1(x,t)≔E[t+g~(x,ξ)]+, π2(x)≔π1(x,0), and g~(x,ξ)≔max⁡{g1(x,ξ),…,gn(x,ξ)}. Note that [a]+≔max⁡{a,0}.We use DC approximation (39) to replace the probability function in (38). We assume that the stochastic variables ξ are defined on the sample space Ω. For an integrable function ψ:Ω→R, the Monte Carlo sampling estimate for E[·] is obtained by taking independently and identically distributed random samples [ξ1,…,ξL] from Ω and letting E[ψ(ω)]≈(1/L)∑l=1Lρ(ωl)ψ(ωl), where ρ(ωl) is the probability. Define (40)cx,ξl≔max1≤t≤n⁡cjx,ξtlL,l=1,…,L,where ct(x,ξtl)≔ξtl-(x1+x2+⋯+xt),t=1,…,n,l=1,…,L. In this paper, we use (41)f2x≔∑l=1L0.05+cx,ξl+-cx,ξl+0.05as the approximation function to (39), where ξl∈[1,2],l=1,…,L are stochastically generated, and [·]+ denotes that [x]+=x, if x>0; otherwise [x]+=0,(x≤0). Define the feasible set(42)S≔0≤xt≤Mtwt,t∈1,n,st≥∑j=1txj-∑l=1LξtlL,t∈1,n-1,sn=∑j=1nxj-∑l=1LξnlL,st≥0,wt2+1-wt2=1,t∈1,n.With the above notations, we can describe Algorithm4 with U≔R+m for solving Problem (38) as follows.Algorithm 13.Step 0. Give w0≔(w10,w20,…,wn0)∈{0,1}n; xj0∈[0,Mtwt],j=1,…,n; st0≔∑j=1txj0-∑k=1Kξtk/K,t=1,…,n. Let k≔0.Step 1. Compute the following optimization problem:(43)minηs.tf1x,s,w+12x,s,w-xk,sk,wk2≤η∑l=1L0.05+cx,ξl+-∇xcj∗xp,ξlI0,+∞cxp,ξlTx-xk0.05+θk2x-xk2≤ηx,s,w∈S,where I(0,+∞)(·) is the indicator function defined as I(0,+∞)(y)=1, if y∈(0,+∞); otherwise, 0; j∗ satisfies c(x,ξl)≔max1≤j≤n(cjx,ξjl/L),l=1,…,L. (xk+1,sk+1,wk+1) is the optimum of the above subproblem.Step 2. If (xk+1,sk+1,wk+1)-(xk,sk,wk)≤10-6, then stop; otherwise, k≔k+1 and go to Step 1.Similarly, we can present Algorithm8 and ϵ–approximate algorithm for solving problem (38).


### 4.2. Numerical Results

To show the efficiency of the proposed method, this section presents several numerical tests; that is, use Algorithms4 and 8 and ϵ-proximal algorithm for solving problem (38). We note that the codes are written in Matlab 7.10 with built-in solver “fmincon” to solve the convex subproblems. A DELL computer is used to conduct the tests where the computer is with 4.00 GB of memory and Intel(R)Core(TM)i5-2400 processor (3.10 GHz).The parameters used in the tests are set as follows:θjk and θk are stochastically generated in the set [1,2]; the initial point is stochastically chosen from the feasible region of (38); the terminating rule ε≔1×10-6; for k≥1, ϵk is set as 1/k2; ϵ0 is set as zero; we assume that Mt∈[10,20], and μt,νt,γt,ξt∈[1,2],t=1,…,n, are stochastically generated. The numerical reports are presented in Table 1, where computing time in seconds (“CPU”) and the number of iterations (“Iter”) are given. We note that 500 is set as the maximal number of iterations. From Table 1, we conclude that Algorithm 8 under performs Algorithm 4 with respect to CPU time and the number of iterations. The ϵ-approximation of Algorithm 8 also underperforms the corresponding ϵ-approximation of Algorithm 4 with respect to CPU time and the number of iterations. These results mean that the theoretical results are true and the proposed algorithms are effective in solving (38).Table 1
Numerical results.
n
K
Algorithm4
Algorithm8
ϵ-Algorithm 4
ϵ-Algorithm 8
Iter
CPU
Iter
CPU
Iter
CPU
Iter
CPU
10
500
15
0.02
17
0.02
17
0.03
27
0.04
10
1000
16
0.03
17
0.02
18
0.03
27
0.03
20
500
21
0.09
24
0.09
26
0.1
32
0.15
20
1000
21
0.12
34
0.22
28
0.25
34
0.28
50
500
37
0.47
48
0.75
50
0.55
50
0.56
50
1000
37
0.47
49
0.77
59
0.62
59
0.67
100
500
59
0.99
78
0.81
75
1.33
78
1.47
100
1000
87
1.55
98
1.89
124
3.96
170
4.39
150
500
341
57.2
500
207.13
500
292.12
500
287.58
150
1000
500
321.22
500
210.35
500
299.27
500
294.77


## 4.1. Probabilistic Lot Sizing with Service Levels

In probabilistic lot sizing with service levels, the order quantities,xt,t=1,…,n, are determined at the beginning of the planning horizon by considering to simultaneously minimize the expected total cost and maximize the guarantee of both the inventory balance and service levels. The model can be described as follows [25]:(38)minE∑j=1nμjxj+νjsjξj+γjwjmaxPx1≥ξ1x1+x2≥ξ2⋮x1+x2+x3+⋯+xn≥ξns.t.0≤xt≤Mtwt,t∈1,n,stξt≥∑j=1txj-ξt,t∈1,n-1,snξn=∑t=1nxt-ξn,stξt≥0,wt2+1-wt2=1,t∈1,n,where μj,νj, and γj are parameters, xj,sj, and wj are decision variables, and ξt, t=1,…,n are stochastic variables.Definegt(x,ξ)≔ξt-(x1+⋯+xt), t=1,…,n. A fundamental difficulty in solving (38) is that the evaluation of function P[g(x,ξ)≤0] is nontrival and it is difficult to have its closed form, where g≔(g1,…,gn). Therefore, many approximate methods have been proposed. CVaR approximation presented by Rockafellar and Uryasev is one of those methods, which is the best convex conservative approximation [26]. However, Hong et al. point out that the CVaR approximation is not a good approximation [27]. Therefore, Hong et al. present a DC approach, which can approximate p(x) better than CVaR approximation [27]. Define p(x)≔1-P[g(x,ξ)≤0]. The DC approximation of p(x) can be stated as follows:(39)p~x,t≔π1x,t-π2xt,where π1(x,t)≔E[t+g~(x,ξ)]+, π2(x)≔π1(x,0), and g~(x,ξ)≔max⁡{g1(x,ξ),…,gn(x,ξ)}. Note that [a]+≔max⁡{a,0}.We use DC approximation (39) to replace the probability function in (38). We assume that the stochastic variables ξ are defined on the sample space Ω. For an integrable function ψ:Ω→R, the Monte Carlo sampling estimate for E[·] is obtained by taking independently and identically distributed random samples [ξ1,…,ξL] from Ω and letting E[ψ(ω)]≈(1/L)∑l=1Lρ(ωl)ψ(ωl), where ρ(ωl) is the probability. Define (40)cx,ξl≔max1≤t≤n⁡cjx,ξtlL,l=1,…,L,where ct(x,ξtl)≔ξtl-(x1+x2+⋯+xt),t=1,…,n,l=1,…,L. In this paper, we use (41)f2x≔∑l=1L0.05+cx,ξl+-cx,ξl+0.05as the approximation function to (39), where ξl∈[1,2],l=1,…,L are stochastically generated, and [·]+ denotes that [x]+=x, if x>0; otherwise [x]+=0,(x≤0). Define the feasible set(42)S≔0≤xt≤Mtwt,t∈1,n,st≥∑j=1txj-∑l=1LξtlL,t∈1,n-1,sn=∑j=1nxj-∑l=1LξnlL,st≥0,wt2+1-wt2=1,t∈1,n.With the above notations, we can describe Algorithm4 with U≔R+m for solving Problem (38) as follows.Algorithm 13.Step 0. Give w0≔(w10,w20,…,wn0)∈{0,1}n; xj0∈[0,Mtwt],j=1,…,n; st0≔∑j=1txj0-∑k=1Kξtk/K,t=1,…,n. Let k≔0.Step 1. Compute the following optimization problem:(43)minηs.tf1x,s,w+12x,s,w-xk,sk,wk2≤η∑l=1L0.05+cx,ξl+-∇xcj∗xp,ξlI0,+∞cxp,ξlTx-xk0.05+θk2x-xk2≤ηx,s,w∈S,where I(0,+∞)(·) is the indicator function defined as I(0,+∞)(y)=1, if y∈(0,+∞); otherwise, 0; j∗ satisfies c(x,ξl)≔max1≤j≤n(cjx,ξjl/L),l=1,…,L. (xk+1,sk+1,wk+1) is the optimum of the above subproblem.Step 2. If (xk+1,sk+1,wk+1)-(xk,sk,wk)≤10-6, then stop; otherwise, k≔k+1 and go to Step 1.Similarly, we can present Algorithm8 and ϵ–approximate algorithm for solving problem (38).


## 4.2. Numerical Results

To show the efficiency of the proposed method, this section presents several numerical tests; that is, use Algorithms4 and 8 and ϵ-proximal algorithm for solving problem (38). We note that the codes are written in Matlab 7.10 with built-in solver “fmincon” to solve the convex subproblems. A DELL computer is used to conduct the tests where the computer is with 4.00 GB of memory and Intel(R)Core(TM)i5-2400 processor (3.10 GHz).The parameters used in the tests are set as follows:θjk and θk are stochastically generated in the set [1,2]; the initial point is stochastically chosen from the feasible region of (38); the terminating rule ε≔1×10-6; for k≥1, ϵk is set as 1/k2; ϵ0 is set as zero; we assume that Mt∈[10,20], and μt,νt,γt,ξt∈[1,2],t=1,…,n, are stochastically generated. The numerical reports are presented in Table 1, where computing time in seconds (“CPU”) and the number of iterations (“Iter”) are given. We note that 500 is set as the maximal number of iterations. From Table 1, we conclude that Algorithm 8 under performs Algorithm 4 with respect to CPU time and the number of iterations. The ϵ-approximation of Algorithm 8 also underperforms the corresponding ϵ-approximation of Algorithm 4 with respect to CPU time and the number of iterations. These results mean that the theoretical results are true and the proposed algorithms are effective in solving (38).Table 1
Numerical results.
n
K
Algorithm4
Algorithm8
ϵ-Algorithm 4
ϵ-Algorithm 8
Iter
CPU
Iter
CPU
Iter
CPU
Iter
CPU
10
500
15
0.02
17
0.02
17
0.03
27
0.04
10
1000
16
0.03
17
0.02
18
0.03
27
0.03
20
500
21
0.09
24
0.09
26
0.1
32
0.15
20
1000
21
0.12
34
0.22
28
0.25
34
0.28
50
500
37
0.47
48
0.75
50
0.55
50
0.56
50
1000
37
0.47
49
0.77
59
0.62
59
0.67
100
500
59
0.99
78
0.81
75
1.33
78
1.47
100
1000
87
1.55
98
1.89
124
3.96
170
4.39
150
500
341
57.2
500
207.13
500
292.12
500
287.58
150
1000
500
321.22
500
210.35
500
299.27
500
294.77


## 5. Conclusion

This paper proposes both exact and inexact proximal point algorithms for solving vector DC optimization problems. The proposed algorithms enjoy both well-posedness and global convergence under suitable assumptions. An application to a probabilistic lot sizing with service levels is considered. We first show that this model can be equivalently cast as a multiobjective DC optimization problem. Then, the proposed algorithms are utilized to solve the resulting problem. The numerical results show that the methods are efficient. For future work, we can discuss the local convergence of the proposed algorithms. The construction of methods for solving the vector DC optimization problems with nonsmooth objectives is also an interesting topic for future work.



---

*Source: 5675183-2017-10-31.xml*