Proximity measures based on KKT points for constrained multi-objective optimization
- PDF / 3,147,054 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 65 Downloads / 146 Views
Proximity measures based on KKT points for constrained multi-objective optimization Gabriele Eichfelder1
· Leo Warnow1
Received: 16 December 2019 / Accepted: 14 November 2020 © The Author(s) 2020
Abstract An important aspect of optimization algorithms, for instance evolutionary algorithms, are termination criteria that measure the proximity of the found solution to the optimal solution set. A frequently used approach is the numerical verification of necessary optimality conditions such as the Karush–Kuhn–Tucker (KKT) conditions. In this paper, we present a proximity measure which characterizes the violation of the KKT conditions. It can be computed easily and is continuous in every efficient solution. Hence, it can be used as an indicator for the proximity of a certain point to the set of efficient (Edgeworth-Pareto-minimal) solutions and is well suited for algorithmic use due to its continuity properties. This is especially useful within evolutionary algorithms for candidate selection and termination, which we also illustrate numerically for some test problems. Keywords Multiobjective optimization · KKT approximation · Proximity measure Mathematics Subject Classification 90C26 · 90C29 · 90C46 · 90C59
1 Introduction In applications, one often has to deal with not only one but multiple objectives at the same time. This leads to multi-objective optimization problems. Then it is the aim to find globally optimal solutions, called efficient solutions, for such optimization problems using optimization algorithms, e.g., evolutionary algorithms as proposed in [6]. Especially evolutionary algorithms are often considered to be able to overcome regions with only locally efficient solutions and to generate points close to the global Pareto front, i.e., close to the image set of all globally efficient solutions. An important aspect in such algorithms is then the question when the algorithm can finally be stopped as one is sufficiently close to the Pareto front. For that decision, for instance in [7] and [10], proximity measures
B
Leo Warnow [email protected] Gabriele Eichfelder [email protected]
1
Technische Universität Ilmenau, Po 10 05 65, 98684 Ilmenau, Germany
123
Journal of Global Optimization
for termination have been examined by Deb, Dutta and co-authors. We follow this line of research for multi-objective problems, and we do this without the detour of scalarization. A necessary condition for being efficient is to satisfy necessary optimality conditions, at least under certain constraint qualifications. This can also be used, based on the results of this paper, to evaluate the proximity of the generated points to the Pareto front: a necessary condition for being close to the Pareto front is that certain necessary optimality conditions are satisfied at least approximately. In this paper we present two proximity measures which characterize the approximate fulfillment of the so-called Karush–Kuhn–Tucker (KKT) conditions. They can be used for candidate selection and, what is more, as a term
Data Loading...
