Geodesic
New technique for solving univariate global optimization
Archivum mathematicum, Tome 53 (2017) no. 1, pp. 19-33
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper, a new global optimization method is proposed for an optimization problem with twice differentiable objective function a single variable with box constraint. The method employs a difference of linear interpolant of the objective and a concave function, where the former is a continuous piecewise convex quadratic function underestimator. The main objectives of this research are to determine the value of the lower bound that does not need an iterative local optimizer. The proposed method is proven to have a finite convergence to locate the global optimum point. The numerical experiments indicate that the proposed method competes with another covering methods.
In this paper, a new global optimization method is proposed for an optimization problem with twice differentiable objective function a single variable with box constraint. The method employs a difference of linear interpolant of the objective and a concave function, where the former is a continuous piecewise convex quadratic function underestimator. The main objectives of this research are to determine the value of the lower bound that does not need an iterative local optimizer. The proposed method is proven to have a finite convergence to locate the global optimum point. The numerical experiments indicate that the proposed method competes with another covering methods.
DOI : 10.5817/AM2017-1-19
Classification : 90C26, 90C30
Keywords: global optimization; Branch and Bound method; convex underestimation; piecewise quadratic; explicit solution 
@article{10_5817_AM2017_1_19,
     author = {Aaid, Djamel and Noui, Amel and Ouanes, Mohand},
     title = {New technique for solving univariate global optimization},
     journal = {Archivum mathematicum},
     pages = {19--33},
     year = {2017},
     volume = {53},
     number = {1},
     doi = {10.5817/AM2017-1-19},
     mrnumber = {3636679},
     zbl = {06738496},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.5817/AM2017-1-19/}
}
TY  - JOUR
AU  - Aaid, Djamel
AU  - Noui, Amel
AU  - Ouanes, Mohand
TI  - New technique for solving univariate global optimization
JO  - Archivum mathematicum
PY  - 2017
SP  - 19
EP  - 33
VL  - 53
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.5817/AM2017-1-19/
DO  - 10.5817/AM2017-1-19
LA  - en
ID  - 10_5817_AM2017_1_19
ER  - 
%0 Journal Article
%A Aaid, Djamel
%A Noui, Amel
%A Ouanes, Mohand
%T New technique for solving univariate global optimization
%J Archivum mathematicum
%D 2017
%P 19-33
%V 53
%N 1
%U http://geodesic.mathdoc.fr/articles/10.5817/AM2017-1-19/
%R 10.5817/AM2017-1-19
%G en
%F 10_5817_AM2017_1_19
Aaid, Djamel; Noui, Amel; Ouanes, Mohand. New technique for solving univariate global optimization. Archivum mathematicum, Tome 53 (2017) no. 1, pp. 19-33. doi: 10.5817/AM2017-1-19

[1] Aaid, D.: Étude numérique comparative entre des méthodes de résolution d’un problème de transport à quatre indices avec capacités. Thése de l'université de Constantine (2010), http://bu.umc.edu.dz/theses/math/AAI5587.pdf

[2] Aaid, D., Noui, A., Le Thi, H.A., Zidna, A.: A modified classical algorithm ALPT4C for solving a capacitated four-index transportation problem. Acta Math. Vietnam. 37 (3) (2012), 379–390. | MR | Zbl

[3] Aaid, D., Noui, A., Ouanes, M.: Piecewise quadratic underestimation for global optimization. JSLAROMAD II Tiziouzou. Algeria, 28 – 30 Octobre 2013 (2013).

[4] Aaid, D., Noui, A., Zidna, A., Ouanes, M.: A quadratic branch and bound with Alienor method for global optimization. MAGO'2014, Málaga, Spain, 1 – 4 September, 2014.

[5] Adjiman, C.S., Androulakis, I.P., Floudas, C.A.: A global optimization method, alpha BB, for general twice differentiable NLPs – II. Implementation and computational results. Internat. J. Comput. Appl. in Chem. Engrg. 29 (3) (1998), 1159–1179. | DOI | MR

[6] Akrotirianakis, I.G., Floudas, C.A.: Computational experience with a new class of convex underestimators: box-constrained NLP problems. J. Global Optim. 29 (3) (2004), 249–264. | DOI | MR | Zbl

[7] Bendiab, O., Cherruault, Y.: A new method for global optimization in two dimensions. Int. J. Biomed. Comput. 38 (1) (1995), 71–73. | DOI

[8] Benneouala, T., Cherruault, Y.: Alienor method for global optimization with a large number of variables. Kybernetes 34 (7–8) (2005), 1104–1111. | DOI | Zbl

[9] Caratzoulas, S., Floudas, C.A.: A trigonometric convex underestimator for the base functions in Fourier space. J. Optim. Theory Appl. 124 (2) (2005), 336–362. | DOI | MR

[10] Cartis, C., Fowkes, J.M., Gould, N.I.M.: Branching and bounding improvements for global optimization algorithms with Lipschitz continuity properties. J. Global Optim. 61 (3) (2015), 429–457. | DOI | MR | Zbl

[11] Cherruault, Y., Mora, G.: Optimisation globale : théorie des courbes alpha-denses. Economica Paris, 2005.

[12] Chrysanthos, E., Gounaris, C., Floudas, A.: Tight convex underestimators for $C^2$-continuous problems. I. Univariate functions. J. Global Optim. 42 (1) (2008). | MR

[13] Grosan, C., Abraham, A.: On a class of global optimization test functions. Neural Network World, http://falklands.globat.com/~softcomputing.net/nnw2009.pdf

[14] Guettal, D., Ziadi, A.: Reducing transformation and global optimization. Appl. Math. Comput. 218 (2012), 5848–5860. | MR | Zbl

[15] Guillez, A.: Alienor, fractal algorithm for multivariable minimization problems. Math. Comput. Modelling 14 (1990), 245–247. | DOI | Zbl

[16] Horst, R., Pardalos, P.M.: Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht, 1995. | MR | Zbl

[17] Kvasov, D.E, Sergeyev, Y.D.: A univariate global search working with a set of Lipschitz constants for the first derivative. Optim. Lett. 3 (2) (2009), 303–318. | DOI | MR | Zbl

[18] Le Thi, H.A., Ouanes, M.: Convex quadratic underestimation and branch and bound for univariate global optimization with one nonconvex constraint. RAIRO Oper. Res. 40 (2006), 285–302. | DOI | MR | Zbl

[19] Lera, D., Sergeyev, Y.D.: Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives. SIAM J. Optim. 23 (1) (2013), 508–529. | DOI | MR | Zbl

[20] Leslous, F., Marthon, P., Oukacha, B., Ouanes, M.: Nonconvex optimization based on DC programming and DCA in the search of a global optimum of a nonconvex function. J. Egyptian Math. Soc. (2015). DOI:  | DOI

[21] Noui, A., Aaid, D., Ouanes, M.: An efficient algorithm for the Bernstein polynomial approach to global optimization. JSLAROMAD II, Tiziouzou, Algeria, 2013, 28–30 Octobre 2013.

[22] Ouanes, M.: A combined descent gradient method and descritization method for convex SIP. Internat. J. Appl. Math. 25 (4) (2012), 503–513. | MR

[23] Ouanes, M.: A new approach for nonconvex SIP. Internat. J. Appl. Math. 81 (3) (2012), 479–486. | Zbl

[24] Ouanes, M.: The main diagonal method in C 1 global optimization problem. Internat. J. Appl. Math. 25 (5) (2012), 663–672. | MR | Zbl

[25] Ouanes, M.: New underestimator for multivariate global optimization with box costraints. Internat. J. of Pure and Appl. Math. 84 (1) (2013), 73–83. | DOI

[26] Ouanes, M., Le Thi, H.A., Trong, P.N., Zidna, A.: New quadratic lower bound for multivariate functions in global optimization. Math. Comput. Simulation 109 (2015), 197–211. | DOI | MR

[27] Pardalos, P.M., Romeijn, H.E.: Handbook of Global Optimization, Volume 2. Nonconvex Optimization and Its Applications. Springer, Boston–Dordrecht–London, 2002. | MR

[28] Piyavskii, S.A.: An algorithm for finding the absolute extremum of a function. USSR Computational Mathematics and Mathematical Physics 12 (4) (1972), 57–67. | DOI | MR

[29] Rahal, M., Ziadi, A.: A new extention of Piyavski’s method to holder functions of sveral variables. Appl. Math. Comput. 218 (2012), 478–488. | MR

[30] Sergeyev, Y.D.: A one-dimensional deterministic global minimization algorithm. Comput. Math. Math. Phys. 35 (5) (1995), 705–717. | MR

[31] Sergeyev, Y.D.: Global one-dimensional optimization using smooth auxiliary functions. Math. Programming 81 (1), Ser. A (1998), 127–146. | DOI | MR | Zbl

[32] Shpak, A.: Global optimization in one-dimensional case using analytically defined derivatives of objective function. Comput. Sci. J. Moldova 3 (8) (1995), 168–184. | MR | Zbl

Cité par Sources :