A nonsmooth version of the univariate optimization algorithm for locating the nearest extremum (locating extremum in nonsmooth univariate optimization)

Marek Smietanski

Open Mathematics, Tome 6 (2008), p. 469-481 / Harvested from The Polish Digital Mathematics Library

Résumé

An algorithm for univariate optimization using a linear lower bounding function is extended to a nonsmooth case by using the generalized gradient instead of the derivative. A convergence theorem is proved under the condition of semismoothness. This approach gives a globally superlinear convergence of algorithm, which is a generalized Newton-type method.

Détail

Publié le : 2008-01-01

Zbl 1155.65050

EUDML-ID : urn:eudml:doc:269692

Bibliographie

[1] Bazaraa M.S., Sherali H.D., Shetty C.M., Nonlinear programming, theory and algorithms, John Wiley & Sons Inc., New York, 1993 | Zbl 0774.90075

[2] Bromberg M., Chang T.S., Global optimization using linear lower bounds: one dimensional case, In: Proceedings of the 29th Conference on Decision and Control, Honolulu, Hawaii, 1990

[3] Chen X., Superlinear convergence of smoothing quasi-Newton methods for nonsmooth equations, J. Comput. Appl. Math., 1997, 80, 105–126 http://dx.doi.org/10.1016/S0377-0427(97)80133-1 | Zbl 0881.65042

[4] Clarke F.H., Optimization and nonsmooth analysis, John Wiley & Sons Inc., New York, 1983 | Zbl 0582.49001

[5] Conn A.R., Gould N.I.M., Toint P.L., Trust-region methods, SIAM, Philadelphia, 2000 | Zbl 0958.65071

[6] Dennis Jr. J.E., Moré J.J., A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp., 1974, 28, 549–560 http://dx.doi.org/10.2307/2005926 | Zbl 0282.65042

[7] Famularo D., Sergeyev Ya.D., Pugliese P., Test problems for Lipschitz univariate global optimization with multiextremal constraints, In: Dzemyda G., Saltenis V., Žilinskas A. (Eds.), Stochastic and global optimization, Kluwer Academic Publishers, Dordrecht, 2002 | Zbl 1211.90180

[8] Hansen P., Jaumard B., Lu S.H., Global optimization of univariate Lipschitz functions I: survey and properties, Math. Program., 1992, 55, 251–273 http://dx.doi.org/10.1007/BF01581202 | Zbl 0825.90755

[9] Harker P.T., Xiao B., Newton’s method for the nonlinear complementarity problem: a B-differentiable equation approach, Math. Program., 1990, 48, 339–357 http://dx.doi.org/10.1007/BF01582262 | Zbl 0724.90071

[10] Kahya E., A class of exponential quadratically convergent iterative formulae for unconstrained optimization., Appl. Math. Comput., 2007, 186, 1010–1017 http://dx.doi.org/10.1016/j.amc.2006.08.040 | Zbl 1121.65067

[11] Mifflin R., Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 1977, 15, 959–972 http://dx.doi.org/10.1137/0315061 | Zbl 0376.90081

[12] Pang J.S., Newton’s method for B-differentiable equations, Math. Oper. Res., 1990, 15, 311–341 http://dx.doi.org/10.1287/moor.15.2.311 | Zbl 0716.90090

[13] Potra F.A., Qi L., Sun D., Secant methods for semismooth equations, Numer. Math., 1998, 80, 305–324 http://dx.doi.org/10.1007/s002110050369 | Zbl 0914.65051

[14] Qi L., Sun J., A nonsmooth version of Newton’s method, Math. Program., 1993, 58, 353–367 http://dx.doi.org/10.1007/BF01581275 | Zbl 0780.90090

[15] Sergeyev Ya.D., Daponte P., Grimaldi D., Molinaro A., Two methods for solving optimization problems arising in electronic measurements and electrical engineering, SIAM J. Optim., 1999, 10, 1–21 http://dx.doi.org/10.1137/S1052623496312393 | Zbl 0953.90054

[16] Shapiro A., On concepts of directional differentiability, J. Optim. Theory Appl., 1990, 66, 477–487 http://dx.doi.org/10.1007/BF00940933 | Zbl 0682.49015

[17] Smietanski M.J., A new versions of approximate Newton method for solving nonsmooth equations, Ph.D. thesis, University of Lódz, Poland, 1999 (in Polish)

[18] Tseng C.L., A Newton-type univariate optimization algorithm for locating the nearest extremum, Eur. J. Oper. Res., 1998, 105, 236–246 http://dx.doi.org/10.1016/S0377-2217(97)00026-X | Zbl 0955.90124