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

El Mouatasim, Abdelkrim; Ellaia, Rachid; de Cursi, Eduardo

doi:10.2478/v10006-011-0024-z

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.

References

Bagirov, A. and Yearwood, J. (2006). A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems, European Journal of Operational Research170(2): 578-596.10.1016/j.ejor.2004.06.014
Search in Google Scholar
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 Mathematics229(1): 283-293.10.1016/j.cam.2008.10.047
Search in Google Scholar
Bouleau, N. (1986). Variables Aléatoires et Simulation, Hermann Editions, Paris.
Search in Google Scholar
Broyden, C. (1970). The convergence of a class of double-rank minimization algorithms, Journal Institute of Mathematics and Its Applications6(1): 76-90.10.1093/imamat/6.1.76
Search in Google Scholar
Correa, R. and Lemaréchal, C. (1993). Convergence of some algorithms for convex minimization, Mathematical Programming62(2): 261-275.10.1007/BF01585170
Search in Google Scholar
Davidon, W. (1991). Variable metric method for minimization, SIAM Journal on Optimization1(1): 1-17.10.1137/0801001
Search in Google Scholar
Dorea, C. (1990). Stopping rules for a random optimization method, SIAM Journal on Control and Optimization28(4): 841-850.10.1137/0328048
Search in Google Scholar
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 Applications2(2): 183-197.
Search in Google Scholar
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 Science16(4): 463-474.
Search in Google Scholar
Fletcher, R. (1970). A new approach to variable metric algorithms, Computer Journal13(3): 317-322.10.1093/comjnl/13.3.317
Search in Google Scholar
Fletcher, R. and Powell, M. (1963). A rapidly convergent descent method for minimization, Computer Journal6(2): 163-168.10.1093/comjnl/6.2.163
Search in Google Scholar
Goldfarb, D. (1970). A family of variable metric methods derived by variational means, Mathematics of Computation24(109): 23-26.10.1090/S0025-5718-1970-0258249-6
Search in Google Scholar
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.
Search in Google Scholar
Kelley, J. (1960). The cutting plane method for solving convex programs, Journal of the Society for Industrial and Applied Mathematics8(4): 703-712.10.1137/0108053
Search in Google Scholar
Kiwiel, K. (1985). Method of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics, Vol. 1133, Springer-Verlag, Berlin.
Search in Google Scholar
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 Science18(4), DOI: 10.2478/v10006-008-0049-0.10.2478/v10006-008-0049-0
Search in Google Scholar
Kryazhimskii, A. (2001). Optimization problems with convex epigraphs. application to optimal control, International Journal of Applied Mathematics and Computer Science11(4): 773-801.
Search in Google Scholar
Larsson, T., Patrksson, M. and Stromberg, A. (1996). Conditional subgradient optimization-theory and applications, European Journal of Operational Research88(2): 382-403.10.1016/0377-2217(94)00200-2
Search in Google Scholar
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.10.1016/B978-0-12-468662-5.50015-X
Search in Google Scholar
Luenberger, D. (1973). Introduction to Linear and Nonlinear Programming, Addison-Wesley Publishing Company, London.
Search in Google Scholar
Luksan, L. and Vlcek, 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.
Search in Google Scholar
Makela, M. and Neittaanmaki, P. (1992). Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control, World Scientific Publishing Co., London.
Search in Google Scholar
Malanowski, K. (2004). Convergence of the Lagrange-Newton method for optimal control problems, International Journal of Applied Mathematics and Computer Science14(4): 531-540.
Search in Google Scholar
Panier, E. (1987). An active set method for solving linearly constrained nonsmooth optimization problems, Mathematical Programming37(3): 269-292.10.1007/BF02591738
Search in Google Scholar
Peng, Y. and Heying, Q. (2009). A filter-variable-metric method for nonsmooth convex constrained optimization, Applied Mathematics and Computation208(1): 119-128.10.1016/j.amc.2008.11.019
Search in Google Scholar
Petersen, I. (2006). Minimax LQG control, International Journal of Applied Mathematics and Computer Science16(3): 309-323.
Search in Google Scholar
Pinter, J. (1996). Global Optimization in Action, Kluwer, Dordrecht.10.1007/978-1-4757-2502-5
Search in Google Scholar
Pogu, M. and Souza de Cursi, J. (1994). Global optimization by random perturbation of the gradient method with a fixed parameter, Journal of Global Optimization5(2): 159-180.10.1007/BF01100691
Search in Google Scholar
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 Optimization2: 121-152.10.1137/0802008
Search in Google Scholar
Shanno, D. (1970). Conditioning of quasi-Newton methods for function minimization, Mathematics of Computation24(111): 647-657.10.1090/S0025-5718-1970-0274029-X
Search in Google Scholar
Souza de Cursi, J. (1991). Introduction aux probabilités, Ecole Centrale Nantes, Nantes.
Search in Google Scholar
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.
Search in Google Scholar
Uryasev, S. (1991). New variable metric algorithms for nondifferentiable optimization problems, Journal of Optimization Theory and Applications71(2): 359-388.10.1007/BF00939925
Search in Google Scholar
Zhang, G. (2009). A note on: A continuous approach to nonlinear integer programming, Applied Mathematics and Computation215(6): 2388-2389.10.1016/j.amc.2009.08.015
Search in Google Scholar

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

Abstract

Paradigm

My account