# An Infeasible Incremental Bundle Method for Nonsmooth Optimization Problem Based on CVaR Portfolio

Authors: Jia-Tong Li; Jie Shen; Na Xu
Journal: Complexity
 (2021)

---

## Abstract

For CVaR (conditional value-at-risk) portfolio nonsmooth optimization problem, we propose an infeasible incremental bundle method on the basis of the improvement function and the main idea of incremental method for solving convex finite min-max problems. The presented algorithm only employs the information of the objective function and one component function of constraint functions to form the approximate model for improvement function. By introducing the aggregate technique, we keep the information of previous iterate points that may be deleted from bundle to overcome the difficulty of numerical computation and storage. Our algorithm does not enforce the feasibility of iterate points and the monotonicity of objective function, and the global convergence of the algorithm is established under mild conditions. Compared with the available results, our method loosens the requirements of computing the whole constraint function, which makes the algorithm easier to implement.


---

## Body

## 1. Introduction

Optimization problems arise in the wide range of practical applications, and they have been successfully solved by utilizing various methods, especially by state of the art approaches [1–3]. For an actual engineering optimization problem [2], a new optimal mutation strategy based on the complementary advantages of five mutation strategies is designed to develop a novel improved differential evolution algorithm with the wavelet basis function; the proposed method can improve the search quality, accelerate convergence and avoid fall into local optimum and stagnation. Parametric analysis and optimization are conducted for a novel geothermal combined cooling and power system [3], and not only the combined system performs better than the separate system but also the n-nonane brings the lowest total product unit cost to the proposed system. Nonsmooth optimization (NSO) problems are in general difficult to solve. Lots of approaches are proposed to solve these problems [4–8]. Among others, bundle methods are considered as one of the most efficient and promising methods. Infeasible bundle methods [9,10] can be viewed as the unconstrained proximal-like bundle methods applied to improvement functions, and the main advantage superior to other methods is that it does not require the feasibility of the iterate points and the monotonicity of the objective function. Conditional value-at-risk (CVaR) is currently the main tool to measure financial risk when we face portfolio for selected risky assets, and the study of CVaR model usually brings about the following nonsmooth optimization problem:(1)minx,α∈Rn×RFθx,α=α+11−θJ∑j=1J−xTyj−α+,s.t,−xTm≤−M,∑i=1nxi=1,x≥0,where Fθx,α is the approximate performance function which is convex and θ∈0,1 is the probability level, YJ×n=yji is the scenario matrix, J is the number of scenarios, and its element yji denotes the yield rate of risky asset under scenario j. The vector yj=yj1,yj2,…,yjnT is the vector of yield rate of scenario, j. ·+=max0,·. The vector y∈Rn denotes the yield rate at the end of investment which is uncertain, and m=Ey, the constant M is the given rate of expected return. We rewrite problem (1) in more general form:(2)minx,α∈Rn×RFθx,α,s.tcx,α≤0,where cx,α=maxcjx,α|,j∈J˜=1,2,…,n+3 is the pointwise maximum of finite many convex functions, c1x,α=−xTe1,c2x,α=−xTe2,…,cnx,α=−xTen,cn+1x,α=−xTm+M, and cn+2x,α=xTe−1,cn+3x,α=−xTe+1 are called the component functions of c, and ei=0,…,1ith,…,0T∈Rn,e=1,1,…,1T∈Rn. Obviously, function c:Rn+1⟶R is convex and nondifferentiable.Problem (2) involves a special constraint function, namely, the max-valued function. Qing-Ye Zhang and Yan Gao [11] once transform the objective function in the CVaR model into a piecewise smooth function and present an algorithm by employing common proximal bundle methods, where the values of every component function need to be evaluated at each iteration. An incremental method for solving convex finite min-max problem provides us a new approach to deal with max-valued function, which extends the philosophy of the incremental approaches [12], and it does not need to evaluate the actual value of max-valued function. The idea has already been applied to linearly constrained min-max problems [13] and to inequality constraint min-max problems [14]. The algorithms provided by the above two papers are feasible and descent methods. But in some cases, the feasibility of iterate points is difficult to realize since we have to make a tradeoff between the search for feasibility and for the reduction of the objective function.Motivated by the work [14, 15], we provide an iterate method which is strongly connected with the incremental technique [12] and the infeasible idea [9]. The algorithm we design does not require the evaluation of each component function of the constraint function. In other words, we employ the incomplete knowledge of the constraint function to construct a lower approximate model for improvement function associated with the original problem, which reduces the number of elements in bundle and decreases the difficulty of implementation of the algorithm. Based on the approximate model, a descent test is presented. Even though the model is a more rough approximation to improvement function, the proposed algorithm still possesses good convergence properties under mild conditions.This paper is organized as follows: In Section2, we introduce basic notations, concepts, and existing results which are the basis for the construction of approximate model and the design of overall algorithm. A new cutting-planes framework and the way to update the elements in bundle are also given in this section. Section 3 presents an infeasible incremental bundle algorithm for solving problem (2). The convergence analysis of the presented algorithm is discussed in Section 4, and the optimal solution to problem (2) is obtained under mild conditions.


## 2. Preliminaries and the Construction of Subproblem

We denote by·,· and · the usual inner product and norm in Rn, respectively. The subdifferential of a convex function f:Rn⟶R at x is defined by ∂fx=p∈Rn|fy≥fx+p,y−x,∀y∈Rn. Let(3)D=x,α∈Rn+1|cx,α≤0be the feasible set of problem (2), and for sake of the notation simplicity, we leave out the confidence parameter θ in (2) and indicate Fθx,α by Fx,α.Lemma 1.
Suppose thatfixi∈I is the convex differentiable function and the index set I is finite. Then, the subdifferential of function fx=maxfix|i∈I is ∂fx=co∇fix|i∈Ix, where “co” denotes the convex hull, Ix=i∈I|fix=fx.Definition 1.
For giveny,β∈Rn+1, the following function,(4)Hy,βx,α=maxFx,α−Fy,β,cx,α,x,α∈Rn+1,is called the improvement function associated with problem (2).
The following lemmas present some useful properties of improvement function which play an important role in designing our algorithm.Lemma 2.
[9] The subdifferential of improvement function Hy,β·,· at point x,α is given by(5)∂Hy,βx,α=∂Fx,α,ifFx,α−Fy,β>cx,α,conv∂Fx,α∪∂cx,α,ifFx,α−Fy,β=cx,α,∂cx,α,ifFx,α−Fy,β<cx,α.Lemma 3.
[16] Suppose that the Slater constraint qualification is satisfied for problem (2), the following statements are equivalent:(i)
x¯,α¯ is a solution to problem (2)(ii)
minHx¯,α¯y,β|y,β∈Rn+1=Hx¯,α¯x¯,α¯(iii)
0∈∂Hx¯,α¯x¯,α¯, i.e., 0∈∂ϕx¯,α¯, where ϕ·,·=Hx¯,α¯·,·
Suppose thatxk,αk is the current stability center (the current last serious step) and yi,βi is the trial point generated from previous iterations. We indicate Hxk,αk·,· by Hk·,·. Choose arbitrarily one component function cjofc and define the values of the linearization functions of Fand cj at point xk,αk:(6)sFik=Fyi,βi+gFi,xk,αk−yi,βi,tcjik=cjyi,βi+gcji,xk,αk−yi,βi,where gFi∈∂Fyi,βi,gcji∈∂cjyi,βi. Bundle Bl keeps memory of the information of previous iterations:(7)Bl=Bl1∪Bl2∪xk,αk,Fxk,αk,cxk,αk,k=kl,withBl1⊆∪i<lFyi,βi,cjyi,βi,sFik,tcjik,gFi∈∂Fyi,βi,gcji∈∂cjyi,βi,Bl2⊆∪i<lε^ik,g^i∈∂ε^ikHkxk,αk,if there is compression,where kl denotes the index of the last serious step preceding the iteration l, when it is clear from the context, we do not specify the dependence of k on the current iteration index l. The element ε^ik,g^i in Bl2 is the aggregate couple that is introduced when compression of bundle is implemented for controlling the size of bundle, and we will discuss aggregate technique later in detail.Lemma 4.
Define(8)eik=Fxk,αk−sFik+c+xk,αk,ifFyi,βi−Fxk,αk≥cyi,βi,−tcjik+c+xk,αk,ifFyi,βi−Fxk,αk<cyi,βi,gHki=gFi,ifFyi,βi−Fxk,αk≥cyi,βi,gcji,ifFyi,βi−Fxk,αk<cyi,βi,where notations sFik,tcjik,gFi,gcji,yi,βi, and xk,αk are from (6) and (7). Then, we have eik≥0 and gHki∈∂eikHkxk,αk.Proof.
By definitions ofsFik,tcjik and gFi∈Fyi,βi,gcji∈∂cjyi,βi, we have
Fxk,αk−sFik≥0 and cjxk,αk−tcjik≥0. Since c+xk,αk≥0,c+xk,αk≥cjxk,αk, it follows from (8) that eik≥0. According to the definition of improvement function Hk·,·, we have(9)Hky,β≥maxFy,β−Fxk,αkcy,β≥maxFy,β−Fxk,αkcjy,β=max−Fxk,αk+sFik+gFi,y,β−xk,αktcjik+gcji,y,β−xk,αk=c+xk,αk+gHki,y,β−xk,αk−Fxk,αk−sFik+c+xk,αk,ifFyi,βi−Fxk,αk≥cyi,βi,−tcjik+c+xk,αk,ifFyi,βi−Fxk,αk<cyi,βi.
Notice thatHkxk,αk=c+xk,αk and the above inequality implies gHki∈∂eikHkxk,αk.
Now, we are in position to define the cutting-planes model forHk·,·:(10)ψly,β=c+xk,αk+maxmaxi∈Bl1−eik+gHki,y,β−xk,αk,maxi∈Bl2−ε^ik+g^i,y,β−xk,αk.
By Lemma3 and g^i∈∂ε^ikHkxk,αk, ψl is a lower approximate model for Hk, that is,(11)ψly,β≤Hky,β,∀y,β∈Rn+1.
Givenμl, a positive proximal parameter, the next trial point yl,βl is generated by solving the following quadratic programming:(12)miny,β∈Rn+1ψly,β+μl2y,β−xk,αk2.
Obviously,yl,βl is unique and(13)yl,βl=xk,αk−1μlg^l,whereg^l∈∂ψlyl,βl.
In order to measure whether the new trial pointyl,βl provides sufficient decrease of Hk·,·, we define the nominal decrease δl by(14)δl=Hkxk,αk−ψlyl,βl−μl2yl,βl−xk,αk2=ε^lk+12μlg^l2,where(15)ε^lk=Hkxk,αk−ψlyl,βl−1μlg^l2≥0.
Sinceyl,βl is the solution to problem (12) and ψl is a lower approximation to Hk, we have(16)Hkxk,αk≥ψlxk,αk≥ψlyl,βl+μl2yl,βl−xk,αk2.
It follows thatδl≥0. Now, we present the descent test. Let m∈0,1 be a given parameter, when yl,βl satisfies:(17)Hkyl,βl≤cj+xk,αk−mδl,then we declare a serious step: xk+1,αk+1=yl,βl; otherwise, a null step is declared: xk+1,αk+1=xk,αk. Notice that here we only employ the information of one component function cj of c to measure the “property” of the new generated trial point yl,βl, unlike [9]; therein, they use the whole information of c.
Obviously, for anyy,β∈Rn+1,(18)Hky,β≥ψly,β≥ψlyl,βl+g^l,y,β−yl,βl=Hkxk,αk−g^l,y,β−xk,αk−ε^lk,Hence, g^l∈∂ε^lkHxk,αk. If ε^lk and g^l are very small, it follows that the approximate optimality condition is satisfied and the algorithm stops (see Step 3 in Algorithm 1).
As iterations go along, the number of elements in bundleBl increases and the burden of computation and storage increases simultaneously. When the size of bundle becomes too big, it is necessary to compress and to clean the model. We have to discard some elements from bundle Bl1 and append the aggregate couple ε^lk,g^l into bundle Bl2 since the aggregate couple summarizes the information of previous iterate points [17]. For this purpose, we introduce the aggregate function:(19)lk,ly,β=Hkxk,αk+g^l,y,β−xk,αk−ε^lk,y,β∈Rn+1.
It has the following equivalent expression:(20)lk,ly,β=ψlyl,βl+g^l,y,β−yl,βl,y,β∈Rn+1.
For eachk, the following conditions guarantee the bundle technique applied to function Hkeither produces a serious step after a finite number of null steps, or the current serious step xk,αk is the minimum of Hk[18]:(21)aψly,β≤Hky,β,for alll≥1;blkl,ly,β≤ψl+1y,β,yl,βlis a null step;cHkyl,βl+gHkl,y,β−yl,βl,yl,βlis a null step.
Conditions (b) and (c) mean that the bundleBl should contain both the aggregate information and the last generated information.
For model functionψl defined by (10) to satisfy conditions (a)-(c) when passing to the next iteration l+1, we should consider two cases of the lth iteration being a null step or a serious step. When there is a null step, the updates of the elements in bundle and the model do not present any problems since the improvement function is fixed between consecutive serious steps. Now suppose that the lth iteration produces a serious step, i.e., x,k+1αk+1=yl,βl, it means that for the next iteration we have to work with the new function Hk+1·,·=Hxk+1,αk+1·,·. Since serious step can be infeasible and the monotonicity of the objective function is not enforced, we can only make sure Hkxk+1,αk+1<Hkxk,αk, it is possible that Fxk+1,αk+1>Fxk,αk, and in that case, we have Hk+1·,·≤Hk·,·, and, as a consequence, the cutting-planes model for Hk·,· may not be a lower approximation for Hk+1·,·. Thus, the old model must be revised and adjusted to ensure that the conditions a−c are satisfied for the new function Hk+1·,·.
Next lemma provides one approach to make sure that all elements in bundle correspond to approximate subgradients of new improvement functionHk+1 at x,k+1αk+1; hence, the model ψl+1 is still a lower approximation function for Hk+1 after adjusting the bundle. For elements in Bl1, we only need to update the values of the linearization functions of F and cj at x,k+1αk+1. For elements in Bl2, we have to invoke the information of F and c in order to make sure the aggregate subgradient g^i also corresponds to some approximate subgradient of Hk+1at x,k+1αk+1.Algorithm 1:Infeasible incremental bundle method for CVaR portfolio.
Input:ε1>0,ε2>0,γ>0, μmax>μmin>0,m¯∈0,1, and Bmax≥2.Step 1: given an initial proximal parameterμ0>0. Choose x0,α0∈Rn+1and one component function cjof c, set y0,β0=x0,α0, and compute Fy0,β0,cjy0,β0,gF0∈∂Fy0,β0,gcj0∈∂cjy0,β0. Set k=0,l=1, sF00=Fy0,β0,tcj00=cjy0,β0.DefineB11=sF00,tcj00,Fy0,β0,cjy0,β0,gF0,gcj0, B12=∅.Step 2: find the solutionyl,βl to problem (12). Compute g^l=μlxk,αk−yl,βl,ε^lk=Hkxk,αk−ψlyl,βl−1/μlg^l2,δl=ε^lk+1/2μlg^l2,Fyl,βl,cjyl,βl,gFl,gcjl, and sFlk,tcjlk using (6) written i with l.Step 3: ifε^lk≤ε1and g^l2≤ε2, then stop, xk,αk is an approximate solution to problem (2).Step 4: computeHkyl,βl. If Hkyl,βl≤cj+xk,αk−m¯δl, then set xk+1,αk+1=yl,βl (serious step) and μl+1=maxμl/γ,μmin. Otherwise, set xk+1,αk+1=xk,αk (null step) and μl+1=minγμl,μmax.Step 5: setBl+11=Bl1,Bl+12=Bl2, if Bl+1=Bmax, then delete at least two elements from Bl+1, and append ε^lk,g^lto Bl+12. Append Fyl,βl,cjyl,βl,gFl,gcjl,sFlk,tcjlk to Bl+11.Step 6: if a serious step is taken, choosej¯∈J˜xk+1,αk+1=j∈J˜|cjxk+1,αk+1=cxk+1,αk+1 such that the function cj¯ is the component function of cwe choose for constructing the cutting-planes model for Hk+1·,·. Replace component function cj by cj¯ and compute tcjik again. Update sFik+1,tcjik+1 for i∈Bl+11 by (22) and update ε^ik+1 for i∈Bl+12 by (23).Setk=k+1.Step 7: setl=l+1, go to Step 2.End of Algorithm1.Lemma 5.
Suppose that the trial pointyl,βl generated by (12) is a serious step, i.e.,xk+1,αk+1=yl,βl. Then, the following statements hold:(i)
For eachi∈Bl1,(22)sFik+1=sFik+gFi,xk+1,αk+1−xk,αk,tcjik+1=tcjik+gcji,xk+1,αk+1−xk,αk.Furthermore,gHk+1i∈∂eik+1Hk+1xk+1,αk+1, where eik+1≥0 and gHk+1i are defined in (8) written with k replaced by k+1.(ii)
For eachi∈Bl2, define(23)ε^ik+1=ε^ik+c+xk+1,αk+1−c+xk,αk+Fxk+1,αk+1−Fxk,αk++g^i,xk,αk−xk+1,αk+1.
Then,ε^ik+1≥0 and g^i∈∂ε^ik+1Hk+1xk+1,αk+1.Proof.
For eachi∈Bl1, we have, for all y,β∈Rn+1,(24)Fy,β≥Fyi,βi+gFi,y,β−yi,βi=Fxk,αk+gFi,y,β−xk,αk−Fxk,αk−sFik≥Fxk+1,αk+1+gFi,y,β−xk+1,αk+1−Fxk+1,αk+1−sFik+gFi,xk+1,αk+1−xk,αk.
It follows from (22) and gFi∈Fxk,αk−sFikFxk+1,αk+1 that(25)Fxk+1,αk+1≥Fxk,αk+gFi,xk+1,αk+1−xk,αk−Fxk,αk−sFik=sFik+gFi,xk+1,αk+1−xk,αk=sFik+1.
Therefore,Fxk+1,αk+1−sFik+1≥0 and gFi∈Fxk+1,αk+1−sFik+1Fxk+1,αk+1. Similarly,
we havegcji∈cjxk+1,αk+1−tcjik+1cjxk+1,αk+1. The remaining proof can be finished by imitating the proof of Lemma 2.3 in [9], where the quantities l,k,sFik,tcjik are replaced by l+1,k+1,sFik+1,tcjik+1, respectively.
For eachi∈Bl2, the update pattern is just the one in [9], so we omit the proof.
To sum up, no matter whether thelth iteration produces a null step or a serious step, as long as,(26)Bl+11⊆∪i<l+1Fyi,βi,cjyi,βi,sFik+1,tcjik+1,gFi,gcji,Bl+22⊆∪i<l+1ε^ik+1,g^i,the model(27)ψl+1y,β=c+xk+1,αk+1+maxmaxi∈Bl+11−eik+1+gHk+1i,y,β−xk+1,αk+1,maxi∈Bl+12−ε^ik+1+g^i,y,β−xk+1,αk+1satisfies condition (a) in (21) written with l replaced by l+1 and k replaced by k+1, and the point xk+1,αk+1 indicates the k+1th stability center which may be xk,αk if a null step is executed. Furthermore, if ε^lk,g^l⊆Bl+12, then ψl+1 satisfies condition (b) in (21), and if Fyl,βl,cjyl,βl,sFlk+1,tcjlk+1,gFl,gcjl⊆Bl+11, then ψl+1 satisfies condition (c) in (21).


## 3. Infeasible Incremental Bundle Algorithm for Problem (2)

Remark 1.
If a serious step is declared, we have(28)Fxk+1,αk+1−Fxk,αk≤cj+xk,αk−m¯δl,(29)cxk+1,αk+1≤cj+xk,αk−m¯δl.


## 4. Convergence Analysis

In this part, we discuss the convergence of Algorithm1 by borrowing the main idea from [9]. From now on we assume that Algorithm 1 produces an infinite sequence of iterate points. As usual in the convergence analysis of bundle methods, we consider two cases: the number of serious steps is infinite and the number of serious steps is finite, and the last serious step is followed by infinitely many null steps. Let Ls=l|yl,βlis a serious step be the set which collects the indices of serious steps in the sequence yl,βl.Proposition 1.
For any iteration indexk0≥0 of serious step, it holds that(30)xk,αk∈x,α∈Rn+1|cx,α≤c+xk0,αk0,∀k≥k0.
In particular, ifxk1,αk1∈D for some k1≥0, then xk,αk∈D, for all k≥k1.Proof.
In Algorithm1, the descent test is designed as follows: Hkyl,βl≤cj+xk,αk−m¯δl. Since function c is the pointwise maximum of finite convex functions cjj∈J˜, it follows that c+xk,αk≥cj+xk,αk. If a serious step is declared, we have Hkyl,βl≤c+xk,αk−m¯δl. Next, we adopt the techniques similar to [9], and the desired conclusions can be obtained.Proposition 2.
SupposeF is bounded below on D and Algorithm 1 generates an infinite number of serious steps. Then ε^lkl∈Ls⟶0 and g^ll∈Ls⟶0.Proof.
It follows from (29) and cxk,αk=maxcjxk,αk|j∈J˜ that if a serious step is declared,(31)cxk+1,αk+1≤cj+xk,αk−m¯δlk+1≤cxk,αk−m¯δlk+1.
Hence, the sequencecxk,αk is decreasing. Notice the update pattern of proximal parameter sequence μl in Algorithm 1, we have μl≤μmax for all l, i.e., the condition μl≤μ¯ for some μ¯>0 holds. Following the thinking of [6], we can prove ε^lkl∈Ls⟶0 and g^ll∈Ls⟶0.
Next proposition discusses the conditions which ensure the boundedness of sequence of serious stepsxk,αk.Proposition 3.
Suppose that problem (2) has a solution x¯,α¯ and Algorithm 1 produces an infinite number of serious steps. If the feasible set D is bounded or there exists some iteration index k1 such that Fx¯,α¯≤Fxk,αk+cj+xk,αk for all k≥k1 and for some j∈J˜, then the sequence xk,αk is bounded.Proof.
For the first case that the feasible setD is bounded, since D is the level set of function c, the convexity of function c implies that all the level sets of function c are bounded. Then, the boundedness of xk,αk follows from the conclusion of Proposition 1. For the second case, since g^l∈∂ε^lkHkxk,αk and δl=ε^lk+1/2μlg^l2, we have(32)xk+1,αk+1−x¯,α¯2=xk,αk−x¯,α¯2−2μlg^l,xk,αk−x¯,α¯+1μl2g^l2≤xk,αk−x¯,α¯2+2μlHkx¯,α¯−Hkxk,αk+δl.
Observe thatFx¯,α¯≤Fxk,αk+cj+xk,αk≤Fxk,αk+c+xk,αk for all k≥k1 and cjx¯,α¯≤0,c+xk,αk≥0, we have(33)Hkx¯,α¯−Hkxk,αk=maxFx¯,α¯−Fxk,αk,cx¯,α¯−c+xk,αk≤0.
By combining (32) and (33), it follows that(34)xk+1,αk+1−x¯,α¯2≤xk,αk−x¯,α¯2+2μlδl,∀k≥kl.
By [19], ∑l∈Lsδl<+∞, and the conclusion we have just proved in Proposition 2, the sequence xk+1,αk+1−x¯,α¯ is convergent, and hence the sequence xk,αk is bounded.Theorem 1.
Suppose that problem (2) satisfies the Slater constraint qualification and its solution set is nonempty. Assume that Algorithm 1 generates an infinite number of serious steps, which is bounded. Then, all the accumulation points of the sequence xk,αkare solutions to problem (2). And, if there exists some iteration index k1 such that Fx¯,α¯≤Fxk,αk+cj+xk,αkfor all k≥k1 and for some j∈J˜, the whole sequence xk,αk converges to a solution to problem (2).Proof.
Since the proof is very similar to the one in [9], we omit it.
Now we consider the second case that the Algorithm1 generates finite serious steps followed by infinitely many null steps, i.e., there exists an index last=maxl|l∈Ls, and the corresponding last serious step index is denoted by klast. Notice that the improvement function is fixed for k≥klast, that is, Hk·,·=Hklast·,·, ∀k≥klast.Theorem 2.
Suppose that problem (2) satisfies the Slater constraint qualification and Algorithm 1 produces a finite number of serious steps, then xklast,αklast is a solution to problem (2).Proof.
We consider the casel≥llast and denote H·,·=Hklast·,·. By imitating the proof of Theorem 4.5 in [9], we obtain(35)Hy¯,β¯+μmax2y¯,β¯−xklast,αklast2≤Hxklast,αklast,(36)ψliyli,βli⟶Hy¯,β¯,i⟶+∞,where y¯,β¯ is an accumulation point of yl,βl, i.e.,yli,βli⟶y¯,β¯ as i⟶+∞. Since we assume that klast is the last index for serious step, the descent test is not satisfied for l≥last:(37)Hyl,βl−cj+xklast,αklast>−m¯δl≥−m¯Hxklast,αklast−ψlyl,βl.
From Step 6 in Algorithm1, we know if a serious step is declared, we choose j¯ from J˜xk+1,αk+1=j∈J¯|cjxk+1,αk+1=cxk+1,αk+1 such that the function cj¯ is the component function of c we chose for constructing the cutting-planes model for Hk+1·,·. Therefore, according to (37),(38)Hyl,βl−Hxklast,αklast≥−m¯Hxklast,αklast−ψlyl,βl.
Taking the limits along the specified subsequence asi⟶+∞, by using (36), we obtain 0≤1−m¯Hxklast,αklast−Hyl,βl. Since m¯∈0,1, we have Hxklast,αklast≤Hyl,βl. Taking into account (36), we have xklast,αklast=y¯,β¯. It follows from (35) that y¯,β¯ is the optimal solution to the following problem:(39)miny,β∈Rn+1Hy,β+μmax2y,β−xklast,αklast2.
According to the optimality condition,0∈∂Hyl,βl=∂Hxklast,αklast, where H·,·=Hklast·,·. By Lemma 3, xklast,αklast is a solution to problem (2).


## 5. Conclusions

We present an infeasible incremental bundle method for the CVaR portfolio nonsmooth optimization problem; the algorithm is easier to implement since it only employs the information of the objective function and one component function of constraint functions. The algorithm does not enforce the feasibility of iterate points and the monotonicity of objective function, but the global convergence is established under mild conditions.



---

*Source: 6640781-2021-01-18.xml*