Library

Description: A commercial aircraft cannot freely use the available airspace but instead has to stick to a three-dimensional network of segments similar to a car in a road network. In this network it faces several variable and interdependent costs in the form of travel time, fuel consumption and overflight charges. These are also highly dependent on other factors such as weather conditions, aircraft performance, take-off time and weight as well as the changing availability of elements in the graph. This is further complicated by the distinction of separate flight phases that challenge the standard notion of a graph with predetermined nodes and arcs. Therefore when trying to find either a distance, fuel, time or cost minimal trajectory for a specific aircraft between an origin and a destination airport, one faces a very complex shortest path problem in the airway network graph that even for strong implifications is often NP-hard. This thesis will focus on exploring the costs that occur in this graph and that are associated with the aircraft performance. Here we will rely on actual performance and weather data supplied by Lufthansa Systems AG in Frankfurt and analyze whether they meet the requirements necessary for common algorithms such as the First-in, First-out property. Since it is vital for any shortest path algorithm to have a fast and accurate way of determining the costs in the graph, we will face two problems regarding the calculation of aircraft performance during cruise as well as the calculation of the so-called air distance. So far these problems have been approached by the industry with rudimentary approximative methods. We will reformulate them as initial value problems and try to find good approximations using both general Runge-Kutta methods as well as a novel approach which relies on finding piecewise linear approximations of some primitive integrals in pre-processing. Computations will show that these approaches deliver fast and accurate results.

Description: This paper studies the empirical efficacy and benefits of using projection-free first-order methods in the form of Conditional Gradients, a.k.a. Frank-Wolfe methods, for training Neural Networks with constrained parameters. We draw comparisons both to current state-of-the-art stochastic Gradient Descent methods as well as across different variants of stochastic Conditional Gradients. In particular, we show the general feasibility of training Neural Networks whose parameters are constrained by a convex feasible region using Frank-Wolfe algorithms and compare different stochastic variants. We then show that, by choosing an appropriate region, one can achieve performance exceeding that of unconstrained stochastic Gradient Descent and matching state-of-the-art results relying on L2-regularization. Lastly, we also demonstrate that, besides impacting performance, the particular choice of constraints can have a drastic impact on the learned representations.

Description: The complexity in large-scale optimization can lie in both handling the objective function and handling the constraint set. In this respect, stochastic Frank-Wolfe algorithms occupy a unique position as they alleviate both computational burdens, by querying only approximate first-order information from the objective and by maintaining feasibility of the iterates without using projections. In this paper, we improve the quality of their first-order information by blending in adaptive gradients. We derive convergence rates and demonstrate the computational advantage of our method over the state-of-the-art stochastic Frank-Wolfe algorithms on both convex and nonconvex objectives. The experiments further show that our method can improve the performance of adaptive gradient algorithms for constrained optimization.

Description: We study two related problems concerning the number of monochromatic cliques in two-colorings of the complete graph that go back to questions of Erdős. Most notably, we improve the 25-year-old upper bounds of Thomason on the Ramsey multiplicity of K4 and K5 and we settle the minimum number of independent sets of size 4 in graphs with clique number at most 4. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic K4 or K5 in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a finite graph and were found through search heuristics. They are complemented by lower bounds and stability results established using Flag Algebras, resulting in a fully computer-assisted approach. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs.

Description: The Hales-Jewett Theorem states that any r-colouring of [m]ⁿ contains a monochromatic combinatorial line if n is large enough. Shelah's proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial line whose set of active coordinates is the union of at most r intervals. For odd r, Conlon and Kamčev constructed r–colourings for which it cannot be fewer than r intervals. However, we show that for even r and large n, any r–colouring of [3]ⁿ contains a monochromatic combinatorial line whose set of active coordinates is the union of at most r−1 intervals. This is optimal and extends a result of Leader and Räty for r=2.

Description: We present a fully computer-assisted proof system for solving a particular family of problems in Extremal Combinatorics. Existing techniques using Flag Algebras have proven powerful in the past, but have so far lacked a computational counterpart to derive matching constructive bounds. We demonstrate that common search heuristics are capable of finding constructions far beyond the reach of human intuition. Additionally, the most obvious downside of such heuristics, namely a missing guarantee of global optimality, can often be fully eliminated in this case through lower bounds and stability results coming from the Flag Algebra approach. To illustrate the potential of this approach, we study two related and well-known problems in Extremal Graph Theory that go back to questions of Erdős from the 60s. Most notably, we present the first major improvement in the upper bound of the Ramsey multiplicity of the complete graph on 4 vertices in 25 years, precisely determine the first off-diagonal Ramsey multiplicity number, and settle the minimum number of independent sets of size four in graphs with clique number strictly less than five.