An implementable algorithm for solving a nonsmooth convex optimization problem is proposed by combining Moreau-Yosida regularization and bundle and quasi-Newton ideas. In contrast with quasi-Newton bundle methods of Mifflin et al. (1998), we only assume that the values of the objective function and its subgradients are evaluated approximately, which makes the method easier to implement. Under some reasonable assumptions, the proposed method is shown to have a Q-superlinear rate of convergence.

1. Introduction

In this paper we are concerned with the unconstrained minimization of a real-valued, convex function f : Rⁿ → R, namely,

()

and in general f is nondifferentiable. A number of attempts have been made to obtain convergent algorithms for solving (1). Fukushima and Qi [1] propose an algorithm for solving (1) under semismoothness and regularity assumptions. The proposed algorithm is shown to have a Q-superlinear rate of convergence. An implementable BFGS method for general nonsmooth problems is presented by Rauf and Fukushima [2], and global convergence is obtained based on the assumption of strong convexity. A superlinearly convergent method for (1) is proposed by Qi and Chen [3], but it requires the semismoothness condition. He [4] obtains a globally convergent algorithm for convex constrained minimization problems under certain regularity and uniform continuity assumptions. Among methods for nonsmooth optimization problems, some have superlinear rate of convergence, for instance, see Mifflin and Sagastizábal [5] and Lemaréchal et al. [6]. They propose two conceptual algorithms with superlinear convergence for minimizing a class of convex functions, and the latter demands that the objective function f should be differentiable in a certain space U (the subspace along which ∂f(p) has 0 breadth at a given point p), but sometimes it is difficult to decompose the space. Besides these methods mentioned above, there is a quasi-Newton bundle type method proposed by Mifflin et al. [7] it has superlinear rate of convergence, but the exact values of the objective function and its subgradients are required. In this paper, we present an implementable algorithm by using bundle and quasi-Newton ideas and Moreau-Yosida regularization, and the proposed algorithm can be shown to have a superlinear rate of convergence. An obvious advantage of the proposed algorithm lies in the fact that we only need the approximate values of the objective function and its subgradients.

It is well known that (1) can be solved by means of the Moreau-Yosida regularization F : Rⁿ → R of f, which is defined by

()

where λ is a fixed positive parameter and ∥·∥ denotes the Euclidean norm or its induced matrix norm on R^n×n. The problem of minimizing F(x), that is,

()

is equivalent to (1) in the sense that x ∈ Rⁿ solves (1) if and only if it solves (3), see Hiriart-Urruty and Lemaréchal [8]. The problem (3) has a remarkable feature that the objective function F is a differentiable convex function, even though f is nondifferentiable. Moreover F has a Lipschitz continuous gradient

()

where p(x) is the unique minimizer of (2) and ∂f is the subdifferential mapping of f. Hence, by Rademacher’s theorem, G is differentiable almost everywhere and the set

()

is nonempty and bounded for each x. We say G is BD-regular at x if all matrices D ∈ ∂_BG(x) are nonsingular. It is reasonable to pay more attention to the problem (3) since F has such good properties. However, because the Moreau-Yosida regularization itself is defined through a minimization problem involving f, the exact values of F and its gradient G at an arbitrary point x are difficult or even impossible to compute in general. Therefore, we attempt to explore the possibility of utilizing the approximations of these values.

Several attempts have been made to combine quasi-Newton idea with Moreau-Yosida regularization to solve (1). For related works on this subject, see Chen and Fukushima [9] and Mifflin [10]. In particular, Mifflin et al. [7] consider using bundle ideas to approximate linearly the values of f in order to approximate F in which the exact values of f and one of its subgradients g at some points are needed. In this paper we assume that for given x ∈ Rⁿ and ε ≥ 0, we can find some

and g^a(x, ε) ∈ Rⁿ such that

()

which means that g^a(x, ε) ∈ ∂_εf(x). This setting is realistic in many applications, see Kiwiel [11]. Let us see some examples. Assume that f is strongly convex with modulus μ > 0, that is,

()

and that f(x) = w(v(x)) with v : Rⁿ → R^m continuously differentiable and w : R^m → R convex. By the chain rule we have

. Now assume that we have an approximation ∇_hv(x) of ∇v(x) such that ∥ ∇_hv(x)−∇v(x) ∥≤κ(h), h > 0. Such an approximation may be obtained by using finite differences. In this case, typically κ(h) → 0 for h → 0. Let

. Then, we have

()

for all x, z ∈ Rⁿ and

. Some simple manipulations show that

()

By the definition of ξ, the bound ε_h depends on x, we obtain

()

From the local boundedness of ∂w(v(x)), we infer that ε_h > 0 is locally bounded. Thus, g_h(x) is an ε_h-subgradient of f at x, see Hintermüller [12]. As for the approximate function values, if f is a max-type function of the form

()

where each ϕ_u : Rⁿ → R is convex and U is an infinite set, then it may be impossible to calculate f(x). However, for any positive ε one can usually find in finite time an ε-solution to the maximization problem (11), that is, an element u_ε ∈ U satisfying

. Then one may set

. On the other hand, in some applications, calculating u_ε for a prescribed ε ≥ 0 may require much less work than computing u₀. This is, for instance, the case when the maximization problem (11) involves solving a linear or discrete programming problem by the methods of Gabasov and Kirilova [13]. Some people have tried to solve (1) by assuming the values of the objective function, and its subgradients can only be computed approximately. For example, Solodov [14] considers the proximal form of a bundle algorithm for (1), assuming the values of the function and its subgradients are evaluated approximately, and it is shown how these approximations should be controlled in order to satisfy the desired optimality tolerance. Kiwiel [15] proposes an algorithm for (1), and the algorithm utilizes the approximation evaluations of the objective function and its subgradients; global convergence of the method is obtained. Kiwiel [11] introduces another method for (1); it requires only the approximate evaluations of f and its ε-subgradients, and this method converges globally. It is in evidence that bundle methods with superlinear convergence for solving (1) by using approximate values of the objective and its subgradients are seldom obtained. Compared with the methods mentioned above, the method proposed in this paper is not only implementable but also has a superlinear rate of convergence under some additional assumptions, and it should be noted that we only use the approximate values of the objective function and its subgradients which makes the algorithm easier to implement.

Some notations are listed below for presenting the algorithm.

(i)
∂f(x) = {ξ ∈ Rⁿ∣f(z) ≥ f(x) + ξ^T(z − x), ∀ z ∈ Rⁿ}, the subdifferential of f at x, and each such ξ is called a subgradient of f at x.
(ii)
∂_εf(x) = {η ∈ Rⁿ∣f(z) ≥ f(x) + η^T(z − x) − ε}, the ε-subdifferential of f at x, and each such η is called an ε-subgradient of f at x.
(iii)
, the unique minimizer of (2).
(iv)
G(x) = λ⁻¹(x − p(x)), the gradient of F at x.

This paper is organized as follows: in Section 2, to approximate the unique minimizer p(x) of (2), we introduce the bundle idea, which uses approximate values of the objective function and its subgradients. The approximate quasi-Newton bundle-type algorithm is presented in Section 3. In the last section, we prove the global convergence and, under additional assumptions, Q-superlinear convergence of the proposed algorithm.

2. The Approximation of p(x)

Let x = x^k and s = z − x^k, where x^k is the current iterate point of AQNBT algorithm presented in Section 3, then (13) has the form

()

Now we consider approximating f(x^k + s) by using the bundle idea. Suppose we have a bundle J^k generated sequentially starting from x^k and possibly a subset of the previous set used to generate x^k. The bundle includes the data

, i ∈ J^k, where zⁱ ∈ Rⁿ,

, and g^a(zⁱ, ε_i) ∈ Rⁿ satisfy

()

Suppose that the elements in J^k can be arranged according to the order of their entering the bundle. Without loss of generality we may suppose J^k = {1, …, j}. ε_i is updated by the rule ε_i+1 = γε_i, 0 < γ < 1, i ∈ J^k. The condition (13) means

, i ∈ J^k. By using the data in the bundle we construct a polyhedral function f_a(x^k + s) defined by

()

Obviously f_a(x^k + s) is a lower approximation of f(x^k + s), so f_a(x^k + s) ≤ f(x^k + s). We define a linearization error by

()

where

satisfies

()

Then f_a(x^k + s) can be written as

()

Let

()

The problem (18) can be dealt with by solving the following quadratic programming:

()

As iterations go along, the number of elements in bundle J^k increases. When the size of the bundle becomes too big, it may cause serious computational difficulties in the form of unbounded storage requirement. To overcome these difficulties, it is necessary to compress the bundle and clean the model. Wolfe [16] and Lemaréchal [17], for the first time, introduce the aggregation strategy, which requires storing only a limited number of subgradients, see Kiwiel and Mifflin [18–20]. Aggregation strategy is the synthesis mechanism that condenses the essential information of the bundle into one single couple

(defined below). The corresponding affine function, inserted in the model when there is compression, is called aggregate linearization (defined below). This function summarizes all the information generated up to iteration k. Suppose J_max is the upper bound of the number of elements in J^k, k = 1,2, …. If |J^k| reaches the prescribed J_max, two or more of those elements are deleted from the bundle J^k; that is, two or more linear pieces in the constraints of (19) are discarded (notice that different selections of discarded linear pieces may result in different speed of convergence), and introduce the aggregate linearization associated with the aggregate ε-subgradient and linearization error into bundle. Define the aggregate linearization as

()

where

. Multiplier

is the optimal solution of dual problem for (19), see Solodov [14]. By doing so, the surrogate aggregate linearization maintains the information of the deleted linear pieces and at the same time the problem (19) is manageable since the number of the elements in J^k is limited. Suppose s(x^k) solves the problem (19), and let p^a(x^k) = x^k + s(x^k) be an approximation of p(x^k) and

. Let

()

where

is chosen to satisfy

()

The results stated below are fundamental and useful in the subsequent discussions.

(P1)
F_a(x^k) ≤ F(x^k) ≤ F^a(x^k).
(P2)
F^a(x^k) = F(x^k) if and only if p^a(x^k) = p(x^k) and .

Note that p(x^k) is the unique minimizer of (2) and (P1) and (P2) can be obtained by the definitions of F^a(x^k), F_a(x^k), and F(x^k).

(P3)
- (i)
  If we define , where g(zⁱ) ∈ ∂f(zⁱ), then F_a(x^k) → F_ea(x^k) as the new point z^j+1 = x^k + s(x^k) is appended into the bundle J^k infinitely.
- (ii)
  Let . if g^a(zⁱ, ε_i) = g(zⁱ) ∈ ∂f(zⁱ), then F_a(x^k) ≥ F_ea(x^k) − ε.

Because ε_i → 0 by the update rule ε_i+1 = γε_i, 0 < γ < 1, we have g^a(zⁱ, ε_i) → g(zⁱ) and

. Thus

, so F_ea(x^k) → F_a(x^k). It is easy to see that

≥

. Therefore,

≥ F_ea(x^k) − ε.

Let

()

We accept p^a(x^k) as an approximation of p(x^k) based on the following rule:

()

where m(x^k) and L are given positive numbers and m(x^k) is fixed during one bundling process; that is, m(x^k) depends on x^k, see Step 1 in AQNBT algorithm presented in Section 3. If (24) is not satisfied, we let z^j+1 = x^k + s(x^k) and ε_j+1 = γε_j, 0 < γ < 1, and take

and g^a(z^j+1, ε_j+1) ∈ Rⁿ satisfying

()

and then append a new piece

to (14), replace j by j + 1, and solve (19) for finding a new s(x^k) and a(x^k) to be tested in (24). If this bundle process does not terminate, we have the following conclusion.

(P4)
Suppose that x^k is not the minimizer of f. If (24) is never satisfied, then a(x^k) → 0 as the new point z^j+1 is appended into the bundle J^k infinitely.

Suppose that |J^k| = |{1,2, …, j}| = j < J_max. Define the functions ϕ and φ_j+1, j = 1,2, … by

()

Let z^j+1 be the unique minimizer of , and let z^j+2 be the unique minimizer of , where . Note that if |{1,2, …, j + 1}| = j + 1 < J_max, then let J^k+1 = {1,2, …, j + 1}, so φ_j+1(z^j+1) ≤ φ_j+2(z^j+2); if |{1,2, …, j + 1}| = j + 1 = J_max, delete at least two elements from {1,2, …, j + 1}, say q₁, q₂, and q₁ ≠ j + 1, q₂ ≠ j + 1, the order of the other elements in {1,2, …, j + 1} are left intact. Introduce an additional index associated with the aggregated ε-subgradient and linearization error into J^k+1 and let , so |J^k+1| = j < J_max. By adjusting λ appropriately, we can make sure that z^j+1 and z^j+2 are not far away from x^k. According to the proof of Proposition 3, see Fukushima [21], we find that ϕ(z^j) has limit, say ϕ^*, and φ_j+1(z^j+1) also converges to ϕ^* as j → ∞. By the definitions of F(x^k) and F^a(x^k) we have F_a(x^k) → F(x^k) and F^a(x^k) → F(x^k) as j → ∞, so a(x^k) → 0 as j → ∞.

In the next part we give the definition of G^a(x^k), which is the approximation of G(x^k),

()

and some properties of G^a(x^k) are discussed. It is easy to see that the approximation of G(x^k) is associated with F(x^k):

(P5)
.

By the strong convexity of ϕ(z), we have ϕ(p^a(x^k)) ≥ ϕ(p(x^k))+(2λ) ⁻¹ ∥ p(x^k) − p^a(x^k)∥². From the definitions of F^a(x^k) and p(x^k), we obtain

≥ f(p^a(x^k))+(2λ) ⁻¹ ∥ p^a(x^k) − x^k∥² = ϕ(p^a(x^k)) ≥ ϕ(p(x^k))+(2λ) ⁻¹ ∥ p(x^k) − p^a(x^k)∥² = F(x^k)+(2λ) ⁻¹ ∥ p(x^k) − p^a(x^k)∥². By (P1), (P5) holds.

By (P4) and (P5), we have the following (P6). In fact, (P6) says that the bundle subalgorithm for finding s(x^k) terminates in finite steps.

(P6)
If x^k does not minimize f, then we can find one solution s(x^k) of (18) such that (24) holds.

3. Approximate Quasi-Newton Bundle-Type Algorithm

For presenting the algorithm, we use the following notations: a_k = a(x^k), s^k = s(x^k), and m_k = m(x^k). Given positive numbers δ, υ, γ, and L such that 0 < δ < 1, 0 < υ < 1, 0 < γ < 1, and one symmetric n × n positive definite matrix N.

Approximate Quasi-Newton Bundle-Type Algorithm (AQNBT Alg):

Step 1 (initialization). Let x¹ be a starting point, and let B₁ be an n × n symmetric positive definite matrix. Let ε₁ and λ be positive numbers. Choose a sequence of positive numbers such that . Set k = 1. Find s¹ ∈ Rⁿ and a₁ such that

()

Let G^a(x¹) = −λ⁻¹s¹, z¹ = x¹, j = 1, and j be the running index of bundle subalgorithm.

Step 2 (finding a search direction). If ∥G^a(x^k)∥ = 0, stop with x^k optimal. Otherwise compute

()

Step 3 (line search). Starting with u = 1, let i_k be the smallest nonnegative integer u such that

()

where ε_u+1 = γε_u corresponds to the approximations F_a(x^k + υ^ud^k) and F^a(x^k + υ^ud^k) of F at x^k + υ^ud^k; F_a(x^k + υ^ud^k) satisfies

()

and s(x^k + υ^ud^k) is the solution of (19), in which x^k is replaced by x^k + υ^ud^k, and the expression of F^a(x^k + υ^ud^k) is similar to (21), but x is replaced by x^k + υ^ud^k. Set

and x^k+1 = x^k + t^kd^k.

Step 4 (computing the approximate gradient). Compute G^a(x^k+1) = −λ⁻¹s^k+1.

Step 5 (updating Bk). Let Δx^k = x^k+1 − x^k and Δg^k = G^a(x^k+1) − G^a(x^k). Set

()

Set k = k + 1, and go to Step 2.

End of AQNBT algorithm.

4. Convergence Analysis

In this section we prove the global convergence of the algorithm described in Section 3, and furthermore under the assumptions of semismoothness and regularity, we show that the proposed algorithm has a Q-superlinear convergence rate. Following the proof of Theorem 3, see Mifflin et al. [7], we can show that, at each iteration k, i_k is well defined, and hence the stepsize t^k > 0 can be determined finitely in Step 4. We assume the proposed algorithm does not terminate in finite steps, so the sequence is an infinite sequence. Since the sequence satisfies , there exists a constant W such that . Let D_a = {x ∈ Rⁿ∣F(x) ≤ F(x¹) + 2LW}. By making a slight change of the proof of Lemma 1, see Mifflin et al. [7], we have the following lemma.

Lemma 1. F(x^k+1) ≤ F(x^k) + L(m_k + m_k+1) for all k ≥ 1 and x^k ∈ D_a.

Theorem 2. Suppose f is bounded below and there exists a constant β such that

()

Then any accumulation point of {x^k} is an optimal solution of problem (1).

Proof. According to the first part of the proof of Theorem 3, see Mifflin et al., [7], we have lim _k→∞F(x^k) = F^*. Since m_k → 0, from (P1) we obtain a_k → 0 as k → ∞, and lim _k→∞F_a(x^k) = lim _k→∞F^a(x^k) = F^*. Thus

()

Let

be an arbitrary accumulation point of {x^k}, and let {x^k} _k∈K be a subsequence converging to

. By (P5) we have

()

Since

is bounded, we may suppose

()

for some

. Moreover we have

()

If lim inf _k→∞t^k > 0, then

. Otherwise, if lim inf _k→∞t^k = 0, by taking a subsequence if necessary we may assume t^k → 0 for k ∈ K. The definition of i_k in the line search rule gives

()

where

. So by (P1) we obtain

()

By taking the limit in (39) on the subsequence k ∈ K, we have

()

In view of (37), the last inequality also gives

. Since

and B_k is bounded, it follows from

that

()

Therefore,

is an optimal solution of problem (1).

In the next part, we focus our attention on establishing Q-superlinear convergence of the proposed algorithm.

Theorem 3. Suppose that the conditions of Theorem 2 hold and is an optimal solution of (1). Assume that G is BD-regular at . Then is the unique optimal solution of (1) and the entire sequence {x^k} converges to .

Proof. By the convexity and BD-regularity of G at , is the unique optimal solution of (3); for the proof, see Qi and Womersley [22]. So is also the unique optimal solution of (1). This implies that both f and F must have compact level sets. By Lemma 1 {x^k} has at least one accumulation point, and from Theorem 2 we know this accumulation point must be since is the unique solution of (1). Next following the proof of Theorem 5.1, see Fukushima and Qi [1], we can prove that the entire sequence {x^k} converges to .

The condition that the Lipschitz continuous gradient G of F is semismooth at the unique optimal solution of (1) is required in the next theorem. This condition is identified if f is the maximum of several affine functions or f satisfies the constant rank constraint qualification.

Theorem 4. Suppose that the conditions of Theorem 3 hold and G is semismooth at the unique optimal solution of (1). Suppose further that

(i)
,
(ii)
lim _k→∞dist (B_k, ∂_BG(x^k)) = 0,
(iii)
t^k ≡ 1, for all large k.

Then {x^k} converges to

Q-superlinearly.

Proof. Firstly we have {x^k} converges to by Theorem 3. Then by condition (i) and (P5), we have

()

By condition (ii), there is a

such that

()

Since G is semismooth at

, we have, according to Qi and Sun [13],

()

Notice that

, (42)–(44) and condition (iii), for all large k, we have

()

This establishes Q-superlinear convergence of {x^k} to

Condition (i) can be replaced by a more realistic condition without impairing the convergence result since a_k is chosen before x_k is generated. For condition (ii), Fukushima and Qi [1] suggest one of possible choices of B_k, we may expect B_k to provide a reasonable approximation to an element in ∂_BG(x^k), but it may be far from what we should approximate. There are some approaches to overcome this phenomenon, see Mifflin [10] and Qi and Chen [3]. For condition (iii) we can make sure that if the conditions of Theorem 4, except (iii), hold and 0 < δ < 1/2, then condition (iii) holds automatically.

Acknowledgment

This research was partially supported by the National Natural Science Foundation of China (Grants no. 11171049 and no. 11171138).

References

1 Fukushima M. and Qi L., A globally and superlinearly convergent algorithm for nonsmooth convex minimization, SIAM Journal on Optimization. (1996) 6, no. 4, 1106–1120, https://doi.org/10.1137/S1052623494278839, MR1416531, ZBL0868.90109.
10.1137/S1052623494278839
Web of Science® Google Scholar
2 Rauf A. I. and Fukushima M., Globally convergent BFGS method for nonsmooth convex optimization, Journal of Optimization Theory and Applications. (2000) 104, no. 3, 539–558, https://doi.org/10.1023/A:1004633524446, MR1760737, ZBL0986.90076.
10.1023/A:1004633524446
Web of Science® Google Scholar
3 Qi L. and Chen X., A preconditioning proximal Newton method for nondifferentiable convex optimization, Mathematical Programming. (1997) 76, no. 3, 411–429, https://doi.org/10.1016/S0025-5610(96)00054-8, MR1433964, ZBL0871.90065.
10.1007/BF02614391
Web of Science® Google Scholar
4 He Y. R., Minimizing and stationary sequences of convex constrained minimization problems, Journal of Optimization Theory and Applications. (2001) 111, no. 1, 137–153, https://doi.org/10.1023/A:1017575415432, MR1850682, ZBL0987.90067.
10.1023/A:1017575415432
Web of Science® Google Scholar
5 Mifflin R. and Sagastizábal C., A VU-proximal point algorithm for minimization, Numerical Optimization, 2002, Springer, Berlin, Germany, Universitext.
Google Scholar
6 Lemaréchal C., Oustry F., and Sagastizábal C., The U-Lagrangian of a convex function, Transactions of the American Mathematical Society. (2000) 352, no. 2, 711–729, https://doi.org/10.1090/S0002-9947-99-02243-6, MR1487623.
10.1090/S0002-9947-99-02243-6
Web of Science® Google Scholar
7 Mifflin R., Sun D., and Qi L., Quasi-Newton bundle-type methods for nondifferentiable convex optimization, SIAM Journal on Optimization. (1998) 8, no. 2, 583–603, https://doi.org/10.1137/S1052623496303329, MR1618547, ZBL0927.65074.
10.1137/S1052623496303329
Web of Science® Google Scholar
8 Hiriart-Urruty J. B. and Lemaréchal C., Convex Analysis and Minimization Algorithms, 1993, Springer, Berlin, Germany.
10.1007/978-3-662-02796-7
Google Scholar
9 Chen X. and Fukushima M., Proximal quasi-newton methods for nondifferentiable convex optimization, Applied Mathematics Report, 1995, no. 95/32, School of Mathematics, The University of New South Wales, Sydney, Australia.
Google Scholar
10 Mifflin R., A quasi-second-order proximal bundle algorithm, Mathematical Programming. (1996) 73, no. 1, 51–72, https://doi.org/10.1016/0025-5610(95)00053-4, MR1389668, ZBL0848.90100.
10.1007/BF02592098
Web of Science® Google Scholar
11 Kiwiel K. C., Approximations in proximal bundle methods and decomposition of convex programs, Journal of Optimization Theory and Applications. (1995) 84, no. 3, 529–548, https://doi.org/10.1007/BF02191984, MR1326074, ZBL0824.90110.
10.1007/BF02191984
Web of Science® Google Scholar
12 Hintermüller M., A proximal bundle method based on approximate subgradients, Computational Optimization and Applications. (2001) 20, no. 3, 245–266, https://doi.org/10.1023/A:1011259017643, MR1857057, ZBL1054.90053.
10.1023/A:1011259017643
Web of Science® Google Scholar
13 Gabasov R. and Kirilova F. M., Methods of Linear Programming, Part 3, SpecialProblems, 1980 (Russian), Izdatel'Stov BGU, Minsk, Belarus.
Google Scholar
14 Solodov M. V., On approximations with finite precision in bundle methods for nonsmooth optimization, Journal of Optimization Theory and Applications. (2003) 119, no. 1, 151–165, https://doi.org/10.1023/B:JOTA.0000005046.70410.02, MR2028443, ZBL1094.90046.
10.1023/B:JOTA.0000005046.70410.02
Web of Science® Google Scholar
15 Kiwiel K. C., An algorithm for nonsmooth convex minimization with errors, Mathematics of Computation. (1985) 45, no. 171, 173–180, https://doi.org/10.2307/2008055, MR790650, ZBL0584.65034.
10.1090/S0025-5718-1985-0790650-5
Web of Science® Google Scholar
16 Wolfe P., A method of conjugate subgradients for minimizing nondifferentiable functions, Mathematical Programming Study. (1975) 3, 145–173, MR0448896, ZBL0369.90093.
10.1007/BFb0120703
Google Scholar
17 Lemaréchal C., An extension of davidon methods to non differentiable problems, Mathematical Programming Study. (1975) 3, 95–109, MR0436586, ZBL0358.90051.
10.1007/BFb0120700
Google Scholar
18 Kiwiel K. C., A Variable Metric Method of Centres for Nonsmooth Minimization, 1981, International Institute for Applied Systems Analysis, Laxemnburg, Austria.
Google Scholar
19 Kiwiel K. C., Efficient algorithms for nonsmooth optimization and their applications [Ph.D. thesis], 1982, Department of Electronics, Technical University of Warsaw, Warsaw, Poland.
Google Scholar
20 Mifflin R., A modification and extension of Lemarechal′s algorithm for nonsmooth minimization, Mathematical Programming Study. (1982) 17, 77–90, MR654692, ZBL0476.65047.
10.1007/BFb0120960
Web of Science® Google Scholar
21 Fukushima M., A descent algorithm for nonsmooth convex optimization, Mathematical Programming. (1984) 30, no. 2, 163–175, https://doi.org/10.1007/BF02591883, MR758002, ZBL0545.90082.
10.1007/BF02591883
Web of Science® Google Scholar
22 Qi L. Q. and Womersley R. S., An SQP algorithm for extended linear-quadratic problems in stochastic programming, Annals of Operations Research. (1995) 56, 251–285, https://doi.org/10.1007/BF02031711, MR1339796, ZBL0835.90058.
10.1007/BF02031711
Web of Science® Google Scholar

All articles

An Approximate Quasi-Newton Bundle-Type Method for Nonsmooth Optimization

Abstract

1. Introduction

2. The Approximation of p(x)

3. Approximate Quasi-Newton Bundle-Type Algorithm

4. Convergence Analysis

Acknowledgment

References

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

An Approximate Quasi-Newton Bundle-Type Method for Nonsmooth Optimization

Abstract

1. Introduction

2. The Approximation of p(x)

3. Approximate Quasi-Newton Bundle-Type Algorithm

4. Convergence Analysis

Acknowledgment

References

References

Related

Information