Search

We define and analyze the notion of variational Wardrop equilibrium for nonatomic aggregative games with an infinity of players types. These equilibria are characterized through an infinite-dimensional variational inequality. We show, under monotonicity conditions, a convergence theorem enables to approximate such an equilibrium with arbitrary precision. To this end, we introduce a sequence of nonatomic games with a finite number of players types, which approximates the initial game. We show the existence of a symmetric Wardrop equilibrium in each of these games. We prove that those symmetric equilibria converge to an equilibrium of the infinite game, and that they can be computed as solutions of finite-dimensional variational inequalities. The model is illustrated through an example from smart grids: the description of a large population of electricity consumers by a parametric distribution gives a nonatomic game with an infinity of different players types, with actions subject to coupling constraints., arXiv admin note: substantial text overlap with arXiv:1806.06230

This paper addresses the single-item single-stocking location non-stationary stochastic lot-sizing problem under a reorder point – order quantity control strategy. The reorder points and order quantities are chosen at the beginning of the planning horizon. The reorder points are allowed to vary with time and we consider order quantities either to be a series of time-dependent constants or a fixed value; this leads to two variants of the policy: the ( s t , Q t ) and the ( s t , Q ) policies, respectively. For both policies, we present stochastic dynamic programs (SDP) to determine optimal policy parameters and introduce mixed integer non-linear programming (MINLP) heuristics that leverage piecewise-linear approximations of the cost function. Numerical experiments demonstrate that our solution method efficiently computes near-optimal parameters for a broad class of problem instances.

This work focuses on finding optimal locations for charging stations for one-way electric car sharing programs. The relocation of vehicles by a service staff is generally required in vehicle sharing programs in order to correct imbalances in the network. We seek to limit the need for vehicle relocation by strategically locating charging stations given estimates of traffic flow. A mixed-integer linear programming formulation is presented with a large number of potential charging station locations. A column generation approach is used which finds an optimal set of locations for the continuous relaxation of our problem. Results of a numerical experiment using real traffic and geographic information system location data show that our formulation significantly increases the balanced flow across the network, while our column generation technique was found to produce a superior solution in much shorter computation time compared to solving the original formulation with all possible station locations.

In a Hilbert space, we provide a fast dynamic approach to the hierarchical minimization problem which consists in finding the minimum norm solution of a convex minimization problem. For this, we study the convergence properties of the trajectories generated by a damped inertial dynamic with Tikhonov regularization. When the time goes to infinity, the Tikhonov regularization parameter is supposed to tend towards zero, not too fast, which is a key property to make the trajectories strongly converge towards the minimizer of $f$ of minimum norm. According to the structure of the heavy ball method for strongly convex functions, the viscous damping coefficient is proportional to the square root of the Tikhonov regularization parameter. Therefore, it also converges to zero, which will ensure rapid convergence of values. Precisely, under a proper tuning of these parameters, based on Lyapunov's analysis, we show that the trajectories strongly converge towards the minimizer of minimum norm, and we provide the convergence rate of the values. We show a trade off between the property of fast convergence of values, and the property of strong convergence towards the minimum norm solution. This study improves several previous works where this type of results was obtained under restrictive hypotheses., 22 pages, 1 figure. arXiv admin note: text overlap with arXiv:2104.11987

Network flow formulations are among the most successful tools to solve optimization problems. Such formulations correspond to determining an optimal flow in a network. One particular class of network flow formulations is the arc flow, where variables represent flows on individual arcs of the network. For N P -hard problems, polynomial-sized arc flow models typically provide weak linear relaxations and may have too much symmetry to be efficient in practice. Instead, arc flow models with a pseudo-polynomial size usually provide strong relaxations and are efficient in practice. The interest in pseudo-polynomial arc flow formulations has grown considerably in the last twenty years, in which they have been used to solve many open instances of hard problems. A remarkable advantage of pseudo-polynomial arc flow models is the possibility to solve practical-sized instances directly by a Mixed Integer Linear Programming solver, avoiding the implementation of complex methods based on column generation. In this survey, we present theoretical foundations of pseudo-polynomial arc flow formulations, by showing a relation between their network and Dynamic Programming (DP). This relation allows a better understanding of the strength of these formulations, through a link with models obtained by Dantzig-Wolfe decomposition. The relation with DP also allows a new perspective to relate state-space relaxation methods for DP with arc flow models. We also present a dual point of view to contrast the linear relaxation of arc flow models with that of models based on paths and cycles. To conclude, we review the main solution methods and applications of arc flow models based on DP in several domains such as cutting, packing, scheduling, and routing.

Metaheuristics are widely employed to solve hard optimization problems, like vehicle routing problems (VRP), for which exact solution methods are impractical. In particular, local search-based metaheuristics have been successfully applied to the capacitated VRP (CVRP). The CVRP aims at defining the minimum-cost delivery routes for a given set of identical vehicles since each vehicle only travels one route and there is a single (central) depot. The best metaheuristics to the CVRP avoid getting stuck in local optima by embedding specific hill-climbing mechanisms such as diversification strategies into the solution methods. This paper introduces a hybridization of a novel adaptive version of Iterated Local Search with Path-Relinking (AILS-PR) to the CVRP. The major contribution of this paper is an automatic mechanism to control the diversity step of the metaheuristic to allow it to escape from local optima. The results of experiments with 100 benchmark CVPR instances show that AILS-PR outperformed the state-of-the-art CVRP metaheuristics.

Mobile medical units (MMUs) are customized vehicles fitted with medical equipment that are used to provide primary care in rural environments. As MMUs can be easily relocated, they enable a demand-oriented, flexible, and local provision of health services. In this paper, we investigate the strategic planning of an MMU service by deciding where MMU operation sites should be set up and how often these should be serviced. To that end, we study the strategic planning problem for MMUs ( SPMMU ) – a capacitated set covering problem that includes existing practices and two types of patient demands: (i) steerable demands representing patients who seek health services through a centralized appointment system and can be steered to any treatment facility within a given consideration set and (ii) unsteerable demands representing walk-in patients who always visit the closest available treatment facility. We propose an integer linear program for the SPMMU that can be solved via Benders decomposition and constraint generation. Starting from this formulation, we focus on the uncertain version of the problem in which steerable and unsteerable demands are modeled as random variables that may vary within a given interval. Using methods from robust optimization and duality theory, we devise exact constraint generation methods to solve the robust counterparts for interval and budgeted uncertainty sets. All our results transfer to the session-specific SPMMU and we evaluate our models in a computational study based on a set of instances generated from a rural primary care system in Germany.

Sustainable Supply Chain (SSC) management aims at integrating economic, environmental and social goals to assist in the long-term planning of a company and its supply chains. There is no consensus in the literature as to whether social and environmental responsibilities are profit-compatible. However, the conflicting nature of these goals is explicit when considering specific assessment measures and, in this scenario, multi-objective optimization is a way to represent problems that simultaneously optimize the goals. This paper proposes a Lagrangian matheuristic method, called $AugMathLagr$, to solve a hard and relevant multi-objective problem found in the literature. $AugMathLagr$ was extensively tested using artificial instances defined by a generator presented in this paper. The results show a competitive performance of $AugMathLagr$ when compared with an exact multi-objective method limited by time and a matheuristic recently proposed in the literature and adapted here to address the studied problem. In addition, computational results on a case study are presented and analyzed, and demonstrate the outstanding performance of $AugMathLagr$., 45 pages. Paper accepted to European Journal of Operational Research

A method to compute optimal collision avoidance maneuvers for short-term encounters is presented. The maneuvers are modeled as multiple-impulses to handle impulsive cases and to approximate finite burn arcs associated either with short alert times or the use of low-thrust propulsion. The maneuver design is formulated as a sequence of convex optimization problems solved in polynomial time by state-of-the-art primal–dual interior-point algorithms. The proposed approach calculates optimal solutions without assumptions about the thrust arc structure and thrust direction. The execution time is fraction of a second for an optimization problem with hundreds of variables and constraints, making it suitable for autonomous calculations.

Pairwise comparisons are used in a wide variety of decision situations where the importance of alternatives should be measured on a numerical scale. One popular method to derive the priorities is based on the right eigenvector of a multiplicative pairwise comparison matrix. We consider two monotonicity axioms in this setting. First, increasing an arbitrary entry of a pairwise comparison matrix is not allowed to result in a counter-intuitive rank reversal, that is, the favoured alternative in the corresponding row cannot be ranked lower than any other alternative if this was not the case before the change (rank monotonicity). Second, the same modification should not decrease the normalised weight of the favoured alternative (weight monotonicity). Both properties are satisfied by the geometric mean method but violated by the eigenvector method. The axioms do not uniquely determine the geometric mean. The relationship between the two monotonicity properties and the Saaty inconsistency index are investigated for the eigenvector method via simulations. Even though their violation turns out not to be a usual problem even for heavily inconsistent matrices, all decision-makers should be informed about the possible occurrence of such unexpected consequences of increasing a matrix entry., Comment: 16 pages, 2 figures, 2 tables

We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results., Comment: Restructuring (focus on representative families instead of facility location), slight running time improvements, algorithms factored out

In this paper, we solve a separation of singularities problem in the Bergman space. More precisely, we show that if $P\subset \mathbb{C}$ is a convex polygon which is the intersection of $n$ half planes, then the Bergman space on $P$ decomposes into the sum of the Bergman spaces on these half planes. The result applies to the characterization of the reachable space of the one-dimensional heat equation on a finite interval with boundary controls. We prove that this space is a Bergman space of the square which has the given interval as a diagonal. This gives an affirmative answer to a conjecture raised in [HKT20]., Comment: Journal de Math{\'e}matiques Pures et Appliqu{\'e}es, Elsevier, 2021

Strategic customer behavior is strongly influenced by the level of information that is provided to customers. Hence, to optimize the design of queueing systems, many studies consider various versions of the same service model and compare them under different information structures. In particular, two extreme versions are usually considered and compared: the observable in which customers are informed about the number of customers in the system and the unobservable in which they are only informed about the system parameters, e.g., arrival and service rates. In the present work, we study a model that bridges these two versions. More concretely, we assume that the system alternates between observable and unobservable periods. We characterize and compute customer equilibrium joining/balking strategies and show that the present model unifies and extends existing approaches of both heterogeneously observable models and models with delayed observations. More importantly, our findings indicate that an alternating information structure implies in general higher equilibrium throughput and social welfare in comparison to both the observable and unobservable cases. We complement our results with numerical experiments and provide managerial insight on the optimal control of the system parameters.

Decision rules offer a rich and tractable framework for solving certain classes of multistage adaptive optimization problems. Recent literature has shown the promise of using linear and nonlinear decision rules in which wait-and-see decisions are represented as functions, whose parameters are decision variables to be optimized, of the underlying uncertain parameters. Despite this growing success, solving real-world stochastic optimization problems can become computationally prohibitive when using nonlinear decision rules, and in some cases, linear ones. Consequently, decision rules that offer a competitive trade-off between solution quality and computational time become more attractive. Whereas the extant research has always used homogeneous (i.e., either linear or piecewise-linear) decision rules, the major contribution of this paper is a computational exploration of hybrid decision rules combining the benefits of the two classes of decision rules. We first verify empirically that having higher uncertainty resolution or more linear pieces in early stages is more significant than having it in late stages in terms of solution quality. Then, we compare non-increasing and non-decreasing (i.e., higher uncertainty resolution in early and late stages, respectively) hybrid decision rules in a computational study to illustrate the trade-off between solution quality and computational cost. We also demonstrate a case where, unexpectedly, a linear decision rule is superior to a more complex piecewise-linear decision rule within a simulator. This observation bolsters the need to assess the quality of decision rules obtained from a look-ahead model within a simulator rather than just using the optimal look-ahead objective function value.

StochAstic Recursive grAdient algoritHm (SARAH), originally proposed for convex optimization and also proven to be effective for general nonconvex optimization, has received great attention because of its simple recursive framework for updating stochastic gradient estimates. The performance of SARAH significantly depends on the choice of the step size sequence. However, SARAH and its variants often manually select a best-tuned step size, which is time consuming in practice. Motivated by this gap, we propose a variant of the Barzilai-Borwein (BB) method, referred to as the Random Barzilai-Borwein (RBB) method, to determine the step size for SARAH in the mini-batch setting, leading to a new SARAH method: MB-SARAH-RBB. We prove that MB-SARAH-RBB converges linearly in expectation for strongly convex objective functions. Moreover, we analyze the gradient complexity of MB-SARAH-RBB and show that it is better than the original method. To further confirm the efficacy of the RBB method, we propose the MB-SARAH+-RBB method, by incorporating it into the MB-SARAH + method. Numerical experiments on standard data sets indicate that our proposed methods outperform or match state-of-the-art algorithms.

We establish sufficient conditions for finite convergence of the alternating projections method for two non-intersecting and potentially nonconvex sets. Our results are based on a generalization of the concept of intrinsic transversality, which until now has been restricted to sets with nonempty intersection. In the special case of a polyhedron and closed half space, our sufficient conditions define the minimum distance between the two sets that is required for alternating projections to converge in a single iteration., 9 pages, 7 figures

Linear programs (LPs) can be solved by polynomially many moves along the circuit direction improving the objective the most, so-called deepest-descent steps (dd-steps). Computing these steps is NP-hard (De Loera et al. (2019)), a consequence of the hardness of deciding the existence of an optimal circuit-neighbor (OCNP) on LPs with non-unique optima. We prove OCNP is easy under the promise of unique optima, but already O ( n 1 − e ) -approximating dd-steps remains hard even for totally unimodular n -dimensional 0/1-LPs with a unique optimum. We provide a matching n -approximation.

The Douglas–Rachford algorithm can be represented as the fixed point iteration of a firmly nonexpansive operator. When the operator has no fixed points, the algorithm's iterates diverge, but the difference between consecutive iterates converges to the so-called minimal displacement vector, which can be used to certify infeasibility of an optimization problem. In this paper, we establish new properties of the minimal displacement vector, which allow us to generalize some existing results. © 2021 The Author(s), Operations Research Letters, 49 (2), ISSN:0167-6377, ISSN:1872-7468

The design of nature reserves is becoming, more and more, a crucial task for ensuring the conservation of endangered wildlife. In order to guarantee the preservation of species and a general ecological functioning, the designed reserves must typically verify a series of spatial requirements. Among the required characteristics, practitioners and researchers have pointed out two crucial aspects: (i) connectivity, so as to avoid spatial fragmentation, and (ii) the design of buffer zones surrounding (or protecting) so-called core areas. In this paper, we introduce the Generalized Reserve Set Covering Problem with Connectivity and Buffer Requirements. This problem extends the classical Reserve Set Covering Problem and allows to address these two requirements simultaneously. A solution framework based on Integer Linear Programming and branch-and-cut is developed. The framework is enhanced by valid inequalities, a construction and a primal heuristic and local branching. An extensive computational study on grid-graph instances and real-life instances based on data from three states of the U.S. and one region of Australia is carried out to assess the suitability of the proposed model to deal with the challenges faced by decision-makers in natural reserve design. The results show, on the one hand, the flexibility of the proposed models to provide solutions according to the decision-makers' requirements, and on the other hand, the effectiveness of the devised algorithm for providing' good solutions in reasonable computing times., Comment: Accepted for publication in European Journal of Operational Research; doi: 10.1016/j.ejor.2019.07.017

3D image registration is one of the most fundamental and computationally expensive operations in medical image analysis. Here, we present a mixed-precision, Gauss--Newton--Krylov solver for diffeomorphic registration of two images. Our work extends the publicly available CLAIRE library to GPU architectures. Despite the importance of image registration, only a few implementations of large deformation diffeomorphic registration packages support GPUs. Our contributions are new algorithms to significantly reduce the run time of the two main computational kernels in CLAIRE: calculation of derivatives and scattered-data interpolation. We deploy (i) highly-optimized, mixed-precision GPU-kernels for the evaluation of scattered-data interpolation, (ii) replace Fast-Fourier-Transform (FFT)-based first-order derivatives with optimized 8th-order finite differences, and (iii) compare with state-of-the-art CPU and GPU implementations. As a highlight, we demonstrate that we can register $256^3$ clinical images in less than 6 seconds on a single NVIDIA Tesla V100. This amounts to over 20$\times$ speed-up over the current version of CLAIRE and over 30$\times$ speed-up over existing GPU implementations., 20 pages, 6 figures, 8 tables

We consider the problem of optimizing locations of distribution centers (DCs) and plans for distributing resources such as test kits and vaccines, under spatiotemporal uncertainties of disease spread and demand for the resources. We aim to balance the operational cost (including costs of deploying facilities, shipping, and storage) and quality of service (reflected by demand coverage), while ensuring equity and fairness of resource distribution across multiple populations. We compare a sample-based stochastic programming (SP) approach with a distributionally robust optimization (DRO) approach using a moment-based ambiguity set. Numerical studies are conducted on instances of distributing COVID-19 vaccines in the United States and test kits, to compare SP and DRO models with a deterministic formulation using estimated demand and with the current resource distribution plans implemented in the US. We demonstrate the results over distinct phases of the pandemic to estimate the cost and speed of resource distribution depending on scale and coverage, and show the ``demand-driven'' properties of the SP and DRO solutions. Our results further indicate that if the worst-case unmet demand is prioritized, then the DRO approach is preferred despite of its higher overall cost. Nevertheless, the SP approach can provide an intermediate plan under budgetary restrictions without significant compromises in demand coverage.

It is well-known that the controllability of finite-dimensional nonlinear systems can be established by showing the controllability of the linearized system. However, this classical result does not generalize to infinite-dimensional nonlinear systems. In this paper, we restrict ourselves to semilinear infinite-dimensional systems, and show that the exact controllability of the linearized system implies exact controllability of the nonlinear system. The restrictions concerning the nonlinear operator are similar to those that can be found in the literature about the linearized stability analysis of semilinear systems., accepted as full paper for MTNS 2020

We consider minimization problems with bisubmodular objective functions. We propose valid inequalities, namely the poly-bimatroid inequalities, and provide a complete linear description of the convex hull of the epigraph of a bisubmodular function. Furthermore, we develop a cutting plane algorithm for constrained bisubmodular minimization based on the poly-bimatroid inequalities. Our computational experiments on the minimization subproblem in robust coupled sensor placement show that our algorithm can solve highly non-linear problems that do not admit compact mixed-integer linear formulations.

Evolutionary algorithms (EAs) have found many successful real-world applications, where the optimization problems are often subject to a wide range of uncertainties. To understand the practical behaviors of EAs theoretically, there are a series of efforts devoted to analyzing the running time of EAs for optimization under uncertainties. Existing studies mainly focus on noisy and dynamic optimization, while another common type of uncertain optimization, i.e., robust optimization, has been rarely touched. In this paper, we analyze the expected running time of the (1+1)-EA solving robust linear optimization problems (i.e., linear problems under robust scenarios) with a cardinality constraint $k$. Two common robust scenarios, i.e., deletion-robust and worst-case, are considered. Particularly, we derive tight ranges of the robust parameter $d$ or budget $k$ allowing the (1+1)-EA to find an optimal solution in polynomial running time, which disclose the potential of EAs for robust optimization., Comment: 17 pages, 1 table

We consider a zero-sum stochastic game for continuous-time Markov chain with countable state space and unbounded transition and pay-off rates. The additional feature of the game is that the controllers together with taking actions are also allowed to stop the process. Under suitable hypothesis we show that the game has a value and it is the unique solution of certain dynamic programming inequalities with bilateral constraints. In the process we also prescribe a saddle point equilibrium.

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., Journal of Parallel and Distributed Computing, 144, ISSN:0743-7315, ISSN:1096-0848

We investigate conditions for the unique recoverability of sparse integer-valued signals from a small number of linear measurements. Both the objective of minimizing the number of nonzero components, the so-called l 0 -norm, as well as its popular substitute, the l 1 -norm, are covered. Furthermore, integrality constraints and possible bounds on the variables are investigated. Our results show that the additional prior knowledge of signal integrality allows for recovering more signals than what can be guaranteed by the established recovery conditions from (continuous) compressed sensing. Moreover, even though the considered problems are NP -hard in general (even with an l 1 -objective), we investigate testing the l 0 -recovery conditions via some numerical experiments. It turns out that the corresponding problems are quite hard to solve in practice using black-box software. However, medium-sized instances of l 0 - and l 1 -minimization with binary variables can be solved exactly within reasonable time.

This paper proposes a fractional order gradient method for the backward propagation of convolutional neural networks. To overcome the problem that fractional order gradient method cannot converge to real extreme point, a simplified fractional order gradient method is designed based on Caputo’s definition. The parameters within layers are updated by the designed gradient method, but the propagations between layers still use integer order gradients, and thus the complicated derivatives of composite functions are avoided and the chain rule will be kept. By connecting every layers in series and adding loss functions, the proposed convolutional neural networks can be trained smoothly according to various tasks. Some practical experiments are carried out in order to demonstrate fast convergence, high accuracy and ability to escape local optimal point at last.

Equipping a spacecraft with multiple solar-powered electric engines (of the same or different types) compounds the task of optimal trajectory design due to presence of both real-valued inputs (power input to each engine in addition to the direction of thrust vector) and discrete variables (number of active engines). Each engine can be switched on/off independently and "optimal" operating power of each engine depends on the available solar power, which depends on the distance from the Sun. Application of the Composite Smooth Control (CSC) framework to a heliocentric fuel-optimal trajectory optimization from the Earth to the comet 67P/Churyumov-Gerasimenko is demonstrated, which presents a new approach to deal with multiple-engine problems. Operation of engine clusters with 4, 6, 10 and even 20 engines of the same type can be optimized. Moreover, engine clusters with different/mixed electric engines are considered with either 2, 3 or 4 different types of engines. Remarkably, the CSC framework allows us 1) to reduce the original multi-point boundary-value problem to a two-point boundary-value problem (TPBVP), and 2) to solve the resulting TPBVPs using a single-shooting solution scheme and with a random initialization of the missing costates. While the approach we present is a continuous neighbor of the discontinuous extremals, we show that the discontinuous necessary conditions are satisfied in the asymptotic limit. We believe this is the first indirect method to accommodate a multi-mode control of this level of complexity with realistic engine performance curves. The results are interesting and promising for dealing with a large family of such challenging multi-mode optimal control problems., Comment: 45 pages, 11 figures; Preprint submitted to Acta Astronautica

Efficient performance of a number of engineering systems is achieved through different modes of operation - yielding systems described as "hybrid", containing both real-valued and discrete decision variables. Prominent examples of such systems, in space applications, could be spacecraft equipped with 1) a variable-$I_{\text{sp}}$, variable-thrust engine or 2) multiple engines each capable of switching on/off independently. To alleviate the challenges that arise when an indirect optimization method is used, a new framework --- Composite Smooth Control (CSC) --- is proposed that seeks smoothness over the entire spectrum of distinct control inputs. A salient aftermath of the application of the CSC framework is that the original multi-point boundary-value problem can be treated as a two-point boundary-value problem with smooth, differentiable control inputs; the latter is notably easier to solve, yet can be made to accurately approximate the former hybrid problem. The utility of the CSC framework is demonstrated through a multi-year, multi-revolution heliocentric fuel-optimal trajectory for a spacecraft equipped with a variable-$I_{\text{sp}}$, variable-thrust engine., Comment: 51 pages, 9 figures; pre-print submitted to Acta Astronautica

Harry hides on an edge of a graph and does not move from there. Sally, starting from a known origin, tries to find him as soon as she can. Harry's goal is to be found as late as possible. At any given time, each edge of the graph is either active or inactive, independently of the other edges, with a known probability of being active. This situation can be modeled as a zero-sum two-person stochastic game. We show that the game has a value and we provide upper and lower bounds for this value. Finally, by generalizing optimal strategies of the deterministic case, we provide more refined results for trees and Eulerian graphs., 28 pages, 9 figures

Constrained quasiconvex optimization problems appear in many fields, such as economics, engineering, and management science. In particular, fractional programming, which models ratio indicators such as the profit/cost ratio as fractional objective functions, is an important instance. Subgradient methods and their variants are useful ways for solving these problems efficiently. Many complicated constraint sets onto which it is hard to compute the metric projections in a realistic amount of time appear in these applications. This implies that the existing methods cannot be applied to quasiconvex optimization over a complicated set. Meanwhile, thanks to fixed point theory, we can construct a computable nonexpansive mapping whose fixed point set coincides with a complicated constraint set. This paper proposes an algorithm that uses a computable nonexpansive mapping for solving a constrained quasiconvex optimization problem. We provide convergence analyses for constant diminishing step-size rules. Numerical comparisons between the proposed algorithm and an existing algorithm show that the proposed algorithm runs stably and quickly even when the running time of the existing algorithm exceeds the time limit.

Connected and automated vehicles (CAVs) offer huge potential to improve the performance of automated vehicles (AVs) without communication capabilities, especially in situations when the vehicles (or agents) need to be cooperative to accomplish their maneuver. Lane change maneuvers in dense traffic, e.g., are very challenging for non-connected AVs. To alleviate this problem, we propose a holistic distributed lane change control scheme for CAVs which relies on vehicle-to-vehicle communication. The originally centralized optimal control problem is embedded into a consensus-based Alternating Direction Method of Multipliers framework to solve it in a distributed receding horizon fashion. Although agent dynamics render the underlying optimal control problem nonconvex, we propose a problem reformulation that allows to derive convergence guarantees. In the distributed setting, every agent needs to solve a nonlinear program (NLP) locally. To obtain a real-time solution of the local NLPs, we utilize the optimization engine OpEn which implements the proximal averaged Newton method for optimal control (PANOC). Simulation results prove the efficacy and real-time capability of our approach., Comment: Accepted for IFAC World Congress 2020 (published version)

This contribution presents a backstepping-based state feedback design for the tracking control of a two-phase Stefan problem which is encountered in the Vertical Gradient Freeze crystal growth process. A two-phase Stefan problem consists of two coupled free boundary problems and is a vital part of many crystal growth processes due to the time-varying extent of crystal and melt during growth. In addition, a different approach for the numerical approximation of the backstepping transformations kernel is presented., Comment: 7 pages, 4 figures. Accepted to the 21st IFAC World Congress

We present a numeric method to compute the safe operating flight conditions for a helicopter such that we can ensure a safe landing in the event of a partial or total engine failure. The unsafe operating region is the complement of the backwards reachable tube, which can be found as the sub-zero level set of the viscosity solution of a Hamilton-Jacobi (HJ) equation. Traditionally, numerical methods used to solve the HJ equation rely on a discrete grid of the solution space and exhibit exponential scaling with dimension, which is problematic for the high-fidelity dynamics models required for accurate helicopter modeling. We avoid the use of spatial grids by formulating a trajectory optimization problem, where the solution at each initial condition can be computed in a computationally efficient manner. The proposed method is shown to compute an autonomous landing trajectory from any operating condition, even in non-cruise flight conditions., Accepted for publication in the proceedings of the 2020 IFAC World Congress

This paper considers the optimal multi-agent persistent monitoring problem defined for a team of agents on a set of nodes (targets) interconnected according to a fixed network topology. The aim is to control this team so as to minimize a measure of overall node state uncertainty evaluated over a finite time interval. A class of distributed threshold-based parametric controllers has been proposed in prior work to control agent dwell times at nodes and next-node destinations by enforcing thresholds on the respective node states. Under such a Threshold Control Policy (TCP), an on-line gradient technique was used to determine optimal threshold values. However, due to the non-convexity of the problem, this approach often leads to a poor local optima highly dependent on the initial thresholds used. To overcome this initialization challenge, we develop a computationally efficient off-line greedy technique based on the asymptotic analysis of the network system. This analysis is then used to generate a high-performing set of initial thresholds. Extensive numerical results show that such initial thresholds are almost immediately (locally) optimal or quickly lead to optimal values. In all cases, they perform significantly better than the locally optimal solutions known to date., Submitted to Automatica

This article focuses on the optimization of a complex system which is composed of several subsystems. On the one hand, these subsystems are subject to multiple objectives, local constraints as well as local variables, and they are associated with an own, subsystem-dependent decision maker. On the other hand, these subsystems are interconnected to each other by global variables or linking constraints. Due to these interdependencies, it is in general not possible to simply optimize each subsystem individually to improve the performance of the overall system. This article introduces a formal graph-based representation of such complex systems and generalizes the classical notions of feasibility and optimality to match this complex situation. Moreover, several algorithmic approaches are suggested and analyzed.

Fuel consumption of heavy-duty vehicles such as tractors, bulldozers etc. is comparably high due to their scope of operation. The operation settings are usually fixed and not tuned to the environmental factors, such as ground conditions. Yet exactly the ground-to-propelling-unit properties are decisive in energy efficiency. Optimizing the latter would require a means of identifying those properties. This is the central matter of the current study. More specifically, the goal is to estimate the ground conditions from the available measurements, such as drive train signals, and to establish a map of those. The ground condition parameters are estimated using an adaptive unscented Kalman filter. A case study is provided with the actual and estimated ground condition maps. Such a mapping can be seen as a crucial milestone in optimal operation control of heavy-duty vehicles., Comment: Accepted for publication at the IFAC WC 2020

We propose a distributed algorithm to compute an equilibrium in aggregate games where players communicate over a fixed undirected network. Our algorithm exploits correlated perturbation to obfuscate information shared over the network. We prove that our algorithm does not reveal private information of players to an honest-but-curious adversary who monitors several nodes in the network. In contrast with differential privacy based algorithms, our method does not sacrifice accuracy of equilibrium computation to provide privacy guarantees.

Behind the concept of Industry 4.0, there are a number of principles and ideas; one of them is the integration of problems of different decision levels. In this work, we integrate maintenance with planning problems, aiming to take full advantage of the production capacity providing immediate delivery of products to customers and avoiding failures. We propose a hybrid approach for solving a maintenance problem integrated with the lot-sizing and scheduling problems. The approach is based on the concepts of robustness and simheuristics, considering preventive, predictive and corrective maintenances in a parallel machine environment. Simulations are performed to consider machine failures. Results indicate that as we increase the robustness parameter at the lot-sizing problem, we obtain lower deviations related to the initial objective function of the lot-sizing problem and lower probabilities of infeasibility after the occurrence of failures. The approach makes it possible to find an average expected result for each of the scenarios analyzed taking into account historical data on the behavior of the failures., 7 pages, 4th IFAC Workshop on Advanced Maintenance Engineering, Services and Technologies

In this paper we show that a convexifiability property of nonconvex quadratic programs with nonnegative variables and quadratic constraints guarantees zero duality gap between the quadratic programs and their semi-Lagrangian duals. More importantly, we establish that this convexifiability is hidden in classes of nonnegative homogeneous quadratic programs and discrete quadratic programs, such as mixed integer quadratic programs, revealing zero duality gaps. As an application, we prove that robust counterparts of uncertain mixed integer quadratic programs with objective data uncertainty enjoy zero duality gaps under suitable conditions. Various sufficient conditions for convexifiability are also given.

This paper presents an optimization-based receding horizon trajectory planning algorithm for dynamical systems operating in unstructured and cluttered environments. The proposed approach is a two-step procedure that uses a motion planning algorithm in a first step to efficiently find a feasible, but possibly suboptimal, nominal solution to the trajectory planning problem where in particular the combinatorial aspects of the problem are solved. The resulting nominal trajectory is then improved in a second optimization-based receding horizon planning step which performs local trajectory refinement over a sliding time window. In the second step, the nominal trajectory is used in a novel way to both represent a terminal manifold and obtain an upper bound on the cost-to-go online. This enables the possibility to provide theoretical guarantees in terms of recursive feasibility, objective function value, and convergence to the desired terminal state. The established theoretical guarantees and the performance of the proposed algorithm are verified in a set of challenging trajectory planning scenarios for a truck and trailer system., Comment: Submitted for IFAC World Congress 2020

In this paper, we propose a new method based on the Sliding Algorithm from Lan(2016, 2019) for the convex composite optimization problem that includes two terms: smooth one and non-smooth one. Our method uses the stochastic noised zeroth-order oracle for the non-smooth part and the first-order oracle for the smooth part. To the best of our knowledge, this is the first method in the literature that uses such a mixed oracle for the composite optimization. We prove the convergence rate for the new method that matches the corresponding rate for the first-order method up to a factor proportional to the dimension of the space or, in some cases, its squared logarithm. We apply this method for the decentralized distributed optimization and derive upper bounds for the number of communication rounds for this method that matches known lower bounds. Moreover, our bound for the number of zeroth-order oracle calls per node matches the similar state-of-the-art bound for the first-order decentralized distributed optimization up to to the factor proportional to the dimension of the space or, in some cases, even its squared logarithm.

In this paper we present a data-driven approach for uncertainty propagation. In particular, we consider stochastic differential equations with parametric uncertainty. Solution of the differential equation is approximated using maximum entropy (maxent) basis functions similar to polynomial chaos expansions. Maxent basis functions are derived from available data by maximization of information-theoretic entropy, therefore, there is no need to specify basis functions beforehand. We compare the proposed maxent based approach with existing methods.

The problem of navigating a formation of interconnected tethered drones, named STEM (System of TEthered Multicopters), in an unknown environment is considered. The tethers feed electrical power from a ground station to the drones and also serve as communication links. The presence of more than one interconnected drone provides enough degrees of freedom to navigate in a cluttered area. The leader drone in the formation must reach a given point of interest, while the followers must move accordingly, avoiding interference with the obstacles. The challenges are the uncertainty in the environment, with obstacles of unknown shape and position, the use of LiDAR (Light Detection And Ranging) sensors, providing only partial information of the surroundings of each drone, and the presence of the tethers, which must not impact with the obstacles and pose additional constraints to how the drones can move. To cope with these problems, a novel real-time planning algorithm based on numerical optimization is proposed: the reference position of each drone is chosen in a centralized way via a convex program, where the LiDAR scans are used to approximate the free space and the drones are moved towards suitably defined intermediate goals in order to eventually reach the point of interest. The approach is successfully tested in numerical simulations with a realistic model of the system.

Recently, the problem of boundary stabilization and estimation for unstable linear constant-coefficient reaction-diffusion equation on n-balls (in particular, disks and spheres) has been solved by means of the backstepping method. However, the extension of this result to spatially-varying coefficients is far from trivial. Some early success has been achieved under simplifying conditions, such as radially-varying reaction coefficients under revolution symmetry, on a disk or a sphere. These particular cases notwithstanding, the problem remains open. The main issue is that the equations become singular in the radius; when applying the backstepping method, the same type of singularity appears in the kernel equations. Traditionally, well-posedness of these equations has been proved by transforming them into integral equations and then applying the method of successive approximations. In this case, with the resulting integral equation becoming singular, successive approximations do not easily apply. This paper takes a different route and directly addresses the kernel equations via a power series approach, finding in the process the required conditions for the radially-varying reaction (namely, analyticity and evenness) and showing the existence and convergence of the series solution. This approach provides a direct numerical method that can be readily applied, despite singularities, to both control and observer boundary design problems., Comment: Preprint submitted to Systems and Control Letters

In this work, we propose a non-parametric technique for online modeling of systems with unknown nonlinear Lipschitz dynamics. The key idea is to successively utilize measurements to approximate the graph of the state-update function using envelopes described by quadratic constraints. The proposed approach is then demonstrated on two control applications: (i) computation of tractable bounds for unmodeled dynamics, and (ii) computation of positive invariant sets. We further highlight the efficacy of the proposed approach via a detailed numerical example.

While research in robust optimization has attracted considerable interest over the last decades, its algorithmic development has been hindered by several factors. One of them is a missing set of benchmark instances that make algorithm performance better comparable, and makes reproducing instances unnecessary. Such a benchmark set should contain hard instances in particular, but so far, the standard approach to produce instances has been to sample values randomly from a uniform distribution. In this paper we introduce a new method to produce hard instances for min-max combinatorial optimization problems, which is based on an optimization model itself. Our approach does not make any assumptions on the problem structure and can thus be applied to any combinatorial problem. Using the Selection and Traveling Salesman problems as examples, we show that it is possible to produce instances which are up to 500 times harder to solve for a mixed-integer programming solver than the current state-of-the-art instances.

With the gradual transformation of power generation towards renewables, distributed energy resources are becoming more and more relevant for grid stabilization. In order to involve all participants in the joint solution of this challenging task, we propose a distributed, model-based and unifying controller for frequency and voltage regulation in AC microgrids, based on steady-state optimal control. It not only unifies frequency and voltage control, but also incorporates the classic hierarchy of primary, secondary and tertiary control layers with each closed-loop equilibrium being a minimizer of a user-defined cost function. By considering the individual voltage limits as additional constraints in the corresponding optimization problem, no superordinate specification of voltage setpoints is required. Since the dynamic model of the microgrid has a port-Hamiltonian structure, stability of the overall system can be assessed using shifted passivity properties. Furthermore, we demonstrate the effectiveness of the controller and its robustness against fluctuations in active and reactive power demand by means of numerical examples.

This paper addresses a learning problem for nonlinear dynamical systems with incorporating any specified dissipativity property. The nonlinear systems are described by the Koopman operator, which is a linear operator defined on the infinite-dimensional lifted state space. The problem of learning the Koopman operator under specified quadratic dissipativity constraints is formulated and addressed. The learning problem is in a class of the non-convex optimization problem due to nonlinear constraints and is numerically intractable. By applying the change of variable technique and the convex overbounding approximation, the problem is reduced to sequential convex optimization and is solved in a numerically efficient manner. Finally, a numerical simulation is given, where high modeling accuracy achieved by the proposed approach including the specified dissipativity is demonstrated.