New on arXiv
Sort: by field | by arXiv number | trending
An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
We study composite optimization over the Bures--Wasserstein (BW) space of Gaussian measures. Our main observation is that a useful class of BW problems can be lifted into the Euclidean space of affine transport maps, such that the lifted problems can be solved efficiently using accelerated proximal gradient methods. For objectives whose smooth and nonsmooth components admit convex smooth and...
Augmented Lagrangian methods with telescopic subproblems for MPCCs and cardinality constraints with general constraints: constraint-preserving swaps and B-stationarity
We consider optimization problems with general equality and inequality constraints and partitioned cardinality constraints, which include complementarity constraints. In the augmented Lagrangian method that we consider, the bounds and the cardinality constraints are kept in the subproblems, which are solved by the Telescopic Method. The limit points of this method are B-stationary, without...
A Theoretical Analysis of a Bilevel Optimization Formulation for Combined Local-Global Optical Flow Models
This paper analyzes a bilevel formulation for learning the regularization parameter of combined local-global (CLG) optical flow models. The lower-level problem computes the flow from a Lucas--Kanade data term and a quadratic or total variation (TV) regularizer, and the upper-level problem selects the parameter that minimizes the squared distance to a ground-truth flow. The setting is...
Hardness of integer linear feasibility with cyclic support
We prove that integer linear feasibility is strongly $NP$-complete even when the constraint matrix has exactly two nonzero entries in every row and column, with its support forming a single cycle. This holds already for monotone systems (one positive and one negative coefficient in each inequality) with nonzero coefficients of absolute value $2$ or $3$ and right-hand sides in $\{-1,0,1,2\}$. No...
A Proximal Newton Framework with Local Superlinear Convergence for Simple Bilevel Optimization
In this paper, we study a penalty method for simple bilevel optimization in which the lower-level objective has a convex composite structure. Our approach is based on a vanishing-penalty reformulation, which gives rise to a sequence of penalized problems as the penalty parameter decreases. A key difficulty is that metric subregularity of the lower-level optimality mapping does not, in general,...
Adaptive pairwise preference elicitation for decision support: identifying the best alternative with fewer judgments
Interactive decision support systems often require repeated preference judgments, although identifying the best alternative may not justify eliciting all \(n(n-1)/2\) pairwise comparisons. We propose ALEC (Adaptive Lexicographic Elicitation of Comparisons), which re-ranks the alternatives after each judgment and asks the first unobserved pair in the lexicographic order of the current ranking,...
Overcoming Fundamental Control Limitations in Powered Descent Flight through Robust Incremental Nonlinear Dynamic Inversion
This work identifies a fundamental, controller-independent limitation in reusable launch vehicle powered descent: a sudden $180^\circ$ phase transition in the open-loop transfer functions from the control inputs to the lateral drift and drift rate. The transition occurs inside the flight envelope, reverses the effective control direction, and can destabilize the closed loop system under...
On the Minimal Controllability of Boolean Networks With $k$-Regular Dependency Graphs
Boolean networks (BNs) are widely used to model gene regulatory networks and other biological systems. In this paper, we investigate the minimal controllability problem for BNs subject to degree constraints. We first establish three new best-case upper bounds for XOR-BNs whose dependency graphs are $k$-regular. We then introduce classes of BNs that are invariant under cyclically partite...
A Solution Method for Single-Source Capacitated Facility Location Problems Under Decision-Dependent Demand Uncertainty
We present a model and an exact solution method for single-source capacitated facility location problems with decision-dependent demand uncertainty. The model allows the joint probability distribution of customer demands to depend on the facility to which demand points are allocated. The number of possible decision-dependent distributions is therefore equal to the number of feasible allocations...
A globally convergent stochastic semismooth Newton method for strongly convex problems in Hilbert spaces
We propose and analyze a globalized stochastic semismooth Newton method for stochastic optimization problems in Hilbert spaces where the objective is strongly convex with Lipschitz continuous, Newton differentiable gradient. Gradient and generalized Hessian information are only available through mini-batching. In each iteration, a full semismooth Newton trial step is accepted or rejected based on...
Funnel MPC for port-Hamiltonian systems
Port-Hamiltonian systems are an energy-based modelling formalism, that has strong ties to the physical models and allows interconnection of systems. Funnel MPC, a Model Predictive Control (MPC) scheme, allows for output tracking with prescribed error bounds. Earlier works focused on systems with stable internal dynamics, which typically excludes port-Hamiltonian systems. We introduce a modified...
Quantifying the remaining search space in analogue optimisation
Benchmarking analogue optimisers requires certifying not only how close a returned energy is to the optimum, but also how many better configurations may remain. Semidefinite relaxations provide rigorous bounds on the ground-state energy and selected observables, yet reveal little about the size of this residual search space. We introduce a deterministic, instance-specific upper bound on the...
On the Spectral Dependence of Decentralized Stochastic Gradient Tracking
We study how the spectral geometry of the mixing matrix enters the convergence of decentralized stochastic gradient tracking (GT) for smooth strongly convex problems. General bounds contain the factor $\Delta_\lambda^{-3}$ in the higher-order stochastic term, where $\Delta_\lambda$ is the absolute spectral gap. We show that, even for two agents with identical quadratic objectives, the exact...
Newton Steps are Faster for Linear Complementarity Problems
Linear Complementarity Problems (LCPs) with sufficient matrices form a well-studied class of problems, dating back from the foundational works of Cottle and Dantzig (1968). LCPs capture convex quadratic programs, and admit reductions from problems such as discounted stochastic games or mean-payoff games. While the original approach for solving these problems was based on pivoting methods, in...
Online Optimization for Controlling HVAC Systems
Heating, ventilation, and air-conditioning (HVAC) systems account for a significant portion of buildings' energy consumption, motivating the design of energy- and cost-efficient control strategies. However, conventional strategies employ simple, reactive control, without incorporating a model. Therefore, in this paper we adopt an economic model predictive control framework and focus on designing...
Randomized and Oracle-Based Feasible Directions Methods for Nonsmooth Nonconvex Constrained Optimization
Minimizing nonsmooth nonconvex objectives over general convex sets using no derivatives of the objective, together with structural access to the constraint set, poses a fundamental geometric difficulty: at boundary points, the feasible direction cone may fail to be closed, preventing the construction of finite sets of search directions that capture all feasible descent directions. We develop a...
Randomized Parallel Complexity of Weakly Convex Optimization
We study the minimum number of query rounds needed to find approximate stationary points of nonsmooth weakly convex functions, measured by the gradient of the Moreau envelope. Each round permits multiple simultaneous queries. In the stated parameter regime, the standard subgradient rate is optimal in sufficiently high dimensions, even for randomized algorithms making polynomially many parallel...
A Graph-Theoretic Approach to Matrix AM-GM: Counterexamples and Sharp Exponential Bounds
We develop a graph-theoretic approach to the expected-norm matrix arithmetic--geometric mean inequality. By encoding matrix interactions with a path-supported Gram matrix, we obtain a projection family whose product is nonzero exactly when the transition graph of its index sequence is a path. This gives an intuitive explanation for failure: repeated indices can create cycles or branches that...
Projection-Free Gradient Tracking Neurodynamic for Distributed Nonnegative Sparse Optimization
This paper proposes a continuous-time, projection-free neurodynamic system based on gradient tracking for distributed nonnegative sparse optimization. Unlike traditional methods, our approach avoids projecting states onto the feasible set. Instead, it employs gradient tracking to estimate average gradients under heterogeneous costs, coupling primal and dual dynamics such that feasibility and...
A Bilevel Neurodynamic Approach for Distributed SCAD-Regularized Sparse Least Squares
This paper proposes a bilevel particle swarm optimization (PSO)-neurodynamic method for solving the distributed sparse least-squares problem regularized by the smoothly clipped absolute deviation (SCAD) penalty to global optimality. The SCAD penalty is nonsmooth and nonconvex, so existing distributed neurodynamic methods have not been extended to it directly. Through two-time-scale singular...
Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent
Stochastic Gradient Descent (SGD) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet its practical implementation differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (Shuffling SGD). A particularly popular strategy in Shuffling SGD is Random Reshuffling (RR), which has achieved great empirical...
Continuous-time q-Learning for Finite-Horizon Portfolio Choice with Optimal Stopping in Jump-Diffusion Markets
We develop a structured continuous-time q-learning framework for finite-horizon investment and optimal stopping under jump-diffusion dynamics with unknown parameters. A penalty approximation transforms the Hamilton-Jacobi-Bellman variational inequality into an HJB equation with a binary control for the stopping penalty. An auxiliary state incorporates the resulting control-dependent discount...
From What Is Used to What Is Missing: Rethinking Dynamic Rank in LoRA
Parameter-efficient fine-tuning with LoRA is governed by rank, which controls parameter budget and locally accessible task updates. Existing dynamic-rank methods mainly focus on capacity allocation, leaving unresolved whether the current adaptation space is sufficient for the task. We characterize the first-order information boundary of standard factor gradients, showing that their unobservable...
Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems
Last-iterate convergence guarantees for stochastic gradient methods have attracted significant attention as practical implementations typically return the last iterate instead of an average of the iterates. In this paper, we study two approaches for analyzing the last-iterate convergence of proximal and projected stochastic gradient methods without bounded domain or bounded variance assumptions,...
Selecting the best UAV pursuer for minimum time moving target interception among obstacles
A team of unmanned aerial vehicles (pursuers) with different positions, headings, speeds, minimum turning radii and launch delays must respond to a target that moves at constant velocity through a region containing static circular obstacles. Only one pursuer is launched, namely the one that can intercept the target first. We present a computationally efficient, obstacle-aware...
Cubic Optimization over Three Nonnegative Integers Is NP-hard
We prove that deciding whether an integer cubic polynomial takes a value at most one over three nonnegative integers is NP-hard. Hardness holds even when every feasible objective value is a positive integer, so every constructed instance has a finite, attained minimum. This establishes a sharp dimension boundary for the tractability of cubic integer optimization in fixed dimension. Our reduction...
Multiplayer Stopping Games with a Conditionally Atomless Filtration
Stopping games are the multiplayer generalization of optimal stopping problems, in which each player independently chooses when to stop, and the payoff depends on who stops first and when. While the existence of $\varepsilon$-equilibria in two-player stopping games with integrable payoffs is known, the multiplayer case has remained open. We prove that every multiplayer stopping game in discrete...
How to Look Inside the Black Box: A Survey of Yu. E. Nesterov's Contributions (On the Award of the 2026 Gauss Prize)
On July 23, 2026, at the opening of the International Congress of Mathematicians in Philadelphia, the International Mathematical Union announced the award of the Gauss Prize to Yurii Evgenievich Nesterov -- an award for mathematical work with significant applications outside mathematics. This article explains the mathematical content of the recognized work of Yu. E. Nesterov and traces its...
Practical Semialgebraic Optimization via Sparse Sample-Based Sum-of-Squares Programming
As the importance of semialgebraic optimization grows in engineering, so does the need for scalable sum-of-squares (SOS) methods. Their convex relaxations can guide mixed-integer search and often deliver certified global optima outright. Scaling traditional SOS typically requires hand-crafted bases and redundant constraints, whereas sample-based SOS numerically exploits feasible set geometry to...
Ramification of Weighted Central Paths and Super-linear Interior-Point Methods for Semi-definite Optimization
The local convergence of primal-dual interior-point methods for semi-definite optimization is closely tied to the regularity of the central path at its limiting point. Without strict complementarity, the central path can exhibit fractional power asymptotics and need not be differentiable in the ordinary barrier parameter. We show that this obstruction can be removed simultaneously for a family of...
Noether's Second Theorem and the Pareto Front Structure in Multi-Criteria Variational Problems
This paper establishes a rigorous connection between Noether's second theorem and the structure of Pareto fronts in multi-criteria variational problems. We prove that for a family of functionals invariant under a common gauge Lie group, the regular part of the Pareto front is contained in the union of solutions to weighted Euler--Lagrange equations, and that on Pareto-optimal sections,...
The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
The complexity of finding second-order stationary points (SOSPs) in constrained settings has remained unclear and has been highlighted as an open question by the works of Hollender and Zampetakis [2023] and Kontogiannis et al. [2024]. In particular, under one established definition (SOSP1) where nonnegative curvature is required only along the null space of the active constraints [Bertsekas,...
Only titles, authors and the start of each abstract are shown here, as arXiv published them. Open a paper to read its whole abstract and, with your own AI key, a plain-language summary. Papers on arXiv are preprints and may not have been peer reviewed.
Data from arXiv, used through the arXiv API. Thank you to arXiv for use of its open access interoperability.