Optimization and Control
See recent articles
- [1] arXiv:2408.00037 [pdf, html, other]
-
Title: How We Decide the Future of the Olympics ?Subjects: Optimization and Control (math.OC)
The "Olympic Agenda 2020" stresses the urgency of measuring the impact of the Olympic Games on host cities in the face of declining bids. This paper presents the Hosting the Olympics Influence Evaluation Model (HOIEM) to assess these impacts and propose sustainable solutions.We select indicators (economic, socio-cultural, human, environmental and political) based on literature review and construct HOIEM. We use AHP and TOPSIS-EWM to determine the final weights for these indicators. We identify 45 potential host cities based on IOC requirements. For the Winter Olympics, secondary screening and the GM(1,1) model highlight Calgary, Canada as the top city. For the Summer Olympics, the SWOT analysis identifies Beijing, China. We propose to hold Spring, Summer, Autumn and Winter Olympics every 4 years, with fixed cities for Summer and Winter and bidding for Spring and Autumn.Finally, we conduct sensitivity analysis for HOIEM, demonstrating the independence and relevance of selected indicators through semi-quantitative visual analysis.
- [2] arXiv:2408.00235 [pdf, html, other]
-
Title: Solving cluster moment relaxation with hierarchical matrixSubjects: Optimization and Control (math.OC); Numerical Analysis (math.NA)
Convex relaxation methods are powerful tools for studying the lowest energy of many-body problems. By relaxing the representability conditions for marginals to a set of local constraints, along with a global semidefinite constraint, a polynomial-time solvable semidefinite program (SDP) that provides a lower bound for the energy can be derived. In this paper, we propose accelerating the solution of such an SDP relaxation by imposing a hierarchical structure on the positive semidefinite (PSD) primal and dual variables. Furthermore, these matrices can be updated efficiently using the algebra of the compressed representations within an augmented Lagrangian method. We achieve quadratic and even near-linear time per-iteration complexity. Through experimentation on the quantum transverse field Ising model, we showcase the capability of our approach to provide a sufficiently accurate lower bound for the exact ground-state energy.
- [3] arXiv:2408.00431 [pdf, other]
-
Title: An Operational Scheduling Framework for Tanker-based Water Distribution System under UncertaintyComments: 46 pages, 11 figuresSubjects: Optimization and Control (math.OC)
Tanker water systems play critical role in providing adequate service to meet potable water demands in the face of acute water crisis in many cities globally. Managing tanker movements among the supply and demand sides requires an efficient scheduling framework that could promote economic feasibility, ensure timely delivery, and avoid water wastage. However, to realize such a sustainable water supply operation, inherent uncertainties related to consumer demand and tanker travel time need to accounted in the operational scheduling. Herein, a two-stage stochastic optimization model with a recourse approach is developed for scheduling and optimization of tanker based water supply and treatment facility operations under uncertainty. The uncertain water demands and tanker travel times are combinedly modelled in a computationally efficient manner using a hybrid Monte Carlo simulation and scenario tree approach. The maximum demand fulfillment, limited extraction of groundwater, and timely delivery of quality water are enforced through a set of constraints to achieve sustainable operation. A representative urban case study is demonstrated, results are discussed for two uncertainty cases (i) only demand, and (ii) integrated demand-travel time. Value of stochastic solution over expected value and perfect information model solutions are analyzed and features of the framework for informed decision-making are discussed.
- [4] arXiv:2408.00543 [pdf, html, other]
-
Title: Global convergence of a modified BFGS-type method based on function information for nonconvex multiobjective optimization problemsSubjects: Optimization and Control (math.OC)
We propose a modified BFGS-type method based on function information for nonconvex multiobjective optimization problems (MFQNMO). The method employs a common BFGS matrix to approximate the Hessian matrix of all objective functions in each iteration. This matrix is updated using function and gradient information from the previous step. Our analysis confirms the convergence of the method without relying on convexity assumptions. We also establish a local superlinear convergence rate for MFQNMO under mild conditions and validate its effectiveness through experiments on both nonconvex and convex test problems.
- [5] arXiv:2408.00586 [pdf, html, other]
-
Title: Lipschitz Modulus of Convex Functions via Function ValuesSubjects: Optimization and Control (math.OC)
In this note, we establish the Lipschitz continuity of finite-dimensional globally convex functions on all given balls and global Lipschitz continuity for eligible functions of that type. The Lipschitz constants in both situations draw information solely from function values, and the global Lipschitz modulus is found when it exists. Some examples of classes of globally Lipschitz continuous convex functions beside the norms are also provided along with their global Lipschitz modulus.
- [6] arXiv:2408.00598 [pdf, html, other]
-
Title: HOT: An Efficient Halpern Accelerating Algorithm for Optimal Transport ProblemsSubjects: Optimization and Control (math.OC)
This paper proposes an efficient HOT algorithm for solving the optimal transport (OT) problems with finite supports. We particularly focus on an efficient implementation of the HOT algorithm for the case where the supports are in $\mathbb{R}^2$ with ground distances calculated by $L_2^2$-norm. Specifically, we design a Halpern accelerating algorithm to solve the equivalent reduced model of the discrete OT problem. Moreover, we derive a novel procedure to solve the involved linear systems in the HOT algorithm in linear time complexity. Consequently, we can obtain an $\varepsilon$-approximate solution to the optimal transport problem with $M$ supports in $O(M^{1.5}/\varepsilon)$ flops, which significantly improves the best-known computational complexity. We further propose an efficient procedure to recover an optimal transport plan for the original OT problem based on a solution to the reduced model, thereby overcoming the limitations of the reduced OT model in applications that require the transport map. We implement the HOT algorithm in PyTorch and extensive numerical results show the superior performance of the HOT algorithm compared to existing state-of-the-art algorithms for solving the OT problems.
- [7] arXiv:2408.00663 [pdf, other]
-
Title: Fleet-mix Electric Vehicle Routing Problem for the E-commerce Delivery with Limited Off-Hour Delivery ImplementationHyun-Seop Uhm, Abdelrahman Ismael, Natalia Zuniga-Garcia, Olcay Sahin, James Cook, Joshua Auld, Monique StinsonSubjects: Optimization and Control (math.OC)
Freight truck electrification for last-mile delivery is one of the most important research topics to reduce the dependency on fossil fuel operations. Although a battery electric truck still has limitations on daily operations with lower driving ranges and higher purchasing cost than a conventional truck, operations with electrified trucks reduce total energy usage and driving noise on routes. In this paper, we propose a fleet-mix and multi-shift electric vehicle routing problem for joint implementation of fleet electrification and off-hour delivery in urban e-commerce delivery systems. Every electrified truck is assumed to have two shifts for both daytime and nighttime delivery operations while conventional trucks can operate during daytime only because of municipal restrictions on nighttime deliveries, which are related to engine noise. Also, every electrified truck must recharge between shifts at its depot. A fleet owner decides the best electrification ratio of the fleet and the proper number of chargers which gives the minimum total cost. The optimization problem is described as a mixed-integer linear programming model including common constraints for vehicle routing problem, recharging constraints, and two-shift operation of electrified trucks. A bi-level VNS-TS heuristic is also suggested for efficient solution search. The upper-level problem assigns trucks with engine type and brief route information using variable neighborhood search heuristic, and the lower-level problem finds the best route of each assigned truck using a tabu search heuristic. Scenarios with different EV driving ranges and nighttime operation availabilities are developed and evaluated with the POLARIS transportation simulation framework, and results are reported.
- [8] arXiv:2408.00697 [pdf, html, other]
-
Title: On the Controllability of an Orbiting Satellite Model with Electromagnetic-only ActuationSubjects: Optimization and Control (math.OC)
This paper presents sufficient conditions for small-time local controllability of a control-affine system that describes the rotational motion of a satellite in a circular orbit. The satellite is modeled as a rigid body subject to electromagnetic actuation. We focus on the underactuated scenario where the control torque is generated solely by magnetorquers. The main contributions of this work include proving small-time local controllability around the relative equilibrium under some natural assumptions on the mass distribution of the rigid body. This result is based on the Lie algebra rank condition and Sussmann's controllability condition. Furthermore, it is shown that the linearized system is not controllable in a neighborhood of the considered equilibrium.
- [9] arXiv:2408.00718 [pdf, html, other]
-
Title: A Multi-Reference Relaxation Enforced Neighborhood Search Heuristic in SCIPComments: six pages, new primal heuristic in SCIP, mixed integer linear optimizationSubjects: Optimization and Control (math.OC); Mathematical Software (cs.MS)
This paper proposes and evaluates a Multi-Reference Relaxation Enforced Neighborhood Search (MRENS) heuristic within the SCIP solver. This study marks the first integration and evaluation of MRENS in a full-fledged MILP solver, specifically coupled with the recently-introduced Lagromory separator for generating multiple reference solutions. Computational experiments on the MIPLIB 2017 benchmark set show that MRENS, with multiple reference solutions, improves the solver's ability to find higher-quality feasible solutions compared to single-reference approaches. This study highlights the potential of multi-reference heuristics in enhancing primal heuristics in MILP solvers.
- [10] arXiv:2408.00720 [pdf, html, other]
-
Title: Nonasymptotic Analysis of Accelerated Methods With Inexact Oracle Under Absolute Error BoundSubjects: Optimization and Control (math.OC)
Performance analysis of first-order algorithms with inexact oracle has gained recent attention due to various emerging applications in which obtaining exact gradients is impossible or computationally expensive. Previous research has demonstrated that the performance of accelerated first-order methods is more sensitive to gradient errors compared with non-accelerated ones. This paper investigates the nonasymptotic convergence bound of two accelerated methods with inexact gradients to solve deterministic smooth convex problems. Performance Estimation Problem (PEP) is used as the primary tool to analyze the convergence bounds of the underlying algorithms. By finding an analytical solution to PEP, we derive novel convergence bounds for Inexact Optimized Gradient Method (OGM) and Inexact Fast Gradient Method (FGM) with variable inexactness along iterations. Under the absolute error assumption, we derive bounds in which the accumulated errors are independent of the initial conditions and the trajectory of the sequences generated by the algorithms. Furthermore, we analyze the tradeoff between the convergence rate and accumulated error that guides finding the optimal stepsize. Finally, we determine the optimal strategy to set the gradient inexactness along iterations (if possible), ensuring that the accumulated error remains subordinate to the convergence rate.
- [11] arXiv:2408.00733 [pdf, html, other]
-
Title: Potential Mean-Field Games and Gradient FlowsSubjects: Optimization and Control (math.OC)
We consider a mean-field optimal control problem with general dynamics including common noise and jumps and show that its minimizers are Nash equilibria of an associated mean-field game of controls. These types of games are necessarily potential, and the Nash equilibria obtained as the minimizers of the control problems are naturally related to the McKean-Vlasov equations of Langevin type. We provide several examples to motivate the general theory including the Cucker-Smale Flocking and Kuramoto mean-field games. The invariance property of the value function of these control problems, utilized in our proof, is also proved.
New submissions for Friday, 2 August 2024 (showing 11 of 11 entries )
- [12] arXiv:2408.00018 (cross-list from cs.DC) [pdf, html, other]
-
Title: An efficient implementation of parallel simulated annealing algorithm in GPUsSubjects: Distributed, Parallel, and Cluster Computing (cs.DC); Optimization and Control (math.OC)
In this work we propose a highly optimized version of a simulated annealing (SA) algorithm adapted to the more recently developed Graphic Processor Units (GPUs). The programming has been carried out with CUDA toolkit, specially designed for Nvidia GPUs. For this purpose, efficient versions of SA have been first analyzed and adapted to GPUs. Thus, an appropriate sequential SA algorithm has been developed as a starting point. Next, a straightforward asynchronous parallel version has been implemented and then a specific and more efficient synchronous version has been developed. A wide appropriate benchmark to illustrate the performance properties of the implementation has been considered. Among all tests, a classical sample problem provided by the minimization of the normalized Schwefel function has been selected to compare the behavior of the sequential, asynchronous, and synchronous versions, the last one being more advantageous in terms of balance between convergence, accuracy, and computational cost. Also, the implementation of a hybrid method combining SA with a local minimizer method has been developed. Note that the generic feature of the SA algorithm allows its application in a wide set of real problems arising in a large variety of fields, such as biology, physics, engineering, finance, and industrial processes.
- [13] arXiv:2408.00021 (cross-list from math.AP) [pdf, html, other]
-
Title: Optimal design problem with thermal radiationSubjects: Analysis of PDEs (math.AP); Optimization and Control (math.OC)
This paper is concerned with configurations of two-material thermal conductors that minimize the Dirichlet energy for steady-state diffusion equations with nonlinear boundary conditions described mainly by maximal monotone operators. To find such configurations, a homogenization theorem will be proved and applied to an existence theorem for minimizers of a relaxation problem whose minimum value is equivalent to an original design problem. As a typical example of nonlinear boundary conditions, thermal radiation boundary conditions will be the focus, and then the Fréchet derivative of the Dirichlet energy will be derived, which is used to estimate the minimum value. Since optimal configurations of the relaxation problem involve the so-called grayscale domains that do not make sense in general, a perimeter constraint problem via the positive part of the level set function will be introduced as an approximation problem to avoid such domains, and moreover, the existence theorem for minimizers of the perimeter constraint problem will be proved. In particular, it will also be proved that the limit of minimizers for the approximation problem becomes that of the relaxation problem in a specific case, and then candidates for minimizers of the approximation problem will be constructed by employing time-discrete versions of nonlinear diffusion equations. In this paper, it will be shown that optimized configurations deeply depend on force terms as a characteristic of nonlinear problems and will also be applied to real physical problems.
- [14] arXiv:2408.00143 (cross-list from math.DS) [pdf, html, other]
-
Title: Observability of complex systems via conserved quantitiesComments: 15 pages, 3 figuresSubjects: Dynamical Systems (math.DS); Optimization and Control (math.OC)
Many systems in biology, physics, and engineering are modeled by nonlinear dynamical systems where the states are usually unknown and only a subset of the state variables can be physically measured. Can we understand the full system from what we measure? In the mathematics literature, this question is framed as the observability problem. It has to do with recovering information about the state variables from the observed states (the measurements). In this paper, we relate the observability problem to another structural feature of many models relevant in the physical and biological sciences: the conserved quantity. For models based on systems of differential equations, conserved quantities offer desirable properties such as dimension reduction which simplifies model analysis. Here, we use differential embeddings to show that conserved quantities involving a set of special variables provide more flexibility in what can be measured to address the observability problem for systems of interest in biology. Specifically, we provide conditions under which a collection of conserved quantities make the system observable. We apply our methods to provide alternate measurable variables in models where conserved quantities have been used for model analysis historically in biological contexts.
- [15] arXiv:2408.00310 (cross-list from cs.LG) [pdf, other]
-
Title: Online Linear Programming with BatchingSubjects: Machine Learning (cs.LG); Optimization and Control (math.OC)
We study Online Linear Programming (OLP) with batching. The planning horizon is cut into $K$ batches, and the decisions on customers arriving within a batch can be delayed to the end of their associated batch. Compared with OLP without batching, the ability to delay decisions brings better operational performance, as measured by regret. Two research questions of interest are: (1) What is a lower bound of the regret as a function of $K$? (2) What algorithms can achieve the regret lower bound? These questions have been analyzed in the literature when the distribution of the reward and the resource consumption of the customers have finite support. By contrast, this paper analyzes these questions when the conditional distribution of the reward given the resource consumption is continuous, and we show the answers are different under this setting. When there is only a single type of resource and the decision maker knows the total number of customers, we propose an algorithm with a $O(\log K)$ regret upper bound and provide a $\Omega(\log K)$ regret lower bound. We also propose algorithms with $O(\log K)$ regret upper bound for the setting in which there are multiple types of resource and the setting in which customers arrive following a Poisson process. All these regret upper and lower bounds are independent of the length of the planning horizon, and all the proposed algorithms delay decisions on customers arriving in only the first and the last batch. We also take customer impatience into consideration and establish a way of selecting an appropriate batch size.
- [16] arXiv:2408.00329 (cross-list from cs.LG) [pdf, html, other]
-
Title: OTAD: An Optimal Transport-Induced Robust Model for Agnostic Adversarial AttackComments: 14 pages, 2 figuresSubjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Optimization and Control (math.OC); Machine Learning (stat.ML)
Deep neural networks (DNNs) are vulnerable to small adversarial perturbations of the inputs, posing a significant challenge to their reliability and robustness. Empirical methods such as adversarial training can defend against particular attacks but remain vulnerable to more powerful attacks. Alternatively, Lipschitz networks provide certified robustness to unseen perturbations but lack sufficient expressive power. To harness the advantages of both approaches, we design a novel two-step Optimal Transport induced Adversarial Defense (OTAD) model that can fit the training data accurately while preserving the local Lipschitz continuity. First, we train a DNN with a regularizer derived from optimal transport theory, yielding a discrete optimal transport map linking data to its features. By leveraging the map's inherent regularity, we interpolate the map by solving the convex integration problem (CIP) to guarantee the local Lipschitz property. OTAD is extensible to diverse architectures of ResNet and Transformer, making it suitable for complex data. For efficient computation, the CIP can be solved through training neural networks. OTAD opens a novel avenue for developing reliable and secure deep learning systems through the regularity of optimal transport maps. Empirical results demonstrate that OTAD can outperform other robust models on diverse datasets.
- [17] arXiv:2408.00465 (cross-list from cs.DS) [pdf, html, other]
-
Title: Infrequent Resolving Algorithm for Online Linear ProgrammingComments: 35 pages, 7 figuresSubjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Optimization and Control (math.OC)
Online linear programming (OLP) has gained significant attention from both researchers and practitioners due to its extensive applications, such as online auction, network revenue management and advertising. Existing OLP algorithms fall into two categories: LP-based algorithms and LP-free algorithms. The former one typically guarantees better performance, even offering a constant regret, but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithm only requires first-order computations but induces a worse performance, lacking a constant regret bound. In this work, we bridge the gap between these two extremes by proposing an algorithm that achieves a constant regret while solving LPs only $O(\log\log T)$ times over the time horizon $T$. Moreover, when we are allowed to solve LPs only $M$ times, we propose an algorithm that can guarantee an $O\left(T^{(1/2+\epsilon)^{M-1}}\right)$ regret. Furthermore, when the arrival probabilities are known at the beginning, our algorithm can guarantee a constant regret by solving LPs $O(\log\log T)$ times, and an $O\left(T^{(1/2+\epsilon)^{M}}\right)$ regret by solving LPs only $M$ times. Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms.
- [18] arXiv:2408.00581 (cross-list from math.NA) [pdf, html, other]
-
Title: Dimension reduction for large-scale stochastic systems with non-zero initial states and controlled diffusionSubjects: Numerical Analysis (math.NA); Optimization and Control (math.OC); Probability (math.PR)
In this paper, we establish new strategies to reduce the dimension of large-scale controlled stochastic differential equations with non-zero initial states. The first approach transforms the original setting into a stochastic system with zero initial states. This transformation naturally leads to equations with controlled diffusion. A detailed analysis of dominant subspaces and bounds for the reduction error is provided in this controlled diffusion framework. Subsequently, we introduce a reduced system for the original framework and prove an a-priori error bound for the first ansatz. This bound involves so-called Hankel singular values that are linked to a new pair of Gramians. A second strategy is presented that is based on the idea of reducing control and initial state dynamics separately. Here, different Gramians are used in order to derive a reduced model and their relation to dominant subspaces are pointed out. We also show an a posteriori error bound for the second approach involving two types of Hankel singular values.
- [19] arXiv:2408.00627 (cross-list from math.NA) [pdf, other]
-
Title: Factorization of a prime matrix in even blocksSubjects: Numerical Analysis (math.NA); Optimization and Control (math.OC); Rings and Algebras (math.RA)
In this paper, a matrix is said to be prime if the row and column of this matrix are both prime numbers. We establish various necessary and sufficient conditions for developing matrices into the sum of tensor products of prime matrices. For example, if the diagonal of a matrix blocked evenly are pairwise commutative, it yields such a decomposition. The computational complexity of multiplication of these algorithms is shown to be $O(n^{5/2})$. In the section 5, a decomposition is proved to hold if and only if every even natural number greater than 2 is the sum of two prime numbers.
- [20] arXiv:2408.00647 (cross-list from cs.GT) [pdf, html, other]
-
Title: Counterclockwise Dissipativity, Potential Games and Evolutionary Nash Equilibrium LearningComments: 8 pages, 2 figuresSubjects: Computer Science and Game Theory (cs.GT); Systems and Control (eess.SY); Dynamical Systems (math.DS); Optimization and Control (math.OC)
We use system-theoretic passivity methods to study evolutionary Nash equilibria learning in large populations of agents engaged in strategic, non-cooperative interactions. The agents follow learning rules (rules for short) that capture their strategic preferences and a payoff mechanism ascribes payoffs to the available strategies. The population's aggregate strategic profile is the state of an associated evolutionary dynamical system. Evolutionary Nash equilibrium learning refers to the convergence of this state to the Nash equilibria set of the payoff mechanism. Most approaches consider memoryless payoff mechanisms, such as potential games. Recently, methods using $\delta$-passivity and equilibrium independent passivity (EIP) have introduced dynamic payoff mechanisms. However, $\delta$-passivity does not hold when agents follow rules exhibiting ``imitation" behavior, such as in replicator dynamics. Conversely, EIP applies to the replicator dynamics but not to $\delta$-passive rules. We address this gap using counterclockwise dissipativity (CCW). First, we prove that continuous memoryless payoff mechanisms are CCW if and only if they are potential games. Subsequently, under (possibly dynamic) CCW payoff mechanisms, we establish evolutionary Nash equilibrium learning for any rule within a convex cone spanned by imitation rules and continuous $\delta$-passive rules.
- [21] arXiv:2408.00713 (cross-list from cs.LG) [pdf, html, other]
-
Title: Insurance Portfolio Pursuit with Reinforcement LearningComments: 16 pages, 1 figureSubjects: Machine Learning (cs.LG); Optimization and Control (math.OC); Machine Learning (stat.ML)
When faced with a new customer, many factors contribute to an insurance firm's decision of what offer to make to that customer. In addition to the expected cost of providing the insurance, the firm must consider the other offers likely to be made to the customer, and how sensitive the customer is to differences in price. Moreover, firms often target a specific portfolio of customers that could depend on, e.g., age, location, and occupation. Given such a target portfolio, firms may choose to modulate an individual customer's offer based on whether the firm desires the customer within their portfolio. Given a target portfolio, we term the problem of modulating offers to achieve this target portfolio the portfolio pursuit problem. We give a formulation of portfolio pursuit as a sequential decision making problem, and devise a novel reinforcement learning algorithm for its solution. We test our method on a complex synthetic market environment, and demonstrate that it outperforms a baseline method which mimics current industry approaches to portfolio pursuit.
Cross submissions for Friday, 2 August 2024 (showing 10 of 10 entries )
- [22] arXiv:2006.09884 (replaced) [pdf, html, other]
-
Title: Computer-assisted proofs for Lyapunov stability via Sums of Squares certificates and Constructive AnalysisSubjects: Optimization and Control (math.OC); Logic in Computer Science (cs.LO)
We provide a computer-assisted approach to ensure that a given continuous or discrete-time polynomial system is (asymptotically) stable. Our framework relies on constructive analysis together with formally certified sums of squares Lyapunov functions. The crucial steps are formalized within of the proof assistant Minlog. We illustrate our approach with various examples issued from the control system literature.
- [23] arXiv:2106.11405 (replaced) [pdf, html, other]
-
Title: Optimality and robustness in path-planning under initial uncertaintyComments: 25 pages, 14 figures. Keywords: optimal control, path-planning, Hamilton-Jacobi PDEs, uncertainty, robustness, delayed information acquisitionSubjects: Optimization and Control (math.OC)
Classical deterministic optimal control problems assume full information about the controlled process. The theory of control for general partially-observable processes is powerful, but the methods are computationally expensive and typically address the problems with stochastic dynamics and continuous (directly unobserved) stochastic perturbations. In this paper we focus on path planning problems which are in between -- deterministic, but with an initial uncertainty on either the target or the running cost on parts of the domain. That uncertainty is later removed at some time $T$, and the goal is to choose the optimal trajectory until then. We address this challenge for three different models of information acquisition: with fixed $T$, discretely distributed and exponentially distributed random $T$. We develop models and numerical methods suitable for multiple notions of optimality: based on the average-case performance, the worst-case performance, the average constrained by the worst, the average performance with probabilistic constraints on the bad outcomes, risk-sensitivity, and distributional-robustness. We illustrate our approach using examples of pursuing random targets identified at a (possibly random) later time $T$.
- [24] arXiv:2404.09323 (replaced) [pdf, html, other]
-
Title: Incremental data compression for PDE-constrained optimization with a data assimilation applicationSubjects: Optimization and Control (math.OC); Analysis of PDEs (math.AP)
We propose and analyze an inexact gradient method based on incremental proper orthogonal decomposition (iPOD) to address the data storage difficulty in time-dependent PDE-constrained optimization, particularly for a data assimilation problem as a detailed demonstration for the key ideas. The proposed method is proved robust by rigorous analysis. We first derive a sharp data compression error estimate of the iPOD with the help of Hilbert-Schmidt operators. Then we demonstrate a numerical PDE analysis to show how to properly choose the Hilbert space for the iPOD data compression so that the gradient error is under control. We further prove that for a convex problem with appropriately bounded gradient error, the inexact gradient method achieves the accuracy level of the optimal solution while not hurting the convergence rate compared with the usual gradient method. Finally, numerical experiments are provided to verify the theoretical results and validate the proposed method.
- [25] arXiv:2405.11185 (replaced) [pdf, html, other]
-
Title: Majorization-minimization Bregman proximal gradient algorithms for nonnegative matrix factorization with the Kullback--Leibler divergenceComments: 25 pages, 26 figuresSubjects: Optimization and Control (math.OC)
Nonnegative matrix factorization (NMF) is a popular method in machine learning and signal processing to decompose a given nonnegative matrix into two nonnegative matrices. In this paper, to solve NMF, we propose new algorithms, called majorization-minimization Bregman proximal gradient algorithm (MMBPG) and MMBPG with extrapolation (MMBPGe). MMBPG and MMBPGe minimize an auxiliary function majorizing the Kullback--Leibler (KL) divergence loss by the existing Bregman proximal gradient algorithms. While existing KL-based NMF methods update each variable alternately, proposed algorithms update all variables simultaneously. The proposed MMBPG and MMBPGe are equipped with a separable Bregman distance that satisfies the smooth adaptable property and that makes its subproblem solvable in closed forms. We also proved that even though these algorithms are designed to minimize an auxiliary function, MMBPG and MMBPGe monotonically decrease the objective function and a potential function, respectively. Using this fact, we establish that a sequence generated by MMBPG(e) globally converges to a Karush--Kuhn--Tucker (KKT) point. In numerical experiments, we compared proposed algorithms with existing algorithms on synthetic data.
- [26] arXiv:2406.13168 (replaced) [pdf, other]
-
Title: Stochastic Multi-objective Multi-trip AMR Routing Problem with Time WindowsSubjects: Optimization and Control (math.OC)
In recent years, with the rapidly aging population, alleviating the pressure on medical staff has become a critical issue. To improve the work efficiency of medical staff and reduce the risk of infection, we consider the multi-trip autonomous mobile robot (AMR) routing problem with the stochastic environment to find the solution to minimizing the total expected operating cost and maximizing the total service quality of patients so that each route violates the vehicle capacity and the time window with only a very small probability. The travel time of AMRs is stochastic affected by the surrounding environment, the demand for each ward is unknown until the AMR reaches the ward, and the service time is linearly related to the actual demand. We develop a population-based tabu search algorithm (PTS) that combines the genetic algorithm with the tabu search algorithm to solve the problem. Extensive numerical experiments were conducted on the modified Solomon instances to show that the PTS algorithm the efficient and reveals the impacts of the confidence level on the optimal solution, providing insights for the decision-maker to devise delivery schemes that trade-off the operating cost for patient satisfaction.
- [27] arXiv:2407.19064 (replaced) [pdf, html, other]
-
Title: Volume-preserving physics-informed geometric shape optimization of the Dirichlet energySubjects: Optimization and Control (math.OC); Numerical Analysis (math.NA)
In this work, we explore the numerical solution of geometric shape optimization problems using neural network-based approaches. This involves minimizing a numerical criterion that includes solving a partial differential equation with respect to a domain, often under geometric constraints like constant volume. Our goal is to develop a proof of concept using a flexible and parallelizable methodology to tackle these problems. We focus on a prototypal problem: minimizing the so-called Dirichlet energy with respect to the domain under a volume constraint, involving a Poisson equation in $\mathbb R^2$. We use physics-informed neural networks (PINN) to approximate the Poisson equation's solution on a given domain and represent the shape through a neural network that approximates a volume-preserving transformation from an initial shape to an optimal one. These processes are combined in a single optimization algorithm that minimizes the Dirichlet energy. One of the significant advantages of this approach is its parallelizable nature, which makes it easy to handle the addition of parameters. Additionally, it does not rely on shape derivative or adjoint calculations. Our approach is tested on Dirichlet and Robin boundary conditions, parametric right-hand sides, and extended to Bernoulli-type free boundary problems. The source code for solving the shape optimization problem is open-source and freely available.
- [28] arXiv:1712.02997 (replaced) [pdf, html, other]
-
Title: MV-PURE Spatial Filters with Application to EEG/MEG Source ReconstructionComments: IEEE Transactions on Signal Processing, 2019Subjects: Signal Processing (eess.SP); Optimization and Control (math.OC)
In this paper we propose spatial filters for a linear regression model which are based on the minimum-variance pseudo-unbiased reduced-rank estimation (MV-PURE) framework. As a sample application, we consider the problem of reconstruction of brain activity from electroencephalographic (EEG) or magnetoencephalographic (MEG) measurements. The proposed filters come in two versions depending on whether or not the EEG/MEG forward model explicitly considers interfering activity in the way of brain activity originating in regions different to those of main interest, but measured as correlated with signals of interest by the EEG/MEG sensor array. In both cases, the proposed filters are equipped with a rank-selection criterion minimizing the mean-square error (MSE) of the filter output. Therefore, we consider them as novel nontrivial generalizations of well-known linearly constrained minimum variance (LCMV) and nulling filters. In order to facilitate reproducibility of our research, we provide (jointly with this paper) comprehensive simulation framework that allows for estimation of error of signal reconstruction for a number of spatial filters applied to MEG or EEG signals. Based on this framework, chief properties of proposed filters are verified in a set of detailed simulations.
- [29] arXiv:2312.04932 (replaced) [pdf, html, other]
-
Title: Equivalence of entropy solutions and gradient flows for pressureless 1D Euler systemsComments: 53 pages, 8 figuresSubjects: Analysis of PDEs (math.AP); Optimization and Control (math.OC)
We study distributional solutions of pressureless Euler systems on the line. In particular we show that Lagrangian solutions, introduced by Brenier, Gangbo, Savaré and Westdickenberg, and entropy solutions, studied by Nguyen and Tudorascu for the Euler--Poisson system, are equivalent. For the Euler--Poisson system this can be seen as a generalization to second-order systems of the equivalence between $L^2$-gradient flows and entropy solutions for a first-order aggregation equation proved by Bonaschi, Carrillo, Di Francesco and Peletier. The key observation is an equivalence between Ole\uınik's E-condition for conservation laws and a characterization due to Natile and Savaré of the normal cone for $L^2$-gradient flows. This new equivalence allows us to define unique solutions after blow-up for classical solutions of the Euler--Poisson system with quadratic confinement due to Carrillo, Choi and Zatorska, as well as to describe their asymptotic behavior.
- [30] arXiv:2401.10467 (replaced) [pdf, html, other]
-
Title: Learning Backdoors for Mixed Integer Linear Programs with Contrastive LearningSubjects: Artificial Intelligence (cs.AI); Machine Learning (cs.LG); Optimization and Control (math.OC)
Many real-world problems can be efficiently modeled as Mixed Integer Linear Programs (MILPs) and solved with the Branch-and-Bound method. Prior work has shown the existence of MILP backdoors, small sets of variables such that prioritizing branching on them when possible leads to faster running times. However, finding high-quality backdoors that improve running times remains an open question. Previous work learns to estimate the relative solver speed of randomly sampled backdoors through ranking and then decide whether to use the highest-ranked backdoor candidate. In this paper, we utilize the Monte-Carlo tree search method to collect backdoors for training, rather than relying on random sampling, and adapt a contrastive learning framework to train a Graph Attention Network model to predict backdoors. Our method, evaluated on several common MILP problem domains, demonstrates performance improvements over both Gurobi and previous models.
- [31] arXiv:2405.05638 (replaced) [pdf, html, other]
-
Title: A Correlation-induced Finite Difference EstimatorSubjects: Methodology (stat.ME); Machine Learning (cs.LG); Numerical Analysis (math.NA); Optimization and Control (math.OC)
Finite difference (FD) approximation is a classic approach to stochastic gradient estimation when only noisy function realizations are available. In this paper, we first provide a sample-driven method via the bootstrap technique to estimate the optimal perturbation, and then propose an efficient FD estimator based on correlated samples at the estimated optimal perturbation. Furthermore, theoretical analyses of both the perturbation estimator and the FD estimator reveal that, {\it surprisingly}, the correlation enables the proposed FD estimator to achieve a reduction in variance and, in some cases, a decrease in bias compared to the traditional optimal FD estimator. Numerical results confirm the efficiency of our estimators and align well with the theory presented, especially in scenarios with small sample sizes. Finally, we apply the estimator to solve derivative-free optimization (DFO) problems, and numerical studies show that DFO problems with 100 dimensions can be effectively solved.