Publikationen am Institut für Mathematik

Anzahl der Treffer: 2072
Erstellt: Wed, 27 Mar 2024 23:21:46 +0100 in 0.0858 sec


Eichfelder, Gabriele; Stein, Oliver; Warnow, Leo
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
Wolffram, Daniel; Abbott, Sam; An der Heiden, Matthias; Funk, Sebastian; Günther, Felix; Hailer, Davide; Heyder, Stefan; Hotz, Thomas; van de Kassteele, Jan; Küchenhoff, Helmut; Müller-Hansen, Sören; Syliqi, Diell̈e; Ullrich, Alexander; Weigert, Maximilian; Schienle, Melanie; Bracher, Johannes
Collaborative nowcasting of COVID-19 hospitalization incidences in Germany. - In: PLoS Computational Biology, ISSN 1553-7358, Bd. 19 (2023), 8, e1011394, S. 1-25

Real-time surveillance is a crucial element in the response to infectious disease outbreaks. However, the interpretation of incidence data is often hampered by delays occurring at various stages of data gathering and reporting. As a result, recent values are biased downward, which obscures current trends. Statistical nowcasting techniques can be employed to correct these biases, allowing for accurate characterization of recent developments and thus enhancing situational awareness. In this paper, we present a preregistered real-time assessment of eight nowcasting approaches, applied by independent research teams to German 7-day hospitalization incidences during the COVID-19 pandemic. This indicator played an important role in the management of the outbreak in Germany and was linked to levels of non-pharmaceutical interventions via certain thresholds. Due to its definition, in which hospitalization counts are aggregated by the date of case report rather than admission, German hospitalization incidences are particularly affected by delays and can take several weeks or months to fully stabilize. For this study, all methods were applied from 22 November 2021 to 29 April 2022, with probabilistic nowcasts produced each day for the current and 28 preceding days. Nowcasts at the national, state, and age-group levels were collected in the form of quantiles in a public repository and displayed in a dashboard. Moreover, a mean and a median ensemble nowcast were generated. We find that overall, the compared methods were able to remove a large part of the biases introduced by delays. Most participating teams underestimated the importance of very long delays, though, resulting in nowcasts with a slight downward bias. The accompanying prediction intervals were also too narrow for almost all methods. Averaged over all nowcast horizons, the best performance was achieved by a model using case incidences as a covariate and taking into account longer delays than the other approaches. For the most recent days, which are often considered the most relevant in practice, a mean ensemble of the submitted nowcasts performed best. We conclude by providing some lessons learned on the definition of nowcasting targets and practical challenges.



https://doi.org/10.1371/journal.pcbi.1011394
Bang-Jensen, Jørgen; Hörsch, Florian; Kriesell, Matthias
Complexity of (arc)-connectivity problems involving arc-reversals or deorientations. - In: Theoretical computer science, Bd. 973 (2023), 114097

By a well known theorem of Robbins, a graph G has a strongly connected orientation if and only if G is 2-edge-connected and it is easy to find, in linear time, either a cut edge of G or a strong orientation of G. A result of Durand de Gevigney shows that for every it is NP-hard to decide if a given graph G has a k-strong orientation. Thomassen showed that one can check in polynomial time whether a given graph has a 2-strong orientation. This implies that for a given digraph D we can determine in polynomial time whether we can reorient (=reverse) some arcs of to obtain a 2-strong digraph. This naturally leads to the question of determining the minimum number of such arcs to reverse before the resulting graph is 2-strong. In this paper we show that finding this number is NP-hard. If a 2-connected graph G has no 2-strong orientation, we may ask how many of its edges we may orient so that the resulting mixed graph is still 2-strong. Similarly, we may ask for a 2-edge-connected graph G how many of its edges we can orient such that the resulting mixed graph remains 2-arc-strong. We prove that when restricted to graphs satisfying suitable connectivity conditions, both of these problems are equivalent to finding the minimum number of edges we must double in a 2-edge-connected graph in order to obtain a 4-edge-connected graph. Using this, we show that all these three problems are NP-hard. Finally, we consider the operation of deorienting an arc uv of a digraph D meaning replacing it by an undirected edge between the same vertices. In terms of connectivity properties, this is equivalent to adding the opposite arc vu to D. We prove that for every it is NP-hard to find the minimum number of arcs to deorient in a digraph D in order to obtain an ℓ-strong digraph.



https://doi.org/10.1016/j.tcs.2023.114097
Behrndt, Jussi; Schmitz, Philipp; Teschl, Gerald; Trunk, Carsten
Perturbation and spectral theory for singular indefinite Sturm-Liouville operators. - Ilmenau : Technische Universität Ilmenau, Institut für Mathematik, 2023. - 1 Online-Ressource (26 Seiten). - (Preprint ; M23,08)

We study singular Sturm-Liouville operators of the form 1/r_j (-d/dx p_j d/dx +q_j), j=0,1, in L_2((a; b); rj ), where, in contrast to the usual assumptions, the weight functions r_j have different signs near the singular endpoints a and b. In this situation the associated maximal operators become self-adjoint with respect to indefnite inner products and their spectral properties differ essentially from the Hilbert space situation. We investigate the essential spectra and accumulation properties of nonreal and real discrete eigenvalues; we emphasize that here also perturbations of the indefinite weights r_j are allowed. Special attention is paid to Kneser type results in the indefinite setting and to L_1 perturbations of periodic operators.



https://nbn-resolving.org/urn:nbn:de:gbv:ilm1-2023200208
Honecker, Maria Christine; Gernandt, Hannes; Wulff, Kai; Trunk, Carsten; Reger, Johann
Feedback rectifiable pairs and stabilization of switched linear systems. - Ilmenau : Technische Universität Ilmenau, Institut für Mathematik, 2023. - 1 Online-Ressource (12 Seiten). - (Preprint ; M23,07)

We address the feedback design problem for switched linear systems. In particular we aim to design a switched state-feedback such that the resulting closed-loop switched system is in upper triangular form. To this effect we formulate and analyse the feedback rectification problem for pairs of matrices. We present necessary and sufficient conditions for the feedback rectifiability of pairs for two subsystems and give a constructive procedure to design stabilizing state-feedback for a class of switched systems. Several examples illustrate the characteristics of the problem considered and the application of the proposed constructive procedure.



https://nbn-resolving.org/urn:nbn:de:gbv:ilm1-2023200194
Eichfelder, Gabriele; Warnow, Leo
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
Eichfelder, Gabriele; Gerlach, Tobias; Warnow, Leo
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
Assanova, Anar; Trunk, Carsten; Uteshova, Roza
On the solvability of boundary value problems for linear differential-algebraic equations with constant coefficients. - Ilmenau : Technische Universität Ilmenau, Institut für Mathematik, 2023. - 1 Online-Ressource (7 Seiten). - (Preprint ; M23,06)

We study a two-point boundary value problem for a linear differential-algebraic equation with constant coefficients by using the method of parameterization. The parameter is set as the value of the continuously differentiable component of the solution at the left endpoint of the interval. Applying the Weierstrass canonical form to the matrix pair associated with the differential-algebraic equation, we obtain a criterion for the unique solvability of the problem.



https://nbn-resolving.org/urn:nbn:de:gbv:ilm1-2023200182
Faulwasser, Timm; Ou, Ruchuan; Pan, Guanru; Schmitz, Philipp; Worthmann, Karl
Behavioral theory for stochastic systems? A data-driven journey from Willems to Wiener and back again. - In: Annual reviews in control, ISSN 1872-9088, Bd. 55 (2023), S. 92-117

The fundamental lemma by Jan C. Willems and co-workers is deeply rooted in behavioral systems theory and it has become one of the supporting pillars of the recent progress on data-driven control and system analysis. This tutorial-style paper combines recent insights into stochastic and descriptor-system formulations of the lemma to further extend and broaden the formal basis for behavioral theory of stochastic linear systems. We show that series expansions - in particular Polynomial Chaos Expansions (PCE) of L2-random variables, which date back to Norbert Wiener’s seminal work - enable equivalent behavioral characterizations of linear stochastic systems. Specifically, we prove that under mild assumptions the behavior of the dynamics of the L2-random variables is equivalent to the behavior of the dynamics of the series expansion coefficients and that it entails the behavior composed of sampled realization trajectories. We also illustrate the short-comings of the behavior associated to the time-evolution of the statistical moments. The paper culminates in the formulation of the stochastic fundamental lemma for linear time-invariant systems, which in turn enables numerically tractable formulations of data-driven stochastic optimal control combining Hankel matrices in realization data (i.e. in measurements) with PCE concepts.



https://doi.org/10.1016/j.arcontrol.2023.03.005
Chan, Tsz Lung; Kriesell, Matthias; Schmidt, Jens M.
Contractible edges in longest cycles. - In: Journal of graph theory, ISSN 1097-0118, Bd. 103 (2023), 3, S. 542-563

https://doi.org/10.1002/jgt.22935