×

zbMATH — the first resource for mathematics

Discrete gradient method: Derivative-free method for nonsmooth optimization. (English) Zbl 1165.90021
The paper of A. M. Bagirov, B. Karasözen and M. Sezer is a valuable contribution to the numerical-algorithmical part of unconstrained continuous optimization, in fact, to its nonsmooth version, and the corresponding theory is provided, too. It stands in the tradition of nonsmooth analysis and optimization, but it benefits from some insight and experience related with important classes of modern applications. These are hosted in the fields of data mining, especially, in clustering theory. In fact, there, the classical rules of nonsmooth calculus are not all fully applicable, especially, due the lack of the so-called regularity condition, such that some classical or regularity based nonsmooth results and algorithms can fail. For this reason, A. M. Bagirov with his colleagues had proposed and developed the concept and use of discrete gradients as an alternative in nonsmooth optimization.
In fact, here, the corresponding subgradients are approximated by discrete gradients; their use lets the authors’ approach be one of derivative free optimization. The authors demonstrate that this approximation can be made for a broad class of functions, and that their discrete gradient method (DGM) can be applied to find descent directions. They provide numerical experiments and compare their results with the nonsmooth optimization solver DNLP (from CONTOPT-GAMS) and the derivative-free optimization solver CONDOR.
The paper is well organized by firstly introducing into classes of functions such as locally Lipschitzian, semismooth and quasidifferentiable, by discussing the clustering problem and nonregularity, presenting the approximation of subgradients and computing subdifferenials via discrete gradients, computing descent directions, presenting DGM and, then, giving the numerical experience for (mostly) nonconvex problems, before concluding that, in fact, DGM delivers, very good results within that comparison.
Taking into account how important these data mining applications are, but also that nonsmooth optimization is more and more important in other fields such as finance and engineering, and that the unconstrained case could become treated, too, this conclusion is promising indeed.

MSC:
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives
Software:
GAMS; DGM; CONDOR; GradSamp
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Frangioni, A.: Generalized bundle methods. SIAM J. Optim. 113, 117–156 (2002) · Zbl 1041.90037
[2] Gaudioso, M., Monaco, M.F.: A bundle type approach to the unconstrained minimization of convex nonsmooth functions. Math. Program. 23, 216–226 (1982) · Zbl 0479.90066
[3] Hiriart-Urruty, J.B., Lemarechal, C.: Convex Analysis and Minimization Algorithms, vols. 1 and 2. Springer, Heidelberg (1993)
[4] Kiwiel, K.C.: Methods of Descent for Nondifferentiable Optimization. Lecture Notes in Mathematics, vol. 1133. Springer, Berlin (1985) · Zbl 0561.90059
[5] Lemarechal, C.: An extension of Davidon methods to nondifferentiable problems. In: Balinski, M.L., Wolfe, P. (eds.) Nondifferentiable Optimization. Mathematical Programming Study, vol. 3, pp. 95–109. North-Holland, Amsterdam (1975) · Zbl 0358.90051
[6] Mifflin, R.: An algorithm for constrained optimization with semismooth functions. Math. Oper. Res. 2, 191–207 (1977) · Zbl 0395.90069
[7] Zowe, J.: Nondifferentiable optimization: A motivation and a short introduction into the subgradient and the bundle concept. In: Schittkowski, K. (ed.) Computational Mathematical Programming. NATO SAI Series, vol. 15, pp. 323–356. Springer, New York (1985)
[8] Wolfe, P.H.: A method of conjugate subgradients of minimizing nondifferentiable convex functions. Math. Program. Study 3, 145–173 (1975) · Zbl 0369.90093
[9] Polak, E., Royset, J.O.: Algorithms for finite and semi-infinite min-max-min problems using adaptive smoothing techniques. J. Optim. Theory Appl. 119, 421–457 (2003) · Zbl 1061.90116
[10] 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) · Zbl 1078.65048
[11] Audet, C., Dennis, J.E. Jr.: Analysis of generalized pattern searches. SIAM J. Optim. 13, 889–903 (2003) · Zbl 1053.90118
[12] Torzcon, V.: On the convergence of pattern search algorithms. SIAM J. Optim. 7, 1–25 (1997) · Zbl 0884.65053
[13] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[14] Mifflin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 959–972 (1977) · Zbl 0376.90081
[15] Demyanov, V.F., Rubinov, A.M.: Constructive Nonsmooth Analysis. Peter Lang, Frankfurt am Main (1995) · Zbl 0887.49014
[16] Bagirov, A.M., Rubinov, A.M., Soukhoroukova, A.V., Yearwood, J.: Supervised and unsupervised data classification via nonsmooth and global optimisation. TOP: Spanish Oper. Res. J. 11, 1–93 (2003) · Zbl 1048.65059
[17] Bagirov, A.M., Yearwood, J.: A new nonsmooth optimisation algorithm for minimum sum-of-squares clustering problems. Eur. J. Oper. Res. 170, 578–596 (2006) · Zbl 1085.90045
[18] Bagirov, A.M.: Minimization methods for one class of nonsmooth functions and calculation of semi-equilibrium prices. In: Eberhard, A., et al. (eds.) Progress in Optimization: Contribution from Australasia, pp. 147–175. Kluwer Academic, Dordrecht (1999) · Zbl 1016.90048
[19] Bagirov, A.M.: Continuous subdifferential approximations and their applications. J. Math. Sci. 115, 2567–2609 (2003) · Zbl 1039.49020
[20] Wolfe, P.H.: Finding the nearest point in a polytope. Math. Program. 11, 128–149 (1976) · Zbl 0352.90046
[21] Frangioni, A.: Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. Oper. Res. 23, 1099–1118 (1996) · Zbl 0871.90059
[22] Kiwiel, K.C.: A dual method for certain positive semidefinite quadratic programming problems. SIAM J. Sci. Stat. Comput. 10, 175–186 (1989) · Zbl 0663.65063
[23] Luksan, L., Vlcek, J.: Test problems for nonsmooth unconstrained and linearly constrained optimization. Technical Report 78, Institute of Computer Science, Academy of Sciences of the Czech Republic (2000)
[24] GAMS: The solver manuals. GAMS Development Corporation, Washington D.C. (2004)
[25] Bergen, F.V.: CONDOR: a constrained, non-linear, derivative-free parallel optimizer for continuous, high computing load, noisy objective functions. Ph.D. thesis, Université Libre de Bruxelles, Belgium (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.