We study the convex-concave bilinear saddle-point problem $\min_x \max_y f(x) + y^\top Ax - g(y)$, where both, only one, or none of the functions $f$ and $g$ are strongly convex, and suitable rank conditions on the matrix $A$ hold. The solution of this problem is at the core of many machine learning tasks. By employing tools from monotone operator theory, we systematically prove the contractivity (in turn, the linear convergence) of several first-order primal-dual algorithms, including the Chambolle–Pock method. Our approach results in concise proofs, and it yields new convergence guarantees and tighter bounds compared to known results.

We address the challenge of sequential data-driven decision-making under context distributional uncertainty. This problem arises in numerous real-world scenarios where the learner optimizes black-box objective functions in the presence of uncontrollable contextual variables. We consider the setting where the context distribution is uncertain but known to lie within an ambiguity set defined as a ball in the Wasserstein distance. We propose a novel algorithm for Wasserstein Distributionally Robust Bayesian Optimization that can handle continuous context distributions while maintaining computational tractability. Our theoretical analysis combines recent results in self-normalized concentration in Hilbert spaces and finite-sample bounds for distributionally robust optimization to establish sublinear regret bounds that match state-of-the-art results. Through extensive comparisons with existing approaches on both synthetic and real-world problems, we demonstrate the simplicity, effectiveness, and practical applicability of our proposed method.

Although social networks have expanded the range of ideas and information accessible to users, they are also criticized for amplifying the polarization of user opinions. Given the inherent complexity of these phenomena, existing approaches to counteract these effects typically rely on handcrafted algorithms and heuristics. We propose an elegant solution: we act on the network weights that model user interactions on social networks (e.g., ranking of users’ shared content in feeds), to optimize a performance metric (e.g., minimize polarization), while users’ opinions follow the classical Friedkin-Johnsen model. Our formulation gives rise to a challenging, large-scale optimization problem with non-convex constraints, for which we develop a gradient-based algorithm. Our scheme is simple, scalable, and versatile, as it can readily integrate different, potentially non-convex, objectives. We demonstrate its merit by: (i) rapidly solving complex social network intervention problems with 4.8 million variables based on the Reddit, LiveJournal, and DBLP datasets; (ii) outperforming competing approaches in terms of both computation time and disagreement reduction.

Optimization-based controller tuning is challenging because it requires formulating optimization problems explicitly as functions of controller parameters. Safe learning algorithms overcome the challenge by creating surrogate models from measured data. To ensure safety, such data-driven algorithms often rely on exhaustive grid search, which is computationally inefficient. In this paper, we propose a novel approach to safe learning by formulating a series of optimization problems instead of a grid search. We also develop a method for initializing the optimization problems to guarantee feasibility while using numerical solvers. The performance of the new method is first validated in a simulated precision motion system, demonstrating improved computational efficiency, and illustrating the role of exploiting numerical solvers to reach the desired precision. Experimental validation on an industrial-grade precision motion system confirms that the proposed algorithm achieves 30% better tracking at sub-micrometer precision as a state-of-the-art safe learning algorithm, improves the default auto-tuning solution, and reduces the computational cost seven times compared to learning algorithms based on exhaustive search.

This article presents the guided Bayesian optimization (BO) algorithm as an efficient data-driven method for iteratively tuning closed-loop controller parameters using a digital twin of the system. The digital twin is built using closed-loop data acquired during standard BO iterations, and activated when the uncertainty in the Gaussian Process model of the optimization objective on the real system is high. We define a controller tuning framework independent of the controller or the plant structure. Our proposed methodology is model-free, making it suitable for nonlinear and unmodelled plants with measurement noise. The objective function consists of performance metrics modeled by Gaussian processes. We utilize the available information in the closed-loop system to progressively maintain a digital twin that guides the optimizer, improving the data efficiency of our method. Switching the digital twin on and off is triggered by our data-driven criteria related to the digital twin’s uncertainty estimations in the BO tuning framework. Effectively, it replaces much of the exploration of the real system with exploration performed on the digital twin. We analyze the properties of our method in simulation and demonstrate its performance on two real closed-loop systems with different plant and controller structures. The experimental results show that our method requires fewer experiments on the physical plant than Bayesian optimization to find the optimal controller parameters. Note to Practitioners—Industrial applications typically are difficult to model due to disturbances. Bayesian optimization is a data-efficient iterative tuning method for a black box system in which the performance can only be measured given the control parameters. Iterative measurements involve operational costs. We propose a guided Bayesian optimization method that uses all information flow in a system to define a simplified digital twin of the system using out-of-the-box methods. It is continuously updated with data from the system. We use the digital twin instead of the real system to perform experiments and to find optimal controller parameters while we monitor the uncertainty of the resulting predictions. When the uncertainty exceeds a tolerance threshold, the real system is measured, and the digital twin is updated. This results in fewer experiments on the real system only when needed. We then demonstrate the improved data efficiency of the guided Bayesian optimization on real-time linear and rotary motor hardware. These common industrial plants need to be controlled rigorously in a closed-loop system. Our method requires 57% and 46% fewer experiments on the hardware than Bayesian optimization to tune the control parameters of the linear and rotary motor systems. Our generic approach is not limited to the controller parameters but also can optimize the parameters of a manufacturing process.

In this paper, we study the problem of online tracking in linear control systems, where the objective is to follow a moving target. Unlike classical tracking control, the target is unknown, non-stationary, and its state is revealed sequentially, thus, fitting the framework of online non-stochastic control. We consider the case of quadratic costs and propose a new algorithm, called predictive linear online tracking (PLOT). The algorithm uses recursive least squares with exponential forgetting to learn a time-varying dynamic model of the target. The learned model is used in the optimal policy under the framework of receding horizon control. We show the dynamic regret of PLOT scales with $\mathcal{O}(\sqrt{TV_T})$, where $V_T$ is the total variation of the target dynamics and $T$ is the time horizon. Unlike prior work, our theoretical results hold for non-stationary targets. We implement our online control algorithm on a real quadrotor, thus, showcasing one of the first successful applications of online control methods on real hardware.

This work studies discrete-time discounted Markov decision processes with continuous state and action spaces and addresses the inverse problem of inferring a cost function from observed optimal behavior. We first consider the case in which we have access to the entire expert policy and characterize the set of solutions to the inverse problem by using occupation measures, linear duality, and complementary slackness conditions. To avoid trivial solutions and ill-posedness, we introduce a natural linear normalization constraint. This results in an infinite-dimensional linear feasibility problem, prompting a thorough analysis of its properties. Next, we use linear function approximators and adopt a randomized approach, namely the scenario approach and related probabilistic feasibility guarantees, to derive $\varepsilon$-optimal solutions for the inverse problem. We further discuss the sample complexity for a desired approximation accuracy. Finally, we deal with the more realistic case where we only have access to a finite set of expert demonstrations and a generative model and provide bounds on the error made when working with samples.

Ensuring safety is a key aspect in sequential decision making problems, such as robotics or process control. The complexity of the underlying systems often makes finding the optimal decision challenging, especially when the safety-critical system is time-varying. Overcoming the problem of optimizing an unknown time-varying reward subject to unknown time-varying safety constraints, we propose TVSAFEOPT, a new algorithm built on Bayesian optimization with a spatio-temporal kernel. The algorithm is capable of safely tracking a time-varying safe region without the need for explicit change detection. Optimality guarantees are also provided for the algorithm when the optimization problem becomes stationary. We show that TVSAFEOPT compares favorably against SAFEOPT on synthetic data, both regarding safety and optimality. Evaluation on a realistic case study with gas compressors confirms that TVSAFEOPT ensures safety when solving time-varying optimization problems with unknown reward and safety functions.

Despite their success, policy gradient methods suffer from high variance of the gradient estimator, which can result in unsatisfactory sample complexity. Recently, numerous variance-reduced extensions of policy gradient methods with provably better sample complexity and competitive numerical performance have been proposed. After a compact survey on some of the main variance-reduced REINFORCE-type methods, we propose ProbAbilistic Gradient Estimation for Policy Gradient (PAGE-PG), a novel loopless variance-reduced policy gradient method based on a probabilistic switch between two types of update. Our method is inspired by the PAGE estimator for supervised learning and leverages importance sampling to obtain an unbiased gradient estimator. We show that PAGE-PG enjoys a $\mathcal{O}\left( \epsilon^{-3} \right)$ average sample complexity to reach an $\epsilon$-stationary solution, which matches the sample complexity of its most competitive counterparts under the same setting. A numerical evaluation confirms the competitive performance of our method on classical control tasks.

In this paper, we consider a cyber-physical manufacturing system (CPMS) scenario containing physical components (robots, sensors, and actuators), operating in a digitally connected, constrained environment to perform industrial tasks. The CPMS has a centralized control plane with digital twins (DTs) of the physical resources, computational resources, and a network manager that allocates network resources. Existing approaches for the allocation of network resources are typically fixed with respect to controller-dependent run-time specifications, which may impact the performance of physical processes. We propose a dynamic network management framework, where the network resource allocation schemes are controller-aware. The information about the controllers of the physical resources is implemented at the DT level, and metrics, such as regret bounds, take the process performance measures into account. The proposed network management schemes optimize physical system performance by balancing the shared resources between the physical assets on the plant floor, and by considering their control requirements, providing a new perspective for dynamic resource allocation. A simulation study is provided to illustrate the performance of the proposed network management approaches and compare their resource allocation performance efficiencies.

We consider large-scale Markov decision processes with an unknown cost function and address the problem of learning a policy from a finite set of expert demonstrations. We assume that the learner is not allowed to interact with the expert and has no access to reinforcement signal of any kind. Existing inverse reinforcement learning methods come with strong theoretical guarantees, but are computationally expensive, while state-of-the-art policy optimization algorithms achieve significant empirical success, but are hampered by limited theoretical understanding. To bridge the gap between theory and practice, we introduce a novel bilinear saddle-point framework using Lagrangian duality. The proposed primal-dual viewpoint allows us to develop a model-free provably efficient algorithm through the lens of stochastic convex optimization. The method enjoys the advantages of simplicity of implementation, low memory requirements, and computational and sample complexities independent of the number of states. We further present an equivalent no-regret online-learning interpretation.

We present a reinforcement learning-based solution to autonomously race on a miniature race car platform. We show that a policy that is trained purely in simulation using a relatively simple vehicle model, including model randomization, can be successfully transferred to the real robotic setup. We achieve this by using a novel policy output regularization approach and a lifted action space which enables smooth actions but still aggressive race car driving. We show that this regularized policy does outperform the Soft Actor Critic (SAC) baseline method, both in simulation and on the real car, but it is still outperformed by a Model Predictive Controller (MPC) state-of-the-art method. The refinement of the policy with three hours of real-world interaction data allows the reinforcement learning policy to achieve lap times similar to the MPC controller while reducing track constraint violations by 50%.

Adaptive control approaches yield high-performance controllers when a precise system model or suitable parametrizations of the controller are available. Existing data-driven approaches for adaptive control mostly augment standard model-based methods with additional information about uncertainties in the dynamics or about disturbances. In this work, we propose a purely data-driven, model-free approach for adaptive control. Tuning low-level controllers based solely on system data raises concerns on the underlying algorithm safety and computational performance. Thus, our approach builds on GOOSE, an algorithm for safe and sample-efficient Bayesian optimization. We introduce several computational and algorithmic modifications in GOOSE that enable its practical use on a rotational motion system. We numerically demonstrate for several types of disturbances that our approach is sample efficient, outperforms constrained Bayesian optimization in terms of safety, and achieves the performance optima computed by grid evaluation. We further demonstrate the proposed adaptive control approach experimentally on a rotational motion system.

In this paper we propose a hierarchical controller for autonomous racing where the same vehicle model is used in a two level optimization framework for motion planning. The high-level controller computes a trajectory that minimizes the lap time, and the low-level nonlinear model predictive path following controller tracks the computed trajectory online. Following a computed optimal trajectory avoids online planning and enables fast computational times. The efficiency is further enhanced by the coupling of the two levels through a terminal constraint, computed in the high-level controller. Including this constraint in the real-time optimization level ensures that the prediction horizon can be shortened, while safety is guaranteed. This proves crucial for the experimental validation of the approach on a full size driverless race car. The vehicle in question won two international student racing competitions using the proposed framework; moreover, our hierarchical controller achieved an improvement of 20% in the lap time compared to the state of the art result achieved using a very similar car and track.

The alternating direction method of multipliers (ADMM) is a powerful operator splitting technique for solving structured convex optimization problems. Due to its relatively low per-iteration computational cost and ability to exploit sparsity in the problem data, it is particularly suitable for large-scale optimization. However, the method may still take prohibitively long to compute solutions to very large problem instances. Although ADMM is known to be parallelizable, this feature is rarely exploited in real implementations. In this paper we exploit the parallel computing architecture of a graphics processing unit (GPU) to accelerate ADMM. We build our solver on top of OSQP, a state-of-the-art implementation of ADMM for quadratic programming. Our open-source CUDA C implementation has been tested on many large-scale problems and was shown to be up to two orders of magnitude faster than the CPU implementation.

In this paper, we propose an embedded optimization approach for the localization of Internet of Things (IoT) devices making use of range measurements from ultra-wideband (UWB) signals. Low-cost, low-power UWB radios provide time-of-arrival measurements with decimeter accuracy over large distances. UWB-based localization methods have been envisioned to enable feedback control in IoT applications, particularly, in GPS-denied environments, and large wireless sensor networks. In this paper, we formulate the localization task as a nonlinear least-squares optimization problem based on two-way time-of-arrival measurements between the IoT device and several UWB radios installed in a 3-D environment. For the practical implementation of large-scale IoT deployments we further assume only approximate knowledge of the UWB radio locations. We solve the resulting optimization problem directly on IoT devices equipped with off-the-shelf microcontrollers using state-of-the-art code generation techniques for plug-and-play deployment of the nonlinear-programming algorithms. This paper further provides practical implementation details to improve the localization accuracy for feedback control in experimental IoT applications. The experimental results finally show that subdecimeter localization accuracy can be achieved using the proposed optimization-based approach, even when the majority of the UWB radio locations are unknown.

We consider the problem of estimating a probability distribution that maximizes the entropy while satisfying a finite number of moment constraints, possibly corrupted by noise. Based on duality of convex programming, we present a novel approximation scheme using a smoothed fast gradient method that is equipped with explicit bounds on the approximation error. We further demonstrate how the presented scheme can be used for approximating the chemical master equation through the zero-information moment closure method, and for an approximate dynamic programming approach in the context of constrained Markov decision processes with uncountable state and action spaces.

Understanding the structure and function of complex gene regulatory networks using classical genetic assays is an error-prone procedure that frequently generates ambiguous outcomes. Even some of the best-characterized gene networks contain interactions whose validity is not conclusively proven. Founded on dynamic experimental data, mechanistic mathematical models are able to offer detailed insights that would otherwise require prohibitively large numbers of genetic experiments. Here we attempt mechanistic modeling of the transcriptional network formed by the four GATA-factor proteins, a well-studied system of central importance for nitrogen-source regulation of transcription in the yeast Saccharomyces cerevisiae. To resolve ambiguities in the network organization, we encoded a set of five interactions hypothesized in the literature into a set of 32 mathematical models, and employed Bayesian model selection to identify the most plausible set of interactions based on dynamic gene expression data. The top-ranking model was validated on newly generated GFP reporter dynamic data and was subsequently used to gain a better understanding of how yeast cells organize their transcriptional response to dynamic changes of nitrogen sources. Our work constitutes a necessary and important step towards obtaining a holistic view of the yeast nitrogen regulation mechanisms; on the computational side, it provides a demonstration of how powerful Monte Carlo techniques can be creatively combined and used to address the great challenges of large-scale dynamical system inference.

We formulate fuel-optimal conflict-free aircraft trajectory planning as a hybrid optimal control problem. The discrete modes of the hybrid system capture the air traffic procedures for conflict resolution, e.g., speed and turn advisories. To solve problems of realistic dimensions arising from air traffic sector planning, we formulate a numerically tractable approach to solve the hybrid optimal control problem. The approach is based on introducing binary functions for each mode, relaxing the binary functions and including a penalty term on the relaxation. The transformed and discretized problem is a nonlinear program. We use the approach on a realistic case study with seven aircraft within an air traffic control sector, in which we find minimum-fuel conflict-free trajectories.

We consider a viability based approach to guarantee recursive feasibility of a finite horizon path planner. The path planner is formulated as a hybrid system for which a difference inclusion reformulation is derived by exploiting the special structure of the problem. Based on this approximation, the viability kernel, which characterizes all safe states and the corresponding safe controls, can be calculated. Using the set of safe controls the computation time of the on-line path planning can be reduced, by only generating viable trajectories. Finally, a condition characterizing the unsafe set in case of on-line obstacle avoidance is derived.

MOTIVATION: Fluorescence recovery after photobleaching (FRAP) is a functional live cell imaging technique that permits the exploration of protein dynamics in living cells. To extract kinetic parameters from FRAP data, a number of analytical models have been developed. Simplifications are inherent in these models, which may lead to inexhaustive or inaccurate exploitation of the experimental data. An appealing alternative is offered by the simulation of biological processes in realistic environments at a particle level. However, inference of kinetic parameters using simulation-based models is still limited. RESULTS: We introduce and demonstrate a new method for the inference of kinetic parameter values from FRAP data. A small number of in silico FRAP experiments is used to construct a mapping from FRAP recovery curves to the parameters of the underlying protein kinetics. Parameter estimates from experimental data can then be computed by applying the mapping to the observed recovery curves. A bootstrap process is used to investigate identifiability of the physical parameters and determine confidence regions for their estimates. Our method circumvents the computational burden of seeking the best-fitting parameters via iterative simulation. After validation on synthetic data, the method is applied to the analysis of the nuclear proteins Cdt1, PCNA and GFPnls. Parameter estimation results from several experimental samples are in accordance with previous findings, but also allow us to discuss identifiability issues as well as cell-to-cell variability of the protein kinetics. IMPLEMENTATION: All methods were implemented in MATLAB R2011b. Monte Carlo simulations were run on the HPC cluster Brutus of ETH Zurich. CONTACT: [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We propose an iterative method for approximately computing the capacity of discrete memoryless channels, possibly under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. The presented method requires O(M2N√log N/ε) to provide an estimate of the capacity to within ε, where N and M denote the input and output alphabet size; a single iteration has a complexity O(MN). We also show how to approximately compute the capacity of memoryless channels having a bounded continuous input alphabet and a countable output alphabet under some mild assumptions on the decay rate of the channel's tail. It is shown that discrete-time Poisson channels fall into this problem class. As an example, we compute sharp upper and lower bounds for the capacity of a discrete-time Poisson channel with a peak-power input constraint.

We propose an iterative method for efficiently approximating the capacity of discrete memoryless channels, possibly having additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. To find an ε-approximation of the capacity, in case of no additional input constraints, the presented method has a computational complexity O(1 over εM2N√logN), where N and M denote the input and output alphabet size, and a single iteration has a complexity O(MN).

We present a new algorithm, based on duality of convex programming and the specific structure of the channel capacity problem, to iteratively construct upper and lower bounds for the capacity of memoryless channels having continuous input and countable output alphabets. Under a mild assumption on the decay rate of the channel's tail, explicit bounds for the approximation error are provided. We demonstrate the applicability of our result on the discrete-time Poisson channel having a peak-power input constraint.

We synthesize controllers for discrete-time stochastic hybrid systems such that the probability of satisfying a given specification on the system is maximized. The specifications are defined with finite state automata. It is shown that automata satisfaction is equivalent to a reachability problem in an extended state space consisting of the system and the automaton state spaces. The control policy is defined as a map from this extended state space to the input space. Using existing results on maximizing reachability probability, the control policy is designed to maximize probability of satisfying the specification.

We present a dynamic programming based solution to a stochastic reachability problem for a controlled discrete-time stochastic hybrid system. A sum-multiplicative cost function is introduced along with a corresponding dynamic recursion which quantifies the probability of hitting a target set at some point during a finite time horizon, while avoiding an obstacle set during each time step preceding the target hitting time. In contrast with earlier works which consider the reach and avoid sets as both deterministic and time invariant, we consider the avoid set to be both time-varying and probabilistic. Optimal reach-avoid control policies are derived as the solution to an optimal control problem via dynamic programming. A computational example motivated by aircraft motion planning is provided.

In this paper, impulsive control is applied to a class of linear feedback systems and studied both theoretically and experimentally, with a particular focus on the usage in nanopositioning. By using impulsive control, improvements in tracking performance and tolerance to measurement noise can be achieved which are beyond the limits of conventional linear feedback.

DNA replication is one of the most fundamental processes in the life of every cell. In earlier work a model to capture the mechanics of the DNA replication process was developed in the stochastic hybrid systems framework. Monte Carlo simulations of the model allowed us to make novel predictions regarding the mechanisms behind DNA replication based on experimental data for the fission yeast. Here the stochastic hybrid model is adopted to the Hybrid Input/Output Automaton formalism. We then verify that the model captures the mechanisms of DNA replication process by induction proofs. Our results demonstrate that the model is indeed a faithful representation of the physical reality and lend theoretical support for the predictions of the model.

Probabilistic Computation Tree Logic (PCTL) is a well-known modal logic which has become a standard for expressing temporal properties of finite-state Markov chains in the context of automated model checking. In this paper, we consider PCTL for noncountable-space Markov chains, and we show that there is a substantial affinity between certain of its operators and problems of Dynamic Programming. We prove some basic properties of the solutions to the latter. We also provide two examples and demonstrate how recovery strategies in practical applications, which are naturally stated as reach-avoid problems, can be viewed as particular cases of PCTL formulas.

MOTIVATION: Modern experimental techniques for time course measurement of gene expression enable the identification of dynamical models of genetic regulatory networks. In general, identification involves fitting appropriate network structures and parameters to the data. For a given set of genes, exploring all possible network structures is clearly prohibitive. Modelling and identification methods for the a priori selection of network structures compatible with biological knowledge and experimental data are necessary to make the identification problem tractable. RESULTS: We propose a differential equation modelling framework where the regulatory interactions among genes are expressed in terms of unate functions, a class of gene activation rules commonly encountered in Boolean network modelling. We establish analytical properties of the models in the class and exploit them to devise a two-step procedure for gene network reconstruction from product concentration and synthesis rate time series. The first step isolates a family of model structures compatible with the data from a set of most relevant biological hypotheses. The second step explores this family and returns a pool of best fitting models along with estimates of their parameters. The method is tested on a simulated network and compared with state-of-the-art network inference methods on the benchmark synthetic network IRMA.

DNA replication is one of the most fundamental processes in the life of every cell. In earlier work a model to capture the mechanics of the DNA replication process was developed. The model allowed us to make novel predictions regarding the mechanisms behind DNA replication based on experimental data for the fission yeast. One of the difficulties we had to overcome in the process was tuning of the model parameters based on experimental data, which, for lack of better methods had to be done manually. Here we propose a methodology for systematizing this process, inspired by techniques for multi-objective optimization.

MOTIVATION: Identification of regulatory networks is typically based on deterministic models of gene expression. Increasing experimental evidence suggests that the gene regulation process is intrinsically random. To ensure accurate and thorough processing of the experimental data, stochasticity must be explicitly accounted for both at the modelling stage and in the design of the identification algorithms. RESULTS: We propose a model of gene expression in prokaryotes where transcription is described as a probabilistic event, whereas protein synthesis and degradation are captured by first-order deterministic kinetics. Based on this model and assuming that the network of interactions is known, a method for estimating unknown parameters, such as synthesis and binding rates, from the outcomes of multiple time-course experiments is introduced. The method accounts naturally for sparse, irregularly sampled and noisy data and is applicable to gene networks of arbitrary size. The performance of the method is evaluated on a model of nutrient stress response in Escherichia coli.

Simulated annealing is a popular method for approaching the solution of a global optimization problem. Existing results on its performance apply to discrete com- binatorial optimization where the optimization variables can assume only a finite set of possible values. We introduce a new general formulation of simulated an- nealing which allows one to guarantee finite-time performance in the optimiza- tion of functions of continuous variables. The results hold universally for any optimization problem on a bounded domain and establish a connection between simulated annealing and up-to-date theory of convergence of Markov chain Monte Carlo methods on continuous domains. This work is inspired by the concept of finite-time learning with known accuracy and confidence developed in statistical learning theory. Optimization is the general problem of finding a value of a vector of variables θ that maximizes (or minimizes) some scalar criterion U (θ). The set of all possible values of the vector θ is called the optimization domain. The elements of θ can be discrete or continuous variables. In the first case the optimization domain is usually finite, such as in the well-known traveling salesman problem; in the second case the optimization domain is a continuous set. An important example of a continuous optimization domain is the set of 3-D configurations of a sequence of amino-acids in the problem of finding the minimum energy folding of the corresponding protein [1]. In principle, any optimization problem on a finite domain can be solved by an exhaustive search. However, this is often beyond computational capacity: the optimization domain of the traveling salesman problem with 100 cities contains more than 10155 possible tours. An efficient algorithm to solve the traveling salesman and many similar problems has not yet been found and such prob- lems remain reliably solvable only in principle [2]. Statistical mechanics has inspired widely used methods for finding good approximate solutions in hard discrete optimization problems which defy efficient exact solutions [3, 4, 5, 6]. Here a key idea has been that of simulated annealing [3]: a random search based on the Metropolis-Hastings algorithm, such that the distribution of the ele- ments of the domain visited during the search converges to an equilibrium distribution concentrated around the global optimizers. Convergence and finite-time performance of simulated annealing on finite domains has been evaluated in many works, e.g. [7, 8, 9, 10]. On continuous domains, most popular optimization methods perform a local gradient-based search and in general converge to local optimizers; with the notable exception of convex criteria where convergence to the unique global optimizer occurs [11]. Simulated annealing performs a global search and can be easily implemented on continuous domains. Hence it can be considered a powerful complement to local methods. In this paper, we introduce for the first time rigorous guarantees on the finite-time performance of simulated annealing on continuous domains. We will show that it is possible to derive simulated annealing algorithms which, with an arbitrarily high level of confidence, find an approximate solution to the problem of optimizing a function of continuous variables, within a specified tolerance to the global optimal solution after a known finite number of steps. Rigorous guarantees on the finite-time performance of simulated annealing in the optimiza- tion of functions of continuous variables have never been obtained before; the only results available state that simulated annealing converges to a global optimizer as the number of steps grows to infin- ity, e.g. [12, 13, 14, 15]. The background of our work is twofold. On the one hand, our notion of approximate solution to a global optimization problem is inspired by the concept of finite-time learning with known accuracy and confidence developed in statistical learning theory [16, 17]. We actually maintain an important aspect of statistical learning theory which is that we do not introduce any particular assumption on the optimization criterion, i.e. our results hold regardless of what U is. On the other hand, we ground our results on the theory of convergence, with quantitative bounds on the distance to the target dis- tribution, of the Metropolis-Hastings algorithm and Markov Chain Monte Carlo (MCMC) methods, which has been one of the main achievements of recent research in statistics [18, 19, 20, 21]. In this paper, we will not develop any ready-to-use optimization algorithm. We will instead in- troduce a general formulation of the simulated annealing method which allows one to derive new simulated annealing algorithms with rigorous finite-time guarantees on the basis of existing theory. The Metropolis-Hastings algorithm and the general family of MCMC methods have many degrees of freedom. The choice and comparison of specific algorithms goes beyond the scope of the paper. In Simulated annealing we introduce the method and fix the notation. In Convergence we recall the reasons why finite-time guarantees for simulated annealing on continuous domains have not been obtained before. In Finite-time guaran- tees we present the main result of the paper. In Conclusions we state our findings and conclude the paper. The paper is organized in the following sections. 1 Simulated annealing The original formulation of simulated annealing was inspired by the analogy between the stochastic evolution of the thermodynamic state of an annealing material towards the configurations of minimal energy and the search for the global minimum of an optimization criterion [3]. In the procedure, the optimization criterion plays the role of the energy and the state of the annealed material is simulated by the evolution of the state of an inhomogeneous Markov chain. The state of the chain evolves according to the Metropolis-Hastings algorithm in order to simulate the Boltzmann distribution of thermodynamic equilibrium. The Boltzmann distribution is simulated for a decreasing sequence of temperatures (“cooling”). The target distribution of the cooling procedure is the limiting Boltzmann distribution, for the temperature that tends to zero, which takes non-zero values only on the set of global minimizers [7]. The original formulation of the method was for a finite domain. However, simulated anneal- ing can be generalized straightforwardly to a continuous domain because the Metropolis-Hastings algorithm can be used with almost no differences on discrete and continuous domains The main difference is that on a continuous domain the equilibrium distributions are specified by probability densities. On a continuous domain, Markov transition kernels in which the distribution of the el- ements visited by the chain converges to an equilibrium distribution with the desired density can be constructed using the Metropolis-Hastings algorithm and the general family of MCMC methods [22]. We point out that Boltzmann distributions are not the only distributions which can be adopted as equilibrium distributions in simulated annealing [7]. In this paper it is convenient for us to adopt a different type of equilibrium distribution in place of Boltzmann distributions.

The safety of flights, and, in particular, separation assurance, is one of the main tasks of air traffic control (ATC). Conflict resolution refers to the process used by ATCs to prevent loss of separation. Conflict resolution involves issuing instructions to aircraft to avoid loss of safe separation between them and, at the same time, direct them to their destinations. Conflict resolution requires decision making in the face of the considerable levels of uncertainty inherent in the motion of aircraft. In this paper, a framework for conflict resolution that allows one to take into account such levels of uncertainty using a stochastic simulator is presented. The conflict resolution task is posed as the problem of optimizing an expected value criterion. It is then shown how the cost criterion can be selected to ensure an upper bound on the probability of conflict for the optimal maneuver. Optimization of the expected value resolution criterion is carried out through an iterative procedure based on Markov chain Monte Carlo. Simulation examples inspired by current ATC practice in terminal maneuvering areas and approach sectors illustrate the proposed conflict resolution strategy.

We demonstrate a high-level approach to modeling, analyzing, and verifying complex safety-critical systems through a case study on the traffic alert and collision avoidance system (TCAS); an avionics system that detects and resolves aircraft collision threats. Due to the complexity of the TCAS software and the hybrid nature of the closed-loop system, the traditional testing technique of exhaustive simulation does not constitute a viable verification approach. Moreover, the detailed specification of the system software employed to date as a means toward analysis and verification neither helps in intuitively understanding the behavior of the system nor enables the analysis of the closed-loop system behavior. We advocate defining high-level hybrid system models that capture the behavior not only of the software but also of the airplanes, sensors, pilots, etc. In particular, we show how the core components of TCAS can be captured by relatively simple hybrid I/O automata, which are amenable to format analysis. We then outline a methodology for establishing conditions under which TCAS guarantees sufficient separation in altitude for aircraft involved in collision threats. The contributions of the paper are the high-level models of the closed-loop TCAS system and the demonstration of the usefulness of high-level modeling, analysis, and verification techniques.

We present a method to design controllers for safety specifications in hybrid systems. The hybrid system combines discrete event dynamics with nonlinear continuous dynamics: the discrete event dynamics model linguistic and qualitative information and naturally accommodate mode switching logic, and the continuous dynamics model the physical processes themselves, such as the continuous response of an aircraft to the forces of aileron and throttle. Input variables model both continuous and discrete control and disturbance parameters. We translate safety specifications into restrictions on the system's reachable sets of states. Then, using analysis based on optimal control and game theory for automata and continuous dynamical systems, we derive Hamilton-Jacobi equations whose solutions describe the boundaries of reachable sets. These equations are the heart of our general controller synthesis technique for hybrid systems, in which we calculate feedback control laws for the continuous and discrete variables, which guarantee that the hybrid system remains in the "safe subset" of the reachable set. We discuss issues related to computing solutions to Hamilton-Jacobi equations. Throughout, we demonstrate out techniques on examples of hybrid automata modeling aircraft conflict resolution, autopilot flight mode switching, and vehicle collision avoidance.

Conflict detection and resolution schemes operating at the mid-range and short-range level of the air traffic management process are discussed. Probabilistic models for predicting the aircraft position in the near-term and mid-term future are developed. Based on the mid-term prediction model, the maximum instantaneous probability of conflict is proposed as a criticality measure for two aircraft encounters. Randomized algorithms are introduced to efficiently estimate this measure of criticality and provide quantitative bounds on the level of approximation introduced. For short-term detection, approximate closed-form analytical expressions for the probability of conflict are obtained, using the short-term prediction model. Based on these expressions, an algorithm for decentralized conflict detection and resolution that generalizes potential fields methods for path planning to a probabilistic dynamic environment is proposed. The algorithms are validated using Monte Carlo simulations.

In this paper we demonstrate a high-level approach to modeling and analyzing complex safety-critical systems through a case study in the area of air traffic management. In particular, we focus our attention on the Traffic Alert and Collision Avoidance System (TCAS); an on-board conflict detection and resolution system which alerts pilots to the presence of nearby aircraft that pose a mid-air collision threat and issues conflict resolution advisories. Due to the complexity of the TCAS software and the hybrid nature of the closed-loop system, the traditional testing techniques through simulation do not constitute a viable verification approach. To aid people in analyzing and designing such systems, we advocate defining high-level mathematical system models that capture the behavior not only of the software, but also of the airplanes, sensors, and pilots-that is, high-level hybrid system models. In particular we show how the core components of this complex system can be captured by relatively simple Hybrid I/O Automata (HIOA) which are amenable to formal analysis. We then outline a methodology for establishing conditions under which the conflict resolution advisories issued by TCAS guarantee sufficient separation in altitude for aircraft involved in mid-air collision threats. Although our results are intended only as illustrations of high-level modeling and analysis techniques, the TCAS system models provide a foundation for study of a wide range of properties of the system's behavior.

A formalism for coding fuzzy models of dynamical systems is presented. It is shown that the formalism is rich enough to capture the performance of arbitrary conventional discrete time dynamical systems whose transition maps are polynomials with rational coefficients. The proof of this fact provides a constructive algorithm for generating fuzzy models to arbitrarily closely approximate an arbitrary map on a compact set. Our modeling formalism highlights the similarities between fuzzy systems and hybrid control systems. We hope to be able to exploit these similarities by extending results from the area of hybrid systems to the fuzzy domain and vice versa.