Optimization and Control (math.OC)
Mon, 12 Jun 2023
1.Convergence Rates of the Regularized Optimal Transport : Disentangling Suboptimality and Entropy
Authors:Hugo Malamut CEREMADE, Maxime Sylvestre CEREMADE
Abstract: We study the convergence of the transport plans $\gamma$$\epsilon$ towards $\gamma$0 as well as the cost of the entropy-regularized optimal transport (c, $\gamma$$\epsilon$) towards (c, $\gamma$0) as the regularization parameter $\epsilon$ vanishes in the setting of finite entropy marginals. We show that under the assumption of infinitesimally twisted cost and compactly supported marginals the distance W2($\gamma$$\epsilon$, $\gamma$0) is asymptotically greater than C $\sqrt$ $\epsilon$ and the suboptimality (c, $\gamma$$\epsilon$) -- (c, $\gamma$0) is of order $\epsilon$. In the quadratic cost case the compactness assumption is relaxed into a moment of order 2 + $\delta$ assumption. Moreover, in the case of a Lipschitz transport map for the non-regularized problem, the distance W2($\gamma$$\epsilon$, $\gamma$0) converges to 0 at rate $\sqrt$ $\epsilon$. Finally, if in addition the marginals have finite Fisher information, we prove (c, $\gamma$$\epsilon$) -- (c, $\gamma$0) $\sim$ d$\epsilon$/2 and we provide a companion expansion of H($\gamma$$\epsilon$). These results are achieved by disentangling the role of the cost and the entropy in the regularized problem. Contents
2.Sensitivity Analysis in Parametric Convex Vector Optimization
Authors:Duong Thi Viet An, Le Thanh Tung
Abstract: In this paper, sensitivity analysis of the efficient sets in parametric convex vector optimization is considered. Namely, the perturbation, weak perturbation, and proper perturbation maps are defined as set-valued maps. We establish the formulas for computing the Fr\'{e}chet coderivative of the profile of the above three kinds of perturbation maps. Because of the convexity assumptions, the conditions set are fairly simple if compared to those in the general case. In addition, our conditions are stated directly on the data of the problem. It is worth emphasizing that our approach is based on convex analysis tools which are different from those in the general case.
3.Towards continuous-time MPC: a novel trajectory optimization algorithm
Authors:Souvik Das, Siddhartha Ganguly, Muthyala Anjali, Debasish Chatterjee
Abstract: This article introduces a numerical algorithm that serves as a preliminary step toward solving continuous-time model predictive control (MPC) problems directly without explicit time-discretization. The chief ingredients of the underlying optimal control problem (OCP) are a linear time-invariant system, quadratic instantaneous and terminal cost functions, and convex path constraints. The thrust of the method involves finitely parameterizing the admissible space of control trajectories and solving the OCP satisfying the given constraints at every time instant in a tractable manner without explicit time-discretization. The ensuing OCP turns out to be a convex semi-infinite program (SIP), and some recently developed results are employed to obtain an optimal solution to this convex SIP. Numerical illustrations on some benchmark models are included to show the efficacy of the algorithm.
4.An agent-based decentralized threshold policy finding the constrained shortest paths
Authors:Francesca Rosset, Raffaele Pesenti, Franco Blanchini
Abstract: We consider a problem where autonomous agents enter a dynamic and unknown environment described by a network of weighted arcs. These agents move within the network from node to node according to a decentralized policy using only local information, with the goal of finding a path to an unknown sink node to leave the network. This policy makes each agent move to some adjacent node or stop at the current node. The transition along an arc is allowed or denied based on a threshold mechanism that takes into account the number of agents already accumulated in the arc's end nodes and the arc's weight. We show that this policy ensures path-length optimality in the sense that, in a finite time, all new agents entering the network reach the closer sinks by the shortest paths. Our approach is later extended to support constraints on the paths that agents can follow.
5.On the Computation-Communication Trade-Off with A Flexible Gradient Tracking Approach
Authors:Yan Huang, Jinming Xu
Abstract: We propose a flexible gradient tracking approach with adjustable computation and communication steps for solving distributed stochastic optimization problem over networks. The proposed method allows each node to perform multiple local gradient updates and multiple inter-node communications in each round, aiming to strike a balance between computation and communication costs according to the properties of objective functions and network topology in non-i.i.d. settings. Leveraging a properly designed Lyapunov function, we derive both the computation and communication complexities for achieving arbitrary accuracy on smooth and strongly convex objective functions. Our analysis demonstrates sharp dependence of the convergence performance on graph topology and properties of objective functions, highlighting the trade-off between computation and communication. Numerical experiments are conducted to validate our theoretical findings.
6.Analysis of the vanishing discount limit for optimal control problems in continuous and discrete time
Authors:Piermarco Cannarsa, Stephane Gaubert, Cristian Mendico, Marc Quincampoix
Abstract: A classical problem in ergodic continuous time control consists of studying the limit behavior of the optimal value of a discounted cost functional with infinite horizon as the discount factor $\lambda$ tends to zero. In the literature, this problem has been addressed under various controllability or ergodicity conditions ensuring that the rescaled value function converges uniformly to a constant limit. In this case the limit can be characterized as the unique constant such that a suitable Hamilton-Jacobi equation has at least one continuous viscosity solution. In this paper, we study this problem without such conditions, so that the aforementioned limit needs not be constant. Our main result characterizes the uniform limit (when it exists) as the maximal subsolution of a system of Hamilton-Jacobi equations. Moreover, when such a subsolution is a viscosity solution, we obtain the convergence of optimal values as well as a rate of convergence. This mirrors the analysis of the discrete time case, where we characterize the uniform limit as the supremum over a set of sub-invariant half-lines of the dynamic programming operator. The emerging structure in both discrete and continuous time models shows that the supremum over sub-invariato half-lines with respect to the Lax-Oleinik semigroup/dynamic programming operator, captures the behavior of the limit cost as discount vanishes.