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.

Feb 17, 2026

Towards Efficient Constraint Handling in Neural Solvers for Routing Problems

Neural solvers have achieved impressive progress in addressing simple routing problems, particularly excelling in computational efficiency. However, their advantages under complex constraints remain nascent, for which current constraint-handling schemes via feasibility masking or implicit feasibility awareness can be inefficient or inapplicable for hard constraints. In this paper, we present Construct-and-Refine (CaR), the first general and efficient constraint-handling framework for neural routing solvers based on explicit learning-based feasibility refinement. Unlike prior construction-search hybrids that target reducing optimality gaps through heavy improvements yet still struggle with hard constraints, CaR achieves efficient constraint handling by designing a joint training framework that guides the construction module to generate diverse and high-quality solutions well-suited for a lightweight improvement process, e.g., 10 steps versus 5k steps in prior work. Moreover, CaR presents the first use of construction-improvement-shared representation, enabling potential knowledge sharing across paradigms by unifying the encoder, especially in more complex constrained scenarios. We evaluate CaR on typical hard routing constraints to showcase its broader applicability. Results demonstrate that CaR achieves superior feasibility, solution quality, and efficiency compared to both classical and neural state-of-the-art solvers.

Jieyi Bi, Zhiguang Cao, Jianan Zhou +5

Nanyang Technological University · MIT · Singapore Management University +2

Neural Combinatorial OptimizationConstrained OptimizationVehicle Routing
AskPDF
Feb 17, 2026

ODYN: An All-Shifted Non-Interior-Point Method for Quadratic Programming in Robotics and AI

We introduce ODYN, a novel all-shifted primal-dual non-interior-point quadratic programming (QP) solver designed to efficiently handle challenging dense and sparse QPs. ODYN combines all-shifted nonlinear complementarity problem (NCP) functions with proximal method of multipliers to robustly address ill-conditioned and degenerate problems, without requiring linear independence of the constraints. It exhibits strong warm-start performance and is well suited to both general-purpose optimization, and robotics and AI applications, including model-based control, estimation, and kernel-based learning methods. We provide an open-source implementation and benchmark ODYN on the Maros-Mészáros test set, demonstrating state-of-the-art convergence performance in small-to-high-scale problems. The results highlight ODYN's superior warm-starting capabilities, which are critical in sequential and real-time settings common in robotics and AI. These advantages are further demonstrated by deploying ODYN as the backend of an SQP-based predictive control framework (OdynSQP), as the implicitly differentiable optimization layer for deep learning (ODYNLayer), and the optimizer of a contact-dynamics simulation (ODYNSim).

Jose Rojas, Aristotelis Papatheodorou, Sergi Martinez +3

Robot Motor Intelligence (RoMI) Lab, Heriot-Watt University, U.K. · Oxford Robotics Institute (ORI), University of Oxford, U.K. · Humanoids and Human Centered Mechatronics, Italian Institute of Technology, Italy.

Quadratic ProgrammingConstrained OptimizationPrimal-Dual Optimization
AskPDF
Feb 17, 2026

Spatially-Aware Adaptive Trajectory Optimization with Controller-Guided Feedback for Autonomous Racing

We present a closed-loop framework for autonomous raceline optimization that combines NURBS-based trajectory representation, CMA-ES global trajectory optimization, and controller-guided spatial feedback. Instead of treating tracking errors as transient disturbances, our method exploits them as informative signals of local track characteristics via a Kalman-inspired spatial update. This enables the construction of an adaptive, acceleration-based constraint map that iteratively refines trajectories toward near-optimal performance under spatially varying track and vehicle behavior. In simulation, our approach achieves a 17.38% lap time reduction compared to a controller parametrized with maximum static acceleration. On real hardware, tested with different tire compounds ranging from high to low friction, we obtain a 7.60% lap time improvement without explicitly parametrizing friction. This demonstrates robustness to changing grip conditions in real-world scenarios.

Alexander Wachter, Alexander Willert, Marc-Philip Ecker +1

Automation & Control Institute (ACIN), TU Wien, Vienna, Austria · AIT, Austrian Institute of Technology GmbH, Vienna, Austria

Trajectory OptimizationAutonomous RacingConstrained OptimizationAdaptive Control
AskPDF
Feb 17, 2026

Multi-Objective Coverage via Constraint Active Search

In this paper, we formulate the new multi-objective coverage (MOC) problem where our goal is to identify a small set of representative samples whose predicted outcomes broadly cover the feasible multi-objective space. This problem is of great importance in many critical real-world applications, e.g., drug discovery and materials design, as this representative set can be evaluated much faster than the whole feasible set, thus significantly accelerating the scientific discovery process. Existing works cannot be directly applied as they either focus on sample space coverage or multi-objective optimization that targets the Pareto front. However, chemically diverse samples often yield identical objective profiles, and safety constraints are usually defined on the objectives. To solve this MOC problem, we propose a novel search algorithm, MOC-CAS, which employs an upper confidence bound-based acquisition function to select optimistic samples guided by Gaussian process posterior predictions. For enabling efficient optimization, we develop a smoothed relaxation of the hard feasibility test and derive an approximate optimizer. Compared to the competitive baselines, we show that our MOC-CAS empirically achieves superior performances across large-scale protein-target datasets for SARS-CoV-2 and cancer, each assessed on five objectives derived from SMILES-based features.

Zakaria Shams Siam, Xuefeng Liu, Chong Liu

University at Albany, State University of New York, Albany, United States · University of Chicago, Chicago, United States

Constrained Optimization
AskPDF
Feb 16, 2026

Decision Making under Imperfect Recall: Algorithms and Benchmarks

In game theory, imperfect-recall decision problems model situations in which an agent forgets information it held before. They encompass games such as the ``absentminded driver'' and team games with limited communication. In this paper, we introduce the first benchmark suite for imperfect-recall decision problems. Our benchmarks capture a variety of problem types, including ones concerning privacy in AI systems that elicit sensitive information, and AI safety via testing of agents in simulation. Across 61 problem instances generated using this suite, we evaluate the performance of different algorithms for finding first-order optimal strategies in such problems. In particular, we introduce the family of regret matching (RM) algorithms for nonlinear constrained optimization. This class of parameter-free algorithms has enjoyed tremendous success in solving large two-player zero-sum games, but, surprisingly, they were hitherto relatively unexplored beyond that setting. Our key finding is that RM algorithms consistently outperform commonly employed first-order optimizers such as projected gradient descent, often by orders of magnitude. This establishes, for the first time, the RM family as a formidable approach to large-scale constrained optimization problems.

Emanuel Tewolde, Brian Hu Zhang, Ioannis Anagnostides +2

Computer Science Dept., Carnegie Mellon University, Pittsburgh, USA · Foundations of Cooperative AI Lab (FOCAL) · Strategy Robot, Inc.; Strategic Machine, Inc.; and Optimized Markets, Inc.

Sequential Decision MakingRegret MinimizationConstrained OptimizationImperfect-Information Games
AskPDF
Feb 16, 2026

An Embarrassingly Simple Way to Optimize Orthogonal Matrices at Scale

Orthogonality constraints are ubiquitous in robust and probabilistic machine learning. Unfortunately, current optimizers are computationally expensive and do not scale to problems with hundreds or thousands of constraints. One notable exception is the Landing algorithm (Ablin et al., 2024) which, however comes at the expense of temporarily relaxing orthogonality. In this work, we revisit and improve on the ideas behind Landing, enabling the inclusion of modern adaptive optimizers while ensuring that orthogonal constraints are effectively met. Remarkably, these improvements come at little to no cost, and reduce the number of required hyperparemeters. Our algorithm POGO is fast and GPU-friendly, consisting of only 5 matrix products, and in practice maintains orthogonality at all times. On several challenging benchmarks, POGO greatly outperforms recent optimizers and shows it can optimize problems with thousands of orthogonal matrices in minutes while alternatives would take hours. As such, POGO sets a milestone to finally exploit orthogonality constraints in ML at scale. A PyTorch implementation of POGO is publicly available at https://github.com/adrianjav/pogo.

Adrián Javaloy, Antonio Vergari

Institute for Machine Learning, University of Edinburgh, GB.

Orthogonal OptimizationMatrix OptimizationConstrained OptimizationDeep Learning Optimization
AskPDF
Feb 16, 2026

Truly Adapting to Adversarial Constraints in Constrained MABs

We study the constrained variant of the multi-armed bandit (MAB) problem, in which the learner aims not only at minimizing the total loss incurred during the learning dynamic, but also at controlling the violation of multiple unknown constraints, under both full and bandit feedback. We consider a non-stationary environment that subsumes both stochastic and adversarial models and where, at each round, both losses and constraints are drawn from distributions that may change arbitrarily over time. In such a setting, it is provably not possible to guarantee both sublinear regret and sublinear violation. Accordingly, prior work has mainly focused either on settings with stochastic constraints or on relaxing the benchmark with fully adversarial constraints (e.g., via competitive ratios with respect to the optimum). We provide the first algorithms that achieve optimal rates of regret and positive constraint violation when the constraints are stochastic while the losses may vary arbitrarily, and that simultaneously yield guarantees that degrade smoothly with the degree of adversariality of the constraints. Specifically, under full feedback we propose an algorithm attaining O~(T+C)\widetilde{\mathcal{O}}(\sqrt{T}+C) regret and O~(T+C)\widetilde{\mathcal{O}}(\sqrt{T}+C) {positive} violation, where CC quantifies the amount of non-stationarity in the constraints. We then show how to extend these guarantees when only bandit feedback is available for the losses. Finally, when bandit feedback is available for the constraints, we design an algorithm achieving O~(T+C)\widetilde{\mathcal{O}}(\sqrt{T}+C) {positive} violation and O~(T+CT)\widetilde{\mathcal{O}}(\sqrt{T}+C\sqrt{T}) regret.

Francesco Emanuele Stradi, Kalana Kalupahana, Matteo Castiglioni +2

Politecnico di Milano

Constrained OptimizationAdversarial BanditsRobust Multi-Armed BanditsNon-Stationary BanditsDynamic Regret Minimization
AskPDF
Feb 12, 2026

Learning to Control: The iUzawa-Net for Nonsmooth Optimal Control of Linear PDEs

We propose an optimization-informed deep neural network approach, named iUzawa-Net, aiming for the first solver that enables real-time solutions for a class of nonsmooth optimal control problems of linear partial differential equations (PDEs). The iUzawa-Net unrolls an inexact Uzawa method for saddle point problems, replacing classical preconditioners and PDE solvers with specifically designed learnable neural networks. We prove universal approximation properties and establish the asymptotic ε\varepsilon-optimality for the iUzawa-Net, and validate its promising numerical efficiency through nonsmooth elliptic and parabolic optimal control problems. Our techniques offer a versatile framework for designing and analyzing various optimization-informed deep learning approaches to optimal control and other PDE-constrained optimization problems. The proposed learning-to-control approach synergizes model-based optimization algorithms and data-driven deep learning techniques, inheriting the merits of both methodologies.

Yongcun Song, Xiaoming Yuan, Hangrui Yue +1

Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, 21 Nanyang Link, 637371, Singapore. · Department of Mathematics, The University of Hong Kong, Pok Fu Lam, Hong Kong SAR, China. · School of Mathematical Sciences, Nankai University, Tianjin 300071, China.

Optimal ControlConstrained OptimizationNeural Network OptimizationAlgorithm Unrolling
AskPDF
Jan 31, 2026

Meta-Learning-Assisted Constraint Relaxation for Constrained Black-Box Optimization

Constraint handling is central to constrained black-box optimization (BBO), where objective improvement and feasibility restoration often provide conflicting search signals. Existing εε-relaxation methods are simple and effective, but their relaxation schedules are usually fixed or manually designed for a limited range of problems. To address this limitation, this letter proposes MeCO, a meta-learning-assisted optimizer that learns an adaptive εε-relaxation policy for constrained BBO. MeCO couples a SHADE optimizer with a Double Deep Q-Network controller. At each optimization step, the controller observes compact population and constraint features and selects a scalar action, which is decoded into a relaxation vector for the candidate comparison rule. The policy is trained across constrained BBO instances and then deployed on held-out problems without problem-specific tuning. Experiments on the CEC2017 constrained benchmark, 16 UAV path-planning tasks and eight real-world engineering problems provide evidence that MeCO transfers across held-out benchmark functions, higher dimensions, and an application-domain setting. Ablation and behavior analyses further clarify the roles of constraint-related state features, action scaling, reward shaping, and meta-training.

Sijie Ma, Zeyuan Ma, Yue-Jiao Gong +1

Hong Kong Polytechnic University · South China Normal University · South China University of Technology

Black-Box OptimizationLearning to OptimizeConstrained OptimizationDerivative-Free Optimization
AskPDF
Jan 24, 2026

Unrolled Neural Networks for Constrained Optimization

We develop unrolled neural networks to solve constrained optimization problems, offering accelerated, learnable counterparts to dual ascent (DA) algorithms. Our framework, termed constrained dual unrolling (CDU), comprises two coupled neural networks that jointly approximate the saddle point of the Lagrangian. The primal network emulates an iterative optimizer that finds a stationary point of the Lagrangian for a given dual multiplier, sampled from an unknown distribution. The dual network generates trajectories towards the optimal multipliers across its layers while querying the primal network at each layer. Unlike standard unrolling, which maps the updates of a prescribed iterative solver directly to network layers, CDU preserves the underlying optimization dynamics while learning the update mappings. The desired primal-dual dynamics are therefore induced through constrained learning by enforcing primal-descent and dual-ascent constraints. We formulate training the two networks as a nested optimization problem and propose an alternating procedure that updates the primal and dual networks in turn, mitigating uncertainty in the multiplier distribution required for primal network training. We establish theoretical guarantees on the feasibility and optimality of the coupled networks. We numerically evaluate the framework on quadratic programs (QPs) with linear constraints and power allocation in wireless networks.

Samar Hadou, Alejandro Ribeiro

Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104 USA

Constrained OptimizationLearning to OptimizePrimal-Dual OptimizationNeural Network Optimization
AskPDF
Jan 24, 2026

A Constrained Optimization Perspective of Unrolled Transformers

We introduce a constrained optimization framework for training transformers that behave like optimization descent algorithms. Specifically, we enforce layerwise descent constraints on the objective function and replace standard empirical risk minimization (ERM) with a primal-dual training scheme. This approach yields models whose intermediate representations decrease the loss monotonically in expectation across layers. We apply our method to both unrolled transformer architectures and conventional pretrained transformers on tasks of video denoising and text classification. Across these settings, we observe constrained transformers achieve stronger robustness to perturbations and maintain higher out-of-distribution generalization, while preserving in-distribution performance.

Javier Porras-Valenzuela, Samar Hadou, Alejandro Ribeiro

Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA, United States of America.

Deep Learning OptimizationTransformerOOD GeneralizationConstrained Optimization
AskPDF
Jan 23, 2026

Learning to Optimize by Differentiable Programming

Solving massive-scale optimization problems requires scalable first-order methods with low per-iteration cost. This tutorial highlights a shift in optimization: using differentiable programming not only to execute algorithms but to learn how to design them. Modern frameworks such as PyTorch, TensorFlow, and JAX enable this paradigm through efficient automatic differentiation. Embedding first-order methods within these systems allows end-to-end training that improves convergence and solution quality. Guided by Fenchel-Rockafellar duality, the tutorial demonstrates how duality-informed iterative schemes such as the alternating direction method of multipliers, and the primal-dual hybrid gradient can be learned and adapted through representative case studies.

Liping Tao, Xindi Tong, Chee Wei Tan

Nanyang Technological University, Singapore · Nanyang Technological University, Singapore, Singapore

Primal-Dual OptimizationLearning to OptimizeAlternating Direction Method of MultipliersDifferentiable ProgrammingConstrained OptimizationDifferentiable Optimization
AskPDF
Jan 20, 2026

Refined Gradient-Based Temperature Optimization for the Replica-Exchange Monte-Carlo Method

The replica-exchange Monte-Carlo (RXMC) method is a powerful Markov-chain Monte-Carlo algorithm for sampling from multi-modal distributions, which are challenging for conventional methods. The sampling efficiency of the RXMC method depends highly on the selection of the temperatures, and finding optimal temperatures remains a challenge. In this study, we propose a refined online temperature selection method by extending the gradient-based optimization framework proposed previously. Building upon the existing temperature update approach, we introduce a reparameterization technique to strictly enforce physical constraints, such as the monotonic ordering of inverse temperatures, which were not explicitly addressed in the original formulation. The proposed method defines the variance of acceptance rates between adjacent replicas as a loss function, estimates its gradient using differential information from the sampling process, and optimizes the temperatures via gradient descent. We demonstrate the effectiveness of our method through experiments on benchmark spin systems, including the two-dimensional ferromagnetic Ising model, the two-dimensional ferromagnetic XY model, and the three-dimensional Edwards-Anderson model. Our results show that the method successfully achieves uniform acceptance rates and reduces round-trip times across the temperature space. Furthermore, our proposed method offers a significant advantage over recently proposed policy gradient method that require careful hyperparameter tuning, while simultaneously preventing the constraint violations that destabilize optimization.

Tatsuya Miyata, Shunta Arai, Satoshi Takabe

Institute of Science Tokyo, Ookayama, Tokyo 152-8550, Japan

Parallel TemperingConstrained Optimization
AskPDF
Dec 30, 2025

Decoupling Constraints from Two Directions for Evolutionary Constrained Multi-objective Optimization

Real-world constrained multi-objective optimization problems (CMOPs) commonly involve multiple constraints, and understanding and exploiting their coupling relationships is crucial for efficient optimization. Recent constraint-decoupling methods handle individual constraints separately, but they generally search only in the evolutionary direction to approximate single-constraint Pareto fronts (SCPFs). In this study, we show that part or all of the constrained Pareto front (CPF) may be unrelated to any SCPF and instead be shaped by the boundaries of infeasible regions. We refer to such a portion as the independent CPF (ICPF) and introduce the reverse CPF (RCPF) to characterize its associated informative infeasible boundaries. Based on these observations, we propose a bidirectional constraint-decoupling coevolutionary algorithm named DCF2D. DCF2D dynamically identifies the constraints obstructing the main population and activates constraint-specific auxiliary populations. These populations adaptively search in the evolutionary direction for the corresponding SCPFs or in the reverse evolutionary direction for the corresponding RCPFs. Its three-stage framework integrates unconstrained global exploration, event-driven bidirectional coevolution, and final convergence refinement. Experiments on 87 benchmark instances from seven test suites and 28 real-world engineering CMOPs demonstrate that DCF2D achieves the best overall performance among nine algorithms. Code available at: https://github.com/RuiqingS/DCF2D.

Ruiqing Sun, Dawei Feng, Xing Zhou +6

College of Computer Science and Technology, National University of Defense Technology, Changsha 410000, P.R. China · College of Intelligence Science and Technology, National University of Defense Technology, Changsha, 410000, P.R. China · State Key Laboratory of Complex & Critical Software Environment, College of Information and Communication, National University of Defense Technology, Wuhan 430019, P.R. China +1

Evolutionary OptimizationMulti-Objective Evolutionary OptimizationConstrained OptimizationMulti-Objective Optimization
AskPDF
Dec 24, 2025

Critical Points of Degenerate Metrics on Algebraic Varieties: A Tale of Overparametrization

We study the critical points over an algebraic variety of an optimization problem defined by a quadratic objective that is degenerate. This scenario arises in machine learning when the dataset size is small with respect to the model, and is typically referred to as overparametrization. Our main result relates the degenerate optimization problem to a nondegenerate one via a projection. In the highly-degenerate regime, we find that a central role is played by the ramification locus of the projection. Additionally, we provide tools for counting the number of critical points over projective varieties, and discuss specific cases arising from deep learning. Our work bridges tools from algebraic geometry with ideas from machine learning, and it extends the line of literature around the Euclidean distance degree to the degenerate setting.

Giovanni Luca Marchetti, Erin Connelly, Paul Breiding +1

KTH Royal Institute of Technology & Digital Futures

Constrained OptimizationOverparameterization
AskPDF
Nov 24, 2025

Anytime-Feasible First-Order Optimization via Safe Sequential QCQP

This paper presents the Safe Sequential Quadratically Constrained Quadratic Programming (SS-QCQP) algorithm, a first-order method for smooth inequality-constrained nonconvex optimization that guarantees feasibility at every iteration. The method is derived from a continuous-time dynamical system whose vector field is obtained by solving a convex QCQP that enforces monotonic descent of the objective and forward invariance of the feasible set. The resulting continuous-time dynamics achieve an O(1/t)O(1/t) ergodic convergence rate for the stationarity measure under standard constraint qualification conditions. We then propose a safeguarded Euler discretization with adaptive step-size selection that preserves this convergence rate while maintaining both descent and feasibility in discrete time. To enhance scalability, we develop an active-set variant (SS-QCQP-AS) that selectively enforces constraints near the boundary, substantially reducing computational cost without compromising theoretical guarantees. Numerical experiments on a multi-agent nonlinear optimal control problem demonstrate that SS-QCQP and SS-QCQP-AS maintain feasibility, exhibit the predicted convergence behavior, and deliver solution quality comparable to second-order solvers such as SQP and IPOPT.

Jiarui Wang, Mahyar Fazlyab

Department of Electrical and Computer Engineering, Johns Hopkins University, Baltimore, MD 21218 USA

Constrained OptimizationNonconvex Optimization
AskPDF
Nov 4, 2025

Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity

We develop new accelerated first-order algorithms in the Frank-Wolfe (FW) family for minimizing smooth convex functions over compact convex sets, with a focus on two prominent constraint classes: (1) polytopes and (2) matrix domains given by the spectrahedron and nuclear-norm balls. A key technical ingredient is a complementarity condition that captures solution sparsity---face dimension for polytopes and rank for matrices. We present two algorithms: (1) a purely linear optimization oracle (LOO) method for polytopes that has optimal worst-case first-order (FO) oracle complexity and, aside of a finite burn-in phase and up to a logarithmic factor, has LOO complexity that scales with r/εr/\sqrtε, where εε is the target accuracy and rr is the solution sparsity (independently of the ambient dimension), and (2) a hybrid scheme that combines FW with a sparse projection oracle (e.g., low-rank SVDs for matrix domains with low-rank solutions), which also has optimal FO oracle complexity, and after a finite burn-in phase, only requires O(1/ε)O(1/\sqrtε) sparse projections and LOO calls (independently of both the ambient dimension and the sparsity level of optimal solutions). Our results close a gap on how to accelerate recent advancements in linearly-converging FW algorithms for strongly convex optimization, without paying the price of the dimension.

Dan Garber

Faculty of Data and Decision Sciences Technion - Israel Institute of Technology

Constrained OptimizationFrank-Wolfe AlgorithmsLMO Methods
AskPDF
Nov 3, 2025

Disciplined Biconvex Programming

We introduce disciplined biconvex programming (DBCP), a modeling framework for specifying and solving biconvex optimization problems. Biconvex optimization problems arise in various applications, including machine learning, signal processing, computational science, and control. Solving a biconvex optimization problem in practice usually involves heuristic methods based on alternate convex search (ACS), which iteratively optimizes over one block of variables while keeping the other fixed, so that the resulting subproblems are convex and can be efficiently solved. However, designing and implementing an ACS solver for a specific biconvex optimization problem usually requires significant effort from the user, which can be tedious and error-prone. DBCP extends the principles of disciplined convex programming to biconvex problems, allowing users to specify biconvex optimization problems in a natural way based on a small number of syntax rules. The resulting problem can then be automatically split and transformed into convex subproblems, for which a customized ACS solver is then generated and applied. DBCP allows users to quickly experiment with different biconvex problem formulations, without expertise in convex optimization. We implement DBCP in the open-source Python package dbcp, as an extension to the well known domain specific language CVXPY for convex optimization.

Hao Zhu, Joschka Boedecker

IMBIT//BrainLinks-BrainTools · Department of Computer Science, University of Freiburg

Nonconvex OptimizationConstrained Optimization
AskPDF
Oct 2, 2025

Smooth Quasar-Convex Optimization with Constraints

Quasar-convex functions form a broad nonconvex class with applications to linear dynamical systems, generalized linear models, and Riemannian optimization, among others. Current nearly optimal algorithms work only in affine spaces due to the loss of one degree of freedom when working with general convex constraints. Obtaining an accelerated algorithm that makes nearly optimal O~(1/(γε))\widetilde{O}(1/(γ\sqrt{\varepsilon})) first-order queries to a γγ-quasar convex smooth function with constraints was independently asked as an open problem in Martínez-Rubio (2022); Lezane, Langer, and Koolen (2024). In this work, we solve this question by designing an inexact accelerated proximal point algorithm that we implement using a first-order method achieving the aforementioned rate and, as a consequence, we improve the complexity of the accelerated geodesically Riemannian optimization solution in Martínez-Rubio (2022). We also analyze projected gradient descent and Frank-Wolfe algorithms in this constrained quasar-convex setting. To the best of our knowledge, our work provides the first analyses of first-order methods for quasar-convex smooth functions with general convex constraints.

David Martínez-Rubio

IMDEA Software Institute · Madrid, Spain

Riemannian OptimizationNonconvex OptimizationConstrained Optimization
AskPDF
Sep 28, 2025

MAD-PINN: A Decentralized Physics-Informed Machine Learning Framework for Safe and Optimal Multi-Agent Control

Co-optimizing safety and performance in large-scale multi-agent systems remains a fundamental challenge. Existing approaches based on multi-agent reinforcement learning (MARL), safety filtering, or Model Predictive Control (MPC) either lack strict safety guarantees, suffer from conservatism, or fail to scale effectively. We propose MAD-PINN, a decentralized physics-informed machine learning framework for solving the multi-agent state-constrained optimal control problem (MASC-OCP). Our method leverages an epigraph-based reformulation of SC-OCP to simultaneously capture performance and safety, and approximates its solution via a physics-informed neural network. Scalability is achieved by training the SC-OCP value function on reduced-agent systems and deploying them in a decentralized fashion, where each agent relies only on local observations of its neighbours for decision-making. To further enhance safety and efficiency, we introduce an Hamilton-Jacobi (HJ) reachability-based neighbour selection strategy to prioritize safety-critical interactions, and a receding-horizon policy execution scheme that adapts to dynamic interactions while reducing computational burden. Experiments on multi-agent navigation tasks demonstrate that MAD-PINN achieves superior safety-performance trade-offs, maintains scalability as the number of agents grows, and consistently outperforms state-of-the-art baselines.

Manan Tayal, Aditya Singh, Shishir Kolathaya +1

Center for Cyber-Physical Systems, Indian Institute of Science, Bangalore, India · Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, USA · Department of Aeronautics and Astronautics, Stanford University, USA

Multi-Agent ControlConstrained OptimizationPhysics-Informed ML
AskPDF
Sep 24, 2025

Beyond Slater's Condition in Online CMDPs with Stochastic and Adversarial Constraints

We study online episodic Constrained Markov Decision Processes (CMDPs) under both stochastic and adversarial constraints. We provide a novel algorithm whose guarantees greatly improve those of the state-of-the-art best-of-both-worlds algorithm introduced by Stradi et al. (2025). In the stochastic regime, i.e., when the constraints are sampled from fixed but unknown distributions, our method achieves O~(T)\widetilde{\mathcal{O}}(\sqrt{T}) regret and constraint violation without relying on Slater's condition, thereby handling settings where no strictly feasible solution exists. Moreover, we provide guarantees on the stronger notion of positive constraint violation, which does not allow to recover from large violation in the early episodes by playing strictly safe policies. In the adversarial regime, i.e., when the constraints may change arbitrarily between episodes, our algorithm ensures sublinear constraint violation without Slater's condition, and achieves sublinear αα-regret with respect to the unconstrained optimum, where αα is a suitably defined multiplicative approximation factor. We further validate our results through synthetic experiments, showing the practical effectiveness of our algorithm.

Francesco Emanuele Stradi, Eleonora Fidelia Chiefari, Matteo Castiglioni +2

Politecnico di Milano

Markov Decision ProcessesConstrained RLConstrained Optimization
AskPDF
Aug 30, 2025

Solving Conic Programs over Sparse Graphs using a Variational Quantum Approach: The Case of the AC Optimal Power Flow

Conic programs arising in physics, quantum information, machine learning, and engineering are often defined over sparse graphs. Although such problems can be solved in polynomial time using classical interior-point solvers, the computational complexity scales unfavorably with graph size. We propose a variational quantum paradigm for solving conic programs, including quadratically constrained quadratic programs and semidefinite programs. We encode primal variables via the state of a parameterized quantum circuit (PQC) and dual variables via the probability mass function associated with a second PQC. The Lagrangian function can thus be expressed as scaled expectations of quantum observables. We pursue approximately stationary points of the Lagrangian by minimizing/maximizing the Lagrangian over the parameters of the first/second PQC. This is accomplished in a hybrid fashion: gradients are estimated using the two PQCs, while their parameters are updated classically using a primal-dual method. We propose permuting primal variables so that related observables have a banded form, enabling efficient measurement. We provide a complexity analysis that is useful to determine which problem types may enjoy quantum advantage. The framework is applied to the AC OPF problem, a large-scale optimization problem central to electric power system operation. Numerical tests on the IEEE 57-node system using PennyLane's simulator show that the proposed doubly variational quantum framework can find high-quality OPF solutions. While this demonstration does not yield a quantum speedup, the results serve as a proof-of-concept and highlight challenges toward practical quantum advantage. Although showcased for OPF, the framework has broader scope, including conic programs with many variables and constraints, problems defined over sparse graphs, and training quantum machine learning models to satisfy constraints.

Thinh Viet Le, Mark M. Wilde, Vassilis Kekatos

Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, Indiana 47906, USA · School of Electrical and Computer Engineering, Cornell University, Ithaca, New York 14853, USA

Optimal Power FlowConstrained OptimizationVariational Quantum Algorithms
AskPDF
Jul 13, 2025

Efficiency, Feasibility, and Incentive-Awareness in Constrained Online Resource Allocation

We study the dynamic allocation of indivisible resources to strategic agents under long-term constraints, where the planner aims to maximize social welfare, satisfy multiple constraints, and elicit near-truthful reports. We find standard primal-dual methods fragile in this setting: agents easily manipulate their reports to distort dual variables, sacrificing social efficiency for individual utility. To address this, we propose the Incentive-Aware Primal-Dual (IAPD) framework. On the primal side, we integrate three components to suppress manipulation: a VCG-based payment neutralizes immediate misreporting benefits, while epoch-based lazy updates and random exploration together ensure potential future gains are outweighed by immediate penalties. On the dual side, to overcome a learning barrier due to lazy updates -- which we call the "price of incentives" -- we design a novel optimistic online learning algorithm, O-FTRL-FP. It utilizes a fixed-point oracle to resolve the circular dependency between optimistic dual variables and the resulting allocations. Ultimately, our mechanism attains O~(T)\tilde{\mathcal O}(\sqrt T) social welfare regret, satisfies all long-term constraints, and induces a near-truthful equilibrium. It also smoothly generalizes to multi-unit multi-demand allocation problems. Notably, this O~(T)\tilde{\mathcal O}(\sqrt T) regret near-matches the non-strategic Ω(T)Ω(\sqrt T) lower bound, demonstrating that incentive-awareness can be accommodated at nearly no cost.

Yan Dai, Negin Golrezaei, Patrick Jaillet

Operations Research Center, MIT. · Sloan School of Management, MIT. · Department of EECS, MIT.

Game TheoryOnline Convex OptimizationMechanism DesignPrimal-Dual OptimizationOnline Resource AllocationConstrained Optimization+1
AskPDF
May 28, 2025

Private Rate-Constrained Optimization with Applications to Fair Learning

Many problems in trustworthy ML can be expressed as constraints on prediction rates across subpopulations, including group fairness constraints (demographic parity, equalized odds, etc.). In this work, we study such constrained minimization problems under differential privacy (DP). Standard DP optimization techniques like DP-SGD rely on objectives that decompose over individual examples, enabling per-example gradient clipping and noise addition. Rate constraints, however, depend on aggregate statistics across groups, creating inter-sample dependencies that violate this decomposability. To address this, we develop RaCO-DP, a DP variant of Stochastic Gradient Descent-Ascent (SGDA) that solves the Lagrangian formulation of rate constraint problems. Through careful design, the extra privacy cost incurred by incorporating these constraints in our approach is limited to that of privately estimating a histogram over each mini-batch at every step. We prove the convergence of our algorithm through a novel analysis of SGDA that leverages the linear structure of the dual parameter. Empirical results show that our method Pareto-dominates existing private learning approaches under group fairness constraints and also achieves strong privacy-utility-fairness performance on neural networks.

Mohammad Yaghini, Tudor Cebere, Michael Menart +2

University of Toronto · Vector Institute · PreMeDICaL team +3

Primal-Dual OptimizationGroup FairnessPrivacy-Preserving MLDifferential PrivacyConstrained OptimizationStochastic Gradient Descent
AskPDF
May 5, 2025

Plan-Driven Adaptive Bidding for First-Price Auctions with Budget Constraints under Nonstationarity

We study budget pacing in repeated first-price auctions when an advertiser's private-value distributions change over time and the stationary competing-bid distribution is unknown. We ask how a feasible expenditure plan should enter online bid shading, learning, and hard budget control. We establish a plan-to-performance decomposition for a plan-driven projected-dual policy. The policy uses any feasible expenditure plan as a soft target, learns an unknown stationary competing-bid CDF from thresholds revealed after each auction, and enforces the campaign budget on every sample path. Against a distribution-informed expected-budget fluid benchmark, the uniform-plan reward gap is O(T)+O(WT)O(\sqrt T)+O(\mathcal W_T), where WT\mathcal W_T measures heterogeneity in private-value distributions. With a supplied feasible plan, the global gap decomposes into a one-sided O(T)O(\sqrt{T}) fixed-plan execution term and a plan-mismatch term bounded by (b/2a)PlanError(b/2a)PlanError. The same analysis provides guarantees for strict and relaxed period-cap comparators, exact recovery of the global benchmark under a specific allowance vector, and separate lower bounds establishing the necessity of the temporal-heterogeneity and Plan Error terms. An upstream planner can translate forecasts or managerial priorities into a feasible spending trajectory, while the online controller adapts bids using realized thresholds and expenditures. The guarantee is modular: it evaluates the final normalized or projected plan through PlanErrorPlanError. A specific forecasting model can be linked to the guarantee by establishing how its primitive estimation errors propagate to this plan-quality metric.

Yige Wang, Jiashuo Jiang

Department of Industrial Engineering & Decision Analytics, Hong Kong University of Science and Technology

Primal-Dual OptimizationAutomated BiddingOnline AdvertisingConstrained OptimizationOnline LearningDecision-Making under Uncertainty
AskPDF
May 4, 2025

Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles

This paper explores the performance of a random Gaussian smoothing zeroth-order (ZO) scheme for minimising quasar-convex (QC) and strongly quasar-convex (SQC) functions in both unconstrained and constrained settings. For the unconstrained problem, we establish the ZO algorithm's convergence to a global minimum along with its complexity when applied to both QC and SQC functions. For the constrained problem, we introduce the new notion of proximal-quasar-convexity and prove analogous results to the unconstrained case. Specifically, we derive complexity bounds and prove convergence of the algorithm to a neighbourhood of a global minimum whose size can be controlled under a variance reduction scheme. Beyond the theoretical guarantees, we demonstrate the practical implications of our results on several machine learning problems where quasar-convexity naturally arises, including linear dynamical system identification and generalised linear models.

Amir Ali Farzin, Yuen-Man Pun, Philipp Braun +1

School of Engineering Australian National University · Department of Electrical and Electronic Engineering University of Melbourne · Department of Electrical and Electronic Engineering22 University of Melbourne

Zeroth-Order OptimizationConstrained Optimization
AskPDF
Apr 13, 2025

Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization

In this paper, we study nonconvex constrained stochastic zeroth-order optimization problems with exact constraints and stochastic objective evaluations. To solve this class of problems, we propose a framework of mirror descent linearized augmented Lagrangian methods that employs two-point stochastic zeroth-order gradient estimators and exploits non-Euclidean mirror descent geometry. Under mild assumptions, we establish oracle complexity guarantees for finding an εε-KKT point parameterized by p≥2p \geq 2. Under Rademacher smoothing, our analysis reveals a trade-off between the variance of the zeroth-order gradient estimators and the smoothness of the mirror map. In the high-accuracy regime, the resulting effective oracle complexity is O(pd2/pε−3)\mathcal{O}(p d^{2/p}ε^{-3}) for p∈[2,2ln⁡d]p \in [2,2\ln d] and O(ln⁡d ε−3)\mathcal{O}(\ln d\,ε^{-3}) for p>2ln⁡dp > 2\ln d. These bounds reduce the dimension dependence in the leading term. When p=2p=2, our method recovers the Euclidean setting with an oracle complexity of O(dε−3)\mathcal{O}(dε^{-3}), improving the εε-dependence over existing methods. Furthermore, to eliminate initial near-feasibility requirements, we introduce a multi-stage scheme that finds an εε-KKT point within O(1+log⁡log⁡(e/ε))\mathcal{O}(1+\log\log(e/ε)) stages while maintaining the leading-order complexity. Numerical tests on QCQPs, black-box adversarial attacks, and fairness-constrained classification demonstrate the effectiveness of our proposed method.

Qiankun Shi, Han Yuan, Xiao Wang +1

Sun Yat-sen University, Guangzhou, 510006, China · Pengcheng Laboratory, Shenzhen, 518066, China · Sun Yat-sen University, Guangzhou, 518066, China +1

Zeroth-Order OptimizationAugmented Lagrangian MethodMirror DescentConstrained Optimization
AskPDF
Mar 31, 2025

Optimization on the Oblique Manifold for Sparse Simplex Constraints via Multiplicative Updates

Low-rank optimization problems with sparse simplex constraints involve variables that must satisfy nonnegativity, sparsity, and sum-to-1 conditions, making their optimization particularly challenging due to the interplay between low-rank structures and constraints. These problems arise in various applications, including machine learning, signal processing, environmental fields, and computational biology. In this work, we propose a novel manifold optimization approach to efficiently tackle these problems. Our method leverages the geometry of oblique manifolds to reformulate the problem and introduces a new Riemannian optimization method based on Riemannian gradient descent that strictly maintains the simplex constraints. By exploiting the underlying manifold structure, our approach improves optimization efficiency. Experiments on synthetic and real datasets demonstrate the effectiveness of the proposed method compared to standard Euclidean and Riemannian methods, paving the way for broader applications.

Flavia Esposito, Andersen Ang

Department of Mathematics, University of Bari Aldo Moro, Bari, 70125, Italy. · School of Electronics and Computer Science, University of Southampton, Southampton, SO17 1BJ, United Kingdom.

Riemannian OptimizationConstrained Optimization
AskPDF
Mar 13, 2025

Exploiting Concavity Information in Gaussian Process Contextual Bandit Optimization

The contextual bandit models sequential decision-making problems in which rewards depend on both the chosen action and observed context. In many domains such as medicine, business, and engineering, prior knowledge provides structural information about the reward function that can be exploited to improve optimization efficiency. This paper studies settings where, for each observable context, the conditional mean reward is known to be concave with respect to the action variable. To leverage this structure, we develop a contextual bandit algorithm that conditions a Bayesian Gaussian Process posterior on concavity constraints. We propose a novel reward model that combines a concavity-preserving regression spline basis with a constrained GP posterior, yielding a tractable shape-constrained estimator. Building on this model, we construct a UCB algorithm and establish new posterior concentration inequalities for the constrained posterior, leading to regret guarantees that are never worse than applying standard GP-UCB without concavity information and can be strictly tighter when concavity is informative. Experiments on benchmark problems and a Warfarin dosing test application demonstrate substantial reductions in cumulative regret relative to state-of-the-art baselines.

Kevin Li, Eric Laber

Contextual BanditsGaussian Process BanditsConstrained Optimization
AskPDF
Jan 30, 2025

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

We introduce a novel framework for decentralized projection-free optimization, extending projection-free methods to a broader class of upper-linearizable functions. Our approach leverages decentralized optimization techniques with the flexibility of upper-linearizable function frameworks, effectively generalizing traditional DR-submodular function optimization. We obtain the regret of O(T1−θ/2)O(T^{1-θ/2}) with communication complexity of O(Tθ)O(T^θ) and number of linear optimization oracle calls of O(T2θ)O(T^{2θ}) for decentralized upper-linearizable function optimization, for any 0≤θ≤10\le θ\le 1. This approach allows for the first results for monotone up-concave optimization with general convex constraints and non-monotone up-concave optimization with general convex constraints. Further, the above results for first order feedback are extended to zeroth order, semi-bandit, and bandit feedback.

Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal

Purdue University, West Lafayette, IN, USA · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada

Submodular OptimizationOnline Convex OptimizationBandit LearningConstrained OptimizationDecentralized Optimization
AskPDF