×

On continuation methods for non-linear bi-objective optimization: towards a certified interval-based approach. (English) Zbl 1332.90251

Summary: The global resolution of constrained non-linear bi-objective optimization problems (NLBOO) aims at covering their Pareto-optimal front which is in general a one-manifold in \(\mathbb {R}^2\). Continuation methods can help in this context as they can follow a continuous component of this front once an initial point on it is provided. They constitute somehow a generalization of the classical scalarization framework which transforms the bi-objective problem into a parametric single-objective problem. Recent works have shown that they can play a key role in global algorithms dedicated to bi-objective problems, e.g. population based algorithms, where they allow discovering large portions of locally Pareto optimal vectors, which turns out to strongly support diversification. The contribution of this paper is twofold: we first provide a survey on continuation techniques in global optimization methods for NLBOO, identifying relations between several work and usual limitations, among which the ability to handle inequality constraints. We then propose a rigorous active set management strategy on top of a continuation method based on interval analysis, certified with respect to feasibility, local optimality and connectivity. This allows overcoming the latter limitation as illustrated on a representative bi-objective problem.

MSC:

90C29 Multi-objective and goal programming

Software:

PAINT; NBI; gaol; RealPaver
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allgower, E.L., Georg, K.: Introduction to numerical continuation methods. In: Classics in Applied Mathematics, vol. 45. SIAM, Philadelphia (2003) · Zbl 1036.65047
[2] Askar, S.; Tiwari, A.; Ehrgott, M. (ed.); etal., Multi-objective optimisation problems: a symbolic algorithm for performance measurement of evolutionary computing techniques, No. 5467, 169-182 (2009), Berlin · doi:10.1007/978-3-642-01020-0_17
[3] Beltrán, C., Leykin, A.: Certified numerical homotopy tracking. Exp. Math. 21(1), 69-83 (2012) · Zbl 1238.14048 · doi:10.1080/10586458.2011.606184
[4] Beyn, W.-J., Effenberger, C., Kressner, D.: Continuation of eigenvalues and invariant pairs for parameterized nonlinear eigenvalue problems. Numer. Math. 119, 489-516 (2011) · Zbl 1232.65077 · doi:10.1007/s00211-011-0392-1
[5] Boissonnat, J.-D., Ghosh, A.: Triangulating smooth submanifolds with light scaffolding. Math. Comput. Sci. 4, 431-461 (2010) · Zbl 1229.68077 · doi:10.1007/s11786-011-0066-5
[6] Das, I., Dennis, J.: Normal-boundary intersection: a new method for generating the pareto surface in nonlinear multicriteria optimization problems. SIAM J. Optim. 8(3), 631-657 (1998) · Zbl 0911.90287 · doi:10.1137/S1052623496307510
[7] Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer, Berlin (2005) · Zbl 1132.90001
[8] Eichfelder, G.: Scalarizations for adaptively solving multi-objective optimization problems. Comput. Optim. Appl. 44(2), 249-273 (2009) · Zbl 1184.90152 · doi:10.1007/s10589-007-9155-4
[9] Erfani, T., Utyuzhnikov, S.: Directed search domain: a method for even generation of the pareto frontier in multiobjective optimization. Eng. Optim. 43(5), 467-484 (2011) · doi:10.1080/0305215X.2010.497185
[10] Faudot, D., Michelucci, D.: A new robust algorithm to trace curves. Reliab. Comput. 13(4), 309-324 (2007) · Zbl 1120.65016 · doi:10.1007/s11155-007-9036-7
[11] Goldsztejn, A., Granvilliers, L.: A new framework for sharp and efficient resolution of NCSP with manifolds of solutions. Constraints 15(2), 190-212 (2010) · Zbl 1203.65086 · doi:10.1007/s10601-009-9082-3
[12] Goualard F.: GAOL 3.1.1: Not Just Another Interval Arithmetic Library. LINA, 4.0 edition (2006) · Zbl 0787.65037
[13] Granvilliers, L., Benhamou, F.: Algorithm 852: realPaver: an interval solver using constraint satisfaction techniques. ACM Trans. Math. Softw. 32(1), 138-156 (2006) · Zbl 1346.65020 · doi:10.1145/1132973.1132980
[14] Guddat, J.; Th. Jongen, H.; Nowack, D.; Gmez-Fernandez, JA (ed.); etal., Parametric optimization: pathfollowing with jumps, No. 1354, 43-53 (1988), Berlin · Zbl 0661.90083 · doi:10.1007/BFb0089582
[15] Guddat, J., Vazquez, F.G., Nowack, D., Ruckmann, J.: A modified standard embedding with jumps in nonlinear optimization. Eur. J. Oper. Res. 169(3), 1185-1206 (2006) · Zbl 1079.90131 · doi:10.1016/j.ejor.2004.08.048
[16] Harada, K., Sakuma, J., Kobayashi, S.: Local search for multiobjective function optimization: pareto descent method. In: GECCO, pp. 659-666. ACM (2006) · Zbl 1064.90041
[17] Harada, K., Sakuma, J., Kobayashi, S., Ono, I.: Uniform sampling of local pareto-optimal solution curves by pareto path following and its applications in multi-objective GA. In: GECCO, pp. 813-820. ACM (2007) · Zbl 1079.90627
[18] Harada, K., Sakuma, J., Ono, I., Kobayashi, S.: Constraint-handling method for multi-objective function optimization: pareto descent repair operator. In: Obayashi, S., et al. (eds.) Evolutionary Multi-Criterion Optimization. volume 4403 of LNCS, pp. 156-170. Springer, Berlin (2007)
[19] Hartikainen, M., Miettinen, K., Wiecek, M.M.: Constructing a pareto front approximation for decision making. Math. Meth. Oper. Res. 73(2), 209-234 (2011) · Zbl 1216.49002 · doi:10.1007/s00186-010-0343-0
[20] Hartikainen, M., Miettinen, K., Wiecek, M.M.: Paint: pareto front interpolation for nonlinear multiobjective optimization. Comput. Optim. Appl. 52(3), 845-867 (2012) · Zbl 1259.90119 · doi:10.1007/s10589-011-9441-z
[21] Hillermeier, C.: Generalized homotopy approach to multiobjective optimization. J. Optim. Theor. Appl. 110(3), 557-583 (2001) · Zbl 1064.90041 · doi:10.1023/A:1017536311488
[22] Hillermeier, C.: Nonlinear Multiobjective Optimization: A Generalized Homotopy Approach, vol. 135. Birkäuser, Basel (2001) · Zbl 0966.90069 · doi:10.1007/978-3-0348-8280-4
[23] Kearfott, B., Xing, Z.: An interval step control for continuation methods. SIAM J. Numer. Anal. 31(3), 892-914 (1994) · Zbl 0809.65050 · doi:10.1137/0731048
[24] Lara, A., Sanchez, G., Coello, C., Schütze, O.: HCS: a new local search strategy for memetic multiobjective evolutionary algorithms. IEEE Trans. Evol. Comput. 14(1), 112-132 (2010) · doi:10.1109/TEVC.2009.2024143
[25] Leyffer, S.: A complementarity constraint formulation of convex multiobjective optimization problems. INFORMS J. Comput. 21(2), 257-267 (April 2009) · Zbl 1243.90198
[26] Lovison, A.: Singular continuation: generating piecewise linear approximations to pareto sets via global analysis. SIAM J. Optim. 21(2), 463-490 (2011) · Zbl 1226.90094 · doi:10.1137/100784746
[27] Lovison, A.: Global search perspectives for multiobjective optimization. J. Glob. Optim. 57(2), 385-398 (2013) · Zbl 1274.90274 · doi:10.1007/s10898-012-9943-y
[28] Lundberg, B., Poore, A.: Numerical continuation and singularity detection methods for parametric nonlinear programming. SIAM J. Optim. 3(1), 134-154 (1993) · Zbl 0811.90103 · doi:10.1137/0803007
[29] Martin, B., Goldsztejn, A., Granvilliers, L., Jermann, C.: Certified parallelotope continuation for one-manifolds. SIAM J. Numer. Anal. 51(6), 3373-3401 (2013) · Zbl 1298.65088 · doi:10.1137/130906544
[30] Messac, A., Ismail-Yahaya, A., Mattson, C.: The normalized normal constraint method for generating the pareto frontier. Struct. Multidiscip. Optim. 25(2), 86-98 (2003) · Zbl 1243.90200 · doi:10.1007/s00158-002-0276-1
[31] Messac, A., Mattson, C.: Generating well-distributed sets of pareto points for engineering design using physical programming. Optim. Eng. 3(4), 431-450 (2002) · Zbl 1079.90627 · doi:10.1023/A:1021179727569
[32] Messac, A., Mattson, C.: Normal constraint method with guarantee of even representation of complete pareto frontier. AIAA J. 42, 2101-2111 (2004) · Zbl 1074.46043 · doi:10.2514/1.8977
[33] Miettinen, K.: Nonlinear Multiobjective Optimization, volume 12 of International Series in Operations Research and Management Science. Kluwer, Dordrecht (1999) · Zbl 0949.90082
[34] Neumaier, A.: Interval Methods for Systems of Equations. Cambridge University Press, Cambridge (1991) · Zbl 0715.65030
[35] Pereyra, V.: Fast computation of equispaced pareto manifolds and pareto fronts for multiobjective optimization problems. Math. Comput. Simul. 79(6), 1935-1947 (2009) · Zbl 1159.65060 · doi:10.1016/j.matcom.2007.02.007
[36] Pereyra, V., Saunders, M., Castillo, J.: Equispaced pareto front construction for constrained bi-objective optimization. Math. Comput. Model. 57(9-10), 2122-2131 (2013) · Zbl 1286.90138 · doi:10.1016/j.mcm.2010.12.044
[37] Porta, J.-M., Jaillet, L., Bohigas, O.: Randomized path planning on manifolds based on higher-dimensional continuation. Int. J. Robot. Res. 31(2), 201-215 (2012) · doi:10.1177/0278364911432324
[38] Potschka, A., Logist, F., Van Impe, J., Bock, H.: Tracing the Pareto frontier in bi-objective optimization problems by ODE techniques. Numer. Algorithms 57(2), 217-233 (2011) · Zbl 1217.65110 · doi:10.1007/s11075-010-9425-6
[39] Rakowska, J., Haftka, R., Watson, L.: An active set algorithm for tracing parametrized optima. Struct. Optim. 3(1), 29-44 (1991) · doi:10.1007/BF01743487
[40] Rakowska, J., Haftka, R., Watson, L.: Multi-objective control-structure optimization via homotopy methods. SIAM J. Optim. 3(3), 654-667 (1993) · Zbl 0787.65037 · doi:10.1137/0803033
[41] Rao, J., Papalambros, P.: A non-linear programming continuation strategy for one parameter design optimization problems. In: ASME Design Automation Conference, pp. 77-89 (1989)
[42] Rigoni, E., Poles, S.: NBI and MOGA-II, two complementary algorithms for multi-objective optimizations. In: Practical Approaches to Multi-Objective Optimization, number 04461 in Dagstuhl, Seminar (2005) · Zbl 0911.90287
[43] Ringkamp, M., Ober-Blbaum, S., Dellnitz, M., Schütze, O.: Handling high-dimensional problems with multi-objective continuation methods via successive approximation of the tangent space. Eng. Optim. 44(9), 1117-1146 (2012) · doi:10.1080/0305215X.2011.634407
[44] Ruzika, S., Wiecek, M.M.: Approximation methods in multiobjective programming. J. Optim. Theor. Appl. 126(3), 473-501 (2005) · Zbl 1093.90057 · doi:10.1007/s10957-005-5494-4
[45] Schütze, O., Coello, C.: Coello, S. Mostaghim, E. Talbi, and M. Dellnitz. Hybridizing evolutionary strategies with continuation methods for solving multi-objective problems. Eng. Optim. 40, 383-402 (2008) · doi:10.1080/03052150701821328
[46] Schütze, O., Dell’Aere, A., Dellnitz, M.: On continuation methods for the numerical treatment of multi-objective optimization problems. In: Branke, J. et al. (ed.) Practical Approaches to Multi-Objective Optimization, number 04461 in Dagstuhl Seminar (2005) · Zbl 1165.90637
[47] Schütze, O., Lara, A., Coello Coello, C.: Evolutionary continuation methods for optimization problems. In: GECCO, pp. 651-658. ACM (2009) · Zbl 1229.68077
[48] Smale, S.: Newton’s method estimates from data at one point. In: Ewing, R.E., et al. (eds.) The Merging of Disciplines in Pure, Applied and Computational Mathematics, pp. 185-196. Springer, New York (1986) · Zbl 0613.65058
[49] Utyuzhnikov, S., Fantini, P., Guenov, M.: A method for generating a well-distributed pareto set in nonlinear multiobjective optimization. J. Comput. Appl. Math. 223(2), 820-841 (2009) · Zbl 1165.90637 · doi:10.1016/j.cam.2008.03.011
[50] Zhang, Z.: Immune optimization algorithm for constrained nonlinear multiobjective optimization problems. Appl. Soft Comput. 7(3), 840-857 (2007) · doi:10.1016/j.asoc.2006.02.008
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.