Primal-Dual Optimization

Follow this topic Ask about this topic

Primal-dual optimization solves constrained problems by improving a candidate solution while adjusting multipliers to reflect constraint violations. Common approaches include primal-dual hybrid gradient, ADMM, interior-point methods, and augmented Lagrangian methods, used in settings from large-scale linear programs to distributed control and online resource allocation. Researchers also learn solver parameters or multiplier-update policies, and apply these methods to constrained generation and machine learning. A central challenge is balancing speed and reliable feasibility when problems are nonconvex, noisy, or poorly conditioned, since many guarantees depend on convexity or regularity assumptions.

Latest papers

53 papers10 papers in the last four weeks, up 100% on the four weeks before. 0.1% of all new papers.

Last-Iterate Convergence for Constrained MDPs: From Dual Descent to Primal-Dual
Oct 29, 2026Michael Lu, Max Qiushi Lin, Mo Chen +1Last-Iterate Convergence Constrained RL
Simon Fraser University · Canada CIFAR AI Chair, Amii, Simon Fraser University
AHEAD: Adaptive Neural Acceleration for Large-Scale Linear Programming
Oct 26, 2026Sihao Liu, Zhichao Hou, Huayue Gu +4Learning to Optimize Linear Programming
North Carolina State University · Kennesaw State University · Nokia Applied Research
Parametric Resonance in Primal-Dual Learning for Slowly Non-Stationary Constrained MDPs
Oct 16, 2026Maxime BaeldeMarkov Decision Processes Primal-Dual Optimization
Antvoice, Paris, France
Imperfect Is Perfect: Learned Column Prefilling for Branch-Price-and-Cut
Oct 14, 2026Haoran Liu, Yu YangLearning to Optimize Mixed-Integer Linear Programming
Department of Industrial Systems Engineering, University of Florida, Florida, United States
A Scalable Learned Iterative Solver for Nonlinear MPC via Temporal Decomposition
Oct 9, 2026Lukas Lüken, Sergio LuciaLearning to Optimize Nonlinear MPC
Chair of Process Automation Systems, TU Dortmund University, Emil-Figge Straße 70, Dortmund, 44227, North Rhine-Westphalia, Germany
Primal-Dual Flow Matching for Sample-Wise Constrained Generation
Oct 8, 2026Zhengyan Huan, Peter Y. Lu, Shuchin AeronConstrained Generative Modeling Constrained Sampling
Department of Electrical and Computer Engineering, Tufts University · NSF AI Institute for Artificial Intelligence and Fundamental Interactions
CERO: Where and When to Allocate Rollouts for RL Post-Training
Oct 7, 2026Yiming Zong, Yige Wang, Xing Hu +2Reinforcement Learning RL Post-Training
Department of Industrial Engineering & Decision Analytics, Hong Kong University of Science and Technology · Innovation and Information Management, The University of Hong Kong · Faculty of Engineering & Faculty of Business and Economics, The University of Hong Kong
Neural Algorithmic Reasoning for Graph Saddle Point Problems
Oct 5, 2026Samantha Chen, Jesse He, Coleman Clougherty +2Primal-Dual Optimization Graph Neural Networks
Oberlin College · Department of Computer Science, Oberlin College · University of California, San Diego +2
From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
Oct 2, 2026Kuangyu Ding, Gesualdo ScutariDecentralized Optimization Primal-Dual Optimization
Edwardson School of Industrial Engineering, Purdue University, West Lafayette, IN. · Edwardson School of Industrial Engineering & Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN.
Reinforcement Learning to Accelerate Primal-Dual Hybrid Gradient for Linear Programming
Oct 1, 2026Jinhwan Sul, Alex Oshin, Evangelos A. TheodorouPrimal-Dual Optimization Reinforcement Learning
Georgia Institute of Technology, USA
Learned Preconditioning for a Primal-Dual Interior-Point Method
Sep 28, 2026Abhinav Madabhushi, Jialin Liu, Minxin ZhangPrimal-Dual Optimization Learning to Optimize
Department of Mathematics, University of California, Los Angeles · School of Data, Mathematical, and Statistical Sciences, University of Central Florida
Predictive Dual Smoothing for Column Generation
Sep 28, 2026Senne Berden, Noah Schutte, Andrea Lodi +1Primal-Dual Optimization Linear Programming
KU Leuven · TU Delft · Cornell Tech
Annealed Sinkhorn with Momentum: Certified Unregularized Optimal Transport in Linear Memory
Sep 27, 2026Samuel J. K. Chin, Maximilian SchifferPrimal-Dual Optimization Optimal Transport
MIT · HEC Paris
Feasible Flow Matching for Graph Reconstruction via Within-Sampling Primal-Dual Guidance
Sep 26, 2026Haoming Chen, Nicolas Zilberstein, Santiago Paternain +1Graph Reconstruction Constrained Generative Modeling
Equilibrium bias and convergence in augmented primal--dual dynamics with sampled constraints
Sep 12, 2026Kang Liu, Mengxiao Chen, Siqi Xiong +1Primal-Dual Optimization Stochastic Optimization Convergence
School of Future Technology, Xi’an Jiaotong University, Xi’an, China · School of Automation Science and Engineering, Xi’an Jiaotong University, Xi’an, China · Department of Rehabilitation Sciences, The Hong Kong Polytechnic University, Hong Kong SAR, China
Dual-guided Hierarchical Edge Localization for Large-scale Optimal Transport Across Dimensions
Sep 11, 2026Wenzhou Xia, Qiaoqiao Ding, Jingwei Liang +1Primal-Dual Optimization Optimal Transport
School of Mathematical Sciences, Shanghai Jiao Tong University, Shanghai 200240, China · Institute of Natural Sciences, Shanghai Jiao Tong University, Shanghai 200240, China
Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus
Sep 7, 2026Shao-An YinPrimal-Dual Optimization Dynamical Systems
independent researcher
Resource-Adaptive Primal-Dual Learning for One-Warehouse Multi-Store Systems with Censored Demand
Aug 14, 2026Jiameng LyuInventory Control Online Resource Allocation
Department of Management Science, School of Management, Fudan University, Shanghai 200433, China
ContactIPM: A Structure-Exploiting Interior-Point Solver for Contact-Implicit Trajectory Optimization
Aug 12, 2026Yucheng ChenPrimal-Dual Optimization Trajectory Optimization
DualCert: A Solver for the Traveling Salesman Problem with Constraint-Coupled Learning
Aug 10, 2026Yancheng Song, Yongzhi Qi, Wei Qi +1Traveling Salesperson Problem Primal-Dual Optimization
Department of Industrial Engineering, Tsinghua University, Beijing 100084, China · JD.com, Beijing, China · College of Engineering, UC Berkeley, Berkeley, CA 94720, USA; Faculty of Engineering, Faculty of Business and Economics, University of Hong Kong, Hong Kong, China
Constrained Learning with Universally Learnable Concept Classes
Aug 9, 2026Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis KalogeriasPrimal-Dual Optimization Reproducing Kernel Hilbert Spaces
1Yale University · 2King’s College London
Non-Asymptotic Variational Learning for Monotone Nonlinear Multiscale Elliptic Equations: Scale-Robust Primal-Dual Bounds and Strong-Form Statistical Ill-Conditioning
Jul 17, 2026Ronald KatendePrimal-Dual Optimization Neural PDE Solvers
Department of Mathematics Kabale University Kikungiri Hill, Katuna Road, Kabale, Uganda
Learned Pairwise Deep Dual-Optimal Inequalities for Stabilizing Column Generation
Jul 15, 2026Zhengzhong Ricky You, Bo Tang, Haoran Liu +1Primal-Dual Optimization Combinatorial Optimization
Department of Civil Engineering, Tsinghua University, Beijing 100084, China · MIT Sloan School of Management, Massachusetts Institute of Technology, 100 Main Street, Cambridge, MA 02142, USA · Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA
Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity
Jul 9, 2026Linglingzhi Zhu, Jiajin LiPrimal-Dual Optimization Nonconvex Optimization
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA. · Sauder School of Business, University of British Columbia, Vancouver, BC, Canada.
Neural Certificate Pricing for Combinatorial Optimization Problems
Jul 1, 2026Jingyi Chen, Xinyuan Zhang, Xinwu QianPrimal-Dual Optimization Unsupervised Learning
Department of Civil and Environmental Engineering, Rice University, Houston, TX
Constrained Online Convex Optimization without Slater's Condition
Jun 30, 2026Kihyun Yu, Junehee Lee, Dabeen LeePrimal-Dual Optimization Online Convex Optimization
1KAIST · 2Seoul National University
AI-Assisted Discovery of Convex Relaxations via Dual Agents
Jun 30, 2026Sungyoon Kim, Mert PilanciPrimal-Dual Optimization Convex Relaxation
Department of Electrical Engineering, Stanford University, CA, USA.
Constrained Diffusion Models with Primal-Dual Inference
Jun 15, 2026Samar Hadou, Yigit Berkay Uslu, Alejandro RibeiroPrimal-Dual Optimization Constrained Generative Modeling
Department of Electrical and Systems Engineering, University of Pennsylvania
Elastic ODYN: Differentiable Optimization for Infeasible Control and Learning in Robotics
Jun 15, 2026Aristotelis Papatheodorou, Jose Rojas, Ioannis Havoutis +1Robotic Control Primal-Dual Optimization
Department of Engineering Science, University of Oxford, Oxford, UK · Robot Motor Intelligence (RoMI) Lab, Heriot-Watt University, Edinburgh, UK
Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometry
Jun 9, 2026Susmit Sarkar, Abhinav Raghuvanshi, Kushal Chakrabarti +1Stochastic Optimization Primal-Dual Optimization
Indian Institute of Technology Bombay, Mumbai, Maharashtra, India · Tata Consultancy Services Research, Thane, Maharashtra, India

Oct 29, 2026J/K move · Enter open · S save

Last-Iterate Convergence for Constrained MDPs: From Dual Descent to Primal-Dual

Michael Lu, Max Qiushi Lin, Mo Chen, Sharan Vaswani

Simon Fraser University · Canada CIFAR AI Chair, Amii, Simon Fraser University

Last-Iterate Convergence Constrained RL Primal-Dual Optimization

Open paper AskPDF arXiv

We study policy optimization for infinite-horizon, discounted constrained Markov decision processes. While primal-dual (

\texttt{PD}

) methods are widely used in practice, their theoretical guarantees typically hold for an impractical mixture policy. In contrast, dual descent (

\texttt{DD}

) methods output a single policy ("last iterate") with guarantees on its performance. However, such methods require iteratively solving entropy-regularized MDPs in an inner-loop, limiting their practical effectiveness. Moreover, existing analyses rely on strong coverage assumptions that are difficult to satisfy in practice. Consequently, we first provide a new analysis of

\texttt{DD}

methods that does not require coverage assumptions. We then employ entropy-regularized natural policy gradient and dual regularization to eliminate the inner loop, resulting in an efficient

\texttt{PD}

algorithm. We develop a novel tracking analysis which shows that, compared to existing methods, the proposed algorithm achieves improved last-iterate convergence guarantees. Furthermore, our theoretical framework allows us to analyze a truncated bilevel method that interpolates between

\texttt{DD}

and

\texttt{PD}

methods. Finally, we generalize our analysis to handle linear function approximation. Compared to prior last-iterate methods, we prove stronger guarantees under less restrictive assumptions.