EURO Doctoral Dissertation Award 2024 - Finalists

The five finalists of the 2024 EURO Doctoral Dissertation Award are:

Spyridon Pougkakiotis, University of Edinburgh

Regularized Interior Point Methods for Convex Programming

Large-scale convex optimization is integral to several application domains, given its amenability to efficient solution methods and its versatile modeling capabilities. Interior Point Methods (IPMs) represent a widely adopted class of optimization techniques for solving convex problems due to their ability to yield accurate solutions with a polynomial complexity guarantee. However, challenges such as numerical inaccuracy and ill-posedness of the underlying optimization problem can impede their performance.

To address these challenges, researchers have explored regularized versions of IPMs, which exhibit improved robustness in practical scenarios. Despite the practical success of regularized IPMs, a comprehensive theoretical understanding has been lacking until recently.

In this talk, we present an infeasible IPM combined with the Proximal Method of Multipliers (PMM). The resulting algorithm (IP-PMM) is interpreted as a primal-dual regularized IPM, suitable for solving convex programming problems. We apply few iterations of the interior point method to each sub-problem of the proximal method of multipliers. Once a satisfactory solution of the PMM sub-problem is found, we update the PMM parameters, form a new IPM neighbourhood, and repeat this process.

Crucially, we demonstrate the polynomial complexity of the algorithm for a broad class of convex problems under standard assumptions, marking a significant advancement as the first polynomial complexity result for a primal-dual regularized IPM. By inheriting the polynomial complexity of IPMs and the numerical stability of PMMs, IP-PMM offers a promising solution.

To enhance the applicability of our approach, we discuss general-purpose preconditioning strategies for efficiently solving the associated linear systems within IP-PMM. Subsequently, we present numerical results spanning a diverse range of convex programming problems, showcasing the benefits of regularization in IPMs and affirming the reliability and efficiency of the proposed IP-PMM algorithm.

Shared mobility systems like car sharing and bike sharing have become an attractive and wide-spread type of urban mobility over the past decades. The biggest challenge regarding the profitable operation of such systems is the occurring dynamic imbalance between supply and demand, which stems from fluctuating demand patterns and spatially unbalanced vehicle movements. To counter these imbalances, the scientific literature so far has focused on the supply-sided control approach by means of active vehicle relocation. In this dissertation, demand management is proposed as a cost-efficient alternative, in which the system’s demand side is influenced through pricing and availability control. On the one hand, specific practice-relevant problems are addressed and solved. On the other hand, general modeling and solution approaches are developed, which can be transferred to related optimization problems for tactical and operational control of shared mobility systems. Extensive numerical studies, including case studies of Europe’s largest car sharing company Share Now, demonstrate that demand management can be implemented successfully in shared mobility systems.

Contrary to classic classification and regression trees, built in a greedy heuristic manner, designing the tree model through an optimization problem allows us to easily include desirable properties in Machine Learning in addition to prediction accuracy. We present a Non-Linear Optimization approach that is scalable with respect to the size of the training sample, and illustrate this flexibility to model several important issues in Explainable and Fair Machine Learning. These include sparsity, as a proxy for interpretability, by reducing the amount of information necessary to predict well; fairness, by aiming to avoid predictions that discriminate against sensitive features such as gender or race; the cost-sensitivity for groups of individuals in which prediction errors are more critical, such as patients of a disease, by ensuring an acceptable accuracy performance for them; local explainability, where the goal is to identify the predictor variables that have the largest impact on the individual predictions; as well as data complexity in the form of observations of functional nature. The performance of our approach is illustrated on real and synthetic data sets.

Air travel disruptions due to Covid recovery, strikes, and military presence highlight the need for efficient airspace management. The dissertation presents demand-capacity balancing mechanisms aimed at improving European air traffic management (ATM) performance. The first paper introduces dynamically priced flexible trajectory products to manage demand, based on an optimizing routing under capacity constraints. The second paper proposes a simulation-optimization approach for cross-border capacity planning, showing potential for significant delay reductions. Finally, the third paper analyzes measures to reduce aviation emissions through capacity planning and pricing initiatives. Impacting both research and practice, the findings offer innovative solutions for managing demand-capacity imbalances post-Covid, potentially reshaping European airspace management.

Over the last century, mathematical optimization has become a prominent tool for decision making. Its systematic application in practical fields such as economics, logistics or defense led to the development of algorithmic methods with ever increasing efficiency. Indeed, for a variety of real-world problems, finding an optimal decision among a set of (implicitly or explicitly) predefined alternatives has become conceivable in reasonable time. In the last decades, however, the research community raised more and more attention to the role of uncertainty in the optimization process. In particular, one may question the notion of optimality, and even feasibility, when studying decision problems with unknown or imprecise input parameters.

In this talk, we study a class of optimization problems which suffer from imprecise input data and feature a two-stage decision process, i.e., where decisions are made in a sequential order and where unknown parameters are revealed throughout the stages. The applications of such problems are plethora in practical fields such as, e.g., facility location problems with uncertain demands, transportation problems with uncertain costs or scheduling under uncertain processing times. The uncertainty is dealt with a robust optimization (RO) viewpoint (also known as "worst-case perspective") and we present original contributions to the RO literature on both the theoretical and practical side.