Article
Full entry |
PDF
(0.6 MB)
Feedback
PDF
(0.6 MB)
Feedback
Keywords:
global optimization; Branch and Bound method; convex underestimation; piecewise quadratic; explicit solution
global optimization; Branch and Bound method; convex underestimation; piecewise quadratic; explicit solution
Summary:
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.
References:
[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 3027228 | Zbl 1297.90081
[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 10.1016/S0098-1354(98)00218-X | MR 1365800
[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 10.1023/B:JOGO.0000044768.75992.10 | MR 2109552 | Zbl 1133.90420
[7] Bendiab, O., Cherruault, Y.: A new method for global optimization in two dimensions. Int. J. Biomed. Comput. 38 (1) (1995), 71–73. DOI 10.1016/0020-7101(94)01039-4
[8] Benneouala, T., Cherruault, Y.: Alienor method for global optimization with a large number of variables. Kybernetes 34 (7–8) (2005), 1104–1111. DOI 10.1108/03684920510605911 | Zbl 1130.90397
[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 10.1007/s10957-004-0940-2 | MR 2130074
[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 10.1007/s10898-014-0199-6 | MR 3313179 | Zbl 1318.90057
[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 2425310
[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 2873062 | Zbl 1256.65054
[15] Guillez, A.: Alienor, fractal algorithm for multivariable minimization problems. Math. Comput. Modelling 14 (1990), 245–247. DOI 10.1016/0895-7177(90)90184-O | Zbl 0725.90046
[16] Horst, R., Pardalos, P.M.: Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht, 1995. MR 1377081 | Zbl 0805.00009
[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 10.1007/s11590-008-0110-9 | MR 2472191 | Zbl 1173.90544
[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 10.1051/ro:2006024 | MR 2276160 | Zbl 1180.90249
[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 10.1137/110859129 | MR 3033117 | Zbl 1270.90049
[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: http://dx.doi.org/10.1016/j.joems..08.002 DOI 10.1016/j.joems..08.002
[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 3113955
[23] Ouanes, M.: A new approach for nonconvex SIP. Internat. J. Appl. Math. 81 (3) (2012), 479–486. Zbl 1259.65093
[24] Ouanes, M.: The main diagonal method in C 1 global optimization problem. Internat. J. Appl. Math. 25 (5) (2012), 663–672. MR 3086787 | Zbl 1277.65047
[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 10.12732/ijpam.v84i1.5
[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 10.1016/j.matcom.2014.04.013 | MR 3282082
[27] Pardalos, P.M., Romeijn, H.E.: Handbook of Global Optimization, Volume 2. Nonconvex Optimization and Its Applications. Springer, Boston–Dordrecht–London, 2002. MR 1919528
[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 10.1016/0041-5553(72)90115-2 | MR 0317544
[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 2400670
[30] Sergeyev, Y.D.: A one-dimensional deterministic global minimization algorithm. Comput. Math. Math. Phys. 35 (5) (1995), 705–717. MR 1337015
[31] Sergeyev, Y.D.: Global one-dimensional optimization using smooth auxiliary functions. Math. Programming 81 (1), Ser. A (1998), 127–146. DOI 10.1007/BF01584848 | MR 1617756 | Zbl 0920.90133
[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 1485351 | Zbl 0896.65046
Search
Partner of
