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.

Aug 7, 2026

Flow-Corrected Shape Optimization: Taming Manifold Drift in High-Dimensional 3D Models

Optimizing 3D shapes within the latent spaces of deep generative models is fundamental to computer assisted engineering, yet remains prone to a critical failure mode we term manifold drift: the tendency of gradient-based optimization to move latent vectors away from the manifold of valid shapes. This problem is exacerbated in state-of-the-art 3D shape generative models that operate in increasingly high-dimensional latent spaces where valid shapes occupy a vanishingly small fraction of the full space. Existing mitigation strategies, including latent regularization and flow-matching approaches, either sacrifice expressiveness, demand a difficult trade-off between objective guidance and generative fidelity that remains prone to manifold drift, or are computationally infeasible to scale to modern, large-capacity 3D shape models. We introduce a novel optimizer-corrector framework that alternates between gradient steps for objective minimization and guided flow matching to drive the latent state back to the valid shape manifold. By decoupling objective minimization from flow-based correction, optimizing freely and correcting strictly, this alternating design avoids inherent trade-offs, preserving geometric validity without sacrificing expressiveness while remaining computationally feasible on modern 3D shape models. We demonstrate its effectiveness across generative priors of varying complexity, from simple vector latent spaces to large-scale architectures across a variety of downstream optimization tasks, including aerodynamic drag reduction and object compliance optimization.

Emilien Seiler, Nicolas Talabot, Yingxuan You +2

CVLab, EPFL

Constrained Generative Modeling3D Shape GenerationConstrained Optimization
AskPDF
Aug 6, 2026

Muon on the Stiefel Manifold Admits an Exact Closed-Form Update

We study Muon, a recently proposed matrix-aware optimization method, in the context of the Stiefel manifold. This manifold consists of matrices with orthonormal columns and is ubiquitous in machine learning and scientific computing. Existing extensions of Muon to this manifold rely on heuristic, approximate, or iterative updates with varying computational efficiency. We show that the corresponding Stiefel Muon update admits an exact closed-form solution and use this result to develop Skewon, a practical algorithm for orthogonality-constrained optimization with an efficient implementation. We further establish first-order convergence guarantees for Skewon in the smooth non-convex setting.

Mikhail Solonko, Molozhavenko Alexander, Maxim Rakhuba

HSE University, Moscow, Russia.

Stiefel Manifold OptimizationRiemannian OptimizationOrthogonal OptimizationMuon OptimizerNonconvex OptimizationConstrained Optimization+1
AskPDF
Aug 5, 2026

Differentiating Through Dual Prices: End-to-End Policy Learning Under Capacity Constraints

Many social services assign scarce resources, such as housing assistance or hospital interventions, to people who arrive one at a time. Each arrival must receive a decision immediately, and the long-run usage of every resource must stay within its capacity. We study how to learn such a policy from logged observational data. Recent work (Tang et al., 2024) proposes a decision-blind pipeline that fits one outcome model per treatment by regression, prices each capacitated resource from those models, and assigns each arrival the treatment with the largest predicted outcome minus price. We instead train the outcome models end-to-end, differentiating an off-policy estimate of the deployed policy's value through the dual prices themselves. We study two formulations: an exact nonconvex one, and a convex relaxation whose optimum always satisfies the capacity constraints in expectation and whose suboptimality can be explicitly bounded. Every method is evaluated in a queueing simulation to capture the online decision structure. Across six datasets, our two end-to-end variants lead the delay-adjusted policy value wherever capacity is scarce, once a waiting period carries even a small cost. In particular, decision-blind regression predicts ground truth more accurately, but when resource capacities are stringent these baselines frequently violate them and incur much longer queueing delays. Thus, end-to-end training is best suited to settings where resources are genuinely scarce and feasibility matters.

Mohammadsaeed Haghi, Mahdi Salmani, Nima Kelidari +2

University of Southern California

Constrained OptimizationDifferentiable OptimizationOnline Resource Allocation
AskPDF
Aug 5, 2026

CARGO-VL: Counterfactual Arbitration with Risk-Constrained Group Optimization for Vision-Language Models

Vision-language systems combine images with retrieved text, but these sources can disagree or jointly fail to support an answer. Reliable models must identify the trustworthy source and abstain when neither is adequate. Existing post-training objectives score instances independently and therefore do not enforce coherent behavior under counterfactual evidence changes. We introduce CARGO-VL, a group-relative framework that optimizes matched variants covering aligned, image-correct, text-correct, and both-wrong (A/V/T/N) evidence states as one bundle. Its objective couples condition-wise correctness with transition rewards for answer invariance, source equivariance, and answer-to-abstention switching, while a primal-dual controller balances unsafe answers against excessive deferral. We also contribute XMC (eXtended Modal Conflict), a four-condition conflict training resource, and evaluate transfer on CMC-Bench and Modality-Bias. Across multiple seeds, CARGO-VL improves conflict handling, unsupported-answer avoidance, and modality balance over pointwise baselines. Ablations identify complementary benefits from relational transition signals and adaptive risk control, supporting counterfactual consistency as a practical objective for reliable multimodal evidence arbitration.

De Jiang, Zhengyang Zhang, Kehong Yuan +1

VLM RobustnessCounterfactual Evaluation of VLMsConstrained Optimization
AskPDF
Aug 4, 2026

LaPrune: Controllable Differentiable Sparsity at Million Scale

Top-kk selection determines which components of a sparse model remain active. Hard selection blocks gradients, while continuous relaxations often couple mask hardness to the selected mass. We introduce LaPrune, a mathematically exact-budget differentiable layer that controls the normalized second moment while preserving the selected mass. A LapSum barrier preserves the selection mass, and a normalized second-moment constraint moves the mask from a dense equal-mass allocation toward hard top-kk at each budget. We derive a population prediction of the saturated fraction, a near-binary limiting law, and a tight worst-case guarantee on the near-zero fraction. The normalized hardness parameter is invariant to score scale, while a fixed LapSum temperature is not.

Jakub Antczak, Joanna Wojciechowicz, Łukasz Struski +1

Wrocław University of Science and Technology, Wrocław, Poland · Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland

Constrained Optimization
AskPDF
Aug 4, 2026

Exploiting Separability in Multi-Scale Grey-Box Bayesian Optimization

We consider grey-box optimization problems where the decision variables naturally partition into black-box variables (as arguments to an expensive black-box function) and white-box variables, governed by a set of explicit, closed-form equations that also depend on the output of the black-box function. We exploit this separability through a bilevel reformulation: an outer Bayesian optimization (BO) to optimize the scalar objective as a function of black-box variables alone, while an inner problem solves the white-box subproblem via global optimization. The Gaussian process surrogate used in BO is therefore defined rather than and white-box constraints are satisfied exactly whenever the inner optimizer converges to a feasible point---without penalty functions, chance constraints, or moment approximations. On a suite of 13 benchmark problems, bilevel BO achieves lower regret, with fewer iterations and wall clock time. This advantage is robust to initialization set size, exploration parameters, and inner-solver choice.

Joshua E. Hammond, Tyler A. Soderstrom, Brian A. Korgel +1

McKetta Department of Chemical Engineering, The University of Texas at Austin, 200 E. Dean Keaton St. Stop C0400, Austin, Texas 78712, USA · ExxonMobil Technology and Engineering, 22777 Springwoods Village Pkwy, Spring, Texas 77389, USA · Energy Institute, The University of Texas at Austin, 2304 Whitis Ave. Stop C2400, Austin, Texas 78712, USA +1

Bayesian OptimizationBilevel OptimizationConstrained Optimization
AskPDF
Aug 2, 2026

MixedComplementarityProblems.jl: A Fast, Batched, Open-Source Interior Point Solver for Mixed Complementarity Problems

Mixed complementarity problems (MCPs) arise as the first-order optimality conditions of nonlinear programs and noncooperative games, and provide a natural formulation for multi-agent trajectory optimization problems that appear throughout robotics. The dominant solver for problems of this form is PATH, which offers strong performance on robotics problems but remains closed-source. We present MixedComplementarityProblems.jl, an open-source, pure Julia implementation of an interior point method for parametric MCPs that: (i) matches PATH's reliability on standard benchmarks, (ii) natively supports batched, parallel processing of many parameter instances, either across CPU threads or on an NVIDIA GPU, and (iii) supports efficient automatic differentiation of solutions with respect to problem parameters. On a multi-agent lane-change trajectory game representative of robotics planning problems, our CPU-multithreaded batched solver clears a batch of parametric instances ~100x faster than sequential calls to PATH. A GPU backend, running the same solver implementation unmodified, also clears these batches far faster than PATH, but does not outperform the multithreaded CPU on this problem; the GPU pulls ahead only once each per-instance KKT system grows large, and we characterize this regime dependence. We describe the solver's interior point formulation, the abstraction that lets a single solver implementation run unmodified across dense, batched-sparse, and single-large linear-algebra backends, and report benchmarks against PATH on both randomly generated quadratic programs and trajectory games.

David Fridovich-Keil

Department of Aerospace Engineering and Engineering Mechanics The University of Texas at Austin Austin, TX, USA

Constrained Optimization
AskPDF
Jul 29, 2026

Parameterized Fair Resource Allocation under Diversity Constraints

Resource allocation across multiple agent groups arises in many applications including e-commerce recommendation systems, housing assignment, and course allocation, and is commonly formulated as an optimization problem with diversity constraints to ensure group fairness. Existing approaches typically enforce these constraints as hard conditions, which overly restrict the feasible solution space and often lead to suboptimal allocations. In this paper, we propose PRA, a parameterized framework for fair resource allocation under diversity constraints. Inspired by the use of risk-aversion parameters in economic models, PRA introduces a set of controllable inequality-aversion parameters to softly regulate group-level diversity, thereby enabling flexible trade-offs between fairness and allocation efficiency. With appropriately calibrated parameters, PRA yields fairness-optimal assignments that comply with the specified diversity constraints. To accommodate additional application-specific constraints, we further extend the framework to an adaptive variant, APRA. We establish that the optimality of both PRA and APRA holds regardless of the chosen fairness metric and the nature of the additional constraints, underscoring the generality and robustness of our approach. Extensive experiments on three real-world applications demonstrate that our proposed framework consistently outperforms existing baselines in both effectiveness and robustness.

Keke Huang, Yik Yu Ng, Laks V. S. Lakshmanan +1

Huazhong University of Science and Technology Wuhan, Hubei, China · The University of British Columbia Vancouver, BC, Canada · McGill University Montreal, Quebec, Canada +1

Fair Resource AllocationGroup FairnessConstrained Optimization
AskPDF
Jul 28, 2026

Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling

Distributed constraint optimization problems (DCOPs) provide a popular framework for distributed decision making under limited communication, but many real-world instances are too large to solve monolithically. We address this challenge from two complementary directions. We revisit the connection between DCOPs and potential games, and adapt modern online learning algorithms for equilibrium finding to DCOPs. We show that these algorithms are competitive with representative incomplete DCOP algorithms. We then turn to decomposition frameworks for large-scale DCOPs, motivated by large-scale decentralized satellite scheduling. We propose a new framework that separates a DCOP into two interacting subproblems: a high-level meta-DCOP for task allocation, and independent local optimization problems for scheduling. To couple the two levels, we develop a novel iterative pricing method that updates the meta-level utilities using feedback from the local optimizers. Combining our online learning methods with our iterative pricing framework, we obtain near-optimal performance on real-world decentralized satellite scheduling problem instances, fulfilling over 99% of observation requests compared with 87% for state-of-the-art baselines.

Itai Zilberstein, Pranav Rajbhandari, Steve Chien +1

Department of Computer Science, Carnegie Mellon University · Jet Propulsion Laboratory, California Institute of Technology · Additional affiliations: Strategy Robot, Inc., Strategic Machine, Inc., Optimized Markets, Inc.

Distributed OptimizationPotential GamesConstrained OptimizationOnline Learning
AskPDF
Jul 28, 2026

Optimization with Dynamic Constraint Learning (DCL)

We propose Dynamic Constraint Learning (DCL), a data-driven framework for constrained optimization when constraint functions are unknown and cannot be queried during optimization. At each iteration, the method learns a local surrogate from nearby data and solves a subproblem within a data-supported trust region. Compared with offline global constraint learning, the approach uses local surrogates that adapt to the data distribution during optimization and can achieve solution quality comparable to that of global models while using simpler local models and smaller optimization subproblems. We demonstrate the performance of DCL on a synthetic test problem and two case studies from the literature.

Ezgi Oztekin, Figen Oztoprak, S. Ilker Birbil

Department of Mathematics, Gebze Technical University · Department of Industrial Engineering, Gebze Technical University · Amsterdam Business School, University of Amsterdam

Surrogate-Assisted OptimizationBlack-Box OptimizationConstrained Optimization
AskPDF
Jul 28, 2026

Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization

Constrained online convex optimization requires minimizing regret against adversarial convex costs while satisfying a convex constraint at every round, as needed in safety-critical applications. A computationally efficient method combines online gradient descent with a Polyak feasibility step, using one constraint evaluation and one subgradient per round. Although this method achieves O(sqrt(T)) regret with per-round feasibility, we derive a tighter, data-dependent analysis by retaining two quantities omitted by the standard worst-case argument. First, we replace the gradient envelope G_f^2 T with the observed accumulation G_T = sum_t ||grad f_t(x_t)||^2. Second, we identify a nonnegative Polyak correction P_T that measures the cumulative squared displacement caused by feasibility projections and enters the regret bound with a negative sign. The resulting improvement, Delta_T = (eta/2)(G_f^2 T - G_T) + P_T/(2 eta), is always nonnegative. We further propose AdaOGD-PFS, an adaptive-step-size method that achieves O(sqrt(G_T)) regret while preserving per-round feasibility. Experiments on ball- and halfspace-constrained problems improve the regret bound by 38 to 43 percent, with both data-dependent gradients and Polyak corrections contributing substantially.

Wentao Zhang

Tsinghua Shenzhen International Graduate School · Tsinghua University

Online Convex OptimizationConstrained OptimizationAdaptive Gradient Methods
AskPDF
Jul 28, 2026

Balancing multiscale similarity and cartographic constraints: A similarity-driven optimization framework for line generalization

Cartographic generalization is essential for generating multiscale map representations by balancing information preservation and cartographic readability. However, automated generalization remains challenging because existing approaches often treat spatial similarity evaluation, cartographic constraints, and parameter optimization as separate processes, limiting adaptive and interpretable control across scales. This study formulates cartographic generalization as a constrained multiscale similarity optimization problem and proposes a similarity-driven framework for adaptive generalization control. The framework integrates multiscale spatial similarity as an optimization objective to quantify representation consistency between original and generalized data, while incorporating cartographic constraints to regulate readability, smoothness, and geometric validity. A unified objective function is optimized to automatically identify scale-dependent parameter configurations for different generalization algorithms. Experiments using multiple line simplification algorithms, target scales, and similarity measures, including geometric, structural, and learning-based metrics, demonstrate that the proposed framework achieves an effective balance between similarity preservation and cartographic abstraction. The results further show that combining similarity optimization with cartographic constraints provides more consistent and interpretable parameter control than relying on similarity evaluation alone. This study provides a unified optimization perspective that connects similarity assessment, constraint modeling, and algorithm control, contributing to adaptive and automated cartographic generalization.

Pengbo Li, Haowen Yan, Xiaomin Lu +1

Faculty of Geomatics, Lanzhou Jiaotong University, Lanzhou 730070, China · National-Local Joint Engineering Research Center of Technologies and Applications for National Geographic State Monitoring, Lanzhou 730070, China · Key Laboratory of Science and Technology in Surveying & Mapping, Lanzhou 730070, China

Spatial GeneralizationConstrained Optimization
AskPDF
Jul 28, 2026

Beyond Single-Episode Optimization: Sliding-Window Aware Generative Auto-Bidding for Long-Term Advertising Effectiveness

Auto-bidding systems optimize bids to maximize value under efficiency constraints such as Cost-Per-Action (CPA). Existing methods treat each day as an independent episode. However, many advertisers produce value so sparsely that per-day efficiency ratios become statistically unreliable, undermining advertiser retention. Platforms therefore evaluate window-level efficiency over sliding windows of W=7W{=}7 days, ensuring fair evaluation and long-term advertising effectiveness. This creates cross-episode coupling: each day's bidding decisions affect up to WW overlapping windows, so setting daily targets requires anticipating future market conditions. We propose SWAG-Bid (Sliding-Window Aware Generative Auto-Bidding), a hierarchical framework decomposing this challenge into episode-level planning and step-level execution. The planner uses a Masked Trajectory Model to forecast markets and generate candidate plans, scored across all overlapping windows by Multi-Window Model Predictive Control Sampling (MWMS) with exponential confidence decay. The controller adjusts reliance on this guidance through a state-adaptive gate, Per-Step Gated Adaptive Layer Normalization (PSG-AdaLN), complemented by Return-to-Go and Cost-to-Go channels carrying budget and constraint information. Experiments on AuctionNet-Sparse and online A/B tests on AliExpress show that SWAG-Bid achieves competitive constraint satisfaction and value acquisition under sliding-window evaluation.

Binglin Wu, Chuan Yue, Yingyi Zhang +4

Dalian University of Technology · Alibaba International Digital Commerce Group · Dalian University of Technology & City University of Hong Kong

Automated BiddingOnline AdvertisingConstrained Optimization
AskPDF
Jul 27, 2026

Smooth Learning with Hard Constraints via Legendre-Regularized Policies

We revisit contextual optimization from the perspective of policy class design. A desirable policy class should be expressive enough to learn rich context-decision relationships, should enforce hard feasibility constraints rather than soft penalty terms, and should remain smooth enough for gradient-based training on downstream decision losses. Existing approaches usually emphasize only part of these requirements. We propose Legendre-regularized policies, which parameterize decisions as solutions of regularized optimization problems over the original feasible region. This construction yields policies that are feasible by construction and differentiable with respect to learned latent parameters. We prove that the associated optimizer map is single-valued, maps onto the relative interior of the feasible set, admits an explicit Jacobian, is Lipschitz continuous, and can be made arbitrarily smooth. We also establish a universal approximation result showing that the proposed class can approximate any continuous feasible policy on compact context sets. The framework unifies explicitly regularized optimizers and implicit perturbation-based smooth optimizers. Experiments on contextual newsvendor and resource allocation problems show that our approach improves prescriptive performance relative to the benchmark methods.

Zikun Lin, Rui Chen, Yijie Wang

Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Hong Kong, China. · School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, China. · School of Economics and Management, Tongji University, Shanghai, China.

Decision-Focused LearningConstrained OptimizationDifferentiable Optimization
AskPDF
Jul 26, 2026

A Multi-stage Constrained Optimization Framework for Data-driven Problems

Variational autoencoders (VAEs) transform high-dimensional, often noisy data into a compact latent representation, making downstream optimization more tractable. Three challenges persist in VAE-based constrained optimization: (i) sampling effectively within the latent space, (ii) identifying the active decision variables that actually influence the objective and constraints, and (iii) enforcing constraints without destabilizing training. We propose a Multi-stage Constrained Optimization Framework (MCOF). First, an entropy-constrained VAE (EC-VAE) coupled with a feature selector embeds objective and constraint information into a designated subset of latent variables, so that optimization proceeds over a low-dimensional subspace while the remaining coordinates supply solution diversity. Second, a Uniform Transformation (UT) module applies a per-dimension probability integral transform, replacing the irregular aggregate posterior with a uniform distribution over a bounded box and mitigating posterior collapse and Gaussian mixture bias. Third, a constraint-priority filter method (CPFM) solves the resulting surrogate problem by alternating violation-reduction and objective-reduction steps under a filter acceptance test, returning solutions that are feasible for the learned surrogate to a specified tolerance without requiring multiplier estimation. Finally, unselected latent coordinates are resampled to generate diverse decodings of a single optimized solution. We validate MCOF on a synthetic problem, where we ablate each stage and recover the analytic optimum, and on a ZINC250k drug design task, where the generated molecules satisfy the imposed constraints and are entirely novel relative to the training set.

Ye Shi

Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA

Variational AutoencodersConstrained Generative ModelingConstrained OptimizationLatent Space Optimization
AskPDF
Jul 26, 2026

Constraint-Bound Agnostic Bayesian Optimization: One Model for All Thresholds

Expensive constrained optimization problems in real-world industry design often involve constraint thresholds that are difficult to determine in advance. Engineers may need to adjust constraint thresholds to explore different feasibility-performance trade-offs, requiring solutions under a wide range of threshold settings. However, existing constrained Bayesian optimization methods treat each threshold configuration independently, leading to repeated optimization and failing to exploit the shared relationship among continuously varying thresholds. To address this challenge, we propose constraint-bound agnostic Bayesian optimization (CBA-BO), a learning-based framework that learns a parametric constraint model mapping thresholds to optimal solutions. Once learned, CBA-BO directly predicts solutions for arbitrary unseen threshold configurations without additional optimization, with a one-step Bayesian optimization refinement further improving solution quality. Experiments on benchmark and engineering problems demonstrate that CBA-BO learns a transferable threshold-solution mapping, enabling efficient prediction and optimization for arbitrary threshold queries. An intent-guided constraint-bound recommendation mechanism is further developed to improve objective performance while satisfying user-specified constraint preferences.

Jin Wang, Xi Lin, Handing Wang

School of Artificial Intelligence, Xidian University, China · School of Mathematics and Statistics, Xi’an Jiaotong University, China

Bayesian OptimizationConstrained Optimization
AskPDF
Jul 24, 2026

FMOPF: Latent Flow Matching with Constraint-Aware Interaction Priors for AC Optimal Power Flow

AC optimal power flow determines the minimum-cost generation dispatch under nonlinear power balance constraints and is solved thousands of times daily in electricity market operations. Learning a direct mapping from load conditions to OPF solutions can accelerate this computation, yet with deepening renewable penetration, a single optimal dispatch is no longer sufficient. Operators require a characterization of the distribution of feasible near-optimal solutions for risk quantification, sensitivity analysis, and multi-objective trade-off assessment. Supervised neural networks provide fast point predictions but cannot capture this conditional distribution. Diffusion-based generative models can sample diverse solutions in principle, yet existing methods operating in the raw state space exhibit degraded solution quality and fail to scale beyond medium-sized systems. We identify the root cause as the conflation of two distinct tasks within a single model. Compressing the high-dimensional OPF solution manifold is one task, and learning the conditional mapping from loads to that manifold is another. This paper presents FMOPF, a framework that resolves this conflation by decoupling compression from generation through latent flow matching and by explicitly modeling load-state coupling through a Constraint-Aware Interaction Prior Network. Experiments on four IEEE test systems demonstrate that FMOPF provides the most effective Newton-Raphson warm starts, achieves the lowest tail risk among generative methods, and is the first such method to scale to systems with several hundred buses while preserving full feasibility. Ablation studies confirm that the latent generation pipeline is a necessary condition for physical feasibility and that the interaction prior functions as a late-stage tail-risk controller.

Zhilin Huang

China Southern Power Dispatching and Control Center, China Southern Power Grid

Constrained Generative ModelingFlow MatchingUncertainty QuantificationOptimal Power FlowConstrained OptimizationPower Systems
AskPDF
Jul 21, 2026

Online Optimization of Difference-of-Convex Compositions with Smooth Mappings

We study online optimization for a broad class of structured non-convex non-smooth problems where each loss is a composition of a difference-of-convex function with a smooth mapping, and the feasible region is defined by constraint functions of the same kind. We propose a time-smoothed proximal linear algorithm and a local-regret measure based on a proximal residual mapping. We show that this residual is a proper stationarity measure for the original problem: its fixed-point condition implies first-order stationarity. Our analysis relies on a tangent-cone characterization for a feasible region described by composite difference-of-convex constraints, which is of independent interest and allows each update to be computed via a convex optimization oracle, despite the non-convexity of the problem. We establish a local-regret bound and a bound on the total number of inner convex subproblems. We also derive an error bound connecting the proximal residual to the distance to stationarity, providing a quantitative certificate of approximate stationarity.

Jingwei Ji, Jong-Shi Pang, Renyuan Xu

Management Science and Engineering, Stanford University · The Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California

Nonconvex OptimizationConstrained OptimizationProximal Optimization
AskPDF
Jul 21, 2026

Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory

We prove two lower bounds for the first order oracle complexity of minimizing a dd-dimensional 11-Lipschitz convex function over the unit ball with mm bits of memory. We first show that any such (possibly randomized) algorithm must make Ω~(d2m)\tildeΩ(\frac{d^2}{\sqrt{m}}) oracle queries. For deterministic optimization algorithms, we show that Ω~(min⁡{d1.6,d8/3m2/3})\tildeΩ(\min\{d^{1.6},\frac{d^{8/3}}{m^{2/3}}\}) queries are required. For all memory regimes of interest, these improves upon the previous best known lower bounds of Ω~(max⁡{d8/3m4/3,d4/3m1/6})\tildeΩ(\max\{\frac{d^{8/3}}{m^{4/3}},\frac{d^{4/3}}{m^{1/6}}\}) and Ω~(d5/3m1/3)\tildeΩ(\frac{d^{5/3}}{m^{1/3}}) for randomized and deterministic algorithms respectively. Notably, due to existing upper bounds, our lower bound for deterministic algorithms is the first to show a sharp oracle complexity phase transition around m≈d2m\approx d^2, where a polylogarithmic change in memory leads to a poly(d)\mathsf{poly}(d) change in the number of required oracle calls. Further, when the suboptimality is polynomially small in dd, our lower bound randomized algorithms is the first to show that Ω~(d2)\tildeΩ(d^2) memory is necessary to nearly match the optimal query complexity among algorithms without memory constraints. Previously, such a result was only known for the regime where the suboptimality is quasipolynomially small in dd.

Michael Menart, Aleksandar Nikolov, Ohad Shamir

Department of Computer Science, University of Toronto, Vector Institute · Department of Computer Science, University of Toronto · Weizmann Institute of Science and University of Toronto +1

Query ComplexityOracle ComplexityMemory-Efficient OptimizationConstrained Optimization
AskPDF
Jul 19, 2026

An Iterative Geometric Approach to Optimizing Separating Hyperplanes

Given a binary-labeled linearly separable dataset, and the objective is to compute the maximum-margin separating hyperplane, also known as the hard-margin Support Vector Machine (SVM) classifier. This paper investigates whether, if given an initial separating hyperplane, can it be exploited to reach this unique optimum more efficiently. We present a geometric approach that gradually improves the alignment of the hyperplane, starting from an initial separating hyperplane, while preserving separation and continuously increasing its margin until convergence to the global optimum. At each iteration, the method considers only local information, namely the current active set, and aims to re-align the hyperplane according to the optimal separating hyperplane of this reduced subset. Consequently, the original convex quadratic optimization problem is addressed through a sequence of smaller subproblems. The paper presents the algorithm in detail, together with a preliminary experimental evaluation and several theoretical findings. The results suggest that, when an initial separating hyperplane is available, the proposed method can be competitive on larger datasets and, in some cases, can outperform state-of-the-art approaches that solve the optimization problem directly.

Akos Hajnal

Laboratory of Parallel and Distributed Systems Institute for Computer Science and Control (SZTAKI) · John von Neumann Faculty of Informatics Obuda University Budapest, Hungary

Support Vector MachinesConstrained Optimization
AskPDF
Jul 19, 2026

Constrained Path Reasoning: Measuring When Committed Stages Earn Their Cost

When does a committed intermediate stage in an LLM reasoning pipeline earn its cost? Constrained Path Reasoning (CPR) pairs a source-aware path hypothesis with stage-level accounting. Search generates provisional states; trusted or validated invariants can constrain hard, while other proposals remain soft and revisable. CPR predicts that task-compatible commitments can factor transitions, concentrate candidate mass, induce regularity, and expose feedback when their gains exceed propagated error and execution cost. The formalism covers discrete commitments and continuous flows and measures effective branching, endpoint concentration, and cost per usable output. Across 1,180 generated QCQPs and 40 engineered degenerate polynomial instances (2,140 endpoints), residual triage recovers 63.0% of repair-all's additional feasible yield with 17.7% of its attempts. Fixed-LLM accounting (270 unique calls shared across nested arms) finds usable yield of 41.1% direct, 90.0% after formalization and deterministic execution, 20.0% after one-shot convexification, and 21.1% for the full path. In 120 paired-condition calls, a two-action rollback rule reaches 90% usable yield versus 36.7% for the feedback-conditioned selector. Two endpoint probes separate source from validation: a 72-output cross-trajectory transplant reduces entropy and acceptable mass; a 24-output same-call self-proposal pilot gives unchanged two-repeat collision entropy, 25.0% versus 8.3% usable yield, and 1/8 deterministically confirmed endpoint checks. Model-generated states supply hypotheses; trusted execution earns constraint strength.

Honglin Li

ShanghaiTech University

LLM Inference EfficiencyInference-Time SearchCost-Aware InferenceConstraint-Guided Reasoning in Language ModelsConstrained Optimization
AskPDF
Jul 18, 2026

Certified-Gap Dual-Price Policies for Real-Time Truckload Bid Acceptance with Relocating, Clock-Constrained Resources

A truckload carrier must accept or reject each load tender within seconds. The decision depends on fleet state, hours-of-service (HOS) clocks, and appointment windows. We model this as a weakly coupled dynamic program in which the resources relocate and carry clocks: serving a request moves the truck to a new market and depletes its clocks, and whether a truck can serve a request depends on its state. Occupancy-based reusable-resource models do not cover this setting. We build a real-time dual-price policy from the same Lagrangian relaxation that gives the problem's upper bound. Policy and bound come from one object, so every run reports a certified optimality gap. We prove three things. First, the certificate is valid for any duals, any discretization, and any surrogate quality. Second, the policy's same-time spatial-gradient rule is exactly fluid complementary slackness, and the policy is asymptotically optimal in the subcritical fluid regime; the fitted prices are also portable across sample paths, by linear-programming basis stability. Third, certificates have limits: per-resource Lagrangian slack can stay bounded away from zero at every fleet size. We exhibit a three-truck kernel with an exact rational certificate and a replication lemma. On a public closed-loop benchmark with thirty paired seeds, the policy -- which needs no rollout labels, only one offline dual solve -- beats a rollout-trained surrogate on two of three scenarios (tight: +2.0 pp, 95% CI [+0.5, +3.6], Wilcoxon p = 0.023; mild: +3.5 pp, CI [+2.4, +4.5]) and ties the third. It decides in 0.04-0.09 ms, three orders of magnitude faster than the Monte Carlo rollout teacher. Its certificates are stable across ten bounded instances per scenario, at 57-64% of optimal, within 3-6 points of what the 1000x-slower teacher certifies.

Aswin Chandrasekaran

Bubba AI

Real-Time SchedulingIntelligent Transportation SystemsVehicle RoutingConstrained OptimizationOnline Resource AllocationReal-Time Bidding
AskPDF
Jul 18, 2026

Hybrid Augmented Lagrangian Method for General Constrained Optimization via Evolutionary Algorithms

Constrained Optimization Problems are crucial in fields such as engineering, economics, and robotics, where high-dimensional search spaces and complex objectives and constraints are common. Numerical optimization methods, including Feasible Direction, Interior Point, and Sequential Quadratic Programming, have shown strong performance in finding feasible local optima, but require accurate analytical gradients and effective initialization, which can be challenging in real-world settings. Evolutionary Algorithms, on the other hand, offer gradient-free search and robustness to noisy landscapes, managing to detect global optima more often than numerical methods, but they often suffer from high computational costs and slow convergence. In this work, we propose a Hybrid Augmented Lagrangian (HyAL) method that integrates the AL framework's constraint-handling strengths with the exploratory power of population-based search. Our approach employs evolutionary techniques to solve subproblems within the AL iterations, promoting exploration and aiding in the escape from local optima. We conduct extensive experiments on benchmark optimization problems, comparing our method against state-of-the-art optimizers, including IPOPT and CMA-ES, and a standalone evolutionary optimization baseline (with constraint enforcement via penalties). In addition, we evaluate four population-based methods integrated within the AL framework to study the effect of different evolutionary solvers. Our results show that HyAL consistently produces high-quality solutions across the benchmark suite. It outperforms purely evolutionary approaches and scales more effectively to high-dimensional constrained problems, where evolutionary-only methods often struggle. HyAL also surpasses state-of-the-art numerical optimization algorithms on complex landscapes containing numerous local minima and saddle points.

Lampros Printzios, Konstantinos Chatzilygeroudis

Laboratory of Automation & Robotics (LAR), Department of Electrical & Computer Engineering, University of Patras, University Campus, Patras, GR-26504, Achaia, Greece

Evolutionary OptimizationAugmented Lagrangian MethodConstrained Optimization
AskPDF
Jul 17, 2026

Agentic Calibration of Grey-Box Simulation Models: An LLM-Driven Alternative

Calibration of grey-box simulation models is a constrained optimization problem in which model evaluations are expensive, the parameter space can be high-dimensional, and the search must respect plausibility constraints. Although the simulation code is fully available to the analyst, the joint effect of multiple parameters remains difficult to predict analytically. Classical optimizers such as Nelder--Mead (NM) are simple to deploy but sample-inefficient, particularly under constraints. Modern Bayesian Optimization methods achieve competitive solutions with far fewer evaluations but require non-trivial modeling machinery for constraint handling. We introduce an agentic calibration method in which a large language model acts as the optimizer, with constraints incorporated as a plain-language section of the system prompt. We evaluate the agentic method, NM, and Bayesian Optimization (BO) on an anal cancer simulation model under both unconstrained and clinically constrained calibration. Under unconstrained calibration, the agentic method achieves substantially lower best error than BO and NM, while requiring fewer model evaluations. Under constrained calibration, the agentic method reaches comparable error levels and both outperform NM. These results are obtained at the cost of increased inference time per iteration. Agentic calibration achieves competitive performance with substantially fewer model evaluations, and constraint handling is essentially free at the modeller-facing interface through simple textual specifications rather than additional modelling machinery. The main trade-off lies in increased per-iteration inference cost, making the approach particularly suitable when simulation time dominates. Beyond performance, the per-iteration rationale makes the search auditable and explainable, so its decisions can be scrutinised and justified to third parties.

David Gómez-Guillén, Mireia Diaz, Josep Lluis Arcos +1

Unit of Infections and Cancer – Information and Interventions (UNIC-I&I), Cancer Epidemiology Research Program, Catalan Institute of Oncology-IDIBELL, L’Hospitalet de Llobregat, Spain · Autonomous University of Barcelona (UAB), Spain · Centro de Investigación Biomédica en Red de Epidemiología y Salud Pública (CIBERESP), Ministerio de Ciencia, Innovación y Universidades, Madrid, Spain +1

Parameter EstimationBlack-Box OptimizationLarge Language Model-Guided OptimizationModel CalibrationConstrained Optimization
AskPDF
Jul 15, 2026

Constraint-Driven Model Optimization: An Industry Framework for Selecting Compression and Acceleration Techniques in Modern Machine Learning Systems

The rapid deployment of machine learning systems across cloud, edge, and enterprise environments has brought model optimization to the forefront of systems-engineering. Despite a rich literature spanning quantization, pruning, knowledge distillation, parameter-efficient fine-tuning (PEFT), and inference-time optimization, practitioners are often left navigating these techniques through heuristics rather than principled methodology. We argue that optimization should be formulated as a constraint-driven, multi-objective engineering decision and introduce a unified framework that characterizes any production deployment along five interacting constraint dimensions: data availability, latency budget, memory budget, accuracy tolerance, and retraining budget. Building on this taxonomy, we synthesize empirical gains reported across the research literature and map them to operational constraints rather than algorithmic categories. To ensure practical relevance, we selected these techniques by reviewing recent literature for methods that report measurable improvements against critical deployment bottlenecks. We propose a prescriptive decision framework and provide optimization pipelines for four representative industrial scenarios to illustrate it in practice. To the best of our knowledge, this work provides one of the first structured attempts to formalize model optimization as a constraint-aware, multi-objective engineering process, synthesizing quantitative evidence from the research literature.

Dhruv Shivkant, Saket Mohanty, Utkarsh Wadhwa

Indian Institute of Science · EXL

Model CompressionConstrained OptimizationMulti-Objective Optimization
AskPDF
Jul 15, 2026

Safe Overtaking for Autonomous Racing Using Hierarchical Optimization and Learning-Based Control

Autonomous racing overtaking requires balancing competitive performance with safety under nonlinear vehicle dynamics and real-time constraints. Model Predictive Control (MPC) combined with Control Barrier Functions (CBFs) provides a principled mechanism for certifying forward invariance of a safe set. However, commonly used fixed-decay discrete-time CBF formulations can become overly conservative in interactive racing scenarios, limiting overtaking performance and requiring manual tuning across track conditions. This paper proposes a hierarchical overtaking framework that explicitly separates maneuver-level decision making from safety-certified trajectory control, reducing conservatism while preserving safety. A high-level Mixed-Integer Quadratic Program (MIQP) resolves the combinatorial passing-side selection problem by selecting a feasible overtaking topology, while a nonlinear Frenet-frame MPC enforces vehicle dynamics and safety through embedded discrete-time CBF constraints. This decomposition isolates the combinatorial complexity of maneuver selection from the continuous trajectory optimization. To further mitigate the sensitivity of fixed-decay barrier constraints, a reinforcement learning policy adapts the discrete-time CBF decay parameter online, enabling context-dependent modulation of safety margins without directly controlling vehicle inputs. Simulation and scaled-hardware experiments show that no single fixed decay parameter achieves uniformly strong performance across tracks, whereas the adaptive strategy attains the highest aggregate success rate and consistently strong safety--performance trade-offs without per-track tuning, improving robustness to environment variation while maintaining safety constraint satisfaction in nominal operation.

Hassan Jardali, Kai Yin, Lantao Liu

Luddy School of Informatics, Computing, and Engineering, Indiana University · Machine Learning Science, Expedia Group, Austin, TX 78758 USA

Nonlinear MPCControl Barrier FunctionsAutonomous RacingConstrained OptimizationMixed-Integer QP
AskPDF
Jul 14, 2026

Globalized Constrained Stein Variational Inference for Diverse Feasible Robot Motion Planning

Robot motion planning is inherently multimodal, yet classical planners typically return only a single solution. Probabilistic formulations address this limitation by maintaining a distribution over motions, allowing the planner to reason over multiple low-cost alternatives. In robotics, however, motion samples must also satisfy strict constraints, including collision avoidance, joint limits, contact conditions, and dynamics consistency. These hard requirements make motion sampling substantially more challenging: within a limited planning budget, the ensemble must cover diverse low-cost motions while ensuring that every sample remains feasible under the relevant constraints. We propose SteinSQP (Stein Variational Sequential Quadratic Programming), a constrained Stein variational inference method for diverse feasible robot motion sampling. SteinSQP evolves an interacting particle ensemble, as in Stein variational methods, while embedding constraints directly into a kernel-space SQP subproblem. We solve the resulting constrained Stein-Newton subproblem with a GPU-friendly matrix-free primal-dual algorithm, enabling efficient batched ensemble updates. To globalize the method, we introduce an ensemble-level merit function that jointly balances objective value, constraint violation, and particle diversity. Across five constrained motion-planning tasks, SteinSQP returns fully feasible ensembles while preserving diverse motion alternatives. Compared with first-order constrained Stein baselines and serial multistart nonlinear programming, SteinSQP shows faster and more robust ensemble convergence in terms of iterations, improves particle-wise feasibility, and achieves faster batched time-to-solution on challenging robot-scale tasks.

Jiayun Li, Georgia Chalvatzaki

PEARL Lab, Dept. of Computer Science, TU Darmstadt. · Hessian.AI, Darmstadt, Germany. · Robotics Institute Germany (RIG).

Constrained Motion PlanningConstrained OptimizationMotion PlanningVariational InferenceRobot Motion PlanningMulti-Objective Motion Planning
AskPDF
Jul 14, 2026

A new dual-population constrained multi-objective evolutionary optimization algorithm with repair constraint handling for structural optimization

Structural optimization problems often involve a large number of decision variables and highly non-convex feasible regions, making convergence to the true Pareto front extremely challenging. Even when convergence is achievable, it typically requires thousands of function evaluations, resulting in significant computational cost. This highlights the need for efficient and robust optimization algorithms for real-world engineering applications. In this study, we introduce a novel constrained multi-objective evolutionary algorithm, termed DPCME. The algorithm employs two interacting populations that exchange information, enabling effective global exploration and reducing the risk of convergence to local optima. To further enhance performance, a recent repair-based constraint-handling technique is incorporated, and alternative repair approaches are proposed and systematically evaluated. The proposed algorithm is tested on three engineering problems: the 72-bar truss, the 120-bar truss, and a chemical tanker structure, each involving hundreds of nonlinear failure constraints. Its performance is evaluated against state-of-the-art constrained multi-objective optimization algorithms from the latest PlatEMO package. A total of 43 algorithms are initially tested, from which the 12 best-performing methods are selected for detailed comparison. The results demonstrate that DPCME achieves superior or competitive convergence and diversity across all test cases, and that the inclusion of repair-based constraint handling further improves its performance.

Fardad Homafar, Jasmin Jelovica

Department of Mechanical Engineering, The University of British Columbia, 6250 Applied Science Ln, Vancouver, V6T 1Z4, Canada · Department of Civil Engineering, The University of British Columbia, 6250 Applied Science Ln, Vancouver, V6T 1Z4, Canada

Evolutionary OptimizationMulti-Objective Evolutionary OptimizationConstrained OptimizationMulti-Objective Optimization
AskPDF
Jul 12, 2026

Incremental Transformer for Surrogate-Based Inverse Design of Geopolymer Mixtures

Small-data inverse design is challenging in engineering informatics when observations are heterogeneous, mixed-type, and constrained by physical relations among design variables. This work proposes a topology-aware surrogate framework guided by an Incremental Transformer (INCRT) for physics-constrained inverse design, applied to geopolymer mixture design. The method integrates intrinsic-dimensionality analysis, mixed-variable design-space representation, tabular surrogate prediction, INCRT-based manifold rationalisation, and constrained inverse optimisation. Using a public benchmark of fly-ash and slag-based geopolymer concrete mixtures with compressive-strength and carbon-emission targets, the high-dimensional design space proves strongly redundant, organising around fewer effective mixture regimes. Compressive strength requires nonlinear tabular surrogates, while carbon emission is largely determined by composition and well recovered by regularised linear models. INCRT thus acts not as a replacement for tabular predictors but as a rationalisation layer providing prototype regimes and a manifold-support score for inverse design. Three strategies are compared: unconstrained surrogate optimisation, physics-constrained optimisation, and topology-aware physics-constrained optimisation. Unconstrained optimisation can match target strength but may yield physically invalid or off-manifold candidates; physics-only constraints do not always ensure data support. The topology-aware strategy yields candidates balancing target compliance, carbon reduction, physical admissibility, and proximity to the learned feasible manifold. The framework aims not to replace experimental validation but to support screening of credible candidate mixtures from small, mixed, physically constrained engineering datasets.

Giansalvo Cirrincione, Filippo Grassia

Laboratory of Innovative Technologies (LTI, EA 3899) University of Picardie Jules Verne, Amiens, 80025, Hauts-de-France, France

Surrogate ModelingMaterials Property PredictionMaterials ScienceConstrained OptimizationPhysics-Informed MLInverse Design
AskPDF
Jul 12, 2026

Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)

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. Currently, the best known algorithm is OGD+Projection algorithm of [Vaze and Sinha, 2025] that has simultaneous regret of O(T)O(\sqrt{T}) and CCV of O(T1/3)O(T^{1/3}) for d=2d=2 [Balasundaram et al., 2026], and simultaneous regret of O(T)O(\sqrt{T}) and CCV of O(T)O(\sqrt{T}) for any dd [Sarkar and Sinha, 2026]. In this paper, we show that the CCV of the OGD+Projection algorithm is Ω(Td−12d)Ω(T^{\frac{d-1}{2d}}). This is the first such lower bound result.

Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze

Online Convex OptimizationConstrained Optimization
AskPDF