arXiv daily: Optimization and Control (math.OC)

Authors:Bharat Kumar, Deepmala, A. K. Das

Abstract: This article presents a class of new relaxation modulus-based iterative methods to process the large and sparse implicit complementarity problem (ICP). Using two positive diagonal matrices, we formulate a fixed-point equation and prove that it is equivalent to ICP. Also, we provide sufficient convergence conditions for the proposed methods when the system matrix is a $P$-matrix or an $H_+$-matrix. Keyword: Implicit complementarity problem, $H_{+}$-matrix, $P$-matrix, matrix splitting, convergence

Authors:Piermarco Cannarsa, Cristian Mendico

Abstract: The aim of this work is to provide a systemic study and generalization of the celebrated weak KAM theory and Aubry-Mather theory in sub-Riemannian setting, or equivalently, on a Carnot-Caratheodory metric space. In this framework we consider an optimal control problem with state equation of sub-Riemannian type, namely, admissible trajectories are solutions of a linear in control and nonlinear in space ODE. Such a nonlinearity is given by a family of smooth vector fields satisfying the Hormander condition which implies the controllability of the system. In this case, the Hamiltonian function associated with the above control problem fails to be coercive and thus the results in the Tonelli setting can not be applied. In order to overcome this issue, our approach is based on metric properties of the geometry induced on the state space by the sub-Riemannian structure.

Authors:Beatrice Acciaio, Berenice Anne Neumann

Abstract: We introduce graphs associated to transport problems between discrete marginals, that allow to characterize the set of all optimizers given one primal optimizer. In particular, we establish that connectivity of those graphs is a necessary and sufficient condition for uniqueness of the dual optimizers. Moreover, we provide an algorithm that can efficiently compute the dual optimizer that is the limit, as the regularization parameter goes to zero, of the dual entropic optimizers. Our results find an application in a Stackelberg-Cournot-Nash game, for which we obtain existence and characterization of the equilibria.

Authors:Bram Bekker, Fernando Mário de Oliveira Filho

Abstract: We show that the $k$-point bound of de Laat, Machado, Oliveira, and Vallentin, a hierarchy of upper bounds for the independence number of a topological packing graph derived from the Lasserre hierarchy, converges to the independence number.

Authors:Niels Lindner, Berenike Masing

Abstract: The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables. We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms, namely cycles and arc sets of the digraph underlying the PESP instance. It is known that flip inequalities can be separated in pseudo-polynomial time. We prove that this is best possible unless P $=$ NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed. Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and provide better dual bounds for five instances.

Authors:Salvador Pineda, Juan Miguel Morales, Álvaro Porras, Concepción Domínguez

Abstract: This paper addresses the Optimal Transmission Switching (OTS) problem in electricity networks, which aims to find an optimal power grid topology that minimizes system operation costs while satisfying physical and operational constraints. Existing methods typically convert the OTS problem into a Mixed-Integer Linear Program (MILP) using big-M constants. However, the computational performance of these approaches relies significantly on the tightness of these big-Ms. In this paper, we propose an iterative tightening strategy to strengthen the big-Ms by efficiently solving a series of bounding problems that account for the economics of the OTS objective function through an upper-bound on the generating cost. We also discuss how the performance of the proposed tightening strategy is enhanced if reduced line capacities are considered. Using the 118-bus test system we demonstrate that the proposed methodology outperforms existing approaches, offering tighter bounds and significantly reducing the computational burden of the OTS problem.

Authors:Margarida Carvalho, Gabriele Dragotto, Andrea Lodi, Sriram Sankaranarayan

Abstract: In this tutorial, we present a computational overview on computing Nash equilibria in Integer Programming Games ($IPG$s), $i.e.$, how to compute solutions for a class of non-cooperative and nonconvex games where each player solves a mixed-integer optimization problem. $IPG$s are a broad class of games extending the modeling power of mixed-integer optimization to multi-agent settings. This class of games includes, for instance, any finite game and any multi-agent extension of traditional combinatorial optimization problems. After providing some background motivation and context of applications, we systematically review and classify the state-of-the-art algorithms to compute Nash equilibria. We propose an essential taxonomy of the algorithmic ingredients needed to compute equilibria, and we describe the theoretical and practical challenges associated with equilibria computation. Finally, we quantitatively and qualitatively compare a sequential Stackelberg game with a simultaneous $IPG$ to highlight the different properties of their solutions.

Authors:Torbjørn Cunis

Abstract: The region of attraction characterizes well-behaved and safe operation of a nonlinear system and is hence sought after for verification. In this paper, a framework for probabilistic region of attraction estimation is developed that combines scenario optimization and converse theorems. With this approach, the probability of an unstable condition being included in the estimate is independent of the system's complexity, while convergence in probability to the true region of attraction is proven. Numerical examples demonstrate the effectiveness for optimization-based control applications. Combining systems theory and sampling, the complexity of Monte--Carlo-based verification techniques can be reduced. The results can be extended to arbitrary level sets of which the defining function can be sampled, such as finite-horizon viability. Thus, the proposed approach is applicable and/or adaptable to verification of a wide range of safety-related properties for nonlinear systems including feedback laws based on optimization or learning.

Authors:Sifa Celik, Layla Martin, Albert H. Schrotenboer, Tom Van Woensel

Abstract: Many real-life optimization problems belong to the class of two-stage stochastic mixed-integer programming problems with continuous recourse. This paper introduces Two-Step Benders Decomposition with Scenario Clustering (TBDS) as a general exact solution methodology for solving such stochastic programs to optimality. The method combines and generalizes Benders dual decomposition, partial Benders decomposition, and Scenario Clustering techniques and does so within a novel two-step decomposition along the binary and continuous first-stage decisions. We use TBDS to provide the first exact solutions for the so-called Time Window Assignment Traveling Salesperson problem. This is a canonical optimization problem for service-oriented vehicle routing; it considers jointly assigning time windows to customers and routing a vehicle among them while travel times are stochastic. Extensive experiments show that TBDS is superior to state-of-the-art approaches in the literature. It solves instances with up to 25 customers to optimality. It provides better lower and upper bounds that lead to faster convergence than related methods. For example, Benders dual decomposition cannot solve instances of 10 customers to optimality. We use TBDS to analyze the structure of the optimal solutions. By increasing routing costs only slightly, customer service can be improved tremendously, driven by smartly alternating between high- and low-variance travel arcs to reduce the impact of delay propagation throughout the executed vehicle route.

Authors:Christopher Criscitiello, Nicolas Boumal

Abstract: We study the query complexity of geodesically convex (g-convex) optimization on a manifold. To isolate the effect of that manifold's curvature, we primarily focus on hyperbolic spaces. In a variety of settings (smooth or not; strongly g-convex or not; high- or low-dimensional), known upper bounds worsen with curvature. It is natural to ask whether this is warranted, or an artifact. For many such settings, we propose a first set of lower bounds which indeed confirm that (negative) curvature is detrimental to complexity. To do so, we build on recent lower bounds (Hamilton and Moitra, 2021; Criscitiello and Boumal, 2022) for the particular case of smooth, strongly g-convex optimization. Using a number of techniques, we also secure lower bounds which capture dependence on condition number and optimality gap, which was not previously the case. We suspect these bounds are not optimal. We conjecture optimal ones, and support them with a matching lower bound for a class of algorithms which includes subgradient descent, and a lower bound for a related game. Lastly, to pinpoint the difficulty of proving lower bounds, we study how negative curvature influences (and sometimes obstructs) interpolation with g-convex functions.

Authors:Dirk Lauinger, François Vuille, Daniel Kuhn

Abstract: Low-carbon societies will need to store vast amounts of electricity to balance intermittent generation from wind and solar energy, for example, through frequency regulation. Here, we derive an analytical solution to the decision-making problem of storage operators who sell frequency regulation power to grid operators and trade electricity on day-ahead markets. Mathematically, we treat future frequency deviation trajectories as functional uncertainties in a receding horizon robust optimization problem. We constrain the expected terminal state-of-charge to be equal to some target to allow storage operators to make good decisions not only for the present but also the future. Thanks to this constraint, the amount of electricity traded on day-ahead markets is an implicit function of the regulation power sold to grid operators. The implicit function quantifies the amount of power that needs to be purchased to cover the expected energy loss that results from providing frequency regulation. We show how the marginal cost associated with the expected energy loss decreases with roundtrip efficiency and increases with frequency deviation dispersion. We find that the profits from frequency regulation over the lifetime of energy-constrained storage devices are roughly inversely proportional to the length of time for which regulation power must be committed.

Authors:Siddhartha Ganguly, Debasish Chatterjee

Abstract: We present QuIFS (Quasi-Interpolation driven Feedback Synthesis) -- an offline feedback synthesis algorithm for explicit nonlinear robust minmax model predictive control (MPC) problems with guaranteed quality of approximation. The underlying technique is driven by a particular type of grid-based quasi-interpolation scheme. The QuIFS algorithm departs drastically from conventional approximation algorithms that are employed in the MPC industry (in particular, it is neither based on multi-parametric programming tools nor does it involve kernel methods), and the essence of their point of departure is encoded in the following challenge-answer approach: Given an error margin $\varepsilon>0$, compute a feasible feedback policy that is uniformly $\varepsilon$-close to the optimal MPC feedback policy for a given nonlinear system subjected to hard constraints and bounded uncertainties. Conditions for closed-loop stability and recursive feasibility under the approximate feedback policy are also established. We provide a library of numerical examples to illustrate our results.

Authors:Razvan-Andrei Lascu, Mateusz B. Majka, Łukasz Szpruch

Abstract: We investigate convergence properties of two continuous-time optimization methods, the Mean-Field Best Response and the Fisher-Rao (Mean-Field Birth-Death) flows, for solving convex-concave min-max games with entropy regularization. We introduce suitable Lyapunov functions to establish exponential convergence to the unique mixed Nash equilibrium for both methods, albeit under slightly different conditions. Additionally, we demonstrate the convergence of the fictitious play flow as a by-product of our analysis.

Authors:Bholanath Kumbhakar, Dwijendra Narain Pandey

Abstract: The current paper initially studies the optimal control of linear $\psi$-Hilfer fractional derivatives with state-dependent control constraints and optimal control for a particular type of cost functional. Then, we investigate the approximate controllability of the abstract fractional semilinear differential inclusion involving $\psi$-Hilfer fractional derivative in reflexive Banach spaces. It is known that the existence, uniqueness, optimal control, and approximate controllability of fractional differential equations or inclusions have been demonstrated for a similar type of fractional differential equations or inclusions with different fractional order derivative operators. Hence it has to research fractional differential equations with more general fractional operators which incorporate all the specific fractional derivative operators. This motivates us to consider the $\psi$-Hilfer fractional differential inclusion. We assume the compactness of the corresponding semigroup and the approximate controllability of the associated linear control system and define the control with the help of duality mapping. We observe that convexity is essential in determining the controllability property of semilinear differential inclusion. In the case of Hilbert spaces, there is no issue of convexity as the duality map becomes simply the identity map. In contrast to Hilbert spaces, if we consider reflexive Banach spaces, there is an issue of convexity due to the nonlinear nature of duality mapping. The novelty of this paper is that we overcome this convexity issue and establish our main result. Finally, we test our outcomes through an example.

Authors:Dinesh Nayak, A. V. Sangeetha, D. K. K. Vamsi

Abstract: Mycobacterium leprae is a bacteria that causes the disease Leprosy (Hansen's disease), which is a neglected tropical disease. More than 200000 cases are being reported per year world wide. This disease leads to a chronic stage known as Lepra reaction that majorly causes nerve damage of peripheral nervous system leading to loss of organs. The early detection of this Lepra reaction through the level of bio-markers can prevent this reaction occurring and the further disabilities. Motivated by this, we frame a mathematical model considering the pathogenesis of leprosy and the chemical pathways involved in Lepra reactions. The model incorporates the dynamics of the susceptible schwann cells, infected schwann cells and the bacterial load and the concentration levels of the bio markers $IFN-\gamma$, $TNF-\alpha$, $IL-10$, $IL-12$, $IL-15$ and $IL-17$. We consider a nine compartment optimal control problem considering the drugs used in Multi Drug Therapy (MDT) as controls. We validate the model using 2D - heat plots. We study the correlation between the bio-markers levels and drugs in MDT and propose an optimal drug regimen through these optimal control studies. We use the Newton's Gradient Method for the optimal control studies.

Authors:Laurence Carassus, Johannes Wiesel

Abstract: We investigate an expected utility maximization problem under model uncertainty in a one-period financial market. We capture model uncertainty by replacing the baseline model $\mathbb{P}$ with an adverse choice from a Wasserstein ball of radius $k$ around $\mathbb{P}$ in the space of probability measures and consider the corresponding Wasserstein distributionally robust optimization problem. We show that optimal solutions converge to the uniform diversification strategy when uncertainty is increasingly large, i.e. when the radius $k$ tends to infinity.

Authors:Poulad Moradi, Joachim Arts, Josué Velázquez-Martínez

Abstract: We study the effect of using high-resolution elevation data on the selection of the most fuel-efficient (greenest) path for different trucks in various urban environments. We adapt a variant of the Comprehensive Modal Emission Model (CMEM) to show that the optimal speed and the greenest path are slope dependent (dynamic). When there are no elevation changes in a road network, the most fuel-efficient path is the shortest path with a constant (static) optimal speed throughout. However, if the network is not flat, then the shortest path is not necessarily the greenest path, and the optimal driving speed is dynamic. We prove that the greenest path converges to an asymptotic greenest path as the payload approaches infinity and that this limiting path is attained for a finite load. In a set of extensive numerical experiments, we benchmark the CO2 emissions reduction of our dynamic speed and the greenest path policies against policies that ignore elevation data. We use the geo-spatial data of 25 major cities across 6 continents, such as Los Angeles, Mexico City, Johannesburg, Athens, Ankara, and Canberra. Our results show that, on average, traversing the greenest path with a dynamic optimal speed policy can reduce the CO2 emissions by 1.19% to 10.15% depending on the city and truck type for a moderate payload. They also demonstrate that the average CO2 reduction of the optimal dynamic speed policy is between 2% to 4% for most of the cities, regardless of the truck type. We confirm that disregarding elevation data yields sub-optimal paths that are significantly less CO2 efficient than the greenest paths.

Authors:Feifei Gao, Caixia Kou

Abstract: We firstly propose the new stochastic gradient estimate of unbiasedness and minimized variance in this paper. Secondly, we propose the two algorithms: Algorithml and Algorithm2 which apply the new stochastic gradient estimate to modern stochastic conjugate gradient algorithms SCGA 7and CGVR 8. Then we prove that the proposed algorithms can obtain linearconvergence rate under assumptions of strong convexity and smoothness. Finally, numerical experiments show that the new stochastic gradient estimatecan reduce variance of stochastic gradient effectively. And our algorithms compared SCGA and CGVR can convergent faster in numerical experimentson ridge regression model.

Authors:Carsten W. Scherer, Christian Ebenbauer, Tobias Holicki

Abstract: We expose in a tutorial fashion the mechanisms which underly the synthesis of optimization algorithms based on dynamic integral quadratic constraints. We reveal how these tools from robust control allow to design accelerated gradient descent algorithms with optimal guaranteed convergence rates by solving small-sized convex semi-definite programs. It is shown that this extends to the design of extremum controllers, with the goal to regulate the output of a general linear closed-loop system to the minimum of an objective function. Numerical experiments illustrate that we can not only recover gradient decent and the triple momentum variant of Nesterov's accelerated first order algorithm, but also automatically synthesize optimal algorithms even if the gradient information is passed through non-trivial dynamics, such as time-delays.

Authors:Carsten W. Scherer

Abstract: We propose novel time-domain dynamic integral quadratic constraints with a terminal cost for exponentially weighted slope-restricted gradients of not necessarily convex functions. This extends recent results for subdifferentials of convex function and their link to so-called O'Shea-Zames-Falb multipliers. The benefit of merging time-domain and frequency-domain techniques is demonstrated for linear saturated systems.

Authors:Hongzhe Yu, Joseph Moyalan, Umesh Vaidya, Yongxin Chen

Abstract: In this work we approach the dual optimal reach-safe control problem using sparse approximations of Koopman operator. Matrix approximation of Koopman operator needs to solve a least-squares (LS) problem in the lifted function space, which is computationally intractable for fine discretizations and high dimensions. The state transitional physical meaning of the Koopman operator leads to a sparse LS problem in this space. Leveraging this sparsity, we propose an efficient method to solve the sparse LS problem where we reduce the problem dimension dramatically by formulating the problem using only the non-zero elements in the approximation matrix with known sparsity pattern. The obtained matrix approximation of the operators is then used in a dual optimal reach-safe problem formulation where a linear program with sparse linear constraints naturally appears. We validate our proposed method on various dynamical systems and show that the computation time for operator approximation is greatly reduced with high precision in the solutions.

Authors:Guillaume Olikier, André Uschmajew, Bart Vandereycken

Abstract: We consider gradient-related methods for low-rank matrix optimization with a smooth cost function. The methods operate on single factors of the low-rank factorization and share aspects of both alternating and Riemannian optimization. Two possible choices for the search directions based on Gauss-Southwell type selection rules are compared: one using the gradient of a factorized non-convex formulation, the other using the Riemannian gradient. While both methods provide gradient convergence guarantees that are similar to the unconstrained case, the version based on Riemannian gradient is significantly more robust with respect to small singular values and the condition number of the cost function, as illustrated by numerical experiments. As a side result of our approach, we also obtain new convergence results for the alternating least squares method.

Authors:Samuel Daudin

Abstract: We study the convergence problem of mean-field control theory in the presence of state constraints and non-degenerate idiosyncratic noise. Our main result is the convergence of the value functions associated to stochastic control problems for many interacting particles subject to symmetric, almost-sure constraints toward the value function of a control problem of mean-field type, set on the space of probability measures. The key step of the proof is to show that admissible controls for the limit problem can be turned into admissible controls for the $N$-particle problem up to a correction which vanishes as the number of particles increases. The rest of the proof relies on compactness methods. We also provide optimality conditions for the mean-field problem and discuss the regularity of the optimal controls. Finally we present some applications and connections with large deviations for weakly interacting particle systems.

Authors:Jiacai Liu, Jinchi Chen, Ke Wei

Abstract: The convergence of deterministic policy gradient under the Hadamard parametrization is studied in the tabular setting and the global linear convergence of the algorithm is established. To this end, we first show that the error decreases at an $O(\frac{1}{k})$ rate for all the iterations. Based on this result, we further show that the algorithm has a faster local linear convergence rate after $k_0$ iterations, where $k_0$ is a constant that only depends on the MDP problem and the step size. Overall, the algorithm displays a linear convergence rate for all the iterations with a loose constant than that for the local linear convergence rate.

Authors:Anna Chiara Lai, Monica Motta

Abstract: Given a nonlinear control system, a target set, a nonnegative integral cost, and a continuous function $W$, we say that the system is globally asymptotically controllable to the target with W-regulated cost, whenever, starting from any point z, among the strategies that achieve classical asymptotic controllability we can select one that also keeps the cost less than W(z). In this paper, assuming mild regularity hypotheses on the data, we prove that a necessary and sufficient condition for global asymptotic controllability with regulated cost is the existence of a special, continuous Control Lyapunov function, called a Minimum Restraint function. The main novelty is the necessity implication, obtained here for the first time. Nevertheless, the sufficiency condition extends previous results based on semiconcavity of the Minimum Restraint function, while we require mere continuity.

Authors:Stephan Dempe, Markus Friedemann, Felix Harder, Patrick Mehlitz, Gerd Wachsmuth

Abstract: In this chapter, we are concerned with inverse optimal control problems, i.e., optimization models which are used to identify parameters in optimal control problems from given measurements. Here, we focus on linear-quadratic optimal control problems with control constraints where the reference control plays the role of the parameter and has to be reconstructed. First, it is shown that pointwise M-stationarity, associated with the reformulation of the hierarchical model as a so-called mathematical problem with complementarity constraints (MPCC) in function spaces, provides a necessary optimality condition under some additional assumptions on the data. Second, we review two recently developed algorithms (an augmented Lagrangian method and a nonsmooth Newton method) for the computational identification of M-stationary points of finite-dimensional MPCCs. Finally, a numerical comparison of these methods, based on instances of the appropriately discretized inverse optimal control problem of our interest, is provided.

Authors:Erik Jansson, Klas Modin

Abstract: We investigate a matrix dynamical system related to optimal mass transport in the linear category, namely, the problem of finding an optimal invertible matrix by which two covariance matrices are congruent. We first review the differential geometric structure of the problem in terms of a principal fiber bundle. The dynamical system is a gradient flow restricted to the fibers of the bundle. We prove global existence of solutions to the flow, with convergence to the polar decomposition of the matrix given as initial data. The convergence is illustrated in a numerical example.

Authors:Lateef O. Jolaoso, Patrick Mehlitz, Alain B. Zemkoho

Abstract: In this paper, we revisit the classical problem of solving over-determined systems of nonsmooth equations numerically. We suggest a nonsmooth Levenberg--Marquardt method for its solution which, in contrast to the existing literature, does not require local Lipschitzness of the data functions. This is possible when using Newton-differentiability instead of semismoothness as the underlying tool of generalized differentiation. Conditions for fast local convergence of the method are given. Afterwards, in the context of over-determined mixed nonlinear complementarity systems, our findings are applied, and globalized solution methods, based on a residual induced by the maximum and the Fischer--Burmeister function, respectively, are constructed. The assumptions for fast local convergence are worked out and compared. Finally, these methods are applied for the numerical solution of bilevel optimization problems. We recall the derivation of a stationarity condition taking the shape of an over-determined mixed nonlinear complementarity system involving a penalty parameter, formulate assumptions for local fast convergence of our solution methods explicitly, and present results of numerical experiments. Particularly, we investigate whether the treatment of the appearing penalty parameter as an additional variable is beneficial or not.

Authors:Dingcheng Luo, Thomas O'Leary-Roseberry, Peng Chen, Omar Ghattas

Abstract: We propose a novel machine learning framework for solving optimization problems governed by large-scale partial differential equations (PDEs) with high-dimensional random parameters. Such optimization under uncertainty (OUU) problems may be computational prohibitive using classical methods, particularly when a large number of samples is needed to evaluate risk measures at every iteration of an optimization algorithm, where each sample requires the solution of an expensive-to-solve PDE. To address this challenge, we propose a new neural operator approximation of the PDE solution operator that has the combined merits of (1) accurate approximation of not only the map from the joint inputs of random parameters and optimization variables to the PDE state, but also its derivative with respect to the optimization variables, (2) efficient construction of the neural network using reduced basis architectures that are scalable to high-dimensional OUU problems, and (3) requiring only a limited number of training data to achieve high accuracy for both the PDE solution and the OUU solution. We refer to such neural operators as multi-input reduced basis derivative informed neural operators (MR-DINOs). We demonstrate the accuracy and efficiency our approach through several numerical experiments, i.e. the risk-averse control of a semilinear elliptic PDE and the steady state Navier--Stokes equations in two and three spatial dimensions, each involving random field inputs. Across the examples, MR-DINOs offer $10^{3}$--$10^{7} \times$ reductions in execution time, and are able to produce OUU solutions of comparable accuracies to those from standard PDE based solutions while being over $10 \times$ more cost-efficient after factoring in the cost of construction.

Authors:Alex Dunbar, Lars Ruthotto

Abstract: We propose an alternating minimization heuristic for regression over the space of tropical rational functions with fixed exponents. The method alternates between fitting the numerator and denominator terms via tropical polynomial regression, which is known to admit a closed form solution. We demonstrate the behavior of the alternating minimization method experimentally. Experiments demonstrate that the heuristic provides a reasonable approximation of the input data. Our work is motivated by applications to ReLU neural networks, a popular class of network architectures in the machine learning community which are closely related to tropical rational functions.

Authors:Erhan Bayraktar, Song Yao

Abstract: We study a stochastic control/stopping problem with a series of inequality-type and equality-type expectation constraints in a general non-Markovian framework. We demonstrate that the stochastic control/stopping problem with expectation constraints (CSEC) is independent of a specific probability setting and is equivalent to the constrained stochastic control/stopping problem in weak formulation (an optimization over joint laws of Brownian motion, state dynamics, diffusion controls and stopping rules on an enlarged canonical space). Using a martingale-problem formulation of controlled SDEs in spirit of \cite{Stroock_Varadhan}, we characterize the probability classes in weak formulation by countably many actions of canonical processes, and thus obtain the upper semi-analyticity of the CSEC value function. Then we employ a measurable selection argument to establish a dynamic programming principle (DPP) in weak formulation for the CSEC value function, in which the conditional expected costs act as additional states for constraint levels at the intermediate horizon. This article extends the results of \cite{Elk_Tan_2013b} to the expectation-constraint case. We extend our previous work \cite{OSEC_stopping} to the more complicated setting where the diffusion is controlled. Compared to that paper the topological properties of diffusion-control spaces and the corresponding measurability are more technically involved which complicate the arguments especially for the measurable selection for the super-solution side of DPP in the weak formulation.

Authors:Quanqi Hu, Zi-Hao Qiu, Zhishuai Guo, Lijun Zhang, Tianbao Yang

Abstract: In this paper, we consider non-convex multi-block bilevel optimization (MBBO) problems, which involve $m\gg 1$ lower level problems and have important applications in machine learning. Designing a stochastic gradient and controlling its variance is more intricate due to the hierarchical sampling of blocks and data and the unique challenge of estimating hyper-gradient. We aim to achieve three nice properties for our algorithm: (a) matching the state-of-the-art complexity of standard BO problems with a single block; (b) achieving parallel speedup by sampling $I$ blocks and sampling $B$ samples for each sampled block per-iteration; (c) avoiding the computation of the inverse of a high-dimensional Hessian matrix estimator. However, it is non-trivial to achieve all of these by observing that existing works only achieve one or two of these properties. To address the involved challenges for achieving (a, b, c), we propose two stochastic algorithms by using advanced blockwise variance-reduction techniques for tracking the Hessian matrices (for low-dimensional problems) or the Hessian-vector products (for high-dimensional problems), and prove an iteration complexity of $O(\frac{m\epsilon^{-3}\mathbb{I}(I<m)}{I\sqrt{I}} + \frac{m\epsilon^{-3}}{I\sqrt{B}})$ for finding an $\epsilon$-stationary point under appropriate conditions. We also conduct experiments to verify the effectiveness of the proposed algorithms comparing with existing MBBO algorithms.

Authors:Nguyen Dinh, Miguel A. Goberna, M. Volle

Abstract: The first two authors of this paper asserted in Lemma 4 of "New Farkas-type constraint qualifications in convex infinite programming" (DOI: 10.1051/cocv:2007027) that a given reverse convex inequality is consequence of a given convex system satisfying the Farkas-Minkowski constraint qualification if and only if certain set depending on the data contains a particular point of the vertical axis. This paper identifies a hidden assumption in this reverse Farkas lemma which always holds in its applications to nontrivial optimization problems. Moreover, it shows that the statement remains valid when the Farkas-Minkowski constraint qualification fails by replacing the mentioned set by its closure. This hidden assumption is also characterized in terms of the data. Finally, the paper provides some applications to convex infinite systems and to convex infinite optimization problems.

Authors:Didier Henrion, Maria Infusino, Salma Kuhlmann, Victor Vinnikov

Abstract: We formulate a class of nonlinear {evolution} partial differential equations (PDEs) as linear optimization problems on moments of positive measures supported on infinite-dimensional vector spaces. Using sums of squares (SOS) representations of polynomials in these spaces, we can prove convergence of a hierarchy of finite-dimensional semidefinite relaxations solving approximately these infinite-dimensional optimization problems. As an illustration, we report on numerical experiments for solving the heat equation subject to a nonlinear perturbation.

Authors:Giovanni Fantuzzi, Federico Fuentes

Abstract: We describe a `discretize-then-relax' strategy to globally minimize integral functionals over functions $u$ in a Sobolev space satisfying prescribed Dirichlet boundary conditions. The strategy applies whenever the integral functional depends polynomially on $u$ and its derivatives, even if it is nonconvex. The `discretize' step uses a bounded finite-element scheme to approximate the integral minimization problem with a convergent hierarchy of polynomial optimization problems over a compact feasible set, indexed by the decreasing size $h$ of the finite-element mesh. The `relax' step employs sparse moment-SOS relaxations to approximate each polynomial optimization problem with a hierarchy of convex semidefinite programs, indexed by an increasing relaxation order $\omega$. We prove that, as $\omega\to\infty$ and $h\to 0$, solutions of such semidefinite programs provide approximate minimizers that converge in $L^p$ to the global minimizer of the original integral functional if this is unique. We also report computational experiments that show our numerical strategy works well even when technical conditions required by our theoretical analysis are not satisfied.

Authors:Mengmeng Li, Tobias Sutter, Daniel Kuhn

Abstract: We propose a policy gradient algorithm for robust infinite-horizon Markov Decision Processes (MDPs) with non-rectangular uncertainty sets, thereby addressing an open challenge in the robust MDP literature. Indeed, uncertainty sets that display statistical optimality properties and make optimal use of limited data often fail to be rectangular. Unfortunately, the corresponding robust MDPs cannot be solved with dynamic programming techniques and are in fact provably intractable. This prompts us to develop a projected Langevin dynamics algorithm tailored to the robust policy evaluation problem, which offers global optimality guarantees. We also propose a deterministic policy gradient method that solves the robust policy evaluation problem approximately, and we prove that the approximation error scales with a new measure of non-rectangularity of the uncertainty set. Numerical experiments showcase that our projected Langevin dynamics algorithm can escape local optima, while algorithms tailored to rectangular uncertainty fail to do so.

Authors:Damien Scieur

Abstract: Despite the impressive numerical performance of quasi-Newton and Anderson/nonlinear acceleration methods, their global convergence rates have remained elusive for over 50 years. This paper addresses this long-standing question by introducing a framework that derives novel and adaptive quasi-Newton or nonlinear/Anderson acceleration schemes. Under mild assumptions, the proposed iterative methods exhibit explicit, non-asymptotic convergence rates that blend those of gradient descent and Cubic Regularized Newton's method. Notably, these rates are achieved adaptively, as the method autonomously determines the optimal step size using a simple backtracking strategy. The proposed approach also includes an accelerated version that improves the convergence rate on convex functions. Numerical experiments demonstrate the efficiency of the proposed framework, even compared to a fine-tuned BFGS algorithm with line search.

Authors:Hengchao Chen, Xin Chen, Mohamad Elmasri, Qiang Sun

Abstract: This paper investigates gradient descent for solving low-rank matrix approximation problems. We begin by establishing the local linear convergence of gradient descent for symmetric matrix approximation. Building on this result, we prove the rapid global convergence of gradient descent, particularly when initialized with small random values. Remarkably, we show that even with moderate random initialization, which includes small random initialization as a special case, gradient descent achieves fast global convergence in scenarios where the top eigenvalues are identical. Furthermore, we extend our analysis to address asymmetric matrix approximation problems and investigate the effectiveness of a retraction-free eigenspace computation method. Numerical experiments strongly support our theory. In particular, the retraction-free algorithm outperforms the corresponding Riemannian gradient descent method, resulting in a significant 29\% reduction in runtime.

Authors:Irina Wang, Cole Becker, Bart Van Parys, Bartolomeo Stellato

Abstract: We propose a data-driven technique to automatically learn the uncertainty sets in robust optimization. Our method reshapes the uncertainty sets by minimizing the expected performance across a family of problems while guaranteeing constraint satisfaction. We learn the uncertainty sets using a novel stochastic augmented Lagrangian method that relies on differentiating the solutions of the robust optimization problems with respect to the parameters of the uncertainty set. We show sublinear convergence to stationary points under mild assumptions, and finite-sample probabilistic guarantees of constraint satisfaction using empirical process theory. Our approach is very flexible and can learn a wide variety of uncertainty sets while preserving tractability. Numerical experiments show that our method outperforms traditional approaches in robust and distributionally robust optimization in terms of out of sample performance and constraint satisfaction guarantees. We implemented our method in the open-source package LROPT.

Authors:Adrien Le Franc LAAS-POP, Victor Magron LAAS-POP,IMT, Jean-Bernard Lasserre LAAS-POP, Manuel Ruiz, Patrick Panciatici

Abstract: AC-OPF (Alternative Current Optimal Power Flow)aims at minimizing the operating costs of a power gridunder physical constraints on voltages and power injections.Its mathematical formulation results in a nonconvex polynomial optimizationproblem which is hard to solve in general,but that can be tackled by a sequence of SDP(Semidefinite Programming) relaxationscorresponding to the steps of the moment-SOS (Sums-Of-Squares) hierarchy.Unfortunately, the size of these SDPs grows drastically in the hierarchy,so that even second-order relaxationsexploiting the correlative sparsity pattern of AC-OPFare hardly numerically tractable for largeinstances -- with thousands of power buses.Our contribution lies in a new sparsityframework, termed minimal sparsity, inspiredfrom the specific structure of power flowequations.Despite its heuristic nature, numerical examples show that minimal sparsity allows the computation ofhighly accurate second-order moment-SOS relaxationsof AC-OPF, while requiring far less computing time and memory resources than the standard correlative sparsity pattern. Thus, we manage to compute second-order relaxations on test caseswith about 6000 power buses, which we believe to be unprecedented.

Authors:Keita Kume, Isao Yamada

Abstract: We present an adaptive parametrization strategy for optimization problems over the Stiefel manifold by using generalized Cayley transforms to utilize powerful Euclidean optimization algorithms efficiently. The generalized Cayley transform can translate an open dense subset of the Stiefel manifold into a vector space, and the open dense subset is determined according to a tunable parameter called a center point. With the generalized Cayley transform, we recently proposed the naive Cayley parametrization, which reformulates the optimization problem over the Stiefel manifold as that over the vector space. Although this reformulation enables us to transplant powerful Euclidean optimization algorithms, their convergences may become slow by a poor choice of center points. To avoid such a slow convergence, in this paper, we propose to estimate adaptively 'good' center points so that the reformulated problem can be solved faster. We also present a unified convergence analysis, regarding the gradient, in cases where fairly standard Euclidean optimization algorithms are employed in the proposed adaptive parametrization strategy. Numerical experiments demonstrate that (i) the proposed strategy succeeds in escaping from the slow convergence observed in the naive Cayley parametrization strategy; (ii) the proposed strategy outperforms the standard strategy which employs a retraction.

Authors:Chengchang Liu, Lesi Chen, Luo Luo, John C. S. Lui

Abstract: We propose a communication and computation efficient second-order method for distributed optimization. For each iteration, our method only requires $\mathcal{O}(d)$ communication complexity, where $d$ is the problem dimension. We also provide theoretical analysis to show the proposed method has the similar convergence rate as the classical second-order optimization algorithms. Concretely, our method can find~$\big(\epsilon, \sqrt{dL\epsilon}\,\big)$-second-order stationary points for nonconvex problem by $\mathcal{O}\big(\sqrt{dL}\,\epsilon^{-3/2}\big)$ iterations, where $L$ is the Lipschitz constant of Hessian. Moreover, it enjoys a local superlinear convergence under the strongly-convex assumption. Experiments on both convex and nonconvex problems show that our proposed method performs significantly better than baselines.

Authors:Masaru Ito, Zhaosong Lu, Chuan He

Abstract: In this paper we consider a composite optimization problem that minimizes the sum of a weakly smooth function and a convex function with either a bounded domain or a uniformly convex structure. In particular, we first present a parameter-dependent conditional gradient method for this problem, whose step sizes require prior knowledge of the parameters associated with the H\"older continuity of the gradient of the weakly smooth function, and establish its rate of convergence. Given that these parameters could be unknown or known but possibly conservative, such a method may suffer from implementation issue or slow convergence. We therefore propose a parameter-free conditional gradient method whose step size is determined by using a constructive local quadratic upper approximation and an adaptive line search scheme, without using any problem parameter. We show that this method achieves the same rate of convergence as the parameter-dependent conditional gradient method. Preliminary experiments are also conducted and illustrate the superior performance of the parameter-free conditional gradient method over the methods with some other step size rules.

Authors:Shubham Kumar, Deepmala

Abstract: In this survey paper, we focus on the necessary and sufficient conditions for the unique solvability and unsolvability of the absolute value equations (AVEs) during the last twenty years (2004 to 2023). We discussed unique solvability conditions for various types of AVEs like standard absolute value equation (AVE), Generalized AVE (GAVE), New generalized AVE (NGAVE), Triple AVE (TAVE) and a class of NGAVE based on interval matrix, P-matrix, singular value conditions, spectral radius and $\mathcal{W}$-property. Based on the unique solution of AVEs, we also discussed unique solvability conditions for linear complementarity problems (LCP) and horizontal linear complementarity problems (HLCP).

Authors:Hyungki Im, Paul Grigas

Abstract: We consider distributionally robust optimization (DRO) problems, reformulated as distributionally robust feasibility (DRF) problems, with multiple expectation constraints. We propose a generic stochastic first-order meta-algorithm, where the decision variables and uncertain distribution parameters are each updated separately by applying stochastic first-order methods. We then specialize our results to the case of using two specific versions of stochastic mirror descent (SMD): (i) a novel approximate version of SMD to update the decision variables, and (ii) the bandit mirror descent method to update the distribution parameters in the case of $\chi^2$-divergence sets. For this specialization, we demonstrate that the total number of iterations is independent of the dimensions of the decision variables and distribution parameters. Moreover, the cost per iteration to update both sets of variables is nearly independent of the dimension of the distribution parameters, allowing for high dimensional ambiguity sets. Furthermore, we show that the total number of iterations of our algorithm has a logarithmic dependence on the number of constraints. Experiments on logistic regression with fairness constraints, personalized parameter selection in a social network, and the multi-item newsvendor problem verify the theoretical results and show the usefulness of the algorithm, in particular when the dimension of the distribution parameters is large.

Authors:Aleksandr Lobanov, Alexander Gasnikov, Fedor Stonyakin

Abstract: In this paper, we study the black box optimization problem under the Polyak--Lojasiewicz (PL) condition, assuming that the objective function is not just smooth, but has higher smoothness. By using "kernel-based" approximation instead of the exact gradient in Stochastic Gradient Descent method, we improve the best known results of convergence in the class of gradient-free algorithms solving problem under PL condition. We generalize our results to the case where a zero-order oracle returns a function value at a point with some adversarial noise. We verify our theoretical results on the example of solving a system of nonlinear equations.

Authors:Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, Eric Moulines

Abstract: This paper delves into stochastic optimization problems that involve Markovian noise. We present a unified approach for the theoretical analysis of first-order gradient methods for stochastic optimization and variational inequalities. Our approach covers scenarios for both non-convex and strongly convex minimization problems. To achieve an optimal (linear) dependence on the mixing time of the underlying noise sequence, we use the randomized batching scheme, which is based on the multilevel Monte Carlo method. Moreover, our technique allows us to eliminate the limiting assumptions of previous research on Markov noise, such as the need for a bounded domain and uniformly bounded stochastic gradients. Our extension to variational inequalities under Markovian noise is original. Additionally, we provide lower bounds that match the oracle complexity of our method in the case of strongly convex optimization problems.

Authors:Paul Häusner, Ozan Öktem, Jens Sjölund

Abstract: In this paper, we develop a novel data-driven approach to accelerate solving large-scale linear equation systems encountered in scientific computing and optimization. Our method utilizes self-supervised training of a graph neural network to generate an effective preconditioner tailored to the specific problem domain. By replacing conventional hand-crafted preconditioners used with the conjugate gradient method, our approach, named neural incomplete factorization (NeuralIF), significantly speeds-up convergence and computational efficiency. At the core of our method is a novel message-passing block, inspired by sparse matrix theory, that aligns with the objective to find a sparse factorization of the matrix. We evaluate our proposed method on both a synthetic and a real-world problem arising from scientific computing. Our results demonstrate that NeuralIF consistently outperforms the most common general-purpose preconditioners, including the incomplete Cholesky method, achieving competitive performance across various metrics even outside the training data distribution.

Authors:T. J. Meijer, V. S. Dolk, W. P. M. H. Heemels

Abstract: By computing Lyapunov functions of a certain, convenient structure, Lyapunov-based methods guarantee stability properties of the system or, when performing synthesis, of the relevant closed-loop or error dynamics. In doing so, they provide conclusive affirmative answers to many analysis and design questions in systems and control. When these methods fail to produce a feasible solution, however, they often remain inconclusive due to (a) the method being conservative or (b) the fact that there may be multiple causes for infeasibility, such as ill-conditioning, solver tolerances or true infeasibility. To overcome this, we develop LMI-based theorems of alternatives based upon which we can guarantee, by computing a so-called certificate of nonexistence, that no poly-quadratic Lyapunov function exists for a given linear parameter-varying system. We extend these ideas to also certify the nonexistence of controllers and observers for which the corresponding closed-loop/error dynamics admit a poly-quadratic Lyapunov function. Finally, we illustrate our results in some numerical case studies.

Authors:Marco Rando, Cesare Molinari, Lorenzo Rosasco, Silvia Villa

Abstract: Finite-difference methods are a class of algorithms designed to solve black-box optimization problems by approximating a gradient of the target function on a set of directions. In black-box optimization, the non-smooth setting is particularly relevant since, in practice, differentiability and smoothness assumptions cannot be verified. To cope with nonsmoothness, several authors use a smooth approximation of the target function and show that finite difference methods approximate its gradient. Recently, it has been proved that imposing a structure in the directions allows improving performance. However, only the smooth setting was considered. To close this gap, we introduce and analyze O-ZD, the first structured finite-difference algorithm for non-smooth black-box optimization. Our method exploits a smooth approximation of the target function and we prove that it approximates its gradient on a subset of random {\em orthogonal} directions. We analyze the convergence of O-ZD under different assumptions. For non-smooth convex functions, we obtain the optimal complexity. In the non-smooth non-convex setting, we characterize the number of iterations needed to bound the expected norm of the smoothed gradient. For smooth functions, our analysis recovers existing results for structured zeroth-order methods for the convex case and extends them to the non-convex setting. We conclude with numerical simulations where assumptions are satisfied, observing that our algorithm has very good practical performances.

Authors:Johannes Aspman, Gilles Bareilles, Vyacheslav Kungurtsev, Jakub Marecek, Martin Takáč

Abstract: The Moment/Sum-of-squares hierarchy provides a way to compute the global minimizers of polynomial optimization problems (POP), at the cost of solving a sequence of increasingly large semidefinite programs (SDPs). We consider large-scale POPs, for which interior-point methods are no longer able to solve the resulting SDPs. We propose an algorithm that combines a first-order method for solving the SDP relaxation, and a second-order method on a non-convex problem obtained from the POP. The switch from the first to the second-order method is based on a quantitative criterion, whose satisfaction ensures that Newton's method converges quadratically from its first iteration. This criterion leverages the point-estimation theory of Smale and the active-set identification. We illustrate the methodology to obtain global minimizers of large-scale optimal power flow problems.

Authors:David Martínez-Rubio, Christophe Roux, Christopher Criscitiello, Sebastian Pokutta

Abstract: In this work, we study optimization problems of the form $\min_x \max_y f(x, y)$, where $f(x, y)$ is defined on a product Riemannian manifold $\mathcal{M} \times \mathcal{N}$ and is $\mu_x$-strongly geodesically convex (g-convex) in $x$ and $\mu_y$-strongly g-concave in $y$, for $\mu_x, \mu_y \geq 0$. We design accelerated methods when $f$ is $(L_x, L_y, L_{xy})$-smooth and $\mathcal{M}$, $\mathcal{N}$ are Hadamard. To that aim we introduce new g-convex optimization results, of independent interest: we show global linear convergence for metric-projected Riemannian gradient descent and improve existing accelerated methods by reducing geometric constants. Additionally, we complete the analysis of two previous works applying to the Riemannian min-max case by removing an assumption about iterates staying in a pre-specified compact set.

Authors:Jiseok Chae, Kyuwon Kim, Donghwan Kim

Abstract: Minimax problems are notoriously challenging to optimize. However, we demonstrate that the two-timescale extragradient can be a viable solution. By utilizing dynamical systems theory, we show that it converges to points that satisfy the second-order necessary condition of local minimax points, under a mild condition. This work surpasses all previous results as we eliminate a crucial assumption that the Hessian, with respect to the maximization variable, is nondegenerate.

Authors:Megan Giron, Georgios Korpas, Waqas Parvaiz, Prashant Malik, Johannes Aspman

Abstract: Collateral optimization refers to the systematic allocation of financial assets to satisfy obligations or secure transactions, while simultaneously minimizing costs and optimizing the usage of available resources. {This involves assessing number of characteristics, such as cost of funding and quality of the underlying assets to ascertain the optimal collateral quantity to be posted to cover exposure arising from a given transaction or a set of transactions. One of the common objectives is to minimise the cost of collateral required to mitigate the risk associated with a particular transaction or a portfolio of transactions while ensuring sufficient protection for the involved parties}. Often, this results in a large-scale combinatorial optimization problem. In this study, we initially present a Mixed Integer Linear Programming (MILP) formulation for the collateral optimization problem, followed by a Quadratic Unconstrained Binary optimization (QUBO) formulation in order to pave the way towards approaching the problem in a hybrid-quantum and NISQ-ready way. We conduct local computational small-scale tests using various Software Development Kits (SDKs) and discuss the behavior of our formulations as well as the potential for performance enhancements. We further survey the recent literature that proposes alternative ways to attack combinatorial optimization problems suitable for collateral optimization.

Authors:Liangzu Peng, René Vidal

Abstract: Block coordinate descent is an optimization paradigm that iteratively updates one block of variables at a time, making it quite amenable to big data applications due to its scalability and performance. Its convergence behavior has been extensively studied in the (block-wise) convex case, but it is much less explored in the non-convex case. In this paper we analyze the convergence of block coordinate methods on non-convex sets and derive convergence rates on smooth manifolds under natural or weaker assumptions than prior work. Our analysis applies to many non-convex problems (e.g., generalized PCA, optimal transport, matrix factorization, Burer-Monteiro factorization, outlier-robust estimation, alternating projection, maximal coding rate reduction, neural collapse, adversarial attacks, homomorphic sensing), either yielding novel corollaries or recovering previously known results.

Authors:Qingyuan Liu, Zhengchao Huang, Hao Ye, Dexian Huang, Chao Shang

Abstract: The alternating direction method of multipliers (ADMM) has been widely adopted in low-rank approximation and low-order model identification tasks; however, the performance of nonconvex ADMM is highly reliant on the choice of penalty parameter. To accelerate ADMM for solving rankconstrained identification problems, this paper proposes a new self-adaptive strategy for automatic penalty update. Guided by first-order analysis of the increment of the augmented Lagrangian, the self-adaptive penalty updating enables effective and balanced minimization of both primal and dual residuals and thus ensures a stable convergence. Moreover, improved efficiency can be obtained within the Anderson acceleration scheme. Numerical examples show that the proposed strategy significantly accelerates the convergence of nonconvex ADMM while alleviating the critical reliance on tedious tuning of penalty parameters.

Authors:Ying Cui, Junyi Liu, Jong-Shi Pang

Abstract: There are many significant applied contexts that require the solution of discontinuous optimization problems in finite dimensions. Yet these problems are very difficult, both computationally and analytically. With the functions being discontinuous and a minimizer (local or global) of the problems, even if it exists, being impossible to verifiably compute, a foremost question is what kind of ''stationary solutions'' one can expect to obtain; these solutions provide promising candidates for minimizers; i.e., their defining conditions are necessary for optimality. Motivated by recent results on sparse optimization, we introduce in this paper such a kind of solution, termed ''pseudo B- (for Bouligand) stationary solution'', for a broad class of discontinuous piecewise continuous optimization problems with objective and constraint defined by indicator functions of the positive real axis composite with functions that are possibly nonsmooth. We present two approaches for computing such a solution. One approach is based on lifting the problem to a higher dimension via the epigraphical formulation of the indicator functions; this requires the addition of some auxiliary variables. The other approach is based on certain continuous (albeit not necessarily differentiable) piecewise approximations of the indicator functions and the convergence to a pseudo B-stationary solution of the original problem is established. The conditions for convergence are discussed and illustrated by an example.

Authors:Juanjuan Xu, Huanshui Zhang

Abstract: In this paper, we study the linear quadratic (LQ) optimal control problem of linear systems with private input and measurement information. The main challenging lies in the unavailability of other regulators' historical input information. To overcome this difficulty, we introduce a kind of novel observers by using the private input and measurement information and accordingly design a kind of new decentralized controllers. In particular, it is verified that the corresponding cost function under the proposed decentralized controllers are asymptotically optimal as comparison with the optimal cost under optimal state-feedback controller. The presented results in this paper are new to the best of our knowledge, which represent the fundamental contribution to classical decentralized control.

Authors:Jianzhou Luo, Dingchuan Yang, Ke Wei

Abstract: The Sinkhorn algorithm is a widely used method for solving the optimal transport problem, and the Greenkhorn algorithm is one of its variants. While there are modified versions of these two algorithms whose computational complexities are $O({n^2\|C\|_\infty^2\log n}/{\varepsilon^2})$ to achieve an $\varepsilon$-accuracy, the best known complexities for the vanilla versions are $O({n^2\|C\|_\infty^3\log n}/{\varepsilon^3})$. In this paper we fill this gap and show that the complexities of the vanilla Sinkhorn and Greenkhorn algorithms are indeed $O({n^2\|C\|_\infty^2\log n}/{\varepsilon^2})$. The analysis relies on the equicontinuity of the dual variables of the entropic regularized optimal transport problem, which is of independent interest.

Authors:Siddhartha Ganguly, Souvik Das, Debasish Chatterjee, Ravi Banavar

Abstract: Limited bandwidth and limited saturation in actuators are practical concerns in control systems. Mathematically, these limitations manifest as constraints being imposed on the control actions, their rates of change, and more generally, the global behavior of their paths. While the problem of actuator saturation has been studied extensively, little attention has been devoted to the problem of actuators having limited bandwidth. While attempts have been made in the direction of incorporating frequency constraints on state-action trajectories before, rate constraints on the control at the design stage have not been studied extensively in the discrete-time regime. This article contributes toward filling this lacuna. In particular, we establish a new discrete-time Pontryagin maximum principle with rate constraints being imposed on the control trajectories, and derive first-order necessary conditions for optimality. A brief discussion on the existence of optimal control is included, and numerical examples are provided to illustrate the results.

Authors:Sander Gribling, Sven Polak, Lucas Slot

Abstract: The moment-sum-of-squares (moment-SOS) hierarchy is one of the most celebrated and widely applied methods for approximating the minimum of an n-variate polynomial over a feasible region defined by polynomial (in)equalities. A key feature of the hierarchy is that, at a fixed level, it can be formulated as a semidefinite program of size polynomial in the number of variables n. Although this suggests that it may therefore be computed in polynomial time, this is not necessarily the case. Indeed, as O'Donnell (2017) and later Raghavendra & Weitz (2017) show, there exist examples where the sos-representations used in the hierarchy have exponential bit-complexity. We study the computational complexity of the moment-SOS hierarchy, complementing and expanding upon earlier work of Raghavendra & Weitz (2017). In particular, we establish algebraic and geometric conditions under which polynomial-time computation is guaranteed to be possible.

Authors:Huikang Liu, Xiao Li, Anthony Man-Cho So

Abstract: This work presents ReSync, a Riemannian subgradient-based algorithm for solving the robust rotation synchronization problem, which arises in various engineering applications. ReSync solves a least-unsquared minimization formulation over the rotation group, which is nonsmooth and nonconvex, and aims at recovering the underlying rotations directly. We provide strong theoretical guarantees for ReSync under the random corruption setting. Specifically, we first show that the initialization procedure of ReSync yields a proper initial point that lies in a local region around the ground-truth rotations. We next establish the weak sharpness property of the aforementioned formulation and then utilize this property to derive the local linear convergence of ReSync to the ground-truth rotations. By combining these guarantees, we conclude that ReSync converges linearly to the ground-truth rotations under appropriate conditions. Experiment results demonstrate the effectiveness of ReSync.

Authors:Cristina Bazgan, Arne Herzel, Stefan Ruzika, Clemens Thielen, Daniel Vanderpooten

Abstract: It is well known that, under very weak assumptions, multiobjective optimization problems admit $(1+\varepsilon,\dots,1+\varepsilon)$-approximation sets (also called $\varepsilon$-Pareto sets) of polynomial cardinality (in the size of the instance and in $\frac{1}{\varepsilon}$). While an approximation guarantee of $1+\varepsilon$ for any $\varepsilon>0$ is the best one can expect for singleobjective problems (apart from solving the problem to optimality), even better approximation guarantees than $(1+\varepsilon,\dots,1+\varepsilon)$ can be considered in the multiobjective case since the approximation might be exact in some of the objectives. Hence, in this paper, we consider partially exact approximation sets that require to approximate each feasible solution exactly, i.e., with an approximation guarantee of $1$, in some of the objectives while still obtaining a guarantee of $1+\varepsilon$ in all others. We characterize the types of polynomial-cardinality, partially exact approximation sets that are guaranteed to exist for general multiobjective optimization problems. Moreover, we study minimum-cardinality partially exact approximation sets concerning (weak) efficiency of the contained solutions and relate their cardinalities to the minimum cardinality of a $(1+\varepsilon,\dots,1+\varepsilon)$-approximation set.

Authors:Stephan Helfrich, Stefan Ruzika, Clemens Thielen

Abstract: Convex approximation sets for multiobjective optimization problems are a well-studied relaxation of the common notion of approximation sets. Instead of approximating each image of a feasible solution by the image of some solution in the approximation set up to a multiplicative factor in each component, a convex approximation set only requires this multiplicative approximation to be achieved by some convex combination of finitely many images of solutions in the set. This makes convex approximation sets efficiently computable for a wide range of multiobjective problems - even for many problems for which (classic) approximations sets are hard to compute. In this article, we propose a polynomial-time algorithm to compute convex approximation sets that builds upon an exact or approximate algorithm for the weighted sum scalarization and is, therefore, applicable to a large variety of multiobjective optimization problems. The provided convex approximation quality is arbitrarily close to the approximation quality of the underlying algorithm for the weighted sum scalarization. In essence, our algorithm can be interpreted as an approximate variant of the dual variant of Benson's Outer Approximation Algorithm. Thus, in contrast to existing convex approximation algorithms from the literature, information on solutions obtained during the approximation process is utilized to significantly reduce both the practical running time and the cardinality of the returned solution sets while still guaranteeing the same worst-case approximation quality. We underpin these advantages by the first comparison of all existing convex approximation algorithms on several instances of the triobjective knapsack problem and the triobjective symmetric metric traveling salesman problem.

Authors:Concepción Domínguez, Ricardo Gázquez, Juan Miguel Morales, Salvador Pineda

Abstract: In the Maximum Capture Facility Location (MCFL) problem with a binary choice rule, a company intends to locate a series of facilities to maximize the captured demand, and customers patronize the facility that maximizes their utility. In this work, we generalize the MCFL problem assuming that the facilities of the decision maker act cooperatively to increase the customers' utility over the company. We propose a utility maximization rule between the captured utility of the decision maker and the opt-out utility of a competitor already installed in the market. Furthermore, we model the captured utility by means of an Ordered Median function (OMf) of the partial utilities of newly open facilities. We name this problem "the Cooperative Maximum Capture Facility Location problem" (CMCFL). The OMf serves as a means to compute the utility of each customer towards the company as an aggregation of ordered partial utilities, and constitutes a unifying framework for CMCFL models. We introduce a multiperiod non-linear bilevel formulation for the CMCFL with an embedded assignment problem characterizing the captured utilities. For this model, two exact resolution approaches are presented: a MILP reformulation with valid inequalities and an effective approach based on Benders' decomposition. Extensive computational experiments are provided to test our results with randomly generated data and an application to the location of charging stations for electric vehicles in the city of Trois-Rivi\`eres, Qu\`ebec, is addressed.

Authors:Stephan Helfrich, Arne Herzel, Stefan Ruzika, Clemens Thielen

Abstract: We study the approximation of general multiobjective optimization problems with the help of scalarizations. Existing results state that multiobjective minimization problems can be approximated well by norm-based scalarizations. However, for multiobjective maximization problems, only impossibility results are known so far. Countering this, we show that all multiobjective optimization problems can, in principle, be approximated equally well by scalarizations. In this context, we introduce a transformation theory for scalarizations that establishes the following: Suppose there exists a scalarization that yields an approximation of a certain quality for arbitrary instances of multiobjective optimization problems with a given decomposition specifying which objective functions are to be minimized / maximized. Then, for each other decomposition, our transformation yields another scalarization that yields the same approximation quality for arbitrary instances of problems with this other decomposition. In this sense, the existing results about the approximation via scalarizations for minimization problems carry over to any other objective decomposition -- in particular, to maximization problems -- when suitably adapting the employed scalarization. We further provide necessary and sufficient conditions on a scalarization such that its optimal solutions achieve a constant approximation quality. We give an upper bound on the best achievable approximation quality that applies to general scalarizations and is tight for the majority of norm-based scalarizations applied in the context of multiobjective optimization. As a consequence, none of these norm-based scalarizations can induce approximation sets for optimization problems with maximization objectives, which unifies and generalizes the existing impossibility results concerning the approximation of maximization problems.

Authors:Xiaomeng Chen, Wei Jiang, Themistoklis Charalambous, Ling Shi

Abstract: This paper addresses the problem of distributed optimization, where a network of agents represented as a directed graph (digraph) aims to collaboratively minimize the sum of their individual cost functions. Existing approaches for distributed optimization over digraphs, such as Push-Pull, require agents to exchange explicit state values with their neighbors in order to reach an optimal solution. However, this can result in the disclosure of sensitive and private information. To overcome this issue, we propose a state-decomposition-based privacy-preserving finite-time push-sum (PrFTPS) algorithm without any global information such as network size or graph diameter. Then, based on PrFTPS, we design a gradient descent algorithm (PrFTPS-GD) to solve the distributed optimization problem. It is proved that under PrFTPS-GD, the privacy of each agent is preserved and the linear convergence rate related to the optimization iteration number is achieved. Finally, numerical simulations are provided to illustrate the effectiveness of the proposed approach.

Authors:Peter Richtárik, Elnur Gasanov, Konstantin Burlachenko

Abstract: We provide the first proof that gradient descent $\left({\color{green}\sf GD}\right)$ with greedy sparsification $\left({\color{green}\sf TopK}\right)$ and error feedback $\left({\color{green}\sf EF}\right)$ can obtain better communication complexity than vanilla ${\color{green}\sf GD}$ when solving the distributed optimization problem $\min_{x\in \mathbb{R}^d} {f(x)=\frac{1}{n}\sum_{i=1}^n f_i(x)}$, where $n$ = # of clients, $d$ = # of features, and $f_1,\dots,f_n$ are smooth nonconvex functions. Despite intensive research since 2014 when ${\color{green}\sf EF}$ was first proposed by Seide et al., this problem remained open until now. We show that ${\color{green}\sf EF}$ shines in the regime when features are rare, i.e., when each feature is present in the data owned by a small number of clients only. To illustrate our main result, we show that in order to find a random vector $\hat{x}$ such that $\lVert {\nabla f(\hat{x})} \rVert^2 \leq \varepsilon$ in expectation, ${\color{green}\sf GD}$ with the ${\color{green}\sf Top1}$ sparsifier and ${\color{green}\sf EF}$ requires ${\cal O} \left(\left( L+{\color{blue}r} \sqrt{ \frac{{\color{red}c}}{n} \min \left( \frac{{\color{red}c}}{n} \max_i L_i^2, \frac{1}{n}\sum_{i=1}^n L_i^2 \right) }\right) \frac{1}{\varepsilon} \right)$ bits to be communicated by each worker to the server only, where $L$ is the smoothness constant of $f$, $L_i$ is the smoothness constant of $f_i$, ${\color{red}c}$ is the maximal number of clients owning any feature ($1\leq {\color{red}c} \leq n$), and ${\color{blue}r}$ is the maximal number of features owned by any client ($1\leq {\color{blue}r} \leq d$). Clearly, the communication complexity improves as ${\color{red}c}$ decreases (i.e., as features become more rare), and can be much better than the ${\cal O}({\color{blue}r} L \frac{1}{\varepsilon})$ communication complexity of ${\color{green}\sf GD}$ in the same regime.

Authors:Yulle G. F. Borges, Rafael C. S. Schouery, Flávio K. Miyazawa

Abstract: This paper focuses on exact approaches for the Colored Bin Packing Problem (CBPP), a generalization of the classical one-dimensional Bin Packing Problem in which each item has, in addition to its length, a color, and no two items of the same color can appear consecutively in the same bin. To simplify modeling, we present a characterization of any feasible packing of this problem in a way that does not depend on its ordering. Furthermore, we present four exact algorithms for the CBPP. First, we propose a generalization of Val\'erio de Carvalho's arc flow formulation for the CBPP using a graph with multiple layers, each representing a color. Second, we present an improved arc flow formulation that uses a more compact graph and has the same linear relaxation bound as the first formulation. And finally, we design two exponential set-partition models based on reductions to a generalized vehicle routing problem, which are solved by a branch-cut-and-price algorithm through VRPSolver. To compare the proposed algorithms, a varied benchmark set with 574 instances of the CBPP is presented. Results show that the best model, our improved arc flow formulation, was able to solve over 62% of the proposed instances to optimality, the largest of which with 500 items and 37 colors. While being able to solve fewer instances in total, the set-partition models exceeded their arc flow counterparts in instances with a very small number of colors.

Authors:Axel Ringh, Isabel Haasler, Yongxin Chen, Johan Karlsson

Abstract: In this work we consider mean field type control problems with multiple species that have different dynamics. We formulate the discretized problem using a new type of entropy-regularized multimarginal optimal transport problems where the cost is a decomposable structured tensor. A novel algorithm for solving such problems is derived, using this structure and leveraging recent results in entropy-regularized optimal transport. The algorithm is then demonstrated on a numerical example in robot coordination problem for search and rescue, where three different types of robots are used to cover a given area at minimal cost.

Authors:Han Zhang, Axel Ringh

Abstract: Inverse Optimal Control (IOC) is a powerful framework for learning a behaviour from observations of experts. The framework aims to identify the underlying cost function that the observed optimal trajectories (the experts' behaviour) are optimal with respect to. In this work, we considered the case of identifying the cost and the feedback law from observed trajectories generated by an ``average cost per stage" linear quadratic regulator. We show that identifying the cost is in general an ill-posed problem, and give necessary and sufficient conditions for non-identifiability. Moreover, despite the fact that the problem is in general ill-posed, we construct an estimator for the cost function and show that the control gain corresponding to this estimator is a statistically consistent estimator for the true underlying control gain. In fact, the constructed estimator is based on convex optimization, and hence the proved statistical consistency is also observed in practice. We illustrate the latter by applying the method on a simulation example from rehabilitation robotics.

Authors:Yulle G. F. Borges, Vinícius L. de Lima, Flávio K. Miyazawa, Lehilton L. C. Pedrosa, Thiago A. de Queiroz, Rafael C. S. Schouery

Abstract: This paper presents theoretical and practical results for the bin packing problem with scenarios, a generalization of the classical bin packing problem which considers the presence of uncertain scenarios, of which only one is realized. For this problem, we propose an absolute approximation algorithm whose ratio is bounded by the square root of the number of scenarios times the approximation ratio for an algorithm for the vector bin packing problem. We also show how an asymptotic polynomial-time approximation scheme is derived when the number of scenarios is constant. As a practical study of the problem, we present a branch-and-price algorithm to solve an exponential model and a variable neighborhood search heuristic. To speed up the convergence of the exact algorithm, we also consider lower bounds based on dual feasible functions. Results of these algorithms show the competence of the branch-and-price in obtaining optimal solutions for about 59% of the instances considered, while the combined heuristic and branch-and-price optimally solved 62% of the instances considered.

Authors:Hanchao Liu, Dena Firoozi, Michèle Breton

Abstract: Risk sensitivity plays an important role in the study of finance and economics as risk-neutral models cannot capture and justify all economic behaviors observed in reality. Risk-sensitive mean field game theory was developed recently for systems where there exists a large number of indistinguishable, asymptotically negligible and heterogeneous risk-sensitive players, who are coupled via the empirical distribution of state across population. In this work, we extend the theory of Linear Quadratic Gaussian risk-sensitive mean-field games to the setup where there exists one major agent as well as a large number of minor agents. The major agent has a significant impact on each minor agent and its impact does not collapse with the increase in the number of minor agents. Each agent is subject to linear dynamics with an exponential-of-integral quadratic cost functional. Moreover, all agents interact via the average state of minor agents (so-called empirical mean field) and the major agent's state. We develop a variational analysis approach to derive the best response strategies of agents in the limiting case where the number of agents goes to infinity. We establish that the set of obtained best-response strategies yields a Nash equilibrium in the limiting case and an $\varepsilon$-Nash equilibrium in the finite player case. We conclude the paper with an illustrative example.

Authors:Jérôme Bolte, Edouard Pauwels, Samuel Vaiter

Abstract: In appropriate frameworks, automatic differentiation is transparent to the user at the cost of being a significant computational burden when the number of operations is large. For iterative algorithms, implicit differentiation alleviates this issue but requires custom implementation of Jacobian evaluation. In this paper, we study one-step differentiation, also known as Jacobian-free backpropagation, a method as easy as automatic differentiation and as performant as implicit differentiation for fast algorithms (e.g., superlinear optimization methods). We provide a complete theoretical approximation analysis with specific examples (Newton's method, gradient descent) along with its consequences in bilevel optimization. Several numerical examples illustrate the well-foundness of the one-step estimator.

Authors:Bernhard Maschke, Arjan van der Schaft

Abstract: In this paper we extend the previously introduced class of boundary port-Hamiltonian systems to boundary control systems where the variational derivative of the Hamiltonian functional is replaced by a pair of reciprocal differential operators. In physical systems modelling, these differential operators naturally represent the constitutive relations associated with the implicitly defined energy of the system and obey Maxwell's reciprocity conditions. On top of the boundary variables associated with the Stokes-Dirac structure, this leads to additional boundary port variables and to the new notion of a Stokes-Lagrange subspace. This extended class of boundary port-Hamiltonian systems is illustrated by a number of examples in the modelling of elastic rods with local and non-local elasticity relations. Finally it shown how a Hamiltonian functional on an extended state space can be associated with the Stokes-Lagrange subspace, and how this leads to an energy balance equation involving the boundary variables of the Stokes-Dirac structure as well as of the Stokes-Lagrange subspace.

Authors:Dusan Jakovetic, Natasa Krejic, Greta Malaspina

Abstract: We consider two formulations for distributed optimization wherein $N$ agents in a generic connected network solve a problem of common interest: distributed personalized optimization and consensus optimization. A new method termed DINAS (Distributed Inexact Newton method with Adaptive Stepsize) is proposed. DINAS employs large adaptively computed step-sizes, requires a reduced global parameters knowledge with respect to existing alternatives, and can operate without any local Hessian inverse calculations nor Hessian communications. When solving personalized distributed learning formulations, DINAS achieves quadratic convergence with respect to computational cost and linear convergence with respect to communication cost, the latter rate being independent of the local functions condition numbers or of the network topology. When solving consensus optimization problems, DINAS is shown to converge to the global solution. Extensive numerical experiments demonstrate significant improvements of DINAS over existing alternatives. As a result of independent interest, we provide for the first time convergence analysis of the Newton method with the adaptive Polyak's step-size when the Newton direction is computed inexactly in centralized environment.

Authors:Mingjie Hu, Jie Yan, Liting Chen, Qingwei Lin

Abstract: This paper investigates the column generation (CG) for solving cutting stock problems (CSP). Traditional CG method, which repeatedly solves a restricted master problem (RMP), often suffers from two critical issues in practice -- the loss of solution quality introduced by linear relaxation of both feasible domain and objective and the high time cost of last iterations close to convergence. We empirically find that the first issue is common in ordinary CSPs with linear cutting constraints, while the second issue is especially severe in CSPs with nonlinear cutting constraints that are often generated by approximating chance constraints. We propose an alternative approach, ensembles of multiple column generation processes. In particular, we present two methods -- \mc (multi-column) which return multiple feasible columns in each RMP iteration, and \mt (multi-path) which restarts the RMP iterations from different initialized column sets once the iteration time exceeds a given time limit. The ideas behind are same: leverage the multiple column generation pathes to compensate the loss induced by relaxation, and add earlier sub-optimal columns to accelerate convergence of RMP iterations. Besides, we give theoretical analysis on performance improvement guarantees. Experiments on cutting stock problems demonstrate that compared to traditional CG, our method achieves significant run-time reduction on CSPs with nonlinear constraints, and dramatically improves the ratio of solve-to-optimal on CSPs with linear constraints.

Authors:Aayushya Agarwal, Carmel Fiscko, Soummya Kar, Larry Pileggi, Bruno Sinopoli

Abstract: We introduce a new workflow for unconstrained optimization whereby objective functions are mapped onto a physical domain to more easily design algorithms that are robust to hyperparameters and achieve fast convergence rates. Specifically, we represent optimization problems as an equivalent circuit that are then solved solely as nonlinear circuits using robust solution methods. The equivalent circuit models the trajectory of component-wise scaled gradient flow problem as the transient response of the circuit for which the steady-state coincides with a critical point of the objective function. The equivalent circuit model leverages circuit domain knowledge to methodically design new optimization algorithms that would likely not be developed without a physical model. We incorporate circuit knowledge into optimization methods by 1) enhancing the underlying circuit model for fast numerical analysis, 2) controlling the optimization trajectory by designing the nonlinear circuit components, and 3) solving for step sizes using well-known methods from the circuit simulation. We first establish the necessary conditions that the controls must fulfill for convergence. We show that existing descent algorithms can be re-derived as special cases of this approach and derive new optimization algorithms that are developed with insights from a circuit-based model. The new algorithms can be designed to be robust to hyperparameters, achieve convergence rates comparable or faster than state of the art methods, and are applicable to optimizing a variety of both convex and nonconvex problems.

Authors:Xiao Li, Lei Zhao, Daoli Zhu, Anthony Man-Cho So

Abstract: The subgradient method is one of the most fundamental algorithmic schemes for nonsmooth optimization. The existing complexity and convergence results for this algorithm are mainly derived for Lipschitz continuous objective functions. In this work, we first extend the typical complexity results for the subgradient method to convex and weakly convex minimization without assuming Lipschitz continuity. Specifically, we establish $\mathcal{O}(1/\sqrt{T})$ bound in terms of the suboptimality gap ``$f(x) - f^*$'' for convex case and $\mathcal{O}(1/{T}^{1/4})$ bound in terms of the gradient of the Moreau envelope function for weakly convex case. Furthermore, we provide convergence results for non-Lipschitz convex and weakly convex objective functions using proper diminishing rules on the step sizes. In particular, when $f$ is convex, we show $\mathcal{O}(\log(k)/\sqrt{k})$ rate of convergence in terms of the suboptimality gap. With an additional quadratic growth condition, the rate is improved to $\mathcal{O}(1/k)$ in terms of the squared distance to the optimal solution set. When $f$ is weakly convex, asymptotic convergence is derived. The central idea is that the dynamics of properly chosen step sizes rule fully controls the movement of the subgradient method, which leads to boundedness of the iterates, and then a trajectory-based analysis can be conducted to establish the desired results. To further illustrate the wide applicability of our framework, we extend the complexity results to the truncated subgradient, the stochastic subgradient, the incremental subgradient, and the proximal subgradient methods for non-Lipschitz functions.

Authors:Fritz Colonius, Alexandre J. Santana

Abstract: Affine flows on vector bundles with chain transitive base flow are lifted to linear flows and the decomposition into exponentially separated subbundles provided by Selgrade's theorem is determined. The results are illustrated by an application to affine control systems with bounded control range.

Authors:Peng Li, Bo Liu

Abstract: Scheduling problems are often tackled independently, and rarely solved by leveraging the commonalities across problems. Lack of awareness of this inter-task similarity could impede the search efficacy. A quantifiable relationship between scheduling problems is to-date rather unclear, how to leverage it in combinatorial optimization remains largely unknown, and its effects on search are also undeterminable. This paper addresses these hard questions by delving into quantifiable useful inter-task relationships and, through leveraging the explicit relationship, presenting a speed-up algorithm. After deriving an analytical inter-task distance metric to quantitatively reveal latent similarity across scheduling problems, an adaptive transfer of multi-modality knowledge is devised to promptly adjust the transfer in forms of explicit and implicit knowledge in response to heterogeneity in the inter-task discrepancy. For faintly related problems with disappearing dependences, a problem transformation function is suggested with a matching-feature-based greedy policy, and the function projects faintly related problems into a latent space where these problems gain similarity in a way that creates search speed-ups. Finally, a multi-task scatter search combinatorial algorithm is formed and a large-scale multi-task benchmark is generated serving the purposes of validation. That the algorithm exhibits dramatic speed-ups of 2~3 orders of magnitude, as compared to direct problem solving in strongly related problems and 3 times faster in weakly related ones, suggests leveraging commonality across problems could be successful.

Authors:Yingzhao Lian, Matteo Tacchi, Colin Jones

Abstract: In this era of digitalization, data has widely been used in control engineering. While stability analysis is a mainstay for control science, most stability analysis tools still require explicit knowledge of the model or a high-fidelity simulator. In this work, a new data-driven Lyapunov analysis framework is proposed. Without using the model or its simulator, the proposed approach can learn a piece-wise affine Lyapunov function with a finite and fixed off-line dataset. The learnt Lyapunov function is robust to any dynamics that are consistent with the off-line dataset. Along the development of proposed scheme, the Lyapunov stability criterion is generalized. This generalization enables an iterative algorithm to augment the region of attraction.

Authors:Felix Bestehorn, Christoph Hansknecht, Christian Kirches, Paul Manns

Abstract: The combinatorial integral approximation (CIA) is a solution technique for integer optimal control problems. In order to regularize the solutions produced by CIA, one can minimize switching costs in one of its algorithmic steps. This leads to combinatorial optimization problems, which are called switching cost aware rounding problems (SCARP). They can be solved efficiently on one-dimensional domains but no efficient solution algorithms have been found so far for multi-dimensional domains. The CIA problem formulation depends on a discretization grid. We propose to reduce the number of variables and thus improve the computational tractability of SCARP by means of a non-uniform grid refinement strategy. We prove that the grid refinement preserves the approximation properties of the combinatorial integral approximation. Computational results are offered to show that the proposed approach is able to achieve, within a prescribed time limit, smaller duality gaps that does the uniform approach. For several large instances, a dual bound could only be obtained through adaptivity.

Authors:Jin Won Kim, Prashant G. Mehta

Abstract: This paper is concerned with the problem of nonlinear (stochastic) filter stability of a hidden Markov model (HMM) with white noise observations. The main contribution is the variance decay property which is used to conclude filter stability. The property is closely inspired by the Poincar\'e inequality (PI) in the study of stochastic stability of Markov processes. In this paper, the property is related to both the ergodicity of the Markov process as well as the observability of the HMM. The proofs are based upon a recently discovered minimum variance duality which is used to transform the nonlinear filtering problem into a stochastic optimal control problem for a backward stochastic differential equation (BSDE).

Authors:David Könen, Michael Stiglmayr

Abstract: This paper addresses the problem of enumerating all supported efficient solutions for a linear multi-objective integer minimum cost flow problem (MOIMCF). First, we highlight an inconsistency in various definitions of supported nondominated vectors for multi-objective integer linear programs (MOILP). Several characterizations for supported nondominated vectors/efficient solutions are used in the literature, which are equivalent in the non-integer case. However, they may lead to different sets of supported nondominated vectors/efficient solutions for MOILPs. This motivates us to summarize equivalent definitions and characterizations for supported efficient solutions and to distinguish between supported and weakly supported efficient solutions. In this paper we derive an output-polynomial time algorithm to determine all supported efficient solutions for MOIMCF problems. This is the first approach that solves this general problem in output-polynomial time. Moreover, we prove that the existence of an output-polynomial time algorithm to determine all weakly supported nondominated vectors (or all weakly supported efficient solutions) for a MOIMCF problem with a fixed number of d>3 objectives can be excluded, unless P = NP.

Authors:Andrei Agrachev

Abstract: We consider a smooth system of the form $\dot q=f_0(q)+\sum\limits_{i=1}^k u_i f_i(q)$, $q\in M,\ u_i\in\mathbb R,$ and study controllability issues on the group of diffeomorphisms of $M$. It is well-known that the system can arbitrarily well approximate the movement in the direction of any Lie bracket polynomial of $f_1,\ldots,f_k$. Any Lie bracket polynomial of $f_1,\ldots,f_k$ is good in this sense. Moreover, some combinations of Lie brackets which involve the drift term $f_0$ are also good but surely not all of them. In this paper we try to characterize good ones and, in particular, all universal good combinations, which are good for any nilpotent truncation of any system.

Authors:Konstantin Kraus, Kathrin Klamroth, Michael Stiglmayr

Abstract: We consider an online version of a longest path problem in an undirected and planar graph that is motivated by a location and routing problem occurring in the board game "Turn & Taxis". Path extensions have to be selected based on only partial knowledge on the order in which nodes become available in later iterations. Besides board games, online path extension problems have applications in disaster relief management when infrastructure has to be rebuilt after natural disasters. For example, flooding may affect large parts of a road network, and parts of the network may become available only iteratively and decisions may have to be made without the possibility of planning ahead. We suggest and analyse selection criteria that identify promising nodes (locations) for path extensions. We introduce the concept of tentacles of paths as an indicator for the future extendability. Different initialization and extension heuristics are suggested on compared to an ideal solution that is obtained by an integer linear programming formulation assuming complete knowledge, i.e., assuming that the complete sequence in which nodes become available is known beforehand. All algorithms are tested and evaluated on the original "Turn & Taxis" graph, and on an extended version of the "Turn & Taxis" graph, with different parameter settings. The numerical results confirm that the number of tentacles is a useful criterion when selecting path extensions, leading to near-optimal paths at relatively low computational costs.

Authors:Igor G. Vladimirov

Abstract: This paper is concerned with stochastic systems whose state is a diffusion process governed by an Ito stochastic differential equation (SDE). In the framework of a nominal white-noise model, the SDE is driven by a standard Wiener process. For a scenario of statistical uncertainty, where the driving noise acquires a state-dependent drift and thus deviates from its idealised model, we consider the perturbation of the invariant probability density function (PDF) as a steady-state solution of the Fokker-Planck-Kolmogorov equation. We discuss an upper bound on a logarithmic Dirichlet form for the ratio of the invariant PDF to its nominal counterpart in terms of the Kullback-Leibler relative entropy rate of the actual noise distribution with respect the Wiener measure. This bound is shown to be achievable, provided the PDF ratio is preserved by the nominal steady-state probability flux. The logarithmic Dirichlet form bound is used in order to obtain an upper bound on the relative entropy of the perturbed invariant PDF in terms of quadratic-exponential moments of the noise drift in the uniform ellipticity case. These results are illustrated for perturbations of Gaussian invariant measures in linear stochastic systems involving linear noise drifts.

Authors:Xiaoyu Wang, Mikael Johansson, Tong Zhang

Abstract: In machine learning applications, it is well known that carefully designed learning rate (step size) schedules can significantly improve the convergence of commonly used first-order optimization algorithms. Therefore how to set step size adaptively becomes an important research question. A popular and effective method is the Polyak step size, which sets step size adaptively for gradient descent or stochastic gradient descent without the need to estimate the smoothness parameter of the objective function. However, there has not been a principled way to generalize the Polyak step size for algorithms with momentum accelerations. This paper presents a general framework to set the learning rate adaptively for first-order optimization methods with momentum, motivated by the derivation of Polyak step size. It is shown that the resulting methods are much less sensitive to the choice of momentum parameter and may avoid the oscillation of the heavy-ball method on ill-conditioned problems. These adaptive step sizes are further extended to the stochastic settings, which are attractive choices for stochastic gradient descent with momentum. Our methods are demonstrated to be more effective for stochastic gradient methods than prior adaptive step size algorithms in large-scale machine learning tasks.

Authors:Wentao Zhang, Yang Shi, Baoyong Zhang, Deming Yuan

Abstract: In this paper, we consider a distributed online convex optimization problem over a time-varying multi-agent network. The goal of this network is to minimize a global loss function through local computation and communication with neighbors. To effectively handle the optimization problem with a high-dimensional and complicated constraint set, we develop a distributed online multiple Frank-Wolfe algorithm to avoid the expensive computational cost of projection operation. The dynamic regret bounds are established as $\mathcal{O}(T^{1-\gamma}+H_T)$ with the linear oracle number $\mathcal{O} (T^{1+\gamma})$, which depends on the horizon (total iteration number) $T$, the function variation $H_T$, and the tuning parameter $0<\gamma<1$. In particular, when the stringent computation requirement is satisfied, the bound can be enhanced to $\mathcal{O} (1+H_T)$. Moreover, we illustrate the significant advantages of the multiple iteration technique and reveal a trade-off between computational cost and dynamic regret bound. Finally, the performance of our algorithm is verified and compared through the distributed online ridge regression problems with two constraint sets.

Authors:Slavomír Hanzely

Abstract: In this paper, we propose the first sketch-and-project Newton method with fast $\mathcal O(k^{-2})$ global convergence rate for self-concordant functions. Our method, SGN, can be viewed in three ways: i) as a sketch-and-project algorithm projecting updates of Newton method, ii) as a cubically regularized Newton ethod in sketched subspaces, and iii) as a damped Newton method in sketched subspaces. SGN inherits best of all three worlds: cheap iteration costs of sketch-and-project methods, state-of-the-art $\mathcal O(k^{-2})$ global convergence rate of full-rank Newton-like methods and the algorithm simplicity of damped Newton methods. Finally, we demonstrate its comparable empirical performance to baseline algorithms.

Authors:Kananart Kuwaranancharoen, Shreyas Sundaram

Abstract: The problem of finding the minimizer of a sum of convex functions is central to the field of optimization. In cases where the functions themselves are not fully known (other than their individual minimizers and convexity parameters), it is of interest to understand the region containing the potential minimizers of the sum based only on those known quantities. Characterizing this region in the case of multivariate strongly convex functions is far more complicated than the univariate case. In this paper, we provide both outer and inner approximations for the region containing the minimizer of the sum of two strongly convex functions, subject to a constraint on the norm of the gradient at the minimizer of the sum. In particular, we explicitly characterize the boundary and interior of both outer and inner approximations. Interestingly, the boundaries as well as the interiors turn out to be identical and we show that the boundary of the region containing the potential minimizers is also identical to that of the outer and inner approximations.

Authors:Evgenii Chzhen, Sholom Schechtman

Abstract: We consider the problem of unconstrained minimization of finite sums of functions. We propose a simple, yet, practical way to incorporate variance reduction techniques into SignSGD, guaranteeing convergence that is similar to the full sign gradient descent. The core idea is first instantiated on the problem of minimizing sums of convex and Lipschitz functions and is then extended to the smooth case via variance reduction. Our analysis is elementary and much simpler than the typical proof for variance reduction methods. We show that for smooth functions our method gives $\mathcal{O}(1 / \sqrt{T})$ rate for expected norm of the gradient and $\mathcal{O}(1/T)$ rate in the case of smooth convex functions, recovering convergence results of deterministic methods, while preserving computational advantages of SignSGD.

Authors:Lucia Absalom Bautista, Timotej Hrga, Janez Povh, Shudian Zhao

Abstract: The clustering of data is one of the most important and challenging topics in data science. The minimum sum-of-squares clustering (MSSC) problem asks to cluster the data points into $k$ clusters such that the sum of squared distances between the data points and their cluster centers (centroids) is minimized. This problem is NP-hard, but there exist exact solvers that can solve such problem to optimality for small or medium size instances. In this paper, we use a branch-and-bound solver based on semidefinite programming relaxations called SOS-SDP to compute the optimum solutions of the MSSC problem for various $k$ and for multiple datasets, with real and artificial data, for which the data provider has provided ground truth clustering. Next, we use several extrinsic and intrinsic measures to evaluate how the optimum clustering and ground truth clustering matches, and how well these clusterings perform with respect to the criteria underlying the intrinsic measures. Our calculations show that the ground truth clusterings are generally far from the optimum solution to the MSSC problem. Moreover, the intrinsic measures evaluated on the ground truth clusterings are generally significantly worse compared to the optimum clusterings. However, when the ground truth clustering is in the form of convex sets, e.g., ellipsoids, that are well separated from each other, the ground truth clustering comes very close to the optimum clustering.

Authors:Jinhui Hu, Xin Chen, Lifeng Zheng, Ling Zhang, Huaqing Li

Abstract: This paper studies optimization problems over multi-agent systems, in which all agents cooperatively minimize a global objective function expressed as a sum of local cost functions. Each agent in the systems uses only local computation and communication in the overall process without leaking their private information. Based on the Barzilai-Borwein (BB) method and multi-consensus inner loops, a distributed algorithm with the availability of larger stepsizes and accelerated convergence, namely ADBB, is proposed. Moreover, owing to employing only row-stochastic weight matrices, ADBB can resolve the optimization problems over unbalanced directed networks without requiring the knowledge of neighbors' out-degree for each agent. Via establishing contraction relationships between the consensus error, the optimality gap, and the gradient tracking error, ADBB is theoretically proved to converge linearly to the globally optimal solution. A real-world data set is used in simulations to validate the correctness of the theoretical analysis.

Authors:Ryo Fujino

Abstract: Langevin Dynamics has been extensively employed in global non-convex optimization due to the concentration of its stationary distribution around the global minimum of the potential function at low temperatures. In this paper, we propose to utilize a more comprehensive class of stochastic processes, known as reversible diffusion, and apply the Euler-Maruyama discretization for global non-convex optimization. We design the diffusion coefficient to be larger when distant from the optimum and smaller when near, thus enabling accelerated convergence while regulating discretization error, a strategy inspired by landscape modifications. Our proposed method can also be seen as a time change of Langevin Dynamics, and we prove convergence with respect to KL divergence, investigating the trade-off between convergence speed and discretization error. The efficacy of our proposed method is demonstrated through numerical experiments.

Authors:Mohsen Dastpak, Fausto Errico, Ola Jabali, Federico Malucelli

Abstract: We study EVs traveling from origin to destination in the shortest time, focusing on long-distance settings with energy requirements exceeding EV autonomy. The EV may charge its battery at public Charging Stations (CSs), which are subject to uncertain waiting times. We model CSs using appropriately defined queues, whose status is revealed upon the EV arrival. However, we consider the availability of real-time binary Occupancy Indicator (OI) information, signaling if a CS is busy or not. At each OI update, we determine the sequence of CSs to visit along with associated charging quantities. We name the resulting problem the Electric Vehicle Shortest Path Problem with charging station Occupancy Indicator information (EVSPP-OI). In this problem, we consider that the EV is allowed to partially charge its battery, and we model charging times via piecewise linear charging functions that depend on the CS technology. We propose an MDP formulation for the EVSPP-OI and develop a reoptimization algorithm that establishes the sequence of CS visits and charging amounts based on system updates. Specifically, we propose a simulation-based approach to estimate the waiting time of the EV at a CS as a function of its arrival time. As the path to a CS may consist of multiple intermediate CS stops, estimating the arrival times at each CS is fairly intricate. To this end, we propose an efficient heuristic that yields approximate lower bounds on the arrival time of the EV at each CS. We use these estimations to define a deterministic EVSPP, which we solve with an existing algorithm. We conduct a comprehensive computational study and compare the performance of our methodology with a benchmark that observes the status of CSs only upon arrival. Results show that our method reduces waiting times and total trip duration by an average of 23.7%-95.4% and 1.4%-18.5%, respectively.

Authors:Ben Tu, Nikolas Kantas, Robert M. Lee, Behrang Shafei

Abstract: The goal of multi-objective optimization is to identify a collection of points which describe the best possible trade-offs between the multiple objectives. In order to solve this vector-valued optimization problem, practitioners often appeal to the use of scalarization functions in order to transform the multi-objective problem into a collection of single-objective problems. This set of scalarized problems can then be solved using traditional single-objective optimization techniques. In this work, we formalise this convention into a general mathematical framework. We show how this strategy effectively recasts the original multi-objective optimization problem into a single-objective optimization problem defined over sets. An appropriate class of objective functions for this new problem is the R2 utility function, which is defined as a weighted integral over the scalarized optimization problems. We show that this utility function is a monotone and submodular set function, which can be optimised effectively using greedy optimization algorithms. We analyse the performance of these greedy algorithms both theoretically and empirically. Our analysis largely focusses on Bayesian optimization, which is a popular probabilistic framework for black-box optimization.

Authors:Eugenio Pozzoli

Abstract: We consider a bilinear control problem for the wave equation on a torus of arbitrary dimension. We show that the system is globally approximately controllable in arbitrarily small times from a dense family of initial states. The control strategy is explicit, and based on a small-time limit of conjugated dynamics to move along non-directly accessible directions (a.k.a. Lie brackets of the generators).

Authors:Alain Bensoussan, Tak Kwong Wong, Sheung Chi Phillip Yam, Hongwei Yuan

Abstract: In this article, by using several new crucial {\it a priori} estimates which are still absent in the literature, we provide a comprehensive resolution of the first order generic mean field type control problems and also establish the global-in-time classical solutions of their Bellman and master equations. Rather than developing the analytical approach via tackling the Bellman and master equation directly, we apply the maximum principle approach by considering the induced forward-backward ordinary differential equation (FBODE) system; indeed, we first show the local-in-time unique existence of the solution of the FBODE system for a variety of terminal data by Banach fixed point argument, and then provide crucial a priori estimates of bounding the sensitivity of the terminal data for the backward equation by utilizing a monotonicity condition that can be deduced from the positive definiteness of the Schur complement of the Hessian matrix of the Lagrangian in the lifted version and manipulating first order condition appropriately; this uniform bound over the whole planning horizon $[0, T]$ allows us to partition $[0, T]$ into a number of sub-intervals with a common small length and then glue the consecutive local-in-time solutions together to form the unique global-in-time solution of the FBODE system. The regularity of the global-in-time solution follows from that of the local ones due to the regularity assumptions on the coefficient functions. Moreover, the regularity of the value function will also be shown with the aid of the regularity of the solution couple of the FBODE system and the regularity assumptions on the coefficient functions, with which we can further deduce that this value function and its linear functional derivative satisfy the Bellman and master equations, respectively.

Authors:Revati Gunjal, Sushama Wagh, Syed Shadab Nayyer, Alex Stankovic, Navdeep M. Singh

Abstract: Gradient Descent (GD) is a ubiquitous algorithm for finding the optimal solution to an optimization problem. For reduced computational complexity, the optimal solution $\mathrm{x^*}$ of the optimization problem must be attained in a minimum number of iterations. For this objective, the paper proposes a genesis of an accelerated gradient algorithm through the controlled dynamical system perspective. The objective of optimally reaching the optimal solution $\mathrm{x^*}$ where $\mathrm{\nabla f(x^*)=0}$ with a given initial condition $\mathrm{x(0)}$ is achieved through control.

Authors:Kananart Kuwaranancharoen, Shreyas Sundaram

Abstract: The problem of designing distributed optimization algorithms that are resilient to Byzantine adversaries has received significant attention. For the Byzantine-resilient distributed optimization problem, the goal is to (approximately) minimize the average of the local cost functions held by the regular (non adversarial) agents in the network. In this paper, we provide a general algorithmic framework for Byzantine-resilient distributed optimization which includes some state-of-the-art algorithms as special cases. We analyze the convergence of algorithms within the framework, and derive a geometric rate of convergence of all regular agents to a ball around the optimal solution (whose size we characterize). Furthermore, we show that approximate consensus can be achieved geometrically fast under some minimal conditions. Our analysis provides insights into the relationship among the convergence region, distance between regular agents' values, step-size, and properties of the agents' functions for Byzantine-resilient distributed optimization.

Authors:Shibshankar Dey, Ali Kaan Kurbanzade, Esma S. Gel, Joseph Mihaljevic, Sanjay Mehrotra

Abstract: During various stages of the COVID-19 pandemic, countries implemented diverse vaccine management approaches, influenced by variations in infrastructure and socio-economic conditions. This article provides a comprehensive overview of optimization models developed by the research community throughout the COVID-19 era, aimed at enhancing vaccine distribution and establishing a standardized framework for future pandemic preparedness. These models address critical issues such as site selection, inventory management, allocation strategies, distribution logistics, and route optimization encountered during the COVID-19 crisis. A unified framework is employed to describe the models, emphasizing their integration with epidemiological models to facilitate a holistic understanding.

Authors:Sébastien Dechamps, Frédéric Meunier

Abstract: In a simple model of assigning workers to tasks, every solution that minimizes the load difference between the most loaded worker and the least loaded one actually minimizes the maximal load and maximizes the minimal load. This can be seen as a consequence of standard results of optimization over polymatroids. We show that similar phenomena still occur in close models, simple to state, and that do not enjoy any polymatroid structure.

Authors:Hoai An Le Thi, Thi Tuyet Trinh Nguyen

Abstract: In secure group communications, users of a group share a common group key to prevent eavesdropping and protect the exchange content. A key server distributes the group key as well as performs group rekeying whenever the membership changes dynamically. Instead of rekeying after each join or leave request, we use batch rekeying to alleviate the out-of-sync problem and improve the efficiency. In this paper, we propose an optimization approach to the problem of updating group key in the Logical Key Hierarchy (LKH) structure with batch rekeying. A subtree of new nodes can be appended below a leaf node or is replaced the position of leaving node on the binary key tree. The latter has a lower updating key cost than the former since when a member leaves, all the keys on the path from the root to the deletion node must be updated anyway. We aim to minimize the total rekeying cost, which is the cost of deletion and insertion members while keeping the tree as balanced as possible. The mentioned problem is represented by a unified (deterministic) optimization model whose objective function contains discontinuous step functions with binary variables. Thanks to an exact penalty technique, the problem is equivalently reformulated as a standard DC (Difference of Convex functions) program that can be solved efficiently by DCA (DC algorithm). Numerical experiments have been studied intensively to justify the merit of our proposed approach as well as the corresponding DCA.

Authors:Christos Kolomvakis, Arnaud Vandaele, Nicolas Gillis

Abstract: Boolean matrix factorization (BMF) approximates a given binary input matrix as the product of two smaller binary factors. As opposed to binary matrix factorization which uses standard arithmetic, BMF uses the Boolean OR and Boolean AND operations to perform matrix products, which leads to lower reconstruction errors. BMF is an NP-hard problem. In this paper, we first propose an alternating optimization (AO) strategy that solves the subproblem in one factor matrix in BMF using an integer program (IP). We also provide two ways to initialize the factors within AO. Then, we show how several solutions of BMF can be combined optimally using another IP. This allows us to come up with a new algorithm: it generates several solutions using AO and then combines them in an optimal way. Experiments show that our algorithms (available on gitlab) outperform the state of the art on medium-scale problems.

Authors:Jake Clarkson, Kyle Y Lin

Abstract: Consider a two-person zero-sum search game between a hider and a searcher. The hider hides among $n$ discrete locations, and the searcher successively visits individual locations until finding the hider. Known to both players, a search at location $i$ takes $t_i$ time units and detects the hider -- if hidden there -- independently with probability $\alpha_i$, for $i=1,\ldots,n$. The hider aims to maximize the expected time until detection, while the searcher aims to minimize it. We present an algorithm to compute an optimal strategy for each player. We demonstrate the algorithm's efficiency in a numerical study, in which we also study the characteristics of the optimal hiding strategy.

Authors:Mohamed Awadalla, François Bouffard

Abstract: The objective of electric power system operators is to determine cost-effective operating points by resolving optimization problems that include physical and engineering constraints. As empirical evidence and operator experience indicate, only a small portion of these constraints are found to be binding during operations. Several optimization-based methods have been developed to screen out redundant constraints in operational planning problems like the optimal power flow (OPF) problem. These elimination procedures primarily focus on the feasible region and ignore the role played by the problem's objective function. This letter addresses the constraint screening problem using the bound tightening technique in the context of the OPF problem formulated with a full ac power flow characterization. Due to the non-convexity of the ac OPF, we investigate line constraint screening under different convex relaxations of the problem, and we evaluate how the economics of the objective function impacts screening outcomes.

Authors:Jinhui Hu, Guo Chen, Huaqing Li, Zixiang Shen, Weidong Zhang

Abstract: Distributed stochastic optimization, arising in the crossing and integration of traditional stochastic optimization, distributed computing and storage, and network science, has advantages of high efficiency and a low per-iteration computational complexity in resolving large-scale optimization problems. This paper concentrates on resolving a large-scale convex finite-sum optimization problem in a multi-agent system over unbalanced directed networks. To tackle this problem in an efficient way, a distributed consensus optimization algorithm, adopting the push-sum technique and a distributed loopless stochastic variance-reduced gradient (LSVRG) method with uncoordinated triggered probabilities, is developed and named Push-LSVRG-UP. Each agent under this algorithmic framework performs only local computation and communicates only with its neighbors without leaking their private information. The convergence analysis of Push-LSVRG-UP is relied on analyzing the contraction relationships between four error terms associated with the multi-agent system. Theoretical results provide an explicit feasible range of the constant step-size, a linear convergence rate, and an iteration complexity of Push-LSVRG-UP when achieving the globally optimal solution. It is shown that Push-LSVRG-UP achieves the superior characteristics of accelerated linear convergence, fewer storage costs, and a lower per-iteration computational complexity than most existing works. Meanwhile, the introduction of an uncoordinated probabilistic triggered mechanism allows Push-LSVRG-UP to facilitate the independence and flexibility of agents in computing local batch gradients. In simulations, the practicability and improved performance of Push-LSVRG-UP are manifested via resolving two distributed learning problems based on real-world datasets.

Authors:Luca Di Persio, Peter Kuchling

Abstract: In this article, we analyse the existence of an optimal feedback controller of stochastic optimal control problems governed by SDEs which have the control in the diffusion part. To this end, we consider the underlying Fokker-Planck equation to transform the stochastic optimal control problem into a deterministic problem with open-loop controller.

Authors:Tobias Breiten, Jesper Schröder

Abstract: The analytical background of nonlinear observers based on minimal energy estimation is discussed. It is shown that locally the derivation of the observer equation based on a trajectory with pointwise minimal energy can be done rigorously. The result is obtained by a local sensitivity analysis of the value function based on Pontryagin's maximum principle and the Hamilton-Jacobi-Bellman equation. The consideration of a differential Riccati equation reveals that locally the second derivative of the value function is a positive definite matrix. The local convexity ensures existence of a trajectory minimizing the energy, which is then shown to satisfy the observer equation.

Authors:Shiqiang Zhang, Juan S Campos Salazar, Christian Feldmann, David Walz, Frederik Sandfort, Miriam Mathea, Calvin Tsay, Ruth Misener

Abstract: Optimization over trained machine learning models has applications including: verification, minimizing neural acquisition functions, and integrating a trained surrogate into a larger decision-making problem. This paper formulates and solves optimization problems constrained by trained graph neural networks (GNNs). To circumvent the symmetry issue caused by graph isomorphism, we propose two types of symmetry-breaking constraints: one indexing a node 0 and one indexing the remaining nodes by lexicographically ordering their neighbor sets. To guarantee that adding these constraints will not remove all symmetric solutions, we construct a graph indexing algorithm and prove that the resulting graph indexing satisfies the proposed symmetry-breaking constraints. For the classical GNN architectures considered in this paper, optimizing over a GNN with a fixed graph is equivalent to optimizing over a dense neural network. Thus, we study the case where the input graph is not fixed, implying that each edge is a decision variable, and develop two mixed-integer optimization formulations. To test our symmetry-breaking strategies and optimization formulations, we consider an application in molecular design.

Authors:Mingshang Hu, Shaolin Ji, Rundong Xu, Xiaole Xue

Abstract: In this paper, we propose a formulation to describe a risk-sensitive criterion involving asymmetric risk attitudes toward different risk sources. The introduced criterion can only be defined through quadratic backward stochastic differential equations (BSDE). Before uncovering the mean-variance representation for the introduced asymmetric risk-sensitive criterion by variational approach, some axioms to characterize a variance decomposition of square integrable random variables are provided for the first time. The control problems under the asymmetric risk-sensitive criterion are characterized as a kind of stochastic recursive control problem that includes quadratic BSDEs. Under bounded and unbounded (linear quadratic case) conditions, the stochastic recursive control problems are investigated.

Authors:Hidekazu Yoshioka

Abstract: Conventional harvesting problems for natural resources often assume physiological homogeneity of the body length/weight among individuals. However, such assumptions generally are not valid in real-world problems, where heterogeneity plays an essential role in the planning of biological resource harvesting. Furthermore, it is difficult to observe heterogeneity directly from the available data. This paper presents a novel optimal control framework for the cost-efficient harvesting of biological resources for application in fisheries management. The heterogeneity is incorporated into the resource dynamics, which is the population dynamics in this case, through a probability density that can be distorted from the reality. Subsequently, the distortion, which is the model uncertainty, is penalized through a divergence, leading to a non-standard dynamic differential game wherein the Hamilton-Jacobi-Bellman-Isaacs (HJBI) equation has a unique nonlinear partial differential term. Here, the existence and uniqueness results of the HJBI equation are presented along with an explicit monotone finite difference method. Finally, the proposed optimal control is applied to a harvesting problem with recreationally, economically, and ecologically important fish species using collected field data.

Authors:Samuel Daudin, François Delarue, Joe Jackson

Abstract: The goal of this work is to obtain optimal rates for the convergence problem in mean field control. Our analysis covers cases where the solutions to the limiting problem may not be unique nor stable. Equivalently the value function of the limiting problem might not be differentiable on the entire space. Our main result is then to derive sharp rates of convergence in two distinct regimes. When the data is sufficiently regular, we obtain rates proportional to $N^{-1/2}$, with $N$ being the number of particles. When the data is merely Lipschitz and semi-concave with respect to the first Wasserstein distance, we obtain rates proportional to $N^{-2/(3d+6)}$. Noticeably, the exponent $2/(3d+6)$ is close to $1/d$, which is the optimal rate of convergence for uncontrolled particle systems driven by data with a similar regularity. The key argument in our approach consists in mollifying the value function of the limiting problem in order to produce functions that are almost classical sub-solutions to the limiting Hamilton-Jacobi equation (which is a PDE set on the space of probability measures). These sub-solutions can be projected onto finite dimensional spaces and then compared with the value functions associated with the particle systems. In the end, this comparison is used to prove the most demanding bound in the estimates. The key challenge therein is thus to exhibit an appropriate form of mollification. We do so by employing sup-convolution within a convenient functional Hilbert space. To make the whole easier, we limit ourselves to the periodic setting. We also provide some examples to show that our results are sharp up to some extent.

Authors:Marián Fabian, Alexander Y. Kruger, Patrick Mehlitz

Abstract: We revisit the decoupling approach widely used (often intuitively) in nonlinear analysis and optimization and initially formalized about a quarter of a century ago by Borwein & Zhu, Borwein & Ioffe and Lassonde. It allows one to streamline proofs of necessary optimality conditions and calculus relations, unify and simplify the respective statements, clarify and in many cases weaken the assumptions. In this paper we study weaker concepts of quasiuniform infimum, quasiuniform lower semicontinuity and quasiuniform minimum, putting them into the context of the general theory developed by the aforementioned authors. On the way, we unify the terminology and notation and fill in some gaps in the general theory. We establish rather general primal and dual necessary conditions characterizing quasiuniform $\varepsilon$-minima of the sum of two functions. The obtained fuzzy multiplier rules are formulated in general Banach spaces in terms of Clarke subdifferentials and in Asplund spaces in terms of Fr\'echet subdifferentials. The mentioned fuzzy multiplier rules naturally lead to certain fuzzy subdifferential calculus results. An application from sparse optimal control illustrates applicability of the obtained findings.

Authors:Mihály Petreczky, Roland Tóth, Guillaume Mercère

Abstract: The paper makes the first steps towards a behavioral theory of LPV state-space representations with an affine dependency on scheduling, by characterizing minimality of such state-space representations. It is shown that minimality is equivalent to observability, and that minimal realizations of the same behavior are isomorphic.Finally, we establish a formal relationship between minimality of LPV state-space representations with an affine dependence on scheduling and minimality of LPV state-space representations with a dynamic and meromorphic dependence on scheduling.

Authors:G. Beretta Ca' Foscari University of Venice Polytechnic University of Turin, A. Torcinovich ETH, M. Pelillo Ca' Foscari University of Venice

Abstract: In a seminal 1965 paper, Motzkin and Straus established an elegant connection between the clique number of a graph and the global maxima of a quadratic program defined on the standard simplex. Since then, the result has been the subject of intensive research and has served as the motivation for a number of heuristics and bounds for the maximum clique problem. Most of the studies available in the literature, however, focus typically on the local/global solutions of the program, and little or no attention has been devoted so far to the study of its Karush-Kuhn-Tucker (KKT) points. In contrast, in this paper we study the properties of (a parameterized version of) the Motzkin-Straus program and show that its KKT points can provide interesting structural information and are in fact associated with certain regular sub-structures of the underlying graph.

Authors:Xuyang Wu, Changxin Liu, Sindri Magnusson, Mikael Johansson

Abstract: We propose a delay-agnostic asynchronous coordinate update algorithm (DEGAS) for computing operator fixed points, with applications to asynchronous optimization. DEGAS includes novel asynchronous variants of ADMM and block-coordinate descent as special cases. We prove that DEGAS converges under both bounded and unbounded delays under delay-free parameter conditions. We also validate by theory and experiments that DEGAS adapts well to the actual delays. The effectiveness of DEGAS is demonstrated by numerical experiments on classification problems.

Authors:Tong Guanchun, Michael Muehlebach

Abstract: We discuss a dynamical systems perspective on discrete optimization. Departing from the fact that many combinatorial optimization problems can be reformulated as finding low energy spin configurations in corresponding Ising models, we derive a penalized rank-two relaxation of the Ising formulation. It turns out that the associated gradient flow dynamics exactly correspond to a type of hardware solvers termed oscillator-based Ising machines. We also analyze the advantage of adding angle penalties by leveraging random rounding techniques. Therefore, our work contributes to a rigorous understanding of oscillator-based Ising machines by drawing connections to the penalty method in constrained optimization and providing a rationale for the introduction of sub-harmonic injection locking. Furthermore, we characterize a class of coupling functions between oscillators, which ensures convergence to discrete solutions. This class of coupling functions avoids explicit penalty terms or rounding schemes, which are prevalent in other formulations.

Authors:Mohammad Ali Ahmadpoor, Abbas Momeni

Abstract: For a family of probability spaces $\{(X_k,\mathcal{B}_{X_k},\mu_k)\}_{k=1}^N$ and a cost function $c: X_1\times\cdots\times X_N\to \mathbb{R}$ we consider the Monge-Kantorovich problem \begin{align}\label{MONKANT} \inf_{\lambda\in\Pi(\mu_1,\ldots,\mu_N)}\int_{\prod_{k=1}^N X_k}c\,d\lambda. \end{align} Then for each ordered subset $\mathcal{P}=\{i_1,\ldots,i_p\}\subsetneq\{1,...,N\}$ with $p\geq 2$ we create a new cost function $c_\mathcal{P}$ corresponding to the original cost function $c$ defined on $\prod_{k=1}^p X_{i_k}$. This new cost function $c_\mathcal{P}$ enjoys many of the features of the original cost $c$ while it has the property that any optimal plan $\lambda$ of \eqref{MONKANT} restricted to $\prod_{k=1}^p X_{i_k}$ is also an optimal plan to the problem \begin{align}\label{REDMONKANT} \inf_{\tau\in\Pi(\mu_{i_1},\ldots\mu_{i_p})}\int_{\prod_{k=1}^p X_{i_k}}c_{\mathcal{P}}\,d\tau. \end{align} Our main contribution in this paper is to show that, for appropriate choices of index set $\mathcal{P}$, one can recover the optimal plans of \eqref{MONKANT} from \eqref{REDMONKANT}. In particular, we study situations in which the problem \eqref{MONKANT} admits a unique solution depending on the uniqueness of the solution for the lower marginal problems of the form \eqref{REDMONKANT}. This allows us to prove many uniqueness results for multi-marginal problems when the unique optimal plan is not necessarily induced by a map. To this end, we extensively benefit from disintegration theorems and the $c$-extremality notions. Moreover, by employing this argument, besides recovering many standard results on the subject including the pioneering work of Gangbo-\'Swi\c ech, several new applications will be demonstrated to evince the applicability of this argument.

Authors:Paul Dobson, Jesus Maria Sanz-Serna, Konstantinos Zygalakis

Abstract: We study connections between differential equations and optimization algorithms for $m$-strongly and $L$-smooth convex functions through the use of Lyapunov functions by generalizing the Linear Matrix Inequality framework developed by Fazylab et al. in 2018. Using the new framework we derive analytically a new (discrete) Lyapunov function for a two-parameter family of Nesterov optimization methods and characterize their convergence rate. This allows us to prove a convergence rate that improves substantially on the previously proven rate of Nesterov's method for the standard choice of coefficients, as well as to characterize the choice of coefficients that yields the optimal rate. We obtain a new Lyapunov function for the Polyak ODE and revisit the connection between this ODE and the Nesterov's algorithms. In addition discuss a new interpretation of Nesterov method as an additive Runge-Kutta discretization and explain the structural conditions that discretizations of the Polyak equation should satisfy in order to lead to accelerated optimization algorithms.

Authors:Dejin Ren, Wanli Lu, Jidong Lv, Lijun Zhang, Bai Xue

Abstract: In this paper we investigate the optimal controller synthesis problem, so that the system under the controller can reach a specified target set while satisfying given constraints. Existing model predictive control (MPC) methods learn from a set of discrete states visited by previous (sub-)optimized trajectories and thus result in computationally expensive mixed-integer nonlinear optimization. In this paper a novel MPC method is proposed based on reach-avoid analysis to solve the controller synthesis problem iteratively. The reach-avoid analysis is concerned with computing a reach-avoid set which is a set of initial states such that the system can reach the target set successfully. It not only provides terminal constraints, which ensure feasibility of MPC, but also expands discrete states in existing methods into a continuous set (i.e., reach-avoid sets) and thus leads to nonlinear optimization which is more computationally tractable online due to the absence of integer variables. Finally, we evaluate the proposed method and make comparisons with state-of-the-art ones based on several examples.

Authors:T. J. Meijer, T. Holicki, S. J. A. M. van den Eijnden, C. W. Scherer, W. P. M. H. Heemels

Abstract: The projection lemma (often also referred to as the elimination lemma) is one of the most powerful and useful tools in the context of linear matrix inequalities for system analysis and control. In its traditional formulation, the projection lemma only applies to strict inequalities, however, in many applications we naturally encounter non-strict inequalities. As such, we present, in this note, a non-strict projection lemma that generalizes both its original strict formulation as well as an earlier non-strict version. We demonstrate several applications of our result in robust linear-matrix-inequality-based marginal stability analysis and stabilization, a matrix S-lemma, which is useful in (direct) data-driven control applications, and matrix dilation.

Authors:Nick Tsipinakis, Panagiotis Tigkas, Panos Parpas

Abstract: Second-order methods can address the shortcomings of first-order methods for the optimization of large-scale machine learning models. However, second-order methods have significantly higher computational costs associated with the computation of second-order information. Subspace methods that are based on randomization have addressed some of these computational costs as they compute search directions in lower dimensions. Even though super-linear convergence rates have been empirically observed, it has not been possible to rigorously show that these variants of second-order methods can indeed achieve such fast rates. Also, it is not clear whether subspace methods can be applied to non-convex cases. To address these shortcomings, we develop a link between multigrid optimization methods and low-rank Newton methods that enables us to prove the super-linear rates of stochastic low-rank Newton methods rigorously. Our method does not require any computations in the original model dimension. We further propose a truncated version of the method that is capable of solving high-dimensional non-convex problems. Preliminary numerical experiments show that our method has a better escape rate from saddle points compared to accelerated gradient descent and Adam and thus returns lower training errors.

Authors:Ioana Lal, Constantin Morarescu, Jamal Daafouz, Lucian Busoniu

Abstract: We propose two new optimistic planning algorithms for nonlinear hybrid-input systems, in which the input has both a continuous and a discrete component, and the discrete component must respect a dwell-time constraint. Both algorithms select sets of input sequences for refinement at each step, along with a continuous or discrete step to refine (split). The dwell-time constraint means that the discrete splits must keep the discrete mode constant if the required dwell-time is not yet reached. Convergence rate guarantees are provided for both algorithms, which show the dependency between the near-optimality of the sequence returned and the computational budget. The rates depend on a novel complexity measure of the dwell-time constrained problem. We present simulation results for two problems, an adaptive-quantization networked control system and a model for the COVID pandemic.

Authors:Karthik Elamvazhuthi, Xuechen Zhang, Samet Oymak, Fabio Pasqualetti

Abstract: In numerous robotics and mechanical engineering applications, among others, data is often constrained on smooth manifolds due to the presence of rotational degrees of freedom. Common datadriven and learning-based methods such as neural ordinary differential equations (ODEs), however, typically fail to satisfy these manifold constraints and perform poorly for these applications. To address this shortcoming, in this paper we study a class of neural ordinary differential equations that, by design, leave a given manifold invariant, and characterize their properties by leveraging the controllability properties of control affine systems. In particular, using a result due to Agrachev and Caponigro on approximating diffeomorphisms with flows of feedback control systems, we show that any map that can be represented as the flow of a manifold-constrained dynamical system can also be approximated using the flow of manifold-constrained neural ODE, whenever a certain controllability condition is satisfied. Additionally, we show that this universal approximation property holds when the neural ODE has limited width in each layer, thus leveraging the depth of network instead for approximation. We verify our theoretical findings using numerical experiments on PyTorch for the manifolds S2 and the 3-dimensional orthogonal group SO(3), which are model manifolds for mechanical systems such as spacecrafts and satellites. We also compare the performance of the manifold invariant neural ODE with classical neural ODEs that ignore the manifold invariant properties and show the superiority of our approach in terms of accuracy and sample complexity.

Authors:Asrifa Sultana, Shivani Valecha

Abstract: Any individual's preference represents his choice in the set of available options. It is said to be complete if the person can compare any pair of available options. We aim to initiate the notion of projected solutions for the generalized Nash equilibrium problem with non-ordered (not necessarily complete and transitive) preferences and non-self constraint map. We provide the necessary and sufficient conditions under which projected solutions of a quasi-variational inequality and the considered GNEP coincide. Based on this variational reformulation, we derive the occurrence of projected solutions for the considered GNEP. Alternatively, by using a fixed point result, we ensure the existence of projected solutions for the considered GNEP without requiring the compactness of choice sets.

Authors:Roberto Montemanni, Luca Maria Gambardella

Abstract: This paper discusses a heuristic approach for Team Orienteering Problems with Time Windows. The method we propose takes advantage of a solution model based on a hierarchic generalization of the original problem, which is combined with an Ant Colony System algorithm. Computational results on benchmark instances previously adopted in the literature suggest that the algorithm we propose is effective in practice.

Authors:Anna Ivagnes, Nicola Demo, Gianluigi Rozza

Abstract: In this paper, we propose a shape optimization pipeline for propeller blades, applied to naval applications. The geometrical features of a blade are exploited to parametrize it, allowing to obtain deformed blades by perturbating their parameters. The optimization is performed using a genetic algorithm that exploits the computational speed-up of reduced order models to maximize the efficiency of a given propeller. A standard offline-online procedure is exploited to construct the reduced-order model. In an expensive offline phase, the full order model, which reproduces an open water test, is set up in the open-source software OpenFOAM and the same full order setting is used to run the CFD simulations for all the deformed propellers. The collected high-fidelity snapshots and the deformed parameters are used in the online stage to build the non-intrusive reduced-order model. This paper provides a proof of concept of the pipeline proposed, where the optimized propeller improves the efficiency of the original propeller.

Authors:Hui Xiao, Zhihong Wei

Abstract: This research considers the ranking and selection with input uncertainty. The objective is to maximize the posterior probability of correctly selecting the best alternative under a fixed simulation budget, where each alternative is measured by its worst-case performance. We formulate the dynamic simulation budget allocation decision problem as a stochastic control problem under a Bayesian framework. Following the approximate dynamic programming theory, we derive a one-step-ahead dynamic optimal budget allocation policy and prove that this policy achieves consistency and asymptotic optimality. Numerical experiments demonstrate that the proposed procedure can significantly improve performance.

Authors:Jianbiao Wang, Tomio Miwa, Takayuki Morikawa

Abstract: As an emerging travel mode, the modular vehicle system (MVS) is receiving increasing attention. In particular, the operators could connect multiple modular vehicles as an assembled bus in response to the temporary demand varies. Therefore, in this study, the MVS is adopted in the context of customized bus design to satisfy passengers reserved travel demand. In addition, to increase the potential of the customized modular bus system, the transfer among buses can be considered to group the passengers with the same or close destinations. However, the passengers will not actively transfer as it is viewed as a disutility. Thus, the appropriate incentivization should be provided. To this end, we jointly optimize the passenger-route assignment and the transfer incentivization scheme, in which the transfer demand is considered elastically under different incentivization. Then, the linearization approaches are adopted to transform the original nonlinear model into a mixed integer linear programming model, which can be solved by state-of-the-art solvers. The experiment on the small network reveals that the performance of the bus system with an incentivization scheme is better than that without an incentivization scheme, and the extent of such superiority depends on the total demand level in the system.

Authors:Yongchun Li, Weijun Xie

Abstract: A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective subject to multiple two-sided linear matrix inequalities intersected with a low-rank and spectral constrained domain set. Although solving LSOP is, in general, NP-hard, its partial convexification (i.e., replacing the domain set by its convex hull) termed "LSOP-R," is often tractable and yields a high-quality solution. This motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point of the feasible set of LSOP-R and prove their tightness for the domain sets with different matrix spaces. The proposed rank bounds recover two well-known results in the literature from a fresh angle and also allow us to derive sufficient conditions under which the relaxation LSOP-R is equivalent to the original LSOP. To effectively solve LSOP-R, we develop a column generation algorithm with a vector-based convex pricing oracle, coupled with a rank-reduction algorithm, which ensures the output solution satisfies the theoretical rank bound. Finally, we numerically verify the strength of the LSOP-R and the efficacy of the proposed algorithms.

Authors:V. Ugrinovskii, I. R. Petersen, I. Shames

Abstract: Among first order optimization methods, Polyak's heavy ball method has long been known to guarantee the asymptotic rate of convergence matching Nesterov's lower bound for functions defined in an infinite-dimensional space. In this paper, we use results on the robust gain margin of linear uncertain feedback control systems to show that the heavy ball method is provably worst-case asymptotically optimal when applied to quadratic functions in a finite dimensional space.

Authors:Jaeyeon Kim, Asuman Ozdaglar, Chanwoo Park, Ernest K. Ryu

Abstract: In convex optimization, first-order optimization methods efficiently minimizing function values have been a central subject study since Nesterov's seminal work of 1983. Recently, however, Kim and Fessler's OGM-G and Lee et al.'s FISTA-G have been presented as alternatives that efficiently minimize the gradient magnitude instead. In this paper, we present H-duality, which represents a surprising one-to-one correspondence between methods efficiently minimizing function values and methods efficiently minimizing gradient magnitude. In continuous-time formulations, H-duality corresponds to reversing the time dependence of the dissipation/friction term. To the best of our knowledge, H-duality is different from Lagrange/Fenchel duality and is distinct from any previously known duality or symmetry relations. Using H-duality, we obtain a clearer understanding of the symmetry between Nesterov's method and OGM-G, derive a new class of methods efficiently reducing gradient magnitudes of smooth convex functions, and find a new composite minimization method that is simpler and faster than FISTA-G.

Authors:Luke S. Baker, Sachin Shivakumar, Dieter Armbruster, Rodrigo B. Platte, Anatoly Zlotnik

Abstract: We derive a linear system of ordinary differential equations (ODEs) to approximate the dynamics of natural gas in pipeline networks. Although a closed-form expression of the eigenvalues of the state matrix does not generally exist, the poles of an irrational transfer function corresponding to the linearized partial differential equations are used to approximate the eigenvalues of the ODE system. Our analysis qualitatively demonstrates that the eigenvalues of the state matrix of the entire network system are "pipeline separable" in the sense that the eigenvalues are dominated by the individual pipeline parameters and not the incidence connectivity of the network graph. The linear system is used as the dynamic constraints of a linear optimal control problem (OCP) to design the control actions of compressor units to minimize the energy that they expend. The motivation of this work is to reduce the computational complexity of optimizing gas dynamics in large networks to meet the unpredictable and highly variable demand from electric generators. The linear and corresponding nonlinear OCPs are discretized in time to obtain linear and nonlinear optimization problems, which are demonstrated on a test network to illustrate the validity of linear programming. Moreover, an analytical bound on the error between the solutions of the linear and nonlinear flow dynamics is presented using Lyapunov functions and verified computationally by plotting the error against the size of the flow variation around the steady-state solution.

Authors:Vassilis Apidopoulos, Cesare Molinari, Lorenzo Rosasco, Silvia Villa

Abstract: Dual gradient descent combined with early stopping represents an efficient alternative to the Tikhonov variational approach when the regularizer is strongly convex. However, for many relevant applications, it is crucial to deal with regularizers which are only convex. In this setting, the dual problem is non smooth, and dual gradient descent cannot be used. In this paper, we study the regularization properties of a subgradient dual flow, and we show that the proposed procedure achieves the same recovery accuracy as penalization methods, while being more efficient from the computational perspective.

Authors:Mohammed Bachir, Joel Blot

Abstract: We give a general Lagrange multiplier rule for mathematical programming problems in a Hausdorff locally convex space. We consider infinitely many inequality and equality constraints. Our results gives in particular a generalisation of the result of J. Jahn in \cite{Ja}, replacing Fr\'echet-differentiability assumptions on the functions by the Gateaux-differentiability. Moreover, the closed convex cone with a nonempty interior in the constraints is replaced by a strictly general class of closed subsets introduced in the paper and called {\it "admissible sets"}. Examples illustrating our results are given.

Authors:Mohammed Bachir, Rongzhen Lyu

Abstract: We provide new results of first-order necessary conditions of optimality problem in the form of John's theorem and in the form of Karush-Kuhn-Tucker's theorem. We establish our result in a topological vector space for problems with inequality constraints and in a Banach space for problems with equality and inequality constraints. Our contributions consist in the extension of the results known for the Fr\'echet and Gateaux-differentiable functions as well as for the Clarke's subdifferential of Lipschitz functions, to the more general Dini-differentiable functions. As consequences, we extend the result of B.H. Pourciau in \cite[Theorem 6, p. 445]{Po} from the convexity to the {\it "Dini-pseudoconvexity"}.

Authors:Jan Kronqvist, Boda Li, Jan Rolfes, Shudian Zhao

Abstract: The presented work addresses two-stage stochastic programs (2SPs), a broadly applicable model to capture optimization problems subject to uncertain parameters with adjustable decision variables. In case the adjustable or second-stage variables contain discrete decisions, the corresponding 2SPs are known to be NP-complete. The standard approach of forming a single-stage deterministic equivalent problem can be computationally challenging even for small instances, as the number of variables and constraints scales with the number of scenarios. To avoid forming a potentially huge MILP problem, we build upon an approach of approximating the expected value of the second-stage problem by a neural network (NN) and encoding the resulting NN into the first-stage problem. The proposed algorithm alternates between optimizing the first-stage variables and retraining the NN. We demonstrate the value of our approach with the example of computing operating points in power systems by showing that the alternating approach provides improved first-stage decisions and a tighter approximation between the expected objective and its neural network approximation.

Authors:Duy-Nhat Phan, Sedi Bartz, Nilabja Guha, Hung M. Phan

Abstract: We study a class of nonconvex nonsmooth optimization problems in which the objective is a sum of two functions: One function is the average of a large number of differentiable functions, while the other function is proper, lower semicontinuous and has a surrogate function that satisfies standard assumptions. Such problems arise in machine learning and regularized empirical risk minimization applications. However, nonconvexity and the large-sum structure are challenging for the design of new algorithms. Consequently, effective algorithms for such scenarios are scarce. We introduce and study three stochastic variance-reduced majorization-minimization (MM) algorithms, combining the general MM principle with new variance-reduced techniques. We provide almost surely subsequential convergence of the generated sequence to a stationary point. We further show that our algorithms possess the best-known complexity bounds in terms of gradient evaluations. We demonstrate the effectiveness of our algorithms on sparse binary classification problems, sparse multi-class logistic regressions, and neural networks by employing several widely-used and publicly available data sets.

Authors:Tobias Ehring, Bernard Haasdonk

Abstract: Numerical methods for the optimal feedback control of high-dimensional dynamical systems typically suffer from the curse of dimensionality. In the current presentation, we devise a mesh-free data-based approximation method for the value function of optimal control problems, which partially mitigates the dimensionality problem. The method is based on a greedy Hermite kernel interpolation scheme and incorporates context-knowledge by its structure. Especially, the value function surrogate is elegantly enforced to be 0 in the target state, non-negative and constructed as a correction of a linearized model. The algorithm is proposed in a matrix-free way, which circumvents the large-matrix-problem for multivariate Hermite interpolation. For finite time horizons, both convergence of the surrogate to the value function as well as for the surrogate vs. the optimal controlled dynamical system are proven. Experiments support the effectiveness of the scheme, using among others a new academic model that has a scalable dimension and an explicitly given value function. It may also be useful for the community to validate other optimal control approaches.

Authors:Maryam Daryalal, Ayse N. Arslan, Merve Bodur

Abstract: In this work, we design primal and dual bounding methods for multistage adjustable robust optimization (MSARO) problems by adapting two decision rules rooted in the stochastic programming literature. This approach approximates the primal and dual formulations of an MSARO problem with two-stage models. From the primal perspective, this is achieved by applying two-stage decision rules that restrict the functional forms of a certain subset of decision variables. We present sufficient conditions under which the well-known constraint-and-column generation algorithm can be used to solve the primal approximation with finite convergence guarantees. From the dual side, we introduce a distributionally robust dual problem for MSARO models using their nonanticipative Lagrangian dual and then apply linear decision rules on the Lagrangian multipliers. For this dual approximation, we present a monolithic bilinear program valid for continuous recourse problems, and a cutting-plane method for mixed-integer recourse problems. Our framework is general-purpose and does not require strong assumptions such as a stage-wise independent uncertainty set, and can consider integer recourse variables. Computational experiments on newsvendor, location-transportation, and capital budgeting problems show that our bounds yield considerably smaller optimality gaps compared to the existing methods.

Authors:Philippe Moustrou, Cordian Riener, Hugues Verdure

Abstract: This chapter investigates how symmetries can be used to reduce the computational complexity in polynomial optimization problems. A focus will be specifically given on the Moment-SOS hierarchy in polynomial optimization, where results from representation theory and invariant theory of groups can be used. In addition, symmetry reduction techniques which are more generally applicable are also presented.

Authors:Jens Deussen, Jonathan Hüser, Uwe Naumann

Abstract: We are considering differential-algebraic equations with embedded optimization criteria (DAEOs) in which the embedded optimization problem is solved by global optimization. This actually leads to differential inclusions for cases in which there are multiple global optimizer at the same time. Jump events from one global optimum to another result in nonsmooth DAEs and thus reduction of the convergence order of the numerical integrator to first-order. Implementation of event detection and location as introduced in this work preserves the higher-order convergence behavior of the integrator. This allows to compute discrete tangents and adjoint sensitivities for optimal control problems.

Authors:Bharat Kumar, Deepmala, A. K. Das

Abstract: In this article, we establish a class of new projected type iteration methods based on matrix spitting for solving the linear complementarity problem. Also, we provide a sufficient condition for the convergence analysis when the system matrix is an $H_+$-matrix. We show the efficiency of the proposed method by using two numerical examples for different parameters. Keywords. Iterative method, Linear complementarity problem, $H_{+}$-matrix, $P$-matrix, Matrix splitting, Convergence.

Authors:Safia Kedad-Sidhoum, Anton Medvedev, Frédéric Meunier

Abstract: Two-stage robust optimization is a fundamental paradigm for modeling and solving optimization problems with uncertain parameters. A now classical method within this paradigm is finite-adaptability, introduced by Bertsimas and Caramanis (IEEE Transactions on Automatic Control, 2010). In this note, we point out that the continuity assumption they stated to ensure the convergence of the method is not correct, and we propose an alternative assumption for which we prove the desired convergence.

Authors:Valeriano Antunes de Oliveira

Abstract: In this work, optimality conditions and classical results from duality theory are derived for continuous-time linear optimization problems with inequality constraints. The optimality conditions are given in the Karush-Kuhn-Tucker form. Weak and strong duality properties, as well as, the complementary slackness theorem are established. A result concerning the existence of solutions is also stated.

Authors:Yun Zeng, Deren Han, Yansheng Su, Jiaxin Xie

Abstract: The stochastic heavy ball momentum (SHBM) method has gained considerable popularity as a scalable approach for solving large-scale optimization problems. However, one limitation of this method is its reliance on prior knowledge of certain problem parameters, such as singular values of a matrix. In this paper, we propose an adaptive variant of the SHBM method for solving stochastic problems that are reformulated from linear systems using a user-defined distribution. Our adaptive SHBM (ASHBM) method utilizes iterative information to update the parameters, addressing an open problem in the literature regarding the adaptive learning of momentum parameters. We prove that our method converges linearly in expectation, with a better convergence rate compared to the basic method. Notably, we demonstrate that the deterministic version of our ASHBM algorithm can be reformulated as a variant of the conjugate gradient (CG) method, inheriting many of its appealing properties, such as finite-time convergence. Consequently, the ASHBM method can be further generalized to develop a brand-new framework of the stochastic CG (SCG) method for solving linear systems. Our theoretical results are supported by numerical experiments.

Authors:Yutao Tang, Yicheng Zhang, Ruonan Li, Xinghu Wang

Abstract: This paper aims at distributed algorithms for solving a system of linear algebraic equations. Different from most existing formulations for this problem, we assume that the local data at each node is not accurately measured but subject to some disturbances. To be specific, the local measurement consists of two parts: a nominal value and a multiple sinusoidal disturbance. By introducing an identifier-enhanced observer to estimate the disturbance, we present a novel distributed least squares solver for the linear equations using noisy measurements. The proposed solver is proven to be able to recover the least squares solution to the linear equations associated with the nominal values irrespective of any multi-sinusoidal disturbance even with unknown frequencies. We also show the robustness of the distributed solvers under standard conditions against unstructured perturbations. The effectiveness of our design is verified by a numerical example.

Authors:Marianne Akian, Xavier Allamigeon, Stéphane Gaubert, Sergei Sergeev

Abstract: We study the tropical analogue of the notion of polar of a cone, working over the semiring of tropical numbers with signs and show that the tropical polars of sets of nonnegative tropical vectors are precisely sets of signed vectors that are closed and that are stable by an operation of linear combination. We relate tropical polars with images by the nonarchimedean valuation of classical polars over real closed nonarchimedean fields and show, in particular, that for semi-algebraic sets over such a field, the operation of taking the polar commutes with the operation of signed valuation (keeping track both of the nonarchimedean valuation and sign). We apply these results to characterize images by the signed valuation of classical cones of matrices, including the cones of positive semidefinite matrices, completely positive matrices, completely positive semidefinite matrices, and their polars, including the cone of co-positive matrices. It turns out, in particular, that hierarchies of classical cones collapse under tropicalization. We finally discuss a simple application of these ideas to optimization with signed tropical numbers.

Authors:François Dufour, Tomás Prieto-Rumeau

Abstract: We consider a nonzero-sum N-player Markov game on an abstract measurable state space with compact metric action spaces. The payoff functions are bounded Carath\'eodory functions and the transitions of the system are assumed to have a density function satisfying some continuity conditions. The optimality criterion of the players is given by a total expected payoff on an infinite discrete-time horizon. Under the condition that the game model is absorbing, we establish the existence of Markov strategies that are a noncooperative equilibrium in the family of all history-dependent strategies of the players for both the constrained and the unconstrained problems, We obtain, as a particular case of results, the existence of Nash equilibria for discounted constrained and unconstrained game models.

Authors:Alban Puech IP Paris & DEIF, Gorazd Dimitrov IP Paris, Claudia D'Ambrosio LIX, CNRS

Abstract: As the share of variable renewable energy sources increases in the electricity mix, new solutions are needed to build a flexible and reliable grid. Energy arbitrage with battery storage systems supports renewable energy integration into the grid by shifting demand and increasing the overall utilization of power production systems. In this paper, we propose a mixed integer linear programming model for energy arbitrage on the day-ahead market, that takes into account operational and availability constraints of asset owners willing to get an additional revenue stream from their storage asset. This approach optimally schedules the charge and discharge operations associated with the most profitable trading strategy, and achieves between 80% and 90% of the maximum obtainable profits considering one-year time horizons using the prices of electricity in multiple European countries including Germany, France, Italy, Denmark, and Spain.

Authors:Qiang Fu, Dongchu Xu, Ashia Wilson

Abstract: Non-convex optimization plays a key role in a growing number of machine learning applications. This motivates the identification of specialized structure that enables sharper theoretical analysis. One such identified structure is quasar-convexity, a non-convex generalization of convexity that subsumes convex functions. Existing algorithms for minimizing quasar-convex functions in the stochastic setting have either high complexity or slow convergence, which prompts us to derive a new class of stochastic methods for optimizing smooth quasar-convex functions. We demonstrate that our algorithms have fast convergence and outperform existing algorithms on several examples, including the classical problem of learning linear dynamical systems. We also present a unified analysis of our newly proposed algorithms and a previously studied deterministic algorithm.

Authors:Flavien Léger, Pierre-Cyril Aubin-Frankowski

Abstract: We present a new class of gradient-type optimization methods that extends vanilla gradient descent, mirror descent, Riemannian gradient descent, and natural gradient descent. Our approach involves constructing a surrogate for the objective function in a systematic manner, based on a chosen cost function. This surrogate is then minimized using an alternating minimization scheme. Using optimal transport theory we establish convergence rates based on generalized notions of smoothness and convexity. We provide local versions of these two notions when the cost satisfies a condition known as nonnegative cross-curvature. In particular our framework provides the first global rates for natural gradient descent and Newton's method.

Authors:Puya Latafat, Andreas Themelis, Silvia Villa, Panagiotis Patrinos

Abstract: Bilevel optimization is a comprehensive framework that bridges single- and multi-objective optimization. It encompasses many general formulations, including, but not limited to, standard nonlinear programs. This work demonstrates how elementary proximal gradient iterations can be used to solve a wide class of convex bilevel optimization problems without involving subroutines. Compared to and improving upon existing methods, ours (1) can handle a wider class of problems, including nonsmooth terms in the upper and lower level problems, (2) does not require strong convexity or global Lipschitz gradient continuity assumptions, and (3) provides a systematic adaptive stepsize selection strategy, allowing for the use of large stepsizes while being insensitive to the choice of parameters.

Authors:Erik Nygren, Christian Eichenberger, Emma Frejinger

Abstract: With the aim to stimulate future research, we describe an exploratory study of a railway rescheduling problem. A widely used approach in practice and state of the art is to decompose these complex problems by geographical scope. Instead, we propose defining a core problem that restricts a rescheduling problem in response to a disturbance to only trains that need to be rescheduled, hence restricting the scope in both time and space. In this context, the difficulty resides in defining a scoper that can predict a subset of train services that will be affected by a given disturbance. We report preliminary results using the Flatland simulation environment that highlights the potential and challenges of this idea. We provide an extensible playground open-source implementation based on the Flatland railway environment and Answer-Set Programming.

Authors:Brecht Evens, Pieter Pas, Puya Latafat, Panagiotis Patrinos

Abstract: The proximal point algorithm (PPA) is the most widely recognized method for solving inclusion problems and serves as the foundation for many numerical algorithms. Despite this popularity, its convergence results have been largely limited to the monotone setting. In this work, we study the convergence of (relaxed) preconditioned PPA for a class of nonmonotone problems that satisfy an oblique weak Minty condition. Additionally, we study the (relaxed) Douglas-Rachford splitting (DRS) method in the nonmonotone setting by establishing a connection between DRS and the preconditioned PPA with a positive semidefinite preconditioner. To better characterize the class of problems covered by our analysis, we introduce the class of semimonotone operators, offering a natural extension to (hypo)monotone and co(hypo)monotone operators, and describe some of their properties. Sufficient conditions for global convergence of DRS involving the sum of two semimonotone operators are provided. Notably, it is shown that DRS converges even when the sum of the involved operators (or of their inverses) is nonmonotone. Various example problems are provided, demonstrating the tightness of our convergence results and highlighting the wide range of applications our theory is able to cover.

Authors:Dan Goreac LAMA, Alain Rapaport MISTEA

Abstract: We provide a duality result linking the value function for a control problem with supremum cost H under an isoperimetric inequality G $\le$ gmax, and the value function for the same controlled dynamics with cost G and state constraint H $\le$ hmax. This duality is proven for initial conditions at which lower semi-continuity of the value functions can be guaranteed, and is completed with optimality considerations. Furthermore, we provide structural assumptions on the dynamics under which such regularity can be established. As a by-product, we illustrate the partial equivalence between recentworks dealing with non-pharmaceutically controlled epidemics under peak or budget restrictions.

Authors:Soumitra Dey, V. Vetrivel, Hong-Kun Xu

Abstract: We extend the concept of well-posedness to the split equilibrium problem and establish Furi-Vignoli-type characterizations for the well-posedness. We prove that the well-posedness of the split equilibrium problem is equivalent to the existence and uniqueness of its solution under certain assumptions on the bifunctions involved. We also characterize the generalized well-posedness of the split equilibrium problem via the Kuratowski measure of noncompactness. We illustrate our theoretical results by several examples.

Authors:Gil Marques, Marco Martins Afonso, Sílvio Gama

Abstract: We present a novel method for estimating the circulations and positions of point vortices using trajectory data of passive particles in the presence of Gaussian noise. The method comprises two algorithms: the first one calculates the vortex circulations, while the second one reconstructs the vortex trajectories. This reconstruction is done thanks to a hierarchy of optimization problems, involving the integration of systems of differential equations, over time sub-intervals all with the same amplitude defined by the autocorrelation function for the advected passive particles' trajectories. Our findings indicate that accurately tracking the position of vortices and determining their circulations is achievable, even when passive particle trajectories are affected by noise.

Authors:Bharat Kumar, Deepmala, A. K. Das

Abstract: In this article, we establish a class of new accelerated modulus-based iteration methods for solving the linear complementarity problem. When the system matrix is an $H_+$-matrix, we present appropriate criteria for the convergence analysis. Also, we demonstrate the effectiveness of our proposed method and reduce the number of iterations and CPU time to accelerate the convergence performance by providing two numerical examples for various parameters. Keywords. Linear complementarity problem, Iteration method, $P$-matrix, $H_{+}$-matrix, Convergence analysis, Matrix splitting.

Authors:Keaton Coletti, Pawel Kalczynski, Zvi Drezner

Abstract: The inverse-square law states that the effect a source has on its surroundings is inversely proportional to the square of the Euclidean distance from that source. Its applicability spans multiple fields including physics, engineering, and computer science. We study the combined effect of multiple point sources surrounding a closed region in multidimensional space. We determine that the maximum effect in D dimensions is on the region's boundary if $D \leq 4$, and the minimum is on the boundary if $D \geq 4$.

Authors:Hanbin Yang, Noah Rhodes, Haoxiang Yang, Line Roald, Lewis Ntaimo

Abstract: As climate change evolves, wildfire risk is increasing globally, posing a growing threat to power systems, with grid failures fueling the most destructive wildfires. In day-to-day operations, preemptive de-energization of equipment is an effective tool to mitigate the risk and damage of wildfires. However, such power outages have significant impacts on customers. This paper proposes a novel framework for planning preemptive de-energization of power systems to mitigate wildfire risk and damage. We model wildfire disruptions as stochastic disruptions with random magnitude and timing and formulate a two-stage stochastic program that maximizes the electricity delivered while proactively reducing the risk of wildfires by selectively de-energizing components over multiple time periods. We use cellular automata to sample grid failure and wildfire scenarios based on grid-related risks and environmental factors. We develop a decomposition algorithm that can generate adaptive shutoff plans before a disruption occurs. We test our method on an augmented version of the RTS-GLMC test case in Southern California and compare it with two benchmark cases. We find that our method reduces both wildfire damage costs and load-shedding losses over multiple time periods, and our nominal plan is robust against the uncertainty model perturbation.

Authors:Richard Pates

Abstract: The cyclic feedback interconnection of $n$ subsystems is the basic building block of control theory. Many robust stability tools have been developed for this interconnection. Two notable examples are the small gain theorem and the Secant Criterion. Both of these conditions guarantee stability if an inequality involving the geometric mean of a set of subsystem indices is satisfied. The indices in each case are designed to capture different core properties; gain in the case of the small gain theorem, and the degree of output-strict-passivity in the Secant Criterion. In this paper we identify entire families of other suitable indices based on mappings of the unit disk. This unifies the small gain theorem and the Secant Criterion, as well as a range of other stability criteria, into a single condition.

Authors:Haihao Lu, Jinwen Yang

Abstract: We present a unified viewpoint of proximal point method (PPM), primal-dual hybrid gradient (PDHG) and alternating direction method of multipliers (ADMM) for solving convex-concave primal-dual problems. This viewpoint shows the equivalence of these three algorithms upto a norm change, and it leads to a four-line simple proof of their $\mathcal O(1/k)$ ergodic rates.

Authors:Tian Xia, Jia Liu, Abdel Lisser

Abstract: This paper considers the distributionally robust chance constrained Markov decision process with random reward and ambiguous reward distribution. We consider individual and joint chance constraint cases with Kullback-Leibler divergence based ambiguity sets centered at elliptical distributions or elliptical mixture distributions, respectively. We derive tractable reformulations of the distributionally robust individual chance constrained Markov decision process problems and design a new hybrid algorithm based on the sequential convex approximation and line search method for the joint case. We carry out numerical tests with a machine replacement problem.

Authors:Michael Schneeberger, Florian Dörfler, Silvia Mastellone

Abstract: We propose a novel approach to certify closed-loop stability and safety of a constrained polynomial system based on the combination of Control Lyapunov Functions (CLFs) and Control Barrier Functions (CBFs). For polynomial systems that are affine in the control input, both classes of functions can be constructed via Sum Of Squares (SOS) programming. Using two versions of the Positivstellensatz we derive an SOS formulation seeking a rational controller that - if feasible - results in compatible CLF and multiple CBFs.

Authors:Xiaodong Cheng, Tudor C. Ionescu, Monica Pătraşcu

Abstract: This paper studies a structure-preserving model reduction problem for large-scale second-order dynamical systems via the framework of time-domain moment matching. The moments of a second-order system are interpreted as the solutions of second-order Sylvester equations, which leads to families of parameterized second-order reduced models that match the moments of an original second-order system at selected interpolation points. Based on this, a two-sided moment matching problem is addressed, providing a unique second-order reduced system that match two distinct sets interpolation points. Furthermore, we also construct the reduced second-order systems that matches the moments of both zero and first order derivative of the original second-order system. Finally, the Loewner framework is extended to the second-order systems, where two parameterized families of models are presented that retain the second-order structure and interpolate sets of tangential data.

Authors:Alim Buğra Çınar, Wout Dullaert, Markus Leitner, Rosario Paradiso, Stefan Waldherr

Abstract: High demand, rising customer expectations, and government regulations are forcing companies to increase the efficiency and sustainability of urban (last-mile) distribution. Consequently, several new delivery concepts have been proposed that increase flexibility for customers and other stakeholders. One of these innovations is crowdsourced delivery, where deliveries are made by occasional drivers who wish to utilize their surplus resources (unused transport capacity) by making deliveries in exchange for some compensation. In addition to reducing delivery costs, the potential benefits of crowdsourced delivery include better utilization of transport capacity, a reduction in overall traffic, and increased flexibility (by scaling up and down delivery capacity as needed). The use of occasional drivers poses new challenges because (unlike traditional couriers) neither their availability nor their behavior in accepting delivery offers is certain. The relationship between the compensation offered to occasional drivers and the probability that they will accept a task has been largely neglected in the scientific literature. Therefore, we consider a setting in which compensation-dependent acceptance probabilities are explicitly considered in the process of assigning delivery tasks to occasional drivers. We propose a mixed-integer nonlinear model that minimizes the expected delivery costs while identifying optimal assignments of tasks to a mix of traditional and occasional drivers and their compensation. We propose exact linearization schemes for two practically relevant probability functions and an approximate linearization scheme for the general case. The results of our computational study show clear advantages of our new approach over existing ones.

Authors:Duksang Lee, Nam Ho-Nguyen, Dabeen Lee

Abstract: This paper develops projection-free algorithms for online convex optimization with stochastic constraints. We design an online primal-dual projection-free framework that can take any projection-free algorithms developed for online convex optimization with no long-term constraint. With this general template, we deduce sublinear regret and constraint violation bounds for various settings. Moreover, for the case where the loss and constraint functions are smooth, we develop a primal-dual conditional gradient method that achieves $O(\sqrt{T})$ regret and $O(T^{3/4})$ constraint violations. Furthermore, for the setting where the loss and constraint functions are stochastic and strong duality holds for the associated offline stochastic optimization problem, we prove that the constraint violation can be reduced to have the same asymptotic growth as the regret.

Authors:Felix Benning, Leif Döring

Abstract: While gradient based methods are ubiquitous in machine learning, selecting the right step size often requires "hyperparameter tuning". This is because backtracking procedures like Armijo's rule depend on quality evaluations in every step, which are not available in a stochastic context. Since optimization schemes can be motivated using Taylor approximations, we replace the Taylor approximation with the conditional expectation (the best $L^2$ estimator) and propose "Random Function Descent" (RFD). Under light assumptions common in Bayesian optimization, we prove that RFD is identical to gradient descent, but with calculable step sizes, even in a stochastic context. We beat untuned Adam in synthetic benchmarks. To close the performance gap to tuned Adam, we propose a heuristic extension competitive with tuned Adam.

Authors:Matias Vistnes, Vijay Venu Vadlamudi, Sigurd Hofsmo Jakobsen, Oddbjørn Gjerde

Abstract: With the increasing complexity of power systems, faster methods for power system reliability analysis are needed. We propose a novel methodology to solve the security constrained optimal power flow (SCOPF) problem that reduces the computational time by using the Sherman-Morrison-Woodbury identity and Benders decomposition. The case study suggests that in a 500 node system, the run time is reduced by 83.5% while ensuring a reliable operation of the system considering short- and long-term post-contingency limits and reducing the operational costs, compared to a preventive `N-1' strategy.

Authors:Justina Gianatti, Francisco J. Silva, Ahmad Zorkot

Abstract: We consider a deterministic mean field games problem in which a typical agent solves an optimal control problem where the dynamics is affine with respect to the control and the cost functional has a growth which is polynomial with respect to the state variable. In this framework, we construct a mean field game problem in discrete time and finite state space that approximates equilibria of the original game. Two numerical examples, solved with the fictitious play method, are presented.

Authors:yaacov Kopeliovich

Abstract: In this paper we formulate and solve an optimal problem for Stochastic process with a regime absorbing state. The solution for this problem is obtained through a system of partial differential equations. The method is applied to obtain an explicit solution for the Merton portfolio problem when an asset has a default probability in case of a log utility.

Authors:Amir Davatgari, Taner Cokyasar, Anirudh Subramanyam, Jeffrey Larson, Abolfazl Mohammadian

Abstract: Electric vehicle (EV) supply equipment location and allocation (EVSELCA) problems for freight vehicles are becoming more important because of the trending electrification shift. Some previous works address EV charger location and vehicle routing problems simultaneously by generating vehicle routes from scratch. Although such routes can be efficient, introducing new routes may violate practical constraints, such as drive schedules, and satisfying electrification requirements can require dramatically altering existing routes. To address the challenges in the prevailing adoption scheme, we approach the problem from a fixed-route perspective. We develop a mixed-integer linear program, a clustering approach, and a metaheuristic solution method using a genetic algorithm (GA) to solve the EVSELCA problem. The clustering approach simplifies the problem by grouping customers into clusters, while the GA generates solutions that are shown to be nearly optimal for small problem cases. A case study examines how charger costs, energy costs, the value of time (VOT), and battery capacity impact the cost of the EVSELCA. Charger costs were found to be the most significant component in the objective function, with an 80\% decrease resulting in a 25\% cost reduction. VOT costs decrease substantially as energy costs increase. The number of fast chargers increases as VOT doubles. Longer EV ranges decrease total costs up to a certain point, beyond which the decrease in total costs is negligible.

Authors:Stefanny Ramirez, Maaike Odijk, Dario Bauso

Abstract: We develop a dynamic model of cascading failures in a financial network whereby cross-holdings are viewed as feedback, external assets investments as inputs and failure penalties as static nonlinearities. We provide sufficient milder and stronger conditions for the system to be a positive one, and study equilibrium points and stability. Stability implies absence of cascades and convergence of market values to constant values. We provide a constructive method for control design to obtain stabilizing market investments in the form of feedback-feedforward control inputs.

Authors:Maria Barbati, Salvatore Greco, Isabella M. Lami

Abstract: In this paper, we present a methodology based on a multiobjective optimization suggesting which facility to implement, in which location, and at which time. In this context, we define a new elicitation procedure to handle Decision Makers (DMs) preferences with an intrinsic and more general interest that goes beyond the specific decision problem. In particular, the user's preferences are elicited by conjugating the deck of cards method with the ordinal regression approach allowing the DM to provide preference information in terms of ranking and pairwise comparing with regard to the intensity of preference of some solutions of the optimization problem. Then, the score of the reference solutions obtained through the deck of the cards method is used as a basis for an ordinal regression procedure that, to take into account interaction between criteria, represents DM's multicriteria preferences by means of a value function expressed in terms of a Choquet Integral. The obtained value function is then used to define a multiobjective optimization problem. The new feasible solutions obtained by the resolution of the optimization problem are proposed to the DM to verify his appreciation and collect further new preference information to iterate the interaction procedure ending when the DM is satisfied of the proposed solution. We apply our methodology to a real world problem to handle the planning procedure of a sustainable Ecovillage in the province of Turin (Italy). We consider a set of facilities to be distributed in a given space in a proper temporal sequence that we conveniently formulated in terms of the space time model introduced by Barbati et al. (2020). We interact with the President of the cooperative owning the Ecovillage to detail what facilities of the Ecovillage should be selected among the proposed ones, where they should be located, and when they should be planned.

Authors:Shuo Chen, Bin Shi, Ya-xiang Yuan

Abstract: The high-resolution differential equation framework has been proven to be tailor-made for Nesterov's accelerated gradient descent method~(\texttt{NAG}) and its proximal correspondence -- the class of faster iterative shrinkage thresholding algorithms (FISTA). However, the systems of theories is not still complete, since the underdamped case ($r < 2$) has not been included. In this paper, based on the high-resolution differential equation framework, we construct the new Lyapunov functions for the underdamped case, which is motivated by the power of the time $t^{\gamma}$ or the iteration $k^{\gamma}$ in the mixed term. When the momentum parameter $r$ is $2$, the new Lyapunov functions are identical to the previous ones. These new proofs do not only include the convergence rate of the objective value previously obtained according to the low-resolution differential equation framework but also characterize the convergence rate of the minimal gradient norm square. All the convergence rates obtained for the underdamped case are continuously dependent on the parameter $r$. In addition, it is observed that the high-resolution differential equation approximately simulates the convergence behavior of~\texttt{NAG} for the critical case $r=-1$, while the low-resolution differential equation degenerates to the conservative Newton's equation. The high-resolution differential equation framework also theoretically characterizes the convergence rates, which are consistent with that obtained for the underdamped case with $r=-1$.

Authors:Thomas Oberleitner, Thomas Zahel, Christoph Herwig

Abstract: According to ICH Q8 guidelines, the biopharmaceutical manufacturer submits a design space (DS) definition as part of the regulatory approval application, in which case process parameter (PP) deviations within this space are not considered a change and do not trigger a regulatory post approval procedure. A DS can be described by non-linear PP ranges, i.e., the range of one PP conditioned on specific values of another. However, independent PP ranges (linear combinations) are often preferred in biopharmaceutical manufacturing due to their operation simplicity. While some statistical software supports the calculation of a DS comprised of linear combinations, such methods are generally based on discretizing the parameter space - an approach that scales poorly as the number of PPs increases. Here, we introduce a novel method for finding linear PP combinations using a numeric optimizer to calculate the largest design space within the parameter space that results in critical quality attribute (CQA) boundaries within acceptance criteria, predicted by a regression model. A precomputed approximation of tolerance intervals is used in inequality constraints to facilitate fast evaluations of this boundary using a single matrix multiplication. Correctness of the method was validated against different ground truths with known design spaces. Compared to stateof-the-art, grid-based approaches, the optimizer-based procedure is more accurate, generally yields a larger DS and enables the calculation in higher dimensions. Furthermore, a proposed weighting scheme can be used to favor certain PPs over others and therefore enabling a more dynamic approach to DS definition and exploration. The increased PP ranges of the larger DS provide greater operational flexibility for biopharmaceutical manufacturers.

Authors:Su Meyra Tatar, Erdal Aydin

Abstract: The regulations regarding the Paris Agreement are planned to be adapted soon to keep the global temperature rise within 2 0C. Additionally, integrating renewable energy-based equipment and adopting new ways of producing energy resources, for example Power to Gas technology, becomes essential because of the current environmental and political concerns. Moreover, it is vital to supply the growing energy demand with the increasing population. Uncertainty must be considered in the transition phase since parameters regarding the electricity demand, carbon tax policies, and intermittency of renewable energy-based equipment have intermittent nature. A multi-period two-stage stochastic MILP model is proposed in this work where the wind speed, solar irradiance, temperature, power demand, carbon emission trading (CET) price, and CO2 emission limit are considered uncertain parameters. This model finds one single optimal design for the energy grid while considering several scenarios regarding uncertainties simultaneously. Three stochastic case studies with scenarios including different combinations of the aforementioned uncertain parameters are investigated. Results show that more renewable energy-based equipment with higher rated power values is chosen as the sanctions get stricter. In addition, the optimality of PtG technology is also investigated for a specific location. Implementing the CO2 emission limit as an uncertain parameter instead of including CET price as an uncertain parameter results in lower annual CO2 emission rates and higher net present cost values. Keywords: optimal renewable energy integration, power-to-gas, two-stage stochastic programming, carbon trade, carbon price, green hydrogen

Authors:Alban Puech SE, Tristan Rigaut LAAS-POP, Adrien Le Franc LAAS-POP, William Templier SE, Jean-Christophe Alais SE, Maud Tournoud SE, Victor Bossard SE, Alejandro Yousef SE, Elena Stolyarova SE

Abstract: Microgrids are local energy systems that integrate energy production, demand, and storage units. They are generally connected to the regional grid to import electricity when local production and storage do not meet the demand. In this context, Energy Management Systems (EMS) are used to ensure the balance between supply and demand, while minimizing the electricity bill, or an environmental criterion. The main implementation challenges for an EMS come from the uncertainties in the consumption, the local renewable energy production, and in the price and the carbon intensity of electricity. Model Predictive Control (MPC) is widely used to implement EMS but is particularly sensitive to the forecast quality, and often requires a subscription to expensive third-party forecast services. We introduce four Multistage Stochastic Control Algorithms relying only on historical data obtained from on-site measurements. We formulate them under the shared framework of Multistage Stochastic Programming and benchmark them against two baselines in 61 different microgrid setups using the EMSx dataset. Our most effective algorithm produces notable cost reductions compared to an MPC that utilizes the same uncertainty model to generate predictions, and it demonstrates similar performance levels to an ideal MPC that relies on perfect forecasts.

Authors:Frank E. Curtis, Vyacheslav Kungurtsev, Daniel P. Robinson, Qi Wang

Abstract: A stochastic-gradient-based interior-point algorithm for minimizing a continuously differentiable objective function (that may be nonconvex) subject to bound constraints is presented, analyzed, and demonstrated through experimental results. The algorithm is unique from other interior-point methods for solving smooth (nonconvex) optimization problems since the search directions are computed using stochastic gradient estimates. It is also unique in its use of inner neighborhoods of the feasible region -- defined by a positive and vanishing neighborhood-parameter sequence -- in which the iterates are forced to remain. It is shown that with a careful balance between the barrier, step-size, and neighborhood sequences, the proposed algorithm satisfies convergence guarantees in both deterministic and stochastic settings. The results of numerical experiments show that in both settings the algorithm can outperform a projected-(stochastic)-gradient method.

Authors:Terézia Fulová, Mária Trnovská

Abstract: Procrustes problems are matrix approximation problems searching for a~transformation of the given dataset to fit another dataset. They find applications in numerous areas, such as factor and multivariate analysis, computer vision, multidimensional scaling or finance. The known methods for solving Procrustes problems have been designed to handle specific sub-classes, where the set of feasible solutions has a special structure (e.g. a Stiefel manifold), and the objective function is defined using a specific matrix norm (typically the Frobenius norm). We show that a wide class of Procrustes problems can be formulated and solved as a (rank-constrained) semi-definite program. This includes balanced and unbalanced (weighted) Procrustes problems, possibly to a partially specified target, but also oblique, projection or two-sided Procrustes problems. The proposed approach can handle additional linear, quadratic, or semi-definite constraints and the objective function defined using the Frobenius norm but also standard operator norms. The results are demonstrated on a set of numerical experiments and also on real applications.

Authors:Wenxuan Liu, Zhihai Zhang

Abstract: This paper investigates the data-driven pricing newsvendor problem, which focuses on maximizing expected profit by deciding on inventory and pricing levels based on historical demand and feature data. We first build an approximate model by assigning weights to historical samples. However, due to decision-dependent effects, the resulting approximate model is complicated and unable to solve directly. To address this issue, we introduce the concept of approximate gradients and design an Approximate Gradient Descent (AGD) algorithm. We analyze the convergence of the proposed algorithm in both convex and non-convex settings, which correspond to the newsvendor pricing model and its variants respectively. Finally, we perform numerical experiment on both simulated and real-world dataset to demonstrate the efficiency and effectiveness of the AGD algorithm. We find that the AGD algorithm can converge to the local maximum provided that the approximation is effective. We also illustrate the significance of two characteristics: distribution-free and decision-dependent of our model. Consideration of the decision-dependent effect is necessary for approximation, and the distribution-free model is preferred when there is little information on the demand distribution and how demand reacts to the pricing decision. Moreover, the proposed model and algorithm are not limited to the newsvendor problem, but can also be used for a wide range of decision-dependent problems.

Authors:Tong Han, David J. Hill, Yue Song

Abstract: This paper focuses on the N-k security-constrained optimal transmission switching (OTS) problem for variable renewable energy (VRE) penetrated power grids. A new three-stage stochastic and distributionally robust OTS model is proposed. The first stage has the primary purpose to schedule the power generation and network topology based on the forecast of VRE. The second stage controls the power generation and voltage magnitudes of voltage-controlled buses in response to VRE uncertainty, and the third stage reacts to N-k contingencies additionally by line switching and load shedding. The VRE and N-k contingencies, considering different availability of their probability distributions, are tackled by stochastic and distributionally robust optimization, respectively. By adopting stage-wise realization of uncertainties in VRE and contingencies, the associated corrective controls with different mechanisms can be handled separately and properly, which makes the proposed OTS model more realistic than existing two-stage ones. For solving the proposed OTS model, its tractable reformulation is derived, and a solution approach that combines the nested column-and-constraint generation algorithm and Dantzig-Wolfe procedure is developed. Finally, case studies include a simple IEEE network for illustrative purposes and then real system networks to demonstrate the efficacy of the proposed approach.

Authors:Haochuan Li, Ali Jadbabaie, Alexander Rakhlin

Abstract: In this paper, we provide a rigorous proof of convergence of the Adaptive Moment Estimate (Adam) algorithm for a wide class of optimization objectives. Despite the popularity and efficiency of the Adam algorithm in training deep neural networks, its theoretical properties are not yet fully understood, and existing convergence proofs require unrealistically strong assumptions, such as globally bounded gradients, to show the convergence to stationary points. In this paper, we show that Adam provably converges to $\epsilon$-stationary points with $\mathcal{O}(\epsilon^{-4})$ gradient complexity under far more realistic conditions. The key to our analysis is a new proof of boundedness of gradients along the optimization trajectory, under a generalized smoothness assumption according to which the local smoothness (i.e., Hessian norm when it exists) is bounded by a sub-quadratic function of the gradient norm. Moreover, we propose a variance-reduced version of Adam with an accelerated gradient complexity of $\mathcal{O}(\epsilon^{-3})$.

Authors:Taiwo Adetiloye, Anjali Awasthi

Abstract: The logistics of urban areas are becoming more sophisticated due to the fast city population growth. The stakeholders are faced with the challenges of the dynamic complexity of city logistics(CL) systems characterized by the uncertainty effect together with the freight vehicle emissions causing pollution. In this conceptual paper, we present a research methodology for the environmental sustainability of CL systems that can be attained by effective stakeholders' collaboration under non-chaotic situations and the presumption of the human levity tendency. We propose the mathematical axioms of the uncertainty effect while putting forward the notion of condition effectors, and how to assign hypothetical values to them. Finally, we employ a spider network and causal loop diagram to investigate the system's elements and their behavior over time.

Authors:Jia-Jie Zhu

Abstract: This paper provides answers to an open problem: given a nonlinear data-driven dynamical system model, e.g., kernel conditional mean embedding (CME) and Koopman operator, how can one propagate the ambiguity sets forward for multiple steps? This problem is the key to solving distributionally robust control and learning-based control of such learned system models under a data-distribution shift. Different from previous works that use either static ambiguity sets, e.g., fixed Wasserstein balls, or dynamic ambiguity sets under known piece-wise linear (or affine) dynamics, we propose an algorithm that exactly propagates ambiguity sets through nonlinear data-driven models using the Koopman operator and CME, via the kernel maximum mean discrepancy geometry. Through both theoretical and numerical analysis, we show that our kernel ambiguity sets are the natural geometric structure for the learned data-driven dynamical system models.

Authors:László Csató

Abstract: Assume that some ordinal preferences can be represented by a weakly connected directed acyclic graph. The data are collected into an incomplete pairwise comparison matrix, the missing entries are estimated, and the priorities are derived from the optimally filled pairwise comparison matrix. Our paper studies whether these weights are consistent with the partial order given by the underlying graph. According to previous results from the literature, two popular procedures, the incomplete eigenvector and the incomplete logarithmic least squares methods fail to satisfy the required property. Here, it is shown that the recently introduced lexicographically optimal completion combined with any of these weighting methods avoids ordinal violation in the above setting. This finding provides a powerful argument for using the lexicographically optimal completion to determine the missing elements in an incomplete pairwise comparison matrix.

Authors:Agostino Martinelli

Abstract: This erratum highlights a very serious error in a paper published by SIAM Review in 2011. The error is in Section 6.2 of [1]. It is very important to notify this error because of the following two reasons: (i) [1] is one of the most cited contributions in the field of identifiability of viral dynamics models, and (ii)the error is relevant because, as a result of it, a very popular viral model (perhaps the most popular in the field of HIV dynamics) has been classified as identifiable. In contrast, three of its parameters are not identifiable, even locally. This erratum first proves the non uniqueness of the three unidentifiable parameters by exhibiting infinitely many distinct but indistinguishable values of them. The non uniqueness is even local. Then, this erratum details the error made by the authors of [1] which produced the claimed (but false) local identifiability of all the model parameters.

Authors:Tam Le TSE-R

Abstract: Motivated by the conspicuous use of momentum based algorithms in deep learning, we study a nonsmooth nonconvex stochastic heavy ball method and show its convergence. Our approach relies on semialgebraic assumptions, commonly met in practical situations, which allow to combine a conservative calculus with nonsmooth ODE methods. In particular, we can justify the use of subgradient sampling in practical implementations that employ backpropagation or implicit differentiation. Additionally, we provide general conditions for the sample distribution to ensure the convergence of the objective function. As for the stochastic subgradient method, our analysis highlights that subgradient sampling can make the stochastic heavy ball method converge to artificial critical points. We address this concern showing that these artifacts are almost surely avoided when initializations are randomized.

Authors:Guillaume Lauga OCKHAM, Elisa Riccietti OCKHAM, Nelly Pustelnik Phys-ENS, Paulo Gonçalves OCKHAM

Abstract: This paper presents IML FISTA, a multilevel inertial and inexact forward-backward algorithm, based on the use of the Moreau envelope to build efficient and useful coarse corrections. Such construction is provided for a broad class of composite optimization problems with proximable functions. This approach is supported by strong theoretical guarantees: we prove both the rate of convergence and the convergence of the iterates to a minimum in the convex case, an important result for ill-posed problems. We evaluate our approach on several image reconstruction problems and we show that it considerably accelerates the convergence of classical methods such as FISTA, for large-scale images.

Authors:Elisa Continelli, Cristina Pignotti

Abstract: In this paper, we deal with a minimum time problem in presence of a time delay $\tau.$ The value function of the considered optimal control problem is no longer defined in a subset of $\mathbb{R}^{n}$, as it happens in the undelayed case, but its domain is a subset of the Banach space $C([-\tau,0];\mathbb{R}^{n})$. For the undelayed minimum time problem, it is known that the value function associated with it is semiconcave in a subset of the reachable set and is a viscosity solution of a suitable Hamilton-Jacobi-Belmann equation. The Hamilton-Jacobi theory for optimal control problems involving time delays has been developed by several authors. Here, we are rather interested in investigating the regularity properties of the minimum time functional. Extending classical arguments, we are able to prove that the minimum time functional is semiconcave in a suitable subset of the reachable set.

Authors:Meyer Scetbon

Abstract: In this note, we propose polynomial-time algorithms solving the Monge and Kantorovich formulations of the $\infty$-optimal transport problem in the discrete and finite setting. It is the first time, to the best of our knowledge, that efficient numerical methods for these problems have been proposed.

Authors:Yiyang Zhang, Junyi Liu, Xiaobo Zhao

Abstract: Focusing on stochastic programming (SP) with covariate information, this paper proposes an empirical risk minimization (ERM) method embedded within a nonconvex piecewise affine decision rule (PADR), which aims to learn the direct mapping from features to optimal decisions. We establish the nonasymptotic consistency result of our PADR-based ERM model for unconstrained problems and asymptotic consistency result for constrained ones. To solve the nonconvex and nondifferentiable ERM problem, we develop an enhanced stochastic majorization-minimization algorithm and establish the asymptotic convergence to (composite strong) directional stationarity along with complexity analysis. We show that the proposed PADR-based ERM method applies to a broad class of nonconvex SP problems with theoretical consistency guarantees and computational tractability. Our numerical study demonstrates the superior performance of PADR-based ERM methods compared to state-of-the-art approaches under various settings, with significantly lower costs, less computation time, and robustness to feature dimensions and nonlinearity of the underlying dependency.

Authors:Cyrille Kenne, Gisèle Mophou, Mahamadi Warma

Abstract: In this paper, a class of semilinear fractional elliptic equations associated to the spectral fractional Dirichlet Laplace operator is considered. We establish the existence of optimal solutions as well as a minimum principle of Pontryagin type and the first order necessary optimality conditions of associated optimal control problems. Second order conditions for optimality are also obtained for $L^{\infty}$ and $L^2-$ local solutions under some structural assumptions.

Authors:Roberto Andreani, Gabriel Haeser, Leonardo M. Mito, Héctor Ramírez

Abstract: In a previous paper [R. Andreani, G. Haeser, L. M. Mito, H. Ram\'irez, T. P. Silveira. First- and second-order optimality conditions for second-order cone and semidefinite programming under a constant rank condition. Mathematical Programming, 2023. DOI: 10.1007/s10107-023-01942-8] we introduced a constant rank constraint qualification for nonlinear semidefinite and second-order cone programming by considering all faces of the underlying cone. This condition is independent of Robinson's condition and it implies a strong second-order necessary optimality condition which depends on a single Lagrange multiplier instead of the full set of Lagrange multipliers. In this paper we expand on this result in several directions, namely, we consider the larger class of $\mathcal{C}^2-$cone reducible constraints and we show that it is not necessary to consider all faces of the cone; instead a single specific face should be considered (which turns out to be weaker than Robinson's condition) in order for the first order necessary optimality condition to hold. This gives rise to a notion of facial reduction for nonlinear conic programming, that allows locally redefining the original problem only in terms of this specific face instead of the whole cone, providing a more robust formulation of the problem in which Robinson's condition holds. We were also able to prove the strong second-order necessary optimality condition in this context by considering only the subfaces of this particular face, which is a new result even in nonlinear programming.

Authors:László Csató

Abstract: The best-worst method is an increasingly popular approach to solving multi-criteria decision-making problems. Recently, the logarithmic least squares method has been proposed to derive priorities in the best-worst method since it has favourable properties such as the uniqueness of the weights, simple calculation, and the consideration of indirect comparisons. The current paper gives a sufficient condition for the logarithmic least squares method to guarantee the lack of ordinal violations in the best-worst method. It implies that the logarithmic least squares priorities are consistent with the preference order given by the decision-maker if the best alternative is at least two times more desirable than the others and the worst alternative is at least two times less desirable than the others, furthermore, the number of alternatives exceeds three. Our result provides another argument for using the logarithmic least squares priorities in the best-worst method.

Authors:Feng Guo, Jie Wang

Abstract: We study a class of polynomial optimization problems with a robust polynomial matrix inequality constraint for which the uncertainty set is defined also by a polynomial matrix inequality (including robust polynomial semidefinite programs as a special case). Under certain SOS-convexity assumptions, we construct a hierarchy of moment-SOS relaxations for this problem to obtain convergent upper bounds of the optimal value by solving a sequence of semidefinite programs. To this end, we apply the Positivstellensatz for polynomial matrices and its dual matrix-valued moment theory to a conic reformulation of the problem. Most of the nice features of the moment-SOS hierarchy for the scalar polynomial optimization are generalized to the matrix case. In particular, the finite convergence of the hierarchy can be also certified if the flat extension condition holds. To extract global minimizers in this case, we develop a linear algebra approach to recover the representing matrix-valued measure for the corresponding truncated matrix-valued moment problem. As an application, we use this hierarchy to solve the problem of minimizing the smallest eigenvalue of a polynomial matrix subject to a polynomial matrix inequality. Finally, if SOS-convexity is replaced by convexity, we can still approximate the optimal value as closely as desired by solving a sequence of semidefinite programs, and certify global optimality in case that certain flat extension conditions hold true.

Authors:Victor Ayala, Adriano Da Silva, Maria Torreblanca

Abstract: Our main concern is to continue developing the theory of Linear Control Systems on homogeneous spaces of connected Lie groups. In this manuscript we solve a specific issue for this class of systems: time-optimal problem on a cylinder, a homogeneous space of the solvable Lie group of dimension two.

Authors:Rossen Nenov, Dang-Khoa Nguyen, Peter Balazs

Abstract: The phase retrieval problem is found in various areas of applications of engineering and applied physics. It is also a very active field of research in mathematics, signal processing and machine learning. In this paper, we present an accelerated version of the well known Fast Griffin-Lim algorithm (FGLA) for the phase retrieval problem in a general setting. It has increased the speed of convergence, and most importantly, the limit points of the generated sequence can reach a significantly smaller error than the ones generated by FGLA. We will give a motivation of the acceleration and compare it numerically to its predecessors and other algorithms typically used to solve similar problems.

Authors:Jiadong Liang, Yuze Han, Xiang Li, Zhihua Zhang

Abstract: In this paper we consider linearly constrained optimization problems and propose a loopless projection stochastic approximation (LPSA) algorithm. It performs the projection with probability $p_n$ at the $n$-th iteration to ensure feasibility. Considering a specific family of the probability $p_n$ and step size $\eta_n$, we analyze our algorithm from an asymptotic and continuous perspective. Using a novel jump diffusion approximation, we show that the trajectories connecting those properly rescaled last iterates weakly converge to the solution of specific stochastic differential equations (SDEs). By analyzing SDEs, we identify the asymptotic behaviors of LPSA for different choices of $(p_n, \eta_n)$. We find that the algorithm presents an intriguing asymptotic bias-variance trade-off and yields phase transition phenomenons, according to the relative magnitude of $p_n$ w.r.t. $\eta_n$. This finding provides insights on selecting appropriate ${(p_n, \eta_n)}_{n \geq 1}$ to minimize the projection cost. Additionally, we propose the Debiased LPSA (DLPSA) as a practical application of our jump diffusion approximation result. DLPSA is shown to effectively reduce projection complexity compared to vanilla LPSA.

Authors:Kexue Zhang, Elena Braverman

Abstract: This paper studies the problem of event-triggered impulsive control for discrete-time systems. A novel periodic event-triggering scheme with two tunable parameters is presented to determine the moments of updating impulsive control signals which are called event times. Sufficient conditions are established to guarantee asymptotic stability of the resulting impulsive systems. It is worth mentioning that the event times are different from the impulse times, that is, the control signals are updated at each event time but the actuator performs the impulsive control tasks at a later time due to time delays. The effectiveness of our theoretical result with the proposed scheme is illustrated by three examples.

Authors:Jin Guo, Ting Gao, Peng Zhang, Jinqiao Duan

Abstract: This investigation focuses on discovering the most probable transition pathway for stochastic dynamical systems employing reinforcement learning. We first utilize Onsager-Machlup theory to quantify rare events in stochastic dynamical systems, and then convert the most likely transition path issue into a finite-horizon optimal control problem, because, in many instances, the transition path cannot be determined explicitly by variation. We propose the terminal prediction method and integrate it with reinforcement learning, develop our algorithm Finite Horizon Deep Deterministic Policy Gradient(FH-DDPG) to deal with the finite-horizon optimal control issue. Next, we present the convergence analysis of the algorithm for the value function estimation in terms of the neural network approximation error and the sampling error when estimating the network. Finally, experiments are conducted for the transition problem under Gaussian noise to verify the effectiveness of the algorithm.

Authors:Woundjiagué Apollinaire, Rodwell Kufakunesu, Julius Esunge

Abstract: In this research, we present an analysis of the optimal investment, consumption, and life insurance acquisition problem for a wage earner with partial information. Our study considers the non-linear filter case where risky asset prices are correlated to the factor processes under constant relative risk aversion (CRRA) preferences. We introduce a more general framework with an incomplete market, random parameters adapted to the Brownian motion filtration, and a general factor process with a non-linear state estimation and a correlation between the state process (risky asset prices) and the factor process. To address the wage earner's problem, we formulate it as a stochastic control problem with partial information where the risky assets prices are correlated to the factor processes. Our framework is extensive since the non-linear filter applied to the linear case gives a more robust result than the Kalman filter. We obtain the non-linear filter through the Zakai equation and derive a system of the Hamilton-Jacobi-Bellman (HJB) equation and two backward stochastic differential equations (BSDE). We establish the existence and uniqueness of the solution, prove the verification theorem, and construct the optimal strategy.

Authors:Hoang Huy Nguyen, Siva Theja Maguluri

Abstract: We consider a nonlinear discrete stochastic control system, and our goal is to design a feedback control policy in order to lead the system to a prespecified state. We adopt a stochastic approximation viewpoint of this problem. It is known that by solving the corresponding continuous-time deterministic system, and using the resulting feedback control policy, one ensures almost sure convergence to the prespecified state in the discrete system. In this paper, we adopt such a control mechanism and provide its finite-sample convergence bounds whenever a Lyapunov function is known for the continuous system. In particular, we consider four cases based on whether the Lyapunov function for the continuous system gives exponential or sub-exponential rates and based on whether it is smooth or not. We provide the finite-time bounds in all cases. Our proof relies on constructing a Lyapunov function for the discrete system based on the given Lyapunov function for the continuous system. We do this by appropriately smoothing the given function using the Moreau envelope. We present numerical experiments corresponding to the various cases, which validate the rates we establish.

Authors:Benoît, Bonnet-Weill, Hélène Frankowska

Abstract: In this article, we derive necessary and sufficient conditions for the existence of solutions to state-constrained continuity inclusions in Wasserstein spaces whose right-hand sides may be discontinuous in time. These latter are based on fine investigations of the infinitesimal behaviour of the underlying reachable sets, through which we show that up to a negligible set of times, every admissible velocity of the inclusion can be approximately realised as the metric derivative of a solution of the dynamics, and vice versa. Building on these results, we are able to establish necessary and sufficient geometric conditions for the viability and invariance of stationary and time-dependent constraints, which involve a suitable notion of contingent cones in Wasserstein spaces, presented in ascending order of generality. We then close the article by exhibiting two prototypical examples of constraints sets appearing in applications for which one can compute relevant subfamilies of contingent directions.

Authors:R. Deb, A. K. Das

Abstract: In this article we consider the sparse solutions of the tensor complementarity problem (TCP) which are the solutions of the smallest cardinality. We establish a connection between the least element of the feasible solution set of TCP and sparse solution for $Z$-tensor. We propose a $p$ norm regularized minimization model when $p\in (0,1)$ and show that it can approximate sparse solution applying the regularization of parameter. Keywords: Tensor complementarity problem, sparse solution, $l_p$ regularized minimization, $Z$-tensor.

Authors:Chunming Tang, Hao He, Jinbao Jian, Miantao Chao

Abstract: In this paper, a descent method for nonsmooth multiobjective optimization problems on complete Riemannian manifolds is proposed. The objective functions are only assumed to be locally Lipschitz continuous instead of convexity used in existing methods. A necessary condition for Pareto optimality in Euclidean space is generalized to the Riemannian setting. At every iteration, an acceptable descent direction is obtained by constructing a convex hull of some Riemannian $\varepsilon$-subgradients. And then a Riemannian Armijo-type line search is executed to produce the next iterate. The convergence result is established in the sense that a point satisfying the necessary condition for Pareto optimality can be generated by the algorithm in a finite number of iterations. Finally, some preliminary numerical results are reported, which show that the proposed method is efficient.

Authors:Panagiotis D. Grontas, Carlo Cenedese, Marta Fochesato, Giuseppe Belgioioso, John Lygeros, Florian Dörfler

Abstract: We study the problem of optimally routing plug-in electric and conventional fuel vehicles on a city level. In our model, commuters selfishly aim to minimize a local cost that combines travel time, from a fixed origin to a desired destination, and the monetary cost of using city facilities, parking or service stations. The traffic authority can influence the commuters' preferred routing choice by means of personalized discounts on parking tickets and on the energy price at service stations. We formalize the problem of designing these monetary incentives optimally as a large-scale bilevel game, where constraints arise at both levels due to the finite capacities of city facilities and incentives budget. Then, we develop an efficient decentralized solution scheme with convergence guarantees based on BIG Hype, a recently-proposed hypergradient-based algorithm for hierarchical games. Finally, we validate our model via numerical simulations over the Anaheim's network, and show that the proposed approach produces sensible results in terms of traffic decongestion and it is able to solve in minutes problems with more than 48000 variables and 110000 constraints.

Authors:Leon Tolksdorf, Arturo Tejada, Nathan van de Wouw, Christian Birkner

Abstract: In automated driving, risk describes potential harm to passengers of an autonomous vehicle (AV) and other road users. Recent studies suggest that human-like driving behavior emerges from embedding risk in AV motion planning algorithms. Additionally, providing evidence that risk is minimized during the AV operation is essential to vehicle safety certification. However, there has yet to be a consensus on how to define and operationalize risk in motion planning or how to bound or minimize it during operation. In this paper, we define a stochastic risk measure and introduce it as a constraint into both robust and stochastic nonlinear model predictive path-following controllers (RMPC and SMPC respectively). We compare the vehicle's behavior arising from employing SMPC and RMPC with respect to safety and path-following performance. Further, the implementation of an automated driving example is provided, showcasing the effects of different risk tolerances and uncertainty growths in predictions of other road users for both cases. We find that the RMPC is significantly more conservative than the SMPC, while also displaying greater following errors towards references. Further, the RMPCs behavior cannot be considered as human-like. Moreover, unlike SMPC, the RMPC cannot account for different risk tolerances. The RMPC generates undesired driving behavior for even moderate uncertainties, which are handled better by the SMPC.

Authors:Jonas Hansson, Emma Tegling

Abstract: This paper studies the problem of coordinating a group of $n$th-order integrator systems. As for the well-studied conventional consensus problem, we consider linear and distributed control with only local and relative measurements. We propose a closed-loop dynamic that we call serial consensus and prove it achieves $n$th order consensus regardless of model order and underlying network graph. This alleviates an important scalability limitation in conventional consensus dynamics of order $n\ge 2$, whereby they may lose stability if the underlying network grows. The distributed control law which achieves the desired closed loop dynamics is shown to be localized and obey the limitation to relative state measurements. Furthermore, through use of the small-gain theorem, the serial consensus system is shown to be robust to both model and feedback uncertainties. We illustrate the theoretical results through examples.

Authors:Andrea Poiatti, Andrea Signori

Abstract: In this contribution, we study an optimal control problem for the celebrated nonlocal Cahn-Hilliard equation endowed with the singular Flory-Huggins potential in the three-dimensional setting. The control enters the governing state system in a nonlinear fashion in the form of a prescribed solenoidal, that is a divergence-free, vector field, whereas the cost functional to be minimized is of tracking-type. The novelties of the present paper are twofold: in addition to the control application, the intrinsic difficulties of the optimization problem forced us to first establish new regularity results on the nonlocal Cahn-Hilliard equation that were unknown even without the coupling with a velocity field and are therefore of independent interest. This happens to be shown using the recently proved separation property along with ad hoc H\"older regularities and a bootstrap method. For the control problem, the existence of an optimal strategy as well as first-order necessary conditions are then established.

Authors:Liviu Aolaritei, Marta Fochesato, John Lygeros, Florian Dörfler

Abstract: We study model predictive control (MPC) problems for stochastic LTI systems, where the noise distribution is unknown, compactly supported, and only observable through a limited number of i.i.d. noise samples. Building upon recent results in the literature, which show that distributional uncertainty can be efficiently captured within a Wasserstein ambiguity set, and that such ambiguity sets propagate exactly through the system dynamics, we start by formulating a novel Wasserstein Tube MPC (WT-MPC) problem, with distributionally robust CVaR constraints. We then show that the WT-MPC problem: (1) is a direct generalization of the (deterministic) Robust Tube MPC (RT-MPC) to the stochastic setting; (2) through a scalar parameter, it interpolates between the data-driven formulation based on sample average approximation and the RT-MPC formulation, allowing us to optimally trade between safety and performance; (3) admits a tractable convex reformulation; and (4) is recursively feasible. We conclude the paper with a numerical comparison of WT-MPC and RT-MPC.

Authors:Patrick N. Raanes, Andreas S. Stordal, Rolf J. Lorentzen

Abstract: In robust optimisation problems the objective function consists of an average over (an ensemble of) uncertain parameters. Ensemble optimisation (EnOpt) implements steepest descent by estimating the gradient using linear regression on Monte-Carlo simulations of (an ensemble of) control parameters. Applying EnOpt for robust optimisation is costly unless the evaluations over the two ensembles are combined, i.e. 'paired'. Here, we provide a new and more rigorous perspective on the stochastic simplex approximate gradient (StoSAG) used in EnOpt, explaining how it addresses detrimental cross-correlations arising from pairing by only capturing the variability due to the control vector, and not the vector of uncertain parameters. A few minor variants are derived from a generalised derivation, as well as a new approach using decorrelation. These variants are tested on linear and non-linear toy gradient estimation problems, where they achieve highly similar accuracy, but require a very large ensemble size to outperform the non-robust approach when accounting for variance and not just bias. Other original contributions include a discussion of the particular robust control objectives for which EnOpt is suited, illustrations, a variance reduction perspective, and a discussion on the centring in covariance and gradient estimation.

Authors:Ksenia Bestuzheva, Helena Völker, Ambros Gleixner

Abstract: Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into alternative certificates and approaches to global optimization. We consider sums of nonnegative circuit polynomials (SONC) certificates, which are well-suited for sparse problems since the computational cost depends on the number of terms in the polynomials and does not depend on the degrees of the polynomials. We propose a method that guarantees that given finite variable domains, a SONC relaxation will yield a finite dual bound. This method opens up a new approach to utilizing variable bounds in SONC-based methods, which is particularly crucial for integrating SONC relaxations into branch-and-bound algorithms. We report on computational experiments with incorporating SONC relaxations into the spatial branch-and-bound algorithm of the mixed-integer nonlinear programming framework SCIP. Applying our strengthening method increases the number of instances where the SONC relaxation of the root node yielded a finite dual bound from 9 to 330 out of 349 instances in the test set.

Authors:Raphaël Prunier

Abstract: This paper is concerned with stability of the ball for a class of isoperimetric problems under convexity constraint. Considering the problem of minimizing $P+\varepsilon R$ among convex subsets of $\mathbb{R}^N$ of fixed volume, where $P$ is the perimeter functional, $R$ is a perturbative term and $\varepsilon>0$ is a small parameter, stability of the ball for this perturbed isoperimetric problem means that the ball is the unique (local, up to translation) minimizer for any $\varepsilon$ sufficiently small. We investigate independently two specific cases where $\Omega\mapsto R(\Omega)$ is an energy arising from PDE theory, namely the capacity and the first Dirichlet eigenvalue of a domain $\Omega\subset\mathbb{R}^N$. While in both cases stability fails among all shapes, in the first case we prove (non-sharp) stability of the ball among convex shapes, by building an appropriate competitor for the capacity of a perturbation of the ball. In the second case we prove sharp stability of the ball among convex shapes by providing the optimal range of $\varepsilon$ such that stability holds, relying on the \emph{selection principle} technique and a regularity theory under convexity constraint.

Authors:Gabriel Nicolosi, Christopher Griffin

Abstract: The Bass diffusion equation is a well-known and established modeling approach for describing new product adoption in a competitive market. This model also describes diffusion phenomena in various contexts: infectious disease spread modeling and estimation, rumor spread on social networks, prediction of renewable energy technology markets, among others. Most of these models, however, consider a deterministic trajectory of the associated state variable (e.g., market-share). In reality, the diffusion process is subject to noise, and a stochastic component must be added to the state dynamics. The stochastic Bass model has also been studied in many areas, such as energy markets and marketing. Exploring the stochastic version of the Bass diffusion model, we propose in this work an approximation of (stochastic) optimal control surfaces for a continuous-time problem arising from a $2\times2$ skew symmetric evolutionary game, providing the stochastic counter-part of the Fourier-based optimal control approximation already existent in the literature.

Authors:Jianfeng Zhang

Abstract: For time inconsistent optimal control problems, a quite popular approach is the equilibrium approach, taken by the sophisticated agents. In this short note we construct a deterministic continuous time example where the unique equilibrium is dominated by another control. Therefore, in this situation it may not be wise to take the equilibrium strategy.

Authors:Etika Agarwal, Karthik S. Gurumoorthy, Ankit Ajit Jain, Shantala Manchenahally

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%.

Authors:Lijun Bo, Yijie Huang, Xiang Yu

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.

Authors:Tran Ngoc Thang, Dao Minh Hoang, Nguyen Viet Dung

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.

Authors:T. Alissa Schenck, Christian A. Hans

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.

Authors:Feihu Huang, Songcan Chen

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.

Authors:Yuto Watanabe, Kazunori Sakurama

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.

Authors:Lukas Lanza, Dario Dennstädt, Thomas Berger, Karl Worthmann

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.

Authors:François Dubois LMSSC, LMO, Hedy César Ramírez-De-{Á}vila TecNM, Juan Antonio Rojas-Quintero CONACYT

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.

Authors:Bo Yang, Xinyuan Zhao, Xudong Li, Defeng Sun

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.

Authors:Pierluigi Colli, Gianni Gilardi, Gabriela Marinoschi, Elisabetta Rocca

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.

Authors:Daniel Liberzon

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.

Authors:Tianyun Tang, Kim-Chuan Toh, Nachuan Xiao, Yinyu Ye

Abstract: In this paper, we propose a cubic-regularized Riemannian optimization method (RDRSOM), which partially exploits the second order information and achieves the iteration complexity of $\mathcal{O}(1/\epsilon^{3/2})$. In order to reduce the per-iteration computational cost, we further propose a practical version of (RDRSOM), which is an extension of the well known Barzilai-Borwein method and achieves the iteration complexity of $\mathcal{O}(1/\epsilon^{3/2})$. We apply our method to solve a nonlinear formulation of the wireless sensor network localization problem whose feasible set is a Riemannian manifold that has not been considered in the literature before. Numerical experiments are conducted to verify the high efficiency of our algorithm compared to state-of-the-art Riemannian optimization methods and other nonlinear solvers.

Authors:Marianne Akian, Stéphane Gaubert, Shanqing Liu

Abstract: We introduce a new numerical method to approximate the solution of a finite horizon deterministic optimal control problem. We exploit two Hamilton-Jacobi-Bellman PDE, arising by considering the dynamics in forward and backward time. This allows us to compute a neighborhood of the set of optimal trajectories, in order to reduce the search space. The solutions of both PDE are successively approximated by max-plus linear combinations of appropriate basis functions, using a hierarchy of finer and finer grids. We show that the sequence of approximate value functions obtained in this way does converge to the viscosity solution of the HJB equation in a neighborhood of optimal trajectories. Then, under certain regularity assumptions, we show that the number of arithmetic operations needed to compute an approximate optimal solution of a $d$-dimensional problem, up to a precision $\varepsilon$, is bounded by $O(C^d (1/\varepsilon) )$, for some constant $C>1$, whereas ordinary grid-based methods have a complexity in$O(1/\varepsilon^{ad}$) for some constant $a>0$.

Authors:Matteo Basei, Giorgio Ferrari, Neofytos Rodosthenous

Abstract: The socioeconomic impact of pollution naturally comes with uncertainty due to, e.g., current new technological developments in emissions' abatement or demographic changes. On top of that, the trend of the future costs of the environmental damage is unknown: Will global warming dominate or technological advancements prevail? The truth is that we do not know which scenario will be realised and the scientific debate is still open. This paper captures those two layers of uncertainty by developing a real-options-like model in which a decision maker aims at adopting a once-and-for-all costly reduction in the current emissions rate, when the stochastic dynamics of the socioeconomic costs of pollution are subject to Brownian shocks and the drift is an unobservable random variable. By keeping track of the actual evolution of the costs, the decision maker is able to learn the unknown drift and to form a posterior dynamic belief of its true value. The resulting decision maker's timing problem boils down to a truly two-dimensional optimal stopping problem which we address via probabilistic free-boundary methods and a state-space transformation. We show that the optimal timing for implementing the emissions reduction policy is the first time that the learning process has become ``decisive'' enough; that is, when it exceeds a time-dependent percentage. This is given in terms of an endogenously determined threshold uniquely solving a nonlinear integral equation, which we can solve numerically. We discuss the implications of the optimal policy and also perform comparative statics to understand the role of the relevant model's parameters in the optimal policy.

Authors:Yankai Lin, Michelle S. Chong, Carlos Murguia

Abstract: We consider the problem of ensuring the safety of nonlinear control systems under adversarial signals. Using Lyapunov based reachability analysis, we first give sufficient conditions to assess safety, i.e., to guarantee that the states of the control system, when starting from a given initial set, always remain in a prescribed safe set. We consider polynomial systems with semi-algebraic safe sets. Using the S-procedure for polynomial functions, safety conditions can be formulated as a Sum-Of-Squares (SOS) programme, which can be solved efficiently. When safety cannot be guaranteed, we provide tools via SOS to synthesize polynomial controllers that enforce safety of the closed loop system. The theoretical results are illustrated through numerical simulations.

Authors:Yongqiang Wang

Abstract: In distributed optimization or Nash-equilibrium seeking over directed graphs, it is crucial to find a matrix norm under which the disagreement of individual agents' states contracts. In existing results, the matrix norm is usually defined by approximating the spectral radius of the matrix, which is possible when the matrix is real and has zero row-sums. In this brief note, we show that this technique can be applied to general square complex matrices. More specifically, we prove that the spectral radius of any complex square matrix can be approximated by its "weighted" spectral norm to an arbitrary degree of accuracy.

Authors:Yingzhen Yang, Ping Li

Abstract: Nonconvex and nonsmooth optimization problems are important and challenging for statistics and machine learning. In this paper, we propose Projected Proximal Gradient Descent (PPGD) which solves a class of nonconvex and nonsmooth optimization problems, where the nonconvexity and nonsmoothness come from a nonsmooth regularization term which is nonconvex but piecewise convex. In contrast with existing convergence analysis of accelerated PGD methods for nonconvex and nonsmooth problems based on the Kurdyka-\L{}ojasiewicz (K\L{}) property, we provide a new theoretical analysis showing local fast convergence of PPGD. It is proved that PPGD achieves a fast convergence rate of $\cO(1/k^2)$ when the iteration number $k \ge k_0$ for a finite $k_0$ on a class of nonconvex and nonsmooth problems under mild assumptions, which is locally Nesterov's optimal convergence rate of first-order methods on smooth and convex objective function with Lipschitz continuous gradient. Experimental results demonstrate the effectiveness of PPGD.

Authors:Yixuan Lin, Ji Liu

Abstract: The push-sum algorithm is probably the most important distributed averaging approach over directed graphs, which has been applied to various problems including distributed optimization. This paper establishes the explicit absolute probability sequence for the push-sum algorithm, and based on which, constructs quadratic Lyapunov functions for push-sum based distributed optimization algorithms. As illustrative examples, the proposed novel analysis tool can improve the convergence rates of the subgradient-push and stochastic gradient-push, two important algorithms for distributed convex optimization over unbalanced directed graphs. Specifically, the paper proves that the subgradient-push algorithm converges at a rate of $O(1/\sqrt{t})$ for general convex functions and stochastic gradient-push algorithm converges at a rate of $O(1/t)$ for strongly convex functions, over time-varying unbalanced directed graphs. Both rates are respectively the same as the state-of-the-art rates of their single-agent counterparts and thus optimal, which closes the theoretical gap between the centralized and push-sum based (sub)gradient methods. The paper further proposes a heterogeneous push-sum based subgradient algorithm in which each agent can arbitrarily switch between subgradient-push and push-subgradient. The heterogeneous algorithm thus subsumes both subgradient-push and push-subgradient as special cases, and still converges to an optimal point at an optimal rate. The proposed tool can also be extended to analyze distributed weighted averaging.

Authors:Alexander J. Zaslavski

Abstract: In his recent research M. K. Tam (2018) considered a framework for the analysis of iterative algorithms which can be described in terms of a structured set-valued operator. At each point in the ambient space, the value of the operator can be expressed as a finite union of values of single-valued paracontracting operators. He showed that the associated fixed point iteration is locally convergent around strong fixed points. This result generalizes a theorem due to Bauschke and Noll (2014). In the present paper we generalize the result of Tam and show the global convergence of his algorithm for an arbitrary starting point. An analogous result is also proved for the Krasnosel'ski-Mann iterations.

Authors:Pierre Marion, Raphaël Berthier

Abstract: We study the training dynamics of shallow neural networks, in a two-timescale regime in which the stepsizes for the inner layer are much smaller than those for the outer layer. In this regime, we prove convergence of the gradient flow to a global optimum of the non-convex optimization problem in a simple univariate setting. The number of neurons need not be asymptotically large for our result to hold, distinguishing our result from popular recent approaches such as the neural tangent kernel or mean-field regimes. Experimental illustration is provided, showing that the stochastic gradient descent behaves according to our description of the gradient flow and thus converges to a global optimum in the two-timescale regime, but can fail outside of this regime.

Authors:Mattia Bianchi, Emilio Benenati, Sergio Grammatico

Abstract: We study generalized games with full row rank equality constraints and we provide a strikingly simple proof of strong monotonicity of the associated KKT operator. This allows us to show linear convergence to a variational equilibrium of the resulting primal-dual pseudo-gradient dynamics. Then, we propose a fully-distributed algorithm with linear convergence guarantee for aggregative games under partial-decision information. Based on these results, we establish stability properties for online GNE seeking in games with time-varying cost functions and constraints. Finally, we illustrate our findings numerically on an economic dispatch problem for peer-to-peer energy markets.

Authors:Yair Censor, Rafiq Mansour, Daniel Reem

Abstract: Given two nonempty and disjoint intersections of closed and convex subsets, we look for a best approximation pair relative to them, i.e., a pair of points, one in each intersection, attaining the minimum distance between the disjoint intersections. We propose an iterative process based on projections onto the subsets which generate the intersections. The process is inspired by the Halpern-Lions-Wittmann-Bauschke algorithm and the classical alternating process of Cheney and Goldstein, and its advantage is that there is no need to project onto the intersections themselves, a task which can be rather demanding. We prove that under certain conditions the two interlaced subsequences converge to a best approximation pair. These conditions hold, in particular, when the space is Euclidean and the subsets which generate the intersections are compact and strictly convex. Our result extends the one of Aharoni, Censor and Jiang ["Finding a best approximation pair of points for two polyhedra", Computational Optimization and Applications 71 (2018), 509-523] which considered the case of finite-dimensional polyhedra.

Authors:Jaap Pedersen, Jann Michael Weinand, Chloi Syranidou, Daniel Rehfeldt

Abstract: Existing planning approaches for onshore wind farm siting and network integration often do not meet minimum cost solutions or social and environmental considerations. In this paper, we develop an approach for the multi-objective optimization of turbine locations and their network connection using a Quota Steiner tree problem. Applying a novel transformation on a known directed cut formulation, reduction techniques, and heuristics, we design an exact solver that makes large problem instances solvable and outperforms generic MIP solvers. Although our case studies in selected regions of Germany show large trade-offs between the objective criteria of cost and landscape impact, small burdens on one criterion can significantly improve the other criteria. In addition, we demonstrate that contrary to many approaches for exclusive turbine siting, network integration must be simultaneously optimized in order to avoid excessive costs or landscape impacts in the course of a wind farm project. Our novel problem formulation and the developed solver can assist planners in decision making and help optimize wind farms in large regions in the future.

Authors:Cuong Le, Tien Mai

Abstract: We study the assortment optimization problem under general linear constraints, where the customer choice behavior is captured by the Cross-Nested Logit model. In this problem, there is a set of products organized into multiple subsets (or nests), where each product can belong to more than one nest. The aim is to find an assortment to offer to customers so that the expected revenue is maximized. We show that, under the Cross-Nested Logit model, the assortment problem is NP-hard, even without any constraints. To tackle the assortment optimization problem, we develop a new discretization mechanism to approximate the problem by a linear fractional program with a performance guarantee of $\frac{1 - \epsilon}{1+\epsilon}$, for any accuracy level $\epsilon>0$. We then show that optimal solutions to the approximate problem can be obtained by solving mixed-integer linear programs. We further show that our discretization approach can also be applied to solve a joint assortment optimization and pricing problem, as well as an assortment problem under a mixture of Cross-Nested Logit models to account for multiple classes of customers. Our empirical results on a large number of randomly generated test instances demonstrate that, under a performance guarantee of 90%, the percentage gaps between the objective values obtained from our approximation methods and the optimal expected revenues are no larger than 1.2%.

Authors:John Cao, Muhammad Umar B. Niazi, Karl Henrik Johansson

Abstract: This paper presents a new observer-based approach to detect and isolate faulty sensors in industrial systems. Two types of sensor faults are considered: complete failure and sensor deterioration. The proposed method is applicable to general autonomous nonlinear systems without making any assumptions about its triangular and/or normal form, which is usually considered in the observer design literature. The key aspect of our approach is a learning-based design of the Luenberger observer, which involves using a neural network to approximate the injective map that transforms the nonlinear system into a stable linear system with output injection. This learning-based Luenberger observer accurately estimates the system's state, allowing for the detection of sensor faults through residual generation. The residual is computed as the norm of the difference between the system's measured output and the observer's predicted output vectors. Fault isolation is achieved by comparing each sensor's measurement with its corresponding predicted value. We demonstrate the effectiveness of our approach in capturing and isolating sensor faults while remaining robust in the presence of measurement noise and system uncertainty. We validate our method through numerical simulations of sensor faults in a network of Kuramoto oscillators.

Authors:Tuan Ngoc Hoang, Lim Yongdo, Yend Dong Nguyen

Abstract: This paper gives some results related to the research problem about infinite-dimensional affine variational inequalities raised by N.D. Yen and X. Yang [Affine variational inequalities on normed spaces, J. Optim. Theory Appl., 178 (2018), 36--55]. Namely, we obtain local error bounds for affine variational inequalities on Hilbert spaces. To do so, we revisit two fundamental properties of polyhedral mappings. Then, we prove a locally upper Lipschitzian property of the inverse of the residual mapping of the infinite-dimensional affine variational inequality under consideration. Finally, we derive the desired local error bounds from that locally upper Lipschitzian property.

Authors:Stéphane Drobot, Matteo Tacchi, Colin N. Jones

Abstract: This paper presents a novel Matlab toolbox, aimed at facilitating the use of polynomial optimization for stability analysis of nonlinear systems. Indeed, in the past decade several decisive contributions made it possible to recast the difficult problem of computing stability regions of nonlinear systems, under the form of convex optimization problems that are tractable in modest dimensions. However, these techniques combine sophisticated frameworks such as algebraic geometry, measure theory and mathematical programming, and existing software still requires their user to be fluent in Sum-of-Squares and Moment programming, preventing these techniques from being used more widely in the control community. To address this issue, SOStab entirely automates the writing and solving of optimization problems, and directly outputs relevant data for the user, while requiring minimal input. In particular, no specific knowledge of optimization is needed to use it.

Authors:Sébastien Lleo, Wolfgang J. Runggaldier

Abstract: A typical approach to tackle stochastic control problems with partial observation is to separate the control and estimation tasks. However, it is well known that this separation generally fails to deliver an actual optimal solution for risk-sensitive control problems. This paper investigates the separability of a general class of risk-sensitive investment management problems when a finite-dimensional filter exists. We show that the corresponding separated problem, where instead of the unobserved quantities, one considers their conditional filter distribution given the observations, is strictly equivalent to the original control problem. We widen the applicability of the so-called Modified Zakai Equation (MZE) for the study of the separated problem and prove that the MZE simplifies to a PDE in our approach. Furthermore, we derive criteria for separability. We do not solve the separated control problem but note that the existence of a finite-dimensional filter leads to a finite state space for the separated problem. Hence, the difficulty is equivalent to solving a complete observation risk-sensitive problem. Our results have implications for existing risk-sensitive investment management models with partial observations in that they establish their separability. Their implications for future research on new applications is mainly to provide conditions to ensure separability.

Authors:Jodi Dianetti

Abstract: We consider a class of non-cooperative N-player non-zero-sum stochastic differential games with singular controls, in which each player can affect a linear stochastic differential equation in order to minimize a cost functional which is quadratic in the state and linear in the control. We call these games linear-quadratic-singular stochastic differential games. Under natural assumptions, we show the existence of open-loop Nash equilibria, which are characterized through a linear system of forward-backward stochastic differential equations. The proof is based on an approximation via a sequence of games in which players are restricted to play Lipschitz continuous strategies. We then discuss an application of these results to a model of capacity expansion in oligopoly markets.

Authors:Martina Cerulli, Claudia Archetti, Elena Fernandez, Ivana Ljubic

Abstract: In last-mile delivery logistics, peer-to-peer logistic platforms play an important role in connecting senders, customers, and independent carriers to fulfill delivery requests. Since the carriers are not under the platform's control, the platform has to anticipate their reactions, while deciding how to allocate the delivery operations. Indeed, carriers' decisions largely affect the platform's revenue. In this paper, we model this problem using bilevel programming. At the upper level, the platform decides how to assign the orders to the carriers; at the lower level, each carrier solves a profitable tour problem to determine which offered requests to accept, based on her own profit maximization. Possibly, the platform can influence carriers' decisions by determining also the compensation paid for each accepted request. The two considered settings result in two different formulations: the bilevel profitable tour problem with fixed compensation margins and with margin decisions, respectively. For each of them, we propose single-level reformulations and alternative formulations where the lower-level routing variables are projected out. A branch-and-cut algorithm is proposed to solve the bilevel models, with a tailored warm-start heuristic used to speed up the solution process. Extensive computational tests are performed to compare the proposed formulations and analyze solution characteristics.

Authors:Jiaxu Liu, Song Chen, Shengze Cai, Chao Xu

Abstract: In this paper, we investigate a distributed aggregative optimization problem in a network, where each agent has its own local cost function which depends not only on the local state variable but also on an aggregated function of state variables from all agents. To accelerate the optimization process, we combine heavy ball and Nesterov's accelerated methods with distributed aggregative gradient tracking, and propose two novel algorithms named DAGT-HB and DAGT-NES for solving the distributed aggregative optimization problem. We analyse that the DAGT-HB and DAGT-NES algorithms can converge to an optimal solution at a global $\mathbf{R}-$linear convergence rate when the objective function is smooth and strongly convex, and when the parameters (e.g., step size and momentum coefficients) are selected within certain ranges. A numerical experiment on the optimal placement problem is given to verify the effectiveness and superiority of our proposed algorithms.

Authors:Jonas F. Haderlein, Andre D. H. Peterson, Parvin Zarei Eskikand, Anthony N. Burkitt, Iven M. Y. Mareels, David B. Grayden

Abstract: The empirical success of machine learning models with many more parameters than measurements has generated an interest in the theory of overparameterisation, i.e., underdetermined models. This paradigm has recently been studied in domains such as deep learning, where one is interested in good (local) minima of complex, nonlinear loss functions. Optimisers, like gradient descent, perform well and consistently reach good solutions. Similarly, nonlinear optimisation problems are encountered in the field of system identification. Examples of such high-dimensional problems are optimisation tasks ensuing from the reconstruction of model states and parameters of an assumed known dynamical system from observed time series. In this work, we identify explicit parallels in the benefits of overparameterisation between what has been analysed in the deep learning context and system identification. We test multiple chaotic time series models, analysing the optimisation process for unknown model states and parameters in batch mode. We find that gradient descent reaches better solutions if we assume more parameters to be unknown. We hypothesise that, indeed, overparameterisation leads us towards better minima, and that more degrees of freedom in the optimisation are beneficial so long as the system is, in principle, observable.

Authors:Sonali Sharma, K. Palpandi

Abstract: A tensor ${\mathcal A}$ of order $m$ and dimension $n$ is called a ${\rm Q}$-tensor if the tensor complementarity problem has a solution for all ${\bf q} \in {\mathbb R}^{n}$. This means that for every vector ${\bf q}$, there exists a vector ${\bf u}$ such that ${\bf u} \geq {\bf 0},{\bf w} = {\mathcal A}{\bf u}^{m-1}+{\bf q} \geq {\bf 0},~\text{and}~ {\bf u}^{T}{\bf w} = 0$. In this paper, we prove that within the class of rank one symmetric tensors, the ${\rm Q}$-tensors are precisely the positive tensors. Additionally, for a symmetric ${\mathrm Q}$-tensor ${\mathcal A}$ with $rank({\mathcal A})=2$, we show that ${\mathcal A}$ is an ${\mathrm R}_{0}$-tensor. The idea is inspired by the recent work of Parthasarathy et al. \cite{Parthasarathy} and Sivakumar et al. \cite{Sivakumar} on ${\rm Q}$-matrices.

Authors:Kangkang Deng, Jiang Hu

Abstract: We consider the problem of decentralized nonconvex optimization over a compact submanifold, where each local agent's objective function defined by the local dataset is smooth. Leveraging the powerful tool of proximal smoothness, we establish local linear convergence of the projected gradient descent method with unit step size for solving the consensus problem over the compact manifold. This serves as the basis for analyzing decentralized algorithms on manifolds. Then, we propose two decentralized methods, namely the decentralized projected Riemannian gradient descent (DPRGD) and the decentralized projected Riemannian gradient tracking (DPRGT) methods. We establish their convergence rates of $\mathcal{O}(1/\sqrt{K})$ and $\mathcal{O}(1/K)$, respectively, to reach a stationary point. To the best of our knowledge, DPRGT is the first decentralized algorithm to achieve exact convergence for solving decentralized optimization over a compact manifold. The key ingredients in the proof are the Lipschitz-type inequalities of the projection operator on the compact manifold and smooth functions on the manifold, which could be of independent interest. Finally, we demonstrate the effectiveness of our proposed methods compared to state-of-the-art ones through numerical experiments on eigenvalue problems and low-rank matrix completion.

Authors:Andreas Kofler, Fabian Altekrüger, Fatima Antarou Ba, Christoph Kolbitsch, Evangelos Papoutsellis, David Schote, Clemens Sirotenko, Felix Frederik Zimmermann, Kostas Papafitsoros

Abstract: We propose a method for fast and automatic estimation of spatially dependent regularization maps for total variation-based (TV) tomography reconstruction. The estimation is based on two distinct sub-networks, with the first sub-network estimating the regularization parameter-map from the input data while the second one unrolling T iterations of the Primal-Dual Three-Operator Splitting (PD3O) algorithm. The latter approximately solves the corresponding TV-minimization problem incorporating the previously estimated regularization parameter-map. The overall network is then trained end-to-end in a supervised learning fashion using pairs of clean-corrupted data but crucially without the need of having access to labels for the optimal regularization parameter-maps.

Authors:Abhijeet Vyas, Brian Bullins

Abstract: We propose a study of structured non-convex non-concave min-max problems which goes beyond standard first-order approaches. Inspired by the tight understanding established in recent works [Adil et al., 2022, Lin and Jordan, 2022b], we develop a suite of higher-order methods which show the improvements attainable beyond the monotone and Minty condition settings. Specifically, we provide a new understanding of the use of discrete-time $p^{th}$-order methods for operator norm minimization in the min-max setting, establishing an $O(1/\epsilon^\frac{2}{p})$ rate to achieve $\epsilon$-approximate stationarity, under the weakened Minty variational inequality condition of Diakonikolas et al. [2021]. We further present a continuous-time analysis alongside rates which match those for the discrete-time setting, and our empirical results highlight the practical benefits of our approach over first-order methods.

Authors:Ton de Kok

Abstract: We consider the classical discrete time lost-sales model under stationary continuous demand and linear holding and penalty costs and positive constant lead time. To date the optimal policy structure is only known implicitly by solving numerically the Bellman equations. In this paper we derive the first optimality equation for the lost-sales model. We propose a fixed non-stockout-probability (FP3) policy, implying that each period the order size ensures that P3, the probability of no-stockout at the end of the period of arrival of this order, equals some target value. The FP3-policy can be computed efficiently and accurately from an exact recursive expression and two-moment fits to the emerging random variables. We use the lost-sales optimality equation to compute the optimal FP3-policy. Comparison against the optimal policy for discrete demand suggests that the fixed P3-policy is close-to-optimal. An extensive numerical experiment shows that the FP3-policy outperforms other policies proposed in literature in 97% of all cases. Under the FP3-policy, the volatility of the replenishment process is much lower than the volatility of the demand process. This cv-reduction holds a promise for substantial cost reduction at upstream stages in the supply chain of the end-item under consideration, compared to the situation with backlogging.

Authors:Jiaqi Wang, Shuzhen Yang

Abstract: This paper introduces a new recursive stochastic optimal control problem driven by a forward-backward stochastic differential equations (FBSDEs), where the ter?minal time varies according to the constraints of the state of the forward equation. This new optimal control problem can be used to describe the investment portfolio problems with the varying investment period. Based on novel \r{ho}-moving variational and adjoint equations, we establish the stochastic maximum principle for this optimal control problem including the classical optimal control problem as a particular case. Furthermore, we propose an example to verify our main results.

Authors:Shimin Wang, Martin Guay, Dabo Xu

Abstract: This paper proposes a solution to the practical robust output regulation problem for a class of nonlinear systems with unknown control directions and uncertain exosystem dynamics. The concurrence of the unknown control directions and uncertain parameters in both the system dynamics and the exosystem pose a significant challenge to solve this problem. Moreover, in light of the nonlinear internal model approach, this paper converts the robust, practical output regulation problem into a robust non-adaptive stabilization problem for the augmented system with integral Input-to-State Stable (iISS) inverse dynamics. By employing an extremum-seeking control approach, the construction of the control laws avoids the use of Nussbaumtype gain techniques to handle the practical robust output regulation problem subject to time-varying control directions. The stability of the non-adaptive output regulation design is proven via a Lie bracket averaging technique where uniform ultimate boundedness of the closed-loop signals is guaranteed. As a result, the estimation and tracking errors converge to zero exponentially, provided that the frequency of the dither signal goes to infinity. Finally, a numerical example with unknown coefficients is provided to illustrate the validity of the theoretical results.

Authors:Tiziano Granucci

Abstract: In this paper we study the regularity and the boundedness of the minima of two classes of functionals of the calculus of variations

Authors:Nick Wulbusch, Reinhild Roden, Alexey Chernov, Matthias Blau

Abstract: In many applications, knowledge of the sound pressure transfer to the eardrum is important. The transfer is highly influenced by the shape of the ear canal and its acoustic properties, such as the acoustic impedance at the eardrum. Invasive procedures to measure the sound pressure at the eardrum are usually elaborate or costly. In this work, we propose a numerical method to estimate the transfer impedance at the eardrum given only input impedance measurements at the ear canal entrance by using one-dimensional first-order finite elements and Nelder-Mead optimization algorithm. Estimations on the area function of the ear canal and the acoustic impedance at the eardrum are achieved. Results are validated through numerical simulations on ten different ear canal geometries and three different acoustic impedances at the eardrum using synthetically generated data from three-dimensional finite element simulations.

Authors:Harold van Heukelum, Ruud Binnekamp, Rogier Wolfert

Abstract: Current systems design optimisation methodologies are one-sided as these ignore the dynamic interplay between people's preferences (demand) and engineering assets' physical performance (supply). Moreover, classical multi-objective optimisation methods contain fundamental (aggregation) modelling errors. Also, the classical multi-objective optimisation Pareto front will not offer a best-fit design point but rather a set of design performance alternatives. This leaves designers without a unique solution to their problems. Finally, current multi-objective optimisation processes are rather disconnected from design and management practices since these lack deep involvement of decision-makers for expressing their interests in one common preference domain. Therefore, a new open design systems methodology and a novel integrative optimisation method based on maximising the aggregated group preference are introduced in this paper. Their added value and use are demonstrated in two real-life infrastructure design exemplars, showing how to arrive at a true best fit for common-purpose design points.

Authors:Jun Liu, Yiming Meng, Maxwell Fitzsimmons, Ruikun Zhou

Abstract: The search for Lyapunov functions is a crucial task in the analysis of nonlinear systems. In this paper, we present a physics-informed neural network (PINN) approach to learning a Lyapunov function that is nearly maximal for a given stable set. A Lyapunov function is considered nearly maximal if its sub-level sets can be made arbitrarily close to the boundary of the domain of attraction. We use Zubov's equation to train a maximal Lyapunov function defined on the domain of attraction. Additionally, we propose conditions that can be readily verified by satisfiability modulo theories (SMT) solvers for both local and global stability. We provide theoretical guarantees on the existence of maximal Lyapunov functions and demonstrate the effectiveness of our computational approach through numerical examples.

Authors:Salvador Pineda, Juan Miguel Morales, Asunción Jiménez-Cordero

Abstract: The design of new strategies that exploit methods from Machine Learning to facilitate the resolution of challenging and large-scale mathematical optimization problems has recently become an avenue of prolific and promising research. In this paper, we propose a novel learning procedure to assist in the solution of a well-known computationally difficult optimization problem in power systems: The Direct Current Optimal Transmission Switching (DC-OTS). This model consists in finding the configuration of the power network that results in the cheapest dispatch of the power generating units. For this, the model includes a set of binaries that determine the on/off status of the switchable transmission lines. Therefore, the DC-OTS problem takes the form of a mixed-integer program, which is NP-hard in general. Its solution has been approached by way of exact and heuristic methods. The former employ techniques from mixed-integer programming to solve the problem to certified global optimality, while the latter seek to identify good solutions quickly. While the heuristic methods tend to be comparatively much faster, they may suggest suboptimal or even infeasible networks topologies. The proposed approach in this paper leverages known solutions to past instances of the DC-OTS problem to speed up the mixed-integer optimization of a new unseen model. Although it does not offer optimality guarantees, a series of numerical experiments run on a real-life power system dataset show that it features a very high success rate in identifying the optimal grid topology (especially when compared to alternative competing heuristics), while rendering remarkable speed-up factors.

Authors:Mario Sperl, Luca Saluzzi, Lars Grüne, Dante Kalise

Abstract: A new approach for the construction of separable approximations of optimal value functions from interconnected optimal control problems is presented. The approach is based on assuming decaying sensitivities between subsystems, enabling a curse-of-dimensionality free approximation, for instance by deep neural networks.

Authors:Thomas M. Surowiec, Shawn W. Walker

Abstract: We present an analysis and numerical study of an optimal control problem for the Landau-de Gennes (LdG) model of nematic liquid crystals (LCs), which is a crucial component in modern technology. They exhibit long range orientational order in their nematic phase, which is represented by a tensor-valued (spatial) order parameter $Q = Q(x)$. Equilibrium LC states correspond to $Q$ functions that (locally) minimize an LdG energy functional. Thus, we consider an $L^2$-gradient flow of the LdG energy that allows for finding local minimizers and leads to a semi-linear parabolic PDE, for which we develop an optimal control framework. We then derive several a priori estimates for the forward problem, including continuity in space-time, that allow us to prove existence of optimal boundary and external ``force'' controls and to derive optimality conditions through the use of an adjoint equation. Next, we present a simple finite element scheme for the LdG model and a straightforward optimization algorithm. We illustrate optimization of LC states through numerical experiments in two and three dimensions that seek to place LC defects (where $Q(x) = 0$) in desired locations, which is desirable in applications.

Authors:Christian Kanzow, Fabius Krämer, Patrick Mehlitz, Gerd Wachsmuth, Frank Werner

Abstract: In this paper, fully nonsmooth optimization problems in Banach spaces with finitely many inequality constraints, an equality constraint within a Hilbert space framework, and an additional abstract constraint are considered. First, we suggest a (safeguarded) augmented Lagrangian method for the numerical solution of such problems and provide a derivative-free global convergence theory which applies in situations where the appearing subproblems can be solved to approximate global minimality. Exemplary, the latter is possible in a fully convex setting. As we do not rely on any tool of generalized differentiation, the results are obtained under minimal continuity assumptions on the data functions. We then consider two prominent and difficult applications from image denoising and sparse optimal control where these findings can be applied in a beneficial way. These two applications are discussed and investigated in some detail. Due to the different nature of the two applications, their numerical solution by the (safeguarded) augmented Lagrangian approach requires problem-tailored techniques to compute approximate minima of the resulting subproblems. The corresponding methods are discussed, and numerical results visualize our theoretical findings.

Authors:Takeshi Suguro, Toshiaki Yachimura

Abstract: In this paper, we consider Tsallis entropic regularized optimal transport and discuss the convergence rate as the regularization parameter $\varepsilon$ goes to $0$. In particular, we establish the convergence rate of the Tsallis entropic regularized optimal transport using the quantization and shadow arguments developed by Eckstein--Nutz. We compare this to the convergence rate of the entropic regularized optimal transport with Kullback--Leibler (KL) divergence and show that KL is the fastest convergence rate in terms of Tsallis relative entropy.

Authors:Natalia Pavlasek, Sarah H. Q. Li, Behçet Açıkmeşe, Meeko Oishi, Claus Danielson

Abstract: In many safety-critical optimal control problems, users may request multiple safety constraints that are jointly infeasible due to external factors such as subsystem failures, unexpected disturbances, or fuel limitations. In this manuscript, we introduce the concept of blameless optimality to characterize control actions that a) satisfy the highest prioritized and feasible safety constraints and b) remain optimal with respect to a mission objective. For a general optimal control problem with jointly infeasible safety constraints, we prove that a single optimization problem cannot find a blamelessly optimal controller. Instead, finding blamelessly optimal control actions requires sequentially solving at least two optimal control problems: one to determine the highest priority level of constraints that is feasible and another to determine the optimal control action with respect to these constraints. We apply our results to a helicopter emergency landing scenario in which violating at least one safety-induced landing constraint is unavoidable. Leveraging the concept of blameless optimality, we formulate blamelessly optimal controllers that can autonomously prioritize human safety over property integrity.

Authors:Sally Giuseppe Arcidiacono, Salvatore Corrente, Salvatore Greco

Abstract: In multiple criteria decision aiding, very often the alternatives are compared by means of a value function compatible with the preferences expressed by the Decision Maker. The problem is that, in general, there is a plurality of compatible value functions, and providing a final recommendation on the problem at hand considering only one of them could be considered arbitrary to some extent. For such a reason, Stochastic Multicriteria Acceptability Analysis gives information in statistical terms by taking into account a sample of models compatible with the provided preferences. These statistics are given assuming the existence of a probability distribution in the space of value functions being defined a priori. In this paper, we propose some methods aiming to build a probability distribution on the space of value functions considering the preference information given by the Decision Maker. To prove the goodness of our proposal we performed an extensive set of simulations. Moreover, a sensitivity analysis on the variables of our procedure has been done as well.

Authors:Álvaro Samperio

Abstract: The problem of recovering the topology and parameters of an electrical network from power and voltage data at all nodes is a problem of fitting both an algebraic variety and a graph which is often ill-posed. In case there are multiple electrical networks which fit the data up to a given tolerance, we seek a solution in which the graph and therefore the algebraic equations associated with the electrical network are sparse, i.e. with few edges and terms. From an applied point of view, frequently it is difficult for system operators to know the precise information of the network. On the other hand, improvements on measurement devices increasingly provide more data about voltage and power, so it is useful to use this amount of data to estimate the network. We propose an algorithm for recovering simultaneously a sparse topology and the cable parameters of any network, combining in an iterative procedure the resolution of algebraic fitting convex problems and techniques of spectral graph sparsification. The algorithm is tested on several electrical networks.

Authors:Rolf van Lieshout, Thomas van der Schaft

Abstract: The solution of the Multi-Depot Vehicle Scheduling Problem (MDVSP) can often be improved substantially by incorporating Trip Shifting (TS) as a model feature. By allowing departure times to deviate a few minutes from the original timetable, new combinations of trips may be carried out by the same vehicle, thus leading to more efficient scheduling. However, explicit modeling of each potential trip shift quickly causes the problem to get prohibitively large for current solvers, such that researchers and practitioners were obligated to resort to heuristic methods to solve large instances. In this paper, we develop a Dynamic Discretization Discovery algorithm that guarantees an optimal continuous-time solution to the MDVSP-TS without explicit consideration of all trip shifts. It does so by iteratively solving and refining the problem on a partially time-expanded network until the solution can be converted to a feasible vehicle schedule on the fully time-expanded network. Computational results demonstrate that this algorithm outperforms the explicit modeling approach by a wide margin and is able to solve the MDVSP-TS even when many departure time deviations are considered.

Authors:Georgy Kostin, Alexander Gavrikov

Abstract: An optimal control problem for longitudinal motions of a thin elastic rod is considered. We suppose that a normal force, which changes piecewise constantly along the rod's length, is applied to the cross-section so that the positions of force jumps are equidistantly placed along the length. Additionally, external loads act at the rod ends. These distributed force and boundary loads are considered as control functions of the dynamic system. Given initial and terminal states at fixed time instants, the problem is to minimize the mean mechanical energy stored in the rod during its motion. We replace the classical wave equation with a variational problem solved via traveling waves defined on a special time-space mesh. For a uniform rod, the shortest admissible time horizon is estimated exactly, and the exact optimal control law is symbolically found in a recurrent way.

Authors:Filipa Valdeira, Cláudia Soares, João Gomes

Abstract: Localization is a fundamental enabler technology for many applications, like vehicular networks, IoT, and even medicine. While Global Navigation Satellite Systems solutions offer great performance, it is unavailable in scenarios like indoor or underwater environments, and, for large networks, the cost of instrumentation is prohibitive. We develop a localization algorithm from ranges and bearings, suitable for generic mobile networks of agents. Our algorithm is built on a tight convex relaxation of the Maximum Likelihood position estimator for a generic network. To serve positioning to mobile agents, a horizon-based version is developed accounting for velocity measurements at each agent. To solve the convex problem, a distributed gradient-based method is provided. This constitutes an advantage over other centralized approaches, which usually exhibit high latency for large networks and present a single point of failure. Additionally, the algorithm estimates all required parameters and effectively becomes parameter-free. Our solution to the dynamic network localization problem is theoretically well-founded and still easy to understand. We obtain a parameter-free, outlier-robust and trajectory-agnostic algorithm, with nearly constant positioning error regardless of the trajectories of agents and anchors, achieving better or comparable performance to state-of-the-art methods, as our simulations show. Furthermore, the method is distributed, convex and does not require any particular anchor configuration.

Authors:Dennis Gramlich, Tobias Holicki, Carsten W. Scherer, Christian Ebenbauer

Abstract: In this paper, we revisit structure exploiting SDP solvers dedicated to the solution of Kalman-Yakubovic-Popov semi-definite programs (KYP-SDPs). These SDPs inherit their name from the KYP Lemma and they play a crucial role in e.g. robustness analysis, robust state feedback synthesis, and robust estimator synthesis for uncertain dynamical systems. Off-the-shelve SDP solvers require $O(n^6)$ arithmetic operations per Newton step to solve this class of problems, where $n$ is the state dimension of the dynamical system under consideration. Specialized solvers reduce this complexity to $O(n^3)$. However, existing specialized solvers do not include semi-definite constraints on the Lyapunov matrix, which is necessary for controller synthesis. In this paper, we show how to include such constraints in structure exploiting KYP-SDP solvers.

Authors:Mohamed Hamdouche LPSM, Pierre Henry-Labordere LPSM, Huyên Pham LPSM

Abstract: We propose a novel generative model for time series based on Schr{\"o}dinger bridge (SB) approach. This consists in the entropic interpolation via optimal transport between a reference probability measure on path space and a target measure consistent with the joint data distribution of the time series. The solution is characterized by a stochastic differential equation on finite horizon with a path-dependent drift function, hence respecting the temporal dynamics of the time series distribution. We can estimate the drift function from data samples either by kernel regression methods or with LSTM neural networks, and the simulation of the SB diffusion yields new synthetic data samples of the time series. The performance of our generative model is evaluated through a series of numerical experiments. First, we test with a toy autoregressive model, a GARCH Model, and the example of fractional Brownian motion, and measure the accuracy of our algorithm with marginal and temporal dependencies metrics. Next, we use our SB generated synthetic samples for the application to deep hedging on real-data sets. Finally, we illustrate the SB approach for generating sequence of images.

Authors:Yulong Gao, Shuhao Yan, Jian Zhou, Mark Cannon, Alessandro Abate, Karl H. Johansson

Abstract: This paper is concerned with model predictive control (MPC) of discrete-time linear systems subject to bounded additive disturbance and hard constraints on the state and input, whereas the true disturbance set is unknown. Unlike most existing work on robust MPC, we propose an MPC algorithm incorporating online uncertainty quantification that builds on prior knowledge of the disturbance, i.e., a known but conservative disturbance set. We approximate the true disturbance set at each time step with a parameterised set, which is referred to as a quantified disturbance set, using the scenario approach with additional disturbance realisations collected online. A key novelty of this paper is that the parameterisation of these quantified disturbance sets enjoy desirable properties such that the quantified disturbance set and its corresponding rigid tube bounding disturbance propagation can be efficiently updated online. We provide statistical gaps between the true and quantified disturbance sets, based on which, probabilistic recursive feasibility of MPC optimisation problems are discussed. Numerical simulations are provided to demonstrate the efficacy of our proposed algorithm and compare with conventional robust MPC algorithms.

Authors:Qi Wang, Wenchuan Wu, Chenhui Lin, Xueliang Li

Abstract: Storage-concerned Alternative Current Optimal Power Flow (ACOPF) with complementarity constraints is highly non-convex and intractable. In this letter, we first derive two types of relaxation conditions, which guarantee no simultaneous charging and discharging (SCD) in the relaxed multi-period ACOPF. Moreover, we prove that the regions on LMPs formed by the proposed two conditions both contain the other four typical ones. We also generalize the application premise of sufficient conditions from the positive electricity price requirements to the negative electricity price scenarios. The case studies verify the exactness and advantages of the proposed method.

Authors:Lorenzo Dello Schiavo, Jan Maas, Francesco Pedrotti

Abstract: This paper deals with local criteria for the convergence to a global minimiser for gradient flow trajectories and their discretisations. To obtain quantitative estimates on the speed of convergence, we consider variations on the classical Kurdyka--{\L}ojasiewicz inequality for a large class of parameter functions. Our assumptions are given in terms of the initial data, without any reference to an equilibrium point. The main results are convergence statements for gradient flow curves and proximal point sequences to a global minimiser, together with sharp quantitative estimates on the speed of convergence. These convergence results apply in the general setting of lower semicontinuous functionals on complete metric spaces, generalising recent results for smooth functionals on $\mathbb{R}^n$. While the non-smooth setting covers very general spaces, it is also useful for (non)-smooth functionals on $\mathbb{R}^n$.

Authors:George Pantazis, Filiberto Fele, Kostas Margellos

Abstract: In this paper we focus on noncooperative games with uncertain constraints coupling the agents' decisions. We consider a setting where bounded deviations of agents' decisions from the equilibrium are possible, and uncertain constraints are inferred from data. Building upon recent advances in the so called scenario approach, we propose a randomised algorithm that returns a nominal equilibrium such that a pre-specified bound on the probability of violation for yet unseen constraints is satisfied for an entire region of admissible deviations surrounding it, thus supporting neighbourhoods of equilibria with probabilistic feasibility certificates. For the case in which the game admits a potential function, whose minimum coincides with the social welfare optimum of the population, the proposed algorithmic scheme opens the road to achieve a trade-off between the guaranteed feasibility levels of the region surrounding the nominal equilibrium, and its system-level efficiency. Detailed numerical simulations corroborate our theoretical results.

Authors:Kevin-Martin Aigner, Andreas Bärmann, Kristin Braun, Frauke Liers, Sebastian Pokutta, Oskar Schneider, Kartikey Sharma, Sebastian Tschuppik

Abstract: Stochastic Optimization (SO) is a classical approach for optimization under uncertainty that typically requires knowledge about the probability distribution of uncertain parameters. As the latter is often unknown, Distributionally Robust Optimization (DRO) provides a strong alternative that determines the best guaranteed solution over a set of distributions (ambiguity set). In this work, we present an approach for DRO over time that uses online learning and scenario observations arriving as a data stream to learn more about the uncertainty. Our robust solutions adapt over time and reduce the cost of protection with shrinking ambiguity. For various kinds of ambiguity sets, the robust solutions converge to the SO solution. Our algorithm achieves the optimization and learning goals without solving the DRO problem exactly at any step. We also provide a regret bound for the quality of the online strategy which converges at a rate of $\mathcal{O}(\log T / \sqrt{T})$, where $T$ is the number of iterations. Furthermore, we illustrate the effectiveness of our procedure by numerical experiments on mixed-integer optimization instances from popular benchmark libraries and give practical examples stemming from telecommunications and routing. Our algorithm is able to solve the DRO over time problem significantly faster than standard reformulations.

Authors:Takashi Tsuchiya, Bruno F. Lourenço, Masakazu Muramatsu, Takayuki Okuno

Abstract: Let $({\bf P},{\bf D})$ be a primal-dual pair of SDPs with a nonzero finite duality gap. Under such circumstances, ${\bf P}$ and ${\bf D}$ are weakly feasible and if we perturb the problem data to recover strong feasibility, the (common) optimal value function $v$ as a function of the perturbation is not well-defined at zero (unperturbed data) since there are ``two different optimal values'' $v({\bf P})$ and $v({\bf D})$, where $v({\bf P})$ and $v({\bf D})$ are the optimal values of ${\bf P}$ and ${\bf D}$ respectively. Thus, continuity of $v$ is lost at zero though $v$ is continuous elsewhere. Nevertheless, we show that a limiting version ${v_a}$ of $v$ is a well-defined monotone decreasing continuous bijective function connecting $v({\bf P})$ and $v({\bf D})$ with domain $[0, \pi/2]$ under the assumption that both ${\bf P}$ and ${\bf D}$ have singularity degree one. The domain $[0,\pi/2]$ corresponds to directions of perturbation defined in a certain manner. Thus, ${v_a}$ ``completely fills'' the nonzero duality gap under a mild regularity condition. Our result is tight in that there exists an instance with singularity degree two for which ${v_a}$ is not continuous.

Authors:Kareem T. Elgindy

Abstract: This paper introduces a new accurate model for periodic fractional optimal control problems (PFOCPs) using Riemann-Liouville (RL) and Caputo fractional derivatives (FDs) with sliding fixed memory lengths. The paper also provides a novel numerical method for solving PFOCPs using Fourier and Gegenbauer pseudospectral methods. By employing Fourier collocation at equally spaced nodes and Fourier and Gegenbauer quadratures, the method transforms the PFOCP into a simple constrained nonlinear programming problem (NLP) that can be treated easily using standard NLP solvers. We propose a new transformation that largely simplifies the problem of calculating the periodic FDs of periodic functions to the problem of evaluating the integral of the first derivatives of their trigonometric Lagrange interpolating polynomials, which can be treated accurately and efficiently using Gegenbauer quadratures. We introduce the notion of the {\alpha}th-order fractional integration matrix with index L based on Fourier and Gegenbauer pseudospectral approximations, which proves to be very effective in computing periodic FDs. We also provide a rigorous priori error analysis to predict the quality of the Fourier-Gegenbauer-based approximations to FDs. The numerical results of the benchmark PFOCP demonstrate the performance of the proposed pseudospectral method.

Authors:Woocheol Choi, Myeong-Su Lee, Seok-Bae Yun

Abstract: In this paper, we consider the online proximal mirror descent for solving the time-varying composite optimization problems. For various applications, the algorithm naturally involves the errors in the gradient and proximal operator. We obtain sharp estimates on the dynamic regret of the algorithm when the regular part of the cost is convex and smooth. If the Bregman distance is given by the Euclidean distance, our result also improves the previous work in two ways: (i) We establish a sharper regret bound compared to the previous work in the sense that our estimate does not involve $O(T)$ term appearing in that work. (ii) We also obtain the result when the domain is the whole space $\mathbb{R}^n$, whereas the previous work was obtained only for bounded domains. We also provide numerical tests for problems involving the errors in the gradient and proximal operator.

Authors:Digvijay Boob, Qi Deng

Abstract: The monotone Variational Inequality (VI) is an important problem in machine learning. In numerous instances, the VI problems are accompanied by function constraints which can possibly be data-driven, making the projection operator challenging to compute. In this paper, we present novel first-order methods for function constrained VI (FCVI) problem under various settings, including smooth or nonsmooth problems with a stochastic operator and/or stochastic constraints. First, we introduce the~{\texttt{OpConEx}} method and its stochastic variants, which employ extrapolation of the operator and constraint evaluations to update the variables and the Lagrangian multipliers. These methods achieve optimal operator or sample complexities when the FCVI problem is either (i) deterministic nonsmooth, or (ii) stochastic, including smooth or nonsmooth stochastic constraints. Notably, our algorithms are simple single-loop procedures and do not require the knowledge of Lagrange multipliers to attain these complexities. Second, to obtain the optimal operator complexity for smooth deterministic problems, we present a novel single-loop Adaptive Lagrangian Extrapolation~(\texttt{AdLagEx}) method that can adaptively search for and explicitly bound the Lagrange multipliers. Furthermore, we show that all of our algorithms can be easily extended to saddle point problems with coupled function constraints, hence achieving similar complexity results for the aforementioned cases. To our best knowledge, many of these complexities are obtained for the first time in the literature.

Authors:Bradley Jenks, Aly-Joy Ulusoy, Filippo Pecci, Ivan Stoianov

Abstract: This paper investigates the problem of integrating optimal pressure management and self-cleaning controls in dynamically adaptive water distribution networks. We review existing single-objective valve placement and control problems for minimizing average zone pressure (AZP) and maximizing self-cleaning capacity (SCC). Since AZP and SCC are conflicting objectives, we formulate a bi-objective design-for-control problem where locations and operational settings of pressure control and automatic flushing valves are jointly optimized. We approximate Pareto fronts using the weighted sum scalarization method, which uses a previously developed convex heuristic to solve the sequence of parametrized single-objective problems. The resulting Pareto fronts suggest that significant improvements in SCC can be achieved for minimal trade-offs in AZP performance. Moreover, we demonstrate that a hierarchical design strategy is capable of yielding good quality solutions to both objectives. This hierarchical design considers pressure control valves first placed for the primary AZP objective, followed by automatic flushing valves placed to augment SCC conditions. In addition, we investigate an adaptive control scheme for dynamically transitioning between AZP and SCC controls. We demonstrate these control challenges on case networks with both interconnected and branched topology.

Authors:Matieyendou Lamboni

Abstract: Mathematical models are sometime given as functions of independent input variables and equations or inequations connecting the input variables. A probabilistic characterization of such models results in treating them as functions with non-independent variables. Using the distribution function or copula of such variables that comply with such equations or inequations, we derive two types of partial derivatives of functions with non-independent variables (i.e., actual and dependent derivatives) and argue in favor of the latter. The dependent partial derivatives of functions with non-independent variables rely on the dependent Jacobian matrix of dependent variables, which is also used to define a tensor metric. The differential geometric framework allows for deriving the gradient, Hessian and Taylor-type expansion of functions with non-independent variables.

Authors:Rachel Grotheer, Shuang Li, Anna Ma, Deanna Needell, Jing Qin

Abstract: Due to the explosive growth of large-scale data sets, tensors have been a vital tool to analyze and process high-dimensional data. Different from the matrix case, tensor decomposition has been defined in various formats, which can be further used to define the best low-rank approximation of a tensor to significantly reduce the dimensionality for signal compression and recovery. In this paper, we consider the low-rank tensor completion problem. We propose a novel class of iterative singular tube hard thresholding algorithms for tensor completion based on the low-tubal-rank tensor approximation, including basic, accelerated deterministic and stochastic versions. Convergence guarantees are provided along with the special case when the measurements are linear. Numerical experiments on tensor compressive sensing and color image inpainting are conducted to demonstrate convergence and computational efficiency in practice.

Authors:Nicolai Jork

Abstract: We consider affine optimal control problems subject to semilinear elliptic PDEs. The results are two-fold; first, we continue the analysis of solution stability of control problems under perturbations appearing jointly in the objective functional and the PDE. For this, we consider a coercivity-type property that is common in the field of optimal control. The second result is concerned with the obtainment of error estimates for the numerical approximation for a finite element and a variational discretization scheme. The error estimates for the optimal controls and states are obtained under several conditions of different strengths that appeared recently in the context of solution stability. This includes an improvement of error estimates for the optimal controls and states under a H\"older-type growth condition.