Optimization and Control (math.OC)

Abstract: The use of distributed optimization in machine learning can be motivated either by the resulting preservation of privacy or the increase in computational efficiency. On the one hand, training data might be stored across multiple devices. Training a global model within a network where each node only has access to its confidential data requires the use of distributed algorithms. Even if the data is not confidential, sharing it might be prohibitive due to bandwidth limitations. On the other hand, the ever-increasing amount of available data leads to large-scale machine learning problems. By splitting the training process across multiple nodes its efficiency can be significantly increased. This paper aims to demonstrate how dual decomposition can be applied for distributed training of $ K $-means clustering problems. After an overview of distributed and federated machine learning, the mixed-integer quadratically constrained programming-based formulation of the $ K $-means clustering training problem is presented. The training can be performed in a distributed manner by splitting the data across different nodes and linking these nodes through consensus constraints. Finally, the performance of the subgradient method, the bundle trust method, and the quasi-Newton dual ascent algorithm are evaluated on a set of benchmark problems. While the mixed-integer programming-based formulation of the clustering problems suffers from weak integer relaxations, the presented approach can potentially be used to enable an efficient solution in the future, both in a central and distributed setting.

Abstract: The Perron-Frobenius theorem says that the spectral radius of an irreducible nonnegative tensor is the unique positive eigenvalue corresponding to a positive eigenvector. With this in mind, the purpose of this paper is to find the spectral radius and its corresponding positive eigenvector of an irreducible nonnegative symmetric tensor. By transferring the eigenvalue problem into an equivalent problem of minimizing a concave function on a closed convex set, which is typically a DC (difference of convex functions) programming, we derive a simpler and cheaper iterative method. The proposed method is well-defined. Furthermore, we show that both sequences of the eigenvalue estimates and the eigenvector evaluations generated by the method $Q$-linearly converge to the spectral radius and its corresponding eigenvector, respectively. To accelerate the method, we introduce a line search technique. The improved method retains the same convergence property as the original version. Preliminary numerical results show that the improved method performs quite well.

Abstract: We present DecisionProgramming.jl, a new Julia package for modelling decision problems as mixed-integer programming (MIP) equivalents. The package allows the user to pose decision problems as influence diagrams which are then automatically converted to an equivalent MIP formulation. This MIP formulation is implemented using JuMP.jl, a Julia package providing an algebraic syntax for formulating mathematical programming problems. In this paper, we show novel MIP formulations used in the package, which considerably improve the computational performance of the MIP solver. We also present a novel heuristic that can be employed to warm start the solution, as well as providing heuristic solutions to more computationally challenging problems. Lastly, we describe a novel case study showcasing decision programming as an alternative framework for modelling multi-stage stochastic dynamic programming problems.

Abstract: We study the computation of doubly regularized Wasserstein barycenters, a recently introduced family of entropic barycenters governed by inner and outer regularization strengths. Previous research has demonstrated that various regularization parameter choices unify several notions of entropy-penalized barycenters while also revealing new ones, including a special case of debiased barycenters. In this paper, we propose and analyze an algorithm for computing doubly regularized Wasserstein barycenters. Our procedure builds on damped Sinkhorn iterations followed by exact maximization/minimization steps and guarantees convergence for any choice of regularization parameters. An inexact variant of our algorithm, implementable using approximate Monte Carlo sampling, offers the first non-asymptotic convergence guarantees for approximating Wasserstein barycenters between discrete point clouds in the free-support/grid-free setting.

Abstract: In this work, we consider optimal control problems for mechanical systems on vector spaces with fixed initial and free final state and a quadratic Lagrange term. Specifically, the dynamics is described by a second order ODE containing an affine control term and we allow linear coordinate changes in the configuration space. Classically, Pontryagin's maximum principle gives necessary optimality conditions for the optimal control problem. For smooth problems, alternatively, a variational approach based on an augmented objective can be followed. Here, we propose a new Lagrangian approach leading to equivalent necessary optimality conditions in the form of Euler-Lagrange equations. Thus, the differential geometric structure (similar to classical Lagrangian dynamics) can be exploited in the framework of optimal control problems. In particular, the formulation enables the symplectic discretisation of the optimal control problem via variational integrators in a straightforward way.

Abstract: We propose a novel framework for the Lyapunov analysis of a large class of hybrid systems, inspired by the theory of symbolic dynamics and earlier results on the restricted class of switched systems. This new framework allows us to leverage language theory tools in order to provide a universal characterization of Lyapunov stability for this class of systems. We establish, in particular, a formal connection between multiple Lyapunov functions and techniques based on memorization and/or prediction of the discrete part of the state. This allows us to provide an equivalent (single) Lyapunov function, for any given multiple-Lyapunov criterion. By leveraging our Language-theoretic formalism, a new class of stability conditions is then obtained when considering both memory and future values of the state in a joint fashion, providing new numerical schemes that outperform existing technique. Our techniques are then illustrated on numerical examples.

Abstract: Motivated by applications in e-retail and online advertising, we study the problem of assortment optimization under visibility constraints, that we refer to as APV. We are given a universe of substitutable products and a stream of T customers. The objective is to determine the optimal assortment of products to offer to each customer in order to maximize the total expected revenue, subject to the constraint that each product is required to be shown to a minimum number of customers. The minimum display requirement for each product is given exogenously and we refer to these constraints as visibility constraints. We assume that customer choices follow a Multinomial Logit model (MNL). We provide a characterization of the structure of the optimal assortments and present an efficient polynomial time algorithm for solving APV. To accomplish this, we introduce a novel function called the ``expanded revenue" of an assortment and establish its supermodularity. Our algorithm takes advantage of this structural property. Additionally, we demonstrate that APV can be formulated as a compact linear program. We also examine the revenue loss resulting from the enforcement of visibility constraints, comparing it to the unconstrained version of the problem. To offset this loss, we propose a novel strategy to distribute the loss among the products subject to visibility constraints. Each vendor is charged an amount proportional to their product's contribution to the revenue loss. Finally, we present the results of our numerical experiments providing illustration of the obtained outcomes, and we discuss some preliminary results on the extension of the problem to accommodate cardinality constraints.

Abstract: For a symmetric Lie algebra $\mathfrak g=\mathfrak k\oplus\mathfrak p$ we consider a class of bilinear or more general control-affine systems on $\mathfrak p$ defined by a drift vector field $X$ and control vector fields $\mathrm{ad}_{k_i}$ for $k_i\in\mathfrak k$ such that one has fast and full control on the corresponding compact group $\mathbf K$. We show that under quite general assumptions on $X$ such a control system is essentially equivalent to a natural reduced system on a maximal Abelian subspace $\mathfrak a\subseteq\mathfrak p$, and likewise to related differential inclusions defined on $\mathfrak a$. We derive a number of general results for such systems and as an application we prove a simulation result with respect to the preorder induced by the Weyl group action.

Abstract: In previous work, we have developed an approach for characterizing the long-term dynamics of classes of Biological Interaction Networks (BINs), based on "rate-dependent Lyapunov functions". In this work, we show that stronger notions of convergence can be established by proving structural contractivity with respect to non-standard norms. We illustrate our theory with examples from signaling pathways.