Random perturbation of the projected variable metric method for nonsmooth nonconvex optimization problems with linear constraints

Abdelkrim El Mouatasim; Rachid Ellaia; Eduardo Souza de Cursi

International Journal of Applied Mathematics and Computer Science (2011)

  • Volume: 21, Issue: 2, page 317-329
  • ISSN: 1641-876X

Abstract

top
We present a random perturbation of the projected variable metric method for solving linearly constrained nonsmooth (i.e., nondifferentiable) nonconvex optimization problems, and we establish the convergence to a global minimum for a locally Lipschitz continuous objective function which may be nondifferentiable on a countable set of points. Numerical results show the effectiveness of the proposed approach.

How to cite

top

Abdelkrim El Mouatasim, Rachid Ellaia, and Eduardo Souza de Cursi. "Random perturbation of the projected variable metric method for nonsmooth nonconvex optimization problems with linear constraints." International Journal of Applied Mathematics and Computer Science 21.2 (2011): 317-329. <http://eudml.org/doc/208050>.

@article{AbdelkrimElMouatasim2011,
abstract = {We present a random perturbation of the projected variable metric method for solving linearly constrained nonsmooth (i.e., nondifferentiable) nonconvex optimization problems, and we establish the convergence to a global minimum for a locally Lipschitz continuous objective function which may be nondifferentiable on a countable set of points. Numerical results show the effectiveness of the proposed approach.},
author = {Abdelkrim El Mouatasim, Rachid Ellaia, Eduardo Souza de Cursi},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {global optimization; linear constraints; variable metric method; stochastic perturbation; nonsmooth optimization},
language = {eng},
number = {2},
pages = {317-329},
title = {Random perturbation of the projected variable metric method for nonsmooth nonconvex optimization problems with linear constraints},
url = {http://eudml.org/doc/208050},
volume = {21},
year = {2011},
}

TY - JOUR
AU - Abdelkrim El Mouatasim
AU - Rachid Ellaia
AU - Eduardo Souza de Cursi
TI - Random perturbation of the projected variable metric method for nonsmooth nonconvex optimization problems with linear constraints
JO - International Journal of Applied Mathematics and Computer Science
PY - 2011
VL - 21
IS - 2
SP - 317
EP - 329
AB - We present a random perturbation of the projected variable metric method for solving linearly constrained nonsmooth (i.e., nondifferentiable) nonconvex optimization problems, and we establish the convergence to a global minimum for a locally Lipschitz continuous objective function which may be nondifferentiable on a countable set of points. Numerical results show the effectiveness of the proposed approach.
LA - eng
KW - global optimization; linear constraints; variable metric method; stochastic perturbation; nonsmooth optimization
UR - http://eudml.org/doc/208050
ER -

References

top
  1. Bagirov, A. and Yearwood, J. (2006). A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems, European Journal of Operational Research 170(2): 578-596. Zbl1085.90045
  2. Bogani, C., Gasparo, M.G. and Papini, A. (2009). Generalized pattern search methods for a class of nonsmooth optimization problems with structure, Journal of Computational and Applied Mathematics 229(1): 283-293. Zbl1166.65028
  3. Bouleau, N. (1986). Variables Aléatoires et Simulation, Hermann Editions, Paris. Zbl0659.60001
  4. Broyden, C. (1970). The convergence of a class of double-rank minimization algorithms, Journal Institute of Mathematics and Its Applications 6(1): 76-90. Zbl0223.65023
  5. Correa, R. and Lemaréchal, C. (1993). Convergence of some algorithms for convex minimization, Mathematical Programming 62(2): 261-275. Zbl0805.90083
  6. Davidon, W. (1991). Variable metric method for minimization, SIAM Journal on Optimization 1(1): 1-17. Zbl0752.90062
  7. Dorea, C. (1990). Stopping rules for a random optimization method, SIAM Journal on Control and Optimization 28(4): 841-850. Zbl0711.65043
  8. El Mouatasim, A. and Al-Hossain, A. (2009). Reduced gradient method for minimax estimation of a bounded Poisson mean, Journal of Statistics: Advances in Theory and Applications 2(2): 183-197. Zbl05703861
  9. El Mouatasim, A., Ellaia, R. and Souza de Cursi, J. (2006). Random perturbation of variable metric method for unconstrained nonsmooth nonconvex optimization, International Journal of Applied Mathematics and Computer Science 16(4): 463-474. Zbl1160.90694
  10. Fletcher, R. (1970). A new approach to variable metric algorithms, Computer Journal 13(3): 317-322. Zbl0207.17402
  11. Fletcher, R. and Powell, M. (1963). A rapidly convergent descent method for minimization, Computer Journal 6(2): 163-168. Zbl0132.11603
  12. Goldfarb, D. (1970). A family of variable metric methods derived by variational means, Mathematics of Computation 24(109): 23-26. Zbl0196.18002
  13. Hiriart-Urruty, J.-B. and Lemaréchal, C. (1993). Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods, Grundlehren der mathematischen Wissenschaften, Vol. 306, Springer-Verlag, Berlin. 
  14. Kelley, J. (1960). The cutting plane method for solving convex programs, Journal of the Society for Industrial and Applied Mathematics 8(4): 703-712. Zbl0098.12104
  15. Kiwiel, K. (1985). Method of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, Vol. 1133, Springer-Verlag, Berlin. Zbl0561.90059
  16. Kowalczuk, Z., and Oliski K.O. (2006). Suboptimal fault tolerant control design with the use of discrete optimization, International Journal of Applied Mathematics and Computer Science 18(4), DOI: 10.2478/v10006-008-0049-0. 
  17. Kryazhimskii, A. (2001). Optimization problems with convex epigraphs. application to optimal control, International Journal of Applied Mathematics and Computer Science 11(4): 773-801. Zbl1012.49005
  18. Larsson, T., Patrksson, M. and Stromberg, A. (1996). Conditional subgradient optimization-theory and applications, European Journal of Operational Research 88(2): 382-403. Zbl0913.90225
  19. Lemaréchal, C., Strodiot, J. and Bihain, A. (1981). On a bundle algorithm for nonsmooth optimization, in O. Mangasarian, R. Meyer and S. Robinson (Eds.), Nonlinear Programming, Vol. 4, Academic Press, New York, NY/London, pp. 245-282. Zbl0533.49023
  20. Luenberger, D. (1973). Introduction to Linear and Nonlinear Programming, Addison-Wesley Publishing Company, London. Zbl0297.90044
  21. Luks̃an, L. and Vlc̃ek, J. (2000). Test problems for nonsmooth unconstraint and linearly constraint optimization, Technical Report TR-798, Institute of Computer Sciences, Academy of Sciences of the Czech Republic, Prague. 
  22. Makela, M. and Neittaanmaki, P. (1992). Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control, World Scientific Publishing Co., London. Zbl0757.49017
  23. Malanowski, K. (2004). Convergence of the Lagrange-Newton method for optimal control problems, International Journal of Applied Mathematics and Computer Science 14(4): 531-540. Zbl1082.49033
  24. Panier, E. (1987). An active set method for solving linearly constrained nonsmooth optimization problems, Mathematical Programming 37(3): 269-292. Zbl0641.90061
  25. Peng, Y. and Heying, Q. (2009). A filter-variable-metric method for nonsmooth convex constrained optimization, Applied Mathematics and Computation 208(1): 119-128. Zbl1160.65028
  26. Petersen, I. (2006). Minimax LQG control, International Journal of Applied Mathematics and Computer Science 16(3): 309-323. Zbl1136.93465
  27. Pinter, J. (1996). Global Optimization in Action, Kluwer, Dordrecht. Zbl0842.90110
  28. Pogu, M. and Souza de Cursi, J. (1994). Global optimization by random perturbation of the gradient method with a fixed parameter, Journal of Global Optimization 5(2): 159-180. Zbl0827.90132
  29. Schramm, H. and Zowe, J. (1992). A version of the bundle idea for minimizing a nonsmooth function: Conceptual idea, convergence analysis, numerical results, SIAM Journal of Optimization 2: 121-152. Zbl0761.90090
  30. Shanno, D. (1970). Conditioning of quasi-Newton methods for function minimization, Mathematics of Computation 24(111): 647-657. Zbl0225.65073
  31. Souza de Cursi, J. (1991). Introduction aux probabilités, Ecole Centrale Nantes, Nantes. 
  32. Souza de Cursi, J., Ellaia, R. and Bouhadi, M. (2003). Global optimization under nonlinear restrictions by using stochastic perturbations of the projected gradient, in C.A. Floudas and P.M. Pardalos (eds.), Frontiers in Global Optimization, Vol. 1, Dordrecht, Springer, pp.: 541-562. Zbl1176.90649
  33. Uryasev, S. (1991). New variable metric algorithms for nondifferentiable optimization problems, Journal of Optimization Theory and Applications 71(2): 359-388. Zbl0793.90078
  34. Zhang, G. (2009). A note on: A continuous approach to nonlinear integer programming, Applied Mathematics and Computation 215(6): 2388-2389. Zbl1178.65067

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.