Optimization and Control
New submissions
[ showing up to 2000 entries per page: fewer | more ]
New submissions for Thu, 9 May 24
- [1] arXiv:2405.04618 [pdf, other]
-
Title: Underground Freight Transportation for Package Delivery in Urban EnvironmentsSubjects: Optimization and Control (math.OC)
The use of underground freight transportation (UFT) is gaining attention because of its ability to quickly move freight to locations in urban areas while reducing road traffic and the need for delivery drivers. Since packages are transported through the tunnels by electric motors, the use of tunnels is also environmentally friendly. Unlike other UFT projects, we examine the use of tunnels to transport individual orders, motivated by the last mile delivery of goods from e-commerce providers. The use of UFT for last mile delivery requires more complex network planning than for direct lines that have previously been considered for networks connecting large cities. We introduce a new network design problem based on this delivery model and transform the problem into a fixed charge multicommodity flow problem with additional constraints. We show that this problem, the nd-UFT, is NP-hard, and provide an exact solution method for solving large-scale instances. Our solution approach exploits the combinatorial sub-structures of the problem in a cutting planes fashion, significantly reducing the time to find optimal solutions on most instances compared to a MIP. We provide computational results for real urban environments to build a set of insights into the structure of such networks and evaluate the benefits of such systems. We see that a budget of only 45 miles of tunnel can remove 42% of packages off the roads in Chicago and 32% in New York City. We estimate the fixed and operational costs for implementing UFT systems and break them down into a per package cost. Our estimates indicate over a 40% savings from using a UFT over traditional delivery models. This indicates that UFT systems for last mile delivery are a promising area for future research.
- [2] arXiv:2405.04628 [pdf, other]
-
Title: Wasserstein Proximal Coordinate Gradient AlgorithmsSubjects: Optimization and Control (math.OC); Statistics Theory (math.ST)
Motivated by approximation Bayesian computation using mean-field variational approximation and the computation of equilibrium in multi-species systems with cross-interaction, this paper investigates the composite geodesically convex optimization problem over multiple distributions. The objective functional under consideration is composed of a convex potential energy on a product of Wasserstein spaces and a sum of convex self-interaction and internal energies associated with each distribution. To efficiently solve this problem, we introduce the Wasserstein Proximal Coordinate Gradient (WPCG) algorithms with parallel, sequential and random update schemes. Under a quadratic growth (QC) condition that is weaker than the usual strong convexity requirement on the objective functional, we show that WPCG converges exponentially fast to the unique global optimum. In the absence of the QG condition, WPCG is still demonstrated to converge to the global optimal solution, albeit at a slower polynomial rate. Numerical results for both motivating examples are consistent with our theoretical findings.
- [3] arXiv:2405.04688 [pdf, ps, other]
-
Title: On existence of solutions to non-convex minimization problemsSubjects: Optimization and Control (math.OC)
We provide new sufficient conditions for the finiteness of the optimal value and existence of solutions to a general problem of minimizing a proper closed function over a nonempty closed set. The conditions require an asymptotically bounded decay of a function, a relaxation of p-supercoercivity, and a certain relation for the asymptotic cone of the constraint set and the asymptotic function of the objective function. Our analysis combines these conditions with a regularization technique. We refine the notion of retractive directions of a set, extend its definition to functions, and establish some basic relations for such directions for both sets and functions. Using these tools, we provide existence of solutions results that generalize many of the results in the literature for both non-convex and convex problems.
- [4] arXiv:2405.04785 [pdf, ps, other]
-
Title: Dynamic Workforce Scheduling and Relocation in Hyperconnected Parcel Logistic HubsSubjects: Optimization and Control (math.OC)
With the development of e-commerce during the Covid-19 pandemic, one of the major challenges for many parcel logistics companies is to design reliable and flexible scheduling algorithms to meet uncertainties of parcel arrivals as well as manpower supplies in logistic hubs, especially for those depending on workforce greatly. Currently, most labor scheduling is periodic and limited to single facility, thus the number of required workers in each hub is constrained to meet the peak demand with high variance. We approach this challenge, recognizing that not only workforce schedules but also working locations could be dynamically optimized by developing a dynamic workforce scheduling and relocation system, fed from updated data with sensors and dynamically updated hub arrival demand predictions. In this paper, we propose novel reactive scheduling heuristics to dynamically match predicted arrivals with shifts at hyperconnected parcel logistics hubs. Dynamic scheduling and allocation mechanisms are carried out dynamically during delivery periods to spatiotemporally adjust the available workforce. We also include penalty costs to keep parcels sorted in time and scheduling adjustments are made in advance to allow sufficient time for crew planning. To assess the proposed methods, we conduct comprehensive case studies based on real-world parcel logistic networks of a logistic company in China. The results show that our proposed approach can significantly outperform traditional workforce scheduling strategies in hubs with limited computation time.
- [5] arXiv:2405.04805 [pdf, other]
-
Title: Variational analysis of unbounded and discontinuous generalized eigenvalue functions with application to topology optimizationComments: 28 pages, 9 figuresSubjects: Optimization and Control (math.OC)
The maximum (or minimum) generalized eigenvalue of symmetric positive semidefinite matrices that depend on optimization variables often appears as objective or constraint functions in structural topology optimization when we consider robustness, vibration, and buckling. It can be an unbounded or discontinuous function where matrices become singular (where a topological change of the structural design occurs). Based on variational analysis, we redefine the maximum (and minimum) generalized eigenvalue function as an extended real-valued function and propose a real-valued continuous approximation of it. Then, we show that the proposed approximation epi-converges to the original redefined function, which justifies solving problems with the approximation instead. We consider two specific topology optimization problems: robust compliance optimization and eigenfrequency optimization and conduct simple numerical experiments.
- [6] arXiv:2405.04808 [pdf, ps, other]
-
Title: Multigrid-in-time preconditioners for KKT systemsSubjects: Optimization and Control (math.OC)
We develop multigrid-in-time preconditioners for Karush-Kuhn-Tucker (KKT) systems that arise in the solution of time-dependent optimization problems. We focus on a specific instance of KKT systems, known as augmented systems, which underpin the composite-step sequential quadratic programming framework [1]. To enable time-domain decomposition, our approach introduces virtual state variables and continuity constraints at each discrete time interval. The virtual state variables not only facilitate a decoupling in time but also give rise to fixed-point iterations that aid the solution of KKT systems. These fixed-point schemes can be used either as preconditioners for Krylov subspace methods or as smoothers for multigrid-in-time schemes. For the latter, we develop a block-Jacobi scheme that parallelizes trivially in the time domain. To complete the multigrid construction, we use simple prolongation and restriction operators based on geometric multigrid ideas, and a coarse-grid solver based on a GMRES iteration preconditioned with the symmetric block Gauss-Seidel scheme. We present two optimal control examples, involving the viscous Burgers' and van der Pol oscillator equations, respectively, and demonstrate algorithmic scalability.
- [7] arXiv:2405.04930 [pdf, other]
-
Title: Minimal time of the pointwise controllability for degenerate singular operators and related numerical results via B-splinesSubjects: Optimization and Control (math.OC)
The goal of this paper is to analyze the pointwise controllability properties of a one-dimensional degenerate/singular equation. We prove the conditions that characterize approximate and null controllability. Besides, a numerical simulation based on B-splines will be provided, in which the state $u$ and the control function $h$ are represented in terms of B-spline basis functions. The numerical results obtained match the theoretical ones.
- [8] arXiv:2405.04987 [pdf, other]
-
Title: The Riemannian geometry of Sinkhorn divergencesComments: 52 pages, 6 figuresSubjects: Optimization and Control (math.OC); Metric Geometry (math.MG)
We propose a new metric between probability measures on a compact metric space that mirrors the Riemannian manifold-like structure of quadratic optimal transport but includes entropic regularization. Its metric tensor is given by the Hessian of the Sinkhorn divergence, a debiased variant of entropic optimal transport. We precisely identify the tangent space it induces, which turns out to be related to a Reproducing Kernel Hilbert Space (RKHS). As usual in Riemannian geometry, the distance is built by looking for shortest paths. We prove that our distance is geodesic, metrizes the weak-star topology, and is equivalent to a RKHS norm. Still it retains the geometric flavor of optimal transport: as a paradigmatic example, translations are geodesics for the quadratic cost on $\mathbb{R}^d$. We also show two negative results on the Sinkhorn divergence that may be of independent interest: that it is not jointly convex, and that its square root is not a distance because it fails to satisfy the triangle inequality.
- [9] arXiv:2405.05124 [pdf, other]
-
Title: A Gauss-Newton Method for ODE Optimal Tracking ControlSubjects: Optimization and Control (math.OC)
This paper introduces and analyses a continuous optimization approach to solve optimal control problems involving ordinary differential equations (ODEs) and tracking type objectives. Our aim is to determine control or input functions, and potentially uncertain model parameters, for a dynamical system described by an ODE. We establish the mathematical framework and define the optimal control problem with a tracking functional, incorporating regularization terms and box-constraints for model parameters and input functions. Treating the problem as an infinite-dimensional optimization problem, we employ a Gauss-Newton method within a suitable function space framework. This leads to an iterative process where, at each step, we solve a linearization of the problem by considering a linear surrogate model around the current solution estimate. The resulting linear auxiliary problem resembles a linear-quadratic ODE optimal tracking control problem, which we tackle using either a gradient descent method in function spaces or a Riccati-based approach. Finally, we present and analyze the efficacy of our method through numerical experiments.
Cross-lists for Thu, 9 May 24
- [10] arXiv:2405.04710 (cross-list from cs.LG) [pdf, other]
-
Title: Untangling Lariats: Subgradient Following of Variationally Penalized ObjectivesSubjects: Machine Learning (cs.LG); Optimization and Control (math.OC)
We describe a novel subgradient following apparatus for calculating the optimum of convex problems with variational penalties. In this setting, we receive a sequence $y_i,\ldots,y_n$ and seek a smooth sequence $x_1,\ldots,x_n$. The smooth sequence attains the minimum Bregman divergence to an input sequence with additive variational penalties in the general form of $\sum_i g_i(x_{i+1}-x_i)$. We derive, as special cases of our apparatus, known algorithms for the fused lasso and isotonic regression. Our approach also facilitates new variational penalties such as non-smooth barrier functions. We next derive and analyze multivariate problems in which $\mathbf{x}_i,\mathbf{y}_i\in\mathbb{R}^d$ and variational penalties that depend on $\|\mathbf{x}_{i+1}-\mathbf{x}_i\|$. The norms we consider are $\ell_2$ and $\ell_\infty$ which promote group sparsity. Last but not least, we derive a lattice-based subgradient following for variational penalties characterized through the output of arbitrary convolutional filters. This paradigm yields efficient solvers for problems in which sparse high-order discrete derivatives such as acceleration and jerk are desirable.
- [11] arXiv:2405.05098 (cross-list from math.NA) [pdf, other]
-
Title: Energy stable gradient flow schemes for shape and topology optimization in Navier-Stokes flowsSubjects: Numerical Analysis (math.NA); Optimization and Control (math.OC); Fluid Dynamics (physics.flu-dyn)
We study topology optimization governed by the incompressible Navier-Stokes flows using a phase field model. Novel stabilized semi-implicit schemes for the gradient flows of Allen-Cahn and Cahn-Hilliard types are proposed for solving the resulting optimal control problem. Unconditional energy stability is shown for the gradient flow schemes in continuous and discrete spaces. Numerical experiments of computational fluid dynamics in 2d and 3d show the effectiveness and robustness of the optimization algorithms proposed.
- [12] arXiv:2405.05158 (cross-list from math.NA) [pdf, ps, other]
-
Title: Analysis of the SQP Method for Hyperbolic PDE-Constrained Optimization in Acoustic Full Waveform InversionSubjects: Numerical Analysis (math.NA); Optimization and Control (math.OC)
In this paper, the SQP method applied to a hyperbolic PDE-constrained optimization problem is considered. The model arises from the acoustic full waveform inversion in the time domain. The analysis is mainly challenging due to the involved hyperbolicity and second-order bilinear structure. This notorious character leads to an undesired effect of loss of regularity in the SQP method, calling for a substantial extension of developed parabolic techniques. We propose and analyze a novel strategy for the well-posedness and convergence analysis based on the use of a smooth-in-time initial condition, a tailored self-mapping operator, and a two-step estimation process along with Stampacchia's method for second-order wave equations. Our final theoretical result is the R-superlinear convergence of the SQP method.
- [13] arXiv:2405.05236 (cross-list from eess.SY) [pdf, ps, other]
-
Title: Stability and Performance Analysis of Discrete-Time ReLU Recurrent Neural NetworksSubjects: Systems and Control (eess.SY); Machine Learning (cs.LG); Optimization and Control (math.OC)
This paper presents sufficient conditions for the stability and $\ell_2$-gain performance of recurrent neural networks (RNNs) with ReLU activation functions. These conditions are derived by combining Lyapunov/dissipativity theory with Quadratic Constraints (QCs) satisfied by repeated ReLUs. We write a general class of QCs for repeated RELUs using known properties for the scalar ReLU. Our stability and performance condition uses these QCs along with a "lifted" representation for the ReLU RNN. We show that the positive homogeneity property satisfied by a scalar ReLU does not expand the class of QCs for the repeated ReLU. We present examples to demonstrate the stability / performance condition and study the effect of the lifting horizon.
Replacements for Thu, 9 May 24
- [14] arXiv:2304.07106 (replaced) [pdf, ps, other]
-
Title: Extremum Seeking Nonlinear Regulator with Concurrent Uncertainties in Exosystems and Control DirectionsComments: 11 pages, 7 figuresSubjects: Optimization and Control (math.OC); Systems and Control (eess.SY); Adaptation and Self-Organizing Systems (nlin.AO); Chaotic Dynamics (nlin.CD)
- [15] arXiv:2308.01360 (replaced) [pdf, other]
-
Title: On Second-Order Cone FunctionsComments: 21 pages, 5 figuresSubjects: Optimization and Control (math.OC)
- [16] arXiv:2308.11925 (replaced) [pdf, other]
-
Title: Solving Elliptic Optimal Control Problems via Neural Networks and Optimality SystemComments: 26 pagesSubjects: Optimization and Control (math.OC); Machine Learning (cs.LG); Numerical Analysis (math.NA)
- [17] arXiv:2310.14792 (replaced) [pdf, other]
-
Title: Evaluating synthetic fuel production: A case study on the influence of electricity and CO2 price variationsSubjects: Optimization and Control (math.OC)
- [18] arXiv:2311.02426 (replaced) [pdf, other]
-
Title: Online Long-run Constrained OptimizationComments: Under review by IEEE Transactions on Automatic Control (Technical Note)Subjects: Optimization and Control (math.OC); Machine Learning (cs.LG)
- [19] arXiv:2403.04886 (replaced) [pdf, other]
-
Title: Exponential Lower Bounds for Many Pivot Rules for the Simplex MethodAuthors: Alexander E. BlackComments: 14 pages, 4 figures, changed name from previous versionSubjects: Optimization and Control (math.OC); Combinatorics (math.CO)
- [20] arXiv:2403.19324 (replaced) [pdf, other]
-
Title: Rapid nonlinear convex guidance using a monomial methodComments: 34 pages, 16 figuresSubjects: Optimization and Control (math.OC); Systems and Control (eess.SY)
- [21] arXiv:2405.01788 (replaced) [pdf, other]
-
Title: Markov Chain Monte Carlo for Koopman-based Optimal Control: Technical ReportSubjects: Optimization and Control (math.OC)
- [22] arXiv:2208.03941 (replaced) [pdf, other]
-
Title: Provable Acceleration of Nesterov's Accelerated Gradient Method over Heavy Ball Method in Training Over-Parameterized Neural NetworksComments: 16 pages, accepted to the 33rd International Joint Conference on Artificial Intelligence, IJCAI 2024 (Main) TrackSubjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Optimization and Control (math.OC)
- [23] arXiv:2303.03295 (replaced) [pdf, other]
-
Title: Probabilistic Game-Theoretic Traffic RoutingSubjects: Systems and Control (eess.SY); Optimization and Control (math.OC)
- [24] arXiv:2303.10665 (replaced) [pdf, other]
-
Title: Major-Minor Mean Field Multi-Agent Reinforcement LearningComments: Accepted to ICML 2024Subjects: Machine Learning (cs.LG); Multiagent Systems (cs.MA); Optimization and Control (math.OC)
- [25] arXiv:2310.06771 (replaced) [pdf, other]
-
Title: Correlated Noise Provably Beats Independent Noise for Differentially Private LearningAuthors: Christopher A. Choquette-Choo, Krishnamurthy Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, Abhradeep ThakurtaComments: Christopher A. Choquette-Choo, Krishnamurthy Dvijotham, and Krishna Pillutla contributed equallyJournal-ref: ICLR 2024Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Cryptography and Security (cs.CR); Optimization and Control (math.OC)
- [26] arXiv:2310.16985 (replaced) [pdf, other]
-
Title: TinyMPC: Model-Predictive Control on Resource-Constrained MicrocontrollersComments: Accepted at ICRA 2024. Publicly available at this https URLSubjects: Robotics (cs.RO); Systems and Control (eess.SY); Optimization and Control (math.OC)
- [27] arXiv:2403.13237 (replaced) [pdf, ps, other]
-
Title: Graph Attention Network-based Block Propagation with Optimal AoI and Reputation in Web 3.0Authors: Jiana Liao, Jinbo Wen, Jiawen Kang, Changyan Yi, Yang Zhang, Yutao Jiao, Dusit Niyato, Dong In Kim, Shengli XieSubjects: Cryptography and Security (cs.CR); Optimization and Control (math.OC)
- [28] arXiv:2404.01714 (replaced) [pdf, other]
-
Title: Conjugate-Gradient-like Based Adaptive Moment Estimation Optimization Algorithm for Deep LearningComments: 32 pages, 13 figuresSubjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Computer Vision and Pattern Recognition (cs.CV); Optimization and Control (math.OC)
[ showing up to 2000 entries per page: fewer | more ]
Disable MathJax (What is MathJax?)
Links to: arXiv, form interface, find, math, recent, 2405, contact, help (Access key information)