Papers

We prove that deciding global asymptotic stability for constrained finite-horizon linear model predictive control is undecidable. This holds at horizon one with identity state, input, and terminal weights, unique optimizers, and global feasibility. Separate reductions cover predicted-state boxes, hard input boxes, and quadratically softened input boxes. A fourth reduction fixes the state and input dimensions to three and six. Hence undecidability is not caused by long horizons, growing dimensions, failures of recursive feasibility, or nonuniqueness.

Meta-learning has emerged as an effective paradigm for transferring knowledge across sequential bandit tasks. While substantial progress has been made for stochastic bandits and non-contextual adversarial bandits, meta-learning for adversarial linear contextual bandits (ALCBs) with random action sets remains largely unexplored. To address this problem, we propose Meta-LinEXP3, an online-within-online algorithm that constructs a predictable task-level prior from completed tasks to guide the inner LinEXP3 learner. For known context distributions, we develop a policy-centered estimator that achieves an intrinsic-dimension $\mathcal{O}(\sqrt{n})$ per-task regret bound. For unknown distributions, we introduce a past-only regularized moment estimator with an $\mathcal{O}(n^{2/3})$ leading regret term and explicit finite-sample error. We further establish a direct connection between prior accuracy and transfer regret, showing that increasingly accurate priors yield sublinear transfer-dependent regret across tasks. Experiments demonstrate the effectiveness of Meta-LinEXP3, including its application to structured hyperspectral tensor sampling.

Lewis and Overton conjectured in 2008 that, for BFGS applied to the one-dimensional tilted absolute value with their Armijo–Wolfe line search, every nonterminating execution converges at a trial-normalized rate determined only by the tilt parameter and independent of the initial data. We prove that this initialization-independent rate assertion is false. In fact, for every tilt parameter in an explicit open interval, we construct two nonterminating executions with different sharp trial-normalized convergence rates. The proof reduces the line search to a scale-free state consisting of the iterate sign and the zero-crossing stepsize, and verifies two periodic state cycles by elementary rational inequalities. This yields an explicit family of counterexamples and shows that the asymptotic trial-normalized behavior of nonsmooth BFGS can depend essentially on the initialization even for this canonical one-dimensional model.

We propose a Pareto front approximation (MPFA) method for smooth bi-objective optimization problems on Riemannian manifolds based on a Hermite interpolation technique. Compared with the existing multiobjective optimization numerical algorithms, the proposed method can generate a continuous approximate Pareto front without multiple initial points. We establish convergence of the proposed method and analyze the approximation error of the resulting Pareto front. Numerical experiments on several test problems demonstrate that the proposed approach can effectively approximate the Pareto front with high accuracy and reasonable computational cost. Furthermore, the method is applied to a bi-objective formulation of sparse principal component analysis, illustrating its practical applicability in data analysis problems.

This paper addresses time-varying coverage control for multi-agent systems, formulated as the tracking of an evolving target density via entropy-regularized semi-discrete optimal transport. Unlike the hard Laguerre partition of the unregularized formulation, entropic regularization assigns fractions of the mass at each point to all agents, simplifying the design and numerical implementation of the control law. We derive a feedback-feedforward controller that tracks the evolving first-order optimality conditions with exponential convergence, and we investigate the role of the regularization parameter, which, above a critical threshold, renders the fully collapsed configuration locally optimal. Numerical experiments validate the theory: for moderate regularization, the proposed approach has performance comparable to the unregularized formulation and outperforms the corresponding Voronoi-based coverage baseline.

In online inverse linear optimization, the learner predicts a weight at each round, observes the optimal action of the agent, and updates its prediction. In the general setting, the gap of $\log T$ between the regret upper bound $O(d \log T)$ and the lower bound $\Omega(d)$ is unresolved (here $T$ is the total number of rounds and $d$ is the dimension). When the action set is M-convex, the regret is known to be bounded by $O(d \log d)$, but the method attaining it computes a center of gravity at every round. This paper therefore proposes Small-Gradient Skipping (SGS), a mechanism that skips the update at rounds without a mistake, and applies it to online gradient descent, the online Newton step, and MetaGrad. When the forward problem is an integer linear program with a unique optimal solution, the number of mistakes is bounded, for all three, by a quantity independent of $T$; and for the online Newton step and for MetaGrad with SGS, the dimension dependence of the regret becomes $O(d^2)$, that is, the factor $\log T$ is removed. Moreover, when the action set is M-convex, the regret is bounded efficiently without computing a center of gravity.

We study internal exact controllability of the free Schrödinger equation on finite compact metric graphs with Kirchhoff conditions at interior vertices and a fixed Dirichlet-Neumann assignment at exterior vertices. For a prescribed primitive cycle or exterior-to-exterior path, we identify an arithmetic criterion ensuring that the corresponding scar is accessible by exact high-frequency eigenfunctions of a fixed target metric. The criterion is formulated by intersecting the regular scar stratum of the secular set with the orbit-closure torus of the target length vector, and it can hold for resonant metrics beyond the rationally independent class. Under an intrinsic Diophantine condition on the orbit-closure flow, the construction is quantitative: along an exact eigensequence the mass outside the prescribed support decays polynomially, yielding a polynomial degeneration law for finite-frequency observation when that support is uncontrolled. Rationally independent metrics have full phase-orbit closure and therefore make every primitive obstruction accessible. Combining this spectral result with the known graph-theoretic characterization and sufficiency of the Graph Geometric Control Condition (GGCC), we prove that, for every rationally independent and hence for Lebesgue-almost every metric, GGCC is necessary and sufficient for exact controllability at every positive time in the free setting.

In this paper, we study the closed-loop $\alpha $-potential stochastic differential game (SDG) problem as a continuation of our prior research on open-loop control (see \cite{GLZ2025}). By utilizing the backward stochastic differential equation (BSDE) approach, we derive a precise estimate for the parameter $\alpha $. Compared to our earlier work \cite{GLZ2025}, this study incorporates both first- and second-order sensitivity state processes, as well as the sensitivity of the control process. A distinguishing feature of this work is that, in the context of $N$-player heterogeneous agent games involving mean-field type interactions, we derive an $N$-uniform upper bound for the minimal potential approximation error. In contrast to the corresponding open-loop estimates, the closed-loop bound contains feedback-induced contributions that need not vanish with $N$. Consequently, our present estimate does not in general guarantee $\alpha \rightarrow 0$.

We study how predefined randomized parameter schedules accelerate the heavy-ball method on general smooth convex objectives. Our analysis distinguishes two levels of randomization: sampling gradient-evaluation times within intervals whose boundaries are deterministic, and additionally randomizing the time boundaries themselves. With deterministic time boundaries, we construct fixed-time and anytime schedules that achieve an expected last-iterate function value gap of order $\mathcal{O}(1/K^{4/3})$; the anytime schedule also satisfies the same rate almost surely. We then use randomized time boundaries and obtain the improved last-iterate rate $\mathcal{O}(1/K^{3/2})$, both in expectation and almost surely. To the best of our knowledge, this is the first global nonasymptotic convergence guarantee for the heavy-ball method on general smooth convex functions that improves polynomially over the classical $\mathcal{O}(1/K)$ rate. Our result shows that the heavy-ball method achieves a strictly better convergence rate than the best known result $\mathcal{O}(1/K^{\log_2(1+\sqrt{2})})$ attainable by plain gradient descent with silver stepsize schedules.

Generalized Arimoto–Blahut (AB) algorithms are widely used in information theory and quantum optimization, but monotonic objective decrease and numerical stabilization do not guarantee global optimality. We establish necessary and sufficient conditions for the global optimality of full-rank AB fixed points for convex differentiable objectives under linear constraints. An AB fixed point is globally optimal if and only if the AB update direction and the objective gradient differ by an element of the constraint normal space at that point. The same compatibility condition characterizes agreement between individual AB and mirror-descent (MD) updates, whereas pathwise equivalence requires it along the entire common trajectory. Thus, an AB algorithm may follow a trajectory different from MD and still reach the global optimum. We also develop a posteriori optimality certificates based on feasible directional derivatives, including finite-difference upper bounds on the objective gap that require only objective evaluations. For channel relative entropy between dephasing and depolarizing channels, we analytically identify the global minimizer as the unique full-rank AB fixed point, although pathwise equivalence fails. Numerical experiments illustrate convergence of AB and MD along different trajectories and validate the certificates. By contrast, an amplitude-damping example shows that a monotone AB iteration can stabilize at a suboptimal fixed point, whose nonoptimality is detected by the finite-difference certificate. These results provide structural and computable criteria for assessing global optimality in quantum AB algorithms.

Whether the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method and its variants can fail to converge on smooth nonconvex functions under realistic line-search parameters has remained a central open problem in quasi-Newton theory since the landmark counterexample of Dai (2002), which was confined to small Armijo parameters ($c_1 \le 1/84 \approx 0.0119$ on Powell's geometry, or $c_1 \le 69/7480 \approx 0.0092$ on his six-point cycle) and an objective function unbounded below. In this paper, we resolve the long-standing open question, posed by Dai (2002) following a discussion with J. C. Gilbert, of whether such counterexamples exist in theory for every Armijo parameter $c_1 \in (0, 1)$. Specifically, for every prescribed pair of line-search parameters $0 < c_1 < c_2 < 1$, we construct an objective function $f \in C^\infty(\mathbb{R}^2)$, bounded below and with Lipschitz continuous gradient, on which every method in a broad conjugacy class $\mathcal{C}$ equipped with the first-local-minimizer line search generates an infinite sequence of iterates with $\|\nabla f(x_k)\| = 1$ for all $k \ge 0$. The class $\mathcal{C}$ encompasses the classical full-memory BFGS method, limited-memory BFGS (L-BFGS) with arbitrary memory $m \ge 1$, the Broyden positive family, and the Hestenes-Stiefel conjugate gradient method. The steps are the standard first local minimizers along the search rays and simultaneously satisfy the strong Wolfe, weak Wolfe, Armijo, and Goldstein conditions with constants $(c_1, c_2)$. The construction operates in the minimal possible dimension $n = 2$, exploiting a non-decaying conjugate descent orbit in the plane coupled with an explicit tubular interpolation whose two-bump axial curvature profile places the Armijo ratio anywhere in $(0, 1)$.

Optimization problems with nonlinear equality constraints arise throughout science, engineering, and increasingly in machine learning. Prominent methods for solving such problems include sequential quadratic programming and, more broadly, primal-dual Newton methods. Classical analyses of these methods typically rely on strong assumptions, perhaps most notably positive definiteness of the Lagrangian Hessian on the null space of the constraint Jacobian. In practice, this assumption often necessitates strong regularization or the use of a positive definite Hessian surrogate. Moreover, in large-scale settings, solving the primal-dual Newton subproblem exactly is often computationally infeasible. To address these issues, we propose an inexact primal-dual Newton method with an inner solver based on the conjugate residual (CR) method. Exploiting recently established properties of CR, including negative-curvature detection, iterate monotonicity, and descent guarantees, our method handles indefiniteness in the subproblem directly as it arises. Our method thereby avoids detrimental regularization of the Lagrangian Hessian while naturally accommodating inexact solves. We establish worst-case global convergence guarantees and demonstrate strong empirical performance on large-scale, nonconvex problems.

Computing the optimal success probability for transmitting classical messages through a single use of a quantum channel is NP-hard, even for two messages. An existing semidefinite programming hierarchy based on symmetric extensions provides convergent upper bounds with an a priori error estimate that decays as the inverse square root of the extension level. In this work, we construct a Hermitian sum-of-squares hierarchy for an arbitrary number of messages and prove quadratic convergence in its level. The error bound is proportional to the advantage over random guessing. Our approach combines state-discrimination duality with positive polynomial kernels on products of spheres to construct feasible polynomial dual certificates. For binary messages, the resulting bounds give a multiplicative approximation from above of the trace-norm contraction coefficient.

Problem definition: The car resequencing problem involves rearranging the sequence of cars between two adjacent production shops via an intermediate buffer. This study explores a new variant that aims to minimize the resequencing makespan when the buffer features several forward lanes and a return lane (RL). Both types of lanes follow first-in-first-out rules, but operate in opposite directions. Through the RL, cars can circulate between forward lanes, thereby increasing resequencing flexibility and complexity. The goal is to position cars over time to complete the target sequence change in the shortest possible time. Methodology/results: We prove the problem is NP-complete and develop an exact two-stage branch-and-price approach integrated with constraint programming (BP-CP). Three versions of the master problem (MP) are proposed for the first stage, each paired with a subproblem defined on a specific graph. Using partial integer solutions from branching, a constraint-programming model built in the second stage yields either a feasible solution to the problem or a feasibility cut added to the MP. Experimental results indicate that BP-CP greatly increases the scale of solvable instances for a production batch, especially with a moderately relaxed MP. A comparative analysis shows that the RL markedly enhances resequencing flexibility, enabling smaller buffers to attain makespans comparable to those of larger buffers without the RL across varying resequencing complexities. Managerial implications: Expanding lane capacity alone yields limited gains in resequencing performance and may even reduce efficiency. The RL acts as several forward lanes, supporting a smaller and cost-effective buffer design while maintaining efficient just-in-time operations.

We develop a Balancing Domain Decomposition by Constraints (BDDC) preconditioner for the interface systems arising from active-set semi-smooth Newton linearizations of elliptic optimal control problems with box-constrained controls, $L^1$-sparsity, and Moreau–Yosida regularized state constraints. The domain decomposition and BDDC construction are formulated directly at the infinite-dimensional level. Eliminating the interior variables yields a Schur complement for the state and adjoint traces assembled from local subdomain operators. We prove a global–local equivalence result, establish well-posedness of the local and partially assembled problems under verifiable conditions on the primal constraints. The BDDC operator admits a two-level additive Schwarz representation with independent local solves and a finite-dimensional coarse solve. We implement the preconditioner using conforming finite elements and test it for distributed and Neumann boundary control. For a fixed ratio of subdomain diameter $H$ to mesh size $h$, the GMRES iteration counts are nearly independent of mesh refinement and grow only moderately as this ratio increases. Enriching the coarse space substantially improves convergence and reduces sensitivity to the control regularization and sparsity weights. For the state-constrained problem, scaling the Moreau–Yosida penalty parameter proportionally to $h^2$ yields nearly constant GMRES iteration counts as the mesh is refined.

We study the oracle complexity of computing a point with small fixed-point residual $\|T(x)-x\| \leq \epsilon$, for a general norm $\|\cdot\|$ and a self-map $T$ of a compact convex set. We study this problem in the setting where $T$ is nonexpansive with respect to the same norm $\|\cdot\|$ and accessed via an unbiased stochastic oracle with bounded variance $\sigma^2$. We provide an algorithm that solves such instances for any norm with a weak Rademacher type $q > 1$, with high probability. The algorithm is based on a recursive anchoring technique. For type-$2$ spaces, such as $\ell_p$-spaces for $p \in [2, \infty]$, our algorithm attains stochastic oracle complexity $\tilde O(\sigma^2 \epsilon^{-3} + \epsilon^{-1})$. We further prove a near-matching lower bound (i.e., matching up to poly-log factors) for such $\ell_{\infty}$-norm instances in high dimensions. Our lower bound holds against any randomized algorithm that succeeds with constant probability. It further extends to settings with “sparse” noise, where variance measured with respect to any $\ell_p$ norm is of the same order, ruling out the possibility of improving oracle complexity as a function of $\varepsilon$ by measuring variance in a non-matching $\ell_p$ norm.

Gravity-assist trajectory design requires searching numerous leg combinations, but applying nonlinear programming (NLP) for low-thrust trajectory optimization to all combinations is computationally prohibitive. Therefore, conventional frameworks first perform broad search using lightweight trajectory models such as Lambert-based calculation and simplified deep-space maneuver models, while pruning infeasible candidates. However, to maintain efficiency, conventional approaches handle only low-dimensional formulations with limited constraints such as up to a couple of impulse maneuvers per leg. Consequently, they cannot accommodate the constrained multivariable optimization required for low-thrust design, running the risk of prematurely pruning viable trajectories. To address this, this paper introduces a convex pruning approach capable of solving constrained multivariable problems directly within broad search while retaining the computational efficiency. We then augment the broad search stage with a robust local low-thrust optimization algorithm based on thrust regularization, which together enable global exploration and optimization in an automated fashion. We apply the proposed framework in a BepiColombo-inspired scenario involving nine gravity assists, successfully demonstrating its broad search capability to discover a far greater number of solutions (36,335) compared to a conventional approach (4,664) while identifying a wider feasible launch window by one year.

We study the projected power method (PPM) for synchronizing \(n\) unknown permutations of \(m\) objects under a possibly sparse uniform corruption model. Each pair is observed with probability \(p\), and an observed measurement is uncorrupted with probability \(\pi_0\) and is otherwise an independent uniform permutation. Under \(\log m=o(np\pi_0^2)\), we prove exact one-step recovery (with high probability) of each prescribed block for an independent estimate with a fixed positive majority of correct blocks. When \(np\ge C_0\log n\) and \(m=o(np\pi_0^2)\), we prove that one high-probability event yields a block-error contraction simultaneously for every estimate whose optimally aligned error is at most \(0.5-\epsilon\). The contraction factor is \(O(m/(np\pi_0^2))\) and the error floor is \(O(e^{-cnp\pi_0}+e^{-cnp\pi_0^2}+{\log n}/{n})\). Consequently, one update maps every possibly data-dependent estimate in this basin to vanishing block error, and all subsequent iterates remain almost exact uniformly over the iteration index. The one-step and trajectory results extend to independent, non-identically distributed, permutation-valued corruptions with mean \(m^{-1} \mathbf{1}\mathbf{1}^{\top}\). Under the uniform model, a reference-block spectral initializer has aligned block error \(O_{\mathbb P}(m/(np\pi_0^2))\), yielding an end-to-end almost-exact recovery guarantee. Under a stronger all-block signal condition, PPM reaches exact recovery after finitely many iterations. The theory transfers exactly to partial permutations with common support; for varying supports, we establish deterministic and probabilistic co-visibility margins.

Online gradient descent is usually studied through external regret, where the learner competes with fixed alternatives. Recent work shows that first-order methods control richer action-dependent deviations. We ask for a geometric characterization of the deviations with respect to which online gradient descent, mirror descent, and follow-the-regularized-leader (FTRL) achieve no regret. We identify exactness as the common principle. Exactness means that the relevant displacement field is generated by a scalar potential, or equivalently that the associated one-form is exact in the geometry used by the algorithm. This geometry depends on the algorithm. For gradient descent it is Euclidean geometry, for mirror descent it is the geometry induced by the regularizer, and for FTRL it is the cumulative dual state. Under mild regularity conditions, exactness yields sublinear regret, while nonzero circulation provides the complementary obstruction and leads to linear regret. This gives a unified geometric framework for understanding the deviation classes controlled by these algorithms and reveals that different first-order methods can control genuinely different classes of deviations. These deviation classes have direct consequences for learning, particularly in games. We study the equilibrium notions induced by exact-form deviations and introduce conservative correlated equilibrium, reflecting both the conservative geometry of the underlying displacement fields and the restricted family of deviations available to the players. We characterize its relation to correlated equilibrium, determine when the resulting equilibrium notions coincide and when they separate, and show how these relationships depend on the geometry and the learning algorithm. Overall, this work gives a unified geometric account of what first-order online learning algorithms are no-regret with respect to, beyond fixed comparators.

Quantum state tomography is a fundamental technique for estimating the state of a quantum system from measured data and plays a crucial role in evaluating the performance of quantum devices. However, standard estimation methods become computationally prohibitive as the system size increases due to the exponential growth of the density matrix, describing a quantum state, with the number of qubits. We propose a low-rank tensor-network framework for mixed-state quantum state tomography based on a block tensor train (Block-TT) factorization. Specifically, the density matrix is represented as the contraction of a Block-TT with its Hermitian transpose, yielding a TT analogue of the Burer-Monteiro factorization. This parameterization guarantees Hermiticity and positive semidefiniteness by construction while compressing the number of optimization variables from exponential to linear in the number of qubits. Building on this representation, we develop single-site and two-site density matrix renormalization group (DMRG) algorithms for estimating quantum states from compressed measurements. The resulting methods operate directly on the compressed parameterization, support adaptive rank refinement, and exploit efficient tensor-network contractions for expectation-value evaluation. The framework is applicable to a broad class of low-rank quantum states, including pure states, nearly pure states, and ground states that admit accurate tensor-network approximations. Numerical experiments demonstrate accurate state reconstruction from limited measurements together with substantial reductions in memory requirements and computational cost compared with conventional low-rank tomography methods.

We develop a unifying variational framework for accelerated primal-dual flows in affinely constrained convex optimization. In particular, it is shown that applying the Euler-Lagrange-Rayleigh (ELR) principle to coupled augmented Bregman Lagrangians systematically generates accelerated dynamics over general Bregman geometries and recovers a family of existing primal-dual mirror and Alternating Direction Method of Multipliers (ADMM) flows as special cases. We then establish $\mathcal{O}(e^{-b_t})$ convergence guarantees for these flows under mild assumptions. Lastly, we show that the proposed framework for algorithmic development extends from finite-dimensional optimization to constrained optimization over probability distributions.

First-order methods for linear conic programming often stall on long plateaus. Existing analyses characterize when during a run or on which problem instances slow convergence occurs; we instead ask where in the state space slow convergence is present. We introduce the slow region family for parameterized averaged fixed-point iterations. On a slow region, one step moves the state by only a small fraction of its distance to the fixed-point set, so an orbit starting there keeps almost its initial distance for arbitrarily many iterations. We then develop the afterimage principle to construct them. A center family and a nearby petal family share the same limit parameter, so their residual fields become close, while their fixed-point sets or forward drifts stay far apart. The petal geometry then certifies a slow region for the center. We verify the standing assumptions for ADMM, sGS-ADMM, and PDHG, and give an LP, SOCP, and SDP gallery showing how varied slow regions can be.

We propose variants of model-based trust region derivative-free algorithms that are closest to methods initially proposed and implemented by Powell. These methods rely on low degree polynomial interpolation and carefully maintain geometry of the interpolation sets. We are able to derive complexity bounds for these methods that make them theoretically competitive to other derivative-free methods. Applying these methods in randomly generated subspaces recovers what we believe to be nearly tight complexity. This paper builds on recent results where complexity of a much simplified version of Powell's methods was derived. Here, we extend the analysis to fully incorporate Powell's geometry handling approach and conduct an extensive numerical comparison of the model-based trust region methods connecting practical and theoretical performance. We also extend the analysis of subspace model-based trust region methods to the case of noisy function evaluations.

This paper develops a novel distributed optimization algorithm based on the Alternating Direction Method of Multipliers (ADMM) to solve hierarchical optimization problems over tree-structured networks, termed hierarchical ADMM (hADMM), with a particular focus on enhancing communication efficiency across the network. By rearranging the augmented Lagrangian to establish a query-response communication mechanism between nodes that explicitly exploits the hierarchical tree structure, the proposed algorithm significantly reduces communication costs compared to existing ADMM-based methods for hierarchical optimization. Furthermore, hADMM guarantees asymptotic convergence under convexity assumptions. We also present a convergence rate analysis based on linear matrix inequalities to characterize the maximum theoretically achievable convergence rates across different network topologies, showing that the proposed hADMM attains linear convergence under mild conditions. Three numerical experiments demonstrate that hADMM is compatible with arbitrary tree network structures and outperforms existing approaches in terms of communication efficiency.

The fixed-charge network flow problem (FCNFP) couples continuous flow allocation with discrete arc-activation decisions, making it a canonical but computationally challenging model for a variety of network design and resource allocation problems. Exact mixed-integer linear programming formulations capture the fixed-charge structure faithfully, but often become difficult to solve on large networks. We propose a scalable continuous-optimization algorithm for large-scale single-commodity FCNFP based on an iteratively reweighted least-squares (IRLS) framework. The method replaces the discontinuous fixed-charge and linear arc cost objective with a smooth nonconvex Lasry–Lions surrogate and solves a sequence of weighted quadratic flow subproblems. Each subproblem is solved by a warm-started dual semismooth Newton method whose Newton systems have weighted graph-Laplacian structure, enabling the use of modern Laplacian solvers. To further improve the discovered arc supports of the challenging underlying combinatorial problem, we also develop an algorithmic variant that incorporates objective-driven perturbation restarts and an anchor-union restricted search that jointly leverages supports discovered by IRLS and by complementary FCNFP heuristics. Computational experiments on 410 benchmark, synthetic, and large-scale instances show that our method obtains the best objective quality among the evaluated scalable FCNFP algorithms, with a mean gap of $1.316\%$ to a time-limited MILP reference and a win-or-tie rate of $90.0\%$ among the non-MILP methods. The results indicate that combining smooth continuous optimization with support-level search is an effective strategy for producing high-quality feasible solutions to large-scale FCNFP.

We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Writing $p_{\mathrm{sil}}=\log_2(1+\sqrt{2})$, we prove an $\Omega\left(n^{-p_{\mathrm{sil}}-O(\sqrt{\log\log n/\log n})}\right)$ non-anytime lower bound. In the anytime setting, every infinite schedule has infinitely many horizons with error $\Omega\left(n^{-\frac{2p_{\mathrm{sil}}}{1+p_{\mathrm{sil}}}-O(\sqrt{\log\log n/\log n})}\right)$. Together with the silver-schedule upper bound [Altschuler and Parrilo, 2025] and the anytime upper bound [Zhang et al., 2025], our results determine the optimal polynomial convergence exponents in both settings.

Large linear programs can exceed the memory of a single compute node. Although first-order methods replace sparse factorizations with GPU-suited matrix-vector products, other solver phases can reintroduce a single-node memory limit. We present SHARDLP, a distributed GPU LP solver that keeps the matrix and primal-dual state partitioned from sharded input through solution output. On the Google PDLP benchmark, SHARDLP reaches the published criterion on nine of eleven instances, compared with eight in the published CPU PDLP study. On the largest benchmark, eight H200 GPUs solve a 1.185-billion-variable, 6.338-billion-nonzero LP in 9.9 minutes; the published CPU experiment reports 21.06 hours on different hardware. Beyond this benchmark, separately checked multi-node solves reach up to 13.604 billion variables and 40.807 billion nonzeros, while validated executions span up to 76 GPUs across 29 compute nodes. For column-partitioned solves, support-aware communication skips GPUs that store no coefficients for a row; on an LP with 2.76 billion nonzeros, it cuts modelled communication by 92.97% and improves solver time by 1.27x-1.52x

We establish a linear quantum query lower bound for high-accuracy convex optimization over an explicit family of $n$-dimensional ellipsoids. We focus on linear optimization with an explicitly given objective, where the feasible set is accessed through a membership oracle. We show that any algorithm that, for every unit linear objective, returns an exactly feasible point with additive objective error $\Theta(n^{-1/2})$ requires $\Omega(n)$ membership queries, where the ellipsoids are contained in the unit ball. The same lower bound can be shown to hold if the returned point is only required to be approximately feasible, within $\Theta(n^{-3/2})$ distance from the feasible set. This resolves an open question posed by Chakrabarti, Childs, Li, and Wu~(Quantum, 2020) and by van Apeldoorn, Gilyén, Gribling, and de Wolf~(Quantum, 2020). Coupled with the upper bounds in these papers, the query complexity of high-accuracy convex optimization is characterized tightly up to logarithmic factors. The proof is built around a lower bound for determinant computation that is derived via a novel polynomial method based on Fourier-rank. In the continuous matrix phase-query model, computing the determinant of a real $n\times n$ matrix requires at least $n/2$ matrix-vector product queries. The construction also yields an $\Omega(n)$ phase-query lower bound for estimating the minimum eigenvalue of a real symmetric $n\times n$ matrix to additive accuracy $\Theta(n^{-2})$. These results extend the determinant and minimum-eigenvalue lower bounds of Childs, Hung, and Li~(ICALP 2021) from finite fields to the real-valued setting. Based on the same constructions, we also prove an $\Omega(\min\{\sqrt\kappa,n\})$ gradient-query lower bound for constant-accuracy optimization of $1$-strongly convex and $\kappa$-smooth functions, which is optimal up to a logarithmic factor.

In this paper, we establish the well-posedness and exponential stability of a class of semilinear neutral abstract evolution equations with constant time delay. Two damping mechanisms are considered: frictional damping of the form $CC^*u_t$ and viscoelastic damping with memory. Under suitable assumptions, we prove global well-posedness and exponential decay of solutions for sufficiently small initial data. This result is of considerable importance, as it provides a unified framework for the analysis of a wide class of neutral systems arising in structural mechanics, seismic isolation, and control theory. The abstract results are illustrated by some concrete examples. The analysis relies on a combination of semigroup theory, energy estimates, Duhamel's formula, and Gronwall-type arguments.

This paper studies a time-inconsistent mixed regular-singular control problem in continuous time with non-exponential discount. We seek time-consistent equilibria in an intrapersonal game framework and propose a novel definition of regular-singular equilibrium where both regular and singular controls are unified via control laws. We establish a verification theorem to provide a sufficient condition of the equilibrium. Furthermore, we propose a novel concept of mild equilibrium for which perturbations are applied separately to the regular and singular control and give the mild verification theorem. We illustrate the applicability of the theory to the effort and dividend problem and obtain an explicit equilibrium depending on the effort and dividend thresholds under a mixture of exponential discount functions and a pseudo-exponential discount function by solving the extended Hamilton–Jacobi–Bellman (HJB) system. The convexity of the value function is rigorously established, and the equilibrium conditions are verified. In addition, we establish the existence of the effort and dividend thresholds under a mixture of exponential discount functions. Numerical results reveal the impacts of exogenous parameters on the effort and dividend thresholds and the equilibrium value function, along with their economic implications.