We consider the global optimization of a nonsmooth (nondifferentiable) nonconvex real function. We introduce a variable metric descent method adapted to nonsmooth situations, which is modified by the incorporation of suitable random perturbations. Convergence to a global minimum is established and a simple method for the generation of suitable perturbations is introduced. An algorithm is proposed and numerical results are presented, showing that the method is computationally effective and stable.
@article{bwmeta1.element.bwnjournal-article-amcv16i4p463bwm,
author = {El Mouatasim, Abdelkrim and Ellaia, Rachid and Souza de Cursi, Jos\'e},
title = {Random perturbation of the variable metric method for unconstrained nonsmooth nonconvex optimization},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {16},
year = {2006},
pages = {463-474},
zbl = {1160.90694},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv16i4p463bwm}
}
El Mouatasim, Abdelkrim; Ellaia, Rachid; Souza de Cursi, José. Random perturbation of the variable metric method for unconstrained nonsmooth nonconvex optimization. International Journal of Applied Mathematics and Computer Science, Tome 16 (2006) pp. 463-474. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv16i4p463bwm/
[000] Aluffi-Pentini F., Parisi V. and Zirilli F. (1988): ALGORITHM 667:SIGMA - A Stochastic-Integration Global Minimization Algorithm. - ACM Trans. Math. Softw., Vol. 14, No. 4, pp. 366-380. | Zbl 0709.65519
[001] Bagirov A.M., Rubinov A.M., Soukhoroukova N.V. and Yearwood J. (2003): Unsupervised and supervised data classification via nonsmooth and global optimization. - Trab. Invest. Oper., Vol. 11, No. 1, pp. 1-93. | Zbl 1048.65059
[002] Batukhtin V.D., Kirillova F.M. and Ukhobotov V.I.(1998): Nonsmooth and discontinuous problems of control and optimization. - Proc. IFAC Workshop NDPCO'98,Chelyabinsk, Russia, pp. 25-34.
[003] Bihain A. (1984): Optimization of upper semidifferentiable functions. - J. Optim. Theory Applic., Vol. 4, No. 4, pp. 545-568. | Zbl 0534.90069
[004] Bouleau N. (1986): Variables Aleatoires et Simulation. - Paris: Editions Hermann. | Zbl 0659.60001
[005] Boyd S., Xiao L. and Mutapcic A. (2003): Subgradient Methods. - Notes for EE392o, Stanford University.
[006] Carson Y. and Maria A. (1997): Simulation optimization: Methods and applications. - Proc. Winter Simulation Conf., Atlanta, GA, USA, pp. 118-126.
[007] Clarke F. (1983): Optimization and Nonsmooth Analysis. - New York: Wiley. | Zbl 0582.49001
[008] Clarke F. (1975): Generalized gradient and applications. - Trans. Amer. Math. Soc.,Vol. 205, pp. 247-262. | Zbl 0307.26012
[009] Davidon W. (1991): Variable metric method forminimization. - SIAM J. Optim., Vol. 1, No. 1, pp. 1-17. | Zbl 0752.90062
[010] Dorea C.C.Y. (1990): Stopping rules for a random optimization method. - SIAM J. Contr. Optim., Vol. 28, No. 4,pp. 841-850. | Zbl 0711.65043
[011] Ellaia R. (1992): Contributions à l'optimisation globale et à l'analyse nondifferentiable. - Thèse d'etat, Universite Mohammed V, Faculte des Sciences, Rabat, Morocco.
[012] Ellaia R. and Elmouatasim A., (2004): Random perturbation of reduced gradient method for global optimization. -Proc. Conf. Modelling, Computation and Optimization, MCO'04, Metz, France, (to appear.)
[013] Fletcher R. (1980): Practical Methods of Optimization, Vol.2. - New York: Wiley. | Zbl 0439.93001
[014] Hiriart-Urruty J. and Lemarechal C. (1993): Convex Analysis and Minimization Algorithms II. - Berlin: Springer. | Zbl 0795.49002
[015] Kiwiel K.C. (1985): Method of Descent for Nondifferentiable Optimization. - Berlin: Springer. | Zbl 0561.90059
[016] Kiwiel K.C. (1989): An ellipsoid trust region bundle method for nonsmooth convex minimization. - SIAM J.Contr. Optim., Vol. 27, No. 4, pp. 737-757. | Zbl 0694.65026
[017] Kiwiel K.C. (1994): Free-steering relaxation methods for problems with strictly convex costs and linear constraints. - Tech. Rep. IIASA, No. A-2361, Laxenburg, Austria. | Zbl 0883.90100
[018] Larsson T., Patrksson M. and Stromberg A.B. (1996): Conditional subgradient optimization-Theory and applications. - Europ. J. Oper. Res., Vol. 88, No. 2, pp. 382-403. | Zbl 0913.90225
[019] Lemarechal C. (1982): Numerical experiments in nonsmooth optimization. - Proc.II ASA Workshop Progress in Nondifferentiable Optimization, Laxemburg, Austria, pp. 61-84. | Zbl 0509.65025
[020] Lemarechal C., Strodiot J.J. and Bihain A. (1981): On a bundle algorithm for nonsmooth optimization, In: Nonlinear Programming 4 (O. Mangasarian, R. Meyer and S. Robinson, Eds.). - New York: Academic Press, pp. 245-282. | Zbl 0533.49023
[021] Makela M.M. and Neittaanmaki P. (1992): Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. - London: World Scientific. | Zbl 0757.49017
[022] Nguyen V.H. and Strodiot J.J. (1992): Computing a Global Optimal Solution to a Design Centering Problem. - Tech.Rep., No. 8812, Facultes Universitaires Notre-Dame de la Paix, Belgium. | Zbl 0751.90071
[023] Outrata J. (1987): On numerical solution of optimal control problems with nonsmooth objectives: Application to economic models. - Kybernetika, Vol. 23, pp. 54-66. | Zbl 0617.65062
[024] Outrata J., Kocvara M. and Zowe J. (1998): Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results. - Dordrecht: Kluwer. | Zbl 0947.90093
[025] Pierre L. and Renee T. (1996): On the Deng-Linrandom number generators and related methods, In: Global Optimization in Action (Pinter J., Ed.). - Les cahiers du GERAD,Dordrecht: Kluwer.
[026] Pogu M. and Souza J.E. (1994): Global optimizationby random perturbation of the gradient method with a fixed parameter. - J. Glob. Optim., Vol. 5, No. 2, pp. 159-180. | Zbl 0827.90132
[027] Schramm H. and Zowe J. (1992): A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results. - SIAM J. Optim., Vol. 2,No. 1, pp. 121-152. | Zbl 0761.90090
[028] Souza de Cursi J.E. (1992a): Minimisation stochastique de fonctionnelles non convexes en dimension finie. - Tech. Rep. ECN, Available at http://meca.insa-rouen.fr/~souza
[029] Souza de Cursi J.E. (1992b): Recuit simule et application a l'approximation par des sommes d'exponentielles. - Tech. Rep. ECN, Available at http//:meca.insa-rouen.fr/~souza
[030] Souza de Cursi J.E., Ellaia R. and Bouhadi M. (2003): Global optimization under nonlinear restrictions by using stochastic perturbations of the projected gradient, In: Frontiers In Global Optimization (C.A. Floudas and Panos Pardalos, Eds.). - Boston, MA: Kluwer Academic Publishers,Nonconvex Optim. Appl., Vol. 74, pp. 541-561. | Zbl 1176.90649
[031] Souza de Cursi J.E., Ellaia R. and El Mouatasim A.(2005): Stochastic perturbation of active set method for nonconvex nonsmooth optimization problem with linear constraints. - RAIRO-Recherche Operational, (submitted). | Zbl 1271.49022
[032] Uryasev S.P. (1991): New variable metric algorithms for nondifferentiable optimization problems. - J. Optim. Theory Applic., Vol. 71, No. 2, pp. 359-388. | Zbl 0793.90078
[033] Wang I.J. and Spall J.C. (1999): A constrained simultaneous perturbation stochastic approximation algorithm based on penalty functions. - Proc. Amer. Contr. Conf. San Diego, CA, Vol. 1, pp. 393-399.
[034] Zowe J. (1985): Nondifferentiable optimization, In: Computational Mathematical Programming (K. Schittkowski,Ed.). - Berlin: Springer Verlag, pp. 323-356. | Zbl 0581.90072