Optimization and Control (math.OC)

Abstract: This paper proposes a generalised framework for density estimation in large networks with measurable spatiotemporal variance in edge weights. We solve the stochastic shortest path problem for a large network by estimating the density of the edge weights in the network and analytically finding the distribution of a path. In this study, we employ Gaussian Processes to model the edge weights. This approach not only reduces the analytical complexity associated with computing the stochastic shortest path but also yields satisfactory performance. We also provide an online version of the model that yields a 30 times speedup in the algorithm's runtime while retaining equivalent performance. As an application of the model, we design a real-time trip planning system to find the stochastic shortest path between locations in the public transit network of Delhi. Our observations show that different paths have different likelihoods of being the shortest path at any given time in a public transit network. We demonstrate that choosing the stochastic shortest path over a deterministic shortest path leads to savings in travel time of up to 40\%. Thus, our model takes a significant step towards creating a reliable trip planner and increase the confidence of the general public in developing countries to take up public transit as a primary mode of transportation.

Abstract: We consider the problem of finding a low-cost allocation and ordering of tasks between a team of robots in a d-dimensional, uncertain, landscape, and the sensitivity of this solution to changes in the cost function. Various algorithms have been shown to give a 2-approximation to the MinSum allocation problem. By analysing such an auction algorithm, we obtain intervals on each cost, such that any fluctuation of the costs within these intervals will result in the auction algorithm outputting the same solution.

Abstract: This survey presents recent research on determining control-theoretic properties and designing controllers with rigorous guarantees and for nonlinear systems for which no mathematical models but measured trajectories are available. Data-driven control techniques have been developed to circumvent a time-consuming modelling by first principles and because of the increasing availability of data. Recently, this research field has gained increased attention by the application of Willems' fundamental lemma, which provides a fertile ground for the development of data-driven control schemes with guarantees for linear time-invariant systems. While the fundamental lemma can be generalized to further system classes, there does not exist a comparable comprising theory for nonlinear systems. At the same time, nonlinear systems constitute the majority of practical systems. Moreover, they include additional challenges such as nonconvex optimization and data-based surrogate models that prevent end-to-end guarantees. Therefore, a variety of data-driven control approaches has been developed with different required prior insights into the system to ensure a guaranteed inference. In this survey, we will discuss developments in the context of data-driven control for nonlinear systems. In particular, we will focus on approaches providing guarantees from finite data, while the analysis and the controller design are computationally tractable due to semidefinite programming. Thus, these approaches achieve reasonable advances compared to the state-of-the-art system analysis and controller design by models from system identification.

Abstract: In this paper, we provide a generalization of the forward-backward splitting algorithm for minimizing the sum of a proper convex lower semicontinuous function and a differentiable convex function whose gradient satisfies a locally Lipschitztype condition. We prove the convergence of our method and derive a linear convergence rate when the differentiable function is locally strongly convex. We recover classical results in the case when the gradient of the differentiable function is globally Lipschitz continuous and an already known linear convergence rate when the function is globally strongly convex. We apply the algorithm to approximate equilibria of variational mean field game systems with local couplings. Compared with some benchmark algorithms to solve these problems, our numerical tests show similar performances in terms of the number of iterations but an important gain in the required computational time.

Abstract: Optimal management of thermal and energy grids with fluctuating demand and prices requires to orchestrate the generation units (GU) among all their operating modes. A hierarchical approach is proposed to control coupled energy nonlinear systems. The high level hybrid optimization defines the unit commitment, with the optimal transition strategy, and best production profiles. The low level dynamic model predictive control (MPC), receiving the set-points from the upper layer, safely governs the systems considering process constraints. To enhance the overall efficiency of the system, a method to optimal start-up the GU is here presented: a linear parameter varying MPC computes the optimal trajectory in closed-loop by iteratively linearising the system along the previous optimal solution. The introduction of an intermediate equilibrium state as additional decision variable permits the reduction of the optimization horizon,while a terminal cost term steers the system to the target set-point. Simulation results show the effectiveness of the proposed approach.

Abstract: We propose an optimization formulation for the simultaneous estimation of a latent variable and the identification of a linear continuous-time dynamic system, given a single input-output pair. We justify this approach based on Bayesian maximum a posteriori estimators. Our scheme takes the form of a convex alternating minimization, over the trajectories and the dynamic model respectively. We prove its convergence to a local minimum which verifies a two point-boundary problem for the (latent) state variable and a tensor product expression for the optimal dynamics.

Abstract: We prove existence of equal area partitions of the unit sphere via optimal transport methods, accompanied by diameter bounds written in terms of Monge--Kantorovich distances. This can be used to obtain bounds on the expectation of the maximum diameter of partition sets, when points are uniformly sampled from the sphere. An application to the computation of sliced Monge--Kantorovich distances is also presented.

Abstract: The Sum-of-Squares (SOS) approximation method is a technique used in optimization problems to derive lower bounds to the optimal value of an objective function. By representing the objective function as a sum of squares in a feature space, the SOS method transforms non-convex global optimization problems into solvable semidefinite programs. This note presents an overview of the SOS method. We start with its application in finite-dimensional feature spaces and, subsequently, we extend it to infinite-dimensional feature spaces using kernels (k-SOS). Additionally, we highlight the utilization of SOS for estimating some relevant quantities in information theory, including the log-partition function.

Abstract: Hospital choice models often employ random utility theory and include waiting time as a choice determinant. When applied to evaluate health system improvement interventions, these models disregard that hospital choice in turn is a determinant of waiting time. We present a novel, general model capturing the endogeneous relationship between waiting time and hospital choice, including the choice to opt out, and characterize the unique equilibrium solution of the resulting convex problem. We apply the general model in a case study on the urban Chinese health system, specifying that patient choice follows a multinomial logit (MNL) model and waiting times are determined by M/M/1 queues. The results reveal that analyses which solely rely on MNL models overestimate the effectiveness of present policy interventions and that this effectiveness is limited. We explore alternative, more effective, improvement interventions.

Abstract: The appropriate design, construction, and operation of carbon capture and storage (CCS) and enhanced oil recovery (EOR) processes require a deep understanding of the resulting phases behavior in hydrocarbons-CO_2 multi-component mixtures under reservoir conditions. To model this behavior a nonlinear system consists of the equation of states and some mixing rules (for each component) needed to be solved simultaneously. The mixing usually requires to model the binary interaction between the components of the mixture. This work employs optimization techniques to enhance the predictions of such model by optimizing the binary interaction parameters. The results show that the optimized parameters, although obtained mathematically, are in physical ranges and can reproduce successfully the experimental observations, specially for the multi-component hydrocarbons systems containing Carbon dioxide at reservoir temperatures and pressures

Abstract: In this paper, based on information-theoretic upper bound on noise in convex Lipschitz continuous zeroth-order optimisation, we provide corresponding upper bounds for strongly-convex and smooth classes of problems using non-constructive proofs through optimal reductions. Also, we show that based on one-dimensional grid-search optimisation algorithm one can construct algorithm for simplex-constrained optimisation with upper bound on noise better than that for ball-constrained and asymptotic in dimensionality case.