# A Cutting Plane and Level Stabilization Bundle Method with Inexact Data for Minimizing Nonsmooth Nonconvex Functions

Authors: Jie Shen; Dan Li; Li-Ping Pang
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Under the condition that the values of the objective function and its subgradient are computed approximately, we introduce a cutting plane and level bundle method for minimizing nonsmooth nonconvex functions by combining cutting plane method with the ideas of proximity control and level constraint. The proposed algorithm is based on the construction of both a lower and an upper polyhedral approximation model to the objective function and calculates new iteration points by solving a subproblem in which the model is employed not only in the objective function but also in the constraints. Compared with other proximal bundle methods, the new variant updates the lower bound of the optimal value, providing an additional useful stopping test based on the optimality gap. Another merit is that our algorithm makes a distinction between affine pieces that exhibit a convex or a concave behavior relative to the current iterate. Convergence to some kind of stationarity point is proved under some looser conditions.


---

## Body

## 1. Introduction

Bundle methods family is based on the cutting plane method, first described in [1, 2], where the convexity of the objective function is the fundamental assumption. The extension of bundle methods to the nonconvex case is not straightforward; however, it is apparent that a number of ideas valid in the convex framework are also valuable in the treatment of the nonconvex case. In [3], by combining cutting plane method with proximity control, for minimizing nonsmooth nonconvex function, the authors propose an iterative algorithm which makes a distinction between affine pieces that exhibit a convex or a concave behavior relative to the current point in the iterative procedure, but the exact information of the objective function and its subgradient is needed.Level bundle method is another method which is easier to implement and has shown encouraging numerical results [4, 5]. Some evidence shows that constrained level bundle methods are preferable under certain conditions. Also, strategies for updating the level parameter lk are readily available [6].In various real-world applications, the objective function and/or its subgradient can be costly (sometimes impossible) to compute. This is particularly true whenf is given by some optimization problem; for example, f(x)=max⁡u∈Uϕ(x,u). In such situations, approximate values must be used. Various inexact bundle methods that use approximate functions values and subgradient evaluations have been studied [7].In this work, we combine the level bundle method with cutting plane method involving the idea of proximal control by employing inexact objective function information for minimizing a nonconvex function. The proposed algorithm makes a distinction between affine pieces that exhibit a convex or a concave behavior relative to the current iteration point such that the downward shifting of the affine pieces is not arbitrary. The rest of this paper is organized as follows. Section2 gives some preliminary results and introduces the basic idea of the proposed algorithm. Section 3 describes formally the cutting plane and level stabilization bundle method with inexact data for minimizing nonsmooth nonconvex functions. Section 4 is devoted to convergence analysis of the algorithm with looser conditions than [3]. Section 5 contains some conclusions of the proposed method.


## 2. The Construction of the Model

In this paper, we consider the following unconstrained minimization problem:(1)min⁡f(x)s.t.x∈Rn,
where f:Rn→R+ is not necessarily differentiable. We assume that f is locally Lipschitz; then f is differentiable almost everywhere. It is well known that, in [8], under the above hypotheses, there is defined at each point x the generalized gradient (Clarke's gradient):
(2)∂f(x)=conv{g∈Rn∣∇f(xk)→g,xk→x,xk∉Ωf},
where Ωf is the set, where f is not differentiable, and ∂f(x) is locally bounded. An extension of the generalized gradient is the Goldstein ɛ-subdifferential ∂ɛGf(x) defined as
(3)∂ɛGf(x)=conv{∂f(y)∣∥y-x∥≤ɛ},
which is first described by Goldstein in [9]. The Goldstein subdifferential is both outer and inner semicontinuous as a multifunction of x and ɛ.Throughout the paper, we assume that, givenx∈Rn, the oracle provides some approximate values fx∈R and gxG∈Rn of the objective function and its subgradient, respectively, such that
(4)fx=f(x)-ηx,gxG∈∂ηxgGf(x)=conv{∂f(y)∣∥y-x∥≤ηxg},
where ηx∈R and ηxg≥0 are some unknown errors. Specifically, ηx is uniformly bounded; that is, there exists η≥0 such that
(5)|ηx|≤η,∀x∈Rn.
Let x^k be the current stability center; the bundle Ik of available information is the set of elements:
(6)(xi,fxi,gxiG,αi,ai),i∈Ik,
where αi is the linearization error defined by
(7)αi=fx^k-fxi-〈gxiG,x^k-xi〉
and ai=∥x^k-xi∥. With this information, we create the linearization
(8)f¯i(x)=fxi+〈gxiG,x-xi〉.
At iteration k, a polyhedral cutting plane model of f is available:
(9)fˇk(x)=max⁡i∈Ik{fxi+〈gxiG,x-xi〉}.
Suppose there exists βk>0 such that fˇk(x)≤f(x)+βk, ∀x∈Rn, and βk is uniformly bounded; that is, there exists β>0 such that βk≤β, ∀k. We recall that the classical cutting plane methods [1, 2] minimize fˇk(x) at each iteration, and the minimization of fˇk(x) can be written in linear programming form:
(10)min⁡v~s.t.v~≥fxi+〈gxiG,x-xi〉,i∈Ik,
which is equivalent to solving
(11)min⁡v:=v~-2ηs.t.v:=v~-2η≥(gxiG)Td-αi-2η,i∈Ik,
where d=x-x^k. We divide the set Ik into two sets Ik+ and Ik- defined as follows:
(12)Ik+={i∈Ik∣αi≥-2η},Ik-={i∈Ik∣αi<-2η}.
We observe that Ik+ is never empty since k∈Ik+. By using Ik+ and Ik-, we define two piecewise affine functions:
(13)Δ+(d)=max⁡i∈Ik+{(gxiG)Td-αi},Δ-(d)=min⁡i∈Ik-{(gxiG)Td-αi}.
In fact, Δ+(d) can be regarded as an approximation of the difference function h(d)=fx^k+d-fx^k. Because Δ+(0)≤2η and Δ-(0)>2η, thus Δ+(0)<Δ-(0); it is reasonable to consider the approximation Δ+(d) significant as far as Δ+(d)≤Δ-(d). Therefore we introduce a kind of trust model:
(14)Sf={d∈Rn∣Δ+(d)≤Δ-(d)}.
Let νkl be a nonnegative scalar representing how much we aim to reduce the value fx^k at the current iteration. Define the corresponding level parameter lk=fx^k-νkl. Since f(x)>0, lk>0. Then the level set associated with fˇk(·) and lk is given by
(15)Xk={x∈Rn∣fˇk(x)≤lk}.
We obtain the search direction by solving the following convex quadratic subproblem, parameterized in the nonnegative scalar u, where the first two constraints ensure d∈Sf and the last constraint represents the idea of level bundle method:
(16)QP(u){zu=min⁡uv+12∥d∥2s.t.v≥(gxiG)Td-αi-2η,i∈Ik+,v≤(gxiG)Td-αi-2η,i∈Ik-,v≤lk.
Observe that zu≤0 since (v,d)=(0,0) is feasible. We have consequently that the optimal value v cannot be positive.The dual problem ofQP(u) can be written in the form
(17)DP(u){min⁡12∥G+λ-G-μ∥2+α+Tλ-α-Tμ+ξlk+2η(eTλ-eTμ)s.t.λ,μ,ξ≥0,eTλ-eTμ-ξ=u,
where G+ and G- are matrices whose columns are, respectively, the vectors gxiG, i∈Ik+ and gxiG, i∈Ik- and α+ and α- are vectors whose components are αi, i∈Ik+ and αi, i∈Ik-, respectively. λ and μ are the vectors with components λi, i∈Ik+, μi, i∈Ik-, and e=(1,1,…,1)T, ξ∈R+. The primal optimal solution (vu,du) is related to the dual optimal solution (λu,μu,ξu) by the following formulae:
(18)du=-G+λu+G-μu,(19)vu=-1u[∥du∥2+(α++2ηe)Tλu-(α-+2ηe)Tμu+ξulk].Before giving a description of the algorithm, we state some simple properties ofQP(u).Lemma 1.
Let0<u2<u1; then the following conclusions hold:(i)
zu1≤zu2;(ii)
vu1≤vu2;(iii)
∥du1∥≥∥du2∥.Proof.
We omit the proof since the conclusions can be obtained by imitating the proof of Lemma 2.1 [3].Lemma 2.
For anyu>0, the following conclusions hold:(i)
∥du∥≤2u∥gx^kG∥+2uη;(ii)
zu≥-(1/2)u2∥gx^kG∥2-2uη;(iii)
|vu|≥(1/2u)∥du∥2.Proof.
The conclusions can be obtained by imitating the proof of Lemma 2.2 [3].


## 3. Algorithm

In this section, we state the algorithm in full detail and give some comments on it.Algorithm 3.
We have the following.
Step
0 (initialization). The following global parameters are to be set: the stopping tolerances δ>0, TolΔ≥0, the proximity measure ɛ≥0, the descent parameter m∈(0,1), the cut parameter ρ∈(m,1), the reduction parameter r∈(0,1), the increase parameter R>1, and the level measure parameter ml∈(0,1). Choose a starting point x0∈Rn; set x^0=x0; the oracle provides fx0∈R and gx0G∈Rn satisfying Assumption (4). The initial bundle is made up of just one element (x0,fx0,gx0G,0,0) so that I0- is empty, while I0+ is a singleton. Since f(x)>0, a lower bound f0low for finf⁡=min⁡{f(x)∣x∈Rn} is available; set ν0l=(1-ml)(fx^0-f0low). Set the iteration counter k=0.
Step
1 (first stopping test). If ∥gx^kG∥≤δ, then terminate.
Step
2 (second stopping test). Set Δk=fx^k-fklow. If Δk≤TolΔ, then stop.
Step
3 (level feasibility checking). Set the level parameter lk=fx^k-νkl. If the level set Xk defined by (15) is detected to be empty, then set fklow=lk, νkl=(1-ml)(fx^k-fklow) and go back to Step 2. Otherwise set umin⁡k=rɛ/2∥gx^kG∥,  umax⁡k=Rumin⁡k, and θ(k)=rδumin⁡k.
Step
4 (direction finding). Find the solution (du^k,vu^k) of QP(u^) for increasing value of u, such that
(20)fx^k+du^>fx^k+mvu^,
where u^ equals the minimum value of u∈[umin⁡k,umax⁡k] if such u does exist; otherwise set u^=umax⁡k.
Step
5 (bundle updating). Set
(21)Ik+=Ik+∖{i∈Ik+∣ai>ɛ},Ik-=Ik-∖{i∈Ik-∣ai>ɛ}.
Calculate
(22)g*=argmin{∥g∥∣g∈conv{gxiG∣i∈Ik+}}.
If ∥g*∥≤δ, then terminate.
Else setumax⁡k=umax⁡k-r(umax⁡k-umin⁡k); go to Step 4.
Step
6 (trial point calculating). Set xk+1=x^k+du^k, calculate fxk+1, gxk+1G∈∂ηxk+1gGf(xx+1), and set αk+1=fx^k-fxk+1+(gxk+1G)Tdu^k.
Step
7 (index insertion). (a) If αk+1<-2η and ∥du^k∥>ɛ, then insert the element (xk+1,fxk+1,gxk+1G,αk+1,∥du^k∥) into the bundle for an appropriate value of i∈Ik- and set u^=u^-r(u^-umin⁡k).
(b) Else, if(gxk+1G)Tdu^k≥ρvu^k-2η, then insert the element (xk+1,fxk+1,gxk+1G,max⁡{αk+1,-2η},∥du^k∥) into the bundle for an appropriate value of i∈Ik+.
(c) Else find a scalart∈(0,1) such that g(t)∈∂ηx^k+tdu^kgGf(x^k+tdu^k) satisfies the condition g(t)Tdu^k≥ρvu^k-2η and insert the element (x^k+tdu^k,fx^k+tdu^k,g(t),max⁡{-2η,αt},t∥du^k∥) into the bundle for an appropriate value of i∈Ik+, where αt=fx^k-fx^k+tdu^k+tg(t)Tdu^k.Step
8 (descent test). If ∥du^k∥≤θ, go to Step 5. Choose fk+1low∈[fklow,finf⁡].If(23)fxk+1≤fx^k+mvu^k,
set the new stability center x^k+1=xk+1, νk+1l=(1-ml)(fx^k+1-fk+1low), set k=k+1, and go to Step 1 (serious step).Otherwise setx^k+1=x^k, νk+1l=(1-ml)(fx^k+1-fk+1low), set k=k+1, and go to Step 9 (null step).Step
9 (resolving QU(u) or DP(u)). Solve QP(u) or, equivalently, DP(u), to obtain the primal and dual optimal solutions (vu^,du^) and (λu^,μu^,ξu^) and go to Step 6.That is the end of the algorithm.A few comments on the algorithm are in the following order.(a) Step 1 is justified by the optimality estimate.(b) Step 2 is another stopping criterion.Xk=∅ means that lk≤fˇk(x)≤f(x)+β, ∀x∈Rn, and since the update sets fklow=lk, it holds that fklow≤finf⁡+β for all k. If Algorithm 3 stops at Step 2, we have that
(24)TolΔ≥fx^k-fklow≥fx^k-finf⁡-β=f(x^k)-ηx^k-finf⁡-β≥f(x^k)-η-finf⁡-β,
which means that x^k is a (TolΔ+η+β)-approximate solution to problem (1). If at Step 2 the rule lk=fx^k-νkl is replaced by lk=+∞ for all k, Algorithm 3 becomes an approximate proximal bundle algorithm.(c) Step 4 may use the dual quadratic programming method of [10], which can solve efficiently sequences of related subproblems QP(u) with varying u. The construction of du^k at Step 4 may be discretized by repeatedly solving QP(u) for increasing values of u or by adopting techniques of the type described in [11].(d)du^k≤θ is never a consequence of the choice of too small u^. In fact, we note that if ∥gx^kG∥>δ, it holds that
(25)∥dumin⁡∥≤2umin⁡∥gx^kG∥+2umin⁡η=2θ(∥gx^kG∥+η)rδ.
The right-hand side of the above inequality is bigger than θ, so too small u^ cannot lead to du^k≤θ; therefore we need to increase the value of u.(e)We remark that the insertion of a bundle index intoIk+ or Ik- at Step 7 is not simply based on the sign of αi.(f) The level constraintfˇk(x)≤lk provides an additional useful stopping test based on a certain optimality gap, something not present in cutting plane methods. It should be noted that this additional stopping test is useful, as usual proximal bundle methods sometimes “take time” to accumulate enough information to recognize that an acceptable approximate solution has been already computed.(g) To keep the size of problem (16) manageable, the number of elements in bundle should be kept bounded, without impairing convergence. For this, the usual aggregation techniques of proximal bundle methods can be employed here. Specifically, the model can be composed of as few as only two cutting planes, corresponding to the new linearization and the aggregate linearization.


## 4. Convergence Analysis

Convergence analysis of Algorithm3 has to account for all the following cases:
(26)thelevelsetsXkareemptyforinfinitelymanytimes;(27)infinitelymanydescentstepsaregenerated;(28)finitelymanydescentstepsaregenerated.
For the first case (26), if the stopping tolerance TolΔ is positive, then the method terminates with an approximate solution in a finite number of iterations.Lemma 4.
Suppose the level setsXk are empty for infinitely many times; then Δk→0:
(29)lim⁡k→∞fx^k≤finf⁡+β.
And every cluster point of the sequence {x^k} (if any exists) is a (η+β)-approximate solution to problem (1).Proof.
Sincefklow>-∞, Δk<+∞. Also, by Steps 3 and 8, νkl≤(1-ml)Δk; thus
(30)fx^k-lk=fx^k-(fx^k-νkl)=νkl≤(1-ml)Δk,
which means that if Xk is empty at iteration k, then the update decreases the optimality gap Δk by a factor of at least (1-ml). Hence if this happens infinitely many times, we have Δk→0 as k→∞. Moreover, we have Δk=fx^k-fklow≥fx^k-finf⁡-β. As {fx^k} is decreasing and bounded below (fx^k=f(x^k)-ηx^k>f(x^k)-η>finf⁡-η>-∞), we conclude that
(31)lim⁡k→∞fx^k-finf⁡-β≤lim⁡k→∞fx^k-fklow=lim⁡k→∞Δk=0,
which gives (29). Let x~ be any cluster point of {x^k}, and let {x^k(j)} be a subsequence converging to x~ as j→∞. Then
(32)finf⁡+β≥lim⁡j→∞fx^k(j)=lim⁡j→∞(f(x^k(j))-ηx^k(j))≥f(x~)-η,
which establishes the last conclusion.From now on, we consider the case whenXk≠∅ for k large enough. Without loss of generality, we can simply assume Xk≠∅ for all k. For cases (27) and (28) we make the following assumptions:(A1)
the setS0={x∈Rn∣fx≤fx0} is compact;(A2)
for anyd∈Rn, the directional directive f′(x;d) of f at x exists and
(33)f′(x;d)=lim⁡t↓0g(t)Td,
where g(t)∈∂ηx+tdgGf(x+td).Remark 5.
Assumption(A2) is a looser condition than the one emerging in [3], where the condition that f is weakly semismooth is required.Next we introduce Lemma6 to see what will happen if no really new stability center is generated; that is, there exists the last stability center and from then on only null steps are generated.Lemma 6.
Supposex^k is the last stability center followed by a null step sequence (du^j,vu^j) such that ∥du^j∥>θ and
(34)fx^k+du^j-fx^k>mvu^j
with the algorithm looping between Steps 6 and 9. Then the following conclusions hold.(i)
There exists an indexj¯ such that, for each j≥j¯, every new bundle index is inserted into Ik+ and u^ remains unchanged.(ii)
Step 7(c) is well defined.(iii)
Whenever a new bundle index is inserted intoIk+, the condition (gjG)Tdu^j≥ρvu^j-2η holds, where gjG is the subgradient corresponding to the new bundle element.Proof.
(i) The conclusion can be obtained by noting that no bundle index can be inserted intoIk- as soon as u^ falls below the threshold ɛ/(2∥gx^k∥+2η).
(ii) Since the sufficient decrease condition (23) is not satisfied, it follows that
(35)ρvu^j<mvu^j<fx^k+du^j-fx^k.
According to the inexact data in Assumption (4), fx^k+du^j-fx^k≤f(x^k+du^j)-f(x^k)+2η, by mean value theorem there exists a scalar tj¯∈(0,1) such that
(36)ρvu^j<f′(x^k+t¯jdu^j;du^kj)+2η.
Thus the conclusion follows from Assumption (A2).
(iii) Observe that the condition(gjG)Tdu^j≥ρvu^j-2η is ensured either by construction or by the fact that
(37)(gjG)Tdu^j+2η≥(gjG)Tdu^j-αu^j=fx^k+du^j-fx^k>mvu^j>ρvu^j,
whenever αu^j≥-2η.Now we consider the case of infinitely many descent steps; we prove that either an approximate solution is achieved at Step 5 or we obtain a really new stability centerx^k+1≠x^k.Lemma 7.
For Algorithm3, if infinitely many descent steps are generated one either obtains an approximate solution at Step 5 or one executes descent step at Step 8.Proof.
Firstly we prove that the algorithm cannot pass through Step 5 for infinitely many times. Just like the result of Lemma 4.2 in [3], we can obtain that the indices of the new bundle elements are inserted into Ik+ and are never removed. Moreover, when a passage at Step 5 occurs all the elements with index i∈Ik- are removed. Taking into account (18) and the constraint eTλ-eTμ-ξ=u^ in the dual problem DP(u^), there exists an index j¯ such that, for all j≥j¯, du^j can be expressed in the form (say |Ik+|=m)
(38)du^j=-G+λj=-∑i∈Ik+‍λigxiG=-∑i∈Ik+‍λi(λ1∑i∈Ik+‍λigx1G+⋯+λm∑i∈Ik+‍λigxmG)=-(u^+ξ)g(j),
where g(j)∈conv{gxiG∣i∈Ik+}. But since ∥du^j∥≤θ and ∥g*(j)∥>δ, we have
(39)θ≥∥du^j∥=|u^+ξ|∥gj∥≥umin⁡∥g*(j)∥>θrδδ>θ,
which leads to a contradiction.
Next we show that it is impossible to havedu^j>θ for infinitely many times and the descent condition (23) is not satisfied with the algorithm looping between Steps 6 and 9. Indexing by j∈J the jth passage through such a loop, we observe that, by Lemma 6 (i), there exists an index j¯ such that, for every j≥j¯, the sequence {zu^j} is nondecreasing, bounded, and hence convergent. Moreover, {du^j} is bounded; it admits a convergent subsequence, say {du^j}j∈J′⊂J. The above consideration implies also that {vu^j}j∈J′⊂J is convergent to a nonpositive limit, say v¯. Next, we can imitate the proof of Lemma 4.2 in [3] to show that v¯=0, which, by Lemma 2 (iii), contradicts the fact that ∥du^j∥>θ.Finally we show after a finite number of descent steps that Algorithm3 stops at a point satisfying the condition of some kind of approximate solution.Theorem 8.
For anyɛ>0 and δ>0, Algorithm 3 stops in a finite number of iterations at a point satisfying the approximate stationarity condition
(40)∥g*∥≤δ
with g*∈conv{∂ηygGf(y)∣∥y-x^k∥≤ɛ}.Proof.
Suppose that the conclusion does not hold. It follows from Lemma7 that for infinitely many times the descent condition (23) is satisfied. Let x^k be the stability center at the kth passage; then ∥du^k∥>θ and
(41)fx^k+1≤fx^k+mvu^k,fx^k+1-fx^0≤m∑i=0k‍vu^i.
Since umin⁡k=rɛ/2∥gx^k∥ and θ(k)=rδumin⁡k, so θ(k)≥r2ɛδ/2L0, where L0 is the Lipschitz constant of f on S0. It follows from ∥du^k∥>θ(k)≥r2ɛδ/2L0 that ∥du^j∥ is bounded away from zero. Then from Lemma 2(iii), vu^j is bounded away from zero as well. Therefore by passing to the limit we obtain
(42)lim⁡k→∞fx^k+1-fx^0≤-∞.
Since fx^k+1=f(x^k+1)-ηx^k+1≤f(x^k+1)+η, fx^0=f(x^0)-ηx^0≤f(x^0)+η, we have lim⁡k→∞f(x^k+1)=-∞, which contradicts the fact that the value of f at x∈Rn is positive.


## 5. Conclusions

In this paper, we propose a new algorithm for nonsmooth nonconvex minimization by employing the approximate values of the objective function and its subgradient. It combines the cutting plane method, level bundle method, and the idea of proximal control. The aim is to take advantage of good properties of all above-mentioned methods, thus speeding up the optimization process. In addition, the algorithm provides a useful stopping test based on the optimality gap, something not present in the proximal bundle methods. Compared with bundle methods for nonsmooth nonconvex functions, the amount of the shifting of affine pieces appears somehow arbitrary, but in our paper, the use of downward shifting is restricted to some particular cases.



---

*Source: 192893-2014-04-14.xml*