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.

Oct 3, 2026

ML-OPF-Bench: Benchmarking Machine Learning for Optimal Power Flow

Machine Learning (ML) methods promise a fast solution process for Optimal Power Flow (OPF). While inconsistent test cases, implementations, and evaluation metrics across existing studies make it challenging to determine which algorithmic advances are most critical for real-world deployment. To this end, we propose ML-OPF-Bench, a unified benchmark for AC- and DC-OPF that evaluates representative ML algorithms under a consistent pipeline, stress-tests them across system sizes, distribution shifts, and resource budgets, and ranks them with a multi-objective framework. We find that prediction accuracy alone is not a reliable indicator of operational feasibility. Under heavily loaded, congested conditions, even the strongest in-distribution performers lose their advantage, while feasibility is maintained largely by post-processing that enforces the target constraints rather than by the underlying pure ML predictor. Data scaling shows that prediction accuracy and constraint violations follow different trajectories, whereas compute scaling shows that returns diminish and that larger models do not consistently perform better. These results expose critical trade-offs among ML methods' speed, accuracy, and feasibility, and offer practical guidance for future ML-OPF design. We open-source the benchmark as an extensible Python package for integrating new learning-based OPF algorithms and evaluating them under the same standard as the existing baselines.

Xinyi Liu, Xuan He, Danny H. K. Tsang +1

Dartmouth College · Hong Kong University of Science and Technology (Guangzhou) · University of Alberta

Optimal Power FlowLearning to OptimizeConstrained Optimization
AskPDF
Oct 2, 2026

O~(T)\tilde{O}(\sqrt{T}) Regret and Polylogarithmic Constraint Violation for COCO

We study constrained online convex optimization with adversarial convex costs and constraints (COCO\mathsf{COCO}). At each round t∈[T]t\in[T], a learner selects xtx_t from a dd-dimensional convex decision set XX, after which an adaptive adversary reveals a convex cost function ftf_t and constraint function gtg_t. Consequently, the learner incurs a cost of ft(xt)f_t(x_t) and a constraint violation of max⁡{0,gt(xt)}\max\{0,g_t(x_t)\}, and aims to simultaneously minimize regret and cumulative constraint violation (CCV\mathsf{CCV}) over the entire horizon. Existing algorithms achieve O(T)O(\sqrt{T}) regret and O~(T)\widetilde O(\sqrt{T}) CCV\mathsf{CCV}. We show that an online policy can achieve O(Tlog⁡T)O(\sqrt{T\log T}) regret and O(log⁡2T)O(\log^2 T) CCV\mathsf{CCV}, reducing the CCV\mathsf{CCV} from polynomial to polylogarithmic while retaining near-optimal regret. When all cost functions are either αα-exp-concave or ββ-strongly convex, the algorithm achieves O(log⁡T)O(\log T) regret with the same CCV\mathsf{CCV} bound as above. Our approach combines continuous Hedge with elimination on shrinking feasible sets. The key observation is that whenever the mean of the Hedge distribution violates a constraint, Grünbaum's inequality guarantees that a constant fraction of the Hedge probability mass is eliminated. We use an adaptive learning-rate schedule and a potential function coupling the surviving volume with the learning rate to convert this probability-mass reduction into a bound of O(log⁡2T)O(\log^2 T) on the CCV\mathsf{CCV}.

Dhruv Sarkar, Abhishek Sinha

MIT Cambridge, USA · Tata Institute of Fundamental Research Mumbai, India

Online Convex OptimizationConstrained Optimization
AskPDF
Oct 2, 2026

DePICT: Decision-Preserving Interface for Constrained Downstream Tasks

A constrained optimization problem may involve a parameter in its objective and active constraints, yet the final decision may remain insensitive to small changes in that parameter. This raises a fundamental question: which inputs does a decision making system truly depend on? Building on this question, we introduce DePICT, a procedure for constructing decision preserving interfaces by ranking context directions according to the optimizer's solution sensitivity and aggregating them across an operating regime. We study this problem in a high dimensional setting where primitive context parameterizes a constrained task and the downstream agent observes only a selected subset of context directions. For locally regular constrained programs, we derive a Karush Kuhn Tucker (KKT) based characterization of when a context direction is optimizer relevant. Our analysis shows that appearing in the active optimization problem does not necessarily imply that a variable affects the final decision. Some context directions can alter the KKT conditions while leaving the optimal solution unchanged because their effect is absorbed by the dual variables. DePICT is designed to remove exactly these directions. In a controlled diagnosis, it recovers the decision relevant interface exactly and reduces linear predictor regret to 0.009, compared with 0.475 for the strongest competing baseline.

Utkarsh Grover, Ravi Ranjan, Agoritsa Polyzou +4

University of South Florida · Florida International University · DEVCOM Army Research Lab

Predict-Then-OptimizeConstrained OptimizationFeature SelectionSensitivity Analysis
AskPDF
Oct 2, 2026

A hybrid CNN-adjoint optimization framework for reconstruction of viscoelastic tissue properties in magnetic resonance elastography

Magnetic resonance elastography (MRE) is a noninvasive imaging modality for quantifying the viscoelastic properties of soft tissues from shear wave propagation. Recovering the complex-valued shear modulus from measured displacement fields leads to a severely ill-posed inverse problem, particularly in the presence of noise and limited boundary excitations. We investigate adjoint-based optimization, convolutional neural network (CNN) reconstruction, and a hybrid framework combining both approaches. The forward model is based on a scalar form of the modified stationary Stokes system with a complex shear modulus. We establish well-posedness of the forward problem, existence of minimizers, and first-order optimality conditions for the adjoint-based formulation, and implement a nonlinear conjugate-gradient method with Armijo line search. While PDE-constrained optimization can accurately refine coefficient reconstructions, its performance depends strongly on initialization. We therefore construct a two-dimensional CNN that maps complex-valued displacement measurements to spatially varying complex shear modulus fields and provides rapid, informative initial reconstructions. The proposed hybrid method uses the CNN reconstruction to initialize the adjoint-based optimization, yielding faster convergence and improved accuracy. The CNN is trained on coefficient fields containing individual perturbations and tested on both individual and previously unseen combined configurations. Numerical experiments demonstrate that the CNN generalizes to these more challenging configurations, while subsequent PDE-constrained optimization further refines the reconstructed coefficient. These results demonstrate the potential of combining data-driven initialization with physics-based optimization for efficient and accurate MRE reconstruction.

Anwesa Dey, Johann Rudi, Elena Cherkaev

Department of Mathematics, The University of Utah, address USA. · Department of Mathematics, Virginia Tech, address USA. · Department of Mathematics, The University of Utah, address, address, USA.

Image Inverse ProblemsMagnetic Resonance ImagingConstrained OptimizationConvolutional Neural Networks
AskPDF
Oct 1, 2026

Cross-entropy optimization with prioritized constraints

When constraints conflict, an optimizer must determine which requirements to preserve and which to relax. On the one hand, a priority ordering specifies which requirements take precedence. On the other hand, penalty-based formulations encode their relative importance through numerical weights. Depending on these weights, a solution can improve its weighted score while violating intended priorities. We introduce TierCEM, a variant of the cross-entropy method that incorporates strict constraint priorities directly into elite selection without requiring per-constraint importance weights. TierCEM works by sequentially filtering sampled candidates, from highest- to lowest-priority constraint. If and when a constraint eliminates all remaining candidates, TierCEM returns to the last nonempty set and selects elites with the smallest violations of that blocking constraint, recursively preserving satisfaction of all higher-priority constraints. We evaluate TierCEM on 2D navigation and contact-rich pushing tasks in proprioceptive and learned world-model settings. Experiments show that reversing the constraint ordering changes which constraints are violated under conflict. Prioritizing progress toward the task objective also enables TierCEM to relax lower-priority constraints when they would otherwise prevent further progress.

Francisco Roldan Sanchez, Pau de las Heras Molins, David Fridovich-Keil +1

LTCI, Télécom Paris, Institut Polytechnique de Paris · The University of Texas at Austin

Constrained Motion PlanningBlack-Box OptimizationConstrained OptimizationMulti-Objective Optimization
AskPDF
Oct 1, 2026

Fixing a Model That Learned Worse Cancer Means Lower Risk: Monotonic Constraints in Bladder Cancer Recurrence Prediction

Background and Objective: Clinicians expect recurrence risk to climb with cancer severity. In a UK multicentre trial, an unconstrained XGBoost model learnt that higher tumour stage and carcinoma in situ predicted lower recurrence risk, and discrimination, calibration, and SHAP were all blind to it. We developed a counterfactual testing framework to detect this inversion and a monotonic-constraint framework to remove it without hurting performance. Methods: BOXIT enrolled 472 patients with protocol-mandated cystoscopy across 51 UK sites (2007-2012); 435 had at least two years' follow-up (153 recurrences, 35.2%). We developed a counterfactual direction test and a monotonic-constraint correction, with constraint directions drawn from the EORTC and EAU risk systems, and evaluated both against unconstrained XGBoost and logistic regression on 18 predictors (seven directed) over 50 cross-validation folds. The test worsened each patient on one directed feature at a time to check whether risk fell; SHAP direction and calibration were also assessed. Key Findings and Limitations: Tumour stage and carcinoma in situ were associated with lower recurrence, opposite to medical intuition; the unconstrained model reversed carcinoma in situ counterfactuals in 90.2% of cases and stage in 74.3%. Discrimination (ΔΔAUC 0.005, p=0.47), calibration, and SHAP magnitude were all blind to the inversion. Monotonic constraints eliminated every violation at no cost to discrimination (0.723 vs 0.718) and outperformed EORTC (p=8.9e-16). Limitations: single trial, internal-external validation only. Conclusions and Clinical Implications: A model that had learned this inversion passed every conventional check. A counterfactual direction test, run as a single refit with pre-specified monotonic constraints, catches this failure at no cost to performance and should be routine before clinical deployment.

Saram Abbas, David Thomas, Naeem Soomro +3

School of Engineering, Newcastle University, Newcastle upon Tyne, UK · Electronics and Computer Science, University of Southampton, Southampton, UK · Department of Urology, Freeman Hospital, Newcastle upon Tyne, UK +1

Counterfactual EvaluationGradient-Boosted Decision TreesMonotonicity ConstraintsClinical Outcome PredictionConstrained OptimizationClinical Risk Prediction
AskPDF
Sep 30, 2026

A Simple Doxastic Deontic Logic for Norm-Guided Decision Making

Making decisions despite conflicting norms and incomplete or unreliable information is a fundamental challenge for autonomous systems. We introduce a simple doxastic deontic logic for this setting: a classically reducible fragment of Chellas' Minimal Deontic Logic, extended with explicit conditional norms and combined with multi-agent KD45, so that norms can depend on agents' beliefs about both facts and norms. On this logic we define the Doxastic Norm Compliance Optimization Problem, where an agent chooses a decision minimizing weighted norm violations. We distinguish subjective optimization (relative to the agent's beliefs) from objective optimization (relative to the actual facts). We give conditions under which (i) the two coincide and (ii) optimal decision-making can be reduced to weighted partial MaxSAT in polynomial time.

Thorsten Engesser, Agata Ciabattoni

TU Wien

Logical ReasoningConstrained OptimizationDeontic LogicDecision-Making under Uncertainty
AskPDF
Sep 30, 2026

Autoresearch in Mixed-Integer Linear and Nonlinear Programming

Despite recent progress in autoresearch, applying it to practical operations research problems, typically formulated as NP-hard mixed-integer linear or nonlinear programs (MILPs or MINLPs), remains challenging because effective research requires systematically managing competing ideas and long-horizon experimental trajectories. We introduce AutoMIP, a reusable agent skill for organizing long-horizon autoresearch in mixed-integer programming through idea pooling and algorithm tree search. AutoMIP maintains a persistent pool of complementary candidate ideas while organizing executable experiments into an algorithm tree, enabling the agent to preserve unexplored hypotheses, refine promising algorithms, and switch to alternative methodological directions based on historical states. On MILP and MINLP benchmark cohorts, AutoMIP achieves the highest final success rates among the evaluated autoresearch frameworks. On MIPLib, AutoMIP discovers new best solutions for 31 of 60 instances, surpassing existing autoresearch frameworks. On MINLPLib, it achieves new best solutions for 52 of 60 instances. Ablation studies further demonstrate the complementary contributions of idea pooling and algorithm tree search, highlighting the importance of jointly maintaining diverse research ideas and structured experimental trajectories for long-horizon autoresearch.

Yuwei Gu, Yaoxin Wu, Tong Guo +2

Chengdu University of Information Technology · Eindhoven University of Technology · Nanyang University of Technology +2

Automated Algorithm DiscoveryMixed-Integer Linear ProgrammingConstrained OptimizationAutonomous ExperimentationAutonomous Research Agents
AskPDF
Sep 30, 2026

Generalized Geometry Block Proximal Linearized Method for Multiblock Nonconvex and Nonsmooth Optimization

This paper considers a class of multiblock nonconvex and nonsmooth optimization problems arising in many applications. Existing methods construct proximal linearized operators or their variants within standard Euclidean geometry to solve this class of problems, forcing their block variable updates to rely on the standard inner product and its induced norm. Nevertheless, this construction fails to capture the geometric structure of the target problem, leading to low numerical efficiency. To overcome these drawbacks, we propose a generalized geometry proximal linearized operator for updating block variables, and develop the Generalized Geometry Block Proximal Linearized (GGBPL) method based on this operator. Compared with existing proximal linearized operators, the proposed operator allows the block surrogate functions to be constructed using arbitrary inner products and general admissible metrics, thereby enabling the GGBPL method to adapt its updates to the geometric structure of various problems. We also introduce the inertial version of GGBPL, named the inertial GGBPL (iGGBPL) method. We further establish a new unified convergence framework under this generalized geometry, within which we prove that our methods guarantee convergence of the objective function values, establish global convergence of the generated sequence to a critical point, and derive the convergence rate of our methods. We also establish an O(ε−2)\mathcal{O}(\varepsilon^{-2}) iteration complexity bound for obtaining an ε\varepsilon-stationary point. We apply our methods to two nonconvex and nonsmooth problems: sparse nonnegative matrix factorization with ℓ0\ell_0-constraints and sparse nonnegative CP decomposition with ℓ0\ell_0-constraints. Numerical results demonstrate the superior numerical performance of our proposed methods over several state-of-the-art methods.

Weifeng Yang

Nonconvex OptimizationConstrained Optimization
AskPDF
Sep 29, 2026

A QCQP-Representable IMU Pre-Integration Factor for Certifiable State Estimation

We propose a QCQP-representable IMU pre-integration factor that enables certifiable estimation with pre-integrated inertial measurements. To the best of our knowledge, this is the first work to directly incorporate IMU pre-integration into certifiable estimation. Inertial sensing is a common and reliable modality in robotics, and incorporating it broadens the practical scope of certifiable estimation. The main challenges are obtaining the required algebraic structure and a sufficiently tight convex relaxation. Standard IMU pre-integration relies on the exponential map, which does not admit an exact polynomial representation. Moreover, obtaining a QCQP formulation requires auxiliary lifting variables, for which the standard semidefinite programming (SDP) relaxation can be loose. We address these issues by deriving an IMU pre-integration factor based on the Cayley map and an explicit set of redundant constraints that tighten the resulting relaxation. To validate the proposed factor, we apply it to certifiable GNSS-IMU smoothing and evaluate it on synthetic and real-world data. The results show that the proposed formulation yields tight relaxations and solves the resulting estimation problems to verified global optimality.

Utkarsh Rai, Zhexin Xu, Bang-Shien Chen +1

Robust Autonomy Lab, Institute for Experiential Robotics, Northeastern University, 360 Huntington Ave, Boston, MA 02115, USA

Constrained OptimizationRobot State EstimationInertial Navigation
AskPDF
Sep 28, 2026

Learning Samples Importance: Parameterizing Dual Variables in Everywhere Learning

Everywhere learning provides a principled framework for training AI models under constraints that must hold throughout the data distribution. In the dual domain, these pointwise constraints give rise to functional dual variables. In this work, we propose to learn these dual variables, motivated by the fact that their values encode useful information about the underlying constrained problem. By representing the dual variable as a parametric function of each sample, we enable the learned multiplier to be evaluated on new, unseen samples. This contrasts with standard empirical dual formulations, which assign an independent multiplier to each training sample. We characterize the error in the recovered primal solution induced by restricting the dual variable to a parametric function class and show that it is controlled by how well this class approximates the optimal statistical multiplier. Moreover, we show that the learned parametric multiplier retains the sensitivity interpretation of the optimal statistical multiplier, yielding approximate sensitivity guarantees that extend beyond the samples used for training. We empirically validate our theory across a variety of everywhere learning tasks, showing that the resulting constrained problems can be solved efficiently and that the learned dual variables provide meaningful representations of sample-level sensitivity.

Ignacio Boero, Jonathan Nixon, Alejandro Ribeiro

University of Pennsylvania

Constrained OptimizationSensitivity Analysis
AskPDF
Sep 28, 2026

Learned Preconditioning for a Primal-Dual Interior-Point Method

Interior-point methods (IPMs) are among the most widely used algorithms for constrained optimization, yet their Newton-based search directions require costly second-order information and large linear-system solves. Learning to optimize offers cheaper updates learned from data, but the singular behavior of logarithmic barriers near constraint boundaries makes IPMs highly sensitive to perturbations, complicating both warm starting and learning reliable updates. We introduce pdLIP, an IPM for smooth nonlinear programs that integrates learned preconditioning with pdProj, an all-shifted primal-dual projected-search IPM. A shared coordinate-wise recurrent network predicts a positive diagonal preconditioner that scales the right-hand side of the reduced Newton system for the primal step, and the remaining slack and multiplier directions are recovered analytically. The learned iterations avoid Hessian evaluations and Newton-system solves, using only first-order and coordinate-wise operations amenable to GPU parallelization. Training is self-supervised, with a loss based on a penalty-barrier merit function and the residual of perturbed optimality conditions, requiring neither target directions nor precomputed solutions. Primal and dual shifts mitigate the barrier's sensitivity to perturbations near constraint boundaries, enabling effective warm starting. Across four classes of 200-dimensional convex and nonconvex constrained problems, pdLIP warm starts reduce pdProj refinement iterations by 63-67% compared with cold starts at the same KKT residual tolerance of 10−810^{-8}, with negligible warm-start generation cost relative to the subsequent pdProj solve. Improvements persist on box-constrained QPs with 1000 variables and extend to applications including portfolio optimization, support vector machines, and a nonlinear control example.

Abhinav Madabhushi, Jialin Liu, Minxin Zhang

Department of Mathematics, University of California, Los Angeles · School of Data, Mathematical, and Statistical Sciences, University of Central Florida

Primal-Dual OptimizationLearning to OptimizeConstrained Optimization
AskPDF
Sep 28, 2026

Riemannian Difference-of-Convex Optimization for K-Means Clustering

K-means is a widely adopted clustering approach in signal processing and machine learning. In this paper, we study K-means clustering through a cardinality-constrained formulation on a compact embedded submanifold. We replace the cardinality constraint with a difference-of-convex (DC) penalty and establish a global error bound to prove that the penalized and constrained formulations share the same global minimizers whenever the penalty parameter exceeds a finite threshold. To solve the resulting nonsmooth Riemannian DC problem, we reformulate it as a minimax problem and propose RADA-DC, a Riemannian alternating descent ascent method combining dual regularization with DC linearization. Under standard assumptions and suitable parameter choices, RADA-DC finds an εε-Riemannian critical point within O(ε−3)O(ε^{-3}) iterations. We conduct experiments on synthetic and real-world datasets to demonstrate that the proposed method outperforms the tested baselines, including K-means++, in solution quality at competitive computational cost when the number of clusters is large.

Meng Xu, Bo Jiang, Hanfu Zhang +2

AMSS, Chinese Academy of Sciences, and University of Chinese Academy of Sciences, Beijing, China · Ministry of Education Key Laboratory of NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing, China · Ministry of Education Key Laboratory of Mathematics and Information Networks, School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing, China +1

Riemannian OptimizationClusteringConstrained Optimization
AskPDF
Sep 27, 2026

dOPT: Differentiating Conic Optimization via Geometric Reduction

Optimization layers enable the incorporation of structured constraints and decision problems into learning systems. Training such systems requires differentiating through the embedded optimization problem, which can be challenging for general conic programs. We introduce dOPT, a solver-agnostic framework that, rather than differentiating the full conic formulation, reduces it at a computed primal-dual solution to an equality-constrained quadratic program that preserves the reference solution and its first-order sensitivity. The reduction captures the local first- and second-order conic geometry relevant to differentiation and remains well defined at singular configurations. Computing solution derivatives then requires a single symmetric linear solve, independently of the forward solver. We derive explicit reductions for convex NLPs, QPs, SOCPs, and SDPs. Numerical experiments validate the computed gradients and show favorable backward-pass scalability, with substantial speedups over existing differentiable conic optimization methods as problem size increases.

Fengyu Yang, Connor W. Magoon, Tyler Watts +1

Department of Mathematics University of North Carolina at Chapel Hill

Implicit DifferentiationDifferentiable ProgrammingConstrained OptimizationDifferentiable Optimization
AskPDF
Sep 27, 2026

The cost of useful natural gradient updates

What information is needed to turn a natural-gradient direction into a useful finite update? Under a population Kullback-Leibler (KL) budget, we call a step useful if it is feasible and loses at most a fraction ε\varepsilon of the best feasible gain along the direction. We construct a four-state exponential family whose laws share their initial gradient, scalar Fisher information and natural gradient, yet two laws have disjoint useful-step sets. With these quantities supplied exactly and the law otherwise known only through draws, the family's worst-case sample complexity is Θ(log⁡(1/δ)/(pε2))Θ(\log(1/δ)/(p\varepsilon^2)) for small ε\varepsilon, where pp scales rare-state probabilities and δδ is the failure probability. The budget is fixed and the optimal gain stays bounded away from zero, so the step length, not the direction, carries this cost. For succinctly described event-tilt models, returning a useful step is NP-hard even with the exact natural gradient and efficient exact sampling. Recovering the unit natural gradient to constant error is also NP-hard even in a two-parameter logistic family with Fisher condition number at most 3. We also give matching sample bounds for event tilts, sample bounds for damped Fisher solves and a population-KL certificate for affine classifiers. In frozen-feature classifier heads, stopping at a sampled KL boundary succeeds in about half of the trials, and a 10% KL margin raises joint success above 93% at a KL budget of 0.01. Thus, knowing where to move is not enough: how far to move can carry an update's entire cost.

Subhransu S. Bhattacharjee, Dylan Campbell, Rahul Shome

School of Computing, The Australian National University

Sample ComplexityNatural Gradient MethodsConstrained Optimization
AskPDF
Sep 27, 2026

Local LMO is Secretly a Projection Method!

The local linear minimization oracle (Ferris and Zavriev, 1996; arXiv:2605.08850), or Local LMO, solves constrained convex problems without having to compute a projection: it minimizes a linear model over the intersection of the feasible set with a ball around the current iterate. We show that, whenever the ball radius does not exceed the Polyak radius, the Local LMO step is the Euclidean projection of the current iterate onto the intersection of the feasible set with a half-space that separates the iterate from the solution set; this projection is nonetheless computable by a linear oracle alone. We demonstrate that Local LMO belongs to a broader family of projection methods which may be indexed by the depth of the localizing half-space. For objectives with ϑ\vartheta-Hölder continuous gradient, every method from this family whose half-space lies sufficiently deep drives the best of its first KK iterates to optimality at the universal rate O(K−(1+ϑ)/2)\mathcal{O}(K^{-(1+\vartheta)/2}), matching the non-accelerated universal gradient method of Nesterov (2015). Run at the Polyak radius, Local LMO attains the same rate when the constrained optima are also unconstrained (∥∇f(x⋆)∥=0\|\nabla f(x_\star)\| = 0), and the rate O(K−1/(2−ϑ))\mathcal{O}(K^{-1/(2-\vartheta)}) otherwise.

Peter Richtárik, Ammar Mahran

King Abdullah University of Science and Technology, Thuwal, Saudi Arabia

LMO MethodsConstrained Optimization
AskPDF
Sep 27, 2026

Identifying the Predictable Drift of a Semimartingale from Marginal Laws

A special semimartingale admits a unique decomposition X=X0+M+AX=X_0+M+A into a local martingale MM and a predictable finite-variation part AA. We consider the identification of AA when XX is observed only through repeated cross-sections. The estimand is then the projection of the sampled predictable compensator onto the observable feature filtration, namely the current state together with whatever randomness is shared across the population, so that at a fixed diffusion coefficient the marginal flow identifies the drift only up to a Markovian projection. If the drift is an affine functional of an observed lag window, the joint problem is a convex quadratic programme whose solution is the pseudo-panel regression of econometrics. Our principal concern is the case, which we believe not to have been treated before, in which the drift is the output of a hidden linear dynamical system whose dynamics are themselves to be identified from the marginals. The joint problem is then a bilinear quadratically constrained programme, which we solve to certified global optimality by spatial branch and bound; with unpenalised state disturbances and a drift basis growing with the grid it is NP-hard already in latent dimension one, by reduction from ℓ1\ell^1 rank-one matrix approximation, whereas the complexity of the deterministic system at fixed latent dimension remains open. A block-coordinate decomposition offers a cheaper alternative. For the estimator itself, we obtain rates at a fixed mesh, separated into Monte-Carlo, estimation and grid contributions.

Jakub Marecek, Enrico Biffis, Abigail Langbridge +1

Department of Computer Science, Czech Technical University in Prague, Czechia · Department of Finance, Imperial College London, UK · Dyson School of Design Engineering, Imperial College London, UK

Latent Dynamics ModelingConstrained OptimizationState Space Models
AskPDF
Sep 26, 2026

Decentralized Optimization with Cross-Coupled Mixed Affine Constraints

We study decentralized optimization with cross-coupled mixed affine constraints, where local and shared variables interact through two affine channels. We show that the intrinsic difficulty of combining separately well-conditioned channels is governed by their Friedrichs angle. This geometry induces a cross-coupling factor that cannot be removed by channelwise preconditioning and governs the additional affine-oracle and communication complexity. We develop an accelerated decentralized method with matching minimax guarantees in the smooth strongly convex regime and extend the framework to smooth and nonsmooth convex objectives. Experiments confirm the predicted dependence on cross-channel geometry and network conditioning.

Ewsey Obzherin, Ilya Khomchenko, Natalia Shelegeda +4

Moscow Independent Research Institute of Artificial Intelligence · FusionBrain Lab · Innopolis University

Decentralized OptimizationConstrained Optimization
AskPDF
Sep 26, 2026

PolyStepOR: Learning to Decide Without Optimal Decisions

Decision-focused learning (DFL) trains predictors for downstream decision quality, but often relies on optimal reference decisions that are expensive to obtain. We present PolyStepOR, which trains directly from realized decision costs without pre-computed optima and extends to in-constraint predictions through repair or infeasibility penalties. To handle piecewise-constant losses, PolyStepOR perturbs predictor parameters, evaluates the resulting decisions, and uses optimal transport to favor lower-cost directions, requiring no derivatives. Without task-specific tuning, PolyStepOR performs strongly on classical optimization benchmarks and competitively on predicted-constraint and real-world problems. Theoretically, we characterize decision-preserving perturbations and boundary detection, bound sensitivity to cost errors, and establish stationarity guarantees for a smoothed objective. PolyStepOR thus replaces optimal reference decisions and derivatives with forward evaluations.

Viet The Nguyen, Gunther Gust, An Thai Le

University of Würzburg, Germany · Center for Artificial Intelligence and Data Science (CAIDAS), Germany · Center for AI Research, VinUniversity, Vietnam +1

Decision-Focused LearningPredict-Then-OptimizeZeroth-Order OptimizationConstrained Optimization
AskPDF
Sep 25, 2026

Game-Theoretic Control with Constrained Potential Surgery

Constrained general-sum dynamic games are a popular formulation for highly interactive multi-agent planning problems. In recent years, Generalized Nash Equilibrium (GNE) solvers have achieved real-time performance for small dynamic games. However, solution speed still remains a bottleneck, and controlling even a small number of agents (e.g., more than four) in a dynamic task remains elusive. In addition, Newton solvers that focus on the first-order conditions are vulnerable to non-Nash saddle points, limiting the usefulness of the provided solution. In this work, we propose a fast and versatile interior point solver for constrained dynamic games, along with a computationally efficient second-order correction that increases the probability of converging to a local GNE solution in constrained dynamic games. The performance of the proposed method is evaluated on numerical benchmarks and a physical experiment involving scaled race cars.

Zhiyuan Zhang, Panagiotis Tsiotras

School of Aerospace Engineering, Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332, USA

Nash Equilibrium ComputationGame TheoryMulti-Agent ControlConstrained Optimization
AskPDF
Sep 24, 2026

LensDesigner: A Self-Improving Agent for Optical Lens Design

Optical lens design is a complex, non-convex optimization challenge that relies heavily on human experience and intuition. Existing optimized-based automatic lens design methods struggle to navigate this vast parameter space without meticulous manual tuning. In this paper, we present LensDesigner, an autonomous agent framework that mirrors the problem-solving workflow of expert opticians. To overcome the initial cold start problem, we construct LensLib100K, an extensive optical lens library, and employ Optics-Aware Retrieval to supply physically valid structural seeds. Within an interactive physical simulation environment, the agent executes macroscopic orchestration while receiving immediate optical feedback. Furthermore, we introduce a continuous self-evolving mechanism guided by a curriculum agent. By iteratively solving design tasks with progressively increasing difficulty, the agent autonomously extracts, accumulates, and reuses design heuristics, effectively evolving its optical lens design expertise over time. At the evaluation level, we introduce LensArena, a standardized evaluation benchmark comprising 120120 diverse optical design tasks, covering extreme configurations. Extensive experiments on this benchmark demonstrate that LensDesigner significantly outperforms publicly available baseline algorithms, achieving superior success rates and optimization efficiency. We hope this work sheds light on the emerging field of intelligent optics. The code will be publicly available.

Lei Sun, Haoran Liang, Dannong Xu +6

INSAIT, Sofia University “St. Kliment Ohridski” · Zhejiang University

Self-Improving AgentsAutomated Heuristic DesignConstrained Optimization
AskPDF
Sep 24, 2026

A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model

We prove nearly quadratic lower bounds for randomized algorithms for linear optimization and uniform sampling over convex bodies in the membership oracle model. For linear optimization, this matches the known nearly quadratic upper bound up to a polylog factor in the dimension. For uniform sampling, this improves on the previous linear lower bound. Our construction also implies the same lower bound for volume estimation.

Santosh S. Vempala

Georgia Tech

Oracle ComplexityConstrained Optimization
AskPDF
Sep 24, 2026

What, When, and How: Audio Description as Constrained Global Optimization

Audio Description (AD) makes movies accessible to blind and visually impaired audiences by narrating visual information in gaps between dialogue. Existing automatic AD systems largely treat generation as a local video-to-text problem, assuming that the content to describe and its temporal location are already provided. Realistic AD instead requires coupled decisions about what visual information is narratively important, when it can be spoken without interfering with dialogue, and how it should be formulated to fit within the available time. We formalize AD generation as a constrained optimization problem over these three decisions. Our hybrid system uses large language models to propose and ground visual elements, estimate their salience to the narrative, and generate compressed realizations. A mixed-integer linear program then jointly selects and schedules descriptions across a scene subject to temporal constraints. When evaluated on REFRAMED, a benchmark for realistic AD of movies, our approach makes better decisions than prompted LLMs about what to describe and when to describe it, establishing a new SOTA on narrative QA and temporally grounded metrics. Ablations show that explicit temporal constraints drive gains in placement, while salience estimation controls how much narratively useful content is retained. Improvements are concentrated on temporal and narrative measures rather than n-gram overlap, although a significant gap to professional describers remains.

Igor Sterner, Mirella Lapata, Alex Lascarides +1

School of Informatics University of Edinburgh United Kingdom

Audio Description GenerationConstrained Optimization
AskPDF
Sep 24, 2026

AT-SKM-Net: An Accelerated Trainable Sampling Kaczmarz-Motzkin Framework for Linear Hard-Constraint Feasibility on Dynamic Graphs

Graph-structured optimization with linear constraints is fundamental to critical infrastructure but faces scalability limits due to massive strict hard constraints and high dimensionality. While recent projection-based methods such as Trainable Sampling Kaczmarz-Motzkin Net (T-SKM-Net) guarantee feasibility, they face high computational costs in dynamic environments by processing the entire constraint set and requiring expensive matrix factorizations. To bridge this gap, we propose the Accelerated Trainable-SKM (AT-SKM) Net framework. To concentrate computation on the active constraints and eliminate redundant calculations, we introduce a hybrid sampling strategy guided by a topology-aware heterogeneous GNN model. To efficiently handle topological shifts in graph-based constraints, we employ a Cholesky Update mechanism that theoretically reduces the equality projection complexity from O(N^3) to O(N^2) under low-rank perturbations. Experiments on random geometric graphs, N-1 Security-Constrained DC-OPF, and minimum-cost gas transport problem demonstrate that AT-SKM reduces iteration counts by up to 85% and achieves 2.95x-7.29x SKM layer speedups, while maintaining zero constraint violations.

Xiaochen Zhang, Haoyu Zhu, Yao Zhang +1

Zhejiang University

Constrained Optimization
AskPDF
Sep 23, 2026

Amplify: A Lightweight Library for Reproducible Nonlinear Programming Problems in Robotics

Optimization problems (OPs) are key to solving many challenging research problems in robotics. However, reproducibility still remains a major issue. In this paper, we present Amplify, a lightweight nonlinear programming library aimed at reproducible results of robotic-related trajectory optimization problems. The minimalistic requirements for the 537-line library (80 characters per line) are an Internet connection, familiarity with the AMPL modeling language, and a text editor. Our primary contribution is the formulation of a library where trajectory optimization algorithms are represented directly within the optimization model. Specifically, we implement the algorithms used to compute the dynamics, trajectories, and reference motions as constraints of the OP in a declarative programming paradigm. We outline how our formulation of objectives, decisions variables, and constraints can be implemented in other transcription libraries that want to be lightweight and reproducible. We also compare the Amplify framework with 3 other libraries across examples of benchmark optimization problems across several fields, including bipedal locomotion and grasp planning.

Nelson Rosa

Robotic OptimizationTrajectory OptimizationScientific ReproducibilityConstrained Optimization
AskPDF
Sep 22, 2026

Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfe

Self-supervised learning for combinatorial optimization has emerged as a promising paradigm for solving discrete optimization problems with neural networks, but a central challenge remains: handling hard combinatorial constraints within continuous, gradient-based training. Continuously extending combinatorial objectives to convex domains is a powerful technique, yet existing approaches often require projection steps that constrain neural network outputs to lie inside the feasible polytope and rely on ad-hoc and problem-specific constructions. We propose a general framework in which the neural network is allowed to predict arbitrary continuous vectors that could potentially lie outside of the feasible polytope. These predictions are then approximated by sparse convex combinations of feasible solutions using a geometric decomposition algorithm based on Frank--Wolfe methods and approximate Caratheodory results. This decomposition induces an a.e.-differentiable, self-supervised loss defined as the expected value of the discrete objective. The same procedure provides an automatic rounding guarantee at inference time. We demonstrate strong empirical performance across multiple combinatorial problems, including the Quadratic Assignment Problem, Maximum Coverage, and the Traveling Salesperson Problem.

Akbar Rafiey, Yifei Xu, Nikolaos Karalias

NYU · MIT

Self-Supervised LearningCombinatorial OptimizationConstrained OptimizationNeural Combinatorial OptimizationFrank-Wolfe Algorithms
AskPDF
Sep 18, 2026

Near-Optimal Acceleration for Smooth ℓp\ell_p / ℓq\ell_q Nondual Convex First-Order Oracle Optimization

We study the optimization of convex objectives with (L,κ−1)(L,κ-1)-Hölder-continuous gradients in ℓq\ell_q over RBpdR B_p^d, 1<κ≤21<κ\le 2. (MG26) provides selectors with a movement bound for the problem of chasing high-dimensional convex nested sets for every p<qp<q and generally reduces Lipschitz convex optimization to bounds on the movement of selectors. We couple that movement with Hölder descent yielding a polynomial-runtime first-order method whose feasible output, in the high-dimensional regime T≤dT\le d and for p<min⁡{q,2}p<\min\{q,2\}, has error O~κ,p,q ⁣(LRκTκ(1+1/p−(1/q−1/2)+)−1),\widetilde O_{κ,p,q}\!\left( \frac{LR^κ}{T^{κ(1+1/p-(1/q-1/2)_+)-1}} \right), after TT queries to a first-order oracle, solving the COLT 2015 open problem of (Guz15), up to logarithmic factors. At (p,q)=(1,2)(p,q)=(1,2), the rate is O~(LRκ/T2κ−1)\widetilde{O}(LR^κ/T^{2κ-1}), including O~(LR2/T3)\widetilde{O}(LR^2/T^{3}) cubic decay in the smooth case.

David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1

IMDEA Software Institute, Madrid, Spain · Purdue University, West Lafayette, IN, USA · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Cat´olica de Chile, Santiago, Chile +1

Accelerated Gradient MethodsConstrained Optimization
AskPDF
Sep 18, 2026

Bilevel Optimization of Topology and Hyperparameters (BOTH)

Topology optimization (TO) represents a significant step towards automating the design process: given a working simulation, TO can produce a viable prototype at the press of a button by differentiating the simulation and iteratively improving the design. In practice, however, TO is riddled with magic numbers''---hyperparameters whose tuning significantly affects the outcome. Finding the right values typically requires not only deep problem-specific knowledge but also extensive trial-and-error. While practitioners can use surrogate-assisted hyperparameter optimization as an alternative, this approach requires strictly limiting the number of hyperparameters through careful problem formulation. Here, we propose differentiating TO itself using automatic differentiation. This yields hypergradients'' that allow us to tune these hyperparameters in tandem with the primary optimization. We show that evaluating just one or two steps of TO is sufficiently informative and that the method scales favorably to thousands of hyperparameters at an expense comparable to only a few standard TO runs. We demonstrate this approach on stress-constrained and compliance problems, with the latter utilizing a neural parameterization of the density field.

Suryanarayanan Manoj Sanu, Miguel Anibal Bessa, Alejandro Marcos Aragón

Faculty of Mechanical Engineering Delft university of technology Delft The Netherlands · School of engineering Brown University Providence United States of America

Hypergradient OptimizationTopology OptimizationHyperparameter OptimizationBilevel OptimizationDifferentiable OptimizationConstrained Optimization
AskPDF
Sep 17, 2026

Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates

We study efficient algorithms for realizing the first-order oracle complexity of optimization of GG-Lipschitz convex functions with respect to the ℓq\ell_{q}-norm over an ℓp\ell_{p}-ball of radius RR, where 1≤p,q≤∞1\leq p,q\leq \infty. For p<qp<q, we obtain error O~p,q(GR/T1/p−(1/q−1/2)+)\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)_{+}}) after TT oracle queries, efficiently realizing the nearly optimal rates of (MBG+26), thereby resolving the nonsmooth end of the COLT 2015 open problem (Guz15b). In particular, the rate is O~(GR/T)\widetilde{O}(GR/T) for Euclidean Lipschitzness over an ℓ1\ell_1-ball of radius RR (p=1,q=2p=1,q=2). Our solution consists of reducing convex Lipschitz optimization to the chasing nested convex sets problem in sublevel sets of an evolving bundle (LNN95; BBE+20): at each query we either find a point with low function value or we produce a deep cut in the current sublevel of the bundle, that we chase. The dichotomy between stability of selectors and forced movement by deep cuts bounds the number of iterations of the algorithm near optimally. For nested subsets of RBpdR B_{p}^{d}, we introduce a novel notion of stable center whose movement is bounded by O~p,q(RT1−1/p+(1/q−1/2)+)\widetilde{O}_{p,q}(RT^{1-1/p+(1/q-1/2)_{+}}) in the ℓq\ell_{q}-norm after TT steps, which we show is nearly optimal in high dimensions. A Monte Carlo average of the proposed selector achieves near-optimal rates with high probability and can be implemented in polynomial time for our optimization algorithm in the real-arithmetic model.

David Martínez-Rubio, Cristóbal Guzmán

IMDEA Software Institute, Madrid, Spain · Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, Santiago, Chile

Constrained OptimizationNonsmooth Convex Optimization
AskPDF
Sep 17, 2026

DR-MPC: Fast and Feasible Dynamics-Relaxed Model-Predictive Control for Legged Locomotion

This paper presents dynamics-relaxed model predictive control (DR-MPC), a novel MPC formulation for legged locomotion, and a tailored interior-point method (IPM) solver. The formulation combines online optimization feasibility by construction with a contact-aware input parameterization. DR-MPC moves the dynamics equality and affine input constraints into quadratic penalties and retains only nonempty box constraints. The resulting box-constrained quadratic program (QP) has a block-arrow Hessian that enables the state and affine-output directions to be eliminated through a Schur complement. The solver factors only the reduced control system after swing-force elimination and contact-aligned move blocking. For the evaluated implementations using the same DR-MPC formulation, our method achieves median end-to-end MPC speedups of 16.0×16.0\times over HPIPM and 4.4×4.4\times over OSQP, with comparable locomotion performance in simulation. DR-MPC achieves a median onboard MPC end-to-end time of 4.44.4 ms and is validated on a Unitree Go1 quadruped. Open-source code will be made available after publication.

Run Wang, Alapati Tuerxun, Shuo Liu +4

Department of Automation, Tsinghua University, Beijing, China · Department of Mechanical Engineering, Boston University, Brookline, MA, USA · School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore +1

Model Predictive ControlConstrained OptimizationQuadruped Locomotion
AskPDF