A New Non-monotone Line Search Algorithm to Solve Non-smooth Optimization Finance Problem

Subject Areas : Numerical Methods in Mathematical Finance

Saeed Banimehri ¹ , Hamid Esmaeili ²

1 - Department of Mathematics, Bu-Ali sina University, hamedan, Iran
2 - Department of Mathematics, Bu-Ali Sina University, Hamedan, Iran

Received: 2022-08-13 Accepted : 2023-01-18 Published : 2024-02-26

Keywords: Derivative-free optimization, Non-smooth optimization, Non-monotone Armijo line search, Diagonal discrete gradient bundle method,

Abstract :

In this paper, a new non-monotone line search is used in the diagonal discrete gradient bundle method to solve large-scale non-smooth optimization problems. Non-smooth optimization problems are encountered in many applications in fi-nance problems. The new principle causes the step in each iteration to be longer, which reduces the number of iterations, evaluations, and the computational time. In other words, the efficiency and performance of the method are improved. We prove that the diagonal discrete gradient bundle method converges with the pro-posed non-monotone line search principle for semi-smooth functions, which are not necessarily differentiable or convex. In addition, the numerical results confirm the efficiency of the proposed correction.

References:


[1] Ahookhosh, M., Amini, K., Bahrami, S., A class of nonmonotone Armijo-type line search method for unconstrained optimization, Journal of Optimization Theory and Applications, 2012; 61(4): 387-404. doi: 10.1080/02331934.2011.641126

[2] Bagirov, A.M., Karasözen, B., Sezer, M., Discrete gradient method: derivative-free method for nonsmooth optimization, Journal of Optimization Theory and Applications, 2008; 137(2):317-334. doi: 10.1007/s10957-007-9335-5

[3] Bagirov, A.M., Karmitsa, N., Mäkelä, M.M., Introduction to Nonsmooth Optimization: theory, practice and software, Vol. 12. Springer, Switzerland, 2014.

[4] Barzilai, J., Borwein, J.M., Two-point step size gradient methods, IMA journal of numerical analysis, 1988; 8(1): 141-148. doi: 10.1093/imanum/8.1.141

[5] Dai, Y.H., Liao, L.Z., R‐linear convergence of the Barzilai and Borwein gradient method, IMA Journal of Numerical Analysis, 2002; 22(1):1-10. doi: 10.1093/imanum/22.1.1

[6] Dai, Y.H., On the nonmonotone line search, Journal of Optimization theory and Applications, 2002; 112(2): 315-330. doi: 10.1023/A:1013653923062

[7] Darabi, R., Baghban, M., Application of Clayton Copula in Portfolio Optimization and its Comparison with Markowitz Mean-Variance Analysis, Advances in mathematical finance & applications, 2018; 3(1):33-51. doi: 10.22034/amfa.2018.539133

[8] Grimaldi, R., Fibonacci and Catalan Numbers, John Wiley and Sons, 2012.

[9] Grippo, L., Lampariello, F., Lucidi, S., A class of nonmonotone stabilization methods in unconstrained optimization, Numerische Mathematik, 1991; 59(1): 779-801. doi: 10.1007/BF01385810

[10] Grippo, L., Lampariello, F., Lucidi, S., A nonmonotone line search technique for Newton’s method, SIAM Journal of Numerical Analysis, 1986; 23(4): 707-716. doi: 10.1137/0723046

[11] Griva, I., Nash, S.G., Sofar, A., Linear and nonlinear optimization, Vol. 108. SIAM, Philadelphia, 2009.

[12] Haarala, M., The Large-scale nonsmooth optimization: variable metric bundle method with limited memory, Academic Jyvaskyla, Jyvaskyla, 2004.

[13] Haarala, M., Miettinen, K., Makela, M.M., New limited memory bundle method for large-scale nonsmooth optimization, Optimization Methods and Software, 2004;19(6):673-692. doi: 10.1080/10556780410001689225

[14] Haarala, N., Miettinen, K., Makela, M.M., Globally convergent limited memory bundle method for large-scale nonsmooth optimization, Mathematical Programming, 2007; 109(1):181-205. doi: 10.1007/s10107-006-0728-2

[15] Karmitsa, N., Diagonal bundle method for nonsmooth sparse optimization, Journal of Optimization Theory and Applications, 2015; 166(3):886-905. doi: 10.1007/s10957-014-0666-8

[16] Karmitsa, N., Diagonal discrete gradient bundle method for derivative free nonsmooth optimization, Optimization, 2016; 65(8):1599-1614. doi: 10.1080/02331934.2016.1171865

[17] Lemarechal, C., Strodiot, J.J., Bihain, A., On a bundle algorithm for nonsmooth optimization, Nonlinear programming4; 1981: 245-282. doi: 10.1016/B978-0-12-468662-5.50015-X

[18] Mifflin, R., A modification and an extension of Lemaréchal’s algorithm for nonsmooth minimization, Nondifferential and variational techniques in optimization,1980; 77-90.doi: 10.1007/BFb0120960

[19] Rahmani, M., Khalili Eraqi, M., Nikoomaram, H., Portfolio Optimization by Means of Meta Heuristic Algorithms, Advances in mathematical finance & applications, 2019; 4(4):83-97. doi:10.22034/amfa.2019.579510.1144

[20] Raydan, M., On the Barzilai and Borwein choice of steplength for the gradient method, IMA Journal of Numerical Analysis, 1993; 13(3): 321-326. doi:10.1093/imanum/13.3.321

[21] Raydan, M., The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM Journal on Optimization, 1997; 7(1):26-33. doi:10.1137/S1052623494266365

[22] Sun, W., Han, J., Sun, J., Global convergence of nonmonotone descent methods for unconstrained optimization problems, Journal of Computational and Applied Mathematics, 2002; 146(1):89-98. doi: 10.1016/S0377-0427(02)00420-X

[23] Vlcek, J., Lukšan, L., Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization, Journal of Optimization Theory and Applications, 2001; 111(2):407-430. doi: 10.1023/A:1011990503369

[24] Zanjirdar, M., Overview of Portfolio Optimization Models, Advances in mathematical finance & applications, 2020; 5(4):419-435. doi:10.22034/amfa.2020.1897346.1407

[25] Zhang, H., Hager, W.W., A nonmonotone line search technique and its application to unconstrained optimization, SIAM journal on Optimization, 2004;14(4):1043-1056. doi: 10.1137/S1052623403428208

Full-Text:



Adv. Math. Fin. App., 2024, 9(2), P.461-469
	Advances in Mathematical Finance & Applications www.amfa.iau-arak.ac.ir Print ISSN: 2538-5569 Online ISSN: 2645-4610 Doi: 10.22034/amfa.2023.1965376.1784

 

  Original Research

A New Non-Monotone Line Search Algorithm to Solve Non-Smooth Optimization Finance Problem

Saeed Banimehri, Hamid Esmaeili∗

Department of Mathematics, Bu-Ali Sina University, Hamedan, Iran

 

Article Info Article history: Received 2022-08-13 Accepted 2023-01-18   Keywords: Non-smooth optimization Derivative-free optimization Diagonal discrete gradient bundle method Non-monotone Armijo line search		Abstract
		In this paper, a new non-monotone line search is used in the diagonal discrete gradient bundle method to solve large-scale non-smooth optimization problems. Non-smooth optimization problems are encountered in many applications in finance problems. The new principle causes the step in each iteration to be longer, which reduces the number of iterations, evaluations, and the computational time. In other words, the efficiency and performance of the method are improved. We prove that the diagonal discrete gradient bundle method converges with the proposed non-monotone line search principle for semi-smooth functions, which are not necessarily differentiable or convex. In addition, the numerical results confirm the efficiency of the proposed correction.

 

 

1 Introduction

In this paper, we are considering the non-smooth optimization problem of the form

where the objective function  is supposed to be semi-smooth and the number of variables n is supposed to be large. Note that no differentiability or convexity assumptions for problem (1) are made. In general, iterative algorithms for non-smooth optimization proceed as follows: given a point , find a descent direction  such that  ( is discrete gradient), a suitable steplength  and construct the new point as follows:

(1)

The line search is a sub-problem to find  in iterative process (2). In this process to find a steplength , we must solve the following one-dimensional minimization problem

(2)

Very often in practice, we use the line search technique to find the step length. Exact line search methods to calculate step length can be expensive and time consuming. Therefore, some inexact line search techniques [6, 7, 9, 22] namely the Armijo technique, the Wolfe technique and the Goldstein technique have been proposed to determine an acceptable step length . Among these condition, the Armijo condition is the most popular condition stating as follows:

(3)

Where . According to the condition (4), we can conclude , so this procedure is called a monotone line search.

In [10], Grippo et al. presented the new line search condition for unconstrained optimization that allows  more than , so they called their rule as the non-monotone line search. Non-monotone line search method is a new approach to determine the step length in optimization problems. This method reduces the line search range to find the largest step length in each iteration and avoids being confined to a narrow valley as much as possible [6, 11, 19]. Grippo et al. defined their condition as follows:

(4)

Where  is an integer constant,  and for all , we have , Although this non-monotone condition has some benefits,but it includs some drawbacks (see [1, 9, 25]).

The problems with the diagonal discrete gradient bundle method, one is that it may not work for some problems. Our purpose in this article is to modify the above method. In the diagonal discrete gradient bundle method, Armijo line search method is used to calculate the step length. In this paper, we present a non-monotone line search algorithm to solve non-smooth optimization problems. In this algorithm, we combine a non-monotone strategy with the modified Armijo rule and design a new algorithm that will probably choose a larger step length at each iteration. This strategy may reduce the number of iterates, time and function evaluations and can improve the efficiency of the new approach. Numerical results show that the new approach to solving non-smooth optimization problems is robust and efficient.

The paper is organized as follows. In Section 2, we introduce the diagonal discrete gradient bundle method. In Section 3, we describe a new non-monotone Armijo line search algorithm and present its convergence properties. Section 4 shows numerical results of the algorithm. Finally, Section 5 concludes the paper.

2 Diagonal Discrete Gradient Bundle Method

In this section, we introduce the diagonal discrete gradient bundle method. The diagonal discrete gradient bundle method uses the ideas of the variable metric bundle method [12] to calculate the null step, simple aggregate, and the sub-gradient locality measure. The diagonal discrete gradient bundle method uses discrete gradients instead of sub-gradients in our calculations and the search direction  is calculated using the diagonal variable metric update in which

(5)

where  is (an aggregate) discrete gradient and  is the diagonal variable metric update.

In order to determine a new step into the search direction , the DDG-BUNDLE uses the so-called armijo line search (see [14, 23, 24]) for a new iteration point  and a new auxiliary point    produced such that

(6)

With   , where  and  are step sizes, and  is the upper bound for the step size. A necessary condition for a serious step is to have

(7)

Where  is a line search parameter and  represents the desirable amount of descent of  at . If the condition (8) is satisfied, we set  and a serious step is taken. On the other hand, a null step is taken if

(8)

Where  is a line search parameter and . Moreover,   is analogous to the sub-gradient locality measure [17, 18] used in standard bundle methods, that is

(9)

Here,  is a distance measure parameter supplied by the user. In the case of a null step, we set  but information about the objective function is increased because we store the auxiliary point  and the corresponding auxiliary discrete gradient .

The DDG-BUNDLE uses the original discrete gradient   after the serious step and the aggregate sub-gradient  after the null step for direction finding (i.e. we set  if the previous step is a serious step). The aggregation procedure is carried out by determining multipliers  satisfying  for all  and  that minimize a simple quadratic function

(10)

Here,  is the current discrete gradient,  is the auxiliary discrete gradient, and  is the current aggregate discrete gradient from the previous iteration . In addition, is the current sub-gradient locality measure and  is the current aggregate sub-gradient locality measure  (see [22]).

The resulting aggregate discrete gradient  and aggregate sub-gradient locality measure are computed by

(11)

Due to this simple aggregation procedure, only one trial point  and the corresponding discrete gradient  need to be stored.

We need to consider how to update the matrix  and, at the same time, to find the search direction  . The basic idea in direction finding is the same as that with the limited memory bundle method. However, due to the usage of null steps some modification similar to the variable metric bundle methods has to be made: If the previous step is a null step, the matrix  is formed by using the limited memory SR1 update [15]. This update formula gives us a possibility to preserve the boundedness and some other properties of generated matrices that are required in the proof of global convergence.

The stopping parameter  at iteration k is defined by

(12)

and the algorithm stops if  for some user specified . The parameter  is also used during the line search procedure to represent the desirable amount of descent. (See [1516] for more details on the diagonal discrete gradient bundle method)

 

3 Modified Non-Monotone Line Search Method

Non-monotone line search methods have been studied by many researchers (see [6, 9, 22]). The Barzilai and Borwein method [4, 5, 21] is a descent method. In many cases, nonlinear linear search does not need to satisfy condition (5); therefore, it is suitable for overcoming the situation where the repetition sequence goes to a very narrow valley [6, 11], the event that occurs in most practical nonlinear optimization problems. Grippo et al [9, 10]. introduce new linear search methods, including non-monotone line search method for Newton method. In addition, the non-monotone line search method has been studied by many researchers. In the following, we will introduce non-monotone Armijo line search. In this article, we want to look at how to choose step length  and develop a modification of non-monotone Armijo line search method [9].

We use the condition

(13)

to produce a serious step, where is the largest number in ,with  and

(14)

In condition (14),  is obtained from the following equation:

(15)

where is a constant. In [25], it is shown that one can obtain a stronger non-monotone strategy whenever  is close to 1 and can obtain a weaker non-monotone strategy whenever  is close to 0. In this paper, we use the Fibonacci sequence to calculate  (see [8]). At a glance to the standard Armijo rule and the new Armijo-type line search, firstly, we can see that the term  is added to right-hand side of the Armijo rule. Secondly, we substitute  instead of  which is possibly greater than. Therefore, we can see the right-hand side of the approach is greater than the right-hand side of the standard Armijo rule, so a larger steplength is possible for the algorithm to gain. These changes may reduce the number of iterations and function evaluations for attaining the same optimum.

 

3.1. Non-Monotone Line Search Procedure.

Initial. Positive parameters  , , ,  satisfying  and , distance measure parameter , an interpolation parameter  and . All of these parameters are constant.

Step i. Set  and .

Step ii Calculate ,  and  

If , set ; otherwise, set .

Step iii (Serious step). If , set  and return.

Step iv (Null step). If  , set  , and return.

Step v. Choose by some interpolation procedure, and go to Step (ii).

3.2. Convergence Analysis

In this section, we show the global convergence of the diagonal discrete gradient bundle algorithm. The convergence of diagonal discrete gradient bundle algorithm is described in [15]. In [1], it is shown that the non-monotone line search method is well-defined. We will continue to show that the non-monotone line search procedure terminates in a finite number of iterations. First, the non-monotone line search procedure has been proved to be finite under the assumption of upper semi-smoothness when sub-gradients are used.

Lemma 1. Let f satisfy the following semi-smoothness hypothesis. For any  ,  and sequences  and  satisfying  and , one has

(16)

Then, the non-monotone line search procedure terminates in a finite number of iterations.

Proof. The proof becomes identical to the proof of Theorem 3.6 in [23] by replacing  by .

The set of discrete gradients is an approximation to the sub-differential if the function is semi-smooth. Since the class of semi-smooth functions includes the class of upper semi-smooth functions, we here assume that the objective function f is semi-smooth. Now, due to assumption of semi-smoothness and sub-gradient (see [15]), the non-monotone Armijo line search procedure is also finite when sub-gradients are replaced with discrete gradients.

 

4 Numerical Experiments

As already said, the test set used in our experiments consists of extensions of classical academic non-smooth minimization problems from the literature. That is, problems  were first introduced in [13, 19, 24]. These problems can be formulated with any number of variables. Note that in the computation of both the Armijo line search and non-monotone Armijo line search, more than n function evaluations are needed for each iteration. Here, we examine problems with dimensions of 50, 200 and 1000 variables. We perform our experiments in MATLAB 8.1 programming environment. We say that a solver finds the solution with respect to a tolerance  if

(17)

or

(18)

Where and  are the values of the function and the optimal point in the current iteration, and are the values of the function and the optimal point in the previous iteration. We have accepted the results with respect to the tolerance . For the diagonal discrete gradient bundle method, these are

 

 

 

.

We put  in the modified line search condition, where  is the sum of the first k sentences of the Fibonacci sequence(see [8]).Also, in this paper, multipliers for  are calculated by the default optimization method in MATLAB.

(19)

Table 1: Summary of the Results with 50 Variables.
problem	Armijo line search nf / time	Modi ed non-monotone Armijo line search nf / time
1	3201 / 0.077	3008 / 0.066
2	Fail	10563 / 0.122
3	8132 / 0.513	7952 / 0.318
4	14189 / 0.302	14009 / 0.282
5	5400 / 0.268	4984 / 0.234
6	3345 / 0.09	3002 / 0.03
7	11471 / 0.18	10891 / 0.11
8	13356 / 0.11	12803 / 0.07

 

Table 2: Summary of the Results with 200 Variables.
problem	Armijo line search nf / time	Modi ed non-monotone Armijo line search nf / time
1	42815 / 1.168	41095 / 0.844
2	Fail	52364 / 2.690
3	44654 / 1.638	43031 / 1.375
4	113918 / 10.291	110523 / 1.001
5	41104 / 1.663	40980 / 1.532
6	279301 / 5.36	209147 / 4.13
7	58965 / 7.235	54178 / 6.137
8	51297 / 1.34	48354 / 0.98

 

 

 

 

 

Table 3: Summary of the Results with1000 Variables.
problem	Armijo line search nf / time	Modi ed non-monotone Armijo line search nf / time
1	1821133 / 47.864	1523451 / 42.796
2	Fail	902478 / 40426
3	1506899 / 81.411	1498568 / 76.298
4	2932844 / 39.886	2523569 / 38.416
5	129091 / 47.276	121957 / 46.289
6	176458 / 55.45	175142 / 30.25
7	203372 / 61.32	199354 / 45.37
8	5390563 / 59.45	5142 638 / 51.871

 

The results are summarized in Tables 1-3 where we have compared the efficiency of the conditions both in terms of the computational time and the number of function evaluations (nf, evaluations for short). The phrase Fail indicates that the method in question is not able to solve the problem. In problem 2, the old method is not able to solve the problem, but the modified method is able to solve the problem. In details, these results suggest that the proposed algorithm has promising behaviour encountering with medium-scale and large-scale unconstrained optimization problems and it is superior to the considered algorithm in all cases. Summarizing the results of tables. 1, 2 and 3 implies that modified diagonal discrete gradient bundle method is superior to the presented algorithm with respect to the number of iterations and function evaluations.

5 Conclusions

In this paper, we propose a new family of Armijo-type line search approach to calculate the step length in an unconstrained optimization problem that the objective function is non-smooth and non-convex. In the sense, we present a correction for the diagonal discrete gradient bundle method. In this modification, we focus on a new approach to new non-monotone line search. This rule produces a larger step size, especially when the repetition is far from optimal. We proved the global convergence of this method for semi-smooth functions that are not necessarily differentiable and convex. The numerical experiments confirm the efficiency of the proposed correction compared to the diagonal discrete gradient bundle method to solve large-scale non-smooth optimization problems.

 

References

[1] Ahookhosh, M., Amini, K., Bahrami, S., A class of nonmonotone Armijo-type line search method for unconstrained optimization, Journal of Optimization Theory and Applications, 2012; 61(4): 387-404. doi: 10.1080/02331934.2011.641126

 

[2] Bagirov, A.M., Karasözen, B., Sezer, M., Discrete gradient method: derivative-free method for nonsmooth optimization, Journal of Optimization Theory and Applications, 2008; 137(2):317-334. doi: 10.1007/s10957-007-9335-5

 

[3] Bagirov, A.M., Karmitsa, N., Mäkelä, M.M., Introduction to Nonsmooth Optimization: theory, practice and software, Vol. 12. Springer, Switzerland, 2014.

 

[4] Barzilai, J., Borwein, J.M., Two-point step size gradient methods, IMA journal of numerical analysis, 1988; 8(1): 141-148. doi: 10.1093/imanum/8.1.141

 

[5] Dai, Y.H., Liao, L.Z., R‐linear convergence of the Barzilai and Borwein gradient method, IMA Journal of Numerical Analysis, 2002; 22(1):1-10. doi: 10.1093/imanum/22.1.1

 

[6] Dai, Y.H., On the nonmonotone line search, Journal of Optimization theory and Applications, 2002; 112(2): 315-330. doi: 10.1023/A:1013653923062

 

[7] Darabi, R., Baghban, M., Application of Clayton Copula in Portfolio Optimization and its Comparison with Markowitz Mean-Variance Analysis, Advances in mathematical finance & applications, 2018; 3(1):33-51. doi: 10.22034/amfa.2018.539133

 

[8] Grimaldi, R., Fibonacci and Catalan Numbers, John Wiley and Sons, 2012.

 

[9] Grippo, L., Lampariello, F., Lucidi, S., A class of nonmonotone stabilization methods in unconstrained optimization, Numerische Mathematik, 1991; 59(1): 779-801. doi: 10.1007/BF01385810

 

[10] Grippo, L., Lampariello, F., Lucidi, S., A nonmonotone line search technique for Newton’s method, SIAM Journal of Numerical Analysis, 1986; 23(4): 707-716. doi: 10.1137/0723046

 

[11] Griva, I., Nash, S.G., Sofar, A., Linear and nonlinear optimization, Vol. 108. SIAM, Philadelphia, 2009.

 

[12] Haarala, M., The Large-scale nonsmooth optimization: variable metric bundle method with limited memory, Academic Jyvaskyla, Jyvaskyla, 2004.

 

[13] Haarala, M., Miettinen, K., Makela, M.M., New limited memory bundle method for large-scale nonsmooth optimization, Optimization Methods and Software, 2004;19(6):673-692. doi: 10.1080/10556780410001689225

 

[14] Haarala, N., Miettinen, K., Makela, M.M., Globally convergent limited memory bundle method for large-scale nonsmooth optimization, Mathematical Programming, 2007; 109(1):181-205. doi: 10.1007/s10107-006-0728-2

 

[15] Karmitsa, N., Diagonal bundle method for nonsmooth sparse optimization, Journal of Optimization Theory and Applications, 2015; 166(3):886-905. doi: 10.1007/s10957-014-0666-8

 

[16] Karmitsa, N., Diagonal discrete gradient bundle method for derivative free nonsmooth optimization, Optimization, 2016; 65(8):1599-1614. doi: 10.1080/02331934.2016.1171865

 

[17] Lemarechal, C., Strodiot, J.J., Bihain, A., On a bundle algorithm for nonsmooth optimization, Nonlinear programming4; 1981: 245-282. doi: 10.1016/B978-0-12-468662-5.50015-X

 

[18] Mifflin, R., A modification and an extension of Lemaréchal’s algorithm for nonsmooth minimization, Nondifferential and variational techniques in optimization,1980; 77-90.doi: 10.1007/BFb0120960

 

[19] Rahmani, M., Khalili Eraqi, M., Nikoomaram, H., Portfolio Optimization by Means of Meta Heuristic Algorithms, Advances in mathematical finance & applications, 2019; 4(4):83-97. doi:10.22034/amfa.2019.579510.1144

 

[20] Raydan, M., On the Barzilai and Borwein choice of steplength for the gradient method, IMA Journal of Numerical Analysis, 1993; 13(3): 321-326. doi:10.1093/imanum/13.3.321

 

[21] Raydan, M., The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM Journal on Optimization, 1997; 7(1):26-33. doi:10.1137/S1052623494266365

 

[22] Sun, W., Han, J., Sun, J., Global convergence of nonmonotone descent methods for unconstrained optimization problems, Journal of Computational and Applied Mathematics, 2002; 146(1):89-98. doi: 10.1016/S0377-0427(02)00420-X

 

[23] Vlcek, J., Lukšan, L., Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization, Journal of Optimization Theory and Applications, 2001; 111(2):407-430. doi: 10.1023/A:1011990503369

 

[24] Zanjirdar, M., Overview of Portfolio Optimization Models, Advances in mathematical finance & applications, 2020; 5(4):419-435. doi:10.22034/amfa.2020.1897346.1407

 

[25] Zhang, H., Hager, W.W., A nonmonotone line search technique and its application to unconstrained optimization, SIAM journal on Optimization, 2004;14(4):1043-1056. doi: 10.1137/S1052623403428208

 

 

 

 

 

 

 

 

 

 

 

 

* Corresponding author. Tel.: [phone]. E-mail address: [e-mail]

© 2024. All rights reserved.   Hosting by IA University of Arak Press

 

---

Related articles