Introduction

Consider the following optimization problem: (1) If the constrained set satisfies Φ = ℜⁿ, then Eq (1) is called unconstrained optimization; if Φ = {x ∣ l ≤ x ≤ u, x ∈ ℜⁿ}, where n is the number of variables and the vectors l and u represent the lower and upper bounds on the variables, then Eq (1) is called box-constrained optimization; and if Φ = {x ∣ h_i(x) = 0, g_j(x) ≤ 0, x ∈ ℜⁿ, i = 1, ⋯, r, j = 1, ⋯, k}, where r and k are positive integers, then Eq (1) is called normal constrained optimization. If the objective function f: ℜⁿ → ℜ^m is continuously differentiable, then Eq (1) is called smooth optimization; if f: ℜⁿ → ℜ^m is a nondifferentiable function, then Eq (1) is called nonsmooth optimization. For a given objective function f and constrained set Φ, Eq (1) will be called the corresponding optimization problem.

Optimization problems are encountered in many fields, including engineering, management, finance, medicine, and biology, and similarly, optimization models can be used in many fields (see [1–13]). At present, there are many efficient methods available for solving optimization problems [14–24]. However, many challenging optimization problems exist, for example, large-scale problems and nonsmooth problems. The workload increases greatly as the dimension of the problem increases, causing the required CPU time to become very long. For certain large-scale problems, a computer may fail to solve them. To address this issue, more efficient algorithms should be designed. It is well known that spectral gradient approaches, conjugate gradient (CG) techniques and limited-memory quasi-Newton methods can cope with large-scale optimization problems. CG methods in particular have been widely used in many practical large-scale optimization problems because of their simplicity and low memory requirements.

Nonsmooth problems are believed to be very difficult to solve, even when they are unconstrained. The direct application of smooth gradient-based methods to nonsmooth problems may lead to a failure in optimality conditions, convergence, or gradient approximation [25]. Haarala et al. (see, e.g., [26, 27]) presented limited-memory bundle methods for large-scale nonsmooth unconstrained and constrained minimization and demonstrated their application to test problems of up to one thousand variables in dimension. Karmitsa et al. [28] tested and compared various methods of both types as well as several methods that may be regarded as hybrids of these two approaches and/or others; the dimensions of the tested nonsmooth problems ranged from 20 to 4000, and the most effective method for large- and extra-large-scale problems was found to be that of [27]. Therefore, special tools for solving nonsmooth optimization problems are needed.

This paper is organized as follows. In the next section, the Hager and Zhang (HZ) CG method is presented, and a modified HZ (MHZ) CG formula is proposed. In Section 3, the application of the HZ and MHZ methods to large-scale nonsmooth problems is discussed, global convergence is established, and numerical experiments on nonsmooth problems are reported. In the last section, conclusions are presented. Throughout the paper, ‖⋅‖ denotes the Euclidean norm.

The HZ CG formula [29, 30] and a modification thereof

For convenience, we rewrite Eq (1) as the following special case: (2) where f: ℜⁿ → ℜ is continuously differentiable; Eq (2) is called an unconstrained optimization problem. CG methods are a class of effective line search methods for solving Eq (2), especially when the dimension n is large. The iterative formula for CG methods is defined as follows: (3) where x_k is the current point in the iteration, α_k > 0 is the step length, and d_k is the search direction; the latter is determined as (4) where g_k+1 = ∇f(x_k+1) is the gradient of f(x) at point x_k+1 and β_k ∈ ℜ is a scalar. The parameter β_k is chosen such that when the method is applied to minimize a strongly convex quadratic function, the directions d_k and d_k−1 are conjugate with respective to the Hessian of the quadratic function. Let where from [29] (5) with y_k = g_k+1 − g_k; we call this formula for [29] the HZ formula. If , then Eq (4) with satisfies (6) This method exhibits global convergence for the strongly convex function f. To obtain a similar result for a general nonlinear function, Hager and Zhang [30] proposed the formula where η > 0 is a constant; in their experiments, they set η = 0.01. This new parameter also has the property expressed in Eq (6).

Based on the formula for , if we let , we can obtain the more general formula (7) In this paper, we set where c ∈ (0, 1) is a scalar. It is easy to deduce that ; moreover, if , then Eq (7) is identical to the HZ formula. The modified formula has the following features:

(i) The new formula can overcome the shortcomings of the CG parameter β_k. If , it is not difficult to find that (8)

(ii) Another property of this formula is that it can ensure that the new direction d_k+1 in Eq (4) with belongs to a trust region without the need for any line search technique. By Eq (4), for , we obtain (9) By combining this result with Step 1 of Algorithm 2.2, we find that for all k.

(iii) If T_k ≠ 0, then the new direction d_k+1 in Eq (4) when possesses the following sufficient descent property: (10) which holds for all k. Now let us analyze this result. If k = 0, we have d₁ = −g₁ and satisfying Eq (10). For k ≥ 1, because T_k ≠ 0, multiplying Eq (4) by yields (11) Let and ; then, by the inequality , we have

Nonsmooth Convex Problems and Their Results

Consider the unconstrained convex optimization problem (12) where f: ℜⁿ → ℜ is a possibly nonsmooth convex function. For the special case that f is continuously differentiable, this optimization problem has been well studied for several decades. However, nonsmooth optimization problems of the form of Eq (12) also arise in many applications, such as image restoration [31] and optimal control [32]. The Moreau-Yosida regularization of f generates (13) where λ is a positive parameter; then, Eq (12) is equivalent to the following problem: (14) Let p(x) = argmin θ(z) and define a function Thus, p(x) is well defined and unique because the function θ(z) is strongly convex. Therefore, F(x) can be expressed as follows: F(x) possesses many known features (see, e.g., [33–35]). The generalized Jacobian of F(x) and its property of BD-regularity are demonstrated in [36, 37]. Here, we list some additional findings regarding the function F(x), as follows:

(i) x is an optimal solution to Eq (12) ⇔ ∇F(x) = 0, i.e., p(x) = x.

(ii) (15) where (16) is the gradient of F.

(iii) The set of generalized Jacobian matrices ∂_Bg(x) = {V ∈ ℜ^n×n: V = lim_{xk → x}∇g(x_k), x_k ∈ D_g} is nonempty and compact, where

Furthermore, every V ∈ ∂_Bg(x) is a symmetric positive semidefinite matrix for each x ∈ ℜⁿ because g is a gradient mapping of the convex function F.

(iv) There exist two constants, μ₁ > 0 and μ₂ > 0, and a neighborhood Ω of x that satisfy

Two algorithms for nonsmooth problems

Based on the above discussion, we present two algorithms for application to nonsmooth problems of the form Eq (14); afterward, we analyze the solution of Eq (12). In the following, unless otherwise noted, g_k = g(x_k) is defined as in Eq (16).

Algorithm 1 Algorithm 4.1.

Require:

 An initial point x₀ ∈ ℜⁿ, λ > 0, σ, η ∈ (0, 1), ρ ∈ (0, 1/2], ϵ ∈ [0, 1).

 Specify g₀ by solving the subproblem Eq (13);

 d₀ ← −g₀, k ← 0.

 while ‖g_k‖ > ϵ do

  Determine the step size α_k = max{ρ^j|j = 0, 1, 2, ⋯} satisfying the following Armijo line search condition (17)

  x_k+1 = x_k + α_k d_k;

  Compute g_k+1 by solving the subproblem Eq (13);

  if ‖g_k+1‖ ≤ ϵ then

   break.

  else

   Compute d_k as (18)

  end if

  x_k ← x_k+1, d_k ← d_k+1, k ← k + 1.

end while

Algorithm 4.2. Eq (18) of Algorithm 4.1 is replaced with the following: Compute d_k as (19) and let k: = k + 1, go back to Step 2.

The following assumptions are needed to ensure the global convergence of Algorithms 4.1 and 4.2.

Assumption 4.1. (i) F is bounded from below and the sequence {V_k} is bounded, namely, there exists a constant M > 0 such that (20)

(ii) g is BD-regular at x, namely, item (iv) in Section 3 above holds.

By Assumption 4.1, it is not difficult to deduce that there exists a constant M_* > 1 such that (21)

Lemma 1 The sequence {x_k} is generated by Algorithm 4.1 (or Algorithm 4.2). Let Assumption 4.1 hold; then, for sufficiently large k, there exists a constant α_* > 0 that satisfies (22)

Proof. Suppose that α_k satisfies the Armijo line search condition Eq (17). The proof is complete if α_k = 1 holds. Otherwise, let ; then, we have By performing a Taylor expansion, we obtain (23) where and the last inequality follows from Eq (20). By combining Eqs (21) and (23), we obtain (24) Thus, we find that Let , and the proof is complete.

Now, let us prove the global convergence of Algorithm 4.1.

Theorem 1 Suppose that the conditions in Lemma 1 hold. Then, we have (25) moreover, any accumulation point of x_k is an optimal solution of Eq (12).

Proof. Suppose that Eq (25) is not true. Then, there must exist two constants, ϵ₀ > 0 and k_* > 0, that satisfy (26) By combining , Eqs (17), (22) and (26), we obtain (27) Because F(x) is bounded from below for all k, it follows from Eq (27) that This contradicts Therefore, Eq (25) holds. Let x* be an accumulation point of {x_k} and, without loss of generality, suppose that there exists a subsequence {x_k}_K that satisfies (28) From Eq (28), we find that ‖g(x*)‖ = ‖∇F(x*)‖ = 0. Then, from property (i) of F(x) as given in Section 3, x* is an optimal solution of Eq (12). The proof is complete.

In a manner similar to Theorem 4.1 in [38], we can establish the linear convergence rate of Algorithm 4.1 (or Algorithm 4.2). Here, we simply state this property, as follows, but omit the proof.

Theorem 2 Let Assumptions 4.1 (i) and (ii) hold, and let x* be the unique solution of Eq (14). Then, there exist two constants b > 0 and r ∈ (0, 1) that satisfy (29) namely, the sequence {x_k} generated by Algorithm 4.1 (or Algorithm 4.2) linearly converges to x*.

Numerical results for nonsmooth problems

In this section, we present several numerical experiments using Algorithms 4.1 and 4.2 and a modified Polak-Ribière-Polyak conjugate gradient algorithm (called MPRP) [18]. It is well known that the CG method is very effective for large-scale smooth problems. We will show that these two algorithms are also applicable to large-scale nonsmooth problems. The nonsmooth academic test problems that are listed, along with their initial points, in Table 1 are described in [27], where “Problem” is the name of the test problem, “x₀” is the initial point, and the corresponding numbers of variables are also given, “f_ops” is the optimal value of the test problem. Problems 1-5 are convex functions, and the others are nonconvex functions. The detailed characteristics of these problems can be found in [27]. Because we wished to test the three considered methods for application to large-scale nonsmooth problems, problem dimensions of 5000, 10000, 50000, and 100000 were chosen. In our experiments, we found that problem 2 required a considerably amount of time to solve; therefore, we set its largest dimension to 50000.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 1. Test problems and their initial points and optimal value.

https://doi.org/10.1371/journal.pone.0164289.t001

Both algorithms were implemented using Fortran PowerStation 4.0 with double-precision arithmetic, and all experiments were run on a PC with a Core 2 Duo E7500 CPU @2.93 GHz with 2.00 GB of memory and the Windows XP operating system. The following parameters were chosen for Algorithms 4.1 and 4.2 and MPRP: σ = 0.8, ρ = 0.5, c = 0.01, ϵ_k = 1E − 15, and η = 0.01. We stopped the algorithms when the condition ‖g(x)‖ ≤ 1E − 5 or ∣F(x_k+1) − F(x_k)∣ ≤ 1E − 8 or |f(x_k) − f_ops| ≤ 1E − 4 was satisfied. If the number of iterations exceeded ten thousand, the program would also terminate. Because a line search cannot always ensure the descent condition , an uphill search direction may arise in real numerical experiments, which may cause the line search rule to fail. To avoid this condition, the step size α_k was accepted only if the search number in the line search was greater than five.

In the experiments, the subproblem Eq (13) was solved using the PRP CG method (called the sub-algorithm), and its numbers of iterations and function evaluations were added to those of Algorithm 4.1, Algorithm 4.2 or MPRP (called the main algorithm). In the sub-algorithm, if ‖∂f(x_k)‖ ≤ 1E − 4 or f(x_k+1) − f(x_k) + ‖∂f(x_k+1)‖² − ‖∂f(x_k)‖² ≤ 1E − 3 (see [39]) holds, where ∂f(x_k) is the subgradient of f(x) at point x_k, then the algorithm terminates. The sub-algorithm will also terminate when the iteration number exceeds ten. For the line search, the Armijo line search technique was used and the step length was accepted if the search number was greater than five. The columns in Tables 2, 3 and 4 have the following meanings:

1. Dim: the dimensions of problem.
2. NI: the total number of iterations.
3. NF: the number of function evaluations.
4. ‖g(x)‖: the norm of g(x) at the final iteration.
5. Time: the CPU time in seconds.
6. f_final: the value of f(x) at the final iteration.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 2. Test results for Algorithm 4.1.

https://doi.org/10.1371/journal.pone.0164289.t002

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 3. Test results for Algorithm 4.2.

https://doi.org/10.1371/journal.pone.0164289.t003

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 4. Test results for MPRP.

https://doi.org/10.1371/journal.pone.0164289.t004

From the above three tables, it is not difficult to see that Algorithm 4.1 is superior to Algorithm 4.2 and MPRP in terms of NI, NF, and ‖g(x)‖. Algorithm 4.1 yields smaller values of NI and NF when the program terminates; moreover, the value of ‖g(x)‖ is smaller than that for Algorithm 4.2 in most cases. However, we also note that our algorithms can efficient solve the 3000 dimensional(with maximum dimensional) case for problems 3, 4, 5 and 8, if we increase the dimensional, these algorithms fail to converge to good minima and become stuck at local. To directly illustrate the performances of these two methods, we used the tool developed by Dolan and Moré [40] to analyze their efficiencies in terms of the number of iterations, number of function evaluations, and CPU time. In the following, Figs 1, 2 and 3 represent the results presented in Tables 2, 3 and 4 in terms of NI, NF, and Time, respectively.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 1. Performance profiles of these methods (NI).

https://doi.org/10.1371/journal.pone.0164289.g001

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 2. Performance profiles of these methods (NF).

https://doi.org/10.1371/journal.pone.0164289.g002

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 3. Performance profiles of these methods (Time).

https://doi.org/10.1371/journal.pone.0164289.g003

From Figs 1 and 2, we can conclude that Algorithm 4.1 performs better than Algorithm 4.2 and MPRP do in terms of the numbers of iterations and function evaluations. Moreover, the excellence of Algorithm 4.1 can obviously be attributed to the superior theoretical properties of the MHZ method compared with the usual HZ method. However, Fig 3 indicates that Algorithm 4.2 is superior to Algorithm 4.1 and MPRP in terms of CPU time. Overall, all methods are very effective for application to large-scale nonsmooth optimization problems.

Conclusion

(i) In this paper, we focus on the HZ CG method and study the application of this method to solve nonsmooth optimization problems. Several results are presented that prove the efficiency of this method for application to large-scale problems of nonsmooth unconstrained optimization.

(ii) Motivated by the HZ formula, we also present a modified HZ CG formula. The modified HZ formula not only possesses the sufficient descent property of the HZ formula but also belongs to a trust region and has the non-negative scale

(iii) We report the results of applying three methods to solve large-scale nonsmooth convex minimization problems. Global convergence is achieved, and numerical experiments verify that both methods can be successfully used to solve large-scale nonsmooth problems.

(iv) Although the HZ and MHZ methods offer several key achievements for large-scale nonsmooth optimization, we believe that there are at least five issues that could be addressed to gain further improvements. The first is the scale c in the modified HZ CG algorithm, which could be adjusted. The second is the application of other CG methods for this type of optimization areas; perhaps there exists a more suitable CG method for this purpose. Regarding the third issue, it is well known that limited-memory quasi-Newton methods are effective techniques for solving certain classes of large-scale optimization problems because they require minimal storage; this inspires us to combine limited-memory quasi-Newton methods with the HZ CG technique to solve large-scale nonsmooth optimization. In future, we will also use the HZ CG method to investigate large-scale nonsmooth optimization with constraints; this is the fourth issue that we believe must be addressed. The last issue is the most important one, namely, the consideration of other optimality conditions and convergence conditions in nonsmooth problems should be paid. All of these issues will be addressed in our future work.

Acknowledgments

The authors would like to thank the referees for their valuable comments which greatly improve this paper. This work was supported by the Guangxi Science Fund for Distinguished Young Scholars (Grant No. 2015GXNSFGA139001), the National Natural Science Foundation of China (Grant No. 11261006 and 11661009), National Natural Science Foundation of China No. 61232016, National Natural Science Foundation of China No. U1405254, and PAPD issue of Jiangsu advantages discipline.