Approximation properties of Sum-Up Rounding

Manns, Paul

doi:10.24355/dbbs.084-202001071053-0

Published

Approximation properties of Sum-Up Rounding

English
German

Optimization problems that involve discrete variables are exposed to the conflict between being a powerful modeling tool and often being hard to solve. Infinite-dimensional processes, as e.g. described by differential equations, underlying the optimization may lead to the need to solve for distributed discrete control variables.

This work analyzes approximation arguments that replace the need for solving the optimization problem by the need for first solving a relaxation and second computing appropriate roundings to regain discrete controls. We provide sufficient conditions on rounding algorithms and their grid refinement strategies that allow to prove approximation of the relaxed controls by the discrete controls in weaker topologies, a feature due to the infinite-dimensional vantage point. If the control-to-state mapping of the underlying process exhibits suitable compactness properties, state vector approximation follows in the norm topology as well as, under additional assumptions, optimality principles of the computed discrete controls. The conditions are verified for representatives of the family of Sum-Up Rounding algorithms.

We apply the arguments on different classes of mixed-integer optimization problems that are constrained by partial differential equations. Specifically, we consider discrete control inputs, which are distributed in the time domain, for evolution equations that are governed by a differential operator that generates a strongly continuous semigroup, discrete control inputs, which are distributed in multi-dimensional spatial domains, for elliptic boundary value problems and discrete control inputs, which are distributed in space-time cylinders, for evolution equations that are governed by differential operators such that the corresponding Cauchy problem satisfies maximal parabolic regularity. Furthermore, we apply the arguments outside the scope of partial differential equations to a signal reconstruction problem. Computational results illustrate the findings.

Optimierungsprobleme mit diskreten Variablen befinden sich im Spannungsfeld zwischen hoher Modellierungsmächtigkeit und oft schwerer Lösbarkeit. Zur Optimierung unendlichdimensionaler Prozesse, z.B. beschrieben mit Hilfe von Differentialgleichungen, kann die Lösung nach verteilten diskreten Kontrollvariablen erforderlich sein.

Diese Arbeit untersucht Approximationsargumente, mit deren Hilfe die Notwendigkeit einer Lösung des Optimierungsproblems durch die Notwendigkeit zuerst eine Relaxierung zu lösen und anschließend eine passende Rundung zu berechnen, um wieder diskrete Kontrollvariablen zu erhalten, ersetzt wird. Wir geben hinreichende Bedingungen an Rundungsalgorithmen und ihre Gitterverfeinerungsstrategien an, um eine Approximation der relaxierten Kontrollvariablen mit den diskreten Kontrollvariablen in schwächeren Topologien zu erhalten, was aus der unendlichdimensionalen Betrachtung des Problems folgt. Falls der Steuerungs-Zustands-Operator des zugrundeliegenden Prozesses passende Kompaktheitseigenschaften aufweist, folgen die Approximation der Zustandsvektoren in der Normtopologie und, unter zusätzlichen Bedingungen, Optimalitätsprinzipien für die berechneten diskreten Kontrollvariablen. Die Bedingungen werden für Repräsentanten der Familie von Sum-Up Rounding Algorithmen nachgewiesen.

Wir wenden die Argumente auf verschiedene Klassen von gemischt-ganzzahligen Optimierungsproblemen, die von partiellen Differentialgleichungen beschränkt werden, an. Insbesondere betrachten wir diskrete, in der Zeit verteilte, Steuerungen in Evolutionsgleichungen mit Differentialoperatoren, die stark stetige Halbgruppen erzeugen; diskrete, mehrdimensional im Ort verteilte, Steuerungen in elliptischen Randwertproblemen und diskrete, in Ort und Zeit verteilte, Steuerungen in Evolutionsgleichungen mit Differentialoperatoren, deren zugehörige Cauchyprobleme maximale parabolische Regularität aufweisen. Des Weiteren wenden wir die Argumente außerhalb des Kontexts partieller Differentialgleichungen auf ein Signalrekonstruktionsproblem an. Numerische Beispiele illustrieren die gezeigten Resultate.