Optimization and Control (math.OC)

Abstract: We study the extended version of the non-uniform, capacitated facility location problem with multiple fulfilment channels between the facilities and clients, each with their own channel capacities and service cost. Though the problem has been extensively studied in the literature, all the prior works assume a single channel of fulfilment, and the existing methods based on linear programming, primal-dual relationships, local search heuristics etc. do not scale for a large supply chain system involving millions of decision variables. Using the concepts of sub-modularity and optimal transport theory, we present a scalable algorithm for determining the set of facilities to be opened under a cardinality constraint. By introducing various schemes such as: (i) iterative facility selection using incremental gain, (ii) approximation of the linear program using novel multi-stage Sinkhorn iterations, (iii) creation of facilities one for each fulfilment channel etc., we develop a fast but a tight approximate solution, requiring $\mathcal{O}\left(\frac{3+k}{m}ln\left(\frac{1}{\epsilon}\right)\right)$ instances of optimal transport problems to select k facilities from m options, each solvable in linear time. Our algorithm is implicitly endowed with all the theoretical guarantees enjoyed by submodular maximisation problems and the Sinkhorn distances. When compared against the state-of-the-art commercial MILP solvers, we obtain a 100-fold speedup in computation, while the difference in objective values lies within a narrow range of 3%.

Abstract: This paper studies a Merton's optimal portfolio and consumption problem in an extended formulation incorporating the tracking of a benchmark process described by a geometric Brownian motion. We consider a relaxed tracking formulation such that that the wealth process compensated by a fictitious capital injection outperforms the external benchmark at all times. The fund manager aims to maximize the expected utility of consumption deducted by the cost of the capital injection, where the latter term can also be regarded as the expected largest shortfall with reference to the benchmark. By introducing an auxiliary state process with reflection, we formulate and tackle an equivalent stochastic control problem by means of the dual transform and probabilistic representation, where the dual PDE can be solved explicitly. On the strength of the closed-form results, we can derive and verify the feedback optimal control in the semi-analytical form for the primal control problem, allowing us to observe and discuss some new and interesting financial implications on portfolio and consumption decision making induced by the additional risk-taking in capital injection and the goal of tracking.

Abstract: The article proposes an exact approach to find the global solution of a nonconvex semivectorial bilevel optimization problem, where the objective functions at each level are pseudoconvex, and the constraints are quasiconvex. Due to its non-convexity, this problem is challenging, but it attracts more and more interest because of its practical applications. The algorithm is developed based on monotonic optimization combined with a recent neurodynamic approach, where the solution set of the lower-level problem is inner approximated by copolyblocks in outcome space. From that, the upper-level problem is solved using the branch-and-bound method. Finding the bounds is converted to pseudoconvex programming problems, which are solved using the neurodynamic method. The algorithm's convergence is proved, and computational experiments are implemented to demonstrate the accuracy of the proposed approach.

Abstract: Microgrids are autonomous clusters of generators, storage units and loads. Special requirements arise in interconnected operation: control schemes that do not require individual microgrids to disclose data about their internal structure and operating objectives are preferred for privacy reasons. Moreover, a safe and economically meaningful operation shall be achieved in presence of uncertain load and weather-dependent availability of renewable infeed. In this paper, we propose a distributed model predictive control approach that satisfies these requirements. Specifically, we demonstrate that costs and safety of supply can be improved through a scenario-based stochastic control scheme. In a numerical case study, our approach is compared to a certainty equivalence scheme. The results illustrate the improved safety and reduced runtime costs as well as sufficiently fast convergence.

Abstract: Minimax optimization plays an important role in many machine learning tasks such as generative adversarial networks (GANs) and adversarial training. Although recently a wide variety of optimization methods have been proposed to solve the minimax problems, most of them ignore the distributed setting where the data is distributed on multiple workers. Meanwhile, the existing decentralized minimax optimization methods rely on the strictly assumptions such as (strongly) concavity and variational inequality conditions. In the paper, thus, we propose an efficient decentralized momentum-based gradient descent ascent (DM-GDA) method for the distributed nonconvex-PL minimax optimization, which is nonconvex in primal variable and is nonconcave in dual variable and satisfies the Polyak-Lojasiewicz (PL) condition. In particular, our DM-GDA method simultaneously uses the momentum-based techniques to update variables and estimate the stochastic gradients. Moreover, we provide a solid convergence analysis for our DM-GDA method, and prove that it obtains a near-optimal gradient complexity of $O(\epsilon^{-3})$ for finding an $\epsilon$-stationary solution of the nonconvex-PL stochastic minimax problems, which reaches the lower bound of nonconvex stochastic optimization. To the best of our knowledge, we first study the decentralized algorithm for Nonconvex-PL stochastic minimax optimization over a network.

Abstract: This study addresses a distributed optimization with a novel class of coupling of variables, called clique-wise coupling. A clique is a node set of a complete subgraph of an undirected graph. This setup is an extension of pairwise coupled optimization problems (e.g., consensus optimization) and allows us to handle coupling of variables consisting of more than two agents systematically. To solve this problem, we propose a clique-based linearized ADMM algorithm, which is proved to be distributed. Additionally, we consider objective functions given as a sum of nonsmooth and smooth convex functions and present a more flexible algorithm based on the FLiP-ADMM algorithm. Moreover, we provide convergence theorems of these algorithms. Notably, all the algorithmic parameters and the derived condition in the theorems depend only on local information, which means that each agent can choose the parameters in a distributed manner. Finally, we apply the proposed methods to a consensus optimization problem and demonstrate their effectiveness via numerical experiments.

Abstract: Recently, a two component MPC scheme was introduced, consisting of pure feedback control (funnel control) and model-based predictive control (funnel MPC). It achieves output tracking of a given reference signal with prescribed performance of the tracking error for a class of unknown nonlinear systems. Relying on the feedback controller's ability to compensate for tracking errors even in the presence of noise and uncertainties, this control structure is robust with respect to model-plant mismatches and bounded disturbances. In the present article, we extend this control structure by a learning component in order to adapt the underlying model to the system data and hence to improve the contribution of MPC. Since the combined control scheme robust funnel MPC is inherently robust with respect to model-plant mismatches and the evolution of the tracking error in the prescribed performance funnel is always guaranteed, the additional learning component is able to perform the learning task online without an initial model or offline training.

Abstract: In this work, we consider a mechanical system whose mass tensor implements a scalar product in a Riemannian manifold. This system is controlled with the help of forces and torques. A cost functional is minimized to achieve an optimal trajectory. In this contribution, this cost function is supposed to be an arbitrary regular function invariant under a change of coordinates. Optimal control evolution based on Pontryagin's principle induces a covariant second-order ordinary differential equation for an adjoint variable featuring the Riemann curvature tensor. This second order time evolution is derived in this contribution.

Abstract: To ensure the system stability of the $\bf{\mathcal{H}_{2}}$-guaranteed cost optimal decentralized control problem (ODC), an approximate semidefinite programming (SDP) problem is formulated based on the sparsity of the gain matrix of the decentralized controller. To reduce data storage and improve computational efficiency, the SDP problem is vectorized into a conic programming (CP) problem using the Kronecker product. Then, a proximal alternating direction method of multipliers (PADMM) is proposed to solve the dual of the resulted CP. By linking the (generalized) PADMM with the (relaxed) proximal point algorithm, we are able to accelerate the proposed PADMM via the Halpern fixed-point iterative scheme. This results in a fast convergence rate for the Karush-Kuhn-Tucker (KKT) residual along the sequence generated by the accelerated algorithm. Numerical experiments further demonstrate that the accelerated PADMM outperforms both the well-known CVXOPT and SCS algorithms for solving the large-scale CP problems arising from $\bf{\mathcal{H}_{2}}$-guaranteed cost ODC problems.

Abstract: This paper is concerned with the well-posedness and optimal control problem of a reaction-diffusion system for an epidemic Susceptible-Infected-Recovered-Susceptible (SIRS) mathematical model in which the dynamics develops in a spatially heterogeneous environment. Using as control variables the transmission rates $u_{i}$ and $u_{e}$ of contagion resulting from the contact with both asymptomatic and symptomatic persons, respectively, we optimize the number of exposed and infected individuals at a final time $T$ of the controlled evolution of the system. More precisely, we search for the optimal $u_{i}$ and $u_{e}$ such that the number of infected plus exposed does not exceed at the final time a threshold value $\Lambda$, fixed a priori. We prove here the existence of optimal controls in a proper functional framework and we derive the first-order necessary optimality conditions in terms of the adjoint variables.

Abstract: This expository article presents an overview of research, conducted mostly between the mid-1990s and late 2000s, that explores a link between commutation relations among a family of asymptotically stable vector fields and stability properties of the switched system that these vector fields generate. This topic is viewed through the lens of the author's own involvement with it, by interspersing explanations of technical developments with personal reminiscences and anecdotes.