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

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

Mar 27, 2026

Breaking Exponential Complexity in Games of Ordered Preference: A Tractable Reformulation

Games of ordered preference (GOOPs) model multi-player equilibrium problems in which each player maintains a distinct hierarchy of strictly prioritized objectives. Existing approaches solve GOOPs by deriving and enforcing the necessary optimality conditions that characterize lexicographically constrained Nash equilibria through a single-level reformulation. However, the number of primal and dual variables in the resulting KKT system grows exponentially with the number of preference levels, leading to severe scalability challenges. We derive a compact reformulation of these necessary conditions that preserves the essential primal stationarity structure across hierarchy levels, yielding a "reduced" KKT system whose size grows polynomially with both the number of players and the number of preference levels. The reduced system constitutes a relaxation of the complete KKT system, yet it remains a valid necessary condition for local GOOP equilibria. For GOOPs with quadratic objectives and linear constraints, we prove that the primal solution sets of the reduced and complete KKT systems coincide. More generally, for GOOPs with arbitrary (but smooth) nonlinear objectives and constraints, the reduced KKT conditions recover all local GOOP equilibria but may admit spurious non-equilibrium solutions. We introduce a second-order sufficient condition to certify when a candidate point corresponds to a local GOOP equilibrium. We also develop a primal-dual interior-point method for computing a local GOOP equilibrium with local quadratic convergence. The resulting framework enables scalable and efficient computation of GOOP equilibria beyond the tractable range of existing exponentially complex formulations.

Dong Ho Lee, Jingqi Li, Lasse Peters +2

Aerospace Engineering and Engineering Mechanics, University of Texas at Austin, Austin, TX 78712-1221 USA · Oden Institute for Computational Engineering and Sciences, University of Texas at Austin, Austin, TX 78712-1221 USA · Department of Mechanical Engineering, UC Berkeley, Berkeley, CA 94720-1740 USA +1

Nash Equilibrium ComputationMulti-Objective OptimizationConstrained Optimization
AskPDF
Mar 24, 2026

Double Coupling Architecture and Training Method for Optimization Problems of Differential Algebraic Equations with Parameters

Simulation and modeling are essential in product development, integrated into the design and manufacturing process to enhance efficiency and quality. They are typically represented as complex nonlinear differential algebraic equations. The growing diversity of product requirements demands multi-task optimization, a key challenge in simulation modeling research. A dual physics-informed neural network architecture has been proposed to decouple constraints and objective functions in parametric differential algebraic equation optimization problems. Theoretical analysis shows that introducing a relaxation variable with a global error bound ensures solution equivalence between the network and optimization problem. A genetic algorithm-enhanced training framework for physics-informed neural networks improves training precision and efficiency, avoiding redundant solving of differential algebraic equations. This approach enables generalization for multi-task objectives with a single, training maintaining real-time responsiveness to product requirements.

Wenqiang Yang, Wenyuan Wu, Yong Feng +1

Chongqing Key Laboratory of Automated Reasoning and Cognition, Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, 266 Fangzheng Avenue, Liangjiang District, 400714, Chongqing, China. · Chongqing School, University of Chinese Academy of Sciences, 266 Fangzheng Avenue, Liangjiang District, 400714, Chongqing, China.

Constrained OptimizationPhysics-Informed MLMulti-Task Optimization
AskPDF
Mar 21, 2026

Spectral-Sphere-Constrained Hyper-Connections

Hyper-Connections (HC) extend residual connections into multiple streams, employing residual matrices for cross-stream mixing to enrich model expressivity. However, unconstrained mixing disrupts the identity mapping property intrinsic to the residual connection, causing unstable training. To address this, Manifold-Constrained Hyper-Connections (mHC) and its variants restrict these matrices to be doubly stochastic via Sinkhorn-Knopp (SK) algorithm or permutation-based parameterizations. We reveal three limitations of this doubly stochastic constraint: (1) identity degeneration, where learned matrices collapse around the identity initialization and diminish cross-stream interactions, (2) a expressivity bottleneck, where the doubly stochastic constraint restricts the freedom of the subdominant spectrum of the residual matrices, preventing the model from selectively preserving or attenuating cross-stream variations, and (3) parameterization inefficiencies, manifesting as unstable SK iterations or the factorial-scaling overhead of permutation-based parameterizations. To overcome these flaws, we propose Spectral-Sphere-Constrained Hyper-Connections (s2\mathrm{s}^{2}HC). By confining residual matrices to a spectral norm sphere, s2\mathrm{s}^{2}HC restores free control over the subdominant spectrum, enabling the model to selectively preserve or attenuate cross-stream variations. This shift eliminates unstable SK iterations and factorial parameterization, enabling expressive, non-degenerate residual matrices while preserving training stability.

Zhaoyi Liu, Haichuan Zhang, Ang Li

University of Maryland, College Park · University of Utah

Hyper-ConnectionsResidual LearningConstrained Optimization
AskPDF
Mar 21, 2026

Breaking the O(T)O(\sqrt{T}) Cumulative Constraint Violation Barrier while Achieving O(T)O(\sqrt{T}) Static Regret in Constrained Online Convex Optimization

The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action xt∈X⊂Rdx_t \in \mathcal{X} \subset \mathbb{R}^d, a convex loss function ftf_t and a convex constraint function gtg_t that drives the constraint gt(x)≤0g_t(x)\le 0 are revealed. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV) compared to the benchmark that knows the loss functions and constraint functions ftf_t and gtg_t for all tt ahead of time, and chooses a static optimal action that is feasible with respect to all gt(x)≤0g_t(x)\le 0. In recent prior work Sinha and Vaze [2024], algorithms with simultaneous regret of O(T)O(\sqrt{T}) and CCV of O(T)O(\sqrt{T}) or (CCV of O(1)O(1) in specific cases Vaze and Sinha [2025], e.g. when d=1d=1) have been proposed. It is widely believed that CCV is Ω(T)Ω(\sqrt{T}) for all algorithms that ensure that regret is O(T)O(\sqrt{T}) with the worst case input for any d≥2d\ge 2. In this paper, we refute this and show that the algorithm of Vaze and Sinha [2025] simultaneously achieves regret of O(T)O(\sqrt{T}) regret and CCV of O(T1/3)O(T^{1/3}) when d=2d=2.

Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze

Online Convex OptimizationConstrained OptimizationRegret Minimization
AskPDF
Mar 19, 2026

Fast and Effective Computation of Generalized Symmetric Matrix Factorization

In this paper, we study a nonconvex, nonsmooth, and non-Lipschitz generalized symmetric matrix factorization model that unifies a broad class of matrix factorization formulations arising in machine learning, image science, engineering, and related areas. We first establish two exactness properties. On the modeling side, we prove an exact penalty property showing that, under suitable conditions, the symmetry-inducing quadratic penalty enforces symmetry whenever the penalty parameter is sufficiently large but finite, thereby exactly recovering the associated symmetric formulation. On the algorithmic side, we introduce an auxiliary-variable splitting formulation and establish an exact relaxation relationship that rigorously links stationary points of the original objective function to those of a relaxed potential function. Building on these exactness properties, we propose an average-type nonmonotone alternating updating method (A-NAUM) based on the relaxed potential function. At each iteration, A-NAUM alternately updates the two factor blocks by (approximately) minimizing the potential function, while the auxiliary block is updated in closed form. To ensure the convergence and enhance practical performance, we further incorporate an average-type nonmonotone line search and show that it is well-defined under mild conditions. Moreover, based on the Kurdyka-Łojasiewicz property and its associated exponent, we establish global convergence of the entire sequence to a stationary point and derive convergence rate results. Finally, numerical experiments on real datasets demonstrate the efficiency of A-NAUM.

Lei Yang, Han Wan, Min Zhang +1

School of Computer Science and Engineering, and Guangdong Province Key Laboratory of Computational Science, Sun Yat-sen University · School of Computer Science and Engineering, Sun Yat-sen University · School of Mathematics and Information Science, Guangzhou University +1

Matrix FactorizationNonconvex OptimizationOptimization Convergence AnalysisConstrained Optimization
AskPDF
Mar 18, 2026

Constrained Hybrid Metaheuristic: A Universal Framework for Continuous Optimisation

This paper presents the constrained Hybrid Metaheuristic (cHM) algorithm as a general framework for continuous optimisation. Unlike many existing metaheuristics that are tailored to specific function classes or problem domains, cHM is designed to operate across a broad spectrum of objective functions, including those with unknown, heterogeneous, or complex properties such as non-convexity, non-separability, and varying smoothness. We provide a formal description of the algorithm, highlighting its modular structure and two-phase operation, which facilitates dynamic adaptation to the problem's characteristics. A key feature of cHM is its ability to harness synergy between both candidate solutions and component metaheuristic strategies. This property allows the algorithm to apply the most appropriate search behaviour at each stage of the optimisation process, thereby improving convergence and robustness. Our extensive experimental evaluation on 28 benchmark functions demonstrates that cHM consistently matches or outperforms traditional metaheuristics in terms of solution quality and convergence speed. In addition, a practical application of the algorithm is demonstrated for a feature selection problem in the context of data classification. The results underscore its potential as a versatile and effective black-box optimiser suitable for both theoretical research and practical applications.

Piotr A. Kowalski, Szymon Kucharczyk, Jacek Mańdziuk

Faculty of Physics and Applied Computer Science, AGH University of Krakow, al. A. Mickiewicza 30, 30-059 Cracow, Poland. · Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01-447 Warsaw, Poland. · AGH Doctoral School, AGH University of Krakow, al. A. Mickiewicza 30, 30-059 Cracow, Poland. +2

Metaheuristic OptimizationBlack-Box OptimizationConstrained Optimization
AskPDF
Mar 12, 2026

UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimization

Unsupervised neural combinatorial optimization (NCO) offers an appealing alternative to supervised approaches by training learning-based solvers without ground-truth solutions, directly minimizing instance objectives and constraint violations. Yet for graph node subset-selection problems (e.g., Maximum Clique and Maximum Independent Set), existing unsupervised methods are typically specialized to a single problem class and rely on problem-specific surrogate losses, which hinders learning across classes within a unified framework. In this work, we propose UniHetCO, a unified heterogeneous graph representation for constrained quadratic programming-based combinatorial optimization that encodes problem structure, objective terms, and linear constraints in a single input. This formulation enables training a single model across multiple problem classes with a unified label-free objective. To improve stability under multi-problem learning, we employ a gradient-norm-based dynamic weighting scheme that alleviates gradient imbalance among classes. Experiments on multiple datasets and four constrained problem classes demonstrate competitive performance with state-of-the-art unsupervised NCO baselines, strong cross-problem adaptation potential, and effective warm starts for a commercial classical solver under tight time limits.

Kien X. Nguyen, Ilya Safro

Department of Computer and Information Sciences, University of Delaware, Newark DE 19716, USA

Combinatorial OptimizationNeural Combinatorial OptimizationConstrained OptimizationHeterogeneous GNNs
AskPDF
Mar 11, 2026

ADMM-based Continuous Trajectory Optimization in Graphs of Convex Sets

This paper presents a numerical solver for computing continuous trajectories in non-convex environments. Our approach relies on a customized implementation of the Alternating Direction Method of Multipliers (ADMM) built upon two key components: First, we parameterize trajectories as polynomials, allowing the primal update to be computed in closed form as a minimum-control-effort problem. Second, we introduce the concept of a spatio-temporal allocation graph based on a mixed-integer formulation and pose the slack update as a shortest-path search. The combination of these ingredients results in a solver with several distinct advantages over the state of the art. By jointly optimizing over both discrete and continuous domains, our method accesses a larger search space than existing decoupled approaches, enabling the discovery of superior trajectories. Additionally, the solver's structural robustness ensures reliable convergence from naive initializations, removing the bottleneck of complex warm starting in non-convex environments.

Lukas Pries, Jon Arrizabalaga, Zachary Manchester +1

Autonomous Aerial Systems Lab, Dep. of Aerospace and Geodesy, TU Munich, Germany · Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, USA

Trajectory OptimizationAlternating Direction Method of MultipliersNonconvex OptimizationConstrained OptimizationMotion Planning
AskPDF
Mar 11, 2026

Bayesian Optimization of Partially Known Systems using Hybrid Models

Bayesian optimization (BO) has gained attention as an efficient algorithm for black-box optimization of expensive-to-evaluate systems, where the BO algorithm iteratively queries the system and suggests new trials based on a probabilistic model fitted to previous samples. Still, the standard BO loop may require a prohibitively large number of experiments to converge to the optimum, especially for high-dimensional and nonlinear systems. We present a hybrid model-based BO formulation that combines the iterative Bayesian learning of BO with partially known mechanistic physical models. Instead of learning a direct mapping from inputs to the objective, we write all known equations for a physics-based model and infer expressions for variables missing equations using a probabilistic model, in our case, a Gaussian process (GP). The final formulation then includes the GP as a constraint in the hybrid model, thereby allowing other physics-based nonlinear and implicit model constraints. This hybrid model formulation yields a constrained, nonlinear stochastic program, which we discretize using the sample-average approximation. In an in-silico optimization of a single-stage distillation, the hybrid BO model based on mass conservation laws yields significantly better designs than a standard BO loop. Furthermore, the hybrid model converges in as few as one iteration, depending on the initial samples, whereas, the standard BO does not converge within 25 for any of the seeds. Overall, the proposed hybrid BO scheme presents a promising optimization method for partially known systems, leveraging the strengths of both mechanistic modeling and data-driven optimization.

Eike Cramer, Luis Kutschat, Oliver Stollenwerk +2

University College London, Sargent Centre for Process Systems Engineering, Department of Chemical Engineering, London WC1E 7JE, United Kingdom · RWTH Aachen University, Process Systems Engineering (AVT.SVT), Aachen 52074, Germany · University of Wisconsin–Madison, Department of Chemical & Biological Engineering, Madison, WI 53706, USA +2

Bayesian OptimizationConstrained Optimization
AskPDF
Mar 10, 2026

A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method

In this paper, we propose a trust-region interior-point stochastic sequential quadratic programming (TR-IP-SSQP) method for solving optimization problems with a stochastic objective and deterministic nonlinear equality and inequality constraints. In this setting, exact evaluations of the objective function and its gradient are unavailable, but their stochastic estimates can be constructed. In particular, at each iteration our method builds stochastic oracles, which estimate the objective value and gradient to satisfy proper adaptive accuracy conditions with a fixed probability. To handle inequality constraints, we adopt an interior-point method (IPM), in which the barrier parameter follows a prescribed decaying sequence. Under standard assumptions, we establish global almost-sure convergence of the proposed method to first-order stationary points. We implement the method on a subset of problems from the CUTEst test set, as well as on logistic regression problems, to demonstrate its practical performance.

Yuchen Fang, Jihun Kim, Sen Na +2

Department of Mathematics, University of California, Berkeley · Department of IEOR, University of California, Berkeley · School of Industrial and Systems Engineering, Georgia Tech +1

Constrained OptimizationStochastic OptimizationStochastic Optimization ConvergenceTrust-Region Optimization
AskPDF
Mar 10, 2026

Information Theoretic Bayesian Optimization over the Probability Simplex

Bayesian optimization is a data-efficient technique that has been shown to be extremely powerful to optimize expensive, black-box, and possibly noisy objective functions. Many applications involve optimizing probabilities and mixtures which naturally belong to the probability simplex, a constrained non-Euclidean domain defined by non-negative entries summing to one. This paper introduces αα-GaBO, a novel family of Bayesian optimization algorithms over the probability simplex. Our approach is grounded in information geometry, a branch of Riemannian geometry which endows the simplex with a Riemannian metric and a class of connections. Based on information geometry theory, we construct Matérn kernels that reflect the geometry of the probability simplex, as well as a one-parameter family of geometric optimizers for the acquisition function. We validate our method on benchmark functions and on a variety of real-world applications including mixtures of components, mixtures of classifiers, and a robotic control task, showing its increased performance compared to constrained Euclidean approaches.

Federico Pavesi, Antonio Candelieri, Noémie Jaquier

Department of Robotics, Perception and Learning, KTH Royal Institute of Technology, Stockholm, Sweden · Department of Economics, Management and Statistics, University of Milan, Bicocca, Milan, Italy

Bayesian OptimizationConstrained OptimizationRiemannian Optimization
AskPDF
Mar 9, 2026

First-Order Geometry, Spectral Compression, and Structural Compatibility under Bounded Computation

Optimization under structural constraints is typically analyzed through projection or penalty methods, obscuring the geometric mechanism by which constraints shape admissible dynamics. We propose an operator-theoretic formulation in which computational or feasibility limitations are encoded by self-adjoint operators defining locally reachable subspaces. In this setting, the optimal first-order improvement direction emerges as a pseudoinverse-weighted gradient, revealing how constraints induce a distorted ascent geometry. We further demonstrate that effective dynamics concentrate along dominant spectral modes, yielding a principled notion of spectral compression, and establish a compatibility principle that characterizes the existence of common admissible directions across multiple objectives. The resulting framework unifies gradient projection, spectral truncation, and multi-objective feasibility within a single geometric structure.

Changkai Li

Constrained OptimizationMulti-Objective OptimizationSpectral Methods
AskPDF
Mar 9, 2026

Learning efficient representations of complex constraints for scalable optimization

Complex constraints often make real-world optimization computationally prohibitive at the scale and speed required for operational decision-making. Here we introduce PolyFormer, a PIML framework that learns compact polytopic representations of the geometry induced by complex constraints. PolyFormer captures constraint-induced geometry and transforms it into efficient polytopic reformulations, reducing the complexity of downstream optimization and enabling the use of off-the-shelf solvers. Neural parameterizations further enable rapid adaptation to varying operating conditions without retraining. Through evaluations across three important problems, i.e., large-scale resource aggregation, network-constrained optimization, and optimization under uncertainty, PolyFormer achieves online solver speedups of up to 6,400-fold and memory reductions of up to 99.87%, while maintaining small feasibility and objective errors. Together, these results establish learned geometric constraint representations as an effective and scalable route to prescriptive optimization under diverse forms of constraint complexity.

Yilin Wen, Yi Guo, Bo Zhao +4

School of Electrical and Electronic Engineering, North China Electric Power University, Changping District, Beijing, 102206, China. · Department of Electrical Engineering, Tsinghua University, Haidian District, Beijing, 100084, China. · School of Automation, Beijing Institute of Technology, Haidian District, Beijing, 100081, China. +2

Representation LearningConstrained Optimization
AskPDF
Mar 9, 2026

Local Constrained Bayesian Optimization

Bayesian optimization (BO) for high-dimensional constrained problems remains a significant challenge due to the curse of dimensionality. We propose Local Constrained Bayesian Optimization (LCBO), a novel framework tailored for such settings. Unlike trust-region methods that are prone to premature shrinking when confronting tight or complex constraints, LCBO leverages the differentiable landscape of constraint-penalized surrogates to alternate between rapid local descent and uncertainty-driven exploration. Theoretically, we prove that LCBO achieves a convergence rate for the Karush-Kuhn-Tucker (KKT) residual that depends polynomially on the dimension dd for common kernels under mild assumptions, offering a rigorous alternative to global BO where regret bounds typically scale exponentially. Extensive evaluations on high-dimensional benchmarks (up to 100D) demonstrate that LCBO consistently outperforms state-of-the-art baselines.

Jing Jingzhe, Fan Zheyi, Szu Hui Ng +1

State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China · School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China · Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore.

Surrogate-Assisted OptimizationBayesian OptimizationConstrained Optimization
AskPDF
Mar 6, 2026

LIPP: Load-Aware Informative Path Planning with Physical Sampling

In classical Informative Path Planning (C-IPP), robots are typically modeled as mobile sensors that acquire digital measurements such as images or radiation levels. In this model, since making a measurement leaves the robot's physical state unchanged, the cost of traversing an edge remains static regardless of when it is traversed. This is a natural assumption for many missions, but does not extend to settings involving physical sample collection, where each collected sample adds mass and increases the energy cost of all subsequent motion. As a result, IPP formulations that ignore this coupling between information gain and load-dependent traversal cost can produce plans that are distance-efficient but energy-suboptimal, collecting fewer samples and less data than the energy budget would permit. In this paper, we first introduce Load-aware Informative Path Planning (LIPP), a strict generalization of C-IPP that explicitly models this coupling, with C-IPP recovered as the special case of zero sample mass. We then formulate LIPP as a Mixed-Integer Quadratic Program (MIQP) that jointly optimizes visitation location, order, and per-location sampling count under an energy budget. We further derive theoretical bounds on the path-length increase of LIPP relative to C-IPP, characterizing the trade-off for improved energy efficiency. Finally, through extensive simulations across 2,000 diverse mission scenarios, we demonstrate that LIPP progressively achieves higher uncertainty reduction per unit energy as sample mass increases.

Hojune Kim, Guangyao Shi, Gaurav S. Sukhatme

School of Electrical and Computer Engineering University of Southern California Los Angeles, California · School of Computer Science University of Southern California Los Angeles, California

Informative Path PlanningConstrained OptimizationMotion PlanningMixed-Integer QPRobot Motion Planning
AskPDF
Mar 5, 2026

Cheap Thrills: Effective Amortized Optimization Using Inexpensive Labels

To scale optimization and simulation, prior work has explored training machine-learning surrogates that map problem parameters to solutions inexpensively at inference time. Unfortunately, commonly used approaches, including supervised and self-supervised learning with either soft or hard feasibility enforcement, face inherent challenges such as reliance on expensive high-quality labels or difficult optimization landscapes. To address their trade-offs, we propose a novel framework that collects "cheap" imperfect labels, performs supervised model pretraining with a merit loss-based termination scheme, and finally refines the model through self-supervised learning to improve final performance. Empirical validation across challenging domains -- including nonconvex constrained optimization, power-grid operation, and stiff dynamical systems -- shows that this three-stage strategy yields faster convergence; improved accuracy, feasibility, and optimality; and up to 59x reductions in total offline computational cost. We further analyze why and when our framework improves surrogate model training, finding that (i) merit loss is an informative signal and (ii) only small numbers of cheap, inexact labels are needed to place the model in a favorable regime for self-supervised learning.

Khai Nguyen, Petros Ellinas, Anvita Bhagavathula +1

Massachusetts Institute of Technology, Cambridge, MA, USA · Technical University of Denmark, Kongens Lyngby, Denmark

Learning to OptimizeNeural Surrogate ModelingConstrained Optimization
AskPDF
Mar 3, 2026

Shape Derivative-Informed Neural Operators with Application to Risk-Averse Shape Optimization

Shape optimization under uncertainty (OUU) is computationally intensive for classical PDE-based methods due to the high cost of repeated sampling-based risk evaluation across many uncertainty realizations and varying geometries, while standard neural surrogates often fail to provide accurate and efficient sensitivities for optimization. We introduce Shape-DINO, a derivative-informed neural operator framework for learning PDE solution operators on families of varying geometries, with a particular focus on accelerating PDE-constrained shape OUU. Shape-DINOs encode geometric variability through diffeomorphic mappings to a fixed reference domain and employ a derivative-informed operator learning objective that jointly learns the PDE solution and its Fréchet derivatives with respect to design variables and uncertain parameters, enabling accurate state predictions and reliable gradients for large-scale OUU. We establish a priori error bounds linking surrogate accuracy to optimization error and prove universal approximation results for multi-input reduced basis neural operators in suitable C1C^1 norms. We demonstrate efficiency and scalability on three representative shape OUU problems, including boundary design for a Poisson equation and shape design governed by steady-state Navier-Stokes exterior flows in two and three dimensions. Across these examples, Shape-DINOs produce more reliable optimization results than operator surrogates trained without derivative information. In our examples, Shape-DINOs achieve 3-8 orders-of-magnitude speedups in state and gradient evaluations. Counting training data generation, Shape-DINOs reduce necessary PDE solves by 1-2 orders-of-magnitude compared to a strictly PDE-based approach for a single OUU problem. Moreover, Shape-DINO construction costs can be amortized across many objectives and risk measures, enabling large-scale shape OUU for complex systems.

Xindi Gong, Dingcheng Luo, Thomas O'Leary-Roseberry +2

Oden Institute for Computational Engineering and Sciences, The University of Texas at Austin, Austin, Texas, USA · School of Mathematical Sciences, Queensland University of Technology, Brisbane, Australia · Centre for Data Science, Queensland University of Technology, Brisbane, Australia +3

PDE Operator LearningNeural OperatorsUncertainty QuantificationConstrained Optimization
AskPDF
Mar 3, 2026

cuNRTO: GPU-Accelerated Nonlinear Robust Trajectory Optimization

Robust trajectory optimization enables autonomous systems to operate safely under uncertainty by computing control policies that satisfy the constraints for all bounded disturbances. However, these problems often lead to large Second Order Conic Programming (SOCP) constraints, which are computationally expensive. In this work, we propose the CUDA Nonlinear Robust Trajectory Optimization (cuNRTO) framework by introducing two dynamic optimization architectures that have direct application to robust decision-making and are implemented on CUDA. The first architecture, NRTO-DR, leverages the Douglas-Rachford (DR) splitting method to solve the SOCP inner subproblems of NRTO, thereby significantly reducing the computational burden through parallel SOCP projections and sparse direct solves. The second architecture, NRTO-FullADMM, is a novel variant that further exploits the problem structure to improve scalability using the Alternating Direction Method of Multipliers (ADMM). Finally, we provide GPU implementations of the proposed methodologies using custom CUDA kernels for SOC projection steps and cuBLAS GEMM chains for feedback gain updates. We validate the performance of cuNRTO through simulated experiments on unicycle, quadcopter, and Franka manipulator models, demonstrating speedups of up to 139.6×\times. More details are available at https://cunrto.github.io.

Jiawei Wang, Arshiya Taj Abdul, Evangelos A. Theodorou

University of California, San Diego · Georgia Institute of Technology, Atlanta

Second-Order Cone ProgrammingTrajectory OptimizationConstrained OptimizationGPU AccelerationAlternating Direction Method of Multipliers
AskPDF
Mar 2, 2026

FAST-DIPS: Adjoint-Free Analytic Steps and Hard-Constrained Likelihood Correction for Diffusion-Prior Inverse Problems

Training-free diffusion priors enable inverse-problem solvers without retraining, but for nonlinear forward operators data consistency often relies on repeated derivatives or inner optimization/MCMC loops with conservative step sizes, incurring many iterations and denoiser/score evaluations. We propose a training-free solver that replaces these inner loops with a hard measurement-space feasibility constraint (closed-form projection) and an analytic, model-optimal step size, enabling a small, fixed compute budget per noise level. Anchored at the denoiser prediction, the correction is approximated via an adjoint-free, ADMM-style splitting with projection and a few steepest-descent updates, using one VJP and either one JVP or a forward-difference probe, followed by backtracking and decoupled re-annealing. We prove local model optimality and descent under backtracking for the step-size rule, and derive an explicit KL bound for mode-substitution re-annealing under a local Gaussian conditional surrogate. We also develop a latent variant and a one-parameter pixel→\rightarrowlatent hybrid schedule. Experiments achieve competitive PSNR/SSIM/LPIPS with up to 19.5×\times speedup, without hand-coded adjoints or inner MCMC.

Minwoo Kim, Seunghyeok Shin, Hongki Lim

Department of Electrical and Computer Engineering, Inha University Incheon, 22212, South Korea

Diffusion-Based Inverse ProblemsInverse ProblemsDiffusion Model Inference AccelerationConstrained OptimizationDifferentiable Optimization
AskPDF
Mar 1, 2026

GPU-friendly and Linearly Convergent First-order Methods for Certifying Optimal kk-sparse GLMs

We investigate the problem of certifying optimality for sparse generalized linear models (GLMs), where sparsity is enforced through a cardinality constraint. While Branch-and-Bound (BnB) frameworks can certify optimality using perspective relaxations, existing methods for solving these relaxations are computationally intensive, limiting their scalability. To address this challenge, we reformulate the relaxations as composite optimization problems and develop a unified proximal framework that is both linearly convergent and computationally efficient. Under specific geometric regularity conditions, our analysis links primal quadratic growth to dual quadratic decay, yielding error bounds that make the Fenchel duality gap a sharp proxy for progress towards the solution set. This leads to a duality gap-based restart scheme that upgrades a broad class of sublinear proximal methods to provably linearly convergent methods, and applies beyond the sparse GLM setting. For the implicit perspective regularizer, we further derive specialized routines to evaluate the regularizer and its proximal operator exactly in log-linear time, avoiding costly generic conic solvers. The resulting iterations are dominated by matrix--vector multiplications, which enables GPU acceleration. Experiments on synthetic and real-world datasets show orders-of-magnitude faster dual-bound computations and substantially improved BnB scalability on large instances.

Jiachang Liu, Andrea Lodi, Soroosh Shafiee

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

Constrained OptimizationGeneralized Linear ModelsPrimal-Dual Optimization
AskPDF
Mar 1, 2026

Hippo: High-performance Interior-Point and Projection-based Solver for Generic Constrained Trajectory Optimization

Trajectory optimization is the core of modern model-based robotic control and motion planning. Existing trajectory optimizers, based on sequential quadratic programming (SQP) or differential dynamic programming (DDP), are often limited by their slow computation efficiency, low modeling flexibility, and poor convergence for complex tasks requiring hard constraints. In this paper, we introduce Hippo, a solver that can handle inequality constraints using the interior-point method (IPM) with an adaptive barrier update strategy and hard equality constraints via projection or IPM. Through extensive numerical benchmarks, we show that Hippo is a robust and efficient alternative to existing state-of-the-art solvers for difficult robotic trajectory optimization problems requiring high-quality solutions, such as locomotion and manipulation.

Haizhou Zhao, Ludovic Righetti, Majid Khadiv

Tandon School of Engineering, New York University, USA · Munich Institute of Robotics and Machine Intelligence (MIRMI), Technical University of Munich (TUM), Germany

Trajectory OptimizationConstrained Optimization
AskPDF
Feb 27, 2026

A distributed semismooth Newton based augmented Lagrangian method for distributed optimization

This paper proposes a novel distributed semismooth Newton based augmented Lagrangian method for solving a class of optimization problems over networks, where the global objective is defined as the sum of locally held cost functions, and communication is restricted to neighboring agents. Specifically, we employ the augmented Lagrangian method to solve an equivalently reformulated constrained version of the original problem. Each resulting subproblem is solved inexactly via a distributed semismooth Newton method. By fully leveraging the structure of the generalized Hessian, a distributed accelerated proximal gradient method is proposed to compute the Newton direction efficiently, eliminating the need to communicate with full Hessian matrices. Theoretical results are also obtained to guarantee the convergence of the proposed algorithm. Numerical experiments demonstrate the efficiency and superiority of our algorithm compared to state-of-the-art distributed algorithms.

Qihao Ma, Chengjing Wang, Peipei Tang +2

School of Mathematics, Southwest Jiaotong University, No.999, Xian Road, West Park, High-tech Zone, Chengdu 611756, China · School of Computer and Computing Science, Hangzhou City University, Zhejiang Key Laboratory of Big Data Intelligent Computing, Hangzhou, 310015, China · Department of Control Science and Engineering, College of Electronics and Information Engineering, National Key Laboratory of Autonomous Intelligent Unmanned Systems, Tongji University, Shanghai 201804, China +1

Distributed OptimizationAugmented Lagrangian MethodConstrained Optimization
AskPDF
Feb 26, 2026

Zeroth-Order Stackelberg Control in Combinatorial Congestion Games

We study Stackelberg (leader--follower) tuning of network parameters (tolls, capacities, incentives) in combinatorial congestion games, where selfish users choose discrete routes (or other combinatorial strategies) and settle at a congestion equilibrium. The leader minimizes a system-level objective (e.g., total travel time) evaluated at equilibrium, but this objective is typically nonsmooth because the set of used strategies can change abruptly. We propose ZO-Stackelberg, which couples a projection-free Frank--Wolfe equilibrium solver with a zeroth-order outer update, avoiding differentiation through equilibria. We prove convergence to generalized Goldstein stationary points of the true equilibrium objective, with explicit dependence on the equilibrium approximation error, and analyze subsampled oracles: if an exact minimizer is sampled with probability κmκ_m, then the Frank--Wolfe error decays as O(1/(κmT))\mathcal{O}(1/(κ_m T)). We also propose stratified sampling as a practical way to avoid a vanishing κmκ_m when the strategies that matter most for the Wardrop equilibrium concentrate in a few dominant combinatorial classes (e.g., short paths). Experiments on real-world networks demonstrate that our method achieves orders-of-magnitude speedups over a differentiation-based baseline while converging to follower equilibria.

Saeed Masiha, Sepehr Elahi, Negar Kiyavash +1

EPFL School of Management of Technology · EPFL Department of Computer and Communications Sciences

Frank-Wolfe AlgorithmsStackelberg GamesCongestion GamesGame TheoryZeroth-Order OptimizationConstrained Optimization
AskPDF
Feb 26, 2026

Operationalizing Fairness: Post-Hoc Threshold Optimization Under Hard Resource Limits

The deployment of machine learning in high-stakes domains requires a balance between predictive safety and algorithmic fairness. However, existing fairness interventions often as- sume unconstrained resources and employ group-specific decision thresholds that violate anti- discrimination regulations. We introduce a post-hoc, model-agnostic threshold optimization framework that jointly balances safety, efficiency, and equity under strict and hard capacity constraints. To ensure legal compliance, the framework enforces a single, global decision thresh- old. We formulated a parameterized ethical loss function coupled with a bounded decision rule that mathematically prevents intervention volumes from exceeding the available resources. An- alytically, we prove the key properties of the deployed threshold, including local monotonicity with respect to ethical weighting and the formal identification of critical capacity regimes. We conducted extensive experimental evaluations on diverse high-stakes datasets. The principal re- sults demonstrate that capacity constraints dominate ethical priorities; the strict resource limit determines the final deployed threshold in over 80% of the tested configurations. Furthermore, under a restrictive 25% capacity limit, the proposed framework successfully maintains high risk identification (recall ranging from 0.409 to 0.702), whereas standard unconstrained fairness heuristics collapse to a near-zero utility. We conclude that theoretical fairness objectives must be explicitly subordinated to operational capacity limits to remain in deployment. By decou- pling predictive scoring from policy evaluation and strictly bounding intervention rates, this framework provides a practical and legally compliant mechanism for stakeholders to navigate unavoidable ethical trade-offs in resource-constrained environments.

Moirangthem Tiken Singh, Amit Kalita, Sapam Jitu Singh

Department of Computer Science and Engineering, DUIET, Dibrugarh University, Assam, India · Department of Computer Science and Engineering, MIT, Manipur University, 795003, India

Algorithmic FairnessFair Resource AllocationConstrained OptimizationPost-Hoc Calibration
AskPDF
Feb 25, 2026

ConstraintBench: Benchmarking LLM Constraint Reasoning on Direct Optimization

Large language models are increasingly applied to operational decision-making where the underlying structure is constrained optimization. Existing benchmarks evaluate whether LLMs can formulate optimization problems as solver code, but leave open a complementary question. Can LLMs directly produce correct solutions to fully specified constrained optimization problems without access to a solver? We introduce ConstraintBench, a benchmark for evaluating LLMs on direct constrained optimization across 10 operations research domains, with all ground-truth solutions verified by the Gurobi solver. Each task presents a natural-language scenario with entities, constraints, and an optimization objective; the model must return a structured solution that a deterministic verifier checks against every constraint and the solver-proven optimum. We evaluate six frontier models on 200 tasks and find that feasibility, not optimality, is the primary bottleneck. The best model achieves only 65.0% feasibility, yet feasible solutions average 89 to 96% of the Gurobi-optimal objective. No model exceeds 30.5% on joint feasibility and optimality within 0.1% of the solver reference. Per-domain analysis shows large variation in difficulty, with average feasibility spanning from 85.0% in the facility location domain to 0.8% in the crew assignment domain. Further, systematic failure modes include duration constraint misunderstanding, entity hallucination, and a feasibility-optimality decoupling in facility location and vehicle routing where models achieve high feasibility but 0% optimality. ConstraintBench and all evaluation infrastructure will be publicly released.

Joseph Tso, Preston Schmittou, Quan Huynh +1

Haladir Research Team

Constraint-Guided Reasoning in Language ModelsConstrained OptimizationLLM ReasoningOperations Research
AskPDF
Feb 25, 2026

Provable Last-Iterate Convergence for Multi-Objective Safe LLM Alignment via Optimistic Primal-Dual

Reinforcement Learning from Human Feedback (RLHF) plays a significant role in aligning Large Language Models (LLMs) with human preferences. While RLHF with expected reward constraints can be formulated as a primal-dual optimization problem, standard primal-dual methods only guarantee convergence with a distributional policy where the saddle-point problem is in convex-concave form. Moreover, standard primal-dual methods may exhibit instability or divergence in the last iterate under policy parameterization in practical applications. In this work, we propose a universal primal-dual framework for safe RLHF that unifies a broad class of existing alignment algorithms, including safe-RLHF, one-shot, and multi-shot based methods. Building on this framework, we introduce an optimistic primal-dual (OPD) algorithm that incorporates predictive updates for both primal and dual variables to stabilize saddle-point dynamics. We establish last-iterate convergence guarantees for the proposed method, covering both exact policy optimization in the distributional space and convergence to a neighborhood of the optimal solution whose gap is related to approximation error and bias under parameterized policies. Our analysis reveals that optimism plays a crucial role in mitigating oscillations inherent to constrained alignment objectives, thereby closing a key theoretical gap between constrained RL and practical RLHF.

Yining Li, Peizhong Ju, Ness Shroff

The Ohio State University · University of Kentucky

LLM Safety AlignmentRL from Human FeedbackMulti-Objective Language Model AlignmentConstrained RLConstrained Optimization
AskPDF
Feb 24, 2026

Unified Complementarity-Based Contact Modeling and Planning for Soft Robots

Soft robots were introduced in large part to enable safe, adaptive interaction with the environment, and this interaction relies fundamentally on contact. However, modeling and planning contact-rich interactions for soft robots remain challenging: dense contact candidates along the body create redundant constraints and rank-deficient LCPs, while the disparity between high stiffness and low friction introduces severe ill-conditioning. Existing approaches rely on problem-specific approximations or penalty-based treatments. This letter presents a unified complementarity-based framework for soft-robot contact modeling and planning that brings contact modeling, manipulation, and planning into a unified, physically consistent formulation. We develop a robust Linear Complementarity Problem (LCP) model tailored to discretized soft robots and address these challenges with a three-stage conditioning pipeline: inertial rank selection to remove redundant contacts, Ruiz equilibration to correct scale disparity and ill-conditioning, and lightweight Tikhonov regularization on normal blocks. Building on the same formulation, we introduce a kinematically guided warm-start strategy that enables dynamic trajectory optimization through contact using Mathematical Programs with Complementarity Constraints (MPCC) and demonstrate its effectiveness on contact-rich ball manipulation tasks. In conclusion, CUSP provides a new foundation for unifying contact modeling, simulation, and planning in soft robotics.

Milad Azizkhani, Yue Chen

Woodruff School of Mechanical Engineering, Georgia Institute of Technology, Atlanta, GA, USA · Institute for Robotics and Intelligent Machines (IRIM), Georgia Institute of Technology, Atlanta, GA, USA · Coulter Department of Biomedical Engineering (Georgia Tech and Emory University), Georgia Institute of Technology, Atlanta, GA, USA

Soft RoboticsContact-Rich Robotic ManipulationConstrained OptimizationTrajectory Optimization
AskPDF
Feb 24, 2026

Precedence-Constrained Decision Trees and Coverings

This work considers a number of optimization problems and reductive relations between them. The two main problems we are interested in are the Optimal Decision Tree and Set Cover. We study these two fundamental tasks under precedence constraints, that is, if a test (or set) XX is a predecessor of YY, then in any feasible decision tree XX needs to be an ancestor of YY (or respectively, if YY is added to set cover, then so must be XX). For the Optimal Decision Tree we consider two optimization criteria: worst case identification time (height of the tree) or the average identification time. Similarly, for the Set Cover we study two cost measures: the size of the cover or the average cover time. Our approach is to develop a number of algorithmic reductions, where an approximation algorithm for one problem provides an approximation for another via a black-box usage of a procedure for the former. En route we introduce other optimization problems either to complete the `reduction landscape' or because they hold the essence of combinatorial structure of our problems. The latter is brought by a problem of finding a Maximum Density Precedence-Closed Subfamily, where the density is defined as the ratio of the number of items the family covers to its size. We provide O∗(m)\mathcal{O}^*(\sqrt{m})-approximation polynomial-time algorithms for all aforementioned problems. The picture is complemented by a number of hardness reductions that provide O(m1/12−ε)\mathcal{O}(m^{1/12-ε})-inapproximability results for the decision tree and covering problems. Besides giving a complete set of results for general precedence constraints, we also provide polylogarithmic approximation guarantees for two most typically studied and applicable graph types, outforests and inforests. By providing corresponding hardness results, we show most of these results to be tight.

Michał Szyfelbein, Dariusz Dereniowski

Gdańsk University of Technology, 80-233 Gdańsk, Poland

Combinatorial OptimizationConstrained OptimizationApproximation Algorithms
AskPDF
Feb 24, 2026

Mirror Descent-Type Algorithms for the Variational Inequality Problem with Functional Constraints

Variational inequalities play a key role in machine learning research, such as generative adversarial networks, reinforcement learning, adversarial training, and generative models. This paper is devoted to the constrained variational inequality problems with functional constraints (inequality-type constraints). We propose some mirror descent-type algorithms that switch between productive and non-productive steps depending on the values of the functional constraints at iterations, with many different step size rules and stopping criteria. We analyze the proposed algorithms and prove their optimal convergence rate to achieve a solution with desired accuracy, for problems with bounded and monotone operators and Lipschitz convex functional constraints. In addition, we propose a modification of the proposed algorithms by considering each functional constraint in the calculation when we have a productive step, as well as the first constraint that violates the feasibility. This modification can save the running time of algorithms when we have many functional constraints. In addition, we provide an analysis of the proposed algorithms for δδ-monotone operators, allowing us to apply the proposed algorithms, as a special case, to constrained minimization problems when we do not have access to the exact information about the subgradient of the objective function. Numerical experiments that illustrate the work and performance of the proposed algorithms are also given.

Mohammad S. Alkousa, Fedor S. Stonyakin, Belal A. Alashqar +1

Innopolis University, Innopolis, Universitetskaya Str., 1, 420500, Russia. · Moscow Institute of Physics and Technology, 9 Institutsky lane, Dolgoprudny, 141701, Russia. · V. I. Vernadsky Crimean Federal University, 4 Academician Vernadsky Avenue, Simferopol, 295007, Republic of Crimea, Russia.

Mirror DescentConstrained Optimization
AskPDF
Feb 19, 2026

Multi-Agent Temporal Logic Planning via Penalty Functions and Block-Coordinate Optimization

Multi-agent planning under Signal Temporal Logic (STL) is often hindered by collaborative tasks that lead to computational challenges due to the inherent high dimensionality of the problem, preventing scalable synthesis with satisfaction guarantees. To address this, we formulate STL planning as an optimization program under multi-agent STL constraints and introduce a penalty-based unconstrained relaxation that can be efficiently solved via a Block-Coordinate Gradient Descent (BCGD) method, where each block corresponds to a single agent's decision variables, thereby mitigating complexity. By utilizing a quadratic penalty function defined via smooth STL semantics, we show that BCGD iterations converge to a stationary point of the penalized problem under standard regularity assumptions. To enforce feasibility, the BCGD solver is embedded within a two-layer optimization scheme: inner BCGD updates are performed for a fixed penalty parameter, which is then increased in an outer loop to progressively improve multi-agent STL robustness. The proposed framework enables scalable computations and is validated through various complex multi-robot planning scenarios.

Eleftherios E. Vlahakis, Arash Bahari Kordabad, Lars Lindemann +3

the Division of Computer Engineering and Computer Science, University West, 46132, Trollhättan, Sweden · the Max Planck Institute for Software Systems, Kaiserslautern, Germany · the Automatic Control Laboratory, ETH Zürich, 8092, Zürich, Switzerland +2

STL PlanningMulti-Agent PlanningMulti-Robot Motion PlanningConstrained Optimization
AskPDF