Date: Wed, 8 May 2024 | Total: 12
In source localization problems, the aim is to locate the sources within a domain that causes given measurements on the boundary. In this type of problem, biasing of the solution is one of the main causes of mislocalization. A technique called standardization was developed to reduce biasing. However, the lack of a mathematical background for this method can cause difficulties in its application and confusion regarding the reliability of solutions. Here, we give a rigorous and generalized background for the technique using the Bayesian framework to shed light on the technique's abilities and limitations. In addition, we take a look at the noise robustness of the method that is widely reported in numerical studies. The paper starts by giving a gentle introduction to the problem and its bias and works its way toward standardization.
Data assimilation aims to estimate the states of a dynamical system by optimally combining sparse and noisy observations of the physical system with uncertain forecasts produced by a computational model. The states of many dynamical systems of interest obey nonlinear physical constraints, and the corresponding dynamics is confined to a certain sub-manifold of the state space. Standard data assimilation techniques applied to such systems yield posterior states lying outside the manifold, violating the physical constraints. This work focuses on particle flow filters which use stochastic differential equations to evolve state samples from a prior distribution to samples from an observation-informed posterior distribution. The variational Fokker-Planck (VFP) -- a generic particle flow filtering framework -- is extended to incorporate non-linear, equality state constraints in the analysis. To this end, two algorithmic approaches that modify the VFP stochastic differential equation are discussed: (i) VFPSTAB, to inexactly preserve constraints with the addition of a stabilizing drift term, and (ii) VFPDAE, to exactly preserve constraints by treating the VFP dynamics as a stochastic differential-algebraic equation (SDAE). Additionally, an implicit-explicit time integrator is developed to evolve the VFPDAE dynamics. The strength of the proposed approach for constraint preservation in data assimilation is demonstrated on three test problems: the double pendulum, Korteweg-de-Vries, and the incompressible Navier-Stokes equations.
The interaction between power systems and wildfires can be dangerous and costly. Damaged structures, load shedding, and high operational costs are potential consequences when the grid is unprepared. In fact, the operation of distribution grids can be liable for the outbreak of wildfires when extreme weather conditions arise. Within this context, investment planning should consider the impact of operational actions on the uncertainty related to wildfires that can directly affect line failure likelihood. Neglecting this can compromise the cost-benefit evaluation in planning system investments for wildfire risk. In this paper, we propose a decision-dependent uncertainty (DDU) aware methodology that provides the optimal portfolio of investments for distribution systems while considering that high power-flow levels through line segments in high-threat areas can ignite wildfires and, therefore, increase the probability of line failures. The methodology identifies the best combination of system upgrades (installation of new lines, hardening existing lines, and placement of switching devices) to provide the necessary leeway to operate the distribution system under wildfire-prone conditions. Our case study demonstrates that by modeling the DDU relationship between power flow prescriptions and line failures, investment decisions are more accurate and better prepare the grid infrastructure to deal with wildfire risk.
This book uses optimal control theory to prove that the most unpackable centrally symmetric convex disk in the plane is a smoothed polygon. A smoothed polygon is a polygon whose corners have been rounded in a special way by arcs of hyperbolas. To be highly unpackable means that even densest packing of that disk has low density. Motivated by Minkowski's geometry of numbers, researchers began to search for the most unpackable centrally symmetric convex disk (in brief, the most unpackable disk) starting in the early 1920s. In 1934, Reinhardt conjectured that the most unpackable disk is a smoothed octagon. Working independently of Reinhardt, Mahler attempted without success in 1947 to prove that the most unpackable disk must be a smoothed polygon. This book proves what Mahler set out to prove: Mahler's First conjecture on smoothed polygons. His second conjecture is identical to the Reinhardt conjecture, which remains open. This book explores the many remarkable structures of this packing problem, formulated as a problem in optimal control theory on a Lie group, with connections to hyperbolic geometry and Hamiltonian mechanics. Bang-bang Pontryagin extremals to the optimal control problem are smoothed polygons. Extreme difficulties arise in the proof because of chattering behavior in the optimal control problem, corresponding to possible smoothed polygons with infinitely many sides that need to be ruled out. To analyze and eliminate the possibility of chattering solutions, the book introduces a discrete dynamical system (the Poincare first recurrence map) and gives a full description of its fixed points, stable and unstable manifolds, and basin of attraction on a blowup centered at a singular set. Some proofs in this book are computer-assisted using a computer algebra system.
In this paper, we consider the recently introduced application of the Deck of Cards Method (DCM) to ordinal regression proposing an extension to Robust Ordinal Regression and Stochastic Multiattribute Acceptability Analysis. In Multiple Criteria Decision Aiding context, the proposed methodology permits to assign a value to each alternative evaluated on a set of criteria hierarchically structured. The Decision Maker can provide precise or imprecise information at different levels of the hierarchy of criteria using the classical DCM framework. This information is therefore used to infer a value function compatible with it. The compatible value function can be a simple weighted sum, a piecewise linear value function, a general monotonic value function, or a Choquet integral. To provide robust recommendations to the Decision Maker, we consider the Robust Ordinal Regression and the Stochastic Multicriteria Acceptability Analysis because, even if in different ways, both of them take into account the whole set of models compatible with the preference information provided by the Decision Maker. The applicability of the proposed methodology is shown by a didactic example in which Italian regions are evaluated on criteria representing Circular Economy, Innovation Driven Development and Smart Specialization Strategies.
We consider optimal control problems, where the control appears in the main part of the operator. We derive the Pontryagin maximum principle as a necessary optimality condition. The proof uses the concept of topological derivatives. In contrast to earlier works, we do not need continuity assumptions for the coefficient or gradients of solutions of partial differential equations. Following classical proofs, we consider perturbations of optimal controls by multiples of characteristic functions of sets, whose scaling factor is send to zero. For $2d$ problems, we can perform an optimization over the elliptic shapes of such sets leading to stronger optimality conditions involving a variational inequality of a new type.
In this paper we present an efficient active-set method for the solution of convex quadratic programming problems with general piecewise-linear terms in the objective, with applications to sparse approximations and risk-minimization. The algorithm is derived by combining a proximal method of multipliers (PMM) with a standard semismooth Newton method (SSN), and is shown to be globally convergent under minimal assumptions. Further local linear (and potentially superlinear) convergence is shown under standard additional conditions. The major computational bottleneck of the proposed approach arises from the solution of the associated SSN linear systems. These are solved using a Krylov-subspace method, accelerated by certain novel general-purpose preconditioners which are shown to be optimal with respect to the proximal penalty parameters. The preconditioners are easy to store and invert, since they exploit the structure of the nonsmooth terms appearing in the problem's objective to significantly reduce their memory requirements. We showcase the efficiency, robustness, and scalability of the proposed solver on a variety of problems arising in risk-averse portfolio selection, $L^1$-regularized partial differential equation constrained optimization, quantile regression, and binary classification via linear support vector machines. We provide computational evidence, on real-world datasets, to demonstrate the ability of the solver to efficiently and competitively handle a diverse set of medium- and large-scale optimization instances.
We introduce the class of subdifferentially polynomially bounded (SPB) functions, which is a rich class of locally Lipschitz functions that encompasses all Lipschitz functions, all gradient- or Hessian-Lipschitz functions, and even some non-smooth locally Lipschitz functions. We show that SPB functions are compatible with Gaussian smoothing (GS), in the sense that the GS of any SPB function is well-defined and satisfies a descent lemma akin to gradient-Lipschitz functions, with the Lipschitz constant replaced by a polynomial function. Leveraging this descent lemma, we propose GS-based zeroth-order optimization algorithms with an adaptive stepsize strategy for constrained minimization of SPB functions, and analyze their iteration complexity. An important instrument in our analysis, which could be of independent interest, is the quantification of Goldstein stationarity via the GS gradient.
We study generalized Nash equilibrium problems (GNEPs) such that objectives are polynomial functions, and each player's constraints are linear in their own strategy. For such GNEPs, the KKT sets can be represented as unions of simpler sets by Carath\'{e}odory's theorem. We give a convenient representation for KKT sets using partial Lagrange multiplier expressions. This produces a set of branch polynomial optimization problems, which can be efficiently solved by Moment-SOS relaxations. By doing this, we can compute all generalized Nash equilibria or detect their nonexistence. Numerical experiments are also provided to demonstrate the computational efficiency.
In this paper, we build a framework that facilitates the analysis of discounted infinite horizon Markov Decision Processes (MDPs) by visualizing them as deterministic processes where the states are probability measures on the original state space and the actions are stochastic kernels on the original action space. We provide a simple general algebraic approach to lifting any MDP to this space of measures; we call this to measurize the original stochastic MDP. We show that measurized MDPs are in fact a generalization of stochastic MDPs, thus the measurized framework can be deployed without loss of fidelity. Lifting an MDP can be convenient because the measurized framework enables constraints and value function approximations that are not easily available from the standard MDP setting. For instance, one can add restrictions or build approximations based on moments, quantiles, risk measures, etc. Moreover, since the measurized counterpart to any MDP is deterministic, the measurized optimality equations trade the complexity of dealing with the expected value function that appears in the stochastic optimality equations with a more complex state space.
Temporal difference (TD) learning algorithms with neural network function parameterization have well-established empirical success in many practical large-scale reinforcement learning tasks. However, theoretical understanding of these algorithms remains challenging due to the nonlinearity of the action-value approximation. In this paper, we develop an improved non-asymptotic analysis of the neural TD method with a general $L$-layer neural network. New proof techniques are developed and an improved new $\tilde{\mathcal{O}}(\epsilon^{-1})$ sample complexity is derived. To our best knowledge, this is the first finite-time analysis of neural TD that achieves an $\tilde{\mathcal{O}}(\epsilon^{-1})$ complexity under the Markovian sampling, as opposed to the best known $\tilde{\mathcal{O}}(\epsilon^{-2})$ complexity in the existing literature.
Model-based methods play a key role in the reconstruction of compressed sensing (CS) MRI. Finding an effective prior to describe the statistical distribution of the image family of interest is crucial for model-based methods. Plug-and-play (PnP) is a general framework that uses denoising algorithms as the prior or regularizer. Recent work showed that PnP methods with denoisers based on pretrained convolutional neural networks outperform other classical regularizers in CS MRI reconstruction. However, the numerical solvers for PnP can be slow for CS MRI reconstruction. This paper proposes a preconditioned PnP (P^2nP) method to accelerate the convergence speed. Moreover, we provide proofs of the fixed-point convergence of the P^2nP iterates. Numerical experiments on CS MRI reconstruction with non-Cartesian sampling trajectories illustrate the effectiveness and efficiency of the P^2nP approach.