A05
Refine
Year of publication
Keywords
Document Type
- Article (49)
- Preprint (43)
- Conference Proceeding (3)
- Part of a Book (1)
- Doctoral Thesis (1)
- Lecture (1)
- Other (1)
- Periodical (1)
We present domain decomposition techniques for efficient and scalable simulation and optimization of partial differential equations on network domains. Motivated by transient gas network applications, the state-of-the-art of space-and-time decompositions for systems derived from Euler's equations are presented. Moreover, combinatorial aspects of switching valves are addressed in a decomposition framework for mixed-integer and ODE-constrained problems and a convergence analysis is presented. Motivated by stochastic approximation, we also propose and explore randomized decomposition approaches. Some of these advanced solution strategies can be combined and regarded as variants of certain penalty alternating direction methods. We present the potential applications of these techniques by summarizing numerical results from the literature for transient GasLib instances modeling a realistic gas transport network.
The 121 real schemes, i.e., ambient isotopy classes, of smooth real plane algebraic curves of degree seven were classified by Viro (1984). By constructing one patchwork of the dilated triangle 7⋅Δ2 for each real scheme, we provide an explicit method for constructing polynomials realizing each real scheme. In particular, every real scheme of degree seven can be realized as a T-curve; this settles a question raised by Itenberg and Viro (1996).
A T-curve of degree d is given by a regular unimodular triangulation of d⋅Δ2 together with a sign distribution on its lattice points. By Viro's Patchworking Theorem, this determines the ambient isotopy type (a.k.a. real scheme) of a smooth real plane projective algebraic curve of the same degree. We present a near-quadratic time algorithm for extracting that isotopy type from the triangulation and the signs. Through a GPU-accelerated implementation, this allows one to compute billions of real schemes per second, enabling exhaustive enumeration at scale. This algorithm was essential for our recent construction of all 121 real schemes of degree seven by T-curves.
Solving mixed-integer nonlinear programs (MINLPs) typically relies on constructing relaxations that are easier to tackle than the original problem. Recently, global parabolic (PARA) relaxations were introduced, featuring separable quadratic functions – paraboloids – as global under- or overestimators of general nonlinear constraint functions. So far, the paraboloids are all computed at once by solving a mixed-integer linear program (MIP). For small tolerances or wide function domains, the corresponding MIP grows in size and is eventually intractable, preventing a meaningful comparison with established relaxation techniques.
We therefore propose a novel iterative method to compute PARA approximations that succeeds on all tolerance-domain combinations where the original one has failed. The computational study is preceded by a thorough theoretical explanation and analysis. Finally, the improved method enables a computational comparison with piecewise linear (PWL) relaxations in terms of runtime on general MINLP instances.
The results show that the modern solver SCIP can solve PWL relaxations faster when the olerance is high, shifting strongly in favor of PARA for tighter tolerances. We attribute the effect to the difference in the corresponding problem size: PWL relaxations introduce binary variables to identify the active linear piece and their number grows with decreasing tolerance. PARA, on
the other hand, does not require additional variables such that the dimension is maintained. For problems with at least one (co)sine constraint, the effect significantly amplifies. Thereby, for medium tolerances, PARA relaxations outperform SCIP stand-alone. Applied problems like alternating current optimal power flow (AC-OPF) feature such constraint types, leaving PARA a viable relaxation strategy.
We present two novel six-colorings of the Euclidean plane that avoid monochromatic pairs of points at unit distance in five colors and monochromatic pairs at another specified distance $d$ in the sixth color. Such colorings have previously been known to exist for $0.41 < \sqrt{2} - 1 \le d \le 1 / \sqrt{5} < 0.45$. Our results significantly expand that range to $0.354 \le d \le 0.657$, the first improvement in 30 years. Notably, the constructions underlying this were derived by formalizing colorings suggested by a custom machine learning approach.
We introduce Neural Parameter Regression (NPR), a novel framework specifically developed for learning solution operators in Partial Differential Equations (PDEs). Tailored for operator learning, this approach surpasses traditional DeepONets (Lu et. al, 2021) by employing Physics-Informed Neural Network (Raissi et. al, 2019) techniques to regress Neural Network (NN) parameters. By parametrizing each solution based on specific initial conditions, it effectively approximates a mapping between function spaces. Our method enhances parameter efficiency by incorporating low-rank matrices, thereby boosting computational efficiency and scalability. The framework shows remarkable adaptability to new initial and boundary conditions, allowing for rapid fine-tuning and inference, even in cases of out-of-distribution examples.
We demonstrate how neural networks can drive mathematical discovery through a case study of the Hadwiger-Nelson problem, a long-standing open problem at the intersection of discrete geometry and extremal combinatorics that is concerned with coloring the plane while avoiding monochromatic unit-distance pairs. Using neural networks as approximators, we reformulate this mixed discrete-continuous geometric coloring problem with hard constraints as an optimization task with a probabilistic, differentiable loss function. This enables gradient based exploration of admissible configurations that most significantly led to the discovery of two novel six-colorings, providing the first improvement in thirty years to the off-diagonal variant of the original problem (Mundinger et al., 2024a). Here, we establish the underlying machine learning approach used to obtain these results and demonstrate its broader applicability through additional numerical insights.
We study linear complementarity problems (LCPs) under uncer-
tainty, which we model using chance constraints. Since the complementarity
condition of the LCP is an equality constraint, it is required to consider relax-
ations, which naturally leads to optimization problems in which the relaxation
parameters are minimized for given probability levels. We focus on these
optimization problems and first study the continuity of the related probability
functions and the compactness of the feasible sets. This leads to existence
results for both types of models: one with a joint chance constraint and one
with separate chance constraints for both uncertainty-affected conditions of
the LCP. For both, we prove the differentiability of all probability functions
and derive respective gradient formulae. For the separate case, we prove con-
vexity of the respective optimization problem and use the gradient formulae
to derive necessary and sufficient optimality conditions. In a small case study
regarding a Cournot oligopoly among energy producers, we finally illustrate
the applicability of our theoretical findings.
We study the complexity of identifying the integer feasibility of reverse convex sets. We present various settings where the complexity can be either NP-Hard or efficiently solvable when the dimension is fixed. Of particular interest is the case of bounded reverse convex constraints with a polyhedral domain. We introduce a structure, Boundary Hyperplane Cover, that permits this problem to be solved in polynomial time in fixed dimension provided the number of nonlinear reverse convex sets is fixed.
We propose an approach based on quadratic approximations for solving general Mixed-Integer Nonlinear Programming (MINLP) problems. Specifically, our approach entails the global approximation of the epigraphs of constraint functions by means of paraboloids, which are polynomials of degree two with univariate quadratic terms, and relies on a Lipschitz property only. These approximations are then integrated into the original problem. To this end, we introduce a novel approach to compute globally valid epigraph approximations by paraboloids via a Mixed-Integer Linear Programming (MIP) model. We emphasize the possibility of performing such approximations a-priori and providing them in form of a lookup table, and then present several ways of leveraging the approximations to tackle the original problem. We provide the necessary theoretical background and conduct computational experiments on instances of the MINLPLib. As a result, this approach significantly accelerates the solution process of MINLP problems, particularly those involving many trigonometric or few exponential functions. In general, we highlight that the proposed technique is able to exploit advances in Mixed-Integer Quadratically-Constrained Programming (MIQCP) to solve MINLP problems.