Tracing locally Pareto-optimal points by numerical integration. (English) Zbl 1477.90095
Summary: We suggest a novel approach for the efficient and reliable approximation of the Pareto front of sufficiently smooth unconstrained biobjective optimization problems. Optimality conditions formulated for weighted sum scalarizations of the problem yield a description of (parts of) the Pareto front as a parametric curve, parameterized by the scalarization parameter (i.e., the weight in the weighted sum scalarization). Its sensitivity w.r.t. parameter variations can be described by an ordinary differential equation (ODE). Starting from an arbitrary initial Pareto-optimal solution, the Pareto front can then be traced by numerical integration. We provide an error analysis based on Lipschitz properties and suggest an explicit Runge-Kutta method for the numerical solution of the ODE. The method is validated and compared with a predictor-corrector method on biobjective convex quadratic programming problems and the biobjective test function ZDT3, for which the exact solution is explicitly known and numerically tested on complex biobjective shape optimization problems involving finite element discretizations of the state equation.
MSC:
| 90C29 | Multi-objective and goal programming |
| 90B50 | Management decision making, including multiple objectives |
| 34A12 | Initial value problems, existence, uniqueness, continuous dependence and continuation of solutions to ordinary differential equations |
| 49Q10 | Optimization of shapes other than minimal surfaces |
| 60G55 | Point processes (e.g., Poisson, Cox, Hawkes processes) |
Software:
NBIReferences:
| [1] | R. P. Agarwal and D. O’Regan, An Introduction to Ordinary Differential Equations, Universitext, Springer, New York, 2008, https://doi.org/10.1007/978-0-387-71276-5. · Zbl 1158.34001 |
| [2] | E. Allgower and K. Georg, Introduction to Numerical Continuation Methods, SIAM, Philadelphia, 2003. · Zbl 1036.65047 |
| [3] | U. M. Ascher and L. R. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, SIAM, Philadelphia, 1998, https://doi.org/10.1137/1.9781611971392. · Zbl 0908.65055 |
| [4] | L. Bittner, On Shape Calculus with Elliptic PDE Constraints in Classical Function Spaces, Ph.D. thesis, University of Wuppertal, Germany, 2018. |
| [5] | M. Bolten, H. Gottschalk, C. Hahn, and M. Saadi, Numerical shape optimization to decrease failure probability of ceramic structures, Comput. Vis. Sci., 21 (2019), pp. 1-10, https://doi.org/110.1007/s00791-019-00315-z. · Zbl 07704833 |
| [6] | M. Bolten, H. Gottschalk, and S. Schmitz, Minimal failure probability for ceramic design via shape control, J. Optim. Theory Appl., 166 (2015), pp. 983-1001. · Zbl 1322.49070 |
| [7] | D. Braess, Finite Elements. Theory, Fast Solvers, and Applications in Solid Mechanics, Cambridge University Press, Cambridge, 1997. · Zbl 0894.65054 |
| [8] | J. C. Butcher, Numerical Methods for Ordinary Differential Equations, 3rd ed., Wiley, New York, 2016, https://doi.org/10.1002/9781119121534. With a foreword by J. M. Sanz-Serna. · Zbl 1354.65004 |
| [9] | I. Das and J. Dennis, A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems, Struct. Optim., 14 (1997), pp. 63-69, https://doi.org/10.1007/BF01197559. |
| [10] | M. Dellnitz, O. Schütze, and T. Hestermeyer, Covering Pareto sets by multilevel subdivision techniques, J. Optim. Theory Appl., 124 (2005), pp. 113-136. · Zbl 1137.90015 |
| [11] | O. T. Doganay, H. Gottschalk, C. Hahn, K. Klamroth, J. Schultes, and M. Stiglmayr, Gradient based biobjective shape optimization to improve reliability and cost of ceramic components, Optim. Eng., 21 (2020), pp. 1359-1387, https://doi.org/10.1007/s11081-019-09478-7. · Zbl 1452.74095 |
| [12] | M. Ehrgott, Multicriteria Optimization, 2nd ed., Springer, New York, 2005, https://doi.org/10.1007/978-3-662-22199-0. · Zbl 1132.90001 |
| [13] | G. Eichfelder, An adaptive scalarization method in multi-objective optimization, SIAM J. Optim., 19 (2009), pp. 1694-1718, https://doi.org/10.1137/060672029. · Zbl 1187.90252 |
| [14] | J. Fliege, L. G. Drummond, and B. F. Svaiter, Newton’s method for multiobjective optimization, SIAM J. Optim., 20 (2009), pp. 602-626. · Zbl 1195.90078 |
| [15] | P. Gangl, S. Köthe, C. Mellak, A. Cesarano, and A. Mütze, Multi-Objective Free-Form Shape Optimization of a Synchronous Reluctance Machine, preprint, arXiv:2010.10117, 2020. |
| [16] | H. Gottschalk and M. Reese, An analytical study in multi-physics and multi-criteria shape optimization, J. Optim. Theory Appl., 189 (2021), pp. 486-512, https://doi.org/10.1007/s10957-021-01841-y. · Zbl 1466.49036 |
| [17] | H. Gottschalk and M. Saadi, Shape gradients for the failure probability of a mechanic component under cyclic loading: A discrete adjoint approach, Comput. Mech., 64 (2019), pp. 895-915. · Zbl 1466.74040 |
| [18] | J. Guddat, Parametric optimization: Pivoting and predictor-corrector continuation, a survey, in Parametric Optimization and Related Topics, J. Guddat, H. Jongen, B. Kummer, and F. Nožička, eds., Akademie-Verlag, Berlin, 1987, pp. 125-162. · Zbl 0624.90095 |
| [19] | E. Hairer, S. P. Nørsett, and G. Wanner, Solving Ordinary Differential Equations. I. Nonstiff problems, 2nd ed., Springer Ser. Comput. Math. 8, Springer, New York, · Zbl 0789.65048 |
| [20] | C. Hillermeier, Nonlinear Multiobjective Optimization, Birkhäuser, Basel, 2001, https://doi.org/10.1007/978-3-0348-8280-4. · Zbl 0966.90069 |
| [21] | J. Jahn, Multiobjective search algorithm with subdivision technique, Comput. Optim. Appl., 35 (2006), pp. 161-175, https://doi.org/10.1007/s10589-006-6450-4. · Zbl 1153.90533 |
| [22] | R. Marler and J. Arora, The weighted sum method for multi-objective optimization: New insights, Struct. Multidisc. Optim., 41 (2010), pp. 853-862, https://doi.org/10.1007/s00158-009-0460-7. · Zbl 1274.90359 |
| [23] | A. Martín and O. Schütze, Pareto tracer: A predictor-corrector method for multi-objective optimization problems, Eng. Optim., 50 (2018), pp. 516-536, https://doi.org/10.1080/0305215x.2017.1327579. |
| [24] | B. Martin, A. Goldsztejn, L. Granvilliers, and C. Jermann, On continuation methods for non-linear bi-objective optimization: Towards a certified interval-based approach, J. Global Optim., 64 (2016), pp. 3-16. · Zbl 1332.90251 |
| [25] | A. Messac, A. Ismail-Yahaya, and C. Mattson, The normalized normal constraint method for generating the Pareto frontier, Struct. Multidiscip. Optim., 25 (2003), pp. 86-98. · Zbl 1243.90200 |
| [26] | K. Miettinen, Nonlinear Multiobjective Optimization, Springer, 1998, New York, https://doi.org/10.1007/978-1-4615-5563-6. · Zbl 0949.90082 |
| [27] | e D. Munz and T. Fett, Ceramics-Mechanical Properties, Failure Behaviour, Materials Selection, Springer, New York, 2001. |
| [28] | S. Peitz, Exploiting Structure in Multiobjctive Optimization and Optimal Control, Ph.D. thesis, Universität Paderborn, 2017. |
| [29] | S. Peitz and M. Dellnitz, A survey of recent trends in multiobjective optimal control-Surrogate models, feedback control and objective reduction, Math. Comput. Appl., 23 (2018), https://doi.org/10.3390/mca23020030. |
| [30] | L. Piegl and W. Tiller, The NURBS Book. Monographs in Visual Communication, Springer, New York, 2000. · Zbl 0828.68118 |
| [31] | A. Potschka, F. Logist, J. V. Impe, and H. Bock, Tracing the Pareto frontier in bi-objective optimization problems by ODE techniques, Numer. Algorithms, 57 (2011), pp. 217-233. · Zbl 1217.65110 |
| [32] | M. Ringkamp, S. Ober-Blöbaum, M. Dellnitz, and O. Schütze, Handling high-dimensional problems with multi-objective continuation methods via successive approximation of the tangent space, Eng. Optim., 44 (2012), pp. 1117-1146, https://doi.org/10.1080/0305215X.2011.634407. |
| [33] | C. Runge, Ueber die numerische Auflösung von Differentialgleichungen, Math. Ann., 46 (1895), pp. 167-178, https://doi.org/10.1007/BF01446807. · JFM 26.0341.01 |
| [34] | S. Ruzika and M. Wiecek, Approximation methods in multiobjective programming, J. Optim. Theory Appl., 126 (2005), pp. 473-501, https://doi.org/10.1007/s10957-005-5494-4. · Zbl 1093.90057 |
| [35] | S. Schmidt and V. Schulz, Pareto-curve continuation in multi-objective optimization, Pacific J. Optim., 4 (2008), pp. 243-257. · Zbl 1163.90742 |
| [36] | O. Schütze, A. Dell’Aere, and M. Dellnitz, On continuation methods for the numerical treatment of multi-objective optimization problems, in Practical Approaches to Multi-Objective Optimization, J. Branke, K. Deb, K. Miettinen, and R. E. Steuer, eds., no. 04461 in Dagstuhl Seminar Proceedings, Dagstuhl, Germany, 2005, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, http://drops.dagstuhl.de/opus/volltexte/2005/349. |
| [37] | O. Schütze, K. Witting, S. Ober-Blöbaum, and M. Dellnitz, Set oriented methods for the numerical treatment of multiobjective optimization problems, in EVOLVE-A Bridge between Probability, Set Oriented Numerics and Evolutionary Computation, E. Tantar, A.-A. Tantar, P. Bouvry, P. Del Moral, P. Legrand, C. Coello Coello, and O. Schütze, eds., Stud. Comput. Intell. 447, 2013, Springer, New York, https://doi.org/10.1007/978-3-642-32726-1_5. · Zbl 1251.90356 |
| [38] | J. Shackelford and W. Alexander, eds., CRC Materials Science and Engineering Handbook, 4th ed., CRC Press, Boca Raton, FL, 2015. |
| [39] | C. Toure, A. Auger, D. Brockhoff, and N. Hansen, On bi-objective convex-quadratic problems, in Evolutionary Multi-Criterion Optimization, K. Deb, E. Goodman, C. A. Coello Coello, K. Klamroth, K. Miettinen, S. Mostaghim, and P. Reed, eds., Springer, New York, pp. 3-14, 2019, https://doi.org/10.1007/978-3-030-12598-1_1. |
| [40] | E. Zitzler, K. Deb, and L. Thiele, Comparison of multiobjective evolutionary algorithms: Empirical results, Evol. Comput., 8 (2000), pp. 173-195, https://doi.org/10.1162/106365600568202. |
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.
