Peer Revenue Publish or profit

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Mathematics Optimization and Control

math.OC Watch Optimization and Control (sign in to use)

Thursday 8 October

Optimization and Control

Spatiotemporal Response Decay for Near-Optimal Distributed LQR via System Level Synthesis

Distributed control requires choosing how far information travels and how long it is retained. For networked linear quadratic regulation (LQR), we use System Level Synthesis to bound these resources for a specified performance loss per node relative to centralized control. For locally coupled systems under uniform regularity assumptions, including stabilizability and detectability, we prove that the centralized optimal state and input responses to disturbance impulses satisfy exponential decay bounds in both time and spatial distance. On networks with polynomial neighborhood growth, sufficient communication ranges and memory horizons grow logarithmically with the inverse tolerance, independently of network size. Truncating these responses gives local finite-memory filters with stability and performance guarantees under a computable small-gain condition. Under an additional uniform local feedback condition, we also obtain controllers that confine nominal disturbance effects in space and eliminate them in finite time. Numerical experiments illustrate how performance and disturbance containment requirements guide architecture selection.
Read the full abstract

Optimization and Control

Matching the Lower Bounds: Stochastic Contracting Cubic Newton and Its Optimal Acceleration

We study second-order methods for convex stochastic optimization, where gradients and Hessians are available only through stochastic estimates with variances $\sigma_1^2$ and $\sigma_2^2$, respectively. First, we propose the Stochastic Contracting Cubic Newton method. At each iteration, it minimizes a cubic model with additional quadratic regularization and then contracts the step toward the current point. After $T$ iterations, the method achieves the expected convergence rate $\mathcal{O}(\sigma_1/\sqrt{T}+\sigma_2/T+1/T^2)$. Building on this construction, we develop an accelerated variant achieving $\mathcal{O}(\sigma_1/\sqrt{T}+\sigma_2/T^2+1/T^{7/2})$, matching the known lower bounds of Agafonov et al. (2024) in all three terms.
Read the full abstract

All authors Artem Agafonov, Aslan Ashabokov, Dmitry Kamzolov, Alexander D'yakonov, Alexander Gasnikov, Martin Takáč

Optimization and Control · Cross-listed from math.AP

Continuity and monotonicity of weighted perimeters of convex bodies

We investigate weighted perimeters of convex bodies in $\mathbb{R}^n$. Our main result states that the weighted perimeter is continuous with respect to the Hausdorff metric for every radial weight function. We also establish monotonicity under inclusion under suitable assumptions on the radial weight, and show that these assumptions are sharp. These results are applied to show the existence of minimizers for a shape optimization problem.
Read the full abstract

Optimization and Control

Randomized Transport Maps for Model-Free Policy-Gradient Mean-Field Control

We develop a model-free policy gradient method for discrete-time mean-field control (MFC). In MFC, the policy affects the objective both through the controlled dynamics and through the population distribution. Standard REINFORCE estimators capture the first effect but not the second. We introduce Transport REINFORCE, a transport map-based approach that perturbs a suitable transformation of the population distribution to estimate this missing mean-field contribution. The method applies to both finite and continuous state spaces. In finite state spaces, we perturb the population distribution directly on the probability simplex through a convex combination of the current population weights and random weights. In continuous state spaces, we project the population distribution onto the manifold of Gaussian mixtures, and then randomize it via a transport map that ensures the perturbed law remains within this manifold. We prove consistency of the perturbed objective and gradient as the perturbation vanishes, and derive bias and mean-square error bounds for the resulting sample-based gradient estimator. Numerical experiments on several MFC benchmarks show that Transport REINFORCE improves over standard REINFORCE.
Read the full abstract

All authors Adonis Jamal, Samy Mekkaoui, Yadh Hafsi, Huyên Pham

Optimization and Control · Cross-listed from math.AP

Boundary Control of Two-dimensional Point-Vortex Systems

In this article, we investigate the boundary controllability of finite point-vortex systems in bounded multiply connected planar Lipschitz domains. The controls are applied locally on an arbitrary nonempty relatively open subset of the boundary. Zero incoming vorticity is assumed at the inflow part of the boundary. For time-dependent controls, we prove exact trajectory controllability along arbitrary prescribed collision-free vortex paths remaining away from the boundary. For stationary controls, we prove exact endpoint controllability associated with mutually disjoint real-analytic arcs. The proofs rely on harmonic interpolation, localized Runge approximation, and an implicit-function argument. The optimal control minimizing the length of trajectories is also studied. We prove the nonexistence of minimizers within classes of slightly smooth controls, and establish existence when the control time and the size of the control are penalized.
Read the full abstract

Optimization and Control

Stochastic Gradient Descent for Traffic and Pedestrian Models via Neural Networks and Parameter Identification

We study the calibration of interaction-driven ordinary differential equation (ODE) models for traffic and pedestrian dynamics by means of optimal control and stochastic gradient descent. The interaction forces are either prescribed by classical physics-inspired laws, whose parameters are identified from trajectory data, or represented by feed-forward neural networks whose weights act as control variables. For the neural-network-driven particle system we prove well-posedness of the state equation, Lipschitz-continuous dependence of the trajectories on the initial data and on the network parameters, existence of an optimal parameter set, and a first-order optimality system with an explicit backward adjoint equation. The resulting adjoint representation of the gradient is combined with a projected mini-batch ADADELTA scheme, so that each gradient evaluation requires one forward and one backward ODE solve, independently of the number of network parameters. Building on this framework we propose two new second-order models, one for vehicular traffic and one for crowds, that combine goal-seeking, learned interaction, repulsion-alignment or dissipation, and external control terms. Numerical experiments compare six models (a follow-the-leader model of Lighthill-Whitham-Richards type, a neural-network traffic model, the social force model, a neural-network pedestrian model, and the two new models) in terms of cost reduction and root-mean-square trajectory deviation. The neural-network pedestrian model achieves the lowest final cost, while the richer second-order models trade a higher calibration cost for individualised, behaviourally interpretable dynamics. We conclude by discussing limitations and directions for incorporating richer behavioural and environmental effects.
Read the full abstract

Optimization and Control

On error bounds and noncritical Lagrange multipliers

Critical Lagrange multipliers are known to be responsible for the potentially slow convergence of Newton-type methods, and noncriticality of a given multiplier has been tied to an error bound which estimates the distance of a primal-dual pair associated with a perturbed problem to the primal solution and the multiplier set of the unperturbed one, and is decisive for a local convergence analysis. We investigate this relation in an abstract setting where merely a set-valued mapping assigning primal-dual pairs to a parameter is available, and characterize the error bound of interest in terms of noncriticality of the underlying multiplier and two calmness-type properties of the associated multiplier mapping, one of which is a novel weak inner calmness in the fuzzy sense. No structural assumptions on the underlying problem are needed for that, and the two calmness-type conditions are not only sufficient but also necessary. Afterwards, we specify these findings for composite optimization problems. Whenever the subdifferential of the outer function is a polyhedral mapping, both conditions hold automatically, which explains the equivalence of noncriticality and the error bound observed in the polyhedral setting. Whenever the outer function is $C^2$-decomposable, they are secured by calmness of a restricted multiplier mapping together with a closedness condition, which recovers and extends the known characterization for $C^2$-cone reducible constraint systems.
Read the full abstract

Optimization and Control · Cross-listed from cs.DS

A QPTAS for Stochastic Scheduling of Bernoulli Jobs

We study the classical problem of scheduling jobs with random processing times on $m$ identical machines to minimize the expected sum of completion times, for Bernoulli jobs: job $j$ takes time $p_j$ with probability $q_j$ and time $0$ otherwise, and its outcome is revealed when it starts. The benchmark is an optimal adaptive policy. We give a quasi-polynomial-time approximation scheme for every number of machines. Previously, quasi-polynomial time was known to give an $O(\log N)$-approximation, and approximation schemes were known only for a constant number of distinct sizes. The scheme rests on a simple observation: it suffices to round the times at which machines become free, rather than the times at which jobs start, to a grid whose width is proportional to the job size, and an optimal policy stretched by a factor close to one already respects such grids. We also show that every policy that fixes the order of the jobs in advance loses a factor $\Omega(\log N)$, already on two machines, so a constant factor requires adapting the order to the observed outcomes. Further results include a polynomial-time adaptive rule with ratio $\min\{m,1+\sum_j q_j\}$, a simpler approximation scheme for a constant number of sizes, and #P-hardness of computing the optimal expected cost on two machines.
Read the full abstract

Optimization and Control · Cross-listed from cs.LG

Rare Gate Disagreements Can Limit Plasticity: When Gradient Flow Mispredicts Finite-Batch SGD

Population gradient flow is a common tool for reasoning about how neural networks adapt, including after pretraining. We show that it can mispredict finite-batch stochastic gradient descent (SGD) qualitatively, and we trace the discrepancy to a specific mechanism. In a two-unit ReLU regression, a source task drives the two neurons toward positive proportionality and a target task rewards separating them. After source training for time $T$, gradient flow recovers on the target in time linear in $T$. Online SGD with batch size $b$ and step size $\eta$ in both phases instead fails with high probability throughout a horizon of order $e^{c/\eta}$ once $T \gtrsim \log(b/\eta)$, uniformly on an explicit set of initializations with Gaussian probability above one percent. For each fixed $T$, small-step SGD still recovers, so the failure requires the joint limit of small steps and long pretraining. At the target clone, the population instability is carried entirely by inputs on which the two ReLU gates disagree. For units at angle $\delta$ these inputs form a wedge of probability $\delta/\pi$, and weight decay shrinks the angle exponentially during pretraining. On every other input both units receive the same random linear update, which contracts their separation in conditional expectation. Bounding the cumulative probability of sampling the wedge along the exact online recursion, without a diffusion approximation, shows that recovery with fixed probability from an identical source-gradient-flow checkpoint, within $e^{c/\eta}$ updates, requires $Nb \gtrsim e^{\lambda T}$ target samples and batch size $b \gtrsim \eta e^{\lambda T}$, where $N$ counts updates and $\lambda$ is the weight decay. In simulations, recovery is approximately a function of the disagreement budget $b\delta/\eta$ and saturates in the horizon.
Read the full abstract

All authors Ruoyu Zhao, Mingxuan Zhang, Jianbo Dai, Jiaqi Wu, Chenyu Zhu, Tong Che

Optimization and Control

Nonlinear differential-algebraic systems with dissipative port-Hamiltonian structure

Different representations of nonlinear dissipative Hamiltonian and port-Hamiltonian (pH) differential-algebraic equations (DAE) systems are derived and compared. Using global geometric and algebraic points of view, including singular Lagrange and Dirac structures, as well as Morse families and their skew counterparts, constraints are incorporated in the models. The results are illustrated specifically with constrained mechanical systems using kinematic and geometric constraints. The relation between the different representations is studied and in particular the conversion of Lagrange into Dirac algebraic constraints and vice versa is discussed. To incorporate dissipation also maximally monotone structures are studied.
Read the full abstract

Optimization and Control

Dimension-Adaptive Accuracy Certificates for Convex Optimization

Many convex optimization methods use affine lower models to certify that a candidate solution is near optimal. Keeping full gradients can be costly when the informative directions occupy a small, initially unknown subspace. We develop accuracy certificates that store projected affine minorants together with bounds on the discarded components. The certificates remain valid as the subspace, queries, and certificate weights are chosen adaptively. For quadratic regularization, we derive an exact correction that accounts for when each discarded component was recorded, and a compact problem for selecting certificate weights. We also characterize the strongest lower bound supported by the compressed records when an ambient direction remains unused. The certificates can be used as stopping criteria for methods that provide valid affine minorants. We also analyze an adaptive cutting-plane construction whose oracle bound depends on the discovered dimension. Experiments on kernel SVM and $\nu$-SVR problems show reduced certificate communication and stopping times under an emulated bandwidth constraint.
Read the full abstract

Optimization and Control

Inertial parameterized Douglas-Rachford for generalized DC programming problems

We propose two new Douglas-Rachford type algorithms for solving generalized DC programming problems. More precisely, we deal with the minimization of the sum of two possibly nonsmooth convex functions from which a Fréchet differentiable convex function with a Lipschitz continuous gradient is subtracted, in a Hilbertian framework. We introduce an inertial Douglas-Rachford DC algorithm and a parametrized inertial Douglas-Rachford DC algorithm for solving optimization problems of this type, and study their convergence behavior. Numerical experiments illustrate the behavior of the proposed algorithms when solving sparse recovery and robust classification problems, highlighting their superior performance in comparison with their state-of-the-art counterparts.
Read the full abstract

Optimization and Control

Accelerated Proximal Gradient Method for Non-Strongly Convex Time-Varying Optimization

This paper studies time-varying composite optimization problems with convex but not necessarily strongly convex objective functions, on compact domains and with bounded temporal variability. As a baseline, we first analyze the time-varying proximal gradient (TV-PG) method. We show that its asymptotic function value gap is bounded by $O(\delta^{1/2})$ as $\delta\to0$, where $\delta$ measures the temporal variability of the objective function. This dependence on $\delta$ is tight in the worst case for TV-PG. Our main contribution is a time-varying accelerated proximal gradient method that improves the asymptotic upper bound on the function value gap to $O(\delta^{2/3})$. The method builds on a novel acceleration scheme whose momentum parameter is determined by the current iterates, with no explicit dependence on the iteration index. We establish the bounds for both the baseline and accelerated methods through a unified analysis based on potential functions. Numerical experiments on a synthetic problem and autoregression problems with real-world datasets demonstrate the tracking performance of the proposed algorithm.
Read the full abstract

Optimization and Control

Adaptive relaxed CQ algorithm with dynamic stepsizes for the split feasibility problem

In this paper, we propose a relaxed CQ algorithm with dynamic stepsizes for the split feasibility problem (SFP), where the relaxed parameters are chosen adaptively. We establish the weak convergence of the proposed algorithm under standard assumptions and further derive its linear convergence under the bounded linear regularity property of the SFP. Numerical results on LASSO problem demonstrate that the adaptively over-relaxed CQ algorithm with dynamic stepsizes outperforms the dynamic CQ algorithm proposed in [10].
Read the full abstract

Optimization and Control · Cross-listed from cs.LG

Deflating the Hessian: Rank-4 W4A4 Quantization for Multimodal Diffusion Transformers

In diffusion transformers, low-rank branches can mitigate 4-bit weight–activation (W4A4) post-training quantization (PTQ) loss by decomposing each weight into a low-bit residual and a high-precision low-rank component. Existing low-rank PTQ approaches, however, either optimize low-rank compensation and residual quantization separately, often requiring higher ranks, or rely on second-order weight updates without explicitly modeling activation quantization error, which becomes particularly pronounced under 4-bit quantization. To address these limitations, we present HSVDQuant, a unified framework modeling low-rank-assisted W4A4 PTQ as a coupled calibration problem and deriving optimization-based solvers from the joint objective. Eliminating the output-side low-rank factor yields a deflated Hessian that discounts residual errors already captured by the low-rank component, while an activation-noise surrogate is incorporated to suppress activation quantization error. Across five diffusion backbones, rank-4 HSVDQuant consistently outperforms rank-4 SVDQuant in PSNR and LPIPS. It further surpasses rank-32 SVDQuant on SANA-1.6B, FLUX.1-schnell, and FLUX.1-dev with an $8\times$ smaller rank and up to $6.25\times$ faster quantization. Furthermore, on the Qwen3-8B LLM, rank-4 HSVDQuant improves MMLU accuracy from 61.50% to 68.17% over rank-32 SVDQuant. Overall, HSVDQuant achieves better W4A4 performance with substantially lower rank and quantization cost.
Read the full abstract

Optimization and Control · Cross-listed from cs.LG

From Geometry to Generalization: Why Row Normalization Can Beat Adam and Muon

Different optimizers can fit the same training data while selecting classifiers with substantially different geometries, but whether this difference provably affects population performance remains unclear. We show that row-wise normalization can achieve strictly higher population accuracy than full-batch Adam, a proxy for random-reshuffling Adam, and exact-SVD Muon in high-dimensional multiclass classification. Under an isotropic Gaussian-cloud data model, this advantage arises because row normalization's class-wise Euclidean geometry asymptotically preserves the population decision-boundary directions, whereas Adam's coordinate-wise geometry and Muon's spectral geometry introduce nonvanishing distortions. Beyond isotropy, the advantage persists for full-batch training on class means with independently oriented class-mean and test-noise covariances. It holds for power-law spectra with class-mean exponent below one, even under heavily anisotropic test noise. When both covariances are diagonal and sufficiently close, the advantage over Adam can reverse, while applying the same random rotation to both restores it by changing only their alignment with Adam's coordinate axes. Synthetic and last-layer language-model experiments support the predicted advantage.
Read the full abstract

Optimization and Control

Nonminimizing Attractors of Stochastic Subgradient Methods on Semialgebraic Functions

We disprove a conjecture of Davis, Drusvyatskiy, and Jiang (2026) that subdifferential regularity can be removed from the generic guarantee of convergence to local minimizers for stochastic subgradient methods. We construct a globally Lipschitz, coercive, semialgebraic function in two dimensions for which the method converges to a nonminimizing Clarke critical point. For suitable power-law stepsizes, this convergence holds for open sets of initial points and linear tilts of the objective, uniformly over all perturbation sequences within a prescribed bound.
Read the full abstract

Optimization and Control

Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations

We develop MIQCR-FR, a framework for exact convex reformulation from facially reduced semidefinite relaxations of equality-constrained binary quadratic problems. Standard mixed-integer quadratic convex reformulation (MIQCR) uses dual multipliers of the original relaxation. Facial reduction (FR) reduces the semidefinite matrix order, but recovery of the original dual multipliers is not guaranteed in general. For this class of problems, we identify how retaining the linear equalities and their products with each binary variable enables this recovery. An established dual recovery formula gives an explicit extension of every feasible solution of the reduced dual to the original dual, preserving its bound. For approximate multiplier estimates, we give a spectral shift restoring dual feasibility and two constructions optimizing different bounds within a restricted multiplier family. Maximizing the dual bound yields a trust-region subproblem; maximizing the continuous MIQCR bound requires only a reduced eigenvalue calculation. The latter construction enforces convexity directly, rather than full dual feasibility. We implement it using multiplier estimates from the alternating direction method of multipliers (ADMM). On 431 instances from six problem families, the complete method certifies 296 optima, compared with 156 for the conic-bundle method MIQCR-CB and 187 for direct Gurobi under a common time budget.
Read the full abstract

Wednesday 7 October

Optimization and Control · Cross-listed from cs.AI

Curating Always-Loaded Context for LLM Agents: A Capacitated Assortment Model with Censored Feedback

At the start of every session, LLM agents load a fixed context file, such as $\texttt{AGENTS.md}$. Each loaded token in the file is charged again in every later round of the session, and these files can degrade performance as they grow in size. However, in practice, human or automated curators usually grow these files by appending. We formulate context curation as a capacitated assortment problem. Instructions consume tokens under a finite attention capacity; adding an instruction never raises the compliance of the others, while retained instructions incur a per-session setup cost. We prove an upper bound on the optimal file size, regardless of the number of available candidate instructions, and that appending every instruction with positive standalone value can be arbitrarily worse in net value than selecting an optimal subset. A token budget also limits the loss when the token price is underestimated. We then examine what can be learned from past sessions and how this information can guide decisions to add or remove instructions. Feedback is inherently censored: the benefits and harms of loaded instructions are observable, whereas missing instructions generate feedback only when their absence causes harm. In this setting, we show that deleting instructions ignored by agents can inevitably remove helpful ones. We characterize how much evidence should be collected before adding an instruction. Besides, we bound regret when human reviewers can inspect only a limited number of edits per period. Empirical experiments further show that irrelevant rules drawn from real context files reduce language-model compliance.
Read the full abstract

Optimization and Control · Cross-listed from eess.SY

Constructive Safety-Critical Control for a Class of Underactuated Systems: A Hierarchical Approach

Underactuated systems with nontrivial geometry are abundant in practical robotic problems. However, little is known about constructive safety-critical control design in the presence of underactuation. In this work, we provide a constructive framework for synthesizing safe control architectures and control barrier functions for a class of quadrotor-like underactuated systems. By studying the geometry of their underactuation, we characterize when these systems have natural layered architectures useful for safety-critical control design. Using these architectures, we devise a constructive, hierarchical CBF synthesis procedure and provide conditions under which it succeeds.
Read the full abstract

Optimization and Control · Cross-listed from cs.LG

Budgeted Multi-Source Counterfactual Annotation for Off-Policy Evaluation

Off-policy evaluation (OPE) estimates the value of a target policy from logged data, but limited behavior-policy coverage can force high-variance reweighting or reward-model extrapolation. Counterfactual annotations can add evidence about unobserved actions, yet practical sources, including domain experts and large language models (LLMs), may be costly, biased, or noisy. We study budgeted acquisition of such annotations for contextual-bandit OPE. Given source-specific costs and error profiles, we formulate an integer allocation problem over context-action pairs and annotation sources to minimize the component of estimator variance that depends on the annotation plan. We characterize when annotations are valuable through a first-annotation threshold and local annotation-value regimes. For the coupled multi-source problem, we develop a majorization-minimization algorithm with dynamic-programming subroutines that monotonically improves the objective. Experiments in synthetic clinical and LLM-annotated education bandits show that our allocation method reduces fixed-profile mean squared error (MSE) by 20.58% and 10.77%, respectively, relative to no annotation.
Read the full abstract

All authors Biao Xiang, Ali Eshragh, Yuexing Li, Kai Wang

Optimization and Control

Optimal Control of Dynamic Gas Networks Using Gaussian Processes with Chance-Constraint Reformulation

Natural gas networks must accommodate variable demand and supply while maintaining pressure across pipelines whose stored gas couples operating decisions through time. Probabilistic surrogates can simplify compressor scheduling, but their predictive uncertainty must remain reliable where optimization uses it. We combine direct learning of the minimum pressure margin with assessment at optimizer-selected schedules. Using a warped Gaussian process, we express the posterior pressure requirement as one inequality in its predictive mean and standard deviation. We then parameterize block and Fourier schedules so scalar predictions and analytic derivatives replace trajectory states and time integration in whole-day optimization. In steady state, a surrogate that passes held-out accuracy and coverage checks nevertheless falls below the minimum pressure on 71% of its own dispatches at a nominal 1% tolerance, as the optimizer is drawn to schedules where the margin is overestimated. This diagnostic motivates an enrichment loop that audits selected dispatches against the physics and updates the surrogate by exact conditioning, with fitted quantities held fixed. The loop restores steady-state minimum-pressure risk control at every studied tolerance, with conditioning about four orders of magnitude faster than refitting. In transient operation, we complement this enrichment with empirical threshold calibration to address residual hourly optimism, bringing hourly violation rates closer to their declared tolerances with little compressor work overhead.
Read the full abstract

All authors Taiwo A. Adebiyi, Robert Ferrando, Manuel Garcia, Ruda Zhang, Saif R. Kazi, Kaarthik Sundar

Optimization and Control

Noise-Induced Navigation in Non-convex Domains and Compact Manifolds

In this note, we study the problem of designing a feedback law that globally steers a system to a prescribed target configuration. Even if the system is fully actuated, topological obstructions generally prevent the existence of globally asymptotically stabilizing continuous feedback laws. We revisit this problem in a stochastic setting by allowing noise to enter through the control channels. Using a criterion for asymptotic stability in the large that combines local Lyapunov stability with positive recurrence, we constructively show that one can construct elementary feedback laws that achieve global asymptotic stability in the large, of the target equilibrium point in connected Euclidean domains with obstacles and manifolds without boundary. For Euclidean domains with obstacles, we also show that the method extends naturally to the problem of finding the minimizer of a strongly convex function with non-convex constraints. Numerical experiments illustrate the effectiveness of the approach for Euclidean domains with circular obstacles and the two dimensional sphere. Additionally, we study the role noise strength when there is a non-convex obstacle, in which case the system might show metastability.
Read the full abstract

Optimization and Control

Weakly Quasar-Convex Optimization

This paper introduces the class of weakly quasar-convex functions, a notion that simultaneously generalizes weak convexity (and hence convexity) and quasar-convexity. We establish the theoretical foundation for this new class by developing its basic calculus, deriving characterizations, and systematically investigating its closure and structural properties. Building on these tools, we analyze the proximal point algorithm for minimizing a weakly quasar-convex function under local quadratic growth, proving $Q$-linear convergence of the iterates and $R$-linear convergence of the function values to a global minimizer, with iteration complexity $O(\ln(\varepsilon^{-1}))$; we also give a fully computable, minimizer-free stopping rule via the proximal residual with matching complexity. Finally, we construct a weakly quasar-convex function, satisfying all our standing assumptions, that is neither weakly convex, quasi-convex, star quasi-convex, nor quasar-convex for any modulus, showing that our convergence theory applies to instances outside every prior framework in the literature.
Read the full abstract

Optimization and Control

Integer programming on polytopes of Chvátal rank one is as hard as lattice problems

A rational polyhedron has Chvátal rank at most one if a single round of Chvátal-Gomory cuts yields its integer hull. For such polyhedra, integer feasibility is in NP $\cap$ coNP by a result of Boyd and Pulleyblank from the early 1980s, so it is unlikely to be NP-hard. Whether it is polynomial has remained open since then. We answer this question negatively, under either of two standard assumptions from lattice-based cryptography. First, a polynomial-time algorithm for this problem would solve bounded distance decoding with polynomial factors in deterministic polynomial time, contradicting a widely believed conjecture. Second, assuming the hardness of learning with errors, an average-case analogue of bounded distance decoding, the problem is also hard on average, for an efficiently samplable distribution of polytopes. Both results rest on an elementary sufficient condition: a polyhedron has Chvátal rank at most one if its width is less than one along every row of some unimodular matrix. For our polytopes, such a matrix exists but is hard to find.
Read the full abstract

Optimization and Control · Cross-listed from eess.SY

Deceptive Stochastic Patrolling via Markov Chain Lifting

In this paper we propose lifted Markov Chains (MCs) as a new paradigm for deriving patrol strategies for mobile agents on an environment represented as a graph. Lifted MCs operate on a state space that can be larger than the set of nodes of the graph, and a projection operation maps the MC state to the corresponding node of the graph. We prove bounds on the performance improvement of lifted MCs over non-lifted MCs, where the performance is measured by the Kemeny constant, and show a corresponding monotonicity for the Stackelberg game capture probability and return-time entropy. These bounds yield a result of independent interest that relates the Kemeny constant and the MC conductance for general MCs. We also provide a tractable method for optimizing lifted MCs on general graphs with edge weights encoding travel times. Simulation results on randomly generated and real-world graphs verify that lifted MCs achieve substantial improvements, particularly on sparse graphs.
Read the full abstract

All authors Yohan John, Gilberto Diaz-Garcia, Jason R. Marden, Francesco Bullo

Optimization and Control

Backstepping Stabilization of a Hyperbolic System with a Zero Characteristic Speed

This paper investigates the boundary stabilization of a linear hyperbolic system with a zero characteristic speed. We address a case that cannot be stabilized by proportional boundary feedback and develop a backstepping design for the critical setting where the zero-speed subsystem has no intrinsic dissipation. To this end, we construct a Volterra transformation leading to a nonstandard integro-differential target system. Its asymptotic stability in L2 is established by both the Lyapunov-LaSalle method and a spectral semigroup argument. The backstepping kernel equations are explicitly solved, yielding an explicit boundary feedback law that asymptotically stabilizes the original system. Numerical simulations are provided to illustrate the effectiveness of the proposed control design.
Read the full abstract

Optimization and Control

Strong Legendre regularity and short-time analysis of abnormal curves

We study strictly abnormal sub-Riemannian extremals satisfying the Goh condition and a strong (i.e., coercive) generalized Legendre condition, imposed only at the Lebesgue points of the reference control. We prove that such a control is smooth, that the projected extended Hessian of the end-point map is uniformly coercive on the admissible set of variations for short times, and that the abnormal covector gives a quantitative separation of the end-point of the reference arc from the image of the admissible set under the nonlinear end-point map. As a consequence the reference arc is rigid and, for short times, it is a length minimizer: every admissible curve with the same end-points and no greater length is a reparametrization of the reference arc. In particular, among controls of constant speed the reference control is the unique length minimizer. All the estimates are uniform on the admissible set, and no assumption is made on the dimension of the manifold, on the growth vector of the distribution, or on the corank of the differential of the end-point map.
Read the full abstract

Optimization and Control

Existence and Uniqueness of Viscosity Solutions for Stochastic Hamilton–Jacobi–Bellman Equations

We study stochastic Hamilton–Jacobi–Bellman equations arising from stochastic optimal control problems with random coefficients and possible degenerateness. The viscosity solution is reformulated by using adapted smooth random test fields that touch on stopped space–time neighborhoods almost surely. The state coefficients are predictable, with no continuity assumption on their dependence on the underlying Brownian path. Under linear growth of locally Lipschitz drift and diffusion coefficients, polynomial growth of the running and terminal cost coefficients, and a nonempty separable metric space-valued control set, we show that the value function is the unique viscosity solution in this formulation among adapted continuous fields with square-integrable random polynomial growth bounds. The comparison proof constructs adapted fields from controlled trajectories and spatially shaken conditional values, using a weak semimartingale decomposition and regularization of its positive finite-variation part. In particular, the uniqueness allows for diffusion coefficients being random, degenerate, and depending on time, state, and control, whereas earlier uniqueness results of Qiu [SIAM J. Control Optim. 56 (2018), pp. 3708–3730] and Qiu and Zhang [Ann. Appl. Probab. 33 (2023), pp. 889–930] were obtained under additional structural restrictions on the diffusion coefficient, such as determinism combined with either superparabolicity or independence of the state and controls.
Read the full abstract

Optimization and Control · Cross-listed from eess.SY

Compute-Constrained Safety Filters with Neuromorphic Event Triggering

Safety filters that rely on control barrier function (CBF) quadratic programs (QPs) are typically analyzed under the assumption that the QP is solved instantaneously, although nonzero computation time can render a computed input unsafe by the time it is applied. This paper develops a dual leaky integrate-and-fire (LIF) event-triggered safety filter for linear systems that accounts for this delay. Two LIF states monitor a shifted CBF residual and the deviation of the held input from the nominal feedback law. A computation is initiated when either LIF state reaches its threshold; the previous input remains applied until the prescribed application time, and any solution returned earlier is stored until then. A closed-form charging profile relates the safety-LIF threshold to residual-growth bounds, ensuring sufficient residual margin over the application delay. Under the stated assumptions, the resulting hybrid system guarantees forward invariance, completeness, and non-Zeno execution, with positive lower bounds on computation-initiation and input-application times. A spacecraft terminal-approach simulation demonstrates safety with fewer optimizer calls than a delay-tightened periodic filter.
Read the full abstract

All authors Tochukwu E. Ogri, Opeyemi Owolabi, Luke Fina, Christopher Petersen, Rushikesh Kamalapurkar