Abstract
This paper is devoted to a detailed convergence analysis of the method of codifferential descent (MCD) developed by professor V.F. Demyanov for solving a large class of nonsmooth nonconvex optimization problems. We propose a generalization of the MCD that is more suitable for applications than the original method, and that utilizes only a part of a codifferential on every iteration, which allows one to reduce the overall complexity of the method. With the use of some general results on uniformly codifferentiable functions obtained in this paper, we prove the global convergence of the generalized MCD in the infinite dimensional case. Also, we propose and analyse a quadratic regularization of the MCD, which is the first general method for minimizing a codifferentiable function over a convex set. Apart from convergence analysis, we also discuss the robustness of the MCD with respect to computational errors, possible step size rules, and a choice of parameters of the algorithm. In the end of the paper we estimate the rate of convergence of the MCD for a class of nonsmooth nonconvex functions that arise, in particular, in cluster analysis. We prove that under some general assumptions the method converges with linear rate, and it convergence quadratically, provided a certain first order sufficient optimality condition holds true.
Similar content being viewed by others
References
Demyanov, V.F.: Continuous generalized gradients for nonsmooth functions. In: Kurzhanski, A., Neumann, K., Pallaschke, D. (eds.) Optimization, Parallel Processing and Applications, pp. 24–27. Springer, Berlin (1988)
Demyanov, V.F.: On codifferentiable functions. Vestn. Leningr. Univ. Math. 2, 22–26 (1988)
Demyanov, V.F.: Smoothness of nonsmooth functions. In: Clarke, F.H., Demyanov, V.F., Giannesssi, F. (eds.) Nonsmooth Optimization and Related Topics, pp. 79–88. Springer, Boston (1989)
Demyanov, V.F., Rubinov, A.M.: Constructive Nonsmooth Analysis. Peter Lang, Frankfurt am Main (1995)
Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation I. Basic Theory. Springer, Berlin (2006)
Penot, J.-P.: Calculus Without Derivatives. Springer, New York (2013)
Zaffaroni, A.: Continuous approximations, codifferentiable functions and minimization methods. In: Demyanov, V.F., Rubinov, A.M. (eds.) Quasidifferentiability and Related Topics, pp. 361–391. Kluwer Academic Publishers, Dordrecht (2000)
Dolgopolik, M.V.: Codifferential calculus in normed spaces. J. Math. Sci. 173, 441–462 (2011)
Dolgopolik, M.V.: Abstract convex approximations of nonsmooth functions. Optimization 64, 1439–1469 (2015)
Demyanov, V.F., Stavroulakis, G.E., Polyakova, L.N., Panagiotopoulos, P.D.: Quasidifferentiability and Nonsmooth Modelling in Mechnics, Engineering and Economics. Kluwer Academic Publishers, Dordrecht (1996)
Demyanov, V.F., Rubinov, A.M. (eds.): Quasidifferentiability and Related Topics. Kluwer Academic Publishers, Dordrecht (2000)
Pallaschke, D., Recht, P., Urbański, R.: On locally-Lipschitz quasi-differentiable functions in Banach spaces. Optimization 17, 287–295 (1986)
Uderzo, A.: Fréchet quasidifferential calculus with applications to metric regularity of continuous maps. Optimization 54, 469–493 (2005)
Bagriov, A.M.: Numerical methods for minimizing quasidifferentiable functions: a survey and comparison. In: Demyanov, V.F., Rubinov, A.M. (eds.) Quasidifferentiability and Related Topics, pp. 33–71. Kluwer Academic Publishers, Dordrecht (2000)
Bagirov, A.: A method for minimization of quasidifferentiable functions. Optim. Methods Softw. 17, 31–60 (2002)
Luderer, B., Weigelt, J.: A solution method for a special class of nondifferentiable unconstrained optimization problems. Comput. Optim. Appl. 24, 83–93 (2003)
Mäkelä, M.: Survey of bundle method for nonsmooth optimization. Optim. Methods Softw. 17, 1–29 (2002)
Haarala, N., Miettinen, K., Mäkelä, M.: Globally convergent limited memory bundle method for large-scale nonsmooth optimization. Math. Program. 109, 181–205 (2007)
Hare, W., Sagastizábal, C.: A redistributed proximal bundle method for nonconvex optimization. SIAM J. Optim. 20, 2442–2473 (2010)
Fuduli, A., Gaudioso, M., Nurminski, E.A.: A splitting bundle approach for non-smooth non-convex minimization. Optimization 64, 1131–1151 (2015)
Burke, J.V., Lewis, A.S., Overton, M.L.: A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM J. Optim. 15, 751–779 (2005)
Kiwiel, K.C.: A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 20, 1983–1994 (2010)
Hare, W., Nutini, J.: A derivative-free approximate gradient sampling algorithm for finite minimax problems. Comput. Optim. Appl. 56, 1–38 (2013)
Curtis, F.E., Que, X.: An adaptive gradient sampling algorithm for non-smooth optimization. Optim. Methods Softw. 28, 1302–1324 (2013)
Lewis, A.S., Overton, M.L.: Nonsmooth optimization via quasi-Newton methods. Math. Program. 141, 135–163 (2013)
Keskar, N., Wächter, A.: A limited-memory quasi-Newton algorithm for bound-constrained non-smooth optimization. Optim. Methods Softw. (2017). https://doi.org/10.1080/10556788.2017.1378652
Bagirov, A.M., Karasözen, B., Sezer, M.: Discrete gradient method: derivative-free method for nonsmooth optimization. J. Optim. Theory Appl. 137, 317–334 (2008)
Bagirov, A.M., Rubinov, A.M., Zhang, J.: A multidimensional descent method for global optimization. Optimization 58, 611–625 (2009)
Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. SIAM, Philadelphia (2009)
Karmitsa, N., Bagirov, A., Mäkelä, M.M.: Comparing different nonsmooth minimization methods and software. Optim. Methods Softw. 27, 131–153 (2012)
Bagirov, A., Napsu, K., Mäkelä, M.M.: Introduction to Nonsmooth Optimization. Springer, Cham (2014)
Demyanov, V.F., Bagirov, A.M., Rubinov, A.M.: A method of truncated codifferential with applications to some problems of cluster analysis. J. Glob. Optim. 23, 63–80 (2002)
Bagirov, A.M., Ganjehlou, A.N., Ugon, J., Tor, A.H.: Truncated codifferential method for nonsmooth convex optimization. Pac. J. Optim. 6, 483–496 (2010)
Tor, A.H., Karasözen, B., Bagirov, A.: Truncated codifferential method for linearly constrained nonsmooth optimization. In: The ISI proceedings of 24th mini EURO conference “Continuous Optimization and Information-Based Technologies in the Financial Sector”, Izmir, Turkey, pp 87–93 (2010)
Bagirov, A.M., Ugon, J.: Codifferential method for minimizing nonsmooth DC functions. J. Glob. Optim. 50, 3–22 (2011)
Tor, A.H., Bagirov, A., Karasözen, B.: Aggregate codifferential method for nonsmooth DC optimization. J. Comput. Appl. Math. 259, 851–867 (2014)
Andramonov, M.Yu.: The method of confidence neighbourhoods for minimization of codifferentiable functions. Russ. Math. 48, 1–7 (2004)
Demyanov, V.F., Tamasyan, GSh: Exact penalty functions in isoperimetric problems. Optimization 60, 153–177 (2011)
Demyanov, V.F., Tamasyan, GSh: Direct methods in the parametric moving boundary variational problem. Numer. Funct. Anal. Optim. 35, 932–961 (2014)
Fominyh, A.V., Karelin, V.V., Polyakova, L.N.: Application of the hypodifferential descent method to the problem of constructing an optimal control. Optim. Lett. (2017). https://doi.org/10.1007/s11590-017-1222-x
Pschenichny, B.N., Danilin, Yu.M.: Numerical Methods in Extremal Problems, English edn. Mir Publishers, Moscow (1978)
Pironneau, O., Polak, E.: On the rate of convergence of certain methods of centers. Math. Program. 2, 230–258 (1972)
Daugavet, V.A., Malozemov, V.N.: Quadratic rate of convergence of a linearization method for solving discrete minimax problems. USSR Comput. Math. Math. Phys. 21, 19–28 (1981)
Polak, E.: Optimization, Algorithms and Consistent Approximations. Springer, New York (1997)
Ioffe, A.D., Tihomirov, V.M.: Theory of Extremal Problems. North-Holland Publishing Company, Amsterdam (1979)
Luderer, B.: Does the special choice of quasidifferentials influence necessary minimum conditions? In: Oettli, W., Pallaschke, D. (eds.) Advances in Optimization, pp. 256–266. Springer, Berlin (1992)
Luderer, B., Rösiger, R., Würker, U.: On necessary minimum conditions in quasidifferential calculus: independence of the specific choice of quasidifferentials. Optimization 22, 643–660 (1991)
Kuntz, L.: A charaterization of continuously codifferentiable function and some consequences. Optimization 22, 539–547 (1991)
Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley-Interscience, New York (1983)
Pallaschke, D., Urbański, R.: Pairs of Compact Convex Sets: Fractional Arithmetic with Convex Sets. Kluwer Academic Publishers, Dordrecht (2002)
Di Pillo, G., Facchinei, F.: Exact Barrier Function Methods for Lipschitz Programs. Appl. Math. Optim. 32, 1–31 (1995)
Demyanov, V.F., Malozemov, V.N.: Introduction to Minimax. Wiley, New York (1990)
Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I. Springer, Berlin (1993)
Edwards, R.E.: Functional Analysis: Theory and Applications. Dover Publications, New York (1995)
Penot, J.-P.: On the convergence of descent algorithms. Comput. Optim. Appl. 23, 279–284 (2002)
Dolgopolik, M.V.: Nonsmooth problems of calculus of variations via codifferentiation. ESAIM: Control Optim. Calc. Var. 20, 1153–1180 (2014)
Dolgopolik, M.V.: Inhomogeneous convex approximations of nonsmooth functions. Russ. Math. 56, 28–42 (2012)
Acknowledgements
The author is sincerely grateful to his colleagues G.Sh. Tamasyan, A. Fominyh and T. Angelov for numerous useful discussions on the method of codifferential descent and its applications that played an important role in the preparation of this paper. Also, the author wishes to express his thanks to the anonymous referees for many thoughtful comments that helped to significantly improve the quality of the article, and to professor V.N. Malozemov for pointing out the fact that the PPP algorithm converges quadratically to a Chebyshev (Haar) point.
Author information
Authors and Affiliations
Corresponding author
Additional information
The author was supported by the Russian Foundation for Basic Research under Grant No. 16-31-00056.
Rights and permissions
About this article
Cite this article
Dolgopolik, M.V. A convergence analysis of the method of codifferential descent. Comput Optim Appl 71, 879–913 (2018). https://doi.org/10.1007/s10589-018-0024-0
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-018-0024-0
Keywords
- Nonsmooth optimization
- Nonconvex optimization
- Codifferential
- Quasidifferential
- Method of codifferential descent