×

First order rejection tests for multiple-objective optimization. (English) Zbl 1301.90082

Summary: Three rejection tests for multi-objective optimization problems based on first order optimality conditions are proposed. These tests can certify that a box does not contain any local minimizer, and thus it can be excluded from the search process. They generalize previously proposed rejection tests in several regards: Their scope include inequality and equality constrained smooth or nonsmooth multiple objective problems. Reported experiments show that they allow quite efficiently removing the cluster effect in mono-objective and multi-objective problems, which is one of the key issues in continuous global deterministic optimization.

MSC:

90C29 Multi-objective and goal programming
90C26 Nonconvex programming, global optimization
90C46 Optimality conditions and duality in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alefeld, G., Herzberger, J.: Introduction to interval computations. Comput. Sci. Appl. Math. (1974) · Zbl 0552.65041
[2] Barichard, V., Deleau, H., Hao, J.K., Saubion, F.: A hybrid evolutionary algorithm for CSP. In: Artificial Evolution, volume 2936 of LNCS, pp. 79-90. Springer, Berlin (2004) · Zbl 1098.68643
[3] Barichard, V., Hao, J.K.: A population and interval constraint propagation algorithm. In: Evolutionary Multi-Criterion Optimization, volume 2632 of LNCS, pp. 72-72. Springer, Berlin (2003) · Zbl 1036.90565
[4] Clarke, F.H.: Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathematics, Philadephia (1990) · Zbl 0696.49002 · doi:10.1137/1.9781611971309
[5] Domes, F.: Gloptlab: a configurable framework for the rigorous global solution of quadratic constraint satisfaction problems. Optim. Methods Softw. 24(4-5), 727-747 (2009) · Zbl 1180.90217 · doi:10.1080/10556780902917701
[6] Du, K., Kearfott, R.B.: The cluster problem in multivariate global optimization. J. Glob. Optim. 5, 253-265 (1994) · Zbl 0824.90121 · doi:10.1007/BF01096455
[7] Duran, M.A., Grossman, I.E.: An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Math. Program. 36, 307-339 (1986) · Zbl 0619.90052 · doi:10.1007/BF02592064
[8] Garloff, J.: Interval gaussian elimination with pivot tightening. SIAM J. Matrix Anal. Appl. 30(4), 1761-1772 (2009) · Zbl 1181.65047 · doi:10.1137/080729621
[9] Goldberg, D.: What every computer scientist should know about floating-point arithmetic. Comput. Surv. 23(1), 5-48 (1991) · doi:10.1145/103162.103163
[10] Goualard, F.: GAOL 3.1.1: Not Just Another Interval Arithmetic Library, 4th edn. Laboratoire d’Informatique de Nantes-Atlantique (2006) · Zbl 1243.90205
[11] Granvilliers, L., Goldsztejn, A.: A branch-and-bound algorithm for unconstrained global optimization. In: Proceedings of the 14th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (SCAN) (2010) · Zbl 1203.65086
[12] Hansen, E.: Global Optimization Using Interval Analysis, 2nd edn. Marcel Dekker, NY (1992) · Zbl 0762.90069
[13] Hansen, E.R., Walster, G.W.: Bounds for Lagrange multipliers and optimal points. Comput. Math. Appl. 25(1011), 59-69 (1993) · Zbl 0795.90064 · doi:10.1016/0898-1221(93)90282-Z
[14] Ichida, K., Fujii, Y.: Multicriterion optimization using interval analysis. Computing 44, 47-57 (1990) · Zbl 0699.65053 · doi:10.1007/BF02247964
[15] Jahn, J.: Multiobjective search algorithm with subdivision technique. Comput. Optim. Appl. 35(2), 161-175 (2006) · Zbl 1153.90533 · doi:10.1007/s10589-006-6450-4
[16] Jaulin, L., Kieffer, M., Didrit, O., Walter, E.: Applied Interval Analysis with Examples in Parameter and State Estimation, Robust Control and Robotics. Springer, Berlin (2001) · Zbl 1023.65037
[17] Kearfott, R.B.: Interval computations: introduction, uses, and resources. Euromath Bull. 2(1), 95-112 (1996) · Zbl 1465.65041
[18] Kearfott, R.B.: An interval branch and bound algorithm for bound constrained optimization problems. J. Glob. Optim. 2, 259-280 (1992) · Zbl 0760.90085 · doi:10.1007/BF00171829
[19] Kearfott, R.B.: Interval computations, rigour and non-rigour in deterministic continuous global optimization. Optim. Methods Softw. 26(2), 259-279 (2011) · Zbl 1228.90080 · doi:10.1080/10556781003636851
[20] Knueppel, O.: PROFIL/BIAS—a fast interval library. Computing 53(3-4), 277-287 (1994) · Zbl 0808.65055 · doi:10.1007/BF02307379
[21] Kubica, BJ., Niewiadomska-Szynkiewicz, E.: An improved interval global optimization method and its application to price management problem. In: Applied Parallel Computing. State of the Art in Scientific Computing, volume 4699 of LNCS, pp. 1055-1064. Springer, Berlin (2007)
[22] Kubica, B.J., Wozniak, A.: Interval methods for computing the pareto-front of a multicriterial problem. In: Parallel Processing and Applied Mathematics, volume 4967 of LNCS, pp. 1382-1391. Springer, Berlin (2008)
[23] Kubica, B.J., Wozniak, A.: Using the second-order information in pareto-set Computations of a multi-criteria problem. In: Applied Parallel and Scientific Computing, volume 7134 of LNCS, pp. 137-147. Springer, Berlin (2012)
[24] Lin, Y.; Stadtherr, MA; Floudas, CA (ed.); Pardalos, PM (ed.), Encyclopedia of Optimization, 1937-1943 (2009), USA
[25] Makino, K.; Berz, M.; Corliss, G. (ed.); Faure, C. (ed.); Griewank, A. (ed.); Hascoët, L. (ed.); Naumann, U. (ed.), Automatic differentiation of algorithms (2002), New York
[26] Miettinen, K.M.: Nonlinear Multiobjective Optimization. Kluwer, Dordrecht (1998) · doi:10.1007/978-1-4615-5563-6
[27] Moore, R.: Interval Analysis. Prentice-Hall, Englewood Cliffs, NJ (1966) · Zbl 0176.13301
[28] Neumaier, A.: Interval Methods for Systems of Equations. Cambridge Univ Press, Cambridge (1990) · Zbl 0715.65030
[29] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Berlin (2006) · Zbl 1104.65059
[30] Rohn, J.: Forty necessary and sufficient conditions for regularity of interval matrices: a survey. Electron. J. Linear Algebra 18, 500-512 (2009) · Zbl 1189.65088
[31] Ruetsch, G.R.: An interval algorithm for multi-objective optimization. Struct. Multidiscip. Optim. 30, 27-37 (2005) · Zbl 1243.90205 · doi:10.1007/s00158-004-0496-7
[32] Ruetsch, G.R.: Using interval techniques of direct comparison and differential formulation to solve a multi-objective optimization problem (patent US-7742902), (2010)
[33] Rump, SM; Csendes, T. (ed.), Developments in reliable computing (1999), Dordrecht
[34] Schichl, H., Neumaier, A.: Exclusion regions for systems of equations. SIAM J. Numer. Anal. 42(1), 383-408 (2004) · Zbl 1080.65041 · doi:10.1137/S0036142902418898
[35] Schichl, H., Neumaier, A.: Interval analysis on directed acyclic graphs for global optimization. J. Glob. Optim. 33(4), 541-562 (2005) · Zbl 1094.65061 · doi:10.1007/s10898-005-0937-x
[36] Schichl, H., Neumaier, A.: Transposition theorems and qualification-free optimality conditions. SIAM J. Optim. 17(4), 1035-1055 (2006) · Zbl 1136.90043 · doi:10.1137/05063129X
[37] Shcherbina, O., Neumaier, A., Sam-Haroud D., Vu, X.-H., Nguyen, T.-V.: Benchmarking global optimization and constraint satisfaction codes. In: Bliek, C., Jermann, C., Neumaier, A. (eds.) Global Optimization and Constraint Satisfaction, volume 2861 of Lecture Notes in Computer Science, pp. 211-222. Springer, Berlin (2003) · Zbl 1296.90004
[38] Soares, G.L., Parreiras, R.O., Jaulin, L., Vasconcelos, J.A., Maia, C.A.: Interval robust multi-objective algorithm. Nonlinear Anal. Theor Methods Appl. 71(12), 1818-1825 (2009) · Zbl 1238.90140 · doi:10.1016/j.na.2009.02.077
[39] Tóth, B.G., Hernndez, J.F.: Interval Methods for Single and Bi-objective Optimization Problems Applied to Competitive Facility Location Models. LAP Lambert Academic Publishing (2010)
[40] Vu, X.-H., Schichl, H., Sam-Haroud, D.: Interval propagation and search on directed acyclic graphs for numerical constraint solving. J. Glob. Optim. 45(4), 499-531 (2009) · Zbl 1179.90267 · doi:10.1007/s10898-008-9386-7
[41] Wolfram Research Inc., Mathematica. Champaign, Illinois, Version 7.0 (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.