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

368 papers27 papers in the last four weeks, down 43% on the four weeks before. 0.2% of all new papers.

Nov 17, 2026

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

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

Parallelizable Interior-Point ADMM for Block-Structured Nonconvex Programs

Physics simulation is an increasingly important computational primitive for AI, and local--global/ADMM splitting exposes its parallel structure but lacks matching finite-time convergence guarantees. We close this gap with two ADMM variants, Interior-Point ADMM (IP-ADMM), for block-structured nonconvex composite programs with smooth nonlinear inequality and affine constraints. A one-sided finite-activation wall keeps each constraint split state strictly feasible while the original-space infeasibility vanishes, giving closed-form constraint updates, one proximal call per objective block, and one equality-constrained quadratic consensus solve per iteration. \rev{To our knowledge, this makes IP-ADMM the first single-loop method that updates nonconvex inequality constraints locally and in parallel with finite-time convergence guarantees.} Ordinary IP-ADMM attains a CQ-free best-iterate weak-KKT rate of O(K−1/3)O(K^{-1/3}) or a banded Fritz--John rate of O(K−1/4)O(K^{-1/4}), which converts to KKT at O(K−1/4)O(K^{-1/4}) under a uniform constraint qualification; these are nearby-point certificates that reduce to conventional KKT for smooth blocks. A checkpoint variant, IP-ADMM-Ckpt, improves the asymptotic KKT exponent to O(K−1/3)O(K^{-1/3}). We also show how the bounds scale with the objective- and constraint-block counts and the coupling norm.
Nov 15, 2026

Risk-certified prompt optimization for LLM-as-a-judge guardrails

LLM-as-a-judge guardrails are often controlled primarily through system prompts, yet standard prompt optimization methods target average performance rather than explicit safety constraints. This paper studies system-prompt selection as a constrained optimization problem: maximize benign pass rate while keeping the missed-attack rate below a user-specified level α with finite-sample statistical control. The framework combines LLM-based judging, automatic prompt generation, and distribution-free risk certification. This work instantiates it in two procedures: CPS and CRISP. CPS generates a fixed pool of prompts from training data, then certifies candidates on a held-out evaluation set using simultaneous upper confidence bounds and selects the certified prompt with the highest benign utility. CRISP instead integrates risk feedback into an adaptive search, using hard example-guided rewriting and a reusable-holdout interface to steer generation toward the feasible utility frontier. Experiments on four datasets covering prompt injection, system-prompt leakage, and sensitive-information disclosure show that risk-certified selection consistently respects the target missed-attack level on heldout tests, while utility improves as the permitted risk is relaxed. CRISP is especially useful when fixed-pool search fails to produce certifiable high-utility candidates.
Nov 14, 2026

PSK: A Matrix-Free Single-Loop Method for K-Level Physics-Based Control

Physics-based control is central to robot learning, but differentiating through implicit physics steps typically requires Hessian or Karush--Kuhn--Tucker (KKT) linear solves; we ask whether gradient steps suffice. Each simulation step minimizes an energy under many contact and collision constraints. Without constraints, we view control over KK steps as KK-level optimization with strongly convex lower levels, recast as one min--max problem. Our Penalized Single-loop KK-level method (PSK) uses only gradients and a projection, updates all levels in parallel, and reaches an εε-stationary control in O(ε−3)O(ε^{-3}) iterations, with a KK-independent exponent but a KK-dependent constant. Contact-rich constraints, however, typically violate a constraint qualification (CQ). We replace each constraint by a smooth wall that acts on a band of constant width. Under mild assumptions that need no CQ, every exact solution of the banded lower levels is then feasible and banded Fritz--John, and PSK keeps the O(ε−3)O(ε^{-3}) complexity. Without a CQ that is uniform in the band width, however, a shrinking band loses the KK-independent exponent: with width εε and fixed K≥2K\geq2, deterministic zero-respecting methods need Ω(ε−(K+3)/4)Ω(ε^{-(K+3)/4}) calls on a hard instance whose control dimension grows with 1/ε1/ε. We prove our assumptions for smoothed kinematic and dynamic multi-robot navigation among segment obstacles. In navigation experiments, PSK, tuned per case, reaches every goal with sixteen levels and, at equal time, reaches a lower loss than tuned unrolling in 17 of 18 cases, while implicit differentiation is lower in 10.
Nov 13, 2026

STAMP: Manufacturing-Informed Generative Design and Shape Optimization of Sheet Panels

Generative design of formed sheet panels must preserve geometric manufacturing conditions while exploring layouts and improving performance. STAMP embeds these conditions directly in the shape representation. Each panel is described by its material layout and a reference surface with one height at each occupied position in a plane perpendicular to the drawing direction. Nominal thickness is prescribed along the normal. The representation allows curved surfaces, ribs, and openings. It excludes reference-surface undercuts and keeps nominal thickness fixed without manufacturing penalty terms. Because these conditions belong to the representation, every generated and optimized panel satisfies them regardless of training-set size. Boundary-conditioned diffusion generates alternative layouts, and predictor gradients guide a surface optimization that retains outlines, openings, and designated fixed regions. We demonstrate STAMP on automotive hood inner panels using CarHoods10k. With a comparable number of stored values, depth maps reconstruct surfaces more accurately than point-cloud and voxel baselines. From only five training designs, one of three training runs yields novel and varied layouts. A generator trained on 500 designs, 6.5% of the training set, already reaches the layout variety of the full-data model. Across 11 held-out design families, predictor-based selection among existing dataset designs yields an average gap of 0.18 mm to the best available FEA deformation, versus an expected 1.59 mm for random selection. It does better than random selection in all 11 families. At a 10% depth-change bound, a network not used in the search predicts an average deformation reduction of 24.8% for six generated and existing panels, with a 3.2% average mass increase computed from geometry. Engineers can thus explore and optimize panels within this manufacturing-informed design space.
Nov 13, 2026

Optimizing Drilling Trajectories in Multi-Material Structures Using Quantum Annealers

In this work we present a quantum-hybrid optimization approach for planning drilling trajectories on multi-material structures, with the objective of minimizing total energy consumption. The proposed formulation models the drilling process as a constrained routing problem in which each hole must be visited while accounting for heterogeneous material properties, material-dependent drilling costs and displacement energy, as well as tool-wear penalties. Our method incorporates realistic industrial constraints, including open-path routing and mandatory grouping of holes belonging to the same material to avoid frequent tool-bit changes. The modeled problem is solved using D-Wave's Leap Constrained Quadratic Model Hybrid Solver. To evaluate performance, we benchmark instances ranging from 10 to 55 holes with varying material distributions and cost matrices. The results highlight the capability of quantum-hybrid optimization to handle complex multi-physics constraints and to generate energy-efficient drilling sequences under realistic manufacturing conditions.
Nov 13, 2026

Federated Soft Poly-Level Learning Over a Distributed Network with Guaranteed Convergence

Multi-level learning/optimization, e.g., bilevel optimization, has been recognized for its versatile applicability across a broad array of domains, spanning from signal processing to machine learning. However, most existing works focus on bilevel and trilevel optimization. In contrast, multi-level optimization problems involving four or more hierarchical levels, which we term poly-level learning (PLL) problems, remain largely unexplored.In addition, in practical PLL, data may be distributed across multiple nodes over a distributed network. Nevertheless, extant studies on PLL predominantly focus on the non-federated setting, necessitating the collection of data to central servers and thereby posing potential privacy risks. To this end, we propose a Federated Poly-Level Learning (FPLL) framework over a distributed network to tackle the PLL problems with soft constraints in a federated manner. FPLL hinges on a novel non-linear cut, i.e., LL-cut, for the level-wise relaxation to the PLL problems. Additionally, the proposed federated algorithm is designed with adjustable parameters that allow for a flexible trade-off between its computational complexity and performance efficiency, enabling users to tune it according to specific application requirements. We also carry out non-asymptotic analysis to derive the iteration complexity for the proposed FPLL to achieve the εε-Pareto stationary point. Extensive experiments have been undertaken to elucidate the superior efficacy of the proposed method.
Nov 12, 2026

Calibrated Early Termination with Bounded Optimality Gaps for Constrained Vector Search

Vector search over learned embeddings is the retrieval layer of recommendation and retrieval-augmented generation, and many applications cap how many answer items one category may contribute. Graph indexes answer a query by best-first traversal, and where it stops determines its cost and whether its answer is exact. We study early termination for such constrained kk-nearest-neighbor (kk-NN) queries, with plain kk-NN as a special case, and seek the cheapest stopping rule whose answer is exact with probability at least 1−ε1-\varepsilon. Learned early-termination methods instead target average recall, which does not guarantee exact answers. Multiple testing can calibrate any parameterized stopping rule to our target, but it cannot tell how much a better rule with the same risk and observations would save. Answering this needs a lower bound on the optimum of a rule family too large to enumerate, valid for the query population. Our key idea is to declare the observations a rule may use and to consider every rule monotone in them. Risk-constrained stopping then becomes a linear program over an order polytope, whose Lagrangian minimizers form a nested chain of staircase rules computed exactly by dynamic programming. Fixed-sequence binomial tests along this chain calibrate our rule, CaST, whose failure probability is at most ε\varepsilon with confidence 1−δ1-δ. Lagrangian weak duality bounds the optimum of the declared class from below at all risk levels at once, without a union bound over the rules. On two datasets of one million items each, CaST replayed on logged searches costs at most 1.132 times the class optimum for risk levels from 0.03 to 0.10, at 95% joint confidence per setting. Larger savings thus need a rule outside the class. At a common risk target on held-out queries, CaST is faster than every other calibrated rule we time, which take 4.8% to 45.5% more mean time.
Nov 8, 2026

Resolvent Ellipsoid for Minty Set Inclusions

We study Minty set inclusion on a compact convex set X⊆Rd\mathcal{X} \subseteq \mathbb{R}^d with a set-valued operator A:X⇉RdA : \mathcal{X} \rightrightarrows \mathbb{R}^d. Under the Minty promise, the goal is to compute x∈Xx \in \mathcal{X} and u∈A(x)u \in A(x) such that sup⁡y∈X⟨u,x−y⟩≤ε\sup_{y \in \mathcal{X}} \langle u, x - y \rangle \le \varepsilon. Our approach is geometric and we work in the fixed-scale constrained-resolvent oracle model, where a query at anchor aa is assumed to return a resolvent point x+x^+ together with the Yosida vector gη(a)=(a−x+)/ηg_η(a) = (a - x^+)/η. We prove that each oracle response yields a sharp dichotomy: either the returned point provides an ε\varepsilon-SVI certificate, or the Yosida vector defines a strict separating normal for the Minty set. Thus, a single black-box resolvent query supplies either a certified candidate solution or a valid geometric cut. Combining this separation principle with the ellipsoid method, we obtain RESOLVENT-ELLIPSOID, an algorithm that computes an ε\varepsilon-SVI in O ⁣(poly⁡(d,log⁡(1/ε)))\mathcal{O}\!\left(\operatorname{poly}(d, \log(1/\varepsilon))\right) black-box oracle calls to the fixed-scale constrained resolvent. For monotone inclusions, our algorithm gives, to our knowledge, the first O ⁣(poly(d,log⁡(1/ε)))\mathcal{O}\!\left(\mathrm{poly}(d, \log(1/\varepsilon))\right) black-box guarantee in the fixed-scale resolvent model.
Nov 8, 2026

Large-Scale Hierarchical Decision-Making in Robot Control via ADMM

Sparse hierarchical nonlinear programming (SH-NLP) based on the ℓ0\ell_0-norm provides a powerful framework for integrated, efficient hierarchical decision-making in robot kinematic control, for example in the presence of a large set of possible end-effector candidate locations. While Sequential Sparse Hierarchical Quadratic Programming (S-SHQP) with interior-point method based SHQP sub-problem solvers exploit the hierarchical, sparse structure of such problems, they are less amenable to effective warm-starting between subsequent, coherent control steps. In this work, we formulate an Alternating Direction Method of Multipliers (ADMM) to efficiently solve related SHQP sub-problems. We introduce efficient substitutions for auxiliary variables representing ℓ0\ell_0-norm surrogates. The solver efficiently handles separable decision functions by evaluating linear algebra expressions in the appropriate order. Results in large-scale kinematic and dynamic control show reduced computation times of up to 23.5% compared with a structure-exploiting interior-point method in low- to moderate-accuracy regimes. Furthermore, hierarchical decision-making is extended to whole-body dynamic control for humanoid walking, where the need for high-accuracy solutions is highlighted.
Nov 7, 2026

CONSTRAINER: Promptable Graph-Structured Optimization via Constraint Conditioning

Neural methods for graph-structured optimization have achieved strong performance within individual problem classes, but are typically trained for fixed formulations, limiting reuse across related problem variants. Recent progress in foundation models has motivated shared neural backbones trained across multiple graph-structured optimization tasks; however, existing approaches primarily share instance-level representations while treating feasibility constraints implicitly. A key source of shared structure across constrained optimization problems is the constraint set itself, which often exhibits substantial overlap across tasks. We propose CONSTRAINER, a constraint-conditioned framework for graph-structured optimization that treats constraints as structured inputs. Constraint specifications are parsed into operator graphs and encoded using a graph neural network to produce invariant constraint embeddings, which condition a shared backbone model for solution prediction. We evaluate our approach on power grid optimization and mixed-integer linear programming problems, where it shows improved solution optimality and enables efficient transfer learning and generalization compared to baseline methods.
Nov 7, 2026

GEAR: A GPU-Accelerated Global Solver for Bounded Continuous Nonlinear Programs via Linear Bound Propagation

We present a novel GPU-accelerated global solver for constrained nonlinear programming (NLP) inspired by the efficient linear bound propagation framework in neural network (NN) verification. Existing work on NN verification, a problem that can be cast as feasibility detection for a nonlinear objective, demonstrated orders-of-magnitude speedups with the linear bound propagation-based framework when compared to traditional solvers. Extending this paradigm to global nonlinear programming requires addressing many challenges: a global constrained NLP solver must effectively exploit all, possibly unstructured, nonlinear constraints to improve the objective, whereas NN verification typically handles simple input box constraints over a well-structured NN and does not directly optimize an objective function. We address these challenges by fully exploiting the linear bounds produced by bound propagation: these linear bounds can be viewed as relaxations of nonlinear constraints and used to provide lower bounds, check infeasibility, and guide the search for a primal solution. In addition, we propose tighter linear relaxations for bilinear, quotient, and other commonly used nonlinear functions in NLP problems, and a projected augmented Lagrangian method tightly coupled to our dual solving procedure to produce primal solutions. Our method solves 421 of 505 bounded and continuous NLP problems in the GAMS and MINLPLib benchmarks under a 180-second limit, more than each of the six global solvers we compare with, including Gurobi and BARON (commercial), and SCIP (open-source). Sixteen of these problems are certified by none of the six global solvers; all of them contain exponential, logarithmic, or trigonometric terms, which are often challenging for traditional approaches. Project webpage is at https://verified-intelligence.github.io/GEAR.
Nov 5, 2026

Randomized and Oracle-Based Feasible Directions Methods for Nonsmooth Nonconvex Constrained Optimization

Minimizing nonsmooth nonconvex objectives over general convex sets using no derivatives of the objective, together with structural access to the constraint set, poses a fundamental geometric difficulty: at boundary points, the feasible direction cone may fail to be closed, preventing the construction of finite sets of search directions that capture all feasible descent directions. We develop a feasible-directions framework for problems structured as the difference between a continuously differentiable function and a convex function over a closed convex set, and access the objective without knowledge of its decomposition, through exact line searches along feasible segments. To address the geometric obstruction, we introduce ηη-feasible directions, which remain uniformly separated from the boundary of the feasible direction cone, enabling finite-direction search even in the presence of nonlinear constraints. We present two algorithmic realizations of this framework. The first assumes access to an ηη-direction oracle and extends feasible-directions methods from linear to general convex constraints. The second replaces the oracle by a noise-augmented randomization scheme that constructs spanning directions from the affine-hull inner normal and almost surely avoids nonsmooth boundary points when initialized outside that set. Under curvature bounds and Lipschitz continuity of the smooth component's gradient, we jointly control the spanning coefficients and feasible step lengths of the oracle construction. This yields finite-time approximate dd-stationarity along every unit feasible direction admitting a prescribed positive step length. For both methods, we also establish a rate in the proximal directional minimization (PDM) measure, assuming uniformly bounded direction-set sizes. Randomized exploration ensures that, almost surely, every accumulation point is dd-stationary.
Nov 5, 2026

Projection-Free Gradient Tracking Neurodynamic for Distributed Nonnegative Sparse Optimization

This paper proposes a continuous-time, projection-free neurodynamic system based on gradient tracking for distributed nonnegative sparse optimization. Unlike traditional methods, our approach avoids projecting states onto the feasible set. Instead, it employs gradient tracking to estimate average gradients under heterogeneous costs, coupling primal and dual dynamics such that feasibility and sparsity emerge naturally from the equilibrium conditions. The system ensures unique solutions through a locally Lipschitz vector field and guarantees that every equilibrium corresponds to an exact KKT point. We establish rigorous convergence guarantees for convex objectives through three distinct analytical layers. These include a centralized kernel rate, a computable distributed rate derived from Jacobian analysis without restrictive stability assumptions, and a global exponential stability proof based on Lur'e system theory. Our analysis quantitatively separates these layers, revealing that the convergence rate is primarily limited by graph sparsity and remains robust to variations in momentum time scales. Numerical experiments on strongly convex quadratic problems validate the theoretical rates, demonstrate effective active set recovery, and show that the system maintains stable tail convergence rates even under strong local heterogeneity.
Nov 3, 2026

Refined CMA-ES for CEC 2026 Bound-Constrained Single-Objective Optimization

We present a simplified and parameter-adjusted variant of CMA-ES designed for the CEC 2026 Bound-Constrained Single-Objective Optimization competition. Unlike typical algorithmic developments that increase complexity by adding mechanisms, Refined CMA-ES systematically removes components that do not improve performance, such as the flat-land escape, while retaining standard features that provide measurable benefits. Adjusting key parameters (population size and initial step-size) yields substantial gains, outperforming the baseline CMA-ES and several state-of-the-art competitors. The paper highlights the practical relevance of individual CMA-ES components under the CEC 2026 ranking, which equally weights solution accuracy and convergence speed, demonstrating that simplification combined with improved parameter settings can lead to superior performance.
Oct 31, 2026

HALO-LP: A Homogeneous All-Shifted Non-Interior-Point Method for Linear Programming

This letter introduces HALO-LP, a novel homogeneous all-shifted non-interior-point method for linear programming (LP). The proposed method combines a homogeneous self-dual (HSD) embedding with all-shifted nonlinear complementarity (NCP) functions and proximal primal-dual regularization, enabling arbitrary primal-dual warm starts without requiring strictly interior iterates. The resulting Newton equations admit a condensation based on a positive-definite matrix that can be efficiently factorized using Cholesky decomposition, while the HSD embedding enables primal and dual infeasibility detection through Farkas certificates. Numerical evaluations on perturbed LP instances derived from the Netlib test set demonstrate state-of-the-art warm-starting performance, outperforming the competing solvers in the evaluated setting. We further validate optimality and infeasibility detection on analytically characterized LP problems. Finally, we demonstrate HALO-LP's applicability to robotic optimal control through sequential linear programming (SLP) for centroidal walking and trotting of quadrupedal robots.
Oct 31, 2026

ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints

ALDER, a single-loop augmented-Lagrangian damped extragradient method, is proposed for smooth nonconvex--concave minimax problems with nonlinear coupled inequality constraints. Within an augmented-Lagrangian framework, ALDER combines prediction--correction steps for the primal variables with explicit projected-and-relaxed multiplier updates in a single loop. The penalty parameter is fixed throughout each run, eliminating inner-loop subproblem solves and iterative penalty updates. We establish uniform boundedness of the relaxed multiplier sequence and, under an extended Mangasarian--Fromovitz constraint qualification, boundedness of the projected output multiplier. Building on these bounds, we show that ALDER finds an ε\varepsilon-KKT point within O(ε−7/2)\mathcal{O}(\varepsilon^{-7/2}) complete first-order oracle evaluations in the strongly concave setting and O(ε−4)\mathcal{O}(\varepsilon^{-4}) in the concave setting. These bounds improve upon the best known complexity bounds for multi-loop algorithms for this problem class, achieved by FAL, by removing a log⁡(1/ε)\log(1/\varepsilon) factor, while retaining a single-loop update structure.
Oct 31, 2026

Conic Certification of Transformer Attention

Attention is the computational core of large language models, yet the verifiers that bound how far an attention head's output can move under input perturbations give no guarantee on how loose their bounds are. A weak certificate therefore cannot be told apart from a fragile model. We develop a conic programming theory of attention certification that supplies this guarantee. We prove that the difficulty lies not in the softmax but in the bilinear interaction of a varying query with the keys. This interaction makes certification NP-hard over boxes and inapproximable once the attention logits can move by a constant amount. A fixed query or listed token substitutions, by contrast, make the exact worst case efficiently computable. An exponential cone moment relaxation then certifies a head with an error bounded quadratically in the perturbation radius by computable quantities, an order that cannot be improved. We also show that relaxations that treat a network one operation at a time, linear bound propagation among them, pay on second-order terms a sum of per-operation maxima instead of one coupled maximum. Computational results on GPT-2 indicate that the theory carries over to a trained model. Against exact worst cases with the query fixed, the certificate attains the predicted second-order accuracy. It is tighter than linear bound propagation on every head, and the looseness of bound propagation tracks the predicted per-operation excess.
Oct 28, 2026

Convex-SKM-Net: Low-Latency Block Halfspace Corrections for Neural Convex Constraint Satisfaction

Fast inference and strict constraint satisfaction are essential for learning-based decision-making. Existing methods often rely on constraint-specific projections or feasible-set parameterizations, while iterative repair can be costly. We introduce Convex-SKM-Net, a convex constraint-satisfaction layer that forms linearization halfspaces from residual and (sub)gradient oracles without constraint-specific inequality projectors. It applies fixed-depth dual projected-gradient descent (dual PGD) to minimum-displacement block problems using GPU-friendly matrix operations. We jointly learn the predictor and a positive-definite mobility, adapting the correction geometry to improve objective quality. We prove convergence of the outer iterates at fixed dual depth and linear convergence in distance under Slater's condition and bounded subgradients. All our test outputs on three second-order-cone model-predictive control (SOC-MPC) horizons and six power-system convex relaxations satisfy a 10−310^{-3} feasibility tolerance. Comparisons with the latest constraint-satisfaction methods show inference speedups of up to 144.3×144.3\times on SOC-MPC and 7.7×7.7\times on a convex quadratically constrained quadratic programming (QCQP) benchmark with joint training. On QCQP, the mean objective gap is 0.012%0.012\%, with full test feasibility at 10−410^{-4}. Learning mobility reduces the five-seed affine-task mean gap by 22.4%22.4\% and improves gaps in matched power-system comparisons.
Oct 27, 2026

Understanding Large Language Models as Numerical Optimizers

Large language models (LLMs) have emerged as potential tools for numerical optimization. Despite promising results, their intrinsic optimization capabilities and limitations remain poorly understood, particularly in high dimensions. This paper investigates the ability of LLMs to exploit mathematical problem structures and generate feasible, near-optimal solutions. We develop an evaluation framework that distinguishes solution quality from execution failures, including numerical inaccuracies, constraint violations, and output-format errors. Using representative problems from convex optimization, fractional programming, and constrained projection, we assess LLM performance against deterministic reference solvers across different dimensions. Our results reveal that LLMs can capture useful optimization structures and produce near-optimal solutions, even when their outputs fail to satisfy numerical or formatting requirements. However, reliability deteriorates with increasing problem dimension and depends strongly on the underlying optimization structure. To further investigate the limitations, we deploy an iterative refinement mechanism that provides targeted feedback on feasibility and solution quality. The results demonstrate that iterative refinement substantially improves reliability and extends the range of problem dimensions over which LLMs produce valid solutions. Nevertheless, persistent numerical and structural errors limit their applicability as standalone optimizers. These findings provide insights into the capacity and limits of LLM-based optimization and motivate hybrid approaches that combine LLM reasoning with deterministic numerical verification.
Oct 27, 2026

GNBG-C: A Unified and Configurable Benchmark Generator for Constrained Continuous Optimization

Many real-world optimization tasks are governed not only by what should be optimized, but also by what is allowed: a solution must first satisfy physical, operational, safety, budgetary, or structural requirements before its objective value becomes meaningful. Yet benchmark design for constrained continuous optimization often treats these restrictions as fixed properties of predefined test instances. Existing generators and benchmark suites provide essential foundations for reproducible comparison, but they either focus primarily on configurable objective landscapes or expose constraint properties within limited, predefined regimes, making it difficult to ask targeted questions about constraint-induced difficulty: whether an optimizer struggles because feasible regions are small, boundaries are restrictive, variables are tightly coupled, or constraint information is poorly scaled. We introduce GNBG-C, a Generalized Numerical Benchmark Generator for Constrained Continuous Optimization. The central idea is to treat the feasible region itself as a configurable object rather than as an inseparable attachment to a fixed test function. By generating controlled constraint regimes around the known GNBG global minimizer, the generator enables systematic studies in which feasibility pressure can be varied while preserving that point as a global minimizer of the constrained problem. This allows researchers to examine how optimizers discover feasibility, handle constraint pressure, and improve objective quality under diverse and controllable feasibility conditions. GNBG-C therefore provides a flexible and auditable framework for probing the strengths and weaknesses of constrained continuous optimizers under targeted forms of feasibility-side difficulty.
Oct 26, 2026

Constraint Learning by Optimizing over Trained Neural Networks: A Pragmatic Tutorial

Constraint learning is an emerging paradigm of modeling optimization problems with the help of machine learning. In this paradigm, trained machine learning models are embedded into the optimization model. For example, we can learn constraints empirically from available data, or we can avoid using a nonlinear objective function by learning a simpler approximation for it. Neural networks become a compelling option if the machine learning models must capture more elaborate and nuanced relationships. However, optimization models embedding neural networks may become too large or too slow to solve. In this tutorial, we present practical considerations for an effective and efficient use of constraint learning with neural networks and validate it with a case study highlighting the benefit of smaller and sparser networks.
Oct 26, 2026

Reward-Guided RRT* for Budgeted Task and Motion Planning

Robotic missions involving spatially distributed tasks often require jointly selecting rewarding locations and planning feasible motions under limited travel budgets. This paper proposes Reward-Guided RRT*, a new sampling-based framework that constructs a budget-feasible mission through a sequence of locally joint task-selection-and-motion-planning stages, evaluated directly in the continuous state space, without requiring a precomputed task-transition graph. The method incrementally builds a mission using reward-guided RRT* searches, while a return-feasibility procedure ensures that each selected task can be visited without violating the mission budget. Experiments with increasing obstacle complexity and number of tasks show solutions comparable to VNS-PRM* while requiring substantially fewer sampled states. We also extend the framework to Dubins steering and evaluate it in CoppeliaSim with a scaled car-like robotic platform, demonstrating its ability to incorporate vehicle kinematic constraints.
Oct 25, 2026

Constrained Gradient Equilibrium: Approachability under Locally Constrained Adversaries

Gradient equilibrium (GEQ) is a recent framework in online learning that requires the time-averaged gradients along the learner's trajectory to vanish. We study GEQ when the learner is constrained and ask when such an equilibrium remains achievable in an adversarial environment. We first show that constrained GEQ (CGEQ) can be impossible even under simple and slowly varying constraints, motivating imposing local temporal structure on the adversary. We then develop an approachability framework for CGEQ under locally constrained adversaries, and obtain necessary and sufficient characterizations in the spirit of classical Blackwell approachability. Beyond these theoretical characterizations, we provide an algorithmic principle that converts window-wise no-regret learners into CGEQ algorithms under a local feasibility condition with margin. Experiments on synthetic and real data demonstrate that the resulting algorithms perform strongly in both achieving GEQ and respecting the constraints.
Oct 24, 2026

A Differentiable Chassis Safety Layer for Intelligent Vehicle Motion Control

Learning-based vehicle motion control requires coordination between diverse task objectives and state-dependent chassis safety constraints. Conventional cascaded architectures may compromise task performance when safety filters modify nominal commands independently of policy learning. This article proposes a differentiable chassis safety layer that modularly integrates task-oriented control with explicit physical constraints. Actuator limits, individual-tire force constraints, and vehicle handling envelopes are incorporated into sequential quadratic programs. Each projected command propagates the predicted vehicle dynamics and updates subsequent constraints, enabling temporal gradient coupling through implicit differentiation. A two-stage learning strategy combines expert imitation with risk-guided supervision and conditional intervention guidance to coordinate nominal control decisions with chassis safety constraints. Closed-loop evaluations under unseen scenarios, emergency maneuvers, and ablation studies demonstrate that the proposed method improves safety-performance coordination and exploits vehicle dynamic potential while maintaining handling stability.
Oct 22, 2026

Reliable AI-Assisted Decisions via Selective Auditing

We consider online monitoring of an AI system that produces a sequence of decisions. At each round, the system outputs a proposed decision together with a confidence score estimating the trustworthiness of the decision. The decision and confidence score need not be produced by the same model: for example, one agent may propose a decision, while a separate verifier agent evaluates it and outputs a correctness or safety score. Based on this information, we must decide whether to accept the AI decision automatically or consult an expert, such as a human auditor, who reviews the proposal and either accepts or corrects it. We formulate this task as an online constrained optimization problem in which the goal is to minimize the frequency of expert auditing while guaranteeing that the fraction of AI errors that go unaudited stays below a user-defined threshold. We derive a family of algorithms with provable error-control guarantees with no assumptions, including a method that is optimally efficient: it asymptotically attains the best achievable auditing rate for both adversarial and i.i.d. data streams. Experiments on screening harmful requests to large language models, qualitative text annotation, and data labeling show that our methods achieve valid error control in practice while substantially reducing the need for human auditing compared to baselines.
Oct 20, 2026

Automatic Differentiation with Constraints in Forward and Inverse Problems

Approximate solutions of partial differential equations (PDEs) on unstructured grids can be represented on a graph. Numerical optimization involving stiff evolutionary and static PDEs often requires solving a large system of equations, which can be treated as a constraint. In this work, we present a fully differentiable graph-based implicit solver that incorporates this constraint. We evaluate its performance across four key tasks: a) linear and nonlinear forward modeling of evolutionary and static problems, b) solving inverse problems to estimate equation coefficients, c) solving inverse problems to estimate the right-hand side, and d) learnable graph coarsening to accelerate forward modeling. The stability and differentiability of our solver enable significant reductions in the complexity of forward modeling while efficiently addressing related inverse problems. These capabilities make it a powerful tool for different physics and engineering applications, in particular for geophysics, where inverse problems are commonly solved in order to reduce the model uncertainty.
Oct 19, 2026

ASTOR: Benchmarking and Improving Autoformulation for Soft-Constraint Optimization with a Formal Grammar

Real-world decision problems combine two qualitatively different kinds of constraints: requirements that must be satisfied, called hard constraints, and preferences that can be violated, called soft constraints. Because these problems are often posed to decision-makers in natural language, large language models offer a natural tool for assisting with their solution. This has given rise to autoformulation, which focuses on using LLMs to translate natural-language descriptions of decision problems into executable mathematical optimization models. However, this research often neglects soft constraints like those proposed by consumers, managers, and planners, despite the fact that many practical problems require modeling them explicitly. We introduce ASTOR, an inference-time framework that maps a natural-language decision problem to a grammar-guided abstract syntax tree (AST) before deterministically compiling the resulting representation into executable optimization code. We also introduce SoftOR, a unified benchmark of natural language problems which focuses on soft constraint formulations. On SoftOR, ASTOR achieves the best aggregate accuracy among comparable single-request and multi-agent LLM methods while remaining competitive on standard autoformulation benchmarks that include only hard constraints. Code and data are available at https://anonymous.4open.science/r/astor-softor-iclr-E34C/README.md.
Oct 19, 2026

Learning SOCP Solver Dynamics with Graph Neural Networks

Second-order cone programs (SOCPs) are a fundamental class of convex optimization problems widely applied across engineering domains. Classical interior-point methods are robust and accurate, but their iterative nature can be costly in real-time or repeated-solve settings. This has motivated learning-based solvers that approximate optimizer solutions with neural networks. Recent work has increasingly studied graph neural networks (GNNs) for linear, quadratic, and second-order cone optimization, leveraging their ability to model sparse relational structure among variables, constraints, and objective functions. Most existing GNN-based solvers compress the optimization process into a single forward pass, predicting the optimizer directly without using the intermediate trajectory produced by classical solvers. We introduce SOCPNet, a recursive GNN framework that uses solver trajectories to learn an iterative SOCP solution procedure. A shared GNN model is applied repeatedly, refining the current iterate at each step and enabling inference for a variable number of iterations. Rather than predicting the solution in a single pass, SOCPNet learns from intermediate iterates to progressively refine its estimates using a trajectory-regularized training procedure. We evaluate SOCPNet on multiple datasets spanning standard SOCP problem classes and show that it consistently reduces the final solution error relative to a SOCP-GNN baseline. Finally, we demonstrate how trained SOCPNet models can be used in a hybrid optimization pipeline by warm-starting a classical interior-point solver, reducing solver iterations without loss of accuracy.
Oct 18, 2026

Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares

We establish sharp degree bounds for Putinar sum-of-squares (SOS) certificates in terms of the positivity margin δδ. For any fixed Archimedean quadratic module with prescribed generators and any fixed degree bound on the objective, normalized polynomial objectives admit a uniform certificate-degree upper bound of O(δ−1/2log⁡2(2/δ))O(δ^{-1/2}\log^2(2/δ)). The bound is sharp: we construct a matching lower-bound example in three variables. We further show that the number of inequality generators affects the optimal degree bound. For quadratic modules with at most two inequality generators, the bound improves to O(δ−1/2log⁡(2/δ))O(δ^{-1/2}\log(2/δ)), which is also sharp. This improvement is obtained by directly converting two-generator Stengle refutations into certificates for the original quadratic module. We also establish sharp degree bounds for trigonometric SOS certificates on tori. In particular, for the full torus without additional constraints, the optimal worst-case order improves to δ−1/4δ^{-1/4}, whereas additional equality constraints can lead the order to δ−1/2log⁡(2/δ)δ^{-1/2}\log(2/δ). These results also yield sharp worst-case convergence rates for the Lasserre hierarchy.