An extension of the quasi-Newton method for minimizing locally Lipschitz functions

Iranian Journal of Numerical Analysis and Optimization

مقاله 7، دوره 9، شماره 2 - شماره پیاپی 16، دی 2019، صفحه 123-139   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.v9i2.75991

نویسنده

Z. Akbari^*

University of Mazandaran

چکیده

We present a method to minimize locally Lipschitz functions. At first, a local quadratic model is developed to approximate a locally Lipschitz function. This model is constructed by using the ϵ-subdifferential. We minimize this local model and compute a search direction. It is shown that this direction is descent. We generalize the Wolfe conditions for finding an adequate step length along this direction. Next, the method is equipped with a quasi Newton approach to update the local model and its globally convergence is proposed. Finally, the proposed algorithm is implemented in MATLAB environment on some standard nonsmooth optimization test problems and compared with some algorithms in the literature.

کلیدواژه‌ها

Quasi-Newton method؛ Quadratic model؛ Line search algorithm؛ Lipschitz functions؛ nonsmooth optimization problem

مراجع

1. Akbari, Z. and Yousefpour, R. A trust region method for solving linearly constrained locally Lipschitz optimization problems, Optimization, 66(9) (2017), 1519–1529.

2. Akbari, Z., Yousefpour, R. and Peyghami, M.R.A new Nonsmooth trust region Algorithm for locally Lipschitz unconstrained optimization problems, J. Optim. Theory Appl. 164(3) (2015), 733–754.

3. Bagirov, A.M. Continuous subdifferential approximations and their applications, Optimization and related topics, 2. J. Math. Sci. (N.Y.) 115 (2003), 2567–2609.

4. Bagirov, A.M., Karmitsa, N. and M¨akel¨a, M. M. Introduction to nonsmooth optimization: Theory, practice and software, Springer Publishing Company, Incorporated, 2014.

5. Burke, J.V. and Overton, M.L. A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM J. Optim. 15 (2005), 571–779.

6. Dolan, E.D. and More, J.J. Benchmarking optimization software with performance profiles, Math. Program. 91 (2002), 201–213.

7. Frangioni, A. Generalized bundle methods, SIAM J. Optim. 113 (2003), 117–156.

8. Haarala, N. and Miettinen, K. and M¨akel¨a, M.M. Globally convergent limited memory bundle method for large-scale nonsmooth optimization, Math. Program. 109 (2007), 181–205.

9. Han, S., Pang, J. and Rangaraj, N. Globally Convergent Newton Methods for Nonsmooth Equations, Math. Oper. Res.,17(3) (1992), 586–607.

10. Hiriart-Urruty, J-B. and Lemar´echal, C. Convex analysis and minimization algorithms II: Advanced theory and bundle methods, Springer-Verlag, 1993.

11. Karmitsa, N. and Bagirov, A.M. Limited memory discrete gradient bundle method for nonsmooth derivative-free optimization, Optimization, 61(12) (2012), 1491-1509.

12. Kiwiel, K.C. Convergence of the Gradient Sampling Algorithm for Nonsmooth Nonconvex Optimization, SIAM J. Optim. 18(2) (2007), 379–388.

13. Lewis, A.S. and Overton, M.L. Nonsmooth optimization via quasi-Newton methods, Math. Program. 141(1-2) (2012) Ser. A, 135–163. .

14. Luksan, L. , Tuma, M. , Siska, M., Vlcek, J. and Ramesova, N. UFO 2002: interactive system for universal functional optimization, Academy of Sciences of the Czech Republic, (2012). Also available as http://www.cs.cas.cz/luksan/ufo.pdf.

15. Luksan, L. and Vlcek, J. A bundle-Newton method for nonsmooth unconstrained minimization, Math. Program. 83 (1998), 373–391.

16. Luksan, L. and Vlcek, J. Globally convergent variable metric method for convex nonsmooth unconstrained minimization, J. Optim. Theory Appl. 102 (1999), 593–613.

17. Luksan, L. and Vlcek, J. Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization, J. Optim. The

ory Appl., 111 (2001), 407–430.

18. Mahdavi-Amiri, M. and Yousefpour, R. An effective nonsmooth optimization algorithm for locally Lipschitz functions, J. Optim. Theory Appl. 155 (2012), 180–195.

19. M¨akel¨a, M. M. Survey of bundle methods for nonsmooth optimization, Optim. Methods Softw. 17 (1) (2002), 1–29.

20. M¨akel¨a, M.M. and Neittaanmaki, P. Nonsmooth optimization: Theory and algorithms with applications to optimal control, World Scientific, 1992.

21. Nocedal, J. and Wright, S.J. Numerical Optimization, Springer, 1999.

22. Polak, E. and Royset, J.O. Algorithms for finite and semi-infinite min max-min problems using adaptive smoothing techniques, J. Optim. Theory Appl. 119(421) (2003), 421–457.

23. Qi, L. and Sun, J. A trust region algorithm for minimization of locally Lipschitzian functions, Math. Program. 66 (1994), 25–43.

24. Schramm, H. and Zowe, J. A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM J. Optim. 2 (1992), 121–152.

25. Shor, N. Z. Minimization methods for non-differentiable functions, Springer-Verlag, 1985.

26. Yousefpour, R. Combination of steepest descent and BFGS methods for nonconvex nonsmooth optimization, Numer. Algorithms, 72(1) (2016), 57–90.