Mgr. Jakub Mareček, Ph.D.

In many applications, solutions of convex optimization problems are updated on-line, as functions of time. In this paper, we consider parametric semidefinite programs, which are linear optimization problems in the semidefinite cone whose coefficients (input data) depend on a time parameter. We are interested in the geometry of the solution (output data) trajectory, defined as the set of solutions depending on the parameter. We propose an exhaustive description of the geometry of the solution trajectory. As our main result, we show that only six distinct behaviors can be observed at a neighborhood of a given point along the solution trajectory. Each possible behavior is then illustrated by an example.

Designing lightweight yet stiff structures that can withstand vibrations is a crucial task in structural optimization. Here, we present a novel framework for truss topology optimization under undamped harmonic oscillations. Our approach minimizes the peak power of the structure under harmonic loads, overcoming the limitations of single- frequency and in-phase assumptions found in previous methods. For this, we leverage the concept of semidefinite representable (SDr) functions, demonstrating that while compliance readily conforms to an SDr representation, peak power requires a derivation based on the non-negativity of trigonometric functions. Finally, we introduce convex relaxations for the minimization problem and provide promising computational results.

The ranking of nodes in a network according to their centrality or ``importance'' is a classic problem that has attracted the interest of different scientific communities in the last decades. The COVID-19 pandemic has recently rejuvenated the interest in this problem, as the ranking may be used to decide who should be tested, or vaccinated, first, in a population of asymptomatic individuals. In this paper, we review classic methods for node ranking and compare their performance in a benchmark network that considers the community-based structure of society. The outcome of the ranking procedure is then used to decide which individuals should be tested, and possibly quarantined, first. Finally, we also review the extension of these ranking methods to weighted graphs and explore the importance of weights in a contact network by providing a toy model and comparing node rankings for this case in the context of disease spread.

Quantum computers have demonstrable ability to solve problems at a scale beyond brute-force classical simulation. Interest in quantum algorithms has developed in many areas, particularly in relation to mathematical optimization - a broad field with links to computer science and physics. In this Review, we aim to give an overview of quantum optimization. Provably exact, provably approximate and heuristic settings are first explained using computational complexity theory, and we highlight where quantum advantage is possible in each context. Then, we outline the core building blocks for quantum optimization algorithms, define prominent problem classes and identify key open questions that should be addressed to advance the field. We underscore the importance of benchmarking by proposing clear metrics alongside suitable optimization problems, for appropriate comparisons with classical optimization techniques, and discuss next steps to accelerate progress towards quantum advantage in optimization. This Review discusses quantum optimization, focusing on the potential of exact, approximate and heuristic methods, core algorithmic building blocks, problem classes and benchmarking metrics. The challenges for quantum optimization are considered, and next steps are suggested for progress towards achieving quantum advantage. Quantum computing is advancing rapidly, and quantum optimization is a promising area of application. Quantum optimization algorithms - whether provably exact, provably approximate or heuristic - offer opportunities to demonstrate quantum advantage. Systematic benchmarking is crucial to guide research, track progress and further advance understanding of quantum optimization. Theoretical research and empirical research using real hardware can complement each other, in the move towards demonstrating quantum advantage.

There has been much recent interest in the regulation of AI. We argue for a view based on civil-rights legislation, built on the notions of equal treatment and equal impact. In a closed-loop view of the AI system and its users, the equal treatment concerns one pass through the loop. Equal impact, in our view, concerns the long-run average behaviour across repeated interactions. In order to establish the existence of the average and its properties, one needs to study the ergodic properties of the closed-loop and, in particular, its unique stationary measure.

In this paper we examine algorithmic fairness from the perspective of law aiming to identify best practices and strategies for the specification and adoption of fairness definitions and algorithms in real-world systems and use cases. We start by providing a brief introduction of current anti-discrimination law in the European Union and the United States and discussing the concepts of bias and fairness from an legal and ethical viewpoint. We then proceed by presenting a set of algorithmic fairness definitions by example, aiming to communicate their objectives to non-technical audiences. Then, we introduce a set of core criteria that need to be taken into account when selecting a specific fairness definition for real-world use case applications. Finally, we enumerate a set of key considerations and best practices for the design and employment of fairness methods on real-world AI applications.

There has been great interest in fairness in machine learning, especially in relation to classification problems. In ranking-related problems, such as in online advertising, recommender systems, and HR automation, much work on fairness remains to be done. Two complications arise: first, the protected attribute may not be available in many applications. Second, there are multiple measures of fairness of rankings, and optimization-based methods utilizing a single measure of fairness of rankings may produce rankings that are unfair with respect to other measures. In this work, we propose a randomized method for post-processing rankings, which do not require the availability of the protected attribute. In an extensive numerical study, we show the robustness of our methods with respect to P-Fairness and effectiveness with respect to Normalized Discounted Cumulative Gain (NDCG) from the baseline ranking, improving on previously proposed methods.

There has been much recent interest in near-term applications of quantum computers, i.e., using quantum circuits that have short decoherence times due to hardware limitations. Variational quantum algorithms (VQA), wherein an optimization algorithm implemented on a classical computer evaluates a parametrized quantum circuit as an objective function, are a leading framework in this space. An enormous breadth of algorithms in this framework have been proposed for solving a range of problems in machine learning, forecasting, applied physics, and combinatorial optimization, among others. In this paper, we analyze the iteration complexity of VQA, that is, the number of steps that VQA requires until its iterates satisfy a surrogate measure of optimality. We argue that although VQA procedures incorporate algorithms that can, in the idealized case, be modeled as classic procedures in the optimization literature, the particular nature of noise in near-term devices invalidates the claim of applicability of off-the-shelf analyses of these algorithms. Specifically, noise makes the evaluations of the objective function via quantum circuits biased. . Commonly used optimization procedures, such as SPSA and the parameter shift rule, can thus be seen as derivative-free optimization algorithms with biased function evaluations, for which there are currently no iteration complexity guarantees in the literature. We derive the missing guarantees and find that the rate of convergence is unaffected. However, the level of bias contributes unfavorably to both the constant therein, and the asymptotic distance to stationarity, i.e., the more bias, the farther one is guaranteed, at best, to reach a stationary point of the VQA objective.

There has been much recent progress in time series forecasting and estimation of system matrices of linear dynamical systems. We present an approach to both problems based on an asymptotically convergent hierarchy of convexifications of a certain nonconvex operator-valued problem, which is known as noncommutative polynomial optimization problem. We present promising computational results, including a comparison with methods implemented in MATLAB System Identification Toolbox.

The AIMD algorithm, which underpins the Transmission Control Protocol (TCP) for transporting data packets in communication networks, is perhaps the most successful control algorithm ever deployed. Recently, its use has been extended beyond communication networks, and successful applications of the AIMD algorithm have been reported in transportation, energy, and mathematical biology. A very recent development in the use of AIMD is its application in solving large-scale optimisation and distributed control problems without the need for inter-agent communication. In this context, an interesting problem arises when multiple AIMD networks are coupled in some sense (usually through a nonlinearity). The purpose of this note is to prove that such systems in certain settings inherit the ergodic properties of individual AIMD networks. This result has important consequences for the convergence of the aforementioned optimisation algorithms. The arguments in the paper also correct conceptual and technical errors in Alam et al. (2020, The convergence of finite-averaging of AIMD for distributed heterogeneous resource allocations. arXiv:2001.08083 [math.OC].).

Statistical Static Timing Analysis (SSTA) is studied from the point of view of mathematical optimization. We present two formulations of the problem of finding the critical path delay distribution that were not known before: (i) a formulation of the SSTA problem using Binary-Integer Programming and (ii) a practical formulation using Geometric Programming. For simplicity, we use histogram approximation of the distributions. Scalability of the approaches is studied and possible generalizations are discussed.

There has been a great deal of recent interest in binarized neural networks, especially because of their explainability. At the same time, automatic differentiation algorithms such as back-propagation fail for binarized neural networks, which limits their applicability. We show that binarized neural networks admit a tame representation by reformulating the problem of training binarized neural networks as a subadditive dual of a mixed-integer program, which we show to have nice properties. This makes it possible to use the framework of Bolte et al. for implicit differentiation, which offers the possibility for practical implementation of backpropagation in the context of binarized neural networks. This approach could also be used for a broader class of mixed-integer programs, beyond the training of binarized neural networks, as encountered in symbolic approaches to AI and beyond.

We present an online algorithm for time-varying semidefinite programs (TV-SDPs), based on the tracking of the solution trajectory of a low-rank matrix factorization, also known as the Burer–Monteiro factorization, in a path-following procedure. There, a predictor-corrector algorithm solves a sequence of linearized systems. This requires the introduction of a horizontal space constraint to ensure the local injectivity of the low-rank factorization. The method produces a sequence of approximate solutions for the original TV-SDP problem, for which we show that they stay close to the optimal solution path if properly initialized. Numerical experiments for a time-varying max-cut SDP relaxation demonstrate the computational advantages of the proposed method for tracking TV-SDPs in terms of runtime compared to off-the-shelf interior-point methods.

We investigate the topological quantum compilation of two-qubit operations within a system of Fibonacci anyons. Our primary goal is to generate gates that are approximately leakage-free and equivalent to the controlled-NOT (CNOT) gate up to single-qubit operations. These gates belong to the local equivalence class [CNOT]. Additionally, we explore which local equivalence classes of two-qubit operations can be naturally generated by braiding Fibonacci anyons. We discovered that most of the generated classes are located near the edges of the Weyl chamber representation of two-qubit gates, specifically between the local equivalence classes of the identity [1] and [CNOT], SWAP and between those of the double-controlled-NOT [DCNOT] and [SWAP]. Furthermore, we found a numerically exact implementation of a local equivalent of the SWAP gate using a sequence of only nine elements from the Fibonacci braiding gate set.

We consider rather a general class of multi-level optimization problems, where a convex objective function is to be minimized subject to constraints of optimality of nested convex optimization problems. As a special case, we consider a trilevel optimization problem, where the objective of the two lower layers consists of a sum of a smooth and a non-smooth term. Based on fixed-point theory and related arguments, we present a natural first-order algorithm and analyze its convergence and rates of convergence in several regimes of parameters.

In machine learning, training data often capture the behaviour of multiple subgroups of some underlying human population. This behaviour can often be modelled as observations of an unknown dynamical system with an unobserved state. When the training data for the subgroups are not controlled carefully, however, under-representation bias arises. To counter under-representation bias, we introduce two natural notions of fairness in timeseries forecasting problems: subgroup fairness and instantaneous fairness. These notion extend predictive parity to the learning of dynamical systems. We also show globally convergent methods for the fairness-constrained learning problems using hierarchies of convexifications of non-commutative polynomial optimisation problems. We also show that by exploiting sparsity in the convexifications, we can reduce the run time of our methods considerably. Our empirical results on a biased data set motivated by insurance applications and the well-known COMPAS data set demonstrate the efficacy of our methods.

n many sharing-economy applications, as well as in other, conventional applications, one wishes to regulate the behaviour of an ensemble of agents with guarantees on both the regulation of the ensemble in aggregate and the revenue or quality of service associated with each agent. Previous work [Automatica, Volume 108, 108483] has developed guarantees of unique ergodicity when there are linear filters. Here, we extend the guarantees to systems including non-linear elements, such as non-linear filters.

In power systems, one wishes to regulate the aggregate demand of an ensemble of distributed energy resources (DERs), such as controllable loads and battery energy storage systems. We propose a notion of predictability and fairness, which suggests that the long-term averages of prices or incentives offered should be independent of the initial states of the operators of the DER, the aggregator, and the power grid. We show that this notion cannot be guaranteed with many traditional controllers used by the load aggregator, including the usual proportional-integral (PI) controller. However, even considering the non-linearity of the alternating-current model, this notion of predictability and fairness can be guaranteed for incrementally input-to-state stable (iISS) controllers, under mild assumptions.

It is well known that two-sided markets are unfair in a number of ways. For example, female drivers on ride-hailing platforms earn less than their male colleagues per mile driven. Similar observations have been made for other minority subgroups in other two-sided markets. Here, we suggest a novel market-clearing mechanism for two-sided markets, which promotes equalization of the pay per hour worked across multiple subgroups, as well as within each subgroup. In the process, we introduce a novel notion of subgroup fairness (which we call Inter-fairness), which can be combined with other notions of fairness within each subgroup (called Intra-fairness), and the utility for the customers (Customer-Care) in the objective of the market-clearing problem. Although the novel non-linear terms in the objective complicate market clearing by making the problem non-convex, we show that a certain nonconvex augmented Lagrangian relaxation can be approximated to any precision in time polynomial in the number of market participants using semidefinite programming, thanks to its "hidden convexity". This makes it possible to implement the market-clearing mechanism efficiently. On the example of driver-ride assignment in an Uber-like system, we demonstrate the efficacy and scalability of the approach and trade-offs between Inter- and Intrafairness.

Monitoring of streamed data to detect abnormal behaviour (variously known as event detection, anomaly detection, change detection, or outlier detection) underlies many applications, especially within the Internet of Things. There, one often collects data from a variety of sources, with asynchronous sampling, and missing data. In this setting, one can detect abnormal behavior using low-rank techniques. In particular, we assume that normal observations come from a low-rank subspace, prior to being corrupted by a uniformly distributed noise. Correspondingly, we aim to recover a representation of the subspace, and perform event detection by running point-to-subspace distance query for incoming data. We use a variant of low-rank factorisation, which considers interval uncertainty sets around "known entries", on a suitable flattening of the input data to obtain a low-rank model. On-line, we compute the distance of incoming data to the low-rank normal subspace and update the subspace to keep it consistent with the seasonal changes present. For the distance computation, we consider subsampling. We bound the one-sided error as a function of the number of coordinates employed. In our computational experiments, we test the proposed algorithm on induction-loop data from Dublin, Ireland.

We consider the design of distributed algorithms that govern the manner in which agents contribute to a social sensing platform. Specifically, we are interested in situations where fairness among the agents contributing to the platform is needed. A notable example are platforms operated by public bodies, where fairness is a legal requirement. The design of such distributed systems is challenging due to the fact that we wish to simultaneously realise an efficient social sensing platform, but also deliver a predefined quality of service to the agents (for example, a fair opportunity to contribute to the platform). In this paper, we introduce iterated function systems (IFS) as a tool for the design and analysis of systems of this kind. We show how the IFS framework can be used to realise systems that deliver a predictable quality of service to agents, can be used to underpin contracts governing the interaction of agents with the social sensing platform, and which are efficient. To illustrate our design via a use case, we consider a large, high-density network of participating parked vehicles. When awoken by an administrative centre, this network proceeds to search for moving missing entities of interest using RFID-based techniques. We regulate which vehicles are actively searching for the moving entity of interest at any point in time. In doing so, we seek to equalise vehicular energy consumption across the network. This is illustrated through simulations of a search for a missing Alzheimer's patient in Melbourne, Australia. Experimental results are presented to illustrate the efficacy of our system and the predictability of access of agents to the platform independent of initial conditions.

In machine learning, training data often capture the behaviour of multiple subgroups of some underlying human population. When the amounts of training data for the subgroups are not controlled carefully, under-representation bias arises. We introduce two natural notions of subgroup fairness and instantaneous fairness to address such under-representation bias in time-series forecasting problems. In particular, we consider the subgroup-fair and instant-fair learning of a linear dynamical system (LDS) from multiple trajectories of varying lengths, and the associated forecasting problems. We provide globally convergent methods for the learning problems using hierarchies of convexifications of non-commutative polynomial optimisation problems. Our empirical results on a biased data set motivated by insurance applications and the well-known COMPAS data set demonstrate both the beneficial impact of fairness considerations on statistical performance and encouraging effects of exploiting sparsity on run time.

We present a brief, informal overview of the physical reality of electric power systems, its mathematical models, and some of the associated optimization problems. Many references are provided.

There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.

In semidefinite programming (SDP), a number of pre-processing techniques have been developed, including procedures based on chordal decomposition, which exploit sparsity in the semidefinite program in order to reduce the dimension of individual constraints, and procedures based on facial reduction, which reduces the dimension of the problem by removing redundant rows and columns. So far, these have been studied in isolation. We show that these techniques are, in fact, complementary. In computational experiments, we show that a two-step pre-processing followed by a standard interior-point method outperforms the interior point method, with or without either of the pre-processing techniques, by a considerable margin.