# A Decomposition Algorithm for Convex Nondifferentiable Minimization with Errors

Authors: Yuan Lu; Li-Ping Pang; Jie Shen; Xi-Jun Liang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

A decomposition algorithm based on proximal bundle-type method with inexact data is presented for minimizing an unconstrained nonsmooth convex functionf. At each iteration, only the approximate evaluation of f and its approximate subgradients are required which make the algorithm easier to implement. It is shown that every cluster of the sequence of iterates generated by the proposed algorithm is an exact solution of the unconstrained minimization problem. Numerical tests emphasize the theoretical findings.


---

## Body

## 1. Introduction

Consider minimizing the following problem:(1.1)min⁡⁡{f(x)∣x∈Rn},
where f:Rn→R is a nondifferentiable convex function. It is well known that many practical problems can be formulated as (1.1), for example the problem of catastrophe, ruin, vitality, data mining, and finance. A classical conceptual algorithm for solving (1.1) is the proximal point method, based on the Moreau-Yosida regulation of f [1, 2]. Implementable forms of the method can be obtained by means of a bundle technique, alternating serious steps with sequences of null steps [3, 4].More recently, new conceptual schemes for solving (1.1) have been developed by using an approach that is somewhat different from Moreau-Yosida regularization. This is the 𝒱𝒰-theory introduced in [5]; see also [6, 7]. The idea is to decompose Rn into two orthogonal subspace 𝒱 and 𝒰 at a point x¯ that the nonsmoothness of f is concentrated essentially on 𝒱, and the smoothness of f appears on 𝒰-subspace. More precisely, for a given g¯∈∂f(x¯), where ∂f(x¯) denotes the subdifferential of f at x¯ in the sense of convex analysis, then Rn can be decomposed as direct sum of two orthogonal subspaces, that is, Rn=𝒰⊕𝒱, where 𝒱=lin(∂f(x¯)-g¯) and 𝒰=𝒱⊥. They define the 𝒰-Lagrangian, an approximation of the original function, which can be used to create a second-order expansion of f along certain manifolds.Mifflin and Sagastizábal design a𝒱𝒰-algorithm for convex function in [8]. This algorithm brings the iterate to the primal track with the help of bundle subroutine. Then the 𝒰-Newton step is performed to gain superlinear decrease of the distance to solution. In order to implement this algorithm, [9] gives an algorithm which only uses the subgradients. However, this algorithm is conceptual in the sense that it needs to compute the exact function values of the objective function, which is difficult to evaluate them. For example, consider the situation of Lagrangian relaxation. The primal problem is(1.2)max⁡⁡{q(ξ)∣ξ∈P,h(ξ)=0},
where P is a compact subset of Rm and q:Rm→R, h:Rm→Rn. Lagrangian relaxation of the equality constraints in the problem leads to the following problem(1.3)min⁡x∈Rn⁡C(x),
where
(1.4)C(x)=max⁡ξ∈P⁡{q(ξ)+〈x,h(ξ)〉}
is the dual function. Trying to solve problem (1.2) by means of solving its dual problem (1.3) makes sense in many situations. In this case, evaluating the function value C(x) and a subgradient g(x)∈∂C(x) requires solving the optimization problem (1.4) exactly. Actually, in some cases, computing exact values of C(x) is unnecessary and inefficient. For this reason, some modifications of bundle methods in [9] were needed.The paper is organized as follows. In the next section we present the approximate𝒰-Lagrangian based on the approximate subgradient. Then we design a conceptual Algorithm 2.6 which can deal with the approximate subgradients and approximate function values. Section 3 breaks into 3 parts. In the first part, we propose the approximate primal-dual track. The proximal bundle-type subroutine with inexact data is introduce in the second part. The third part of Section 3 is devoted to establishing an implemental Algorithm 3.5 which substitutes the approximate V-step in Algorithm 2.6 with proximal bundle subroutine. Numerical testing of the resulting Algorithm 3.5 is reported in the final section.


## 2. A Conceptual Approximate Decomposition Algorithm

### 2.1. Approximate𝒰-Lagrangian and Its Properties

In some cases, computing exact values of the objective function and exact subgradient is unnecessary and inefficient. For this reason, some modification of the𝒰-Lagrangian will be proposed in this section. We assume that g¯ satisfies
(2.1)f(x¯+u⊕v)≥f̃(x¯)+〈g¯,u⊕v〉,wheref̃(x¯)∈[f(x¯)-ɛ,f(x¯)],ɛ>0.
Introducing this g¯ to [5], one can restate the definition of 𝒰-Lagrangian and its properties as follows.Definition 2.1.
Assume (2.1). The approximate 𝒰-Lagrangian of f, denoted by Lg¯(u), is defined as follows. 									(2.2)Lg¯(u)=min⁡v∈V⁡{f(x¯+u⊕v)-〈g¯V,v〉V},
and Wg¯(u) is defined by
(2.3)Wg¯(u)=Argmin⁡v∈V⁡{f(x¯+u⊕v)-〈g¯V,v〉V}.Theorem 2.2.
Assume (2.1). Then the following assertions are true:(i)
the functionLg¯ defined in (2.2) is convex and finite everywhere;(ii)
Wg¯(u)={w∣∃g∈∂f(x¯+u⊕w):g𝒱=g¯𝒱};(iii)
0∈Wg¯(0) and Lg¯(0)=f(x¯).Theorem 2.3.
Assume (2.1) and Wg¯(u)≠∅. Then one has that
(2.4)∂Lg¯(u)={u*∣u*⊕g¯V∈∂f(x¯+u⊕w)}.Remark 2.4.
Assume (1.2). If ɛ=0, then the approximate 𝒰-Lagrangian in this paper is exactly the 𝒰-Lagrangian in [5].


### 2.2. Approximate Decomposition Algorithm Frame

In order to give an approximate decomposition algorithm frame, we restate the definition of Hessian matrix in [5] as follows.Definition 2.5.
Assume thatf is finite, x¯ is fixed, and g¯ satisfies (2.1). We say that f has at x¯ a 𝒰-Hessian H𝒰f(x¯) associated with g¯ if Lg¯(u) has a generalized Hessian at 0, setting
(2.5)HUf(x¯)=HLg¯(0).Assume (2.1), we investigate an approximate decomposition algorithm frame based on the definition of the approximate 𝒰-Lagrangian.Algorithm 2.6.
Step 0.
Initiation
x0,η>0,0<τ<1,ɛ0>0,g0 satisfies for all x, f(x)≥f̃(x0)+〈g0,x-x0〉, where f̃(x0)∈[f(x0)-ɛ0,f(x0)] and k=0.
Step 1.
Stop if∥gk∥≤η.
Step 2.
Approximate𝒱-step.
Compute an optimal solutionδv∈𝒱 satisfying
(2.6)δv∈Argmin⁡δv∈Vf(xk+0⊕δv).
Set x′=xk+0⊕δv.
Step 3.
𝒰-step. Make a Newton step in x′.
Compute thatgk satisfies for all x, f(x)≥f̃(x′)+〈gk,x-x′〉, where f̃(x′)∈[f(x′)-ɛk,f(x′)], such that
(2.7)gVk=0,gUk∈∂Lgk((x′-x̅)U).
Compute the solution δu∈𝒰 satisfying
(2.8)gUk+HUf(x̅)δu=0.
Set xk+1=x′+δu⊕0=xk+δu⊕δv and ɛk+1=τɛk.
Step 4.
Update-set
Compute thatgk+1 satisfies for all x, f(x)≥f̃(xk+1)+〈gk+1,x-xk+1〉, where f̃(xk+1)∈[f(xk+1)-ɛk+1,f(xk+1)]. Set k=k+1 and go to Step 1.Theorem 2.7.
Assume (2.1) and f has a positive definite 𝒰-Hessian at x¯, a minimizer of f. Then the iterate points {xk} constructed by Algorithm 2.6 satisfy
(2.9)‖xk+1-x¯‖=o(‖xk-x¯‖).Remark 2.8.
If{ɛk}k=0∞≡0, this algorithm is the same as Algorithm 4.5 in [5]. However, it only uses the approximate objective function values which make the algorithm easier to implement.


## 2.1. Approximate𝒰-Lagrangian and Its Properties

In some cases, computing exact values of the objective function and exact subgradient is unnecessary and inefficient. For this reason, some modification of the𝒰-Lagrangian will be proposed in this section. We assume that g¯ satisfies
(2.1)f(x¯+u⊕v)≥f̃(x¯)+〈g¯,u⊕v〉,wheref̃(x¯)∈[f(x¯)-ɛ,f(x¯)],ɛ>0.
Introducing this g¯ to [5], one can restate the definition of 𝒰-Lagrangian and its properties as follows.Definition 2.1.
Assume (2.1). The approximate 𝒰-Lagrangian of f, denoted by Lg¯(u), is defined as follows. 									(2.2)Lg¯(u)=min⁡v∈V⁡{f(x¯+u⊕v)-〈g¯V,v〉V},
and Wg¯(u) is defined by
(2.3)Wg¯(u)=Argmin⁡v∈V⁡{f(x¯+u⊕v)-〈g¯V,v〉V}.Theorem 2.2.
Assume (2.1). Then the following assertions are true:(i)
the functionLg¯ defined in (2.2) is convex and finite everywhere;(ii)
Wg¯(u)={w∣∃g∈∂f(x¯+u⊕w):g𝒱=g¯𝒱};(iii)
0∈Wg¯(0) and Lg¯(0)=f(x¯).Theorem 2.3.
Assume (2.1) and Wg¯(u)≠∅. Then one has that
(2.4)∂Lg¯(u)={u*∣u*⊕g¯V∈∂f(x¯+u⊕w)}.Remark 2.4.
Assume (1.2). If ɛ=0, then the approximate 𝒰-Lagrangian in this paper is exactly the 𝒰-Lagrangian in [5].


## 2.2. Approximate Decomposition Algorithm Frame

In order to give an approximate decomposition algorithm frame, we restate the definition of Hessian matrix in [5] as follows.Definition 2.5.
Assume thatf is finite, x¯ is fixed, and g¯ satisfies (2.1). We say that f has at x¯ a 𝒰-Hessian H𝒰f(x¯) associated with g¯ if Lg¯(u) has a generalized Hessian at 0, setting
(2.5)HUf(x¯)=HLg¯(0).Assume (2.1), we investigate an approximate decomposition algorithm frame based on the definition of the approximate 𝒰-Lagrangian.Algorithm 2.6.
Step 0.
Initiation
x0,η>0,0<τ<1,ɛ0>0,g0 satisfies for all x, f(x)≥f̃(x0)+〈g0,x-x0〉, where f̃(x0)∈[f(x0)-ɛ0,f(x0)] and k=0.
Step 1.
Stop if∥gk∥≤η.
Step 2.
Approximate𝒱-step.
Compute an optimal solutionδv∈𝒱 satisfying
(2.6)δv∈Argmin⁡δv∈Vf(xk+0⊕δv).
Set x′=xk+0⊕δv.
Step 3.
𝒰-step. Make a Newton step in x′.
Compute thatgk satisfies for all x, f(x)≥f̃(x′)+〈gk,x-x′〉, where f̃(x′)∈[f(x′)-ɛk,f(x′)], such that
(2.7)gVk=0,gUk∈∂Lgk((x′-x̅)U).
Compute the solution δu∈𝒰 satisfying
(2.8)gUk+HUf(x̅)δu=0.
Set xk+1=x′+δu⊕0=xk+δu⊕δv and ɛk+1=τɛk.
Step 4.
Update-set
Compute thatgk+1 satisfies for all x, f(x)≥f̃(xk+1)+〈gk+1,x-xk+1〉, where f̃(xk+1)∈[f(xk+1)-ɛk+1,f(xk+1)]. Set k=k+1 and go to Step 1.Theorem 2.7.
Assume (2.1) and f has a positive definite 𝒰-Hessian at x¯, a minimizer of f. Then the iterate points {xk} constructed by Algorithm 2.6 satisfy
(2.9)‖xk+1-x¯‖=o(‖xk-x¯‖).Remark 2.8.
If{ɛk}k=0∞≡0, this algorithm is the same as Algorithm 4.5 in [5]. However, it only uses the approximate objective function values which make the algorithm easier to implement.


## 3. Approximate Decomposition Algorithm

Since the Algorithm2.6 in Section 2 relies on knowing the subspaces 𝒰 and 𝒱 and converges only locally, it needs significant modification. In [10], Mifflin and Sagastizábal show that a proximal point sequence follows primal track near a minimizer. This opens the way for defining a 𝒱𝒰-algorithm where 𝒱-steps are replaced by proximal steps. In addition, the proximal step can be estimated with a bundle technique which also can approximate the unknown 𝒰 and 𝒱 subspaces as a computational byproduct. Therefore, they establish Algorithm 6 in [8] by combing the bundle subroutine with the 𝒱𝒰-space decomposition method. However, this algorithm needs the exact function values and exact subgradients, which is expensive to compute. Therefore, the study of using approximate values instead of the exact ones is deserving.


### 3.1. Approximate Primal-Dual Track

Given a positive scalar parameterμ, the proximal point function depending on f is defined by(3.1)pμ(x)∶=argmin⁡p∈Rn{f(p)+12μ‖p-x‖2},x∈Rn,
where ∥·∥ stands for the Euclidean norm. It has the property: gμ(x)∶=μ(x-pμ(x))∈∂f(pμ(x)).Similarly to the definition of primal track, we define the approximate primal track.Definition 3.1.
For anyɛ>0, μ=μ(x)>0, we say that Θ(u)=x¯+u⊕v(u) is an approximate primal track leading to x¯, a minimizer of f, if for all u∈Rdim𝒰 small enough, it satisfies the following:(i)
Θ(uμ(x))=x¯+uμ(x)⊕v(uμ(x)), where uμ(x)=(pμ(x)-x¯)𝒰;(ii)
v:Rdim𝒰→Rdim𝒱 is a C2-function satisfying V¯v∈Wg¯(u) for all g¯ satisfies (2.1);(iii)
the JacobianJΘ(u) is a basis matrix for 𝒱(Θ(u))⊥;(iv)
the particular𝒰-Lagrangian L0(u) is a C2-function.Accordingly, we have the approximate dual track denoted byΓ(u) corresponding to the approximate primal track. More precisely,
(3.2)Γ(u)=argmin⁡⁡{‖g‖2:f(x)≥f̃(Θ(u))+〈g,x-Θ(u)〉}.In fact, ifɛ=0, the approximate primal-dual track is exactly the primal-dual track shown in [8].The next lemma addresses that making an approximate𝒱-step in Algorithm 2.6 essentially amounts to finding a corresponding approximate primal track point.Lemma 3.2.
LetΘ(uμ(x)) be an approximate primal track leading to x¯, a minimizer of f, and let H¯∶=∇2L0(0). Then for all u sufficiently small Θ(uμ(x)) is the unique minimizer of f on the affine set Θ(uμ(x))+𝒱(Θ(uμ(x))).Proof.
SinceJΘ(u) is a basis for 𝒱(Θ(u))⊥, Theorem  3.4 in [10] with ℬ𝒰(u)=JΘ(u) gives the result.


### 3.2. The Proximal Bundle-Type Subroutine with Inexact Data

Throughout this section, we make the following assumption: at each given pointx∈Rn, and for ɛ≥0, we can find some f̃(x)∈R and g(x)∈Rn satisfying
(3.3)f̃(x)∈[f(x)-ɛ,f(x)],f(ζ)≥f(x)+〈g(x),ζ-x〉-ɛ¯,∀ζ∈Rn,
where ɛ¯=f(x)-f̃(x). At the same time, it can be ensured that
(3.4)f̃j⟶f̃kifyj⟶xk,
where f̃j∈[f(yj)-ɛk,f(yj)] and f̃k∈[f(xk)-ɛk,f(xk)] for given ɛk>0. The condition (3.3) means that g(x)∈∂ɛ¯f(x). This setting is realistic in many applications; see [11].The bundle method includes two phases. (i) The first phase makes use of the information(xk,f̃k,gk),(xk-1,f̃k-1,gk-1),…,(x1,f̃1,g1) in bundles to establish a polyhedral approximation of f at the actual iterate xk. (ii) Due to the kinky structure of f, the model is possibly not precise for approximation f. Then, more information around the actual iterate xk is mobilized to obtain a more reliable model. Feature (i) leads to the following approximation of f at xk. Let Ik denote the index set at the kth iteration with each j∈Ik representing (yj,f̃j,gj), where f̃j and gj satisfy(3.5)f̃j∈[f(yj)-ɛk,f(yj)],f(x)≥f̃j+〈gj,x-yj〉,∀x∈Rn,
for given ɛk>0. From the choices of f̃j and gj, we have that, for all x∈Rn and for all j∈Ik,(3.6)f(x)≥f̃j+〈gj,x-yj〉=f̃k+gjT(x-xk)+ɛk-αk,j,
where(3.7)αk,j=α(xk,yj)=f̃k-f̃j-gjT(xk-yj)+ɛk.On the basis of the above observation, we attempt to explore the possibility of utilizing the approximate subgradient and approximate function values instead of the exact ones. We approximatef at xk from below by a piecewise linear convex function φ of the form:(3.8)φ(z)∶=f̃k+max⁡j∈Ik⁡{gjT(z-xk)-αk,j}+ɛk.Since (3.8) becomes more and more crude if an approximation of f is farther away from xk, we add the proximal term (1/2)μ∥p-xk∥2,μ>0, to it. To approximate an proximal point, we solve the first quadratic programming subproblem
(3.9)min⁡r+12μ‖p-xk‖2s.t.r≥f̃k+gjT(p-xk)-αk,j+ɛk,j∈Ik.
Its corresponding dual problem is(3.10)min⁡12μ‖∑j∈Ikλjgj‖2+∑j∈Ikλjαk,js.t.∑j∈Ikλj=1,λj≥0,j∈Ik.
Let (r̂,p̂) and λ̂=(λ̂1,…,λ̂|Ik|) denote the optimal solution of (3.9) and (3.10), then it is easily seen that(3.11)r̂=φ(p̂),p̂=xk-1μĝ,whereĝ∶=∑j∈Ikλ̂jgj.
In addition, λ̂j=0 for all j∈Ik such that r>f̃k+gjT(p̂-xk)-αk,j+ɛk and(3.12)φ(p̂)=f̃k+∑j∈Ikλ̂j[gjT(p̂-xk)-αk,j+ɛk]=f̃k-∑j∈Ikλ̂jαk,j+ɛk-1μ‖ĝ‖2.
The vector p̂ is an estimate of an approximate proximal point. Hence, it approximates an approximate primal track point when the latter exists. To proceed further we let yj+∶=p̂ and compute f̃(p̂), ê∶=f̃(p̂)-φ(p̂)=f̃(p̂)-r̂, and gj+ satisfying f(z)≥f̃(p̂)+〈gj+,z-p̂〉,forallz∈Rn.An approximate dual path point, denoted byŝ, is constructed by solving a second quadratic problem, which depends on a new index set(3.13)Îk∶={j∈Ik:r̂=f̃k+gjT(p̂-xk)-αk,j+ɛk}∪{j+}.
The second quadratic programming problem is(3.14)min⁡r+12‖p-xk‖2s.t.r≥gjT(p-xk),j∈Îk.
It has a dual problem(3.15)min⁡12‖∑j∈Îkλjgj‖2s.t.∑j∈Îkλj=1,λj≥0,j∈Îk.
Similar to (3.11), the respective solutions, denoted by (r¯,p¯) and λ¯, satisfy(3.16)r¯=φ(p¯),p¯-xk=-ŝ,whereŝ=∑j∈Îkλ¯jgj.Givenσ∈(0,1/2], the proximal bundle subprocedure is terminated and p̂ is declared to be an approximation of pμ(xk) if(3.17)ê≤σμ‖ŝ‖2.
Otherwise, Ik above is replaced by Îk, and new iterate data are computed by solving updated subproblems (3.9) and (3.14). This update, appending (αk,j+,gj+) to active data at (3.9), ensures convergence to a minimizing point x¯ in case of nontermination.Remark 3.3.
From the talking above, the following results are true:(i)
ŝ=argmin{∥s∥2:s∈co{gj:j∈Îk}};(ii)
sincepμ(x) is an approximate primal track point Θ(uμ(x)) approximated by p̂ and co{gj:j∈Îk} approximates co{g:f(x)≥f̃(Θ(u))+〈g,x-Θ(u)〉}, from (3.2) the corresponding Γ(uμ(x)) is estimated by ŝ;(iii)
we can obtain theÛ by means of the following iteration.Let(3.18)Îkact∶={j∈Îk:r¯=gjT(p¯-x)}.
Then, from (3.16), r¯=-gjTŝ,j∈Îkact, so
(3.19)(gj-gl)Tŝ=0,
for all such j and for a fixed l∈Îkact. Define a full column rank matrix V̂ by choosing the largest number of indices j satisfying (3.19) such that the corresponding vectors gj-gl are linearly independent and by letting these vectors be the columns of V̂. Then let Û be a matrix whose columns form an orthonormal basis for the null space of V̂T with Û=I if V̂ is vacuous.Theorem 3.4.
At thekth iteration, the above proximal bundle subprocedure satisfies the following:(i)
gj∈∂ɛ¯+êf(p̂),j∈Îk, where ɛ¯=f(p̂)-f̃(p̂) and f̃(p̂)∈[f(p̂)-ɛk,f(p̂)];(ii)
ŝ∈∂ɛ¯+êf(p̂) and ĝ∈∂ɛ¯+êf(p̂);(iii)
μ∥p̂-pμ(xk)∥2≤ɛ¯+ê;(iv)
∥ŝ∥≤∥ĝ∥, where ĝ=μ(xk-p̂);(v)
for any parameterm∈(0,1), (3.17) implies(3.20)f̃(p̂)-f̃k≤-m2μ‖ĝ‖2+ɛk.Proof.
(i) Sincegj+ satisfies f(z)≥f̃(p̂)+〈gj+,z-p̂〉 and ê=f̃(p̂)-φ(p̂)≥0, gj+ satisfies
(3.21)f(z)≥f̃(p̂)+〈gj+,z-p̂〉-ê=f(p̂)+〈gj+,z-p̂〉-ê-ɛ¯,
where ɛ¯=f(p̂)-f̃(p̂), so the result of item (i) holds for j=j+. From the definition of p̂,r̂, and Îk we have that for all j≠j+ in Îk(3.22)φ(p̂)=r̂=f̃k+gjT(p̂-xk)-αk,j+ɛk,
so for all such j,
(3.23)ê=f̃(p̂)-φ(p̂)=f̃(p̂)-f̃k-gjT(p̂-xk)+αk,j-ɛk.
In addition,
(3.24)f(z)≥f̃k+gjT(z-xk)-αk,j+ɛk,z∈Rn.
Adding 0=ê-ê to this inequality gives
(3.25)f(z)≥f̃k+gjT(z-xk)+ɛk-αk,j+ê-ê=f̃(p̂)+gjT(z-p̂)-ê=f(p̂)+gjT(z-p̂)-ê-ɛ¯,∀z∈Rn,
which means that gj∈∂ɛ¯+êf(p̂) for j+≠j∈Îk.
(ii) Multiplying each inequality in (3.25) by its corresponding multiplier λ¯j≥0 and summing these inequalities, we have
(3.26)∑j∈Îkλ¯jf(z)≥∑j∈Îkλ¯jf(p̂)+∑j∈Îkλ¯jgjT(z-p̂)-∑j∈Îkλ¯jê-∑j∈Îkλ¯jɛ¯,∀z∈Rn.
Using the definition of ŝ from (3.16) and the fact that ∑j∈Îkλ¯j=1 gives
(3.27)f(z)≥f(p̂)+ŝT(z-p̂)-ê-ɛ¯,∀z∈Rn,
which means that ŝ∈∂ɛ¯+êf(p̂). In a similar manner, this time using the multipliers λ̂j that solve dual problem (3.10) and define ĝ in (3.11), together with λ̂j+∶=0, obtains the result.
(iii) Sincegμ∈∂f(pμ(xk)), we have
(3.28)f(pμ(xk))≤f(p̂)-gμ(xk)T(p̂-pμ(xk)).
From (ii): ĝ∈∂ɛ¯+êf(p̂), we get
(3.29)f(pμ(xk))≥f(p̂)+ĝT(pμ(xk)-p̂)-ɛ¯-ê.
Therefore,
(3.30)f(p̂)+ĝT(pμ(xk)-p̂)-ɛ¯-ê≤f(pμ(xk))≤f(p̂)-gμ(xk)T(p̂-pμ(xk)),
that is, (ĝ-gμ(xk))T(pμ(xk)-p̂)-ɛ¯-ê≤0. Then, since the expression for ĝ from (3.11) written in the form
(3.31)ĝ=-μ(p̂-xk),
combined with gμ(xk)=μ(xk-pμ(xk)) implies that ĝ-gμ(xk)=μ(pμ(xk)-p̂), we obtain item (iii).
(iv) From (3.10), (3.11), (3.31), and the definition of Îk, we have that μ(xk-p̂)=ĝ is in the convex hull of {gj,j∈Îk}. We obtain the result by virtue of the minimum norm property of ŝ.
(v) Sinceσ≤1/2 and m∈(0,1), we have σ≤1-(m/2). Thus if (3.17) holds then ê≤[(1-(m/2))/μ]∥ŝ∥2. Together with the definition of ê, (3.12) and the nonnegativity of λ̂jαj gives
(3.32)f̃(p̂)-f̃k=ê+φ(p̂)-f̃k=ê-∑j∈Ikλ̂jαk,j-1μ‖ĝ‖2+ɛk≤ê-1μ‖ĝ‖2+ɛk≤[(1-(m/2))μ]‖ŝ‖2-1μ‖ĝ‖2+ɛk.
Finally, combing this inequality with item (iv) gives (3.20).


### 3.3. Approximate Decomposition Algorithm and Convergence Analysis

Substituting the approximate𝒱-step in Algorithm 2.6 with proximal bundle-type subroutine, we present an approximate decomposition algorithm as follows. Afterwards a detailed convergence analysis is given. The main statement comprises the fact that each cluster point of the sequence of iterates generated by the algorithm is an optimal solution.Algorithm 3.5.
Choose a starting pointp0∈Rn and positive parameters η,ɛ0,μ̲,τ, and m with τ<1, m<1.
Step 0.
Computeg0 satisfying f(z)≥f̃(p0)+〈g0,z-p0〉, where f̃(p0)∈[f(p0)-ɛ0,f(p0)]. Let U0 be a matrix with orthonormal n-dimensional columns estimating an optimal 𝒰-basis. Set s0=g0 and k∶=0.
Step 1.
Stop if∥sk∥2≤η.
Step 2.
Choose annk×nk positive definite matrix Hk, where nk is the number of columns of Uk.
Step 3.
Compute an approximate𝒰-Newton step by solving the linear system
(3.33)HkΔuk=-UkTsk.
Set xk+1′∶=pk+UkΔuk.
Step 4.
Chooseμk+1>μ̲,σk+1∈(0,1/2], initialize Ik, and run the bundle subprocedure with x=xk+1′. Compute recursively, and set (ek+1′,pk+1′,sk+1′,Uk+1′)∶=(ê,p̂,ŝ,Û).
Step 5.
If(3.34)f̃(pk+1′)-f̃(pk)≤-m2μk+1‖sk+1′‖2+ɛk+1,
then set
(3.35)(xk+1,ek+1,pk+1,sk+1,Uk+1,ɛk+1)∶=(xk+1′,ek+1′,pk+1′,sk+1′,Uk+1′,τɛk).
Otherwise, execute a line search
(3.36)xk+1∶=argmin{f̃(pk),f̃(pk+1′)},
reinitialize Ik, and rerun the bundle subroutine with x=xk+1, to find new values for (ê,p̂,ŝ,Û), then set (ek+1,pk+1,sk+1,Uk+1,ɛk+1)=(ê,p̂,ŝ,Û,τɛk).
Step 6.
Replacek by k+1 and go to Step 1.Remark 3.6.
In this algorithm,{ɛk}k=0∞↓0. If {ɛk}k=0∞≡0, this algorithm is the same as Algorithm 6 in [8]. However, this algorithm uses proximal bundle-type subroutine which can deal with the approximate subgradients and the approximate function values.Theorem 3.7.
One of the following two cases is true:(i)
if the proximal bundle procedure in Algorithm3.5  does not terminate, that is, if (3.17) never hold, then the sequence of p̂-values converges to pμ(x) and pμ(x) is a minimizer of f;(ii)
if the procedure terminates withŝ=0, then the corresponding p̂ equals pμ(x) and is a minimizer of f.Proof.
By ([12], Prop. 4.3), if this procedure does not terminate then it generates an infinite sequence of ê-values and ɛ¯-value converging to zero. Since (3.17) does not hold, the sequence of ∥ŝ∥-values also converges to 0. Thus, item (iii) in Theorem 3.4 implies that {p̂}→pμ(x). And Theorem 3.4 (ii) gives
(3.37)f(z)≥f(p̂)+ŝT(z-p̂)-(ê+ɛ̂),z∈Rn.
By the continuity of f, this becomes
(3.38)f(z)≥f(pμ(x)),z∈Rn.
The termination case with ŝ=0 follows in a similar manner, since (3.17) implies ê=0 in this case.The next theorem establishes the convergence of Algorithm3.5, and the proof of which is similar to Theorem  9 in [8].Theorem 3.8.
Suppose that the sequence{μk} in Algorithm 3.5  is bounded above by μ¯. Then the following hold:(i)
the sequence{f̃(pk)} is decreasing and either {f̃(pk)}→-∞ or {∥sk∥} and {ek} both converge to 0;(ii)
iff is bounded from below, then any accumulation point of {pk} is a minimizers of f.Proof.
In this paper, the inequalities of (3.15), (3.16), and (3.17) in [8] become
(3.39)f̃(pk+1)-f̃(pk)≤-m2μk+1‖sk+1‖2,(3.40)f(z)≥f(pk)+skT(z-pk)-ɛpk-ek,∀z∈Rn,whereɛpk=f(pk)-f̃(pk),(3.41)ek≤σkμk‖sk‖2,
since ∥sk∥≠0, (3.39) implies that {f̃(pk)} is decreasing. Suppose {f̃(pk)}↛-∞. Then summing (3.39) over k and using the fact that m/2μk≥m/2μ¯ for all k implies that {∥sk∥}→0. Then (3.41) with σk≤1/2 and μk≥μ̲>0 implies that {ek}→0, which establishes (i).
Now supposef is bounded from below and p¯ is any accumulation point of {pk}. Then, because {∥sk∥}, {ek}, and {ɛpk} converge to 0, (3.40) together with the continuity of f implies that f(p¯)≤f(z) for all z∈Rn and (ii) is proved.


## 3.1. Approximate Primal-Dual Track

Given a positive scalar parameterμ, the proximal point function depending on f is defined by(3.1)pμ(x)∶=argmin⁡p∈Rn{f(p)+12μ‖p-x‖2},x∈Rn,
where ∥·∥ stands for the Euclidean norm. It has the property: gμ(x)∶=μ(x-pμ(x))∈∂f(pμ(x)).Similarly to the definition of primal track, we define the approximate primal track.Definition 3.1.
For anyɛ>0, μ=μ(x)>0, we say that Θ(u)=x¯+u⊕v(u) is an approximate primal track leading to x¯, a minimizer of f, if for all u∈Rdim𝒰 small enough, it satisfies the following:(i)
Θ(uμ(x))=x¯+uμ(x)⊕v(uμ(x)), where uμ(x)=(pμ(x)-x¯)𝒰;(ii)
v:Rdim𝒰→Rdim𝒱 is a C2-function satisfying V¯v∈Wg¯(u) for all g¯ satisfies (2.1);(iii)
the JacobianJΘ(u) is a basis matrix for 𝒱(Θ(u))⊥;(iv)
the particular𝒰-Lagrangian L0(u) is a C2-function.Accordingly, we have the approximate dual track denoted byΓ(u) corresponding to the approximate primal track. More precisely,
(3.2)Γ(u)=argmin⁡⁡{‖g‖2:f(x)≥f̃(Θ(u))+〈g,x-Θ(u)〉}.In fact, ifɛ=0, the approximate primal-dual track is exactly the primal-dual track shown in [8].The next lemma addresses that making an approximate𝒱-step in Algorithm 2.6 essentially amounts to finding a corresponding approximate primal track point.Lemma 3.2.
LetΘ(uμ(x)) be an approximate primal track leading to x¯, a minimizer of f, and let H¯∶=∇2L0(0). Then for all u sufficiently small Θ(uμ(x)) is the unique minimizer of f on the affine set Θ(uμ(x))+𝒱(Θ(uμ(x))).Proof.
SinceJΘ(u) is a basis for 𝒱(Θ(u))⊥, Theorem  3.4 in [10] with ℬ𝒰(u)=JΘ(u) gives the result.


## 3.2. The Proximal Bundle-Type Subroutine with Inexact Data

Throughout this section, we make the following assumption: at each given pointx∈Rn, and for ɛ≥0, we can find some f̃(x)∈R and g(x)∈Rn satisfying
(3.3)f̃(x)∈[f(x)-ɛ,f(x)],f(ζ)≥f(x)+〈g(x),ζ-x〉-ɛ¯,∀ζ∈Rn,
where ɛ¯=f(x)-f̃(x). At the same time, it can be ensured that
(3.4)f̃j⟶f̃kifyj⟶xk,
where f̃j∈[f(yj)-ɛk,f(yj)] and f̃k∈[f(xk)-ɛk,f(xk)] for given ɛk>0. The condition (3.3) means that g(x)∈∂ɛ¯f(x). This setting is realistic in many applications; see [11].The bundle method includes two phases. (i) The first phase makes use of the information(xk,f̃k,gk),(xk-1,f̃k-1,gk-1),…,(x1,f̃1,g1) in bundles to establish a polyhedral approximation of f at the actual iterate xk. (ii) Due to the kinky structure of f, the model is possibly not precise for approximation f. Then, more information around the actual iterate xk is mobilized to obtain a more reliable model. Feature (i) leads to the following approximation of f at xk. Let Ik denote the index set at the kth iteration with each j∈Ik representing (yj,f̃j,gj), where f̃j and gj satisfy(3.5)f̃j∈[f(yj)-ɛk,f(yj)],f(x)≥f̃j+〈gj,x-yj〉,∀x∈Rn,
for given ɛk>0. From the choices of f̃j and gj, we have that, for all x∈Rn and for all j∈Ik,(3.6)f(x)≥f̃j+〈gj,x-yj〉=f̃k+gjT(x-xk)+ɛk-αk,j,
where(3.7)αk,j=α(xk,yj)=f̃k-f̃j-gjT(xk-yj)+ɛk.On the basis of the above observation, we attempt to explore the possibility of utilizing the approximate subgradient and approximate function values instead of the exact ones. We approximatef at xk from below by a piecewise linear convex function φ of the form:(3.8)φ(z)∶=f̃k+max⁡j∈Ik⁡{gjT(z-xk)-αk,j}+ɛk.Since (3.8) becomes more and more crude if an approximation of f is farther away from xk, we add the proximal term (1/2)μ∥p-xk∥2,μ>0, to it. To approximate an proximal point, we solve the first quadratic programming subproblem
(3.9)min⁡r+12μ‖p-xk‖2s.t.r≥f̃k+gjT(p-xk)-αk,j+ɛk,j∈Ik.
Its corresponding dual problem is(3.10)min⁡12μ‖∑j∈Ikλjgj‖2+∑j∈Ikλjαk,js.t.∑j∈Ikλj=1,λj≥0,j∈Ik.
Let (r̂,p̂) and λ̂=(λ̂1,…,λ̂|Ik|) denote the optimal solution of (3.9) and (3.10), then it is easily seen that(3.11)r̂=φ(p̂),p̂=xk-1μĝ,whereĝ∶=∑j∈Ikλ̂jgj.
In addition, λ̂j=0 for all j∈Ik such that r>f̃k+gjT(p̂-xk)-αk,j+ɛk and(3.12)φ(p̂)=f̃k+∑j∈Ikλ̂j[gjT(p̂-xk)-αk,j+ɛk]=f̃k-∑j∈Ikλ̂jαk,j+ɛk-1μ‖ĝ‖2.
The vector p̂ is an estimate of an approximate proximal point. Hence, it approximates an approximate primal track point when the latter exists. To proceed further we let yj+∶=p̂ and compute f̃(p̂), ê∶=f̃(p̂)-φ(p̂)=f̃(p̂)-r̂, and gj+ satisfying f(z)≥f̃(p̂)+〈gj+,z-p̂〉,forallz∈Rn.An approximate dual path point, denoted byŝ, is constructed by solving a second quadratic problem, which depends on a new index set(3.13)Îk∶={j∈Ik:r̂=f̃k+gjT(p̂-xk)-αk,j+ɛk}∪{j+}.
The second quadratic programming problem is(3.14)min⁡r+12‖p-xk‖2s.t.r≥gjT(p-xk),j∈Îk.
It has a dual problem(3.15)min⁡12‖∑j∈Îkλjgj‖2s.t.∑j∈Îkλj=1,λj≥0,j∈Îk.
Similar to (3.11), the respective solutions, denoted by (r¯,p¯) and λ¯, satisfy(3.16)r¯=φ(p¯),p¯-xk=-ŝ,whereŝ=∑j∈Îkλ¯jgj.Givenσ∈(0,1/2], the proximal bundle subprocedure is terminated and p̂ is declared to be an approximation of pμ(xk) if(3.17)ê≤σμ‖ŝ‖2.
Otherwise, Ik above is replaced by Îk, and new iterate data are computed by solving updated subproblems (3.9) and (3.14). This update, appending (αk,j+,gj+) to active data at (3.9), ensures convergence to a minimizing point x¯ in case of nontermination.Remark 3.3.
From the talking above, the following results are true:(i)
ŝ=argmin{∥s∥2:s∈co{gj:j∈Îk}};(ii)
sincepμ(x) is an approximate primal track point Θ(uμ(x)) approximated by p̂ and co{gj:j∈Îk} approximates co{g:f(x)≥f̃(Θ(u))+〈g,x-Θ(u)〉}, from (3.2) the corresponding Γ(uμ(x)) is estimated by ŝ;(iii)
we can obtain theÛ by means of the following iteration.Let(3.18)Îkact∶={j∈Îk:r¯=gjT(p¯-x)}.
Then, from (3.16), r¯=-gjTŝ,j∈Îkact, so
(3.19)(gj-gl)Tŝ=0,
for all such j and for a fixed l∈Îkact. Define a full column rank matrix V̂ by choosing the largest number of indices j satisfying (3.19) such that the corresponding vectors gj-gl are linearly independent and by letting these vectors be the columns of V̂. Then let Û be a matrix whose columns form an orthonormal basis for the null space of V̂T with Û=I if V̂ is vacuous.Theorem 3.4.
At thekth iteration, the above proximal bundle subprocedure satisfies the following:(i)
gj∈∂ɛ¯+êf(p̂),j∈Îk, where ɛ¯=f(p̂)-f̃(p̂) and f̃(p̂)∈[f(p̂)-ɛk,f(p̂)];(ii)
ŝ∈∂ɛ¯+êf(p̂) and ĝ∈∂ɛ¯+êf(p̂);(iii)
μ∥p̂-pμ(xk)∥2≤ɛ¯+ê;(iv)
∥ŝ∥≤∥ĝ∥, where ĝ=μ(xk-p̂);(v)
for any parameterm∈(0,1), (3.17) implies(3.20)f̃(p̂)-f̃k≤-m2μ‖ĝ‖2+ɛk.Proof.
(i) Sincegj+ satisfies f(z)≥f̃(p̂)+〈gj+,z-p̂〉 and ê=f̃(p̂)-φ(p̂)≥0, gj+ satisfies
(3.21)f(z)≥f̃(p̂)+〈gj+,z-p̂〉-ê=f(p̂)+〈gj+,z-p̂〉-ê-ɛ¯,
where ɛ¯=f(p̂)-f̃(p̂), so the result of item (i) holds for j=j+. From the definition of p̂,r̂, and Îk we have that for all j≠j+ in Îk(3.22)φ(p̂)=r̂=f̃k+gjT(p̂-xk)-αk,j+ɛk,
so for all such j,
(3.23)ê=f̃(p̂)-φ(p̂)=f̃(p̂)-f̃k-gjT(p̂-xk)+αk,j-ɛk.
In addition,
(3.24)f(z)≥f̃k+gjT(z-xk)-αk,j+ɛk,z∈Rn.
Adding 0=ê-ê to this inequality gives
(3.25)f(z)≥f̃k+gjT(z-xk)+ɛk-αk,j+ê-ê=f̃(p̂)+gjT(z-p̂)-ê=f(p̂)+gjT(z-p̂)-ê-ɛ¯,∀z∈Rn,
which means that gj∈∂ɛ¯+êf(p̂) for j+≠j∈Îk.
(ii) Multiplying each inequality in (3.25) by its corresponding multiplier λ¯j≥0 and summing these inequalities, we have
(3.26)∑j∈Îkλ¯jf(z)≥∑j∈Îkλ¯jf(p̂)+∑j∈Îkλ¯jgjT(z-p̂)-∑j∈Îkλ¯jê-∑j∈Îkλ¯jɛ¯,∀z∈Rn.
Using the definition of ŝ from (3.16) and the fact that ∑j∈Îkλ¯j=1 gives
(3.27)f(z)≥f(p̂)+ŝT(z-p̂)-ê-ɛ¯,∀z∈Rn,
which means that ŝ∈∂ɛ¯+êf(p̂). In a similar manner, this time using the multipliers λ̂j that solve dual problem (3.10) and define ĝ in (3.11), together with λ̂j+∶=0, obtains the result.
(iii) Sincegμ∈∂f(pμ(xk)), we have
(3.28)f(pμ(xk))≤f(p̂)-gμ(xk)T(p̂-pμ(xk)).
From (ii): ĝ∈∂ɛ¯+êf(p̂), we get
(3.29)f(pμ(xk))≥f(p̂)+ĝT(pμ(xk)-p̂)-ɛ¯-ê.
Therefore,
(3.30)f(p̂)+ĝT(pμ(xk)-p̂)-ɛ¯-ê≤f(pμ(xk))≤f(p̂)-gμ(xk)T(p̂-pμ(xk)),
that is, (ĝ-gμ(xk))T(pμ(xk)-p̂)-ɛ¯-ê≤0. Then, since the expression for ĝ from (3.11) written in the form
(3.31)ĝ=-μ(p̂-xk),
combined with gμ(xk)=μ(xk-pμ(xk)) implies that ĝ-gμ(xk)=μ(pμ(xk)-p̂), we obtain item (iii).
(iv) From (3.10), (3.11), (3.31), and the definition of Îk, we have that μ(xk-p̂)=ĝ is in the convex hull of {gj,j∈Îk}. We obtain the result by virtue of the minimum norm property of ŝ.
(v) Sinceσ≤1/2 and m∈(0,1), we have σ≤1-(m/2). Thus if (3.17) holds then ê≤[(1-(m/2))/μ]∥ŝ∥2. Together with the definition of ê, (3.12) and the nonnegativity of λ̂jαj gives
(3.32)f̃(p̂)-f̃k=ê+φ(p̂)-f̃k=ê-∑j∈Ikλ̂jαk,j-1μ‖ĝ‖2+ɛk≤ê-1μ‖ĝ‖2+ɛk≤[(1-(m/2))μ]‖ŝ‖2-1μ‖ĝ‖2+ɛk.
Finally, combing this inequality with item (iv) gives (3.20).


## 3.3. Approximate Decomposition Algorithm and Convergence Analysis

Substituting the approximate𝒱-step in Algorithm 2.6 with proximal bundle-type subroutine, we present an approximate decomposition algorithm as follows. Afterwards a detailed convergence analysis is given. The main statement comprises the fact that each cluster point of the sequence of iterates generated by the algorithm is an optimal solution.Algorithm 3.5.
Choose a starting pointp0∈Rn and positive parameters η,ɛ0,μ̲,τ, and m with τ<1, m<1.
Step 0.
Computeg0 satisfying f(z)≥f̃(p0)+〈g0,z-p0〉, where f̃(p0)∈[f(p0)-ɛ0,f(p0)]. Let U0 be a matrix with orthonormal n-dimensional columns estimating an optimal 𝒰-basis. Set s0=g0 and k∶=0.
Step 1.
Stop if∥sk∥2≤η.
Step 2.
Choose annk×nk positive definite matrix Hk, where nk is the number of columns of Uk.
Step 3.
Compute an approximate𝒰-Newton step by solving the linear system
(3.33)HkΔuk=-UkTsk.
Set xk+1′∶=pk+UkΔuk.
Step 4.
Chooseμk+1>μ̲,σk+1∈(0,1/2], initialize Ik, and run the bundle subprocedure with x=xk+1′. Compute recursively, and set (ek+1′,pk+1′,sk+1′,Uk+1′)∶=(ê,p̂,ŝ,Û).
Step 5.
If(3.34)f̃(pk+1′)-f̃(pk)≤-m2μk+1‖sk+1′‖2+ɛk+1,
then set
(3.35)(xk+1,ek+1,pk+1,sk+1,Uk+1,ɛk+1)∶=(xk+1′,ek+1′,pk+1′,sk+1′,Uk+1′,τɛk).
Otherwise, execute a line search
(3.36)xk+1∶=argmin{f̃(pk),f̃(pk+1′)},
reinitialize Ik, and rerun the bundle subroutine with x=xk+1, to find new values for (ê,p̂,ŝ,Û), then set (ek+1,pk+1,sk+1,Uk+1,ɛk+1)=(ê,p̂,ŝ,Û,τɛk).
Step 6.
Replacek by k+1 and go to Step 1.Remark 3.6.
In this algorithm,{ɛk}k=0∞↓0. If {ɛk}k=0∞≡0, this algorithm is the same as Algorithm 6 in [8]. However, this algorithm uses proximal bundle-type subroutine which can deal with the approximate subgradients and the approximate function values.Theorem 3.7.
One of the following two cases is true:(i)
if the proximal bundle procedure in Algorithm3.5  does not terminate, that is, if (3.17) never hold, then the sequence of p̂-values converges to pμ(x) and pμ(x) is a minimizer of f;(ii)
if the procedure terminates withŝ=0, then the corresponding p̂ equals pμ(x) and is a minimizer of f.Proof.
By ([12], Prop. 4.3), if this procedure does not terminate then it generates an infinite sequence of ê-values and ɛ¯-value converging to zero. Since (3.17) does not hold, the sequence of ∥ŝ∥-values also converges to 0. Thus, item (iii) in Theorem 3.4 implies that {p̂}→pμ(x). And Theorem 3.4 (ii) gives
(3.37)f(z)≥f(p̂)+ŝT(z-p̂)-(ê+ɛ̂),z∈Rn.
By the continuity of f, this becomes
(3.38)f(z)≥f(pμ(x)),z∈Rn.
The termination case with ŝ=0 follows in a similar manner, since (3.17) implies ê=0 in this case.The next theorem establishes the convergence of Algorithm3.5, and the proof of which is similar to Theorem  9 in [8].Theorem 3.8.
Suppose that the sequence{μk} in Algorithm 3.5  is bounded above by μ¯. Then the following hold:(i)
the sequence{f̃(pk)} is decreasing and either {f̃(pk)}→-∞ or {∥sk∥} and {ek} both converge to 0;(ii)
iff is bounded from below, then any accumulation point of {pk} is a minimizers of f.Proof.
In this paper, the inequalities of (3.15), (3.16), and (3.17) in [8] become
(3.39)f̃(pk+1)-f̃(pk)≤-m2μk+1‖sk+1‖2,(3.40)f(z)≥f(pk)+skT(z-pk)-ɛpk-ek,∀z∈Rn,whereɛpk=f(pk)-f̃(pk),(3.41)ek≤σkμk‖sk‖2,
since ∥sk∥≠0, (3.39) implies that {f̃(pk)} is decreasing. Suppose {f̃(pk)}↛-∞. Then summing (3.39) over k and using the fact that m/2μk≥m/2μ¯ for all k implies that {∥sk∥}→0. Then (3.41) with σk≤1/2 and μk≥μ̲>0 implies that {ek}→0, which establishes (i).
Now supposef is bounded from below and p¯ is any accumulation point of {pk}. Then, because {∥sk∥}, {ek}, and {ɛpk} converge to 0, (3.40) together with the continuity of f implies that f(p¯)≤f(z) for all z∈Rn and (ii) is proved.


## 4. An Illustrated Numerical Example

We test some examples in this section to validate the effectiveness of the proposed algorithm. The platform is Matlab R2009a, Intel Pentium(R) Dual CPU T2390 1.87 GHz. All test examples are of the form(4.1)f=max⁡i∈Ifi,
where I is finite and each fi is C2 on Rn.For our runs we used the following examples:(i)
F2d: the objective function is given in [8], defined for x∈Rn by(4.2)F2d(x)∶=max⁡⁡{12(x12+x22)-x2,x2};(ii)
F3d-Uv: four functions of three variables, where v=3,2,1,0 denotes the corresponding dimension of the 𝒰-subspace. Given e∶=(0,1,1)T and four parameter vectors βv∈R4, for x∈R3(4.3)F3d-Uv(x)∶=max⁡⁡{12(x12+x22+0.1x32)-eTx-β1v,x12-3x1-β2v,x2-β3v,x2-β4v},
where β3∶=(-5.5,10,11,20),β2∶=(-5,10,0,10),β1∶=(0,10,0,0), and β0∶=(0.5,-2,0,0).In Table1, we show some relevant data for the problems, including the dimensions of 𝒱 and 𝒰, the (known) optimal values and solutions, and the starting points.Table 1
Problem data.
Problemdimdim-𝒱dim-𝒰x*fx*x0F2d211(0 0)0(0.9, 1.9)F3d-U3303(0 1 10)0(100, 34, −90)F3d-U2312(0 0 10)0(100, 33, −90)F3d-U1321(0 −1.741657 10)−1.741657(100, 33, −100)F3d-U0330(1.5 −0.442695 9.962006)−0.25(101, 33, −100)The italic data in Table1 is calculated by our algorithms.We calculate anɛ-subgradient at x by using the method in [13]: gɛ(x)=λg(x)+(1-λ)g(x1), where g(x) is a subgradient at x and g(x1) is a subgradient at a point x1 such that 0<α0(x,x1)=f(x)-f(x1)-g(x1)T(x-x1)≤ɛ. Here x1∈Br(x)={z∈Rn∣∥z-x∥≤r} and λ∈[0,1] are randomly chosen. The approximate function value f̃(x) is randomly taken out from the interval [f(x)-ɛ,f(x)]. The radius r is adjusted iteratively in the following way: If we find the linearization error α0(x,x1)>ɛ then r is reduced by a multiple smaller than one. On the other hand, if α0(x,x1) is significantly smaller than ɛ, then r is increased by a multiple greater than one. When sk=ŝ in the algorithm, then 𝒰-Hessian at x is computed in the following form: Hk=UkT(∑j∈ℬ̂λ¯jHj)Uk, where Hj=∇2fij(yj), ij is an active index such that fij(yj)=f(yj),λ¯j correspond to ŝ via (3.16).The parameters have valuesη=1.0×10-4, ɛ0=1.0×10-4, m=1.0×10-1, τ=1.0×10-1, and U0 equal to the n×n identity matrix. As for σk,μk, one can refer to [8].Table2 shows the results of Algorithm 3.5 for these examples, compared with Algorithm  6 in [8]. Number of f/g denotes the number of evaluation of the function and subgradient (ɛ-subgradient) in Algorithm 6 and Algorithm 3.5. x is the calculated solution, |fx-fx*| stands for the difference between the function values at x and x*.Table 2
Numerical results of UV-decomposition algorithm with inexact data.
Algorithm 6Algorithm3.5F2d#f/g2834x(0.000 0.000)(0.000 0.000)|fx-fx*|0.000E01.753E-10F3d-U3#f/g1132x(0.000 1.000 10.000)(0.000 1.000 10.000)|fx-fx*|0.000E02.248E-13F3d-U2#f/g3243x(0.000 −0.000 10.000)(0.000 0.000 10.000)|fx-fx*|0.000E01.275E-10F3d-U1#f/g****33x****(−0.0000 −1.742 10.000)|fx-fx*|****7.50E-15F3d-U0#f/g3144x(1.500 −0.425 10.000)(1.500 −0.443 9.962)|fx-fx*|8.771E-112.908E-11It is shown in Table2 that we obtain quite accurate solutions by Algorithm 3.5 with inexact data costing a slightly more evaluation number than that with exact data. One noticeable exceptional occurs in the example F3d-U1; it seems that the decomposition algorithm is sensible with exact data, but is more stable when applying inexact data (function values and subgradients). This favorable results demonstrate that it is suitable to use approximate decomposition algorithm to solve (1.1) numerically.



---

*Source: 215160-2011-12-22.xml*