Random perturbation of the variable metric method for unconstrained nonsmooth nonconvex optimization

• Autorzy: El Mouatasim A. , Ellaia R. , Souza de Cursi J. E.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

nonconvex optimization; stochastic perturbation; variable metric method; nonsmooth optimization; generalized gradient

PL

optymalizacja; zaburzenie stochastyczne; zaburzenie losowe

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2006
• Tom: Vol. 16, no 4
• Strony: 463--474
• Opis fizyczny: Bibliogr. 35 poz., tab.

Twórcy

autor

El Mouatasim A.

• Ecole Mohammadia d’Ingénieurs, LERMA, Avenue Ibn Sina BP765-Agdal, Rabat, Morocco

autor

Ellaia R.

• Ecole Mohammadia d’Ingénieurs, LERMA, Avenue Ibn Sina BP765-Agdal, Rabat, Morocco

autor

Souza de Cursi J. E.

• LMR – UMR 6138 CNRS, INSA-Rouen, Avenue de l’Université BP 8, Saint-Etienne du Rouvray, France, FR-76831

Bibliografia

• [1] 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.
• [2] 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.
• [3] 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.
• [4] Bihain A. (1984): Optimization of upper semidifferentiable functions. - J. Optim. Theory Applic., Vol. 4, No. 4, pp. 545- 568.
• [5] Bouleau N. (1986): Variables Aléatoires et Simulation.-Paris: Editions Hermann.
• [6] Boyd S., Xiao L. and Mutapcic A. (2003): Subgradient Methods. - Notes for EE392o, Stanford University.
• [7] Carson Y. and Maria A. (1997): Simulation optimization: Methods and applications. - Proc. Winter Simulation Conf., Atlanta, GA, USA, pp. 118-126.
• [8] Clarke F. (1983): Optimization and Nonsmooth Analysis. - New York: Wiley.
• [9] Clarke F. (1975): Generalized gradient and applications. - Trans. Amer. Math. Soc., Vol. 205, pp. 247-262.
• [10] Davidon W. (1991): Variable metric method for minimization. - SIAM J. Optim., Vol. 1, No. 1, pp. 1-17.
• [11] Dorea C.C.Y. (1990): Stopping rules for a random optimization method.-SIAM J. Contr. Optim., Vol. 28, No. 4, pp. 841-850.
• [12] Ellaia R. (1992): Contributions à l'optimisation globale et à l'analyse nondifférentiable. - Thèse d'état, Université Mohammed V, Faculté des Sciences, Rabat, Morocco.
• [13] 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.)
• [14] Fletcher R. (1980): Practical Methods of Optimization, Vol.2.- New York: Wiley.
• [15] Hiriart-Urruty J. and Lemaréchal C. (1993): Convex Analysis and Minimization Algorithms II.-Berlin: Springer.
• [16] Kiwiel K.C. (1985): Method of Descent for Nondifferentiable Optimization.- Berlin: Springer.
• [17] 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.
• [18] 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.
• [19] 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.
• [20] Lemaréchal C. (1982): Numerical experiments in nonsmooth optimization. - Proc. IIASA Workshop Progress in Nondifferentiable Optimization, Laxemburg, Austria, pp. 61-84.
• [21] Lemaréchal 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.
• [22] Mākelā M.M. and Neittaanmāki P. (1992): Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control.- London: World Scientific.
• [23] Nguyen V.H. and Strodiot J.J. (1992): Computing a Global Optimal Solution to a Design Centering Problem. - Tech. Rep., No. 88/12, Facultés Universitaires Notre-Dame de la Paix, Belgium.
• [24] Outrata J. (1987): On numerical solution of optimal control problems with nonsmooth objectives: Application to economic models. - Kybernetika, Vol. 23, pp. 54-66.
• [25] Outrata J., Kocvara M. and Zowe J. (1998): Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications & Numerical Results. - Dordrecht: Kluwer.
• [26] Pierre L. and Renée T. (1996): On the Deng-Lin random number generators and related methods, In: Global Optimization in Action (Pinter J., Ed.).-Les cahiers du GERAD, Dordrecht: Kluwer.
• [27] Pogu M. and Souza J.E. (1994): Global optimization by random perturbation of the gradient method with a fixed parameter.- J. Glob. Optim., Vol. 5, No. 2, pp. 159-180.
• [28] 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.
• [29] 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
• [30] Souza de Cursi J.E. (1992b): Recuit simulé et application à l'approximation par des sommes d'exponentielles. -Tech. Rep. ECN, Available at http://meca.insa-rouen.fr/~souza
• [31] 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.
• [32] 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).
• [33] Uryasev S.P. (1991): New variable metric algorithms for nondifferentiable optimization problems. - J. Optim. Theory Applic., Vol. 71, No. 2, pp. 359-388.
• [34] 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.
• [35] Zowe J. (1985): Nondifferentiable optimization, In: Computational Mathematical Programming (K. Schittkowski, Ed.). Berlin: Springer Verlag, pp. 323-356.