Constrained Optimization

Ask about this topic

Overview

The field studies how to optimize an objective over a feasible set, from convex programs and combinatorial problems to nonconvex models with complex or conflicting constraints. Classical approaches include projection and Frank–Wolfe methods, interior-point and augmented-Lagrangian algorithms, and evolutionary search; newer work also learns feasible solutions or uses neural projections and solver warm starts. Applications range from robotic trajectory planning and power-grid operation to fair machine learning, resource allocation, and scheduling. A central challenge is balancing scalable computation with reliable feasibility and convergence guarantees, especially for nonconvex or infeasible problems and settings without standard regularity conditions.

Latest papers

CardsList

342 papers40 papers in the last four weeks, up 29% on the four weeks before. 0.2% of all new papers.

May 24, 2026

Manifold-Constrained MPPI: Real-Time Sampling-Based Control for Nonlinear Equality-Constrained Robotic Systems

Sampling-based model predictive control methods, such as Model Predictive Path Integral (MPPI), offer derivative-free optimization and robustness in complex robotic systems. However, standard MPPI relies on cost-based soft penalties that cannot guarantee hard-constraint satisfaction, severely limiting its applicability to highly constrained tasks such as closed-chain manipulation. To address this, we propose Manifold-Constrained MPPI (MC-MPPI), a real-time sampling-based control framework that regulates nonlinear equality constraints while preserving the computational advantages of MPPI. The key idea is to decouple the constrained optimal control problem into latent-space planning and execution-level correction. At the planning stage, a Variational Autoencoder (VAE) learns a low-dimensional latent representation of the constraint manifold, enabling MPPI to efficiently generate near-feasible candidate trajectories without per-sample modification. Since this reference enables accurate linearization of the equality constraints, an execution-level Quadratic Programming (QP) controller resolves the residual manifold mismatch in a single solve rather than through iterative projection. Experiments on a 14-DoF closed-chain dual-arm system in both simulation and real-world settings demonstrate 100 Hz planning and 500 Hz execution, equality-residual regulation in static and dynamic environments, and a 95% success rate over 40 randomized hardware trials. Supplementary videos and implementation details are available at https://rcilab.github.io/mcmppi.

Seulchan Lee, Sanghyun Kim

School of Mechanical Engineering, Kyung Hee University, Yongin, South Korea

Robotic ControlConstrained Motion PlanningConstrained OptimizationMPPI Control
AskPDF
May 22, 2026

Scalable Heterogeneous Graph Foundation Models for Data-Driven Optimal Power Flow in Smart Grids

Fast and reliable optimal power flow (OPF) approximation is important for power system operation, yet heterogeneous OPF graph models are often evaluated either with architecture-specific implementations or on limited training corpora. This paper presents a large-scale heterogeneous graph-learning workflow, built on HydraGNN, for data-driven OPF surrogate modeling and graph foundation-model (GFM) development. The workflow preserves buses, generators, loads, shunts, alternating-current (AC) lines, transformers, and device-to-bus relations and provides a common implementation for distributed preprocessing, multi-graphics-processing-unit (GPU) training, hyperparameter optimization (HPO), and downstream adaptation. Using approximately three million heterogeneous graphs from ten Power Grid Library for Benchmarking AC Optimal Power Flow Algorithms (PGLib-OPF) cases spanning 14 to 13,659 buses, we compare six heterogeneous graph neural network (GNN) families under a common HPO campaign on Frontier, resulting in two compact HeteroSAGE and HeteroHEAT models (~1.6-1.7 million parameters) that achieve the lowest observed validation MSE. Strong and weak scaling using up to 1,024 Frontier nodes show that 256 nodes (corresponding to 1,024 AMD MI250X GPUs) provides the best time-to-solution balance for the measured workload. Two downstream tasks evaluate task adaptation on the IEEE 118-bus case: a classification task to distinguish nominal operating conditions from artificially generated extreme-overload conditions and N-1 single-component-outage regression to predict bus voltage magnitude and phase angle. Partial fine-tuning provides the strongest balance between predictive performance and computational requirements.

Massimiliano Lupo Pasini, Yijiang Li, Kibaek Kim +1

Computational Sciences and Engineering Division, Oak Ridge National Laboratory, 1 Bethel Valley Road, Oak Ridge, TN 37831, USA

Neural Surrogate ModelingHeterogeneous GNNsOptimal Power FlowGraph Foundation ModelsConstrained OptimizationPower Systems
AskPDF
May 21, 2026

From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal kk-Sparse GLMs

GPUs have significantly accelerated first-order methods for large-scale optimization, especially in continuous optimization. However, this success has not transferred cleanly to problems with discrete variables, combinatorial structure, and nonlinear objectives, such as certifying optimal solutions for cardinality-constrained generalized linear models. Major challenges include the sequential processing of heterogeneous nodes in branch and bound (BnB) and frequent data movement between the CPU and GPU. We propose a simple, generic, and modular CPU--GPU framework that processes multiple BnB nodes in batches on GPUs. The framework is built around a small set of GPU-efficient routines and uses padding together with lightweight custom kernels to handle irregular node data structures. Experiments show one to two orders of magnitude speedups and zero optimality gap on challenging instances. The framework can also be extended to collect the entire Rashomon set, enabling downstream statistical analysis such as variable-importance analysis and model selection under secondary user-specific measures (e.g., AUC in classification).

Jiachang Liu, Andrea Lodi

∗Center for Data Science for Enterprise and Society, Cornell University, Ithaca, USA · †School of Operations Research and Information Engineering, Cornell University, Ithaca, USA · ‡Jacobs Technion-Cornell Institute, Cornell Tech and Technion–IIT, New York, USA

Branch and BoundGPU Kernel OptimizationGPU AccelerationHigh-Performance ComputingCombinatorial OptimizationConstrained Optimization+1
AskPDF
May 20, 2026

CMC-Opt: Constraint Manifold with Corners for Inequality-Constrained Optimization

We introduce a manifold-based framework for addressing optimization problems with equality and inequality constraints found in robotics. Our approach transforms the original problem into an unconstrained optimization problem directly on the constrained state space. To achieve this, we introduce ``constraint manifolds with corners" to represent the state space satisfying mixed nonlinear equality and inequality constraints. We further extend manifold optimization algorithms to operate on this new topological structure. We demonstrate the power and robustness of our framework in the context of a large-scale kinodynamic planning problem, successfully generating dynamically feasible trajectories where standard methods fail.

Yetong Zhang, Frank Dellaert

College of Computing Georgia Institute of Technology Atlanta, USA

Kinodynamic Motion PlanningRiemannian OptimizationConstrained OptimizationMotion PlanningRobot Motion PlanningRobotic Optimization
AskPDF
May 20, 2026

Time-Dependent PDE-Constrained Optimization via Weak-Form Latent Dynamics

Optimization problems constrained by high-dimensional, time-dependent partial differential equations require repeated forward and sensitivity solves, making high-fidelity optimization computationally prohibitive in many-query design and control settings. We present a weak-form latent-space reduced-order modeling framework for accelerating gradient-based PDE-constrained optimization. The proposed approach builds on Weak-form Latent Space Dynamics Identification (WLaSDI), which compresses high-dimensional solution trajectories into a low-dimensional latent representation and identifies parametric latent dynamics using weak-form system identification. By avoiding explicit numerical differentiation of training trajectories, the weak-form improves robustness to noisy data and yields more reliable surrogate dynamics for optimization. We formulate the resulting reduced PDE-constrained optimization problem and derive both direct-sensitivity and adjoint-based gradient expressions for the learned latent dynamics, enabling scalable gradient evaluation with respect to design parameters. The framework is demonstrated on three time-dependent benchmark problems: thermal radiative transfer for optimal hohlraum design, the two-stream instability Vlasov-Poisson system, and the inviscid Burgers equation. Across these examples, WLaSDI produces accurate optimal designs, remains robust under noisy training data, and delivers substantial computational savings, including speedups of up to five orders of magnitude relative to full-order optimization. These results demonstrate that weak-form latent dynamics provide an efficient and noise-robust surrogate foundation for gradient-based optimization of complex time-dependent PDE systems.

April Tran, Terry Haut, David Bortz +1

Department of Applied Mathematics, University of Colorado, Boulder, CO, 80309, USA · Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, 94550, CA, USA

Latent Dynamics ModelingPDE Surrogate ModelingSystem IdentificationReduced-Order ModelingConstrained Optimization
AskPDF
May 19, 2026

Exploiting Non-Negativity in DAG Structure Learning

This work addresses the problem of learning directed acyclic graphs (DAGs) from nodal observations adhering to a linear structural equation model. DAG structure learning is a central task in signal processing, machine learning, and causal inference, but it remains challenging because acyclicity is a global combinatorial property and the search space grows superexponentially in the number of nodes. Continuous acyclicity characterizations have led to important algorithmic advances by replacing the discrete DAG restriction with smooth equality constraints on the candidate adjacency matrix. However, existing formulations still involve difficult non-convex optimization landscapes and may suffer from degenerate first-order optimality conditions. Here, we restrict attention to DAGs with non-negative edge weights and exploit this additional structure to obtain a simpler acyclicity characterization devoid of Hadamard products. We propose a new non-negative constrained DAG estimator and develop a tractable, locally convergent algorithm based on the method of multipliers. We further analyze the benign optimization landscape induced by the non-negativity constraints. In the large-sample regime, we show that the true DAG is the unique global minimizer of the population augmented Lagrangian. Moreover, the landscape contains no spurious interior stationary points, and the true DAG is the only acyclic Karush--Kuhn--Tucker (KKT) point. Critically, this allows us to guarantee local convergence to the true DAG given infinite samples. Comprehensive numerical experiments show that the proposed structure identification method improves over state-of-the-art continuous DAG-learning baselines.

Samuel Rey, Madeline navarro, Santiago Segarra +1

Dept. of Electrical and Computer Engineering, University of Rochester, Rochester, NY 14627, USA

Graph Structure LearningStructural Causal ModelsCausal Structure LearningNonconvex OptimizationAugmented Lagrangian MethodConstrained Optimization
AskPDF
May 19, 2026

From SGD to Muon: Adaptive Optimization via Schatten-p Norms

Modern optimizers, like Muon, impose matrix-wise geometry constraints on their updates. These matrix-wise constraints can be unified under Linear Minimization Oracle (LMO) theory. However, all current methods impose fixed LMO geometries for the update rules, chosen by-design or empirically, which are not necessarily optimal according to the problem's geometry. We introduce a novel efficient datadriven criterion for dynamically choosing proxy-optimal update LMO geometries on individual Deep Neural Network layers. Derived in closed form from gradient and activation statistics using a single-step random feature regression surrogate model, our criterion navigates a design space interpolating from SGD to Muon updates. Moreover, integrating parameter-wise preconditioning allows our framework to recover SGD, Muon, Adam, and MuAdam as specific extrema. To make this adaptive approach scalable, we pair it with efficient computational strategies, achieving only a ∼\sim 3% runtime overhead on highly optimized baselines. As a proof of concept, we show that this data-driven optimizer beats or remains competitive with the performance of the best performing optimizer between Muon and AdamW across three different training scenarios. Ultimately, this work provides evidence that LMO geometry can be successfully and efficiently adapted from runtime data, opening a new pathway for optimizer design beyond static geometries.

Thomas Massena, Corentin Friedrich, Mathieu Serrurier

DTIPG - SNCF, IRIT · IRIT

LMO MethodsNeural Network OptimizationMuon OptimizerConstrained OptimizationAdaptive Gradient Methods
AskPDF
May 19, 2026

An Exterior Method for Nonnegative Matrix Factorization

Nonnegative matrix factorization (NMF) seeks a low-rank approximation X≈UVTX \approx UV^T with nonnegative factors and is commonly solved using interior methods that enforce feasibility throughout optimization. We show that such constraint-driven approaches can impede progress in the nonconvex landscape, leading to slow convergence or convergence to suboptimal stationary points. We propose an exterior framework for NMF (eNMF) that separates low-rank approximation from nonnegativity enforcement. Our method initializes from the optimal unconstrained factorization and introduces a rotation procedure that maps unconstrained factors to an exterior point closest to the nonnegative orthant. This viewpoint yields an algorithmic framework in which simple iterative updates converge to KKT-satisfying stationary points on the boundary of the positive orthant. The exterior formulation also enables a geometric interpretation of NMF solutions, clarifying equivalence classes of factorizations under permutation and orthogonal transformations. An intriguing numerical result, involving 400 NMF experiments across both real and synthetic datasets, show that in 99% of the cases, different algorithms tend to converge towards equivalent factor matrices. We benchmark eNMF against 9 state-of-the-art NMF algorithms with 9 initialization schemes across 3 real-world and 2 synthetic datasets. eNMF consistently outperforms all 81 competitors, achieving up to 30% lower reconstruction error under equal-time settings and up to 150% speedup under equal-error settings. The downstream experiments further demonstrate substantial performance gains in audio processing and recommendation tasks, corroborating the practical benefits of the proposed exterior optimization framework. Code is available at https://github.com/roychowdhuryresearch/eNMF

Qiujing Lu, Tonmoy Monsoor, Ehsan Ebrahimzadeh +2

1ECE, UCLA · 2eBay Search Science Team

Non-Negative Matrix FactorizationLow-Rank Matrix DecompositionNonconvex OptimizationLow-Rank ApproximationConstrained OptimizationMatrix Optimization
AskPDF
May 18, 2026

Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming

Lagrangian Relaxation (LR) is a powerful technique for solving large-scale Mixed Integer Linear Programming (MILP), particularly those with decomposable structures, such as vehicle routing or unit commitment problems. By relaxing the coupling constraints, LR enables parallel subproblem solving and often yields tighter dual bounds than standard linear programming relaxations, which is crucial for efficient branch-and-bound pruning. While recent empirical work has shown promising results using machine learning to predict these multipliers, a theoretical understanding of such methods remains an open question. In this work, we bridge this gap by analyzing the problem of learning LR through the lens of Data-driven Algorithm Design, i.e., a statistical learning problem over a distribution of problem instances. Our contributions are as follows: first, we derive a generalization bound of O(s1.5/N)\mathcal{O}(s^{1.5}/\sqrt{N}) for the learned multipliers, where ss is the number of coupling constraints and NN is the sample size. Second, we provide a minimax lower-bound of Ω(s/N)Ω(s/\sqrt{N}), proving that a linear dependency is unavoidable. Third, we constructively close this theoretical gap by proving that Stochastic Gradient Ascent (SGA) with averaging achieves the minimax optimal rate Θ(s/N)Θ(s/\sqrt{N}). Finally, we extend our framework to the learning-to-warm-start setting, proving that it achieves a fast, minimax-optimal rate of Θ(s/N)Θ(s/N) and establishing a theoretical advantage over direct multiplier prediction.

Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen

Université Grenoble Alpes, LJK, CNRS, Grenoble INP, 38000 Grenoble, France · Carnegie Mellon University, Machine Learning Department · Chinese University of Hong Kong, Department of Systems Engineering and Engineering Management.

Mixed-Integer Linear ProgrammingLearning to OptimizeConstrained OptimizationLinear ProgrammingLearning-Augmented Algorithms
AskPDF
May 18, 2026

Stochastic Penalty-Barrier Method for Constrained Machine Learning

Constrained Machine Learning (CML) enables fairness-aware training, physics-informed neural networks, and integration of symbolic domain knowledge into statistical models. In this work, we introduce the Stochastic Penalty-Barrier Method (SPBM) for CML problems. SPBM extends classical penalty and barrier methods by incorporating an exponential averaging of the dual variables, a stabilized penalty schedule, and the Moreau envelope to handle non-smoothness. We analyze the bias that mini-batching introduces in the barrier function and show that the feasible set of the resulting transformed problem is contained within the original one. We compare SPBM with CML baselines across multiple fairness and physics informed neural networks experiments. We find that SPBM is competitive with state-of-the-art methods. We also observe, on our fairness-based computational benchmark, that the per-epoch runtime of CML methods is largely independent of the number of constraints, and within 1.3×1.3\times of the per-epoch runtime of regularized Adam, for a number of constraints ranging from 9090 to 99009900.

Adam Bosák, Andrii Kliachkin, Gilles Bareilles +4

Artificial Intelligence Center, CTU in Prague · CMAP, École Polytechnique, Palaiseau, France

Constrained Optimization
AskPDF
May 18, 2026

New Insight of Variance reduce in Zero-Order Hard-Thresholding: Mitigating Gradient Error and Expansivity Contradictions

Hard-thresholding is an important type of algorithm in machine learning that is used to solve ℓ0\ell_0 constrained optimization problems. However, the true gradient of the objective function can be difficult to access in certain scenarios, which normally can be approximated by zeroth-order (ZO) methods. The SZOHT algorithm is the only algorithm tackling ℓ0\ell_0 sparsity constraints with ZO gradients so far. Unfortunately, SZOHT has a notable limitation on the number of random directions % in ZO gradients due to the inherent conflict between the deviation of ZO gradients and the expansivity of the hard-thresholding operator. This paper approaches this problem by considering the role of variance and provides a new insight into variance reduction: mitigating the unique conflicts between ZO gradients and hard-thresholding. Under this perspective, we propose a generalized variance reduced ZO hard-thresholding algorithm as well as the generalized convergence analysis under standard assumptions. The theoretical results demonstrate the new algorithm eliminates the restrictions on the number of random directions, leading to improved convergence rates and broader applicability compared with SZOHT. Finally, we illustrate the utility of our method on a ridge regression problem as well as black-box adversarial attacks.

Xinzhe Yuan, William de Vazelhes, Bin Gu +1

Harbin Institute of Technology · IASM, Harbin Institute of Technology · Mohamed bin Zayed University of Artificial Intelligence +2

Zeroth-Order OptimizationConstrained OptimizationVariance Reduction
AskPDF
May 18, 2026

Adaptive Stochastic Natural Gradient Method for Safe Optimization on Binary Space

Optimization problems in real-world applications across the medical and engineering domains often involve potential risks when evaluating candidate solutions. Safe optimization aims to perform optimization while suppressing unsafe solution evaluations in such situations. For continuous search spaces, there exist safe optimization methods based on evolutionary computation. However, the algorithm development of safe optimization methods for binary search spaces has not been adequately addressed. In this study, we incorporate additional mechanisms for safe optimization into a binary optimization method, the adaptive stochastic natural gradient method (ASNG) with a family of Bernoulli distributions. For safety functions that must be kept non-negative during optimization, the proposed method, safe ASNG, estimates the Lipschitz constants with respect to the Hamming distance by constructing surrogate models of safety functions based on discrete Walsh functions. Then, safe ASNG computes a safe region that consists of safe solutions around the previously evaluated safe solutions. By projecting newly generated solutions to their nearest neighbors within the safe region, safe ASNG suppresses unsafe solution evaluations. Experimental results on benchmark problems on binary domains confirm that, while the comparative methods fail to suppress unsafe solution evaluations, safe ASNG achieves efficient optimization while effectively suppressing unsafe solution evaluations.

Kento Uchida, Ryoki Hamano, Masahiro Nomura +1

Yokohama National University Yokohama, Kanagawa, Japan · CyberAgent Shibuya, Tokyo, Japan · Institute of Science Tokyo Meguro, Tokyo, Japan

Black-Box OptimizationNatural Gradient MethodsConstrained Optimization
AskPDF
May 14, 2026

Stochastic Compositional Optimization via Hybrid Momentum Frank--Wolfe

Stochastic compositional optimization minimizes F(f(x),x)F(f(x), x) over a compact convex set when the inner map ff is available only through noisy samples. We propose Hybrid Momentum Stochastic Frank--Wolfe, a projection-free method for outer functions FF that are jointly convex and Lipschitz but not necessarily differentiable, such as maxima, CVaR, and norms. The method tracks the Jacobian and the value of ff with momentum, using a Taylor correction for the value, and passes the tracked linearization to a generalized linear minimization oracle. Under finite-variance noise, it attains an expected generalized Frank--Wolfe gap of order K−1/4K^{-1/4} for non-convex objectives and, when the linearized models minorize the objective, a last-iterate primal error of order K−1/3K^{-1/3}. The analysis extends to heavy-tailed noise without clipping, with separate moment orders for values and Jacobians. With an exact oracle, the method reduces to the deterministic method of Vladarean et al. (2023).

El Mahdi Chayti, Mohamad Fakhouri

Machine Learning and Optimization Laboratory (MLO) EPFL, Switzerland

Stochastic OptimizationMomentum MethodsNonconvex Stochastic OptimizationConstrained Optimization
AskPDF
May 13, 2026

TinySDP: Real Time Semidefinite Optimization for Certifiable and Agile Edge Robotics

Semidefinite programming (SDP) provides a principled framework for convex relaxations of nonconvex geometric constraints in motion planning, yet existing solvers are too computationally expensive for real-time control, particularly on resource-constrained embedded systems. To address this gap, we introduce TinySDP, the first semidefinite programming solver designed for embedded systems, enabling real-time model-predictive control (MPC) on microcontrollers for problems with nonconvex obstacle constraints. Our approach integrates positive-semidefinite cone projections into a cached-Riccati-based ADMM solver, leveraging computational structure for embedded tractability. We pair this solver with an a posteriori rank-1 certificate that converts relaxed solutions into explicit geometric guarantees at each timestep. On challenging benchmarks, e.g., cul-de-sac and dynamic obstacle avoidance scenarios that induce failures in local methods, TinySDP achieves collision-free navigation with up to 73% shorter paths than state-of-the-art baselines. We validate our approach on a Crazyflie quadrotor, demonstrating that semidefinite constraints can be enforced at real-time rates for agile embedded robotics.

Ishaan Mahajan, Jon Arrizabalaga, Andrea Grillo +4

Columbia University, USA · Massachusetts Institute of Technology, USA · ´Ecole Polytechnique F´ed´erale de Lausanne (EPFL), Switzerland +1

Semidefinite ProgrammingConstrained Motion PlanningRoboticsModel Predictive ControlConstrained OptimizationSafe Motion Planning
AskPDF
May 12, 2026

Optimal Policy Learning under Budget and Coverage Constraints

We study optimal policy learning under combined budget and minimum coverage constraints. We show that the problem admits a knapsack-type structure and that the optimal policy can be characterized by an affine threshold rule involving both budget and coverage shadow prices. We establish that the linear programming relaxation of the combinatorial solution has an O(1) integrality gap, implying asymptotic equivalence with the optimal discrete allocation. Building on this result, we analyze two implementable approaches: a Greedy-Lagrangian (GLC) and a rank-and-cut (RC) algorithm. We show that the GLC closely approximates the optimal solution and achieves near-optimal performance in finite samples. By contrast, RC is approximately optimal whenever the coverage constraint is slack or costs are homogeneous, while misallocation arises only when cost heterogeneity interacts with a binding coverage constraint. Monte Carlo evidence supports these findings.

Giovanni Cerulli

CNR-IRCrES · National Research Council of Italy · Research Institute on Sustainable Economic Growth

Policy OptimizationCombinatorial OptimizationConstrained RLConstrained Optimization
AskPDF
May 12, 2026

Large Language Models as Amortized Pareto-Front Generators for Constrained Bi-Objective Convex Optimization

Generating feasible Pareto fronts for constrained bi-objective continuous optimization is central to multi-criteria decision-making. Existing methods usually rely on iterative scalarization, evolutionary search, or problem-specific solvers, requiring repeated optimization for each instance. We introduce DIPS, an end-to-end framework that fine-tunes large language models as amortized Pareto-front generators for constrained bi-objective convex optimization. Given a textual problem description, DIPS directly outputs an ordered set of feasible continuous decision vectors approximating the Pareto front. To make continuous optimization compatible with autoregressive language modeling, DIPS combines a compact discretization scheme, Numerically Grounded Token Initialization for new numerical tokens, and Three-Phase Curriculum Optimization, which progressively aligns structural validity, feasibility, and Pareto-front quality. Across five families of constrained bi-objective convex problems, a fine-tuned 7B-parameter model achieves normalized hypervolume ratios of 95.29% to 98.18% relative to reference fronts. With vLLM-accelerated inference, DIPS solves one instance in as little as 0.16 seconds and outperforms general-purpose and reasoning LLM baselines under the evaluated setting. These results suggest that LLMs can serve as effective amortized generators for continuous Pareto-front approximation.

Peipei Xu, SiYuan Ma, Yaohua Liu +4

University of Shanghai for Science and Technology · The Hong Kong University of Science and Technology

Large Language Model-Guided OptimizationConstrained OptimizationMulti-Objective OptimizationPareto Optimization
AskPDF
May 12, 2026

Constrained Stochastic Spectral Preconditioning Converges for Nonconvex Objectives

In this work, we develop proximal preconditioned gradient methods with a focus on spectral gradient methods providing a proximal extension to the Muon and Scion optimizers. We introduce a family of stochastic algorithms that can handle a wide variety of convex and nonconvex constraints and study its convergence under heavy-tailed noise, through a novel analysis tailored to the geometry of the proposed methods. We further propose a variance-reduced version, which achieves faster convergence under standard noise assumptions. Finally, we show that the polynomial iterations used in Muon are more accurately captured by a nonlinear preconditioner than by the ideal matrix sign, leading to a convergence analysis that more faithfully reflects practical implementations.

Konstantinos Oikonomidis, Jan Quan, Kimon Antonakopoulos +3

KU Leuven, Department of Electrical Engineering, STADIUS Center for Dynamical Systems, Signal Processing, and Data Analytics · ´Ecole Polytechnique F´ed´erale de Lausanne (EPFL), Laboratory for Information and Inference Systems (LIONS) · CVN, CentraleSup´elec, Universit´e Paris-Saclay, Inria

Nonconvex Stochastic OptimizationMuon OptimizerConstrained OptimizationStochastic Optimization ConvergenceSpectral Optimization
AskPDF
May 12, 2026

GAR: Carbon-Aware Routing for LLM Inference via Constrained Optimization

The growing deployment of large language models (LLMs) makes per-request routing essential for balancing response quality and computational cost across heterogeneous model pools. Current routing methods rarely consider sustainable energy use and CO2 emissions as optimization objectives, despite grid carbon intensity varying by time and region, and models differing significantly in energy consumption. To address this gap, we introduce Green-Aware Routing (GAR), a constrained multi-objective optimization framework that minimizes per-request CO2 emissions subject to explicit accuracy floors and p95-latency service-level objectives (SLOs). GAR employs adaptive constraint optimization through per-dataset floor tuning and incorporates lightweight estimators for correctness, tail latency, and carbon emissions, enabling real-time routing decisions without additional inference passes. We present GAR-PD, a practical online primal-dual routing algorithm for rolling carbon budgets, alongside heuristic variants that achieve high feasibility coverage while limiting accuracy degradation. Comprehensive experiments across standard NLP benchmarks with heterogeneous LLM pools (7B-70B) demonstrate that GAR achieves substantial carbon reductions while maintaining competitive accuracy and p95 latency guarantees, providing a practical, theoretically grounded approach to sustainable LLM inference.

Disha Sheshanarayana, Rajat Subhra Pal, Manjira Sinha +1

Manipal University Jaipur · TCS Research

LLM Inference EfficiencyConstrained OptimizationLLM RoutingCarbon-Aware Computing
AskPDF
May 12, 2026

Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses

Existing work on linear constrained Markov decision processes (CMDPs) has primarily focused on stochastic settings, where the losses and costs are either fixed or drawn from fixed distributions. However, such formulations are inherently vulnerable to adversarially changing environments. To overcome this limitation, we propose a primal-dual policy optimization algorithm for online finite-horizon {adversarial} linear CMDPs, where the losses are adversarially chosen under full-information feedback and the costs are stochastic under bandit feedback. Our algorithm is the first to achieve sublinear regret and constraint violation bounds in this setting, both bounded by O~(K3/4)\widetilde{\mathcal{O}}(K^{3/4}), where KK denotes the number of episodes. The algorithm introduces and runs with a new class of policies, which we call weighted LogSumExp softmax policies, designed to adapt to adversarially chosen loss functions. Our main result stems from the following key contributions: (i) a new covering number argument for the weighted LogSumExp softmax policies, and (ii) two novel algorithmic components -- periodic policy mixing and a regularized dual update -- which allow us to effectively control both the covering number and the dual variable. We also report numerical results that validate our theoretical findings on the performance of the algorithm.

Kihyun Yu, Seoungbin Bae, Dabeen Lee

Department of Industrial and Systems Engineering KAIST · Department of Mathematical Sciences Seoul National University · Research Institute of Mathematics, Seoul National University; Interdisciplinary Program in Artificial Intelligence, Seoul National University; Korea Institute for Advanced Study

Primal-Dual OptimizationMarkov Decision ProcessesPolicy OptimizationConstrained RLConstrained Optimization
AskPDF
May 12, 2026

Efficient and provably convergent end-to-end training of deep neural networks with linear constraints

Training a deep neural network with the outputs of selected layers satisfying linear constraints is required in many contemporary data-driven applications. While this can be achieved by incorporating projection layers into the neural network, its end-to-end training remains challenging due to the lack of rigorous theory and efficient algorithms for backpropagation. A key difficulty in developing the theory and efficient algorithms for backpropagation arose from the nonsmoothness of the solution mapping of the projection layer. To address this bottleneck, we introduce an efficiently computable HS-Jacobian to the projection layer. Importantly, we prove that the HS-Jacobian is a conservative mapping for the projection operator onto the polyhedral set, enabling its seamless integration into the nonsmooth automatic differentiation framework for backpropagation. Therefore, many efficient algorithms, such as Adam, can be applied for end-to-end training of deep neural networks with linear constraints. Particularly, we establish convergence guarantees of the HS-Jacobian based Adam algorithm for training linearly constrained deep neural networks. Extensive experiment results on several important applications, including finance, computer vision, and network architecture design, demonstrate the superior performance of our method compared to other existing popular methods.

Zonglin Yang, Zhexuan Gu, Yancheng Yuan

Department of Applied Mathematics, The Hong Kong Polytechnic University, Hung Hom, Hong Kong

Deep Learning OptimizationBackpropagationConstrained Optimization
AskPDF
May 11, 2026

ADMM-Q: An Improved Hessian-based Weight Quantizer for Post-Training Quantization of Large Language Models

Quantization is an effective strategy to reduce the storage and computation footprint of large language models (LLMs). Post-training quantization (PTQ) is a leading approach for compressing LLMs. Popular weight quantization procedures, including GPTQ and RTN, suffer in model utility, especially at aggressive quantization levels (sub-4-bit). We propose ADMM-Q, a novel weight quantization algorithm that considers the layer-wise quantization problem. Our algorithm is based on a combinatorial variant of the Alternating Direction Method of Multipliers (ADMM). Our operator-splitting procedure updates weights continuously to minimize the layer-wise reconstruction error, while gradually enforcing the quantization constraints with convergence guarantees. We propose additional algorithmic enhancements (e.g., penalty scheduling, preconditioning, and a local search post-processing step) to make ADMM-Q efficient at LLM scale. ADMM-Q is modular and can be used as a drop-in replacement for any weight quantizer within existing quantization pipelines: ADMM-Q is fully composable with existing techniques including range clipping, learned or random rotations, and activation scaling. Using ADMM-Q in place of GPTQ on Qwen3-8B, we decrease WikiText-2 perplexity in: (i) the W3A16 weight-only setting (12.85 →\rightarrow 10.06); (ii) the W4A8 SmoothQuant procedure (9.29 →\rightarrow 8.68); and (iii) the W2A4KV4 SpinQuant procedure (66.11 →\rightarrow 19.42).

Ryan Lucas, Mehdi Makni, Xiang Meng +2

MIT Operations Research Center · MIT Sloan School of Management · MIT Center for Statistics

LLM QuantizationAlternating Direction Method of MultipliersConstrained OptimizationPost-Training QuantizationLow-Bit QuantizationNeural Network Quantization
AskPDF
May 11, 2026

Exact Fixed-Point Constraints in Neural-ODEs with Provable Universality

We introduce a technique that enables Neural-ODEs to approximate arbitrary velocity fields with a priori planted fixed-points. Specifically, a recipe is given to explicitly accommodate for a finite collection of points in the reference multi-dimensional space of the Neural-ODE where the velocity field is exactly equal to zero. In this way, the gradient-based training is rigorously constrained inside the prescribed hypothesis class while leaving the expressive power of the Neural-ODE unaltered. We rigorously prove the universality of the Neural-ODE under any local constraints in the velocity field and give a computationally convenient way of imposing the fixed points. Our method is then tested on two paradigmatic physical models.

Feliciano Giuseppe Pacifico, Duccio Fanelli, Lorenzo Buffoni +3

Department of Informatics and Computer Science, University of Pisa, Italy · Department of Physics and Astronomy and INFN, University of Florence, Sesto Fiorentino, Italy

Constrained OptimizationNeural Network Approximation TheoryNeural ODEs
AskPDF
May 11, 2026

Meta-Black-Box Optimization Can Do Search Guidance for Expensive Constrained Multi-Objective Optimization

Existing Meta-Black-Box Optimization (MetaBBO) methods focus on how to search when controlling optimizers, but largely overlook where to search. We propose MetaSG-SAEA, a bi-level MetaBBO framework for expensive constrained multi-objective optimization problems (ECMOPs), in which a meta-policy provides search guidance to the low-level Surrogate-Assisted Evolutionary Algorithm (SAEA). To achieve this, we introduce Max-Min Constraint-Calibrated Inequality (MM-CCI), a compact, problem-agnostic region abstraction that maps heterogeneous constraint evaluations to an ordered scalar level; we further provide a theoretical analysis of its fundamental properties. Building on this region abstraction, we adopt diffusion-based population initialization to translate the meta-policy's region-level guidance into solution-level priors for the SAEA. To make MetaSG-SAEA scalable, we construct an attention-based state representation across varying problem dimensions, population sizes, and numbers of objectives and constraints. Experimental results demonstrate that MetaSG-SAEA outperforms state-of-the-art baselines across diverse benchmarks and exhibits the ability to generalize across problem distributions.

Yukun Du, Haiyue Yu, Jiang Jiang +5

National University of Defense Technology, Changsha, Hunan, China.

Constrained OptimizationMulti-Objective Optimization
AskPDF
May 11, 2026

From Single-Step Edit Response to Multi-Step Molecular Optimization

Conditional molecular optimization aims to edit a molecule to realize a specified property shift. In practice, structurally similar molecule data is scarce, while decisions are inherently action-level: at each step, the system must select one local structural edit from a candidate set that is strictly filtered by chemical feasibility rules. This level mismatch between supervision and decision makes oracle-in-the-loop search unstable in molecular optimization. Regressing on property differences between molecule pairs improves data efficiency but relies on oracle-in-the-loop search, entangling transformation effects with global context and providing limited guidance for selecting the next feasible edit, often resorting to oracle-in-the-loop search. For this reason, we propose a response-oriented discrete edit optimization approach comprising two tightly coupled components: a single-step molecular edit response predictor (SMER) and a multi-step planner that composes local predictions into optimization trajectories via guided tree search (SMER-Opt). The approach learns a directional evaluation model over edit actions to support constraint-aware planning. It mines weakly related molecule pairs and decomposes their structural differences into minimal edit units, turning endpoint property annotations into process-level supervision and yielding reusable, transferable action primitives. A directional edit evaluator then scores feasible candidate edits by their likelihood of moving the molecule toward the desired property change, substantially reducing dependence on external evaluator queries at decision time. Code is available at https://anonymous.4open.science/r/SMER.

Haojie Rao, Kun Li, Yida Xiong +5

School of Computer Science, Wuhan University, Wuhan, China · School of Computer Science, Wuhan University Wuhan, China · Department of Data Science and Artificial Intelligence, Monash University, Victoria, Australia +5

Molecular OptimizationConstrained Optimization
AskPDF
May 11, 2026

Selection of the Best Policy under Fairness Constraints for Subpopulations

Many high-stakes decisions in health care, public policy, and clinical development require committing to a single policy that will be applied uniformly across a heterogeneous population. Regulatory and fairness standards sometime requires that the chosen policy performs adequately in every pre-specified subpopulation, not only on average. We formalize this as a Selection of the Best with Fairness Constraints (SBFC) problem, in order to identify the policy with the highest average performance among those policies that meet a minimum per-subpopulation threshold. We establish an instance-specific lower bound on sample complexity of the SBFC problem. We then develop a Track-and-Stop with Constraints on Subpopulation (T-a-S-CS) algorithm that achieves the lower bound asymptotically. We extend the framework to general closed-set and penalty-based fairness specifications with matching guarantees. Numerical experiments and a case study using the International Stroke Trial demonstrate substantial efficiency gains over policy-level allocation baselines.

Tingyu Zhu, Yuhang Wu, Zeyu Zheng

Department of Industrial Engineering and Operations Research & Berkeley Artificial Intelligence Research Lab University of California Berkeley

Multi-Armed BanditsGroup FairnessBest-Arm IdentificationConstrained Optimization
AskPDF
May 10, 2026

Primal-Dual Guided Decoding for Constrained Discrete Diffusion

Discrete diffusion models generate structured sequences by progressively unmasking tokens, but enforcing global property constraints during generation remains an open challenge. We propose primal-dual guided decoding, an inference-time method that formulates constrained generation as a KL-regularised optimisation problem and solves it online via adaptive Lagrangian multipliers. At each denoising step, the method modifies token logits through an additive, constraint-dependent bias, with multipliers updated by mirror descent based on constraint violation. The bias arises as the optimal KL-regularised projection of the constraint, so the constrained distribution remains as close as possible to the model's unconstrained distribution while still satisfying the constraint. The method requires no retraining and no additional model evaluations beyond standard sampling, supports multiple simultaneous constraints, and provides formal bounds on constraint violation. We evaluate our approach on topical text generation, molecular design, and music playlist generation, showing that a single algorithm instantiated via domain-specific scoring functions improves constraint satisfaction while preserving relevant domain-specific quality metrics.

Federico Tomasi, Dmitrii Moor, Alice Wang +1

Spotify

Primal-Dual OptimizationConstrained Generative ModelingConstrained DecodingDiffusion GuidanceConstrained OptimizationDiffusion Models+1
AskPDF
May 10, 2026

RDEx-CASK: Cauchy Mutation, Archive, and Stagnation Kick for RDEx-CSOP

We extend RDEx-CSOP with 3 changes that target stagnation & late-stage variance, plus minor parameter tuning. The second scale factor in the standard branch is sampled independently from a truncated Cauchy. A small feasible-only JADE-style archive (|A|_max = 50) is added & sampled with probability |A|/(|A|+|P|). Per-individual stagnation counter triggers, after 180 no-improvement generations, three local overrides on standard branch: pull toward the global best, lift the archive sampling floor to 0.65, & saturate CR to 0.95 when population success rate is below 0.10. The exploitation biased branch & every other RDEx component are left untouched. On CEC CSOP suite (D=30, 25 runs), RDEx-CASK is competitive with RDEx, UDE-III, & CL-SRDE in feasibility-aware quality & improves time-to-target on most problems.

Dikshant, Dikshit Chauhan, Chen Hao +3

Differential EvolutionEvolutionary OptimizationGlobal OptimizationConstrained Optimization
AskPDF
May 10, 2026

Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctions

The transition to First-Price Auctions (FPA) in digital advertising has spurred significant research, yet existing work typically assumes access to a valuation oracle, ignoring the reality that values must be inferred from censored data. While Linear Treatment Effect (LTE) models address this by learning value uplift, they have not been adapted to realistic settings with hard Budget constraints or Return-on-Spend (RoS) targets requiring regret and violation control. In this work, we propose a unified primal-dual framework for constrained FPAs that jointly learns the latent LTE valuation parameters and the competitor's bid distribution. This simultaneous learning introduces a critical technical challenge: the estimation error is dynamically scaled by the Lagrangian multiplier, potentially leading to unbounded regret. We resolve this by leveraging a strong Slater condition and a novel adaptive burn-in procedure to stabilize the dual variables. Our approach achieves near-optimal regret guarantees, providing the first theoretically grounded solution for constrained bidding with latent valuations.

Zihao Hu, Yuxiao Wen, Yuan Yao +2

Department of Mathematics, The Hong Kong University of Science and Technology · Department of IEDA, The Hong Kong University of Science and Technology · Stern School of Business, New York University

Primal-Dual OptimizationConstrained Optimization
AskPDF
May 10, 2026

Mismatch-Aware Adaptive Constraint Tightening for Bicycle-Model Trajectory Optimization

Trajectory optimization for autonomous vehicles usually relies on the kinematic bicycle model because of its computational simplicity. However, when the planned trajectory is executed under the true vehicle dynamics, which include lateral slip, tire stiffness and yaw-lateral coupling, safety constraints can be violated owing to the model mismatch. In this paper, we make three theoretical contributions. First, we derive a characteristic speed vc=CαL/Mv_c=\sqrt{C_αL/M} which separates two different mismatch regimes: below vcv_c the dynamic bicycle initially oversteers inward (safe); above vcv_c it understeers outward (safety-critical). Second, we prove that the peak outward deviation ε∗\varepsilon^* follows a T2T^2 horizon scaling whose coefficient transitions between a transient bound 12(v2−vc2)κ\frac{1}{2}(v^2-v_c^2)κ and a steady-state bound. Third, we obtain a simulation-free analytical coefficient a2anal=12(1−vc2/vmax⁡2)T2a_2^{\mathrm{anal}}=\frac{1}{2}(1-v_c^2/v_{\max}^2)T^2 that is computable from vehicle parameters and the planning horizon alone. Putting these together, we propose Mismatch-Aware Adaptive Constraint Tightening (MACT), ε(v,κ)=a2v2∣κ∣ε(v,κ)=a_2 v^2|κ|, which replaces a fixed worst-case margin by a state-dependent one that is large at high speed/curvature but nearly zero on gentle paths. Eight numerical experiments confirm the scaling laws. MACT reaches 100% safety with 84% less wasted margin than a fixed-margin baseline on the 2-DOF vehicle, extends to a nonlinear leaning bicycle, and in a closed-loop direct-shooting MPC comparison it cuts the applied margin by 34% compared with tube MPC while keeping the same safety.

Lingxue Lyu, Zihui Liu

School of Engineering and Applied Science, University of Pennsylvania, Philadelphia, PA 19104, USA · Department of Aeronautics & Astronautics, Stanford University, Stanford, CA 94305, USA

Trajectory OptimizationModel Predictive ControlVehicle DynamicsConstrained OptimizationAutonomous Driving Planning
AskPDF
May 10, 2026

Mutual Information Optimal Density Control of Linear Systems and Generalized Schrödinger Bridges with Reference Refinement

We consider a mutual information (MI) regularized optimal density control of a discrete-time linear system. MI optimal control has been utilized for exploration in reinforcement learning and privacy protection in control. MI regularization induces stochasticity in the policy, which poses challenges for applications of MI optimal control in safety-critical scenarios. To remedy this situation, we impose Gaussian density constraints at specified times to directly control state uncertainty. For this MI optimal density control problem, we propose an alternating optimization algorithm and investigate its convergence properties. In addition, we reveal a relationship between the MI optimal density control problem and a so-called generalized Schrödinger bridge problem associated with the discrete-time linear system. Based on the results of MI optimal density control and this relationship, we also investigate alternating optimization for the Schrödinger bridge problem and its convergence properties.

Shoju Enami, Kenji Kashima

Graduate School of Informatics, Kyoto University, Kyoto, Japan

Stochastic Optimal ControlSchrödinger BridgesDistribution MatchingConstrained OptimizationOptimal Control
AskPDF