Optimization and Control
See recent articles
- [1] arXiv:2407.11088 [pdf, other]
-
Title: Variability in Modeling the Cyclic Scheduling of an FMC Depending on the Underlying TSP ModelsSubjects: Optimization and Control (math.OC)
Flexible robotic cells are utilized to produce standardized products at a high speed production rate, and to set up the production floors based on rapid operating environment changes. In FRC, there are a number of computer numerical control machines, an input buffer, an output buffer, and a robot. The input and output buffers contain unprocessed and finished products, respectively, whereas the robot performs the loading and unloading activities and transports the items among buffers and machines. The system repeats a cyclic schedule in its run and the cycle time depends on the order of robot activities. In order to maximize the efficiency of the system, the order of the robot activities yielding the minimum cycle time should be determined. The aim of this research is to find novel exact models to solve this cycling scheduling problem. These types of problems have tight relations with traveling salesman problem. In this study, four main modeling approaches of the TSP, such as Dantzig-Fulkerson-Johnson approach, Miller-Tucker-Zemlin approach, Vajda's n-step approach, and the network flow approach are studied. Only the DFJ approach cannot be adapted to the scheduling problem. The three other approaches are adapted successfully. Similarities and differences are discussed by using several numerical examples.
- [2] arXiv:2407.11099 [pdf, html, other]
-
Title: CFD-based Shape Optimization of Structured Packings for Enhancing Separation Efficiency in DistillationSebastian Blauth, Dennis Stucke, Mohamed Adel Ashour, Johannes Schnebele, Thomas Grützner, Christian LeithäuserSubjects: Optimization and Control (math.OC)
Free-form shape optimization techniques are investigated to improve the separation efficiency of structured packings in laboratory-scale distillation columns. A simplified simulation model based on computational fluid dynamics (CFD) for the mass transfer in the distillation column is used and a corresponding shape optimization problem is formulated. The goal of the optimization is to increase the mass transfer in the column by changing the packing's shape, which has been previously used as criterion for increasing the separation efficiency of the column. The computational shape optimization yields promising results, with an increased mass transfer of nearly 20 %. For validation, the resulting optimized shape is additively manufactured using 3D-printing and investigated experimentally. The experimental results are in good agreement with the performance improvement predicted by the computational model, yielding an increase in separation efficiency of around 20 %.
- [3] arXiv:2407.11209 [pdf, html, other]
-
Title: Optimal Control of State-Triggered Linear Hybrid SystemsComments: 12 pages, 9 figuresSubjects: Optimization and Control (math.OC); Systems and Control (eess.SY)
The linear quadratic regulator is a famous application of optimal control theory. This class of control systems has linear dynamics (in both the state and control), while minimizing a quadratic cost. Upon application of Pontryagin's maximum principle, the co-states can be fully decoupled from the state which results in a matrix Riccati equation. As such, solutions can be found by solving this matrix equation backwards. The purpose of this work is to extend this analysis to systems with linear state jumps, which are referred to as linear hybrid systems. The extension of the maximum principle to these systems results in the ``hybrid maximum principle.'' However, successful application of this theory requires many subtle properties which are usually ignored - specifically beating/blocking and Zeno. It turns out that these phenomena occur in linear hybrid systems and as such, the hybrid maximum principle is not immediately applicable to these seemingly simple systems. We show that for spatially triggered linear hybrid systems, beating always occurs while blocking and Zeno can be successfully avoided if a certain controllability assumption is satisfied. For these trivially blocking systems, we develop conditions for optimality for the two cases of when beating is excluded and present. This work concluded with an example.
- [4] arXiv:2407.11413 [pdf, html, other]
-
Title: Distributed Prescribed-Time Convex Optimization: Cascade Design and Time-Varying Gain ApproachSubjects: Optimization and Control (math.OC); Systems and Control (eess.SY)
In this paper, we address the distributed prescribed-time convex optimization (DPTCO) problem for a class of nonlinear multi-agent systems (MASs) under undirected connected graph. A cascade design framework is proposed such that the DPTCO implementation is divided into two parts: distributed optimal trajectory generator design and local reference trajectory tracking controller design. The DPTCO problem is then transformed into the prescribed-time stabilization problem of a cascaded system. Changing Lyapunov function method and time-varying state transformation method together with the sufficient conditions are proposed to prove the prescribed-time stabilization of the cascaded system as well as the uniform boundedness of internal signals in the closed-loop systems. The proposed framework is then utilized to solve robust DPTCO problem for a class of chain-integrator MASs with external disturbances by constructing a novel variables and exploiting the property of time-varying gains. The proposed framework is further utilized to solve the adaptive DPTCO problem for a class of strict-feedback MASs with parameter uncertainty, in which backstepping method with prescribed-time dynamic filter is adopted. The descending power state transformation is introduced to compensate the growth of increasing rate induced by the derivative of time-varying gains in recursive steps and the high-order derivative of local reference trajectory is not required. Finally, theoretical results are verified by two numerical examples.
- [5] arXiv:2407.11457 [pdf, html, other]
-
Title: Decision-Based vs. Distribution-Driven Clustering for Stochastic Energy System Design OptimizationComments: 6 pages, 3 figures, submitted to Annual International Conference of the German Operations Research Society (GOR) 2024Subjects: Optimization and Control (math.OC)
Stochastic programming is widely used for energy system design optimization under uncertainty but can exponentially increase the computational complexity with the number of scenarios. Common scenario reduction techniques, like moments-matching or distribution-driven clustering, pre-select representative scenarios based on input parameters. In contrast, decision-based clustering groups scenarios by similarity in resulting model decisions. Decision-based clustering has shown potential in network design and fleet planning. However, its potential in energy system design remains unexplored.
In our work, we examine the effectiveness of decision-based clustering in energy system design using a four-step method: 1) Determine the optimal design for each scenario; 2) Aggregate and normalize installed capacities as features reflecting optimal decisions; 3) Use these features for k-medoids clustering to identify representative scenarios; 4) Utilize these scenarios to optimize cost in stochastic programming.
We apply our method to a real-world industrial energy system modeled as a mixed-integer linear program. We incorporate uncertainty by scaling time series with representative factors. We generate 500 single-year scenarios via Monte Carlo sampling, which we reduce using decision-based clustering. For benchmarking, we conduct distribution-driven k-medoids clustering based on the representative factors. In our case studies, both clustering methods yield designs with similar cost efficiency, although decision-based clustering requires substantially more computational resources. To our knowledge, this is the first application of decision-based clustering on energy system design optimization. Future research should investigate the conditions under which decision-based clustering yields more cost-efficient designs compared to distribution-driven clustering. - [6] arXiv:2407.11530 [pdf, html, other]
-
Title: Output-based receding horizon stabilizing controlComments: 9 figures, 22 subfiguresSubjects: Optimization and Control (math.OC)
A receding horizon control framework is coupled with a Luenberger observer to construct an output-based control input stabilizing parabolic equations. The actuators and sensors are indicator functions of small subdomains, representing localized actuation and localized measurements. It is shown that, for a class of explicitly given sets of actuators and sensors, we can guarantee the stabilizing property of the constructed input. Results of numerical simulations are presented validating the theoretical findings.
- [7] arXiv:2407.11618 [pdf, html, other]
-
Title: Decarbonization of Existing Heating Networks through Optimal Producer Retrofit and Low-Temperature OperationSubjects: Optimization and Control (math.OC)
District heating networks are considered a key factor for enabling emission-free heat supply, while many existing networks still heavily rely on fossil fuels. With district heating network pipes easily exceeding a lifetime of 30 years, there is a growing potential to retrofit the heat producers of existing networks to enable low-emission heat supply. Today, the heat producer retrofit for district heating networks usually focuses on simplified approaches, where the non-linear nature of the design problem is relaxed or not considered at all. Some approaches take non-linearities into account but use optimization routines that are either not scalable to large problems or are not reliable in obtaining an optimal solution, such as parameter optimization and sensitivity studies. This paper presents an automated design approach, to decarbonize existing heating networks through optimal producer retrofit and ultimately enabling 4th generation operation. The approach uses multi-objective, mathematical optimization to balance CO2 emissions and network costs, by assessing different CO2 prices, and is based on a detailed physical model. The optimizer is given the freedom to choose the producer types, their capacities, and for each period, their supplied heat and supply temperature. A non-linear heat transport model accurately accounts for heat and momentum losses throughout the network, and ensures the feasibility of the proposed design and operation. The multi-period formulation incorporates temporal changes in heat demand and environmental conditions throughout the year. By formulating a continuous problem and using adjoint-based optimization, the automated approach remains scalable towards large scale applications. The design approach was assessed on a medium-sized 3rd generation DHN case and was able to optimally retrofit the heat producers.
- [8] arXiv:2407.11628 [pdf, html, other]
-
Title: Block triangular preconditioning for elliptic boundary optimal control with mixed boundary conditionsSubjects: Optimization and Control (math.OC); Numerical Analysis (math.NA)
In this paper, preconditioning the saddle point problem arising from the elliptic boundary optimal control problem with mixed boundary conditions is considered. A block triangular reconditioning method is proposed based on permutations of the saddle point problem and approximations of the corresponding Schur complement. The spectral properties of the preconditioned matrix is analyzed. Numerical experiments are conducted to demonstrate the effectiveness of the proposed preconditioning method.
- [9] arXiv:2407.11703 [pdf, html, other]
-
Title: Numerical Eigenvalue Optimization by Shape-Variations for Maxwell's Eigenvalue ProblemSubjects: Optimization and Control (math.OC); Numerical Analysis (math.NA)
In this paper we consider the free-form optimization of eigenvalues in electromagnetic systems by means of shape-variations with respect to small deformations. The objective is to optimize a particular eigenvalue to a target value. We introduce the mixed variational formulation of the Maxwell eigenvalue problem introduced by Kikuchi (1987) in function spaces of (H(\operatorname{curl}; \Omega)) and (H^1(\Omega)). To handle this formulation, suitable transformations of these spaces are utilized, e.g., of Piola-type for the space of (H(\operatorname{curl}; \Omega)). This allows for a formulation of the problem on a fixed reference domain together with a domain mapping. Local uniqueness of the solution is obtained by a normalization of the the eigenfunctions. This allows us to derive adjoint formulas for the derivatives of the eigenvalues with respect to domain variations. For the solution of the resulting optimization problem, we develop a particular damped inverse BFGS method that allows for an easy line search procedure while retaining positive definiteness of the inverse Hessian approximation. The infinite dimensional problem is discretized by mixed finite elements and a numerical example shows the efficiency of the proposed approach.
- [10] arXiv:2407.11713 [pdf, other]
-
Title: AutoFreeFem: Automatic code generation with FreeFEM++ and LaTex output for shape and topology optimization of non-linear multi-physics problemsSubjects: Optimization and Control (math.OC)
For an educational purpose we develop the Python package AutoFreeFem which generates all ingredients for shape optimization with non-linear multi-physics in FreeFEM++ and also outputs the expressions for use in LaTex. As an input, the objective function and the weak form of the problem have to be specified only once. This ensures consistency between the simulation code and its documentation. In particular, AutoFreeFem provides the linearization of the state equation, the adjoint problem, the shape derivative, as well as a basic implementation of the level-set based mesh evolution method for shape optimization. For the computation of shape derivatives we utilize the mathematical Lagrangian approach for differentiating PDE-constrained shape functions. Differentiation is done symbolically using Sympy. In numerical experiments we verify the accuracy of the computed derivatives. Finally, we showcase the capabilities of AutoFreeFem by considering shape optimization of a non-linear diffusion problem, linear and non-linear elasticity problems, a thermo-elasticity problem and a fluid-structure interaction problem.
- [11] arXiv:2407.11739 [pdf, html, other]
-
Title: A Strengthened Conjecture on the Minimax Optimal Constant Stepsize for Gradient DescentSubjects: Optimization and Control (math.OC)
Drori and Teboulle [4] conjectured that the minimax optimal constant stepsize for N steps of gradient descent is given by the stepsize that balances performance on Huber and quadratic objective functions. This was numerically supported by semidefinite program (SDP) solves of the associated performance estimation problems up to $N\approx 100$. This note presents a strengthened version of the initial conjecture. Specifically, we conjecture the existence of a certificate for the convergence rate with a very specific low-rank structure. This structure allows us to bypass SDPs and to numerically verify both conjectures up to $N = 20160$.
- [12] arXiv:2407.11760 [pdf, html, other]
-
Title: The Pivoting Framework: Frank-Wolfe Algorithms with Active Set Size ControlSubjects: Optimization and Control (math.OC)
We propose the pivoting meta algorithm (PM), a framework designed to enhance optimization algorithms that generate iterates as convex combinations of vertices of a feasible region $\mathcal{C}\subseteq \mathbb{R}^n$, including several variants of the Frank-Wolfe algorithm (FW). PM guarantees that the active set of the modified algorithm remains as small as guaranteed by Carathéodory's theorem. PM achieves this by reformulating the active set expansion task into an equivalent linear programming problem, which can be efficiently solved using a single pivot step akin to the primal simplex algorithm. We establish that PM bounds the cardinality of the active set by the dimension of $\mathcal{C}$ plus one, while preserving the convergence rate guarantees of a class of original algorithms, including various variants of the Frank-Wolfe algorithm. Furthermore, we establish the connection between PM and active set identification. Specifically, when $\mathcal{C}$ is a polytope and under mild assumptions, PM applied to the away-step Frank-Wolfe algorithm (AFW) or the blended pairwise Frank-Wolfe algorithm (BPFW) ensures that the active set size is at most the dimension of the optimal face plus one. To illustrate the practicality of PM, we provide algorithmic implementations for standard Frank-Wolfe variants and conduct a comprehensive numerical evaluation, demonstrating its effectiveness in inducing sparsity.
- [13] arXiv:2407.11817 [pdf, html, other]
-
Title: A gradient flow on control space with rough initial conditionSubjects: Optimization and Control (math.OC); Probability (math.PR)
We consider the (sub-Riemannian type) control problem of finding a path going from an initial point $x$ to a target point $y$, by only moving in certain admissible directions. We assume that the corresponding vector fields satisfy the bracket-generating (Hörmander) condition, so that the classical Chow-Rashevskii theorem guarantees the existence of such a path. One natural way to try to solve this problem is via a gradient flow on control space. However, since the corresponding dynamics may have saddle points, any convergence result must rely on suitable (e.g. random) initialisation. We consider the case when this initialisation is irregular, which is conveniently formulated via Lyons' rough path theory. We show that one advantage of this initialisation is that the saddle points are moved to infinity, while minima remain at a finite distance from the starting point. In the step $2$-nilpotent case, we further manage to prove that the gradient flow converges to a solution, if the initial condition is the path of a Brownian motion (or rougher). The proof is based on combining ideas from Malliavin calculus with Łojasiewicz inequalities. A possible motivation for our study comes from the training of deep Residual Neural Nets, in the regime when the number of trainable parameters per layer is smaller than the dimension of the data vector.
- [14] arXiv:2407.11825 [pdf, html, other]
-
Title: Optimization under rare events: scaling laws for linear chance-constrained programsComments: 17 pagesSubjects: Optimization and Control (math.OC); Probability (math.PR)
We consider a class of chance-constrained programs in which profit needs to be maximized while enforcing that a given adverse event remains rare. Using techniques from large deviations and extreme-value theory, we show how the optimal value scales as the prescribed bound on the violation probability becomes small and how convex programs emerge in the limit. We also use our results to show that the popular CVaR approximation is asymptotically optimal under light-tail assumptions, but it is sub-optimal in a heavy-tailed setting. Then, we apply point process techniques and random set theory to study the suboptimality gap in the Monte Carlo based scenario approach.
New submissions for Wednesday, 17 July 2024 (showing 14 of 14 entries )
- [15] arXiv:2407.11035 (cross-list from stat.ME) [pdf, html, other]
-
Title: Optimal estimators of cross-partial derivatives and surrogates of functionsSubjects: Methodology (stat.ME); Optimization and Control (math.OC); Probability (math.PR); Statistics Theory (math.ST); Computation (stat.CO); Machine Learning (stat.ML)
Computing cross-partial derivatives using fewer model runs is relevant in modeling, such as stochastic approximation, derivative-based ANOVA, exploring complex models, and active subspaces. This paper introduces surrogates of all the cross-partial derivatives of functions by evaluating such functions at $N$ randomized points and using a set of $L$ constraints. Randomized points rely on independent, central, and symmetric variables. The associated estimators, based on $NL$ model runs, reach the optimal rates of convergence (i.e., $\mathcal{O}(N^{-1})$), and the biases of our approximations do not suffer from the curse of dimensionality for a wide class of functions. Such results are used for i) computing the main and upper-bounds of sensitivity indices, and ii) deriving emulators of simulators or surrogates of functions thanks to the derivative-based ANOVA. Simulations are presented to show the accuracy of our emulators and estimators of sensitivity indices. The plug-in estimates of indices using the U-statistics of one sample are numerically much stable.
- [16] arXiv:2407.11471 (cross-list from cs.LG) [pdf, html, other]
-
Title: Safe Online Convex Optimization with Multi-Point FeedbackComments: 20 pages, 1 figure. Published in the proceedings of the Learning for Dynamics and Control Conference (L4DC) 2024Subjects: Machine Learning (cs.LG); Optimization and Control (math.OC)
Motivated by the stringent safety requirements that are often present in real-world applications, we study a safe online convex optimization setting where the player needs to simultaneously achieve sublinear regret and zero constraint violation while only using zero-order information. In particular, we consider a multi-point feedback setting, where the player chooses $d + 1$ points in each round (where $d$ is the problem dimension) and then receives the value of the constraint function and cost function at each of these points. To address this problem, we propose an algorithm that leverages forward-difference gradient estimation as well as optimistic and pessimistic action sets to achieve $\mathcal{O}(d \sqrt{T})$ regret and zero constraint violation under the assumption that the constraint function is smooth and strongly convex. We then perform a numerical study to investigate the impacts of the unknown constraint and zero-order feedback on empirical performance.
- [17] arXiv:2407.11533 (cross-list from cs.CG) [pdf, html, other]
-
Title: Transforming the Challenge of Constructing Low-Discrepancy Point Sets into a Permutation Selection ProblemSubjects: Computational Geometry (cs.CG); Optimization and Control (math.OC)
Low discrepancy point sets have been widely used as a tool to approximate continuous objects by discrete ones in numerical processes, for example in numerical integration. Following a century of research on the topic, it is still unclear how low the discrepancy of point sets can go; in other words, how regularly distributed can points be in a given space. Recent insights using optimization and machine learning techniques have led to substantial improvements in the construction of low-discrepancy point sets, resulting in configurations of much lower discrepancy values than previously known. Building on the optimal constructions, we present a simple way to obtain $L_{\infty}$-optimized placement of points that follow the same relative order as an (arbitrary) input set. Applying this approach to point sets in dimensions 2 and 3 for up to 400 and 50 points, respectively, we obtain point sets whose $L_{\infty}$ star discrepancies are up to 25% smaller than those of the current-best sets, and around 50% better than classical constructions such as the Fibonacci set.
- [18] arXiv:2407.11571 (cross-list from cs.LG) [pdf, html, other]
-
Title: Federated Learning Forecasting for Strengthening Grid Reliability and Enabling Markets for ResilienceComments: Submitted to CIRED 2024 USA: Workshop on Resilience of Electric Distribution SystemsSubjects: Machine Learning (cs.LG); Systems and Control (eess.SY); Optimization and Control (math.OC)
We propose a comprehensive approach to increase the reliability and resilience of future power grids rich in distributed energy resources. Our distributed scheme combines federated learning-based attack detection with a local electricity market-based attack mitigation method. We validate the scheme by applying it to a real-world distribution grid rich in solar PV. Simulation results demonstrate that the approach is feasible and can successfully mitigate the grid impacts of cyber-physical attacks.
- [19] arXiv:2407.11649 (cross-list from math.AP) [pdf, html, other]
-
Title: Continuous time Markov chain based approximation of stationary and weak KAM Hamilton-Jacobi equationsComments: 36 pagesSubjects: Analysis of PDEs (math.AP); Optimization and Control (math.OC)
Main objects of the paper are stationary and weak KAM Hamilton-Jacobi equations on the finite-dimensional torus. The key idea of the paper is to replace the underlying calculus of variations problems with continuous time Markov decision problems. This directly leads to an approximation of the stationary Hamilton-Jacobi equation by the Bellman equation for a discounting Markov decision problem. Developing elements of the weak KAM theory for the Markov decision problem, we obtain an approximation of the effective Hamiltonian. Additionally, convergences of the functional parts of the discrete weak KAM equations and Mather measures are shown. It turns out that the approximating equations are systems of algebraic equations. Thus, the paper's result can be seen as numerical schemes for stationary and weak KAM Hamilton-Jacobi equations.
- [20] arXiv:2407.11752 (cross-list from cs.DS) [pdf, html, other]
-
Title: IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard RatesComments: 54 pages, 2 figuresSubjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Optimization and Control (math.OC); Probability (math.PR)
Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given distribution. Upon observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations.
This model has been studied with infinite, finite and unknown number of values. When the gambler faces a random number of values, the model is said to have random horizon. We consider the model in which the gambler is given a priori knowledge of the horizon's distribution. Alijani et al. (2020) designed a single-threshold algorithms achieving a ratio of $1/2$ when the random horizon has an increasing hazard rate and is independent of the values. We prove that with a single-threshold, a ratio of $1/2$ is actually achievable for several larger classes of horizon distributions, with the largest being known as the $\mathcal{G}$ class in reliability theory. Moreover, we extend this result to its dual, the $\overline{\mathcal{G}}$ class (which includes the decreasing hazard rate class), and to low-variance horizons. Finally, we construct the first example of a family of horizons, for which multiple thresholds are necessary to achieve a nonzero ratio. We establish that the Secretary Problem optimal stopping rule provides one such algorithm, paving the way towards the study of the model beyond single-threshold algorithms. - [21] arXiv:2407.11800 (cross-list from math.AP) [pdf, other]
-
Title: Gradient Flows and Riemannian Structure in the Gromov-Wasserstein GeometryComments: 73 pagesSubjects: Analysis of PDEs (math.AP); Optimization and Control (math.OC); Machine Learning (stat.ML)
The Wasserstein space of probability measures is known for its intricate Riemannian structure, which underpins the Wasserstein geometry and enables gradient flow algorithms. However, the Wasserstein geometry may not be suitable for certain tasks or data modalities. Motivated by scenarios where the global structure of the data needs to be preserved, this work initiates the study of gradient flows and Riemannian structure in the Gromov-Wasserstein (GW) geometry, which is particularly suited for such purposes. We focus on the inner product GW (IGW) distance between distributions on $\mathbb{R}^d$. Given a functional $\mathsf{F}:\mathcal{P}_2(\mathbb{R}^d)\to\mathbb{R}$ to optimize, we present an implicit IGW minimizing movement scheme that generates a sequence of distributions $\{\rho_i\}_{i=0}^n$, which are close in IGW and aligned in the 2-Wasserstein sense. Taking the time step to zero, we prove that the discrete solution converges to an IGW generalized minimizing movement (GMM) $(\rho_t)_t$ that follows the continuity equation with a velocity field $v_t\in L^2(\rho_t;\mathbb{R}^d)$, specified by a global transformation of the Wasserstein gradient of $\mathsf{F}$. The transformation is given by a mobility operator that modifies the Wasserstein gradient to encode not only local information, but also global structure. Our gradient flow analysis leads us to identify the Riemannian structure that gives rise to the intrinsic IGW geometry, using which we establish a Benamou-Brenier-like formula for IGW. We conclude with a formal derivation, akin to the Otto calculus, of the IGW gradient as the inverse mobility acting on the Wasserstein gradient. Numerical experiments validating our theory and demonstrating the global nature of IGW interpolations are provided.
- [22] arXiv:2407.11823 (cross-list from cs.LG) [pdf, html, other]
-
Title: Harmonizing Safety and Speed: A Human-Algorithm Approach to Enhance the FDA's Medical Device Clearance PolicySubjects: Machine Learning (cs.LG); Human-Computer Interaction (cs.HC); Optimization and Control (math.OC); Machine Learning (stat.ML)
The United States Food and Drug Administration's (FDA's) Premarket Notification 510(K) pathway allows manufacturers to gain approval for a medical device by demonstrating its substantial equivalence to another legally marketed device. However, the inherent ambiguity of this regulatory procedure has led to high recall rates for many devices cleared through this pathway. This trend has raised significant concerns regarding the efficacy of the FDA's current approach, prompting a reassessment of the 510(K) regulatory framework. In this paper, we develop a combined human-algorithm approach to assist the FDA in improving its 510(k) medical device clearance process by reducing the risk of potential recalls and the workload imposed on the FDA. We first develop machine learning methods to estimate the risk of recall of 510(k) medical devices based on the information available at the time of submission. We then propose a data-driven clearance policy that recommends acceptance, rejection, or deferral to FDA's committees for in-depth evaluation. We conduct an empirical study using a unique large-scale dataset of over 31,000 medical devices and 12,000 national and international manufacturers from over 65 countries that we assembled based on data sources from the FDA and Centers for Medicare and Medicaid Service (CMS). A conservative evaluation of our proposed policy based on this data shows a 38.9% improvement in the recall rate and a 43.0% reduction in the FDA's workload. Our analyses also indicate that implementing our policy could result in significant annual cost-savings ranging between \$2.4 billion and \$2.7 billion, which highlights the value of using a holistic and data-driven approach to improve the FDA's current 510(K) medical device evaluation pathway.
- [23] arXiv:2407.11951 (cross-list from math.AP) [pdf, html, other]
-
Title: Growth estimates on optimal transport maps via concentration inequalitiesSubjects: Analysis of PDEs (math.AP); Functional Analysis (math.FA); Optimization and Control (math.OC); Probability (math.PR)
We give an alternative proof and some extensions of results of Carlier, Figalli and Santambrogio on polynomial upper bounds on the Brenier map between probability measures under various conditions on the densities. The proofs are based on the monotonicity of the map and various concentration inequalities, as already used by Colombo and Fathi to prove quadratic growth for transport maps from the standard Gaussian onto log-concave measures.
Cross submissions for Wednesday, 17 July 2024 (showing 9 of 9 entries )
- [24] arXiv:1805.06444 (replaced) [pdf, html, other]
-
Title: A geometric integration approach to smooth optimisation: Foundations of the discrete gradient methodMatthias J. Ehrhardt (1), Erlend S. Riis (2), Torbjørn Ringholm (3), Carola-Bibiane Schönlieb (2) ((1) Institute for Mathematical Innovation, University of Bath, UK, (2) Department of Applied Mathematics and Theoretical Physics, University of Cambridge, UK, (3) Department of Mathematical Sciences, Norwegian University of Science and Technology, Norway)Journal-ref: IMA Journal of Numerical Analysis (2024), drae037Subjects: Optimization and Control (math.OC)
Discrete gradient methods are geometric integration techniques that can preserve the dissipative structure of gradient flows. Due to the monotonic decay of the function values, they are well suited for general convex and nonconvex optimisation problems. Both zero- and first-order algorithms can be derived from the discrete gradient method by selecting different discrete gradients. In this paper, we present a thorough analysis of the discrete gradient method for optimisation which provides a solid theoretical foundation. We show that the discrete gradient method is well-posed by proving the existence of iterates for any positive time step, as well as uniqueness in some cases, and propose an efficient method for solving the associated discrete gradient equation. Moreover, we establish an $O(1/k)$ convergence rate for convex objectives and prove linear convergence if instead the Polyak-Lojasiewicz inequality is satisfied. The analysis is carried out for three discrete gradients-the Gonzalez discrete gradient, the mean value discrete gradient, and the Itoh-Abe discrete gradient, as well as for a randomised Itoh-Abe method. Our theoretical results are illustrated with a variety of numerical experiments, and we furthermore demonstrate that the methods are robust with respect to stiffness.
- [25] arXiv:1808.01962 (replaced) [pdf, html, other]
-
Title: Semi-discrete unbalanced optimal transport and quantizationSubjects: Optimization and Control (math.OC)
In this paper we study the class of optimal entropy-transport problems introduced by Liero, Mielke and Savaré in Inventiones Mathematicae 211 in 2018. This class of unbalanced transport metrics allows for transport between measures of different total mass, unlike classical optimal transport where both measures must have the same total mass. In particular, we develop the theory for the important subclass of semi-discrete unbalanced transport problems, where one of the measures is diffuse (absolutely continuous with respect to the Lebesgue measure) and the other is discrete (a sum of Dirac masses). We characterize the optimal solutions and show they can be written in terms of generalized Laguerre diagrams. We use this to develop an efficient method for solving the semi-discrete unbalanced transport problem numerically. As an application we study the unbalanced quantization problem, where one looks for the best approximation of a diffuse measure by a discrete measure with respect to an unbalanced transport metric. We prove a type of crystallization result in two dimensions -- optimality of a locally triangular lattice with spatially varying density -- and compute the asymptotic quantization error as the number of Dirac masses tends to infinity.
- [26] arXiv:2205.03260 (replaced) [pdf, other]
-
Title: Convex Analysis at Infinity: An Introduction to Astral SpaceSubjects: Optimization and Control (math.OC); Machine Learning (cs.LG)
Not all convex functions on $\mathbb{R}^n$ have finite minimizers; some can only be minimized by a sequence as it heads to infinity. In this work, we aim to develop a theory for understanding such minimizers at infinity. We study astral space, a compact extension of $\mathbb{R}^n$ to which such points at infinity have been added. Astral space is constructed to be as small as possible while still ensuring that all linear functions can be continuously extended to the new space. Although astral space includes all of $\mathbb{R}^n$, it is not a vector space, nor even a metric space. However, it is sufficiently well-structured to allow useful and meaningful extensions of concepts of convexity, conjugacy, and subdifferentials. We develop these concepts and analyze various properties of convex functions on astral space, including the detailed structure of their minimizers, exact characterizations of continuity, and convergence of descent algorithms.
- [27] arXiv:2310.08603 (replaced) [pdf, html, other]
-
Title: Sufficient Conditions for Error Distance Reduction in the (\ell^2)-norm Trust Region between Minimizers of Local Nonconvex Multivariate Quadratic ApproximatesComments: 11 pagesSubjects: Optimization and Control (math.OC)
This paper analyzes the sufficient conditions for distance reduction between minimizers of local nonconvex quadratic approximate functions with diagonal Hessian in the (\ell^2)-norm trust regions after two iterations. Some examples illustrate the theoretical results of this study.
- [28] arXiv:2407.02186 (replaced) [pdf, html, other]
-
Title: Data-Driven Probabilistic Methodology for Aircraft Conflict Detection Under Wind UncertaintyJournal-ref: IEEE Transactions on Aerospace and Electronic Systems, Volume: 59, Issue: 5, October 2023, Page(s): 5174 - 5186Subjects: Optimization and Control (math.OC)
Assuming the availability of a reliable aircraft trajectory planner, this paper presents a probabilistic methodology to detect conflicts between aircraft, in the cruise phase of the flight, in the presence of wind prediction uncertainties quantified by ensemble weather forecasts, which are regarded as realizations of correlated random processes and employed to derive the eastward and northward components of the wind velocity. First, the Karhunen-Lo`eve expansion is used to obtain a series expansion of the wind components in terms of a set of uncorrelated random variables and deterministic coefficients. Then, the uncertainty induced by these uncorrelated random variables in the outputs of the aircraft trajectory planner is quantified by means of the arbitrary polynomial chaos technique. Finally, the probability density function of the great circle distance between each pair of aircraft is derived from the polynomial expansions using a Gaussian kernel density estimator and employed to estimate the probability of conflict. The arbitrary polynomial chaos technique allows the effects of uncertainties in complex nonlinear dynamical system, such as those underlying aircraft trajectory planners, to be quantified with high computational efficiency, only requiring the existence of a finite number of statistical moments of the random variables of the Karhunen-Lo`eve expansion, while avoiding any assumption on their probability distributions. In order to demonstrate the effectiveness of the proposed conflict detection method, numerical experiments are conducted through an optimal control based aircraft trajectory planner for a given wind forecast represented by an ensemble prediction system.
- [29] arXiv:2407.10544 (replaced) [pdf, html, other]
-
Title: Port-Hamiltonian Modeling and Control of Electric Vehicle Charging StationsSubjects: Optimization and Control (math.OC)
Electric vehicles (EV) are an important part of future sustainable transportation. The increasing integration of EV charging stations (EVCSs) in the existing power grids require new scaleable control algorithms that maintain the stability and resilience of the grid. Here, we present such a control approach using an averaged port-Hamiltonian model. In this approach, the underlying switching behavior of the power converters is approximated by an averaged non-linear system. The averaged models are used to derive various types of stabilizing controllers, including the typically used PI controllers. The pH modeling is showcased by means of a generic setup of an EVCS, where the battery of the vehicle is connected to an AC grid via power lines, converters, and filters. Finally, the control design methods are compared for the averaged pH system and validated using a simulation model of the switched charging station.
- [30] arXiv:1912.04007 (replaced) [pdf, other]
-
Title: Subspace power method for symmetric tensor decompositionComments: 34 pages. v4: reorganized and improved; material on GPCA is removed and will appear elsewhere; title is edited slightly to reflect new versionSubjects: Numerical Analysis (math.NA); Optimization and Control (math.OC)
We introduce the Subspace Power Method (SPM) for calculating the CP decomposition of low-rank real symmetric tensors. This algorithm calculates one new CP component at a time, alternating between applying the shifted symmetric higher-order power method (SS-HOPM) to a certain modified tensor, constructed from a matrix flattening of the original tensor; and using appropriate deflation steps. We obtain rigorous guarantees for SPM regarding convergence and global optima for input tensors of dimension $d$ and order $m$ of rank up to $O(d^{\lfloor m/2\rfloor})$, via results in classical algebraic geometry and optimization theory. As a by-product of our analysis we prove that SS-HOPM converges unconditionally, settling a conjecture of Kolda-Mayo. Numerical experiments demonstrate that SPM is roughly one order of magnitude faster than state-of-the-art CP decomposition algorithms at moderate ranks. Furthermore, prior knowledge of the CP rank is not required by SPM.
- [31] arXiv:2209.09026 (replaced) [pdf, other]
-
Title: Automatic driving path plan based on iterative and triple optimization methodSubjects: Robotics (cs.RO); Optimization and Control (math.OC)
This paper presents a triple optimization algorithm of two-dimensional space, driving path and driving speed, and iterates in the time dimension to obtain the local optimal solution of path and speed in the optimal driving area. Design iterative algorithm to solve the best driving path and speed within the limited conditions. The algorithm can meet the path planning needs of automatic driving vehicle in complex scenes and medium and high-speed scenes.
- [32] arXiv:2210.16395 (replaced) [pdf, html, other]
-
Title: Ensure Differential Privacy and Convergence Accuracy in Consensus Tracking and Aggregative Games with Coupling ConstraintsComments: arXiv admin note: text overlap with arXiv:2209.01486Subjects: Computer Science and Game Theory (cs.GT); Cryptography and Security (cs.CR); Optimization and Control (math.OC)
We address differential privacy for fully distributed aggregative games with shared coupling constraints. By co-designing the generalized Nash equilibrium (GNE) seeking mechanism and the differential-privacy noise injection mechanism, we propose the first GNE seeking algorithm that can ensure both provable convergence to the GNE and rigorous epsilon-differential privacy, even with the number of iterations tending to infinity. As a basis of the co-design, we also propose a new consensus-tracking algorithm that can achieve rigorous epsilon-differential privacy while maintaining accurate tracking performance, which, to our knowledge, has not been achieved before. To facilitate the convergence analysis, we also establish a general convergence result for stochastically-perturbed nonstationary fixed-point iteration processes, which lie at the core of numerous optimization and variational problems. Numerical simulation results confirm the effectiveness of the proposed approach.
- [33] arXiv:2306.13584 (replaced) [pdf, html, other]
-
Title: Revisiting the Optimal PMU Placement Problem in Multi-Machine Power NetworksSubjects: Systems and Control (eess.SY); Optimization and Control (math.OC)
To provide real-time visibility of physics-based states, phasor measurement units (PMUs) are deployed throughout power networks. PMU data enable real-time grid monitoring and control -- and are essential in transitioning to smarter grids. Various considerations are taken into account when determining the geographic, optimal PMU placements (OPP). This paper focuses on the control-theoretic, observability aspect of OPP. A myriad of studies have investigated observability-based formulations to determine the OPP within a transmission network. However, they have mostly adopted a simplified representation of system dynamics, ignored basic algebraic equations that model power flows, disregarded including renewables such as solar and wind, and did not model their uncertainty. Consequently, this paper revisits the observability-based OPP problem by addressing the literature's limitations. A nonlinear differential algebraic representation (NDAE) of the power system is considered. The system is discretized using various discretization approaches while explicitly accounting for uncertainty. A moving horizon estimation approach is explored to reconstruct the joint differential and algebraic initial states of the system, as a gateway to the OPP problem which is then formulated as a computationally tractable integer program (IP). Comprehensive numerical simulations on standard power networks are conducted to validate the different aspects of this approach and test its robustness to various dynamical conditions
- [34] arXiv:2311.16760 (replaced) [pdf, html, other]
-
Title: Fair Interventions in Weighted Congestion GamesSubjects: Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC); Optimization and Control (math.OC)
In this work we study the power and limitations of fair interventions in weighted congestion games. Specifically, we focus on interventions that aim at improving the equilibrium quality (price of anarchy) and are fair in a suitably defined sense. Within this setting, we provide three key contributions. First, we show that no fair intervention can reduce the price of anarchy below a given factor depending solely on the class of latencies considered. Interestingly, this lower bound is unconditional, i.e., it applies regardless of how much computation interventions are allowed to use. Second, we design a taxation mechanism that is fair and achieves a price of anarchy matching this unconditional lower bound, all the while being polynomial-time computable. Third, we show that no intervention (fair or not) can achieve a better approximation if polynomial computability is required. We do so by proving that the minimum social cost is NP-hard to minimize below a factor identical to the one previously introduced. In doing so, our work shows that the algorithm proposed by Makarychev and Sviridenko (Journal of the ACM, 2018) to tackle optimization problems with a "diseconomy of scale" is optimal, and provide a novel way to derandomize its solution via equilibrium computation.
- [35] arXiv:2402.11425 (replaced) [pdf, html, other]
-
Title: Bayesian Online Multiple Testing: A Resource Allocation ApproachSubjects: Methodology (stat.ME); Machine Learning (cs.LG); Optimization and Control (math.OC); Probability (math.PR)
We consider the problem of sequentially conducting multiple experiments where each experiment corresponds to a hypothesis testing task. At each time point, the experimenter must make an irrevocable decision of whether to reject the null hypothesis (or equivalently claim a discovery) before the next experimental result arrives. The goal is to maximize the number of discoveries while maintaining a low error rate at all time points measured by Local False Discovery Rate (LFDR). We formulate the problem as an online knapsack problem with exogenous random budget replenishment. We start with general arrival distributions and show that a simple policy achieves a $O(\sqrt{T})$ regret. We complement the result by showing that such regret rate is in general not improvable. We then shift our focus to discrete arrival distributions. We find that many existing re-solving heuristics in the online resource allocation literature, albeit achieve bounded loss in canonical settings, may incur a $\Omega(\sqrt{T})$ or even a $\Omega(T)$ regret. With the observation that canonical policies tend to be too optimistic and over claim discoveries, we propose a novel policy that incorporates budget safety buffers. It turns out that a little more safety can greatly enhance efficiency -- small additional logarithmic buffers suffice to reduce the regret from $\Omega(\sqrt{T})$ or even $\Omega(T)$ to $O(\ln^2 T)$. From a practical perspective, we extend the policy to the scenario with continuous arrival distributions, time-dependent information structures, as well as unknown $T$. We conduct both synthetic experiments and empirical applications on a time series data from New York City taxi passengers to validate the performance of our proposed policies. Our results emphasize how effective policies should be designed in online resource allocation problems with exogenous budget replenishment.
- [36] arXiv:2403.08906 (replaced) [pdf, html, other]
-
Title: Strategizing against Q-learners: A Control-theoretical ApproachComments: The extended arXiv version of the original paper to appear in IEEE L-CSSJournal-ref: IEEE Control Systems Letters 8 (2024) 1733-1738Subjects: Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI); Optimization and Control (math.OC)
In this paper, we explore the susceptibility of the independent Q-learning algorithms (a classical and widely used multi-agent reinforcement learning method) to strategic manipulation of sophisticated opponents in normal-form games played repeatedly. We quantify how much strategically sophisticated agents can exploit naive Q-learners if they know the opponents' Q-learning algorithm. To this end, we formulate the strategic actors' interactions as a stochastic game (whose state encompasses Q-function estimates of the Q-learners) as if the Q-learning algorithms are the underlying dynamical system. We also present a quantization-based approximation scheme to tackle the continuum state space and analyze its performance for two competing strategic actors and a single strategic actor both analytically and numerically.
- [37] arXiv:2407.02083 (replaced) [pdf, other]
-
Title: Passivity Tools for Hybrid Learning Rules in Large PopulationsComments: 12 pages, 3 figuresSubjects: Dynamical Systems (math.DS); Systems and Control (eess.SY); Optimization and Control (math.OC)
Recent work has pioneered the use of system-theoretic passivity to study equilibrium stability for the dynamics of noncooperative strategic interactions in large populations of learning agents. In this and related works, the stability analysis leverages knowledge that certain ``canonical'' classes of learning rules used to model the agents' strategic behaviors satisfy a passivity condition known as $\delta$-passivity. In this paper, we consider that agents exhibit learning behaviors that do not align with a canonical class. Specifically, we focus on characterizing $\delta$-passivity for hybrid learning rules that combine elements from canonical classes. Our analysis also introduces and uses a more general version of $\delta$-passivity, which, for the first time, can handle discontinuous learning rules, including those showing best-response behaviors. We state and prove theorems establishing $\delta$-passivity for two broad convex cones of hybrid learning rules. These cones can merge into a larger one preserving $\delta$-passivity in scenarios limited to two strategies. In our proofs, we establish intermediate facts that are significant on their own and could potentially be used to further generalize our work. We illustrate the applicability of our results through numerical examples.
- [38] arXiv:2407.10955 (replaced) [pdf, html, other]
-
Title: Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing StepsizeSubjects: Machine Learning (stat.ML); Machine Learning (cs.LG); Optimization and Control (math.OC)
In this paper, we revisit \textsf{ROOT-SGD}, an innovative method for stochastic optimization to bridge the gap between stochastic optimization and statistical efficiency. The proposed method enhances the performance and reliability of \textsf{ROOT-SGD} by integrating a carefully designed \emph{diminishing stepsize strategy}. This approach addresses key challenges in optimization, providing robust theoretical guarantees and practical benefits. Our analysis demonstrates that \textsf{ROOT-SGD} with diminishing achieves optimal convergence rates while maintaining computational efficiency. By dynamically adjusting the learning rate, \textsf{ROOT-SGD} ensures improved stability and precision throughout the optimization process. The findings of this study offer valuable insights for developing advanced optimization algorithms that are both efficient and statistically robust.