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.
@article{bwmeta1.element.bwnjournal-article-amcv21i2p317bwm,
author = {Abdelkrim El Mouatasim and Rachid Ellaia and Eduardo Souza de Cursi},
title = {Random perturbation of the projected variable metric method for nonsmooth nonconvex optimization problems with linear constraints},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {21},
year = {2011},
pages = {317-329},
zbl = {1271.49022},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv21i2p317bwm}
}
Abdelkrim El Mouatasim; Rachid Ellaia; 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, Tome 21 (2011) pp. 317-329. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv21i2p317bwm/
[000] 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. | Zbl 1085.90045
[001] 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. | Zbl 1166.65028
[002] Bouleau, N. (1986). Variables Aléatoires et Simulation, Hermann Editions, Paris. | Zbl 0659.60001
[003] Broyden, C. (1970). The convergence of a class of double-rank minimization algorithms, Journal Institute of Mathematics and Its Applications 6(1): 76-90. | Zbl 0223.65023
[004] Correa, R. and Lemaréchal, C. (1993). Convergence of some algorithms for convex minimization, Mathematical Programming 62(2): 261-275. | Zbl 0805.90083
[005] Davidon, W. (1991). Variable metric method for minimization, SIAM Journal on Optimization 1(1): 1-17. | Zbl 0752.90062
[006] Dorea, C. (1990). Stopping rules for a random optimization method, SIAM Journal on Control and Optimization 28(4): 841-850. | Zbl 0711.65043
[007] 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. | Zbl 05703861
[008] 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. | Zbl 1160.90694
[009] Fletcher, R. (1970). A new approach to variable metric algorithms, Computer Journal 13(3): 317-322. | Zbl 0207.17402
[010] Fletcher, R. and Powell, M. (1963). A rapidly convergent descent method for minimization, Computer Journal 6(2): 163-168. | Zbl 0132.11603
[011] Goldfarb, D. (1970). A family of variable metric methods derived by variational means, Mathematics of Computation 24(109): 23-26. | Zbl 0196.18002
[012] 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.
[013] Kelley, J. (1960). The cutting plane method for solving convex programs, Journal of the Society for Industrial and Applied Mathematics 8(4): 703-712. | Zbl 0098.12104
[014] Kiwiel, K. (1985). Method of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, Vol. 1133, Springer-Verlag, Berlin. | Zbl 0561.90059
[015] 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.
[016] Kryazhimskii, A. (2001). Optimization problems with convex epigraphs. application to optimal control, International Journal of Applied Mathematics and Computer Science 11(4): 773-801. | Zbl 1012.49005
[017] Larsson, T., Patrksson, M. and Stromberg, A. (1996). Conditional subgradient optimization-theory and applications, European Journal of Operational Research 88(2): 382-403. | Zbl 0913.90225
[018] 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. | Zbl 0533.49023
[019] Luenberger, D. (1973). Introduction to Linear and Nonlinear Programming, Addison-Wesley Publishing Company, London. | Zbl 0297.90044
[020] 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.
[021] Makela, M. and Neittaanmaki, P. (1992). Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control, World Scientific Publishing Co., London. | Zbl 0757.49017
[022] 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. | Zbl 1082.49033
[023] Panier, E. (1987). An active set method for solving linearly constrained nonsmooth optimization problems, Mathematical Programming 37(3): 269-292. | Zbl 0641.90061
[024] Peng, Y. and Heying, Q. (2009). A filter-variable-metric method for nonsmooth convex constrained optimization, Applied Mathematics and Computation 208(1): 119-128. | Zbl 1160.65028
[025] Petersen, I. (2006). Minimax LQG control, International Journal of Applied Mathematics and Computer Science 16(3): 309-323. | Zbl 1136.93465
[026] Pinter, J. (1996). Global Optimization in Action, Kluwer, Dordrecht. | Zbl 0842.90110
[027] 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. | Zbl 0827.90132
[028] 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. | Zbl 0761.90090
[029] Shanno, D. (1970). Conditioning of quasi-Newton methods for function minimization, Mathematics of Computation 24(111): 647-657. | Zbl 0225.65073
[030] Souza de Cursi, J. (1991). Introduction aux probabilités, Ecole Centrale Nantes, Nantes.
[031] 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. | Zbl 1176.90649
[032] Uryasev, S. (1991). New variable metric algorithms for nondifferentiable optimization problems, Journal of Optimization Theory and Applications 71(2): 359-388. | Zbl 0793.90078
[033] Zhang, G. (2009). A note on: A continuous approach to nonlinear integer programming, Applied Mathematics and Computation 215(6): 2388-2389. | Zbl 1178.65067