CS Paper Radar

Daily listing

2026-11-17 · math.OC

10 papers first submitted this day (UTC) in math.OC — math.OC. arXiv announces a day's submissions the next evening, so the newest day fills up over ~24 h.

Score = weighted mean ofCitations 20%Upvotes 10%Code stars 10%Venue 15%Code/data 10%Novelty 15%Momentum 15%Substance 5%how it works

AI & Machine Learning 3

Balancing Exploration and Exploitation in Constrained Combinatorial Optimization with U(1)-Symmetric Tensor Trains

cs.LG math.OC ·2026-11-17 ·Sergei Iudin, Mikhail Podobrii, Dmitry Zheltkov, Stanislav Moiseev
publishedcode/data
Abstract · 39 pages, including supplementary material. Code: https://github.com/antientropic-guy/OhMyU1_public. Extends an earlier version presented at…

Tensor Train (TT) decomposition has emerged as a powerful tool for mitigating the curse of dimensionality in a variety of machine learning and combinatorial optimization tasks. Recent advances show that TT-based generative models can efficiently represent and explore high-dimensional discrete spaces, even when the cost function structure is unknown. However, incorporating hard linear constraints into TT-based optimization remains challenging, as existing interpolation and sampling approaches often fail when feasible points are rare. In this work, we develop a general TT-based framework for constrained combinatorial optimization built upon U(1)-symmetric tensor networks. Our method introduces an expressibility-enhancement mechanism for constructing sparse symmetric tensors and a graph-based diversity measure that guides sample selection during training. On assignment benchmarks, expressibility enhancement and diversity-aware selection improve mean solution quality over their respective baselines. The assignment-selected diversifying strategy also extends to nonpolynomial Set Partitioning, with larger relative gains observed in the higher-tensor-rank data families. Separate runtime benchmarks show substantial speedups over ConstrainTNet and PROTES on non-degenerate assignment workloads; comparisons with simulated annealing depend on constraint information and computational budget, but, overall, support the practicality of the current implementation.

0.50

Colombo: A Frontier-to-Frontier Autoresearch System for Oracle-Based Optimization

cs.AI math.OC ·2026-11-17 ·Haihan Zhang, Wendao Wu, Chenheng Zhang, Chunyuan Zheng, Yanyi Li +3 more
Abstract

Science advances from frontier to frontier as discoveries reshape what is known and create the basis for further discovery. We present Colombo, a self-organizing AI researcher that drives this renewal, first instantiated in oracle-based optimization. Here, the central question is how efficiently a problem class can be solved through a prescribed information interface and what costs no admissible algorithm can avoid. The gap between achievable guarantees and unavoidable limits defines the frontier recorded in its Complexity Atlas, a living map of frontier settings and the current state of knowledge. Self-Organization turns unresolved gaps into adaptive research programmes, coordinating conjecture formation, mathematical investigation, and replanning as evidence accumulates. Adversarial Co-Ascent develops algorithms and hard families through reciprocal challenge, exposing mechanisms of information use and concealment that guide stronger methods and proofs of unavoidable costs. Independent review and Lean-based formal certification check mathematical claims, while the Long-Term Memory carries supported findings and research experience across settings. To date, Colombo has established optimal or near-optimal rates for more than fifty settings in the Atlas. Colombo thus takes a concrete step toward Autopoietic Science: a scientific process whose validated advances regenerate the conditions of its own progress, continually reshaping how inquiry is organized and what it can discover.

0.31

An inexact stochastic variance-reduced gradient method for constrained convex finite-sum optimization

cs.LG math.OC ·2026-11-17 ·Zhaosong Lu, Yifeng Xiao
published
Abstract · Accepted by SIAM Journal on Optimization

In this paper, we study a class of constrained convex finite-sum optimization problems. In many practical applications, all or some of the constraints are hard constraints that represent imperative requirements. Consequently, any desirable approximate solution must (nearly) satisfy these constraints. Motivated by this, we focus on computing an $ε$-$surely\ feasible\ stochastic\ optimal$ ($ε$-SFSO) solution, in which the constraint violation is deterministically bounded by $ε$, and the expected optimality gap is at most $ε$. While a recently proposed stochastic variance-reduced first-order penalty method can compute an $ε$-SFSO solution, there remains a significant gap between its first-order oracle complexity for computing an $ε$-SFSO solution and that for computing an $ε$-$expected\ feasible\ stochastic\ optimal$ solution, where both the expected constraint violation and the expected optimality gap are bounded by $ε$. To narrow this gap, we propose an inexact stochastic variance-reduced gradient (SVRG) method that significantly improves the previously best-known first-order oracle complexity for computing an $ε$-SFSO solution. Furthermore, when the objective consists of a single function, the proposed method reduces to a novel deterministic first-order method for solving standard convex conic optimization. It achieves a significantly lower gradient evaluation complexity with respect to the objective function compared to existing methods, and can outperform them when computing constraint gradients and projections onto the associated cone is cheaper than evaluating the objective gradient. Preliminary numerical results are presented to illustrate the performance of the proposed method.

0.27

Theory & Algorithms 1

Binary Affine Optimization with Nearly-Graphic Constraint Matrices

cs.DS math.OC ·2026-11-17 ·Qiming Fang, Sihong Shao, Yuxuan Wu
Abstract · 25 Pages, 5 Figures

We present a polynomial-time algorithm for binary affine optimization with a linear objective when every column of the constraint matrix has Hamming weight at most 2, and prove that the problem is NP-hard when every column of the constraint matrix has Hamming weight exactly 3. We obtain fixed-parameter tractable (FPT) algorithms for the unrestricted problem provided that a nearly-graphic certificate is given, where the certificate roughly measures how far the constraint matrix is from having columns of Hamming weight at most 2. We apply our FPT algorithm to Max-Lin$_2$ on graphs and obtain FPT algorithms parameterized by the contraction distance and contraction rank of the graph, utilizing the concept of Eulerian-spanning set. In the case of contraction distance, another FPT algorithm can be used to find the corresponding certificate; that is, we obtain an FPT algorithm that requires no information beyond the problem instance itself.

0.41

Robotics, Control & Signals 6

The Multivariate Feedback Particle Filter for State-dependent Multiplicative Noises and Its Application to Attitude and Pose Estimations

cs.RO math.OC ·2026-11-17 ·Jingyao You, Xue Luo
Abstract · 14 pages, 5 figures, 3 tables

Nonlinear filtering with state-dependent multiplicative measurement noise poses a notable challenge for spacecraft attitude determination and robotic pose estimation. This work develops the FPF-DM, a decomposition scheme for feedback particle filters tailored to this family of filtering problems. Extending prior decomposition techniques for additive noise and polynomial measurement models, the proposed method resolves the key difficulty that state-dependent multiplicative noise breaks the polynomial assumption and prevents Hermite spectral backward recursion for the weighted Poisson's equation. By measure transformation and importance reweighting, we incorporate the inverse measurement covariance into particle weights and rescale the feedback gain to restore the polynomial-form Poisson's equation, with the decomposition generalized to non-uniformly weighted mixtures for closed-form gain computation. This general FPF-DM is instantiated on quaternion and dual-quaternion manifolds for attitude tracking and point-cloud registration. Simulations on 4D attitude tracking and 8D point-cloud registration verify that the instantiated filters using only 10 particles achieve superior accuracy and computational performance relative to baseline filters.

0.33

Finite sample guarantees of MPPI: suboptimality, sample complexity and closed-loop guarantees

eess.SY math.OC ·2026-11-17 ·Changyi Lei, Dragan Nesic, Ye Pu
theory
Abstract

This paper considers model predictive path integral (MPPI) control for nonlinear finite-horizon optimal control problems with bounded inputs, allowing nonconvex and nonsmooth costs. We prove theoretical guarantees that quantify the suboptimality caused by positive temperature and finite sampling on MPPI and establish their implications for closed-loop guarantees. Specifically, we derive a suboptimality bound for infinite-sample MPPI that characterizes the effects of temperature and prior coverage, followed by a high-probability finite-sample approximation error bound that reveals the dependence on sample size, temperature, and cost variability. By incorporating these bounds into a terminal-constraint-free MPC framework, we further establish semi-global practical recurrence of the closed-loop system. Numerical examples involving a four-link planar manipulator illustrate the temperature-sampling tradeoff and the influence of prior quality on approximation accuracy and closed-loop performance.

0.29

On the recursive feasibility and stability of MPC without terminal constraints

eess.SY math.OC ·2026-11-17 ·Mara Perez, Ignacio Sanchez, Filiberto Fele, Daniel Limon
Abstract · 6 pages, 1 figure. Comments are welcome!

In this paper, we analyze stability and recursive feasibility of a model predictive control (MPC) scheme that does not rely on terminal ingredients -- such as terminal constraints or a terminal cost based on a terminal controller. In the proposed formulation, we augment the cost function by a weighted finite tail which is optimized online, and we show it plays the role of a stabilizing terminal cost. Under a relaxed, local dynamic programming condition on the tail, we certify a family of regions -- parameterized by the tail's weight coefficient -- on which the problem is recursively feasible and the origin is asymptotically stable. These regions are larger as the weight increases: in particular, we show that any state that can be steered within the control horizon to a predefined neighborhood of the origin is contained in a certified region for a sufficiently large weight. Finally, we characterize the closed-loop performance over the certified region, bounding the suboptimality of the closed loop with respect to the infinite-horizon optimal cost. We conclude the discussion by illustrating these results on a simple numerical example.

0.28

Causal Input--Output Modeling with Prior Information

eess.SY math.OC ·2026-11-17 ·Amirhossein Taghvaei, Daran Xu
theory
Abstract

We study the problem of inferring a causal input--output model from unpaired marginal observations and a given prior coupling. We formulate this problem using entropic causal optimal transport, which seeks a coupling that preserves the observed marginals, satisfies a one--sided causality constraint, and remains close to the prior. For Gaussian marginals and general quadratic costs, we prove that the optimal coupling is Gaussian and reduce the problem to a finite--dimensional optimization over covariance matrices. Using a Cholesky transformation to simplify the causality constraint, we derive a Lagrangian dual formulation and develop a block coordinate descent algorithm with explicit update formulas. We establish linear convergence of the algorithm, with explicit convergence rates, and prove stability of the optimal coupling under marginal covariance perturbations and derive a statistical error bound. We further show its equivalence to Sinkhorn iterations. Numerical experiments demonstrate the computational efficiency of the proposed algorithm and illustrate the predictive advantages of causal couplings.

0.25

Transmission Expansion and Energy Storage Planning under Great Britain's Uncertain Energy Transition Pathways

eess.SY math.OC ·2026-11-17 ·Shengming Cao, Runsheng He, Waqquas Bukhsh
benchmark
Abstract · 49 pages, 10 figures

Long term power system planning must account for uncertainty in electricity demand and generation, while recognising the different investment and commissioning characteristics of transmission and energy storage. This paper develops a multi year stochastic framework for coordinated transmission expansion and energy storage planning and applies it to the Great Britain electricity system to assess investment needs through to 2050. The framework integrates multiple energy transition pathways with an enhanced representation of the GB transmission network and captures the different characteristics of transmission and storage investment over time. The coordinated treatment of transmission and storage is considered as a system level benchmark rather than a centralised investment mechanism. In GB, transmission investment is subject to regulated forward looking planning, while storage is largely developed by market participants in response to market signals. The framework therefore quantifies the potential value of improved coordination and identifies where existing investment signals may not encourage complementary storage deployment. Results across alternative transmission only, storage only and coordinated investment strategies show substantial benefits from joint planning. Compared with transmission only planning, coordinated investment reduces additional transmission capacity by 2%, cumulative expected load shedding by 97%, and total expected system cost by 36%, primarily through avoided unserved energy. Transmission preparation periods affect the timing, but not the final portfolio, of investments. Finally, the energy transition pathway materially influences investment requirements, with Electrification and Efficiency requiring 7% more transmission capacity and 45% more storage energy capacity than Falling Behind.

0.23

Grid-Responsive Pricing of Dynamic Wireless Charging with Coupled Residential Demand

eess.SY math.OC ·2026-11-17 ·Zhiheng Wang, Dipanjan Ghose, S. Sivaranjani, Junjie Qin, Qin Lv
Abstract · 5 pages, 2 figures. Submitted to the IEEE Power & Energy Society General Meeting (PESGM) 2027

Dynamic wireless charging (DWC) is an emerging technology that enables electric vehicles (EVs) to recharge while traveling. Its unique operational model creates two revenue streams for DWC operators through lane access tolls and electricity sales. However, these prices influence not only traffic flow and roadway energy delivery but also how much EV charging moves to homes instead, potentially within the same distribution network. Neglecting this coupling can underestimate grid loading and compromise pricing decisions. We develop a coupled traffic, EV energy, driver-response, and AC distribution network model with a model predictive control (MPC) framework that jointly optimizes DWC tolls and charging prices while explicitly accounting for displaced residential charging and network losses. Using 78 days of I-210 West traffic data, we show that conventional MPC exceeds feeder loading limits on 52 days, whereas the proposed residential load aware controller eliminates these violations with only 0.6% lower operator revenue. Under a more constrained feeder configuration, it eliminates 50 overloaded days with a 0.9% revenue reduction. Sensitivity analyses highlight the importance of accurate residential demand estimation and feeder loss modeling, while peak-aware pricing further reduces daily peak loading by 3.7% relative to the base load. These results demonstrate the value of coordinated pricing that captures the interaction between roadway and residential charging.

0.19