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

Abdelkrim El Mouatasim; Rachid Ellaia; José Souza de Cursi

International Journal of Applied Mathematics and Computer Science (2006)

  • Volume: 16, Issue: 4, page 463-474
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

El Mouatasim, Abdelkrim, Ellaia, Rachid, and Souza de Cursi, José. "Random perturbation of the variable metric method for unconstrained nonsmooth nonconvex optimization." International Journal of Applied Mathematics and Computer Science 16.4 (2006): 463-474. <http://eudml.org/doc/207806>.

@article{ElMouatasim2006,
abstract = {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.},
author = {El Mouatasim, Abdelkrim, Ellaia, Rachid, Souza de Cursi, José},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {generalized gradient; nonsmooth optimization; nonconvex optimization; stochastic perturbation; variable metric method; generalized gradient},
language = {eng},
number = {4},
pages = {463-474},
title = {Random perturbation of the variable metric method for unconstrained nonsmooth nonconvex optimization},
url = {http://eudml.org/doc/207806},
volume = {16},
year = {2006},
}

TY - JOUR
AU - El Mouatasim, Abdelkrim
AU - Ellaia, Rachid
AU - Souza de Cursi, José
TI - Random perturbation of the variable metric method for unconstrained nonsmooth nonconvex optimization
JO - International Journal of Applied Mathematics and Computer Science
PY - 2006
VL - 16
IS - 4
SP - 463
EP - 474
AB - 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.
LA - eng
KW - generalized gradient; nonsmooth optimization; nonconvex optimization; stochastic perturbation; variable metric method; generalized gradient
UR - http://eudml.org/doc/207806
ER -

References

top
  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. Zbl0709.65519
  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. Zbl1048.65059
  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. Zbl0534.90069
  5. Bouleau N. (1986): Variables Aleatoires et Simulation. - Paris: Editions Hermann. Zbl0659.60001
  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. Zbl0582.49001
  9. Clarke F. (1975): Generalized gradient and applications. - Trans. Amer. Math. Soc.,Vol. 205, pp. 247-262. Zbl0307.26012
  10. Davidon W. (1991): Variable metric method forminimization. - SIAM J. Optim., Vol. 1, No. 1, pp. 1-17. Zbl0752.90062
  11. Dorea C.C.Y. (1990): Stopping rules for a random optimization method. - SIAM J. Contr. Optim., Vol. 28, No. 4,pp. 841-850. Zbl0711.65043
  12. Ellaia R. (1992): Contributions à l'optimisation globale et à l'analyse nondifferentiable. - Thèse d'etat, Universite Mohammed V, Faculte 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. Zbl0439.93001
  15. Hiriart-Urruty J. and Lemarechal C. (1993): Convex Analysis and Minimization Algorithms II. - Berlin: Springer. Zbl0795.49002
  16. Kiwiel K.C. (1985): Method of Descent for Nondifferentiable Optimization. - Berlin: Springer. Zbl0561.90059
  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. Zbl0694.65026
  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. Zbl0883.90100
  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. Zbl0913.90225
  20. Lemarechal C. (1982): Numerical experiments in nonsmooth optimization. - Proc.II ASA Workshop Progress in Nondifferentiable Optimization, Laxemburg, Austria, pp. 61-84. Zbl0509.65025
  21. 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. Zbl0533.49023
  22. Makela M.M. and Neittaanmaki P. (1992): Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. - London: World Scientific. Zbl0757.49017
  23. 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. Zbl0751.90071
  24. Outrata J. (1987): On numerical solution of optimal control problems with nonsmooth objectives: Application to economic models. - Kybernetika, Vol. 23, pp. 54-66. Zbl0617.65062
  25. Outrata J., Kocvara M. and Zowe J. (1998): Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results. - Dordrecht: Kluwer. Zbl0947.90093
  26. 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. 
  27. 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. Zbl0827.90132
  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. Zbl0761.90090
  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 simule et application a 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. Zbl1176.90649
  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). Zbl1271.49022
  33. Uryasev S.P. (1991): New variable metric algorithms for nondifferentiable optimization problems. - J. Optim. Theory Applic., Vol. 71, No. 2, pp. 359-388. Zbl0793.90078
  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. Zbl0581.90072

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.