# An Approximate Redistributed Proximal Bundle Method with Inexact Data for Minimizing Nonsmooth Nonconvex Functions

Authors: Jie Shen; Xiao-Qian Liu; Fang-Fang Guo; Shu-Xin Wang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We describe an extension of the redistributed technique form classical proximal bundle method to the inexact situation for minimizing nonsmooth nonconvex functions. The cutting-planes model we construct is not the approximation to the whole nonconvex function, but to the local convexification of the approximate objective function, and this kind of local convexification is modified dynamically in order to always yield nonnegative linearization errors. Since we only employ the approximate function values and approximate subgradients, theoretical convergence analysis shows that an approximate stationary point or some double approximate stationary point can be obtained under some mild conditions.


---

## Body

## 1. Introduction and Motivation

Consider the following unconstrained nonsmooth nonconvex optimization problem:(1)
min
⁡
f
x
s.t.
x
∈
R
m
,where f is a function from R
m
→
R. Nonsmooth optimization problems (NSO) arise from many fields of applications. There exist several approaches to solve these kinds of problems; see [1–4]. Bundle methods [5] are based on the cutting-planes methods, first described in [6, 7], where the convexity of the objective function is the fundamental assumption. If the objective function f is convex, tangent lines are cutting planes supporting the epigraph of f and the linearization errors are always nonnegative, and the model functions usually defined by the maximum of tangent lines are lower approximations to the objective function. However, in the nonconvex case the linearization errors can be negative, and the corresponding model function does not stay below f and may even cut off a region containing a minimizer. Very little systematic research has been performed on extending convex bundle methods to nonconvex cases. The bundle methods for nonconvex functions [8–12] are of proximal type, which were developed in the 90’s; see [13]. They still use subgradients locality measures to redefine negative linearization errors, and primal information, corresponding to function values, is again ignored.Note that in some cases computing the exact function value is not easy. The assumptions for using approximate subgradients and approximate values of the function are realistic, for instance, the Lagrangian relaxation problem: iff is a max-type function of the form f
(
y
)
=
s
u
p
{
F
z
(
y
)
∣
z
∈
Z
}, where each F
z
(
y
) is convex and Z is an infinite set, then it may be impossible to calculate f
(
y
) since f itself is defined by a minimization problem involving another function F. However, we may still consider two cases. In the first case, for each positive ɛ
>
0 one can find an element z
y
∈
Z satisfying F
z
y
(
y
)
≥
f
(
y
)
-
ɛ; in the second case, this may be possible only for some fixed (any possibly unknown) ɛ
<
∞. In both cases we may set f
¯
y
=
F
z
y
(
y
)
≥
f
(
y
)
-
ɛ. Besides that, the study of approximate subgradients of convex functions is deserved since in some cases a subgradient ξ
(
x
)
∈
∂
f
(
x
) is expensive to compute. But if we know an already computed subgradient ξ
(
x
¯
)
∈
∂
f
(
x
¯
), where x
¯ is near to x, then we have ξ
(
x
¯
)
∈
∂
ɛ
f
(
x
) because (2)
f
x
+
ξ
x
¯
T
z
-
x
=
f
x
¯
+
ξ
x
¯
T
z
-
x
¯
+
ɛ
≤
f
z
+
ɛ
,
∀
z
∈
R
m
,where ɛ
=
f
(
x
)
-
f
(
x
¯
)
-
ξ
(
x
¯
)
T
(
x
-
x
¯
)
≥
0. For more details and papers involving the approximate function values and subgradients, we refer to [14–16] and the references therein.In our work, we attempt to explore the possibility of using the approximate function values and approximate subgradients off instead of the exact ones for solving problem (1). From the point of view of primal problem, by separating the traditional prox-parameter into two parts, local convexification parameter and new model prox-parameter, and employing the inexact information of the objective function, we construct a cutting-planes model which is the approximation to the local convexification function, and the iterate points are obtained approximately by computing its double approximate proximal points. The cutting-planes model is special in the sense that it no longer approximates the objective function, but rather certain local convexification, centered at the proximal center.This paper is organized as follows: in Section2, some preliminary results and assumptions required in our paper are provided. In Section 3 we pay more attention to the primal pattern of (1) instead of the dual insight and the cutting-planes model of local approximation to the objective function is constructed in this part. In Section 4, the concrete approximate redistributed algorithm for solving (1) is presented. Convergence results are examined and discussed in Section 5, and the iterate points generated by the proposed algorithm converge to an approximate (double approximate) stationary point of the objective function. In the last section, some conclusions are given.


## 2. Preliminaries and Assumptions

In this part, we first present some basic definitions and results [17].(i)
The regular subdifferential off at x
¯ is defined by (3)
∂
^
f
x
¯
=
g
∈
R
m
∣
l
i
m
x
→
x
¯
inf
x
≠
x
¯
⁡
f
x
-
f
x
¯
-
g
,
x
-
x
¯
x
-
x
¯
≥
0
.
(ii)
The limiting subdifferential off at x
¯ is defined by (4)
∂
f
x
¯
=
lim
x
→
x
¯
⁡
sup
f
x
→
f
x
¯
⁡
∂
^
f
x
.If f is finite at x
¯, ∂
^
f
(
x
¯
) and ∂
f
(
x
¯
) are closed and ∂
^
f
(
x
¯
) is convex.(iii)
For givenɛ
>
0, ɛ-limiting subdifferential of f at x
¯ is defined by (5)
∂
ɛ
f
x
¯
=
conv
⁡
∂
f
y
∣
y
-
x
¯
≤
ɛ
.We call elements of this approximate subdifferential approximate subgradients. And iff is finite at x
¯, ∂
ɛ
f
(
x
¯
) is convex and closed.(iv)
We sayf is prox-bounded if there exists R
≥
0 such that f
+
(
R
/
2
)
·
2 is bounded below. The corresponding threshold is the smallest r
ρ
b
≥
0 such that f
+
(
R
/
2
)
·
2 is bounded below for all R
>
r
ρ
b.
(v)
The functionf is lower-C
2 on an open set O if f is finite on O and for any x in O there exists a threshold r
l
c
2
>
0 such that f
+
(
r
/
2
)
·
2 is convex on an open neighbourhood O
′ of x for all r
>
r
l
c
2.Next we give some assumptions needed in our paper.Assumption 1.
For fixed accuracy tolerancesε
f
≥
0, ε
g
≥
0, for each x
∈
R
m, the oracle can provide an approximate function value f
~
x
∈
[
f
(
x
)
-
ε
f
,
f
(
x
)
+
ε
g
] and an approximate subgradient g
ɛ
x of f at x, where ɛ
=
ε
f
+
ε
g.Assumption 2.
Givenx
0
∈
R
m and M
0
>
0, there exist an open bounded set O and a function H such that L
0
=
{
x
∈
R
m
∣
f
~
x
≤
f
~
x
0
+
M
0
}
⊂
O, and H is lower-C
2 on O satisfying H
≡
f
~ on L
0.Lemma 3.
For a functionf satisfying Assumptions 1 and 2, the following conclusions hold:(a)
The approximate level setL
0 is nonempty and compact.
(b)
The approximate functionf
~ is bounded below and prox-bounded with threshold r
ρ
b
=
0.
(c)
There existsρ
i
d
>
0 such that, for any ρ
≥
ρ
i
d and given y
∈
L
0, the function f
+
(
ρ
/
2
)
·
-
y
2 is convex on L
0.
(d)
The approximate functionf
~ is Lipschitz continuous on L
0.Proof.
SinceH is the lower-C
2 function defined in by Assumption 2 which agrees with f
~ on L
0, H is continuous and finite valued on the open set O, which contains L
0. Thus L
0 is closed. By the fact that L
0 is bounded from the boundedness of O, (a) is proved. For item (b), without loss of generality, we assume that f
~ and H are the same function. Since f
~ is finite and continuous on the approximate compact level set L
0, this implies f
~ is bounded below. Any function which is bounded below is prox-bounded with threshold r
ρ
d
=
0. Item (c) can be obtained by [17]. The last item (d) is obvious by noting that all lower-C
2 functions are locally Lipschitz continuous.Define the approximate proximal point mapping(6)
p
~
R
f
~
x
=
arg
⁡
min
y
∈
R
m
⁡
f
~
y
+
R
2
y
-
x
2
,
x
∈
L
0
,which is single-valued and Lipschitz continuous on L
0, provided R is sufficiently large. By imitating the conclusion in [18] and the optimality condition, we define a new kind of approximate stationary point of the objective function.Definition 4.
One callsx
∗
∈
L
0 an approximate stationary point of f if x
∗
=
p
~
R
f
~
(
x
∗
), where p
~
R
f
~
(
x
∗
) is defined by (6), written with x replaced by x
∗.Note thatR is sufficiently large meaning that R
>
ρ
i
d, where ρ
i
d is the value in item (c) in Lemma 3 and(7)
p
~
R
f
~
x
=
p
~
R
-
ρ
i
d
f
~
+
ρ
i
d
2
·
-
x
2
x
.The above relation with the local convexification property plays a fundamental role in the development of our algorithm if we have already known the ideal proximal threshold ρ
i
d.


## 3. Construction of the Model

For a convex functionf, the exact linearization error of f at x
^
k is defined by(8)
e
i
k
=
f
x
^
k
-
f
x
i
+
g
i
,
x
^
k
-
x
i
,where g
i
∈
∂
f
(
x
i
) and x
^
k is the current stability center. Obviously we have e
i
k
≥
0, and the reformulated bundle data consists of {
x
^
k
,
f
(
x
^
k
)
,
g
k
∈
∂
f
(
x
^
k
)
} and the approximate subgradients ∪
i
∈
I
n
{
(
e
i
k
,
g
i
∈
∂
e
i
k
f
(
x
^
k
)
)
}. In our method, at any iteration, bundle method keeps memory of the iterative process in a bundle of inexact information:(9)
⋃
i
∈
I
n
x
i
,
f
~
i
,
g
ɛ
i
∈
∂
ɛ
f
x
i
,where I
n
⊆
{
0,1
,
2
,
…
,
n
}, f
~
i
∈
[
f
(
x
i
)
-
ε
f
,
f
(
x
i
)
+
ε
g
], and f
~
x
^
k
(
n
) is the best approximate value obtained until iteration n, evaluated at the serious step k, corresponding to some past iterate i
k. For nonconvex function f, we work with augmented functions(10)
f
~
η
n
x
^
k
≔
f
~
+
η
n
2
·
-
x
^
k
2
.We consider an augmented bundle of inexact information: ∪
i
∈
I
n
{
(
e
~
i
k
,
d
i
k
,
Δ
i
k
,
g
ɛ
i
)
}, where(11)
e
~
i
k
=
f
~
x
^
k
-
f
~
i
+
g
ɛ
i
,
x
^
k
-
x
i
,
d
i
k
=
x
i
-
x
^
k
2
2
,
Δ
i
k
=
x
i
-
x
^
k
,
g
ɛ
i
∈
∂
ɛ
f
x
i
.Note that the following relation holds:(12)
p
~
R
f
~
x
^
=
p
~
μ
f
~
η
x
^
x
^
,where f
~
η
x
^
=
f
~
+
(
η
/
2
)
·
-
x
^
2, R
=
μ
+
η, and η and μ are called the convexification parameter and model prox-parameter, respectively. We use the past information in bundle to construct a cutting-planes model of the function f
~
η
x
^: (13)
ϕ
~
y
≔
max
i
⁡
f
~
i
+
η
2
x
i
-
x
^
2
+
g
ɛ
i
+
η
x
i
-
x
^
,
y
-
x
i
-
2
ɛ
.An equivalent expression, written with all the iteration indices, is the following:(14)
ϕ
~
n
y
=
f
~
x
^
k
+
max
i
∈
I
n
⁡
-
e
~
i
k
+
η
n
d
i
k
+
2
ɛ
+
g
ɛ
i
+
η
n
Δ
i
k
,
y
-
x
^
k
.The next candidate point is chosen as x
n
+
1
=
p
~
μ
n
ϕ
~
n
(
x
^
k
). The corresponding optimality condition is that there exists α
n
∈
S
n such that(15)
x
n
+
1
=
x
^
k
-
1
μ
n
g
η
n
,
ɛ
-
n
,
g
η
n
,
ɛ
-
n
=
∑
i
∈
I
n
α
i
n
g
ɛ
i
+
η
n
Δ
i
k
∈
∂
ϕ
~
n
x
n
+
1
,where S
n denotes the unit simplex in R
I
n. Denote J
n
a
c
t
:
=
{
i
∈
I
n
∣
α
i
n
>
0
i
n
(
15
)
}. g
η
n
,
ɛ
-
n is called the aggregate approximate subgradient, and the corresponding aggregate bundle element is the quadruplet:(16)
e
~
-
n
k
,
d
-
n
k
,
Δ
-
n
k
,
g
ɛ
-
n
≔
∑
i
∈
I
n
e
~
i
k
,
d
i
k
,
Δ
i
k
,
g
ɛ
i
=
∑
i
∈
J
n
a
c
t
e
~
i
k
,
d
i
k
,
Δ
i
k
,
g
ɛ
i
.Note that for l
=
-
n and all l
∈
J
n
a
c
t we have(17)
ϕ
~
n
x
n
+
1
=
f
~
x
^
k
-
e
~
l
k
+
η
n
d
l
k
+
2
ɛ
+
g
ɛ
l
+
η
n
Δ
l
k
,
x
n
+
1
-
x
^
k
,
(18)
g
η
n
,
ɛ
-
n
=
g
ɛ
-
n
+
η
n
Δ
-
n
k
=
μ
n
x
^
k
-
x
n
+
1
.For all i
∈
I
n, e
~
i
k
+
1, d
i
k
+
1, and Δ
i
k
+
1 can be updated according to the following formula:(19)
e
~
i
k
+
1
=
e
~
i
k
+
f
~
x
^
k
+
1
-
f
~
x
^
k
-
g
ɛ
i
,
x
^
k
+
1
-
x
^
k
,
d
i
k
+
1
=
d
i
k
+
x
^
k
+
1
-
x
^
k
2
2
-
Δ
i
k
,
x
^
k
+
1
-
x
^
k
,
Δ
i
k
+
1
=
Δ
i
k
+
x
^
k
-
x
^
k
+
1
.In classical bundle method with inexact information for convex functions, the bundle consists of the pair (
e
~
i
k
,
g
ɛ
i
) for which g
ɛ
i
∈
∂
2
ɛ
+
e
~
i
k
f
(
x
^
k
) holds whenever 2
ɛ
+
e
~
i
k
≥
0, which can be seen by noting that g
ɛ
i
∈
∂
f
(
x
i
), the definition of e
~
k
i, and (20)
f
y
≥
f
x
i
+
g
ɛ
i
,
y
-
x
i
-
ɛ
=
f
x
^
k
+
g
ɛ
i
,
y
-
x
^
k
-
f
x
^
k
+
f
x
i
+
g
ɛ
i
,
x
^
k
-
x
i
-
ɛ
≥
f
x
^
k
+
g
ɛ
i
,
y
-
x
^
k
-
f
~
x
^
k
-
ε
f
+
f
~
x
i
-
ε
g
+
g
ɛ
i
,
x
^
k
-
x
i
-
ɛ
=
f
x
^
k
+
g
ɛ
i
,
y
-
x
^
k
-
e
~
i
k
-
2
ɛ
.
∀
y
∈
R
m
.For our method, this pair is replaced by a quadruplet (
e
~
i
k
,
d
i
k
,
Δ
i
k
,
g
ɛ
i
) for which the relation(21)
g
ɛ
i
+
η
n
Δ
i
k
∈
∂
e
~
i
k
+
η
n
d
i
k
+
2
ɛ
ϕ
~
n
x
^
k
,
whenever
e
~
i
k
+
η
n
d
i
k
+
2
ɛ
≥
0
,
∀
i
∈
I
n
,holds, since for all i
∈
I
n, whenever e
~
i
k
+
η
n
d
i
k
+
2
ɛ
≥
0, we have (22)
ϕ
~
n
y
≥
f
~
x
^
k
-
e
~
i
k
+
η
n
d
i
k
+
2
ɛ
+
g
ɛ
i
+
η
n
Δ
i
k
,
y
-
x
^
k
≥
ϕ
~
n
x
^
k
-
e
~
i
k
+
η
n
d
i
k
+
2
ɛ
+
g
ɛ
i
+
η
n
Δ
i
k
,
y
-
x
^
k
.We want to make the parameter η
n asymptotically estimate the ideal convexity threshold ρ
i
d, and when η
n is sufficiently large, f
~
+
(
η
n
/
2
)
·
-
x
^
k
2 is a convex function. As a result, the model function ϕ
~
n becomes eventually a lower approximation to a locally convex function f
~
ρ
i
d
x
^
k. Set(23)
η
¯
n
≔
max
i
∈
I
n
,
d
i
k
n
>
0
⁡
-
e
~
i
k
n
+
2
ɛ
d
i
k
n
,and clearly e
~
i
k
+
η
d
i
k
+
2
ɛ
≥
0 for all i
∈
I
n whenever η
≥
η
¯
n.Remark 5.
By comparing withη
~
n [19] and η
n
m
i
n [18], we find that η
~
n
≥
η
n
m
i
n
≥
η
¯
n, which means that the domain of η that ensures that the nonnegativeness of the linearization errors is enlarged.


## 4. Algorithm

Algorithm 6 (approximate redistributed proximal bundle method).
Consider  the following steps.
Step
1 (initialization). Choose an initial point x
0, two parameters M
0
>
0, R
0
>
0, one stopping tolerance T
O
L
s
t
o
p
≥
0, an Armijo-like parameter m
¯
∈
(
0,1
), and a convexification growth parameter τ
>
1. Set n
=
0, k
=
k
(
n
)
=
0, i
0
=
1, I
0
=
{
0
}, and x
0
=
x
^
0. Compute f
~
x
0
∈
[
f
(
x
0
)
-
ε
f
,
f
(
x
0
)
+
ε
g
], g
ɛ
0
∈
∂
ɛ
f
(
x
0
), and the additional bundle information (
e
~
0
0
,
d
0
0
,
Δ
0
0
)
:
=
(
0,0
,
0
). Choose (
μ
0
,
η
0
)
=
(
R
0
,
0
).
Step
2 (computation of trail point). Having the current serious step x
^
k, the bundle {
(
e
~
i
k
,
d
i
k
,
Δ
i
k
,
g
ɛ
i
)
}
i
∈
I
n, and the prox-parameter distribution (
μ
n
,
η
n
) with η
n
≤
R
n, μ
n
=
R
n
-
η
n, define the convex piecewise linear approximate model function ϕ
~
n from (14). Compute (24)
x
n
+
1
=
p
~
μ
n
ϕ
~
n
x
^
k
.The optimal simplicial multipliers α
n from (15) and the aggregate quadruplet from (16) are available. Define the predicted decrease (25)
δ
n
+
1
=
f
~
x
^
k
+
η
n
2
x
n
+
1
-
x
^
k
2
+
2
ɛ
-
ϕ
~
n
x
n
+
1
.
Step
3 (bundle management). Compute f
~
x
n
+
1 and g
ɛ
n
+
1
∈
∂
ɛ
f
(
x
n
+
1
). Set (26)
Δ
n
+
1
k
≔
x
n
+
1
-
x
^
k
,
d
n
+
1
k
≔
x
n
+
1
-
x
^
k
2
2
,
e
~
n
+
1
k
≔
f
~
x
^
k
-
f
~
x
n
+
1
+
g
ɛ
n
+
1
,
x
n
+
1
-
x
^
k
.Choose a new index set I
n
+
1 satisfying (27)
I
n
+
1
⊇
n
+
1
,
i
k
and  either
I
n
+
1
⊇
J
n
a
c
t
≔
i
∈
I
n
∣
α
i
n
>
0
,
or
I
n
+
1
⊇
-
n
.
Step
4 (descent test). If(28)
f
~
x
n
+
1
≤
f
~
x
^
k
-
m
¯
δ
n
+
1
-
2
ɛ
,declare a serious step: set k
(
n
+
1
)
=
k
+
1, i
k
+
1
=
n
+
1, and x
^
k
+
1
=
x
n
+
1, and update bundle elements according to (19).
Otherwise, declare a null step: setk
(
n
+
1
)
=
k
(
n
).
Step
5 (update of local convexification parameter). Set(29)
η
n
+
1
≔
η
n
,
i
f
η
¯
n
+
1
≤
η
n
;
η
n
+
1
≔
τ
η
¯
n
+
1
,
i
f
η
¯
n
+
1
>
η
n
,
R
n
=
μ
n
+
η
n
+
1
,
i
f
η
¯
n
+
1
>
η
n
,where η
¯
n
+
1 is given in (23), written with n replaced by n
+
1.
Step
6 (update of model prox-parameter). If f
~
x
n
+
1
>
f
~
x
^
k
+
M
0, restart the algorithm by setting (30)
η
0
≔
η
n
,
μ
0
≔
τ
μ
n
,
R
0
≔
η
0
+
μ
0
,
x
0
≔
x
^
k
,
e
~
0
0
,
d
0
0
,
Δ
0
0
≔
0,0
,
0
,
k
0
≔
0
,
i
0
≔
0
,
I
0
≔
0
,
n
≔
0
,and loop to Step 2.
Otherwise go to Step 7.
Step
7 (stopping criterion). If δ
n
+
1
-
2
ɛ
≤
T
O
L
s
t
o
p, then stop with the message “Algorithm successfully terminated at x
n
+
1.”
Otherwise, in case of serious step increasek by 1. In all cases increase n by 1, and loop to Step 2.From the definition ofδ
n
+
1, we obtain its equivalent expression(31)
δ
n
+
1
=
e
~
-
n
k
+
η
n
d
-
n
k
+
4
ɛ
+
R
n
+
μ
n
2
x
n
+
1
-
x
^
k
2
≥
0
.Lemma 7.
Consider the sequence{
x
n
} generated by Algorithm 6. If f satisfies Assumptions 1 and 2, and I
n
⊇
{
i
k
}, there can be only a finite number of restarts in Step 6. Eventually the sequence {
x
n
} lies in L
0 and the sequence {
μ
n
} becomes constant.Proof.
Because the functionsϕ
~
n are convex, iterates x
n
+
1 are always well defined. By Lemma 3(d), the function f
~ is Lipschitz continuous on L
0 and let L be the Lipschitz constant. Take ɛ
¯
=
M
0
/
L, and then for any x
¯
∈
{
x
∈
R
m
∣
f
~
x
≤
f
~
x
0
}, the open ball B
ɛ
¯
(
x
¯
)
⊆
L
0. Note that (32)
p
~
μ
n
ϕ
~
n
x
^
k
=
arg
⁡
min
y
⁡
ϕ
~
n
y
+
μ
n
2
y
-
x
^
k
2
∈
y
∣
ϕ
~
n
y
+
μ
n
2
y
-
x
^
k
2
≤
ϕ
~
n
x
^
k
+
μ
n
2
x
^
k
-
x
^
k
2
.Since i
k
∈
I
n, we have g
ɛ
i
k
∈
∂
2
ɛ
ϕ
~
n
(
x
^
k
). From the convexity of ϕ
~
n, we know there exists L
¯
>
0 such that g
ɛ
i
k
≤
L
¯, and hence (33)
p
~
μ
n
ϕ
~
n
x
^
k
∈
y
∣
-
2
ɛ
+
ϕ
~
n
x
^
k
+
g
ɛ
i
k
,
y
-
x
^
k
+
μ
n
2
y
-
x
^
k
2
≤
ϕ
~
n
x
^
k
∈
y
∣
-
g
ɛ
i
k
·
y
-
x
^
k
+
μ
n
2
y
-
x
^
k
2
≤
2
ɛ
∈
y
∣
μ
n
2
y
-
x
^
k
2
≤
L
¯
y
-
x
^
k
+
2
ɛ
=
y
∣
y
-
x
^
k
≤
L
¯
μ
n
+
L
¯
2
μ
n
2
+
4
ɛ
μ
n
.During each Step 6, μ
n increases, eventually we will have L
¯
/
μ
n
+
L
¯
2
/
μ
n
2
+
4
ɛ
/
μ
n
≤
ɛ
¯, and it means that x
n
+
1
=
p
~
μ
n
ϕ
~
n
(
x
^
k
)
∈
B
ɛ
¯
(
x
^
k
). So f
~
x
n
+
1
-
f
~
x
^
k
≤
L
x
n
+
1
-
x
^
k
≤
L
ɛ
¯
=
M
0; that is, f
~
x
n
+
1
≤
f
~
x
^
k
+
M
0.


## 5. Convergence Results

Lemma 8.
For the functionϕ
~
n, the following conclusions hold:(a)
One always has(34)
ϕ
~
n
i
s
a
c
o
n
v
e
x
f
u
n
c
t
i
o
n
.
(b)
Ifη
n
≤
η
¯
n, which is defined in (23), then(35)
ϕ
~
n
x
^
k
≤
f
~
x
^
k
.
(c)
Ifx
n
+
1 is a null step, η
n
+
1
=
η
n, and either I
n
+
1
⊇
I
n
a
c
t or I
n
+
1
⊇
{
-
n
}, then for all w
∈
R
m
(36)
ϕ
~
n
+
1
w
≥
ϕ
~
n
x
n
+
1
+
μ
n
x
^
k
-
x
n
+
1
,
w
-
x
n
+
1
.
(d)
IfI
n
⊇
{
n
}, then, for some g
ɛ
n
∈
∂
ɛ
f
(
x
n
),(37)
ϕ
~
n
+
1
w
≥
f
~
x
n
+
η
n
d
n
k
+
g
ɛ
n
+
η
n
Δ
n
k
,
w
-
x
n
-
2
ɛ
.Proof.
(a) is clear sinceϕ
~
n is the maximum of a collection of affine functions.
(b) follows fromϕ
~
n
(
x
^
k
)
=
f
~
x
^
k
+
m
a
x
{
-
(
e
~
i
k
+
η
n
d
i
k
+
2
ɛ
)
} and (23) ensures e
~
i
k
+
η
n
d
i
k
+
2
ɛ
≥
0 for all i
∈
I
n.
For (c), suppose thatx
n
+
1 is a null step and η
n
+
1
=
η
n; we know(38)
ϕ
~
n
+
1
w
≥
f
~
x
^
k
-
e
~
l
k
-
η
n
d
l
k
-
2
ɛ
+
g
ɛ
l
+
η
n
Δ
l
k
,
w
-
x
^
k
,for all l
∈
I
n
+
1 and w
∈
R
m.  Equation (17) implies that (39)
f
~
x
^
k
-
e
~
l
k
+
η
n
d
l
k
+
2
ɛ
=
ϕ
~
n
x
n
+
1
-
g
ɛ
l
+
η
n
Δ
l
k
,
x
n
+
1
-
x
^
k
.Then we obtain in (38) for all l
∈
J
n
a
c
t and l
=
-
n
(40)
ϕ
~
n
+
1
w
≥
ϕ
~
n
x
n
+
1
+
g
ɛ
l
+
η
n
Δ
l
k
,
w
-
x
^
k
+
x
^
k
-
x
n
+
1
=
ϕ
~
n
x
n
+
1
+
g
ɛ
l
+
η
n
Δ
l
k
,
w
-
x
n
+
1
.If I
n
+
1
⊇
{
-
n
}, since g
ɛ
-
n
+
η
n
Δ
-
n
k
=
μ
n
(
x
^
k
-
x
n
+
1
), the relation above for l
=
-
n is just item (c). For the case I
n
+
1
⊇
J
n
a
c
t, we sum the above inequality by using the convex multipliers α
l
n and obtain the desired result.
For the last conclusion (d), sinceI
n
⊇
{
n
}, from the definition of ϕ
~
n and g
ɛ
n
∈
∂
ɛ
f
(
x
n
), for all w
∈
R
m,(41)
ϕ
~
n
+
1
w
≥
f
~
x
^
k
-
e
~
n
k
+
η
n
d
n
k
+
2
ɛ
+
g
ɛ
n
+
η
n
Δ
n
k
,
w
-
x
^
k
=
f
~
x
^
k
-
f
~
x
^
k
+
f
~
x
n
+
g
ɛ
n
,
x
^
k
-
x
n
-
η
n
d
n
k
-
2
ɛ
+
g
ɛ
n
+
η
n
Δ
n
k
,
w
-
x
^
k
=
f
~
x
n
+
g
ɛ
n
,
w
-
x
n
+
η
n
Δ
n
k
,
w
-
x
n
+
η
n
x
n
-
x
^
k
,
x
n
-
x
^
k
-
η
n
d
n
k
-
2
ɛ
=
f
~
x
n
+
g
ɛ
n
+
η
n
Δ
n
k
,
w
-
x
n
+
η
n
d
n
k
-
2
ɛ
.Lemma 9.
Consider the functionsϕ
~
n
(
y
) given by (14). If f satisfies Assumptions 1 and 2, there exists an iteration n
¯
>
0 such that all the parameters sequences stabilize; that is, (42)
η
n
=
η
¯
,
μ
n
=
μ
¯
,
R
n
=
η
¯
+
μ
¯
,
∀
n
≥
n
¯
.Therefore, condition  (3) in [19] is eventually satisfied. If, in addition, η
¯
≥
ρ
i
d, then(43)
ϕ
~
n
w
≤
f
~
w
+
η
¯
2
w
-
x
^
k
n
2
,
∀
w
∈
L
0
,
n
≥
n
¯
;that is, condition(6) in [19] holds.Proof.
By Lemma7 there are a finite number of restarts in Step 6. Once there are no more restarts, μ
n
=
μ
¯ and the update of η in Step 5 is nondecreasing. If the sequence {
η
n
} is not to be stabilized at some value η
¯, there must be an infinite subsequence of iterations at which η is increased by a factor of at least τ. In this case for some iteration η
n
c, the function f
~
+
(
η
n
c
/
2
)
·
-
x
^
k
(
n
c
)
2 is convex on L
0. And one will have e
~
i
k
+
η
n
c
d
i
k
+
2
ɛ
≥
0 for all i
∈
I
n
c. Hence,(44)
η
n
c
≥
max
i
∈
I
n
c
⁡
-
e
~
i
k
+
2
ɛ
d
i
k
=
η
¯
n
c
+
1
,and therefore, from that iteration on, the convexification parameter remains unchanged; that is, η
n
c
+
j
=
η
n
c for all j
≥
0, and this leads to a contradiction.
Whenη
¯
≥
ρ
i
d, the augmented function f
~
η
¯
x
^
k
(
n
) is convex on L
0, and hence the model function ϕ
~
n remains below the augmented function.If Algorithm6 stops at some iteration n with δ
n
+
1
=
2
ɛ and T
O
L
s
t
o
p
=
0, by the definition of δ
n
+
1, ϕ
~
n
(
x
n
+
1
)
=
f
~
x
^
k
+
(
η
n
/
2
)
x
n
+
1
-
x
^
k
2. Note that f
~
x
^
k
≥
ϕ
~
n
(
x
^
k
) and x
n
+
1
=
p
~
μ
n
ϕ
~
n
(
x
^
k
), and we see (45)
ϕ
~
n
x
n
+
1
+
μ
n
2
x
n
+
1
-
x
^
k
2
≤
ϕ
~
n
x
^
k
,
f
~
x
^
k
+
η
n
+
μ
n
2
x
n
+
1
-
x
^
k
2
≤
ϕ
~
n
x
^
k
,
f
~
x
^
k
+
R
n
2
x
n
+
1
-
x
^
k
2
≤
f
~
x
^
k
,which shows x
n
+
1
=
x
^
k; this implies that x
^
k
=
p
~
μ
n
ϕ
~
n
(
x
^
k
). Suppose that η
n is sufficiently large for f
~
+
(
η
n
/
2
)
·
-
x
^
k
2 to be convex on L
0, and this would imply that (46)
f
~
x
^
k
=
ϕ
~
n
x
^
k
≤
ϕ
~
n
w
+
μ
n
2
w
-
x
^
k
2
,
∀
w
∈
R
m
≤
f
~
w
+
η
n
2
w
-
x
^
k
2
+
μ
n
2
w
-
x
^
k
2
,
∀
w
∈
L
0
=
f
~
w
+
R
n
2
w
-
x
^
k
2
,
∀
w
∈
R
m
.In other words, x
^
k
=
p
~
R
n
f
~
(
x
^
k
); x
^
k is an approximate stationary point of f.Definition 10.
x
∗ is called ɛ-double approximate stationary point of f if (47)
f
~
x
∗
≤
f
~
w
+
R
¯
2
w
-
x
∗
2
+
ɛ
,
∀
w
∈
R
m
,where R
¯
=
μ
¯
+
η
¯, η
¯, and μ
¯ are the stabilized convexification parameter and model prox-parameter.Theorem 11.
Suppose thatT
O
L
s
t
o
p
=
0 and there is no termination. Let η
¯ be the stabilized value for the local convexification parameter sequence, as in Lemma 9, and η
¯
>
ρ
i
d. The following two mutually exclusive conclusions hold:(a)
There is a last serious stepx
^, followed by infinitely many null steps. Then x
n
+
1
→
x
^ and x
^ is an approximate stationary point of f.
(b)
There is an infinite number of serious steps. Then any accumulation point of the sequence{
x
^
k
} is ɛ-double approximate stationary point of f.Proof.
For item (a), consider that iterationn after the last serious step x
^ was generated, so there are only null steps. First, we prove x
n
+
1
→
p
≔
p
~
R
¯
f
~
(
x
^
). Consider the function: L
n
(
w
)
≔
ϕ
~
n
(
x
n
+
1
)
+
(
μ
¯
/
2
)
x
n
+
1
-
x
^
2
+
(
μ
¯
/
2
)
w
-
x
n
+
1
2. And let S
n
+
1
≔
μ
¯
(
x
^
-
x
n
+
1
)
∈
∂
ϕ
~
n
(
x
n
+
1
). Since x
n
+
1
=
p
~
μ
¯
ϕ
~
n
(
x
^
), L
n
(
x
n
+
1
)
≤
ϕ
~
n
(
x
^
), and (35) implies that (48)
L
n
x
n
+
1
≤
f
~
x
^
,
∀
n
≥
n
¯
.Condition (36) gives the inequality (49)
ϕ
~
n
+
1
x
n
+
2
≥
ϕ
~
n
x
n
+
1
+
S
n
+
1
,
x
n
+
2
-
x
n
+
1
.By the definition of L
n, L
n
+
1
(
x
n
+
2
)
=
ϕ
~
n
+
1
(
x
n
+
2
)
+
(
μ
¯
/
2
)
x
n
+
2
-
x
^
2, and hence (50)
L
n
+
1
x
n
+
2
≥
ϕ
~
n
x
n
+
1
+
S
n
+
1
,
x
n
+
2
-
x
n
+
1
+
μ
¯
2
x
n
+
1
-
x
^
2
.But ϕ
~
n
(
x
n
+
1
)
=
L
n
(
x
n
+
1
)
-
(
μ
¯
/
2
)
x
n
+
1
-
x
^
2, so (51)
L
n
+
1
x
n
+
2
≥
L
n
x
n
+
1
+
S
n
+
1
,
x
n
+
2
-
x
n
+
1
+
μ
¯
2
x
n
+
2
-
x
^
2
-
μ
¯
2
x
n
+
1
-
x
^
2
.After expanding squares, the two rightmost terms above satisfy the relation (52)
μ
¯
2
x
n
+
2
-
x
^
2
-
μ
¯
2
x
n
+
1
-
x
^
2
=
-
μ
¯
x
^
-
x
n
+
1
,
x
n
+
2
-
x
n
+
1
+
μ
¯
2
x
n
+
2
-
x
n
+
1
2
=
-
S
n
+
1
,
x
n
+
2
-
x
n
+
1
+
μ
¯
2
x
n
+
2
-
x
n
+
1
2
.So we obtain L
n
+
1
(
x
n
+
2
)
≥
L
n
(
x
n
+
1
)
+
(
μ
¯
/
2
)
x
n
+
2
-
x
n
+
1
2 and the sequence {
L
n
(
x
n
+
1
)
} is eventually increasing and convergent since it is bounded above by f
~
x
^. By conditions (35) and (36) (53)
L
n
x
^
=
ϕ
~
n
x
n
+
1
+
S
n
+
1
,
x
^
-
x
n
+
1
≤
ϕ
~
n
x
^
≤
f
~
x
^
.Since L
n
(
x
n
+
1
)
+
(
μ
¯
/
2
)
x
^
-
x
n
+
1
2
=
L
n
(
x
^
), we obtain that L
n
x
n
+
1
+
(
μ
¯
/
2
)
x
^
-
x
n
+
1
2
≤
f
~
x
^. By the convergence of {
L
n
(
x
n
+
1
)
}, the sequence {
x
n
} is bounded. Note that(54)
0
≤
μ
¯
2
x
n
+
1
-
x
n
2
≤
L
n
x
n
+
1
-
L
n
-
1
x
n
⟶
0
,so x
n
+
1
-
x
n
→
0 as n
→
∞. Since {
x
n
}
⊆
L
0 (when n is sufficiently large), {
x
n
} is bounded. Therefore, the sequence of approximate proximal point {
x
n
} converges. By using the similar technique of Theorem3(ii) in [19], we can prove that x
n
+
1
→
p
~
R
¯
f
~
(
x
^
). For the sequence {
ϕ
~
n
(
x
n
+
1
)
}, we show that there exists N
1
⊆
N such that (55)
lim
n
∈
N
1
,
n
→
∞
⁡
ϕ
~
n
x
n
+
1
-
f
~
p
+
η
¯
2
x
^
-
p
2
≤
2
ɛ
.By Lemma 8(d), when n is sufficiently large, (56)
ϕ
~
n
x
n
+
1
≥
f
~
x
n
+
η
¯
d
n
k
+
g
ɛ
n
+
η
¯
Δ
n
k
,
x
n
+
1
-
x
n
-
2
ɛ
.And at the same time, according to Lemma 9  ϕ
~
n
(
x
n
+
1
)
≤
f
~
x
n
+
1
+
(
η
¯
/
2
)
x
n
+
1
-
x
^
2. As x
n
+
1
→
p, we have ϕ
~
n
(
x
n
+
1
) is bounded, so it has an accumulation point; say for some iterate set N
1
⊆
N, l
i
m
n
∈
N
1
,
n
→
∞
ϕ
~
n
(
x
n
+
1
)
=
ϕ
~
∗. Obviously, (57)
ϕ
~
∗
-
f
~
p
+
η
¯
x
^
-
p
2
2
≤
2
ɛ
.Since ϕ
~
n
(
x
n
+
1
)
=
f
~
x
^
+
(
η
¯
/
2
)
x
^
-
p
2
+
2
ɛ
-
δ
n
+
1, so δ
∗
=
l
i
m
n
∈
N
1
,
n
→
∞
δ
n
+
1
=
f
~
x
^
+
(
η
¯
/
2
)
p
-
x
^
2
+
2
ɛ
-
ϕ
~
∗, and (58)
ϕ
~
∗
-
f
~
p
+
η
¯
x
^
-
p
2
2
=
f
~
x
^
+
η
¯
2
p
-
x
^
2
-
f
~
p
+
η
¯
x
^
-
p
2
2
+
2
ɛ
-
δ
∗
=
δ
∗
-
f
~
x
^
-
f
~
p
-
2
ɛ
≤
2
ɛ
.Because the descent test in Step 4 is not satisfied, taking the limit as n
→
∞ we have (59)
f
~
p
≥
f
~
x
^
-
m
¯
δ
∗
-
2
ɛ
≥
f
~
x
^
+
m
¯
-
f
~
x
^
+
f
~
p
-
2
ɛ
=
f
~
x
^
-
m
¯
f
~
x
^
+
m
¯
f
~
p
-
2
m
¯
ɛ
.Therefore, f
~
p
-
f
~
x
^
≥
m
¯
(
f
~
p
-
f
~
x
^
)
-
2
m
¯
ɛ, and from m
¯
∈
(
0,1
) we obtain f
~
p
-
f
~
x
^
≥
-
2
m
¯
ɛ
/
(
1
-
m
¯
). But p
=
p
~
R
¯
f
~
(
x
^
) implies that f
~
p
+
(
R
¯
/
2
)
p
-
x
^
2
≤
f
~
x
^, which shows that x
^
∈
B
2
m
¯
ɛ
/
(
1
-
m
¯
)
R
¯
(
p
). That is, x
^ equals approximately p
~
R
¯
f
~
(
x
^
); x
^ is an approximate stationary point of f.
To see item (b),{
x
^
k
} has an accumulation point since {
x
^
k
}
⊆
L
0; say for some iterate set K, x
^
k
→
x
i
n
f
∈
L
0 as k
∈
K and k
→
∞. Since x
^
k
+
1
=
x
i
k
+
1, we set j
k
=
i
k
+
1
-
1, so that x
^
k
+
1
=
p
~
μ
¯
ϕ
~
j
k
(
x
^
k
). The descent test (60)
f
~
x
^
k
+
1
≤
f
~
x
^
k
-
m
¯
δ
i
k
+
1
-
2
ɛimplies that as k
→
∞, either f
~
x
^
k
↘
∞ or δ
i
k
+
1
→
2
ɛ. By Lemma 3(b), f
~ is bounded below; therefore δ
i
k
+
1
→
2
ɛ. From (31) both x
^
k
+
1
-
x
^
k
2 and e
~
-
j
k
k
+
η
¯
d
-
j
k
k must converge to zero. Therefore by (14), ϕ
~
j
k
(
x
^
k
+
1
)
-
f
~
x
^
k
→
-
2
ɛ as k
→
∞. Consider now k
∈
K; since x
^
k
+
1
-
x
^
k
2
→
0, both x
^
k
+
1 and x
^
k converge to x
i
n
f, with ϕ
~
j
k
(
x
^
k
+
1
)
→
f
~
x
i
n
f
-
2
ɛ. But x
^
k
+
1
=
p
~
μ
¯
ϕ
~
j
k
(
x
^
k
) and η
¯
>
ρ
i
d implies that, for all w
∈
L
0, (61)
ϕ
~
j
k
x
^
k
+
1
+
μ
¯
2
x
^
k
+
1
-
x
^
k
2
≤
ϕ
~
j
k
w
+
μ
¯
2
w
-
x
^
k
2
≤
f
~
w
+
η
¯
2
w
-
x
^
k
2
+
μ
¯
2
w
-
x
^
k
2
=
f
~
w
+
R
¯
2
w
-
x
^
k
2
.Therefore, we have (62)
f
~
x
i
n
f
-
ɛ
≤
f
~
w
+
R
¯
2
w
-
x
i
n
f
2
,
∀
w
∈
L
0
.As x
i
n
f
∈
L
0, we also have that, for any w
∉
L
0, (63)
f
~
x
i
n
f
-
ɛ
≤
f
~
x
i
n
f
≤
f
~
x
0
+
M
0
<
f
~
w
≤
f
~
w
+
R
¯
2
w
-
x
i
n
f
2
.Hence, f
~
x
i
n
f
≤
f
~
w
+
(
R
¯
/
2
)
w
-
x
i
n
f
2
+
ɛ for all w
∈
R
m. That is, x
i
n
f is ɛ-double approximate stationary point of f.Remark 12.
Note that ifɛ
=
0, the results obtained in Theorem 11 are exactly the ones in [18], which means that our work is really the generalization of previous work.


## 6. Conclusion

We propose an approximate redistributed proximal bundle method for nonsmooth nonconvex optimization by employing the inexact information from the objective function. With the inexact data we prove that the cutting-planes model constructed in this paper is eventually the local lower approximation to the approximate objective function. Analysis of the convergence proceeds by first showing that the convexification parameter eventually stabilized and once stabilized, the convergence to the approximate orɛ-double approximate stationary point of the objective function is obtained under the condition that the stabilized convexification parameter is greater than the ideal proximal threshold ρ
i
d. The local convexification approach opens a new way for future study on nonsmooth nonconvex optimization and can shed a new insight on the first order models from [20].In [21], the authors present a framework of general bundle methods which are capable of handling inexact oracles, and the framework generalizes in various ways a number of algorithms proposed in the literatures. Next we discuss the relationship between our algorithm and [21]. In [21], the objective function f is a finite-valued convex function, and the authors make the following assumptions. For each given u
∈
R
n, the oracle delivers the inexact information:(64)
f
u
=
f
u
-
η
u
,
g
u
∈
R
n
such  that
f
·
≥
f
u
+
g
u
,
·
-
u
-
η
u
g
with
η
u
≤
η
,
η
u
g
≤
η
,where the error bound η is possibly unknown. By (64) we have f
(
·
)
≥
f
(
u
)
+
〈
g
u
,
·
-
u
〉
-
(
η
u
g
+
η
u
). As a result,(65)
g
u
∈
∂
η
u
g
+
η
u
f
u
with
η
u
g
+
η
u
≥
0
,
∀
u
.Even when the value of the upper error bound η is unknown, inequalities (64) and (65) imply that η
≥
η
u
≥
-
η
u
g
≥
-
η, which means that(66)
f
u
∈
f
u
-
η
,
f
u
+
η
,
g
u
∈
∂
2
η
f
u
.In our paper, if f
~ is the function which is locally convex by adding a quadratic term with convexification parameter, we suppose that, for each given x
∈
R
m, an oracle delivers the inexact information:(67)
f
~
x
∈
f
x
-
ε
f
,
f
x
+
ε
g
,
g
ɛ
x
∈
R
m
such  that
f
·
≥
f
~
x
+
g
ɛ
x
,
·
-
u
-
ɛ
with
ɛ
=
ε
f
+
ε
g
.Assumption (67) is more general than (64) since if we choose ε
f
=
ε
g
=
η, (67) will become f
~
x
∈
[
f
(
x
)
-
η
,
f
(
x
)
+
η
], g
ɛ
x
∈
∂
2
η
f
(
x
), which is exactly (66). Therefore, our assumption is, in a sense, some kind of generalization of assumptions in [21].In [21], the authors use the linearizations and the cutting-plane model(68)
f
j
L
u
=
f
u
j
+
g
u
j
,
u
-
u
j
,
j
=
1,2
,
…
,
k
,
f
ˇ
k
·
=
max
⁡
f
j
L
·
∣
j
∈
J
k
=
1,2
,
…
,
k
,and the next trial point is obtained by minimizing the stabilized model function (69)
min
u
∈
R
n
⁡
f
ˇ
k
·
+
1
2
t
k
u
-
u
^
k
2
.In our paper, we choose the cutting-plane model function to be (70)
ϕ
~
n
y
=
max
i
∈
I
n
⁡
f
~
i
+
η
n
2
x
i
-
x
^
k
2
+
g
ɛ
i
+
η
n
x
i
-
x
^
k
,
y
-
x
i
-
2
ɛ
,which becomes a lower approximation to the locally convex objective function. It is similar to (68) except for the appearance of 2
ɛ. At the same time, the next trail point is chosen as x
n
+
1
=
p
~
μ
n
ϕ
~
n
(
x
^
k
), the approximate proximal point of f
~ defined by (6), which is quite different from the general traditional techniques introduced in [21].In [21], the authors mention that, for inexact oracles, the progress made by the algorithm can be measured relative to the model, some nominal reference value, or the approximate objective function, and they are called and denoted by(71)
model  decrease:
δ
k
M
=
l
k
-
f
ˇ
k
u
k
+
1
,
where
l
k
is  chosen  so  that
l
k
≥
f
u
^
k
,
nominal  decrease:
δ
k
N
=
δ
k
M
-
α
k
t
k
u
k
+
1
-
u
^
k
2
,
α
∈
0,1
,
effective  decrease:
δ
k
E
=
f
u
^
k
-
f
u
k
+
1
.In our paper, we define a predicted decrease δ
n
+
1
=
(
f
~
x
^
k
+
(
η
n
/
2
)
x
n
+
1
-
x
^
k
2
+
2
ɛ
)
-
ϕ
~
n
(
x
n
+
1
), which is similar to δ
k
M, but a bit different from δ
k
M since l
k is only associated with current stability center u
^
k, while the first term in δ
n
+
1 is not only related to current stability center x
^
k but also involved with the new trial point x
n
+
1. And this predicted decrease is nonnegative as long as η
n is sufficiently large, and this requirement is exactly coincident with the condition which guarantees that ϕ
~
n
(
·
) is a lower approximation to f
~
(
·
). Therefore, we can further employ it in the descent test to decide between making a descent step or a null step.



---

*Source: 215310-2015-05-31.xml*