Notes on the value function approach to multiobjective bilevel optimization. - In: Optimization, ISSN 1029-4945, Bd. 0 (2024), 0, S. 1-37
This paper is concerned with the value function approach to multiobjective bilevel optimization which exploits a lower-level frontier-type mapping in order to replace the hierarchical model of two interdependent multiobjective optimization problems by a single-level multiobjective optimization problem. As a starting point, different value-function-type reformulations are suggested and their relations are discussed. Here, we focus on the situations where the lower-level problem is solved up to efficiency or weak efficiency, and an intermediate solution concept is suggested as well. We study the graph-closedness of the associated efficiency-type and frontier-type mappings. These findings are then used for two purposes. First, we investigate existence results in multiobjective bilevel optimization. Second, for the derivation of necessary optimality conditions via the value function approach, it is inherent to differentiate frontier-type mappings in a generalized way. Here, we are concerned with the computation of upper coderivative estimates for the frontier-type mapping associated with the setting where the lower-level problem is solved up to weak efficiency. We proceed in two ways, relying, on the one hand, on a weak domination property and, on the other hand, on a scalarization approach. Illustrative examples visualize our findings and some flaws in the related literature.
https://doi.org/10.1080/02331934.2024.2323107
Set-based robust optimization of uncertain multiobjective problems via epigraphical reformulations. - In: European journal of operational research, ISSN 0377-2217, Bd. 313 (2024), 3, S. 871-882
In this paper, we study a method for finding robust solutions to multiobjective optimization problems under uncertainty. We follow the set-based minmax approach for handling the uncertainties which leads to a certain set optimization problem with the strict upper type set relation. We introduce, under some assumptions, a reformulation using instead the strict lower type set relation without sacrificing the compactness property of the image sets. This allows to apply vectorization results to characterize the optimal solutions of these set optimization problems as optimal solutions of a multiobjective optimization problem. We end up with multiobjective semi-infinite problems which can then be studied with classical techniques from the literature.
https://www.sciencedirect.com/science/article/pii/S0377221723007208/pdfft?md5=f5272f8643b0ce953294091001149d0f&pid=1-s2.0-S0377221723007208-main.pdf
Limit sets in global multiobjective optimization. - In: Optimization, ISSN 1029-4945, Bd. 73 (2024), 1, S. 1-27
Inspired by the recently introduced branch-and-bound method for continuous multiobjective optimization problems from G. Eichfelder, P. Kirst, L. Meng, O. Stein [A general branch-and-bound framework for continuous global multiobjective optimization. J Glob Optim. 2021;80:195-227], we study for a general class of branch-and-bound methods in which sense the generated terminal enclosure and the terminal provisional nondominated set approximate the nondominated set when the termination accuracy is driven to zero. Our convergence analysis of the enclosures relies on constructions from the above paper, but is self-contained and also covers the mixed-integer case. The analysis for the provisional nondominated set is based on general convergence properties of the epsilon-nondominated set, and hence it is also applicable to other algorithms which generate such points. Furthermore, we discuss post-processing steps for the terminal enclosure and provide numerical illustrations for the cases of two and three objective functions.
https://doi.org/10.1080/02331934.2022.2092479
Solving multi-objective mixed-integer nonlinear optimization problems. - Ilmenau : Universitätsbibliothek, 2023. - 1 Online-Ressource (ii, 186, XXV Seiten)
Technische Universität Ilmenau, Dissertation 2023
Multikriterielle gemischt-ganzzahlige Optimierungsprobleme treten in einer Vielzahl von Anwendungsgebieten auf. Beispiele dafür sind Portfoliomanagement, sowie Ablauf- und Anlagenplanung. Häufig haben diese Optimierungsprobleme eine hohe Anzahl an Variablen und eine relativ geringe Anzahl an Zielfunktionen. In dieser Arbeit werden drei neue, deterministische Ansätze zur Approximation der nichtdominierten Menge solcher Optimierungsprobleme vorgestellt. Zwei der Ansätze arbeiten fast vollständig im Bildbereich. Dies hat den Vorteil, dass ihre Performance nur geringfügig durch die hohe Anzahl an Variablen beeinflusst wird, die häufig in Anwendungsproblemen auftritt. Während es sich bei einem der Ansätze um ein allgemeines Framework handelt, das nicht immer praktisch und algorithmisch realisiert werden kann, ist der andere Ansatz in der Lage, nahezu jedes multikriterielle gemischt-ganzzahlige konvexe Optimierungsproblem theoretisch und auch praktisch zu lösen. Der dritte vorgestellte Ansatz erlaubt darüber hinaus auch die Lösung multikriterieller gemischt-ganzzahliger nichtkonvexer Optimierungsprobleme. Alle drei Ansätze gehören zu den ersten, die multikriterielle gemischt-ganzzahlige Optimierungsprobleme lösen können und Garantien für die Qualität der von ihnen berechneten Approximation geben. Numerische Tests und Auswertungen für alle drei Ansätze werden ebenfalls in dieser Arbeit vorgestellt. Alle drei Ansätze verwenden dasselbe Konzept einer Einhüllung (enclosure) zur Approximation der nichtdominierten Menge. Deren Berechnung kombiniert Techniken der ganzzahligen und der multikriteriellen kontinuierlichen Optimierung. Darüber hinaus nutzt der Ansatz für gemischt-ganzzahlige konvexe Optimierungsprobleme gezielt die gemischt-ganzzahlige Struktur des Optimierungsproblems aus. Es ist der erste Ansatz, der gleichzeitig mit einer gemischt-ganzzahligen linearen Relaxierung und einer Zerlegung in kontinuierliche konvexe Teilprobleme arbeitet.
https://doi.org/10.22032/dbt.58648
A solver for multiobjective mixed-integer convex and nonconvex optimization. - In: Journal of optimization theory and applications, ISSN 1573-2878, Bd. 0 (2023), 0, insges. 31 S.
This paper proposes a general framework for solving multiobjective nonconvex optimization problems, i.e., optimization problems in which multiple objective functions have to be optimized simultaneously. Thereby, the nonconvexity might come from the objective or constraint functions, or from integrality conditions for some of the variables. In particular, multiobjective mixed-integer convex and nonconvex optimization problems are covered and form the motivation of our studies. The presented algorithm is based on a branch-and-bound method in the pre-image space, a technique which was already successfully applied for continuous nonconvex multiobjective optimization. However, extending this method to the mixed-integer setting is not straightforward, in particular with regard to convergence results. More precisely, new branching rules and lower bounding procedures are needed to obtain an algorithm that is practically applicable and convergent for multiobjective mixed-integer optimization problems. Corresponding results are a main contribution of this paper. What is more, for improving the performance of this new branch-and-bound method we enhance it with two types of cuts in the image space which are based on ideas from multiobjective mixed-integer convex optimization. Those combine continuous convex relaxations with adaptive cuts for the convex hull of the mixed-integer image set, derived from supporting hyperplanes to the relaxed sets. Based on the above ingredients, the paper provides a new multiobjective mixed-integer solver for convex problems with a stopping criterion purely in the image space. What is more, for the first time a solver for multiobjective mixed-integer nonconvex optimization is presented. We provide the results of numerical tests for the new algorithm. Where possible, we compare it with existing procedures.
https://doi.org/10.1007/s10957-023-02285-2
A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problems. - In: Mathematical methods of operations research, ISSN 1432-5217, Bd. 0 (2023), 0, insges. 30 S.
In multi-objective mixed-integer convex optimization, multiple convex objective functions need to be optimized simultaneously while some of the variables are restricted to take integer values. In this paper, we present a new algorithm to compute an enclosure of the nondominated set of such optimization problems. More precisely, we decompose the multi-objective mixed-integer convex optimization problem into several multi-objective continuous convex optimization problems, which we refer to as patches. We then dynamically compute and improve coverages of the nondominated sets of those patches to finally combine them to obtain an enclosure of the nondominated set of the multi-objective mixed-integer convex optimization problem. Additionally, we introduce a mechanism to reduce the number of patches that need to be considered in total. Our new algorithm is the first of its kind and guaranteed to return an enclosure of prescribed quality within a finite number of iterations. For selected numerical test instances we compare our new criterion space based approach to other algorithms from the literature and show that much larger instances can be solved with our new algorithm.
https://doi.org/10.1007/s00186-023-00828-x
A test instance generator for multiobjective mixed-integer optimization. - In: Mathematical methods of operations research, ISSN 1432-5217, Bd. 0 (2023), 0, insges. 26 S.
Application problems can often not be solved adequately by numerical algorithms as several difficulties might arise at the same time. When developing and improving algorithms which hopefully allow to handle those difficulties in the future, good test instances are required. These can then be used to detect the strengths and weaknesses of different algorithmic approaches. In this paper we present a generator for test instances to evaluate solvers for multiobjective mixed-integer linear and nonlinear optimization problems. Based on test instances for purely continuous and purely integer problems with known efficient solutions and known nondominated points, suitable multiobjective mixed-integer test instances can be generated. The special structure allows to construct instances scalable in the number of variables and objective functions. Moreover, it allows to control the resulting efficient and nondominated sets as well as the number of efficient integer assignments.
https://doi.org/10.1007/s00186-023-00826-z
Advancements in the computation of enclosures for multi-objective optimization problems. - In: European journal of operational research, ISSN 0377-2217, Bd. 310 (2023), 1, S. 315-327
A central goal for multi-objective optimization problems is to compute their nondominated sets. In most cases these sets consist of infinitely many points and it is not a practical approach to compute them exactly. One solution to overcome this problem is to compute an enclosure, a special kind of coverage, of the nondominated set. For that computation one often makes use of so-called local upper bounds. In this paper we present a generalization of this concept. For the first time, this allows to apply a warm start strategy to the computation of an enclosure. We also show how this generalized concept allows to remove empty areas of an enclosure by deleting certain parts of the lower and upper bound sets which has not been possible in the past. We demonstrate how to apply our ideas to the box approximation algorithm, a general framework to compute an enclosure, as recently used in the solver called BAMOP. We show how that framework can be simplified and improved significantly, especially concerning its practical numerical use. In fact, we show for selected numerical instances that our new approach is up to eight times faster than the original one. Hence, our new framework is not only of theoretical but also of practical use, for instance for continuous convex or mixed-integer quadratic optimization problems.
https://doi.org/10.1016/j.ejor.2023.02.032
Convexity and continuity of specific set-valued maps and their extremal value functions. - In: Journal of applied and numerical optimization, ISSN 2562-5535, Bd. 5 (2023), 1, S. 71-92
In this paper, we study several classes of set-valued maps, which can be used in set-valued optimization and its applications, and their respective maximum and minimum value functions. The definitions of these maps are based on scalar-valued, vector-valued, and cone-valued maps. Moreover, we consider those extremal value functions which are obtained when optimizing linear functionals over the image sets of the set-valued maps. Such extremal value functions play an important role for instance for derivative concepts for set-valued maps or for algorithmic approaches in set-valued optimization. We formulate conditions under which the set-valued maps and their extremal value functions inherit properties like (Lipschitz-)continuity and convexity.
https://doi.org/10.23952/jano.5.2023.1.05
Relaxed dissipativity assumptions and a simplified algorithm for multiobjective MPC. - In: Computational optimization and applications, ISSN 1573-2894, Bd. 86 (2023), 3, S. 1081-1116
We consider nonlinear model predictive control (MPC) with multiple competing cost functions. In each step of the scheme, a multiobjective optimal control problem with a nonlinear system and terminal conditions is solved. We propose an algorithm and give performance guarantees for the resulting MPC closed loop system. Thereby, we significantly simplify the assumptions made in the literature so far by assuming strict dissipativity and the existence of a compatible terminal cost for one of the competing objective functions only. We give conditions which ensure asymptotic stability of the closed loop and, what is more, obtain performance estimates for all cost criteria. Numerical simulations on various instances illustrate our findings. The proposed algorithm requires the selection of an efficient solution in each iteration, thus we examine several selection rules and their impact on the results. and we also examine numerically how different selection rules impact the results
https://doi.org/10.1007/s10589-022-00398-4