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

• Autorzy: Abdelkrim El Mouatasim , Rachid Ellaia , José E. Souza De Cursi
• 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

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

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2006
• Tom: 16
• Numer: 4
• Strony: 463-474

Daty

wydano

2006

otrzymano

2006-04-19

poprawiono

2006-09-28

(nieznana)

2006-10-06

Twórcy

autor

Abdelkrim El Mouatasim

• Ecole Mohammadia d'Ingenieurs, LERMA, Avenue Ibn Sina BP765-Agdal, Rabat, Morocco

autor

Rachid Ellaia

• Ecole Mohammadia d'Ingenieurs, LERMA, Avenue Ibn Sina BP765-Agdal, Rabat, Morocco

autor

José E. Souza De Cursi

• LMR - UMR 6138 CNRS, INSA-Rouen, Avenue de l'Universite BP 8, Saint-Etienne du Rouvray, France

Bibliografia

• 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.
• 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.
• 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.
• Bihain A. (1984): Optimization of upper semidifferentiable functions. - J. Optim. Theory Applic., Vol. 4, No. 4, pp. 545-568.
• Bouleau N. (1986): Variables Aleatoires et Simulation. - Paris: Editions Hermann.
• Boyd S., Xiao L. and Mutapcic A. (2003): Subgradient Methods. - Notes for EE392o, Stanford University.
• Carson Y. and Maria A. (1997): Simulation optimization: Methods and applications. - Proc. Winter Simulation Conf., Atlanta, GA, USA, pp. 118-126.
• Clarke F. (1983): Optimization and Nonsmooth Analysis. - New York: Wiley.
• Clarke F. (1975): Generalized gradient and applications. - Trans. Amer. Math. Soc.,Vol. 205, pp. 247-262.
• Davidon W. (1991): Variable metric method forminimization. - SIAM J. Optim., Vol. 1, No. 1, pp. 1-17.
• Dorea C.C.Y. (1990): Stopping rules for a random optimization method. - SIAM J. Contr. Optim., Vol. 28, No. 4,pp. 841-850.
• Ellaia R. (1992): Contributions à l'optimisation globale et à l'analyse nondifferentiable. - Thèse d'etat, Universite Mohammed V, Faculte des Sciences, Rabat, Morocco.
• 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.)
• Fletcher R. (1980): Practical Methods of Optimization, Vol.2. - New York: Wiley.
• Hiriart-Urruty J. and Lemarechal C. (1993): Convex Analysis and Minimization Algorithms II. - Berlin: Springer.
• Kiwiel K.C. (1985): Method of Descent for Nondifferentiable Optimization. - Berlin: Springer.
• 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.
• 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.
• 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.
• Lemarechal C. (1982): Numerical experiments in nonsmooth optimization. - Proc.II ASA Workshop Progress in Nondifferentiable Optimization, Laxemburg, Austria, pp. 61-84.
• 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.
• Makela M.M. and Neittaanmaki P. (1992): Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. - London: World Scientific.
• 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.
• Outrata J. (1987): On numerical solution of optimal control problems with nonsmooth objectives: Application to economic models. - Kybernetika, Vol. 23, pp. 54-66.
• Outrata J., Kocvara M. and Zowe J. (1998): Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results. - Dordrecht: Kluwer.
• 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.
• 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.
• 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.
• 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
• 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
• 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.
• 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).
• Uryasev S.P. (1991): New variable metric algorithms for nondifferentiable optimization problems. - J. Optim. Theory Applic., Vol. 71, No. 2, pp. 359-388.
• 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.
• Zowe J. (1985): Nondifferentiable optimization, In: Computational Mathematical Programming (K. Schittkowski,Ed.). - Berlin: Springer Verlag, pp. 323-356.