Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2006 | 16 | 4 | 463-474
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
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.
Opis fizyczny
  • Ecole Mohammadia d'Ingenieurs, LERMA, Avenue Ibn Sina BP765-Agdal, Rabat, Morocco
  • Ecole Mohammadia d'Ingenieurs, LERMA, Avenue Ibn Sina BP765-Agdal, Rabat, Morocco
  • LMR - UMR 6138 CNRS, INSA-Rouen, Avenue de l'Universite BP 8, Saint-Etienne du Rouvray, France
  • 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
  • Souza de Cursi J.E. (1992b): Recuit simule et application a l'approximation par des sommes d'exponentielles. - Tech. Rep. ECN, Available at http//
  • 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.
Typ dokumentu
Identyfikator YADDA
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.