Showing 1–50 of 117 results for author: Dai, Y

A Multiscale Primal-Dual Interior-Point Relaxation Method for Large-Scale Optimal Transport Problems

Authors: Shengyu Sun, Rui-Jin Zhang, Ruoyu Diao, Yu-Hong Dai

Abstract: Large-scale optimal transport (OT) problems involve a vast number of transport variables, leading to prohibitive memory and computational costs. To address these challenges, we propose a multiscale primal-dual interior-point relaxation method (MSIPRM). The multiscale outer framework constructs a hierarchy of standard OT problems at progressively finer levels. At each level, the OT problem is solve… ▽ More Large-scale optimal transport (OT) problems involve a vast number of transport variables, leading to prohibitive memory and computational costs. To address these challenges, we propose a multiscale primal-dual interior-point relaxation method (MSIPRM). The multiscale outer framework constructs a hierarchy of standard OT problems at progressively finer levels. At each level, the OT problem is solved over a sequence of adaptively refined active sets initialized based on the solution support at the previous level. This yields a sequence of closely related sparse subproblems, thereby substantially reducing memory requirements. The primal-dual interior-point relaxation method (IPRM) serves as the inner solver for each sparse subproblem. Since IPRM does not require strictly interior iterates, it can readily use the solution of the previous subproblem as a warm start. To efficiently obtain the Newton direction, we solve a reduced Schur complement system derived from the normal equations. Furthermore, we develop an effective support-identification strategy based on the approximate solutions obtained by IPRM. We establish condition number estimates for the Schur complement matrices and analyze the global and local convergence properties of the algorithm. Numerical experiments on large-scale test problems demonstrate the computational efficiency and scalability of MSIPRM and show that it compares favorably with existing solvers. In particular, MSIPRM can handle instances whose full formulations contain trillions of transport variables. △ Less

Submitted 12 August, 2026; originally announced August 2026.

Polyhedral Outer-Approximations for MISOCP: Geometry and Cutting Planes

Authors: Yongzheng Dai

Abstract: Mixed-integer second-order cone programs are commonly solved by polyhedral outer approximation (OA), which iteratively strengthens a linear relaxation of the conic feasible region through cutting planes. We study how such approximations can be constructed more efficiently. First, we analyze the marginal contribution of a newly generated cut relative to cuts already present in the relaxation. Using… ▽ More Mixed-integer second-order cone programs are commonly solved by polyhedral outer approximation (OA), which iteratively strengthens a linear relaxation of the conic feasible region through cutting planes. We study how such approximations can be constructed more efficiently. First, we analyze the marginal contribution of a newly generated cut relative to cuts already present in the relaxation. Using violation- and volume-based measures, we show that this contribution decreases at least as fast as linearly as the new supporting direction approaches an existing one. Motivated by this geometric analysis, we develop a cut-generation strategy that balances separation depth with angular novelty and admits closed-form constructions. Second, we introduce a progressive-integrality OA framework that proceeds from an LP relaxation through partially integral relaxations before reaching the full MILP, thereby using inexpensive early iterations to strengthen the approximation before later mixed-integer solves. Computational experiments on CBLIB instances and large-scale AC unit-commitment models demonstrate complementary benefits from the proposed cut strategy and progressive integrality, substantially reducing the computational effort of outer approximation. △ Less

Submitted 10 August, 2026; originally announced August 2026.

A primal--dual interior-point method for nonsymmetric conic optimization with conjugate-free scaling

Authors: Rui-Jin Zhang, Wenhao Fu, Yu-Hong Dai

Abstract: We develop a primal--dual interior-point method for nonsymmetric conic optimization based on a conjugate-free scaling matrix. The scaling is obtained from a single-secant BFGS update of the primal barrier Hessian. In contrast to multi-secant BFGS scalings, it does not require conjugate-barrier derivatives. This feature is important for high-dimensional nonsymmetric cones, where conjugate-barrier d… ▽ More We develop a primal--dual interior-point method for nonsymmetric conic optimization based on a conjugate-free scaling matrix. The scaling is obtained from a single-secant BFGS update of the primal barrier Hessian. In contrast to multi-secant BFGS scalings, it does not require conjugate-barrier derivatives. This feature is important for high-dimensional nonsymmetric cones, where conjugate-barrier derivatives may be unavailable in closed form or expensive to compute. We embed the conjugate-free scaling in a homogeneous self-dual predictor--corrector framework. Using a split central-path neighborhood that separately controls the conic variables and the scalar homogeneous variables, we prove that the scaling matrix remains uniformly comparable to the primal barrier Hessian. This comparison bound is used to prove neighborhood preservation and to show that the complementarity measure and the linear residual decrease at a uniform rate. Consequently, the method attains an iteration bound of $\mathcal{O}(\sqrtν\log(1/\varepsilon))$, improving the $\mathcal{O}(ν\log(1/\varepsilon))$ bound of Badenbroek and Dahl [Optim. Methods Softw., 37 (2022), pp. 1027--1064] and matching the best-known complexity order for interior-point methods. Numerical experiments on instances involving the operator perspective epigraph cone and the quantum relative entropy cone show that the method is competitive with QICS, a specialized solver for conic models arising in quantum information. △ Less

Submitted 10 August, 2026; originally announced August 2026.

Comments: 30 pages, 3 figures

MSC Class: 90C25; 90C51; 90C30

Enhancing Presolve in Mixed Integer Programming by Combining Probing and Dual Fixing

Authors: Zhao-Wei Wang, Wei-Kun Chen, Yu-Hong Dai

Abstract: Probing and dual fixing are two powerful presolve techniques in mixed integer programming (MIP) solvers. Probing tentatively sets some binary variables to 0 or 1, applies linear constraint based domain propagation techniques to derive better variable bounds, and extracts useful information such as stronger variable implications and better global variable bounds. Dual fixing attempts to fix variabl… ▽ More Probing and dual fixing are two powerful presolve techniques in mixed integer programming (MIP) solvers. Probing tentatively sets some binary variables to 0 or 1, applies linear constraint based domain propagation techniques to derive better variable bounds, and extracts useful information such as stronger variable implications and better global variable bounds. Dual fixing attempts to fix variables to lower or upper bounds while ensuring that at least one optimal solution is retained, as long as the problem was feasible. In this paper, we investigate how to combine the two approaches in MIP solvers to achieve a better performance. In particular, we first embed dual fixing into the probing framework, deriving more useful variables' implications for enhancing the capability of probing. Then, we develop an improved dual fixing technique where more variable fixings can be applied, and use the probing framework to detect the reductions. Computational results on the MIPLIB 2017 benchmark instances demonstrate the potential of the two proposed techniques in combining probing and dual fixing on the open-source MIP solver HiGHS. △ Less

Submitted 12 July, 2026; originally announced July 2026.

Comments: 15 pages, accepted for publication in Mathematical Programming Computation

Exploiting Variable Implications in Presolve for Mixed Integer Programming

Authors: Wei-Kun Chen, Chang-Long Li, Zhao-Wei Wang, Yu-Hong Dai, Zi-Shuo Li, Meng Lu

Abstract: Presolve for mixed integer programming (MIP) problems aims to eliminate redundant information, strengthen the formulation, and extract useful structural information for the subsequent branch-and-cut process. An important type of such structural information is the variable implications (VIs), which describe how a bound on a variable depends on a bound of a binary variable. In this paper, we develop… ▽ More Presolve for mixed integer programming (MIP) problems aims to eliminate redundant information, strengthen the formulation, and extract useful structural information for the subsequent branch-and-cut process. An important type of such structural information is the variable implications (VIs), which describe how a bound on a variable depends on a bound of a binary variable. In this paper, we develop two new presolve techniques that exploit VIs to derive reductions for MIP problems. The first technique, called VI aggregation, aggregates multiple VIs into a single inequality by using implications between a variable and a set of binary variables that form a clique. This aggregation can reduce the number of constraints and tighten the linear programming relaxation. The second technique, called VI-aware linear constraint propagation (LCP), builds on the standard LCP but incorporates VIs associated with the variable being tightened to derive more reductions and can derive tighter variable bounds. We show that although VI information is additionally considered, the tightest lower or upper bound of a variable can still be derived in linear time. Moreover, compared with a state-of-the-art approach in the literature, the proposed VI-aware LCP can derive tighter variable bounds. Computational results on MIPLIB 2017 benchmark instances demonstrate the effectiveness of VI aggregation and VI-aware LCP in improving the performance of the open-source MIP solver HiGHS. In particular, using the two proposed presolve techniques, a reduction of 4% in solving time and 6% in node number on HiGHS can be achieved. △ Less

Submitted 5 July, 2026; originally announced July 2026.

Comments: 24 pages, 1 figure, 6 tables

Deep Neural Networks for Doubly Robust Estimation with Nonprobability Survey Samples

Authors: Yufang Dai, Shihua Luo, Wendy Lou, Zilin Wang, Xuewen Lu

Abstract: Integrating probability and nonprobability survey samples is an important problem in modern survey sampling. Nonprobability samples often contain rich outcome information but may lack population representativeness, whereas probability samples provide design-based auxiliary information but may not contain the study variable. We propose a deep neural network (DNN)-assisted doubly robust framework fo… ▽ More Integrating probability and nonprobability survey samples is an important problem in modern survey sampling. Nonprobability samples often contain rich outcome information but may lack population representativeness, whereas probability samples provide design-based auxiliary information but may not contain the study variable. We propose a deep neural network (DNN)-assisted doubly robust framework for estimating the finite population mean from these two data sources. The proposed method models the logit sampling score for the nonprobability sample as an unknown nonparametric function and estimates it by maximizing a pseudo-likelihood that combines information from the nonprobability sample and a reference probability sample. The DNN parameters are optimized using the ADAM algorithm. The resulting DNN-estimated sampling scores are incorporated into a DNN-assisted inverse-probability weighted estimator and a deep doubly robust estimator. We establish consistency and convergence rates under regularity conditions and evaluate the finite-sample performance of the proposed estimators through simulation studies and an empirical application using Pew Research Center and Behavioral Risk Factor Surveillance System data. The results suggest that the proposed estimators can improve robustness to parametric propensity-score misspecification, especially when the true selection mechanism is nonlinear. △ Less

Submitted 27 May, 2026; originally announced May 2026.

Comments: 29 pages, 1 figure

MSC Class: 62D05; 62G05 (Primary) 62J02; 62M45 (Secondary)

A Stochastic Implicit Proximal Point Algorithm for Solving Linearly Constrained Stochastic Minimax Problems

Authors: Kehan Zhu, Jiani Wang, Yu-Hong Dai

Abstract: This paper presents a novel approach to solving large-scale minimax problems with nonsmooth regularizers. We propose a stochastic implicit proximal point algorithm with variance reduction techniques where stochastic oracles are selected in two cases -- with or without replacement. The semismooth Newton methods with Armijo line search is used to solve the implicit proximal point update subproblem i… ▽ More This paper presents a novel approach to solving large-scale minimax problems with nonsmooth regularizers. We propose a stochastic implicit proximal point algorithm with variance reduction techniques where stochastic oracles are selected in two cases -- with or without replacement. The semismooth Newton methods with Armijo line search is used to solve the implicit proximal point update subproblem in each iteration. The algorithm efficiently handles the strongly-convex-strongly-concave objective function with nonsmooth regularizers and coupling linear equations, which is proved to exhibit global q-linear convergence of the iterations to the saddle point and global r-linearly convergence of the multipliers to the multiplier set in expectation. Numerical experiments on machine learning problems demonstrate the superiority of the proposed method over state-of-the-art algorithms in terms of both computational efficiency and selection of the step sizes. △ Less

Submitted 22 May, 2026; originally announced May 2026.

Comments: minimax problem; semismooth newton; stochastic proximal point method; variance reduction. arXiv admin note: text overlap with arXiv:2204.00406 by other authors

MSC Class: 65K05; 90C30

Optimality Conditions and Numerical Algorithms for a Class of Minimax Bilevel Optimization Problems

Authors: Yaling Hu, Jiani Wang, Yu-hong Dai, Xiaojiao Tong

Abstract: In many applications, including Stackelberg games, machine learning, and power systems \cite{Mackay2018Selftuning,Heinrich1952The,Wang2021Bi-Level}, the decisions in a minimax optimization problem can be constrained by a solution to an optimization problem. In this paper, we introduce optimality conditions of this novel minimax bilevel optimization problem and develops efficient first-order algori… ▽ More In many applications, including Stackelberg games, machine learning, and power systems \cite{Mackay2018Selftuning,Heinrich1952The,Wang2021Bi-Level}, the decisions in a minimax optimization problem can be constrained by a solution to an optimization problem. In this paper, we introduce optimality conditions of this novel minimax bilevel optimization problem and develops efficient first-order algorithms for this class of problems. Firstly, we establish the optimality conditions for minimax bilevel problems by reconstructing the lower-level problem through its Karush-Kuhn-Tucker (KKT) conditions and value function. Secondly, we develop a penalty method framework to approximately solve the minimax bilevel problem by transforming it into a single-level minimax problem. Thirdly, we design a projected gradient multi-step ascent descent method to solve the resulting minimax problem, which can find an $ε$-KKT solution for the original minimax bilevel problem within $\mathcal{O}(ε^{-3} \log(ε^{-1}))$ iterations. To improve {the convergence rate} of the algorithm, we provide its Nesterov accelerated extension with $\mathcal{O}(ε^{-3} \log(ε^{-1}))$ iteration complexity. Finally, we demonstrate the effectiveness of our model and algorithms through numerical experiments on various minimax bilevel optimization problems and a bilevel economic dispatch in the power system. △ Less

Submitted 25 April, 2026; originally announced April 2026.

MSC Class: 65K05; 90C30; 90C47; 90C90; 90C99

An Alternating Primal Heuristic for Nonconvex MIQCQP with Dynamic Convexification and Parallel Local Branching

Authors: Yongzheng Dai, Chen Chen

Abstract: We develop a novel primal heuristic for nonconvex Mixed-Integer Quadratically Constrained Quadratic Programs (MIQCQPs). The method is built around a convex approximation that is dynamically adjusted within a feasibility-pump-style alternating heuristic. Approximations are adjusted based on the structure of the MIQCQP instance. Additionally, parallelized local branching is incorporated to further r… ▽ More We develop a novel primal heuristic for nonconvex Mixed-Integer Quadratically Constrained Quadratic Programs (MIQCQPs). The method is built around a convex approximation that is dynamically adjusted within a feasibility-pump-style alternating heuristic. Approximations are adjusted based on the structure of the MIQCQP instance. Additionally, parallelized local branching is incorporated to further refine detected solutions. This paper builds upon the second-place finalist submission in the 2025 Land-Doig MIP Computational Competition. Our results are validated with computational experiments on instances from QPLIB, finding feasible solutions for three previously unsolved cases and improving the best-known solutions for fifteen instances within five minutes of runtime. △ Less

Submitted 6 April, 2026; originally announced April 2026.

Polynomial iteration complexity of a path-following smoothing Newton method for symmetric cone programming

Authors: Yu-Hong Dai, Ruoyu Diao, Xin-Wei Liu, Rui-Jin Zhang

Abstract: It has long remained open whether smoothing Newton methods (SNMs) for symmetric cone programming (SCP) admit polynomial iteration complexity. A key difficulty lies in the lack of an analogue of the self-concordant convex framework underlying interior-point methods (IPMs). In this paper, inspired by Nemirovski's self-concordant convex-concave theory, we address this open problem by introducing a re… ▽ More It has long remained open whether smoothing Newton methods (SNMs) for symmetric cone programming (SCP) admit polynomial iteration complexity. A key difficulty lies in the lack of an analogue of the self-concordant convex framework underlying interior-point methods (IPMs). In this paper, inspired by Nemirovski's self-concordant convex-concave theory, we address this open problem by introducing a reduced barrier augmented Lagrangian (BAL) function. We prove that the reduced BAL function is self-concordant convex-concave and establish that the parameterized smooth system arising in SNMs coincides with the first-order optimality conditions of an associated minimax problem. Motivated by this equivalence, we propose a path-following smoothing Newton method (PFSNM). The reduced BAL function induces a central path and an associated neighborhood, which provide estimates for the Newton decrement needed for the path-following analysis. As a result, the method achieves an iteration complexity of $\mathcal{O}(\sqrtν\ln(1/\varepsilon))$, matching the best-known short-step complexity for IPMs. Numerical results on standard benchmarks show that PFSNM is competitive with several well-known interior-point solvers, and the observed performance is consistent with the theoretical development. △ Less

Submitted 20 May, 2026; v1 submitted 5 April, 2026; originally announced April 2026.

Comments: 42 pages, 5 figures

MSC Class: 90C60; 90C25; 65K05

Scheduling Electricity Production Units to Mitigate Severe Weather Impact: An Efficient Computational Implementation

Authors: Yongzheng Dai, Antonio J. Conejo, Feng Qiu

Abstract: Extreme weather events in electric power systems can cause line trips or physical damage to transmission infrastructure, potentially leading to large-scale load shedding. To mitigate this risk, we propose a framework that strategically pre-positions the commitment of generation units--particularly slow-start units--to adapt to transmission topologies that may arise following such events. The objec… ▽ More Extreme weather events in electric power systems can cause line trips or physical damage to transmission infrastructure, potentially leading to large-scale load shedding. To mitigate this risk, we propose a framework that strategically pre-positions the commitment of generation units--particularly slow-start units--to adapt to transmission topologies that may arise following such events. The objective is to minimize load shedding under worst-case conditions. This paper makes two main contributions. First, we provide a more accurate representation of the underlying physical laws than those used in prior studies. Second, we develop a highly efficient solution algorithm that outperforms state-of-the-art, off-the-shelf solvers. The proposed framework is formulated as a two-stage robust optimization model. In the first stage, generation units are scheduled in anticipation of disruptions. In the second stage, power dispatch decisions are optimized to minimize load shedding under the worst-case transmission topology. To ensure system reliability and security, we incorporate convexified AC power flow constraints. The resulting model is a tri-level mixed-integer nonlinear optimization problem. To address its computational complexity, we design a problem-specific outer approximation algorithm embedded within a column-and-constraint generation framework. Computational results show that the proposed model and solution approach can achieve solutions within a standard optimality gap in a reasonable time for moderately large instances. △ Less

Submitted 14 July, 2026; v1 submitted 3 April, 2026; originally announced April 2026.

Warm-Startable Progressive Integrality Outer-Inner Approximation for AC Unit Commitment with Conic Formulation

Authors: Yongzheng Dai

Abstract: The alternating-current unit commitment problem provides a realistic representation of power system operations, which is a nonconvex mixed-integer nonlinear programming problem and hence is computationally intractable. A common relaxation to the alternating-current unit commitment problem is based on the second-order cone, which results in a mixed-integer second-order cone program and remains comp… ▽ More The alternating-current unit commitment problem provides a realistic representation of power system operations, which is a nonconvex mixed-integer nonlinear programming problem and hence is computationally intractable. A common relaxation to the alternating-current unit commitment problem is based on the second-order cone, which results in a mixed-integer second-order cone program and remains computationally challenging. In this paper, we propose a warm-startable outer-inner approximation framework that alternatively solves a mixed-integer linear programming (MILP) as an outer approximation and a convex second-order cone programming as an inner approximation to find a (near-)optimal solution to the second-order cone-based alternating-current unit commitment problem. To improve computational efficiency, we introduce a progressive integrality strategy that gradually enforces integrality, reducing the reliance on expensive MILP solutions in early iterations. In addition, time-block Benders cuts are incorporated to strengthen the outer approximation and accelerate convergence. Computational experiments on large-scale test systems, including 200-bus and 500-bus networks, demonstrate that the proposed framework significantly improves both efficiency and robustness compared to state-of-the-art commercial solvers. △ Less

Submitted 11 August, 2026; v1 submitted 19 March, 2026; originally announced March 2026.

Comments: Withdrawn by the authors. This work has been superseded by a substantially revised and expanded manuscript on general MISOCP, submitted separately as arXiv:2608.10055

Efficient exact sequential lifting algorithm for binary knapsack set

Authors: Xintong Wang, Liang Chen, Yu-Hong Dai

Abstract: Lifting is a crucial technique in mixed integer programming (MIP) for generating strong valid inequalities, which serve as cutting planes to improve the branch-and-cut algorithm. We first propose an exact sequential lifting algorithm for the binary knapsack set, which employs the dominance list structure to remove redundant storage and computation in the dynamic programming (DP) array. This struct… ▽ More Lifting is a crucial technique in mixed integer programming (MIP) for generating strong valid inequalities, which serve as cutting planes to improve the branch-and-cut algorithm. We first propose an exact sequential lifting algorithm for the binary knapsack set, which employs the dominance list structure to remove redundant storage and computation in the dynamic programming (DP) array. This structure preserves scale invariance and effectively handles constraints with non-integer coefficients. Then, a reduction method is developed for the lifting procedure under some conditions, further enhancing computational efficiency. Finally, numerical experiments demonstrate that the proposed algorithm outperforms DP with arrays in terms of both efficiency and stability, particularly for large-scale and large-capacity instances. Moreover, it enables exact sequential lifting for binary knapsack sets with non-integer weights and large capacities, making it directly applicable in modern MIP solvers. △ Less

Submitted 26 February, 2026; originally announced February 2026.

PEST: Physics-Enhanced Swin Transformer for 3D Turbulence Simulation

Authors: Yilong Dai, Shengyu Chen, Xiaowei Jia, Peyman Givi, Runlong Yu

Abstract: Accurate simulation of turbulent flows is fundamental to scientific and engineering applications. Direct numerical simulation (DNS) offers the highest fidelity but is computationally prohibitive, while existing data-driven alternatives struggle with stable long-horizon rollouts, physical consistency, and faithful simulation of small-scale structures. These challenges are particularly acute in thre… ▽ More Accurate simulation of turbulent flows is fundamental to scientific and engineering applications. Direct numerical simulation (DNS) offers the highest fidelity but is computationally prohibitive, while existing data-driven alternatives struggle with stable long-horizon rollouts, physical consistency, and faithful simulation of small-scale structures. These challenges are particularly acute in three-dimensional (3D) settings, where the cubic growth of spatial degrees of freedom dramatically amplifies computational cost, memory demand, and the difficulty of capturing multi-scale interactions. To address these challenges, we propose a Physics-Enhanced Swin Transformer (PEST) for 3D turbulence simulation. PEST leverages a window-based self-attention mechanism to effectively model localized PDE interactions while maintaining computational efficiency. We introduce a frequency-domain adaptive loss that explicitly emphasizes small-scale structures, enabling more faithful simulation of high-frequency dynamics. To improve physical consistency, we incorporate Navier--Stokes residual constraints and divergence-free regularization directly into the learning objective. Extensive experiments on two representative turbulent flow configurations demonstrate that PEST achieves accurate, physically consistent, and stable autoregressive long-term simulations, outperforming existing data-driven baselines. △ Less

Submitted 9 February, 2026; originally announced February 2026.

Polyhedral results for two classes of submodular sets with GUB constraints

Authors: Weikang Qian, Keyan Li, Wei-Kun Chen, Yu-Hong Dai

Abstract: In this paper, we investigate the polyhedral structure of two submodular sets with generalized upper bound (GUB) constraints, which arise as important substructures in various real-world applications. We derive a class of strong valid inequalities for the two sets using sequential lifting techniques. The proposed lifted inequalities are facet-defining for the convex hulls of two sets and are stron… ▽ More In this paper, we investigate the polyhedral structure of two submodular sets with generalized upper bound (GUB) constraints, which arise as important substructures in various real-world applications. We derive a class of strong valid inequalities for the two sets using sequential lifting techniques. The proposed lifted inequalities are facet-defining for the convex hulls of two sets and are stronger than the well-known extended polymatroid inequalities (EPIs). We provide a more compact characterization of these inequalities and show that each of them can be computed in linear time. Moreover, the proposed lifted inequalities, together with bound and GUB constraints, can completely characterize the convex hulls of the two sets, and can be separated using a combinatorial polynomial-time algorithm. Finally, computational results on probabilistic covering location and multiple probabilistic knapsack problems demonstrate the superiority of the proposed lifted inequalities over the EPIs within a branch-and-cut framework. △ Less

Submitted 26 January, 2026; originally announced January 2026.

On strong valid inequalities for a class of mixed-integer nonlinear sets with box constraints

Authors: Keyan Li, Yan-Ru Wang, Wei-Kun Chen, Yu-Hong Dai

Abstract: In this paper, we investigate the mixed-integer nonlinear set with box constraints $X = \{(w,x)\in R\times Z^n:w\leq f(a^Tx),0\leq x\leq μ\}$, where $f$ is a univariate concave function, $a\in R^n$, and $μ\in Z^n_{++}$. This set arises as a substructure in many mixed-integer nonlinear optimization models and encompasses, as special cases, several previously investigated mixed-integer sets, namely… ▽ More In this paper, we investigate the mixed-integer nonlinear set with box constraints $X = \{(w,x)\in R\times Z^n:w\leq f(a^Tx),0\leq x\leq μ\}$, where $f$ is a univariate concave function, $a\in R^n$, and $μ\in Z^n_{++}$. This set arises as a substructure in many mixed-integer nonlinear optimization models and encompasses, as special cases, several previously investigated mixed-integer sets, namely the submodular maximization set, the mixed-integer knapsack set, and the mixed-integer polyhedral conic set. We present the first comprehensive polyhedral study of conv($X$). In particular, we derive a class of seed inequalities for a two-dimensional restriction of $X$, obtained by fixing all but one of the $x$ variables to their bounds in $X$, and develop two lifting procedures to obtain strong valid inequalities for conv($X$). In the first lifting procedure, we derive a subadditive approximation for the exact lifting function of the seed inequalities, and lift all fixed variables in a single phase. In the second lifting procedure, we first lift variables fixed at their lower bounds before those at their upper bounds (and vice versa), using subadditive exact and approximation lifting functions, respectively. The derived single- and two-phase lifted inequalities are shown to be facet-defining for conv($X$) under mild conditions. Moreover, for the aforementioned special cases of conv($X$), we show that the proposed lifted inequalities can either unify existing strong valid inequalities or yield new facet-defining inequalities. Finally, extensive computational experiments on expected utility maximization and weapon-target assignment problems demonstrate that the proposed lifted inequalities can substantially strengthen the continuous relaxations and significantly improve the overall computational performance of branch-and-cut algorithms. △ Less

Submitted 26 January, 2026; originally announced January 2026.

A sequential linear complementarity problem method for generalized Nash equilibrium problems

Authors: Ruoyu Diao, Yu-Hong Dai, Liwei Zhang

Abstract: Generalized Nash equilibrium problems (GNEPs) arise in various applications where multiple players minimize individual cost functions subject to coupled constraints. A relatively unexplored approach to solving such problems is via a sequence of (mixed) linear complementarity problems (LCPs). Compared with the nonlinear equilibrium subproblems arising in recently popular penalty-based methods such… ▽ More Generalized Nash equilibrium problems (GNEPs) arise in various applications where multiple players minimize individual cost functions subject to coupled constraints. A relatively unexplored approach to solving such problems is via a sequence of (mixed) linear complementarity problems (LCPs). Compared with the nonlinear equilibrium subproblems arising in recently popular penalty-based methods such as augmented Lagrangian methods, these LCPs are often substantially easier to solve. However, the existing literature on this approach is very limited, largely because of the difficulty of assessing the search directions generated by the subproblems and establishing a principled step-length acceptance criterion. This paper proposes a sequential linear complementarity problem (SLCP) method with a comprehensive convergence analysis. To assess the search directions, we introduce a novel merit function analogous to the $\ell_1$ penalty function in sequential quadratic programming. The merit function is shown to decrease along the search directions generated by the subproblems under suitable assumptions, thereby guaranteeing the global convergence of the SLCP method. We further establish local quadratic convergence and analyze the solvability of the subproblems. Preliminary numerical results demonstrate the effectiveness and competitiveness of the proposed method relative to existing approaches. △ Less

Submitted 10 May, 2026; v1 submitted 22 January, 2026; originally announced January 2026.

Comments: 36 pages, 5 figures

MSC Class: 65K10; 90C33; 90C55; 91A10

Learning PDE Solvers with Physics and Data: A Unifying View of Physics-Informed Neural Networks and Neural Operators

Authors: Yilong Dai, Shengyu Chen, Ziyi Wang, Xiaowei Jia, Yiqun Xie, Vipin Kumar, Runlong Yu

Abstract: Partial differential equations (PDEs) are central to scientific modeling. Modern workflows increasingly rely on learning-based components to support model reuse, inference, and integration across large computational processes. Despite the emergence of various physics-aware data-driven approaches, the field still lacks a unified perspective to uncover their relationships, limitations, and appropria… ▽ More Partial differential equations (PDEs) are central to scientific modeling. Modern workflows increasingly rely on learning-based components to support model reuse, inference, and integration across large computational processes. Despite the emergence of various physics-aware data-driven approaches, the field still lacks a unified perspective to uncover their relationships, limitations, and appropriate roles in scientific workflows. To this end, we propose a unifying perspective to place two dominant paradigms: Physics-Informed Neural Networks (PINNs) and Neural Operators (NOs), within a shared design space. We organize existing methods from three fundamental dimensions: what is learned, how physical structures are integrated into the learning process, and how the computational load is amortized across problem instances. In this way, many challenges can be best understood as consequences of these structural properties of learning PDEs. By analyzing advances through this unifying view, our survey aims to facilitate the development of reliable learning-based PDE solvers and catalyze a synthesis of physics and data. △ Less

Submitted 18 February, 2026; v1 submitted 20 January, 2026; originally announced January 2026.

Model Error Resonance: The Geometric Nature of Error Dynamics

Authors: Yuntao Dai

Abstract: This paper introduces a geometric theory of model error, treating true and model dynamics as geodesic flows generated by distinct affine connections on a smooth manifold. When these connections differ, the resulting trajectory discrepancy--termed the Latent Error Dynamic Response (LEDR)--acquires an intrinsic dynamical structure governed by curvature. We show that the LEDR satisfies a Jacobi-type… ▽ More This paper introduces a geometric theory of model error, treating true and model dynamics as geodesic flows generated by distinct affine connections on a smooth manifold. When these connections differ, the resulting trajectory discrepancy--termed the Latent Error Dynamic Response (LEDR)--acquires an intrinsic dynamical structure governed by curvature. We show that the LEDR satisfies a Jacobi-type equation, where curvature mismatch acts as an explicit forcing term. In the important case of a flat model connection, the LEDR reduces to a classical Jacobi field on the true manifold, causing Model Error Resonance (MER) to emerge under positive sectional curvature. The theory is extended to a discrete-time analogue, establishing that this geometric structure and its resonant behavior persist in sampled systems. A closed-form analysis of a sphere--plane example demonstrates that curvature can be inferred directly from the LEDR evolution. This framework provides a unified geometric interpretation of structured error dynamics and offers foundational tools for curvature-informed model validation. △ Less

Submitted 12 December, 2025; originally announced December 2025.

A Surrogate Value Function Formulation for Bilevel Optimization

Authors: Mengwei Xu, Yu-Hong Dai, Xin-Wei Liu, Meiqi Ma

Abstract: The value function formulation captures the hierarchical nature of bilevel optimization through the optimal value function of the lower level problem, yet its implicit and nonsmooth characteristics pose significant analytical and computational difficulties. We introduce a surrogate value function formulation that replaces the intractable value function with an explicit surrogate derived from lower… ▽ More The value function formulation captures the hierarchical nature of bilevel optimization through the optimal value function of the lower level problem, yet its implicit and nonsmooth characteristics pose significant analytical and computational difficulties. We introduce a surrogate value function formulation that replaces the intractable value function with an explicit surrogate derived from lower level stationarity conditions. This surrogate formulation preserves the essential idea of the classical value function model but fundamentally departs from Karush Kuhn Tucker (KKT) formulations, which embed lower level stationary points into the upper level feasible region and obscure the hierarchical dependence. Instead, it enforces the hierarchy through a dominance constraint that remains valid even when lower level constraint qualifications fail at the solution. We establish equivalence with the original bilevel problem, reveal the failure of standard constraint qualifications, and show that its strong stationarity implies that of KKT models. To handle the complementarity constraints in the surrogate formulation, we apply a smoothing barrier augmented Lagrangian method and prove its convergence to solutions and Clarke stationary points. Extensive experiments demonstrate the robustness and high numerical precision of this formulation, especially in nonconvex settings, including the classical Mirrlees problem where KKT models fail. △ Less

Submitted 19 October, 2025; originally announced October 2025.

MSC Class: 90C26; 90C30; 90C33

Higher-order Casimir elements and hook partitions for quantum groups of types B, C and D

Authors: Yanmin Dai, Yang Zhang

Abstract: The higher-order quantum Casimir elements, introduced by Zhang, Bracken, and Gould in the early 1990s, were conjectured to generate the centre of the Drinfeld-Jimbo quantum (super)groups. This was previously confirmed in the classical type A. In this paper we extend the result to the classical types B, C, D, with the additional inclusion of quantum Casimir elements arising from spin and half-spin… ▽ More The higher-order quantum Casimir elements, introduced by Zhang, Bracken, and Gould in the early 1990s, were conjectured to generate the centre of the Drinfeld-Jimbo quantum (super)groups. This was previously confirmed in the classical type A. In this paper we extend the result to the classical types B, C, D, with the additional inclusion of quantum Casimir elements arising from spin and half-spin representations in types B and D. We identify the Harish-Chandra images of these elements and reinterpret them uniformly in terms of irreducible characters associated with hook partitions. This yields explicit and minimal generating sets for the centres in all classical types, and provides new connections between higher-order quantum Casimir elements and hook partitions that exhibit a stability phenomenon. △ Less

Submitted 21 September, 2025; originally announced September 2025.

Comments: 25 pages. Comments welcome

Journal ref: Journal of Algebra 706, 2026

An efficient branch-and-cut approach for the sequential competitive facility location problem under partially binary rule

Authors: Yu-Qi Guo, Yan-Ru Wang, Wei-Kun Chen, Yu-Hong Dai

Abstract: We investigate the sequential competitive facility location problem (SCFLP) under partially binary rule where two companies sequentially open a limited number of facilities to maximize their market shares, requiring customers to patronize, for each company, the facility with the highest utility. The SCFLP is a bilevel mixed integer nonlinear programming (MINLP) problem and can be rewritten as a si… ▽ More We investigate the sequential competitive facility location problem (SCFLP) under partially binary rule where two companies sequentially open a limited number of facilities to maximize their market shares, requiring customers to patronize, for each company, the facility with the highest utility. The SCFLP is a bilevel mixed integer nonlinear programming (MINLP) problem and can be rewritten as a single-level MINLP problem, where each nonlinear constraint corresponds to a hypograph of a multiple ratio function characterizing the leader's market share for a fixed follower's location choice. By establishing the submodularity of the multiple ratio functions, we characterize the mixed 0-1 set induced by each hypograph using submodular inequalities and extend a state-of-the-art branch-and-cut (B&C) algorithm to the considered SCFLP. To address the challenge of poor linear programming (LP) relaxation of the underlying formulation, we develop two new mixed integer linear programming (MILP) formulations for the SCFLP as well as efficient B&C algorithms based on them. The first MILP formulation is based on a class of improved submodular inequalities, which include the classic submodular inequalities as special cases, and together with the trivial inequalities characterize the convex hull of the mixed 0-1 set. The second one is an extended formulation of the first one that provides the same LP relaxation bound. We also develop efficient algorithms for the separations of the exponential families of the inequalities in the MILP formulations. Extensive computational experiments show that the proposed B&C algorithms significantly outperform an adapted state-of-the-art B&C algorithm and a sophisticated heuristic algorithm in the literature. Moreover, the proposed B&C algorithms can find optimal solutions for SCFLP instances with up to 1000 customers and facilities within a two-hour time limit. △ Less

Submitted 12 August, 2025; v1 submitted 11 August, 2025; originally announced August 2025.

Comments: 36 pages, 5 figures, submitted for possible publication

MSC Class: 90C11

A Dynamic Relaxation Framework for Global Solution of ACOPF

Authors: Yu-Yang Tang, Liang Chen, Sheng-Jie Chen, Yu-Hong Dai, Bo Zhou, Xiaomeng Ai

Abstract: Solving the Alternating Current Optimal Power Flow (AC OPF) problem to global optimality remains challenging due to its nonconvex quadratic constraints. In this paper, we present a unified framework that combines static piecewise relaxations with dynamic cut-generation mechanism to systematically tighten the classic Second-Order Cone Programming (SOCP) relaxation to arbitrarily small conic violati… ▽ More Solving the Alternating Current Optimal Power Flow (AC OPF) problem to global optimality remains challenging due to its nonconvex quadratic constraints. In this paper, we present a unified framework that combines static piecewise relaxations with dynamic cut-generation mechanism to systematically tighten the classic Second-Order Cone Programming (SOCP) relaxation to arbitrarily small conic violation, thus enabling the recovery of globally optimal solutions. Two static formulations, Pyramidal Relaxation (PR) and Quasi-Pyramidal Relaxation (QPR), are introduced to tighten each branch-flow second-order cone via a finite union of wedges, providing controllable accuracy. Their dynamic counterparts, Dynamic PR (DPR) and Dynamic QPR (DQPR), embed on-the-fly cut generation within a branch-and-cut solver to improve scalability. Convergence is further accelerated through warm starts and a lightweight local-search post-processing. Extensive experiments on benchmarks demonstrate effective elimination of conic violations and flexible trade-offs between solution accuracy and runtime. Practical guidelines are derived for selecting appropriate variants based on network size and accuracy requirements. △ Less

Submitted 16 June, 2025; originally announced June 2025.

Comments: Full version of a submission to IEEE Transactions on Power Systems. Includes all proofs and algorithm pseudocode

A Newton Augmented Lagrangian Method for Symmetric Cone Programming with Complexity Analysis

Authors: Rui-Jin Zhang, Ruoyu Diao, Xin-Wei Liu, Yu-Hong Dai

Abstract: Symmetric cone programming covers a broad class of convex optimization problems, including linear programming, second-order cone programming, and semidefinite programming. Although the augmented Lagrangian method (ALM) is well-suited for large-scale problems, its subproblems are often not twice continuously differentiable, preventing the direct use of classical Newton methods. To address this issu… ▽ More Symmetric cone programming covers a broad class of convex optimization problems, including linear programming, second-order cone programming, and semidefinite programming. Although the augmented Lagrangian method (ALM) is well-suited for large-scale problems, its subproblems are often not twice continuously differentiable, preventing the direct use of classical Newton methods. To address this issue, we observe that barrier functions used in interior-point methods (IPMs) naturally serve as effective smoothing terms to alleviate such nonsmoothness. By combining the strengths of ALM and IPMs, we construct a novel augmented Lagrangian function and subsequently develop a Newton augmented Lagrangian (NAL) method. By leveraging the self-concordance property of the barrier function, the proposed method is shown to achieve an $\mathcal{O}(1/ε)$ complexity bound. In addition, a spectral analysis reveals that the condition numbers of the Schur complement matrices arising in the NAL method are of order $\mathcal{O}(1/μ)$, which is better than the $\mathcal{O}(1/{μ^2})$ order of classical IPMs. This improvement is further illustrated by a heatmap of condition numbers. Numerical experiments conducted on standard benchmarks indicate that the NAL method exhibits significant performance improvements compared to several existing methods. △ Less

Submitted 28 February, 2026; v1 submitted 5 June, 2025; originally announced June 2025.

Comments: 39 pages, 4 figures

MSC Class: 49M15; 90C05; 90C22; 90C25

Spectral-Spatial Extraction through Layered Tensor Decomposition for Hyperspectral Anomaly Detection

Authors: Quan Yu, Yu-Hong Dai, Minru Bai

Abstract: Low rank tensor representation (LRTR) methods are very useful for hyperspectral anomaly detection (HAD). To overcome the limitations that they often overlook spectral anomaly and rely on large-scale matrix singular value decomposition, we first apply non-negative matrix factorization (NMF) to alleviate spectral dimensionality redundancy and extract spectral anomaly and then employ LRTR to extract… ▽ More Low rank tensor representation (LRTR) methods are very useful for hyperspectral anomaly detection (HAD). To overcome the limitations that they often overlook spectral anomaly and rely on large-scale matrix singular value decomposition, we first apply non-negative matrix factorization (NMF) to alleviate spectral dimensionality redundancy and extract spectral anomaly and then employ LRTR to extract spatial anomaly while mitigating spatial redundancy, yielding a highly efffcient layered tensor decomposition (LTD) framework for HAD. An iterative algorithm based on proximal alternating minimization is developed to solve the proposed LTD model, with convergence guarantees provided. Moreover, we introduce a rank reduction strategy with validation mechanism that adaptively reduces data size while preventing excessive reduction. Theoretically, we rigorously establish the equivalence between the tensor tubal rank and tensor group sparsity regularization (TGSR) and, under mild conditions, demonstrate that the relaxed formulation of TGSR shares the same global minimizers and optimal values as its original counterpart. Experimental results on the Airport-Beach-Urban and MVTec datasets demonstrate that our approach outperforms state-of-the-art methods in the HAD task. △ Less

Submitted 7 March, 2025; originally announced March 2025.

MSC Class: 15A69; 47A80; 65K05

Triangle Steepest Descent: A Geometry-Based Gradient Algorithm with Guaranteed R-Linear Convergence

Authors: Ya Shen, Qing-Na Li, Yu-Hong Dai

Abstract: Gradient methods are among the simplest yet most widely used algorithms for unconstrained optimization. Motivated by a geometric property of the steepest descent (SD) method that can alleviate the zigzag behavior in quadratic problems, we develop a new gradient variant called the Triangle Steepest Descent (TSD) method. The TSD method introduces a cycle parameter $j$ that governs the periodic combi… ▽ More Gradient methods are among the simplest yet most widely used algorithms for unconstrained optimization. Motivated by a geometric property of the steepest descent (SD) method that can alleviate the zigzag behavior in quadratic problems, we develop a new gradient variant called the Triangle Steepest Descent (TSD) method. The TSD method introduces a cycle parameter $j$ that governs the periodic combination of past search directions, providing a geometry-driven mechanism to enhance convergence. To the best of our knowledge, TSD is the first formally established geometry-based gradient scheme since Akaike (1959). We prove that TSD is at least R-linearly convergent for strongly convex quadratic problems and demonstrate through extensive numerical experiments that it exhibits superlinear behavior, outperforming the Barzilai-Borwein (BB) method and monotone Dai-Yuan gradient method (DY) in quadratic cases. These results suggest that incorporating geometric information into gradient directions offers a promising avenue for developing efficient optimization algorithms. △ Less

Submitted 17 October, 2025; v1 submitted 28 January, 2025; originally announced January 2025.

MSC Class: 90C20 \and 90C25

Benders decomposition for the large-scale probabilistic set covering problem

Authors: Jie Liang, Cheng-Yang Yu, Wei Lv, Wei-Kun Chen, Yu-Hong Dai

Abstract: In this paper, we consider a probabilistic set covering problem (PSCP) in which each 0-1 row of the constraint matrix is random with a finite discrete distribution, and the objective is to minimize the total cost of the selected columns such that each row is covered with a prespecified probability. We develop an effective decomposition algorithm for the PSCP based on the Benders reformulation of a… ▽ More In this paper, we consider a probabilistic set covering problem (PSCP) in which each 0-1 row of the constraint matrix is random with a finite discrete distribution, and the objective is to minimize the total cost of the selected columns such that each row is covered with a prespecified probability. We develop an effective decomposition algorithm for the PSCP based on the Benders reformulation of a standard mixed integer programming (MIP) formulation. The proposed Benders decomposition (BD) algorithm enjoys two key advantages: (i) the number of variables in the underlying Benders reformulation is equal to the number of columns but independent of the number of scenarios of the random data; and (ii) the Benders feasibility cuts can be separated by an efficient polynomial-time algorithm, which makes it particularly suitable for solving large-scale PSCPs. We enhance the BD algorithm by using initial cuts to strengthen the relaxed master problem, implementing an effective heuristic procedure to find high-quality feasible solutions, and adding mixed integer rounding enhanced Benders feasibility cuts to tighten the problem formulation. Numerical results demonstrate the efficiency of the proposed BD algorithm over a state-of-the-art MIP solver. Moreover, the proposed BD algorithm can efficiently identify optimal solutions for instances with up to 500 rows, 5000 columns, and 2000 scenarios of the random rows. △ Less

Submitted 23 January, 2025; originally announced January 2025.

Comments: 27 pages, 15 figures, accepted for publication in computers & operations research

The smallest normalized signless $\infty$-Laplacian eigenvalue for non-bipartite connected graphs

Authors: Yi Dai

Abstract: In this paper, we aim to study the smallest normalized signless $\infty$-Laplacian eigenvalue $μ_{\infty}$, a generalisation of the smallest signless Laplacian eigenvalue. For a non-bipartite connected graph, we show that the invariant $μ_{\infty}$ equals to the reciprocal of the minimal $\infty$-norm of the generalized inverses of the weighted signless incidence matrix. An example is also given t… ▽ More In this paper, we aim to study the smallest normalized signless $\infty$-Laplacian eigenvalue $μ_{\infty}$, a generalisation of the smallest signless Laplacian eigenvalue. For a non-bipartite connected graph, we show that the invariant $μ_{\infty}$ equals to the reciprocal of the minimal $\infty$-norm of the generalized inverses of the weighted signless incidence matrix. An example is also given to illustrate the result. △ Less

Submitted 29 December, 2024; originally announced December 2024.

An Efficient Stochastic Subgradient Method for the Global Placement Problem in Very Large-Scale Integration Circuits

Authors: Yi-Shuang Yue, Yu-Hong Dai, Haijun Yu

Abstract: The placement problem in Very Large-Scale Integration (VLSI) circuits is a critical step in chip design. Its primary goal is to optimize the wirelength of circuit components within a confined area while adhering to nonoverlapping constraints. This paper introduces a novel approach that directly optimizes the original nonsmooth wirelength and proposes an innovative penalty model tailored for the gl… ▽ More The placement problem in Very Large-Scale Integration (VLSI) circuits is a critical step in chip design. Its primary goal is to optimize the wirelength of circuit components within a confined area while adhering to nonoverlapping constraints. This paper introduces a novel approach that directly optimizes the original nonsmooth wirelength and proposes an innovative penalty model tailored for the global placement problem. Specifically, we transform the nonoverlapping constraints into rectified linear penalty functions, allowing for a more precise formulation of the problem. Notably, we recast the resultant optimization problem into a form analogous to training deep neural network with Rectified Linear Units (ReLU). Leveraging automatic differentiation techniques from deep learning, we efficiently compute the subgradient of the objective function. This facilitates the application of stochastic subgradient methods to solve the model. To enhance the algorithm's performance, several advanced techniques are further introduced, leading to significant improvements in both efficiency and solution quality. Numerical experiments were conducted on Gigascale Systems Research Center (GSRC) benchmark and International Symposium on Physical Design 2005 (ISPD2005) benchmark circuits. The results demonstrate that our proposed model and algorithm achieve significant reductions in wirelength while effectively eliminating overlaps. This highlights the potential of our approach as a transformative advancement for VLSI placement. Furthermore, we establish a rigorous convergence proof for the proposed stochastic subgradient method. To the best of our knowledge, it constitutes the first such result for the ReLU-type nonsmooth and nonconvex optimization problems. △ Less

Submitted 5 May, 2026; v1 submitted 29 December, 2024; originally announced December 2024.

Comments: 26pages

Journal ref: J Glob. Optim. (2026)

Distributed Recursion Revisited

Authors: Wei-Yang Zhang, Feng-Lian Dong, Zhi-Wei Wei, Yan-Ru Wang, Ze-Jin Xu, Wei-Kun Chen, Yu-Hong Dai

Abstract: The distributed recursion (DR) algorithm is an effective method for solving the pooling problem that arises in many applications. It is based on the well-known P-formulation of the pooling problem, which involves the flow and quality variables; and it can be seen as a variant of the successive linear programming (SLP) algorithm, where the linear programming (LP) approximation problem can be transf… ▽ More The distributed recursion (DR) algorithm is an effective method for solving the pooling problem that arises in many applications. It is based on the well-known P-formulation of the pooling problem, which involves the flow and quality variables; and it can be seen as a variant of the successive linear programming (SLP) algorithm, where the linear programming (LP) approximation problem can be transformed from the LP approximation problem derived by using the first-order Taylor series expansion technique. In this paper, we first propose a new nonlinear programming (NLP) formulation for the pooling problem involving only the flow variables, and show that the DR algorithm can be seen as a direct application of the SLP algorithm to the newly proposed formulation. With this new useful theoretical insight, we then develop a new variant of DR algorithm, called penalty DR (PDR) algorithm, based on the proposed formulation. The proposed PDR algorithm is a penalty algorithm where violations of the (linearized) nonlinear constraints are penalized in the objective function of the LP approximation problem with the penalty terms increasing when the constraint violations tend to be large. Compared with the LP approximation problem in the classic DR algorithm, the LP approximation problem in the proposed PDR algorithm can return a solution with a better objective value, which makes it more suitable for finding high-quality solutions for the pooling problem. Numerical experiments on benchmark and randomly constructed instances show that the proposed PDR algorithm is more effective than the classic SLP and DR algorithms in terms of finding a better solution for the pooling problem. △ Less

Submitted 14 November, 2024; originally announced November 2024.

Comments: 22 pages, 2 figures, submitted for possible publication

MSC Class: 90C59

QoS-Aware and Routing-Flexible Network Slicing for Service-Oriented Networks

Authors: Wei-Kun Chen, Ya-Feng Liu, Yu-Hong Dai, Zhi-Quan Luo

Abstract: In this paper, we consider the network slicing (NS) problem which attempts to map multiple customized virtual network requests (also called services) to a common shared network infrastructure and manage network resources to meet diverse quality of service (QoS) requirements. We propose a mixed-integer nonlinear programming (MINLP) formulation for the considered NS problem that can flexibly route t… ▽ More In this paper, we consider the network slicing (NS) problem which attempts to map multiple customized virtual network requests (also called services) to a common shared network infrastructure and manage network resources to meet diverse quality of service (QoS) requirements. We propose a mixed-integer nonlinear programming (MINLP) formulation for the considered NS problem that can flexibly route the traffic flow of the services on multiple paths and provide end-to-end delay and reliability guarantees for all services. To overcome the computational difficulty due to the intrinsic nonlinearity in the MINLP formulation, we transform the MINLP formulation into an equivalent mixed-integer linear programming (MILP) formulation and further show that their continuous relaxations are equivalent. In sharp contrast to the continuous relaxation of the MINLP formulation which is a nonconvex nonlinear programming problem, the continuous relaxation of the MILP formulation is a polynomial-time solvable linear programming problem, which significantly facilitates the algorithmic design. Based on the newly proposed MILP formulation, we develop a customized column generation (cCG) algorithm for solving the NS problem. The proposed cCG algorithm is a decomposition-based algorithm and is particularly suitable for solving large-scale NS problems. Numerical results demonstrate the efficacy of the proposed formulations and the proposed cCG algorithm. △ Less

Submitted 2 July, 2025; v1 submitted 20 September, 2024; originally announced September 2024.

Comments: 18 pages, 11 figs, submitted for possible publication. arXiv admin note: text overlap with arXiv:2110.03915

Local discontinuous Galerkin method for nonlinear BSPDEs of Neumann boundary conditions with deep backward dynamic programming time-marching

Authors: Yixiang Dai, Yunzhang Li, Jing Zhang

Abstract: This paper aims to present a local discontinuous Galerkin (LDG) method for solving backward stochastic partial differential equations (BSPDEs) with Neumann boundary conditions. We establish the $L^2$-stability and optimal error estimates of the proposed numerical scheme. Two numerical examples are provided to demonstrate the performance of the LDG method, where we incorporate a deep learning algor… ▽ More This paper aims to present a local discontinuous Galerkin (LDG) method for solving backward stochastic partial differential equations (BSPDEs) with Neumann boundary conditions. We establish the $L^2$-stability and optimal error estimates of the proposed numerical scheme. Two numerical examples are provided to demonstrate the performance of the LDG method, where we incorporate a deep learning algorithm to address the challenge of the curse of dimensionality in backward stochastic differential equations (BSDEs). The results show the effectiveness and accuracy of the LDG method in tackling BSPDEs with Neumann boundary conditions. △ Less

Submitted 17 September, 2024; originally announced September 2024.

Presolving and cutting planes for the generalized maximal covering location problem

Authors: Wei Lv, Cheng-Yang Yu, Jie Liang, Wei-Kun Chen, Yu-Hong Dai

Abstract: This paper considers the generalized maximal covering location problem (GMCLP) which establishes a fixed number of facilities to maximize the weighted sum of the covered customers, allowing customer weights to be positive or negative. Due to the huge number of linear constraints to model the covering relations between the candidate facility locations and customers, and particularly the poor linear… ▽ More This paper considers the generalized maximal covering location problem (GMCLP) which establishes a fixed number of facilities to maximize the weighted sum of the covered customers, allowing customer weights to be positive or negative. Due to the huge number of linear constraints to model the covering relations between the candidate facility locations and customers, and particularly the poor linear programming (LP) relaxation, the GMCLP is extremely difficult to solve by state-of-the-art mixed integer programming (MIP) solvers. To improve the computational performance of MIP-based approaches for solving GMCLPs, we propose customized presolving and cutting plane techniques, which are isomorphic aggregation, dominance reduction, and two-customer inequalities. The isomorphic aggregation and dominance reduction can not only reduce the problem size but also strengthen the LP relaxation of the MIP formulation of the GMCLP. The two-customer inequalities can be embedded into a branch-and-cut framework to further strengthen the LP relaxation of the MIP formulation on the fly. By extensive computational experiments, we show that all three proposed techniques can substantially improve the capability of MIP solvers in solving GMCLPs. In particular, for a testbed of 40 instances with identical numbers of customers and candidate facility locations in the literature, the proposed techniques enable us to provide optimal solutions for 13 previously unsolved benchmark instances; for a testbed of 336 instances where the number of customers is much larger than the number of candidate facility locations, the proposed techniques can turn most of them from intractable to easily solvable. △ Less

Submitted 9 May, 2025; v1 submitted 15 September, 2024; originally announced September 2024.

Comments: 27 pages, 10 figures, accepted for publication in European Journal of Operational Research

MSC Class: 90C11

Serial and Parallel Two-Column Probing for Mixed-Integer Programming

Authors: Yongzheng Dai, Chen Chen

Abstract: Probing in mixed-integer programming (MIP) is a technique of temporarily fixing variables to discover implications that are useful to branch-and-cut solvers. Such fixing is typically performed one variable at a time -- this paper develops instead a two-column probing scheme that instead fixes a pair of variables per iteration. Although the scheme involves more work per iteration compared to the on… ▽ More Probing in mixed-integer programming (MIP) is a technique of temporarily fixing variables to discover implications that are useful to branch-and-cut solvers. Such fixing is typically performed one variable at a time -- this paper develops instead a two-column probing scheme that instead fixes a pair of variables per iteration. Although the scheme involves more work per iteration compared to the one-column approach, stronger implied bounds as well as more conflicts identified may compensate. Indeed, our prototype implementation was awarded first prize at the MIP Workshop 2024 Computational Competition on novel presolving approaches. This paper presents the aforementioned (serial) prototype and additionally develops an efficient parallelization, leveraging hardware acceleration to further improve overall solve times. Compared to serial two-column probing, our parallel version sacrifices some strength per-pair probed in exchange for greatly increasing the total number of such probings; computational experiments demonstrate its promise. △ Less

Submitted 10 November, 2025; v1 submitted 29 August, 2024; originally announced August 2024.

Comments: 26 pages, 4 figures, 3 charts

MSC Class: 90C10

Adversarial Network Optimization under Bandit Feedback: Maximizing Utility in Non-Stationary Multi-Hop Networks

Authors: Yan Dai, Longbo Huang

Abstract: Stochastic Network Optimization (SNO) concerns scheduling in stochastic queueing systems. It has been widely studied in network theory. Classical SNO algorithms require network conditions to be stationary with time, which fails to capture the non-stationary components in many real-world scenarios. Many existing algorithms also assume knowledge of network conditions before decision, which rules out… ▽ More Stochastic Network Optimization (SNO) concerns scheduling in stochastic queueing systems. It has been widely studied in network theory. Classical SNO algorithms require network conditions to be stationary with time, which fails to capture the non-stationary components in many real-world scenarios. Many existing algorithms also assume knowledge of network conditions before decision, which rules out applications where unpredictability presents. Motivated by these issues, we consider Adversarial Network Optimization (ANO) under bandit feedback. Specifically, we consider the task of *i)* maximizing some unknown and time-varying utility function associated to scheduler's actions, where *ii)* the underlying network is a non-stationary multi-hop one whose conditions change arbitrarily with time, and *iii)* only bandit feedback (effect of actually deployed actions) is revealed after decisions. Our proposed `UMO2` algorithm ensures network stability and also matches the utility maximization performance of any "mildly varying" reference policy up to a polynomially decaying gap. To our knowledge, no previous ANO algorithm handled multi-hop networks or achieved utility guarantees under bandit feedback, whereas ours can do both. Technically, our method builds upon a novel integration of online learning into Lyapunov analyses: To handle complex inter-dependencies among queues in multi-hop networks, we propose meticulous techniques to balance online learning and Lyapunov arguments. To tackle the learning obstacles due to potentially unbounded queue sizes, we design a new online linear optimization algorithm that automatically adapts to loss magnitudes. To maximize utility, we propose a bandit convex optimization algorithm with novel queue-dependent learning rate scheduling that suites drastically varying queue lengths. Our new insights in online learning can be of independent interest. △ Less

Submitted 28 August, 2024; originally announced August 2024.

Enhanced Barrier-Smoothing Technique for Bilevel Optimization with Nonsmooth Mappings

Authors: Mengwei Xu, Yu-Hong Dai, Xin-Wei Liu, Bo Wang

Abstract: Bilevel optimization problems, encountered in fields such as economics, engineering, and machine learning, pose significant computational challenges due to their hierarchical structure and constraints at both upper and lower levels. Traditional gradient-based methods are effective for unconstrained bilevel programs with unique lower level solutions, but struggle with constrained bilevel problems d… ▽ More Bilevel optimization problems, encountered in fields such as economics, engineering, and machine learning, pose significant computational challenges due to their hierarchical structure and constraints at both upper and lower levels. Traditional gradient-based methods are effective for unconstrained bilevel programs with unique lower level solutions, but struggle with constrained bilevel problems due to the nonsmoothness of lower level solution mappings. To overcome these challenges, this paper introduces the Enhanced Barrier-Smoothing Algorithm (EBSA), a novel approach that integrates gradient-based techniques with an augmented Lagrangian framework. EBSA utilizes innovative smoothing functions to approximate the primal-dual solution mapping of the lower level problem, and then transforms the bilevel problem into a sequence of smooth single-level problems. This approach not only addresses the nonsmoothness but also enhances convergence properties. Theoretical analysis demonstrates its superiority in achieving Clarke and, under certain conditions, Bouligand stationary points for bilevel problems. Both theoretical analysis and preliminary numerical experiments confirm the robustness and efficiency of EBSA. △ Less

Submitted 20 August, 2024; v1 submitted 18 August, 2024; originally announced August 2024.

Exploiting Overlap Information in Chance-constrained Program with Random Right-hand Side

Authors: Wei Lv, Wei-Kun Chen, Yu-Hong Dai, Xiao-Jiao Tong

Abstract: We consider the chance-constrained program (CCP) with random right-hand side under a finite discrete distribution. It is known that the standard mixed integer linear programming (MILP) reformulation of the CCP is generally difficult to solve by general-purpose solvers as the branch-and-cut search trees are enormously large, partly due to the weak linear programming relaxation. In this paper, we id… ▽ More We consider the chance-constrained program (CCP) with random right-hand side under a finite discrete distribution. It is known that the standard mixed integer linear programming (MILP) reformulation of the CCP is generally difficult to solve by general-purpose solvers as the branch-and-cut search trees are enormously large, partly due to the weak linear programming relaxation. In this paper, we identify another reason for this phenomenon: the intersection of the feasible regions of the subproblems in the search tree could be nonempty, leading to a wasteful duplication of effort in exploring the uninteresting overlap in the search tree. To address the newly identified challenge and enhance the capability of the MILP-based approach in solving CCPs, we first show that the overlap in the search tree can be completely removed by a family of valid nonlinear if-then constraints, and then propose two practical approaches to tackle the highly nonlinear if-then constraints. In particular, we use the concept of dominance relations between different scenarios of the random variables, and propose a novel branching, called dominance-based branching, which is able to create a valid partition of the problem with a much smaller overlap than the classic variable branching. Moreover, we develop overlap-oriented node pruning and variable fixing techniques, applied at each node of the search tree, to remove more overlaps in the search tree. Computational results demonstrate the effectiveness of the proposed dominance-based branching with the overlap-oriented node pruning and variable fixing techniques in reducing the search tree size and improving the overall solution efficiency. △ Less

Submitted 26 January, 2026; v1 submitted 14 June, 2024; originally announced June 2024.

Comments: 37 pages, 3 figures, submitted for possible publication

MSC Class: 90C11; 90C15

An efficient branch-and-cut approach for large-scale competitive facility location problems with limited choice rule

Authors: Wei-Kun Chen, Wei-Yang Zhang, Yan-Ru Wang, Shahin Gelareh, Yu-Hong Dai

Abstract: In the paper, we consider the competitive facility location problem with limited choice rule (CFLPLCR), which attempts to open a subset of facilities to maximize the net profit of a newcomer company, requiring customers to patronize only a limited number of opening facilities and an outside option. We propose an efficient branch-and-cut (B&C) approach for the CFLPLCR based on newly proposed mixed… ▽ More In the paper, we consider the competitive facility location problem with limited choice rule (CFLPLCR), which attempts to open a subset of facilities to maximize the net profit of a newcomer company, requiring customers to patronize only a limited number of opening facilities and an outside option. We propose an efficient branch-and-cut (B&C) approach for the CFLPLCR based on newly proposed mixed integer linear programming (MILP) formulations. Specifically, by establishing the submodularity of the probability function, we develop an MILP formulation for the CFLPLCR using the submodular inequalities. For the special case where each customer patronizes at most one open facility and the outside option, we show that the submodular inequalities can characterize the convex hull of the considered set and provide a compact MILP formulation. Moreover, for the general case, we strengthen the submodular inequalities by sequential lifting, resulting in a class of facet-defining inequalities. The proposed lifted submodular inequalities are shown to be stronger than the classic submodular inequalities, enabling to obtain another MILP formulation with a tighter linear programming (LP) relaxation. By extensive numerical experiments, we show that the proposed B&C approach outperforms the state-of-the-art generalized Benders decomposition approach by at least one order of magnitude. Furthermore, it enables to solve CFLPLCR instances with 10000 customers and 2000 facilities. △ Less

Submitted 9 June, 2024; originally announced June 2024.

Comments: 29 pages, 2 figures, submitted for possible publication

MSC Class: 90C11

Stability for Nash Equilibrium Problems

Authors: Ruoyu Diao, Yu-Hong Dai, Liwei Zhang

Abstract: This paper is devoted to studying the stability properties of the Karush-Kuhn-Tucker (KKT) solution mapping $S_{\rm KKT}$ for Nash equilibrium problems (NEPs) with canonical perturbations. Firstly, we obtain an exact characterization of the strong regularity of $S_{\rm KKT}$ and a sufficient condition that is easy to verify. Secondly, we propose equivalent conditions for the continuously different… ▽ More This paper is devoted to studying the stability properties of the Karush-Kuhn-Tucker (KKT) solution mapping $S_{\rm KKT}$ for Nash equilibrium problems (NEPs) with canonical perturbations. Firstly, we obtain an exact characterization of the strong regularity of $S_{\rm KKT}$ and a sufficient condition that is easy to verify. Secondly, we propose equivalent conditions for the continuously differentiable single-valued localization of $S_{\rm KKT}$. Thirdly, the isolated calmness of $S_{\rm KKT}$ is studied based on two conditions: Property A and Property B, and Property B proves to be sufficient for the robustness of both $E(p)$ and $S_{\rm KKT}$ under the convex assumptions, where $E(p)$ denotes the Nash equilibria at perturbation $p$. Furthermore, we establish that studying the stability properties of the NEP with canonical perturbations is equivalent to studying those of the NEP with only tilt perturbations based on the prior discussions. Finally, we provide detailed characterizations of stability for NEPs whose each individual player solves a quadratic programming (QP) problem. △ Less

Submitted 8 July, 2025; v1 submitted 18 May, 2024; originally announced May 2024.

Comments: 28 pages

MSC Class: 90C30; 90C31; 49J53

An inexact augmented Lagrangian algorithm for unsymmetric saddle-point systems

Authors: N. Huang, Y. -H. Dai, D. Orban, M. A. Saunders

Abstract: Augmented Lagrangian (AL) methods are a well known class of algorithms for solving constrained optimization problems. They have been extended to the solution of saddle-point systems of linear equations. We study an AL (SPAL) algorithm for unsymmetric saddle-point systems and derive convergence and semi-convergence properties, even when the system is singular. At each step, our SPAL requires the ex… ▽ More Augmented Lagrangian (AL) methods are a well known class of algorithms for solving constrained optimization problems. They have been extended to the solution of saddle-point systems of linear equations. We study an AL (SPAL) algorithm for unsymmetric saddle-point systems and derive convergence and semi-convergence properties, even when the system is singular. At each step, our SPAL requires the exact solution of a linear system of the same size but with an SPD (2,2) block. To improve efficiency, we introduce an inexact SPAL algorithm. We establish its convergence properties under reasonable assumptions. Specifically, we use a gradient method, known as the Barzilai-Borwein (BB) method, to solve the linear system at each iteration. We call the result the augmented Lagrangian BB (SPALBB) algorithm and study its convergence. Numerical experiments on test problems from Navier-Stokes equations and coupled Stokes-Darcy flow show that SPALBB is more robust and efficient than BICGSTAB and GMRES. SPALBB often requires the least CPU time, especially on large systems. △ Less

Submitted 22 April, 2024; originally announced April 2024.

Report number: G-2024-30 MSC Class: 65F10; 65F50

A cut-and-project perspective for linearized Bregman iterations

Authors: Yu-Hong Dai, Kangkang Deng, Hui Zhang

Abstract: The linearized Bregman iterations (LBreI) and its variants are powerful tools for finding sparse or low-rank solutions to underdetermined linear systems. In this study, we propose a cut-and-project perspective for the linearized Bregman method via a bilevel optimization formulation, along with a new unified algorithmic framework. The new perspective not only encompasses various existing linearized… ▽ More The linearized Bregman iterations (LBreI) and its variants are powerful tools for finding sparse or low-rank solutions to underdetermined linear systems. In this study, we propose a cut-and-project perspective for the linearized Bregman method via a bilevel optimization formulation, along with a new unified algorithmic framework. The new perspective not only encompasses various existing linearized Bregman iteration variants as specific instances, but also allows us to extend the linearized Bregman method to solve more general inverse problems. We provide a completed convergence result of the proposed algorithmic framework, including convergence guarantees to feasible points and optimal solutions, and the sublinear convergence rate. Moreover, we introduce the Bregman distance growth condition to ensure linear convergence. At last, our findings are illustrated via numerical tests. △ Less

Submitted 15 April, 2024; originally announced April 2024.

MSC Class: 90C25; 90C30; 65K05; 49M37

A Proximal-Gradient Method for Constrained Optimization

Authors: Yutong Dai, Xiaoyi Qu, Daniel P. Robinson

Abstract: We present a new algorithm for solving optimization problems with objective functions that are the sum of a smooth function and a (potentially) nonsmooth regularization function, and nonlinear equality constraints. The algorithm may be viewed as an extension of the well-known proximal-gradient method that is applicable when constraints are not present. To account for nonlinear equality constraints… ▽ More We present a new algorithm for solving optimization problems with objective functions that are the sum of a smooth function and a (potentially) nonsmooth regularization function, and nonlinear equality constraints. The algorithm may be viewed as an extension of the well-known proximal-gradient method that is applicable when constraints are not present. To account for nonlinear equality constraints, we combine a decomposition procedure for computing trial steps with an exact merit function for determining trial step acceptance. Under common assumptions, we show that both the proximal parameter and merit function parameter eventually remain fixed, and then prove a worst-case complexity result for the maximum number of iterations before an iterate satisfying approximate first-order optimality conditions for a given tolerance is computed. Our preliminary numerical results indicate that our approach has great promise, especially in terms of returning approximate solutions that are structured (e.g., sparse solutions when a one-norm regularizer is used). △ Less

Submitted 10 April, 2024; originally announced April 2024.

MSC Class: 49M37; 65K05; 65K10; 65Y20; 68Q25; 90C30; 90C60

Stochastic Approximation Proximal Subgradient Method for Stochastic Convex-Concave Minimax Optimization

Authors: Yu-Hong Dai, Jiani Wang, Liwei Zhang

Abstract: This paper presents a stochastic approximation proximal subgradient (SAPS) method for stochastic convex-concave minimax optimization. By accessing unbiased and variance bounded approximate subgradients, we show that this algorithm exhibits ${\rm O}(N^{-1/2})$ expected convergence rate of the minimax optimality measure if the parameters in the algorithm are properly chosen, where $N$ denotes the nu… ▽ More This paper presents a stochastic approximation proximal subgradient (SAPS) method for stochastic convex-concave minimax optimization. By accessing unbiased and variance bounded approximate subgradients, we show that this algorithm exhibits ${\rm O}(N^{-1/2})$ expected convergence rate of the minimax optimality measure if the parameters in the algorithm are properly chosen, where $N$ denotes the number of iterations. Moreover, we show that the algorithm has ${\rm O}(\log(N)N^{-1/2})$ minimax optimality measure bound with high probability. Further we study a specific stochastic convex-concave minimax optimization problems arising from stochastic convex conic optimization problems, which the the bounded subgradient condition is fail. To overcome the lack of the bounded subgradient conditions in convex-concave minimax problems, we propose a linearized stochastic approximation augmented Lagrange (LSAAL) method and prove that this algorithm exhibits ${\rm O}(N^{-1/2})$ expected convergence rate for the minimax optimality measure and ${\rm O}(\log^2(N)N^{-1/2})$ minimax optimality measure bound with high probability as well. Preliminary numerical results demonstrate the effect of the SAPS and LSAAL methods. △ Less

Submitted 29 March, 2024; originally announced March 2024.

MSC Class: 90C30

Towards large-scale probabilistic set covering problems: an efficient Benders decomposition approach

Authors: Wei Lv, Wei-Kun Chen, Yi-Long Chen, Yu-Hong Dai

Abstract: In this paper, we investigate the probabilistic set covering problem (PSCP) in which the right-hand side is a binary random vector and the covering constraint is required to be satisfied with a prespecified probability. We consider the case with a finite discrete distribution of the random vector, which usually arises in the context of the sample average approximation approach. We develop an effec… ▽ More In this paper, we investigate the probabilistic set covering problem (PSCP) in which the right-hand side is a binary random vector and the covering constraint is required to be satisfied with a prespecified probability. We consider the case with a finite discrete distribution of the random vector, which usually arises in the context of the sample average approximation approach. We develop an effective Benders decomposition (BD) algorithm for solving large-scale PSCPs, which enjoys two key advantages: (i) the number of variables in the underlying Benders reformulation is independent of the scenario size; and (ii) the Benders cuts can be separated by an efficient combinatorial algorithm. For the special case that random vector is a combination of several independent random blocks/subvectors, we explicitly take this kind of block structure into consideration and develop a more efficient BD algorithm. Moreover, to further speed up the two proposed BD algorithms, we develop a class of strong valid inequalities, which are guaranteed to be facet-defining for the polytope induced by the probabilistic constraint. Numerical results on instances with up to one million scenarios demonstrate the effectiveness of the proposed BD algorithms over a black-box mixed integer programming solver's branch-and-cut and automatic BD algorithms and a state-of-the-art algorithm in the literature. △ Less

Submitted 22 March, 2026; v1 submitted 28 February, 2024; originally announced February 2024.

Comments: 27 pages, accepted for publication in INFORMS Journal on Computing

Tensor Completion via Integer Optimization

Authors: Xin Chen, Sukanya Kudva, Yongzheng Dai, Anil Aswani, Chen Chen

Abstract: The main challenge with the tensor completion problem is a fundamental tension between computation power and the information-theoretic sample complexity rate. Past approaches either achieve the information-theoretic rate but lack practical algorithms to compute the corresponding solution, or have polynomial-time algorithms that require an exponentially-larger number of samples for low estimation e… ▽ More The main challenge with the tensor completion problem is a fundamental tension between computation power and the information-theoretic sample complexity rate. Past approaches either achieve the information-theoretic rate but lack practical algorithms to compute the corresponding solution, or have polynomial-time algorithms that require an exponentially-larger number of samples for low estimation error. This paper develops a novel tensor completion algorithm that resolves this tension by achieving both provable convergence (in numerical tolerance) in a linear number of oracle steps and the information-theoretic rate. Our approach formulates tensor completion as a convex optimization problem constrained using a gauge-based tensor norm, which is defined in a way that allows the use of integer linear optimization to solve linear separation problems over the unit-ball in this new norm. Adaptations based on this insight are incorporated into a Frank-Wolfe variant to build our algorithm. We show our algorithm scales-well using numerical experiments on tensors with up to ten million entries. △ Less

Submitted 3 April, 2024; v1 submitted 6 February, 2024; originally announced February 2024.

Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for Nonconvex Minimax Problems with Coupled linear Constraints

Authors: Huiling Zhang, Zi Xu, Yuhong Dai

Abstract: In this paper, we study zeroth-order algorithms for nonconvex minimax problems with coupled linear constraints under the deterministic and stochastic settings, which have attracted wide attention in machine learning, signal processing and many other fields in recent years, e.g., adversarial attacks in resource allocation problems and network flow problems etc. We propose two single-loop algorithms… ▽ More In this paper, we study zeroth-order algorithms for nonconvex minimax problems with coupled linear constraints under the deterministic and stochastic settings, which have attracted wide attention in machine learning, signal processing and many other fields in recent years, e.g., adversarial attacks in resource allocation problems and network flow problems etc. We propose two single-loop algorithms, namely the zeroth-order primal-dual alternating projected gradient (ZO-PDAPG) algorithm and the zeroth-order regularized momentum primal-dual projected gradient algorithm (ZO-RMPDPG), for solving deterministic and stochastic nonconvex-(strongly) concave minimax problems with coupled linear constraints. The iteration complexity of the two proposed algorithms to obtain an $\varepsilon$-stationary point are proved to be $\mathcal{O}(\varepsilon ^{-2})$ (resp. $\mathcal{O}(\varepsilon ^{-4})$) for solving nonconvex-strongly concave (resp. nonconvex-concave) minimax problems with coupled linear constraints under deterministic settings and $\tilde{\mathcal{O}}(\varepsilon ^{-3})$ (resp. $\tilde{\mathcal{O}}(\varepsilon ^{-6.5})$) under stochastic settings respectively. To the best of our knowledge, they are the first two zeroth-order algorithms with iterative complexity guarantees for solving nonconvex-(strongly) concave minimax problems with coupled linear constraints under the deterministic and stochastic settings. The proposed ZO-RMPDPG algorithm, when specialized to stochastic nonconvex-concave minimax problems without coupled constraints, outperforms all existing zeroth-order algorithms by achieving a better iteration complexity, thus setting a new state-of-the-art. △ Less

Submitted 5 March, 2026; v1 submitted 26 January, 2024; originally announced February 2024.

Comments: arXiv admin note: text overlap with arXiv:2212.04672

Understanding Adam Optimizer via Online Learning of Updates: Adam is FTRL in Disguise

Authors: Kwangjun Ahn, Zhiyu Zhang, Yunbum Kook, Yan Dai

Abstract: Despite the success of the Adam optimizer in practice, the theoretical understanding of its algorithmic components still remains limited. In particular, most existing analyses of Adam show the convergence rate that can be simply achieved by non-adative algorithms like SGD. In this work, we provide a different perspective based on online learning that underscores the importance of Adam's algorithmi… ▽ More Despite the success of the Adam optimizer in practice, the theoretical understanding of its algorithmic components still remains limited. In particular, most existing analyses of Adam show the convergence rate that can be simply achieved by non-adative algorithms like SGD. In this work, we provide a different perspective based on online learning that underscores the importance of Adam's algorithmic components. Inspired by Cutkosky et al. (2023), we consider the framework called online learning of updates/increments, where we choose the updates/increments of an optimizer based on an online learner. With this framework, the design of a good optimizer is reduced to the design of a good online learner. Our main observation is that Adam corresponds to a principled online learning framework called Follow-the-Regularized-Leader (FTRL). Building on this observation, we study the benefits of its algorithmic components from the online learning perspective. △ Less

Submitted 30 May, 2024; v1 submitted 2 February, 2024; originally announced February 2024.

Comments: Accepted at ICML 2024

Parallelized Conflict Graph Cut Generation

Authors: Yongzheng Dai, Chen Chen

Abstract: A conflict graph represents logical relations between binary variables, and effective use of the graph can significantly accelerate branch-and-cut solvers for mixed-integer programming (MIP). In this paper we develop efficient parallel conflict graph management: conflict detection; maximal clique generation; clique extension; and clique merging. We leverage parallel computing in order to intensify… ▽ More A conflict graph represents logical relations between binary variables, and effective use of the graph can significantly accelerate branch-and-cut solvers for mixed-integer programming (MIP). In this paper we develop efficient parallel conflict graph management: conflict detection; maximal clique generation; clique extension; and clique merging. We leverage parallel computing in order to intensify computational effort on the conflict graph, thereby generating a much larger pool of cutting planes than what can be practically achieved in serial. Computational experiments demonstrate that the expanded pool of cuts enabled by parallel computing lead to substantial reductions in total MIP solve time, especially for more challenging cases. △ Less

Submitted 17 June, 2025; v1 submitted 6 November, 2023; originally announced November 2023.

Comments: 25 pages, 3 figures

MSC Class: 90C10

Exact penalty method for D-stationary point of nonlinear optimization

Authors: Xin-Wei Liu, Yu-Hong Dai

Abstract: We consider the nonlinear optimization problem with least $\ell_1$-norm measure of constraint violations and introduce the concepts of the D-stationary point, the DL-stationary point and the DZ-stationary point with the help of exact penalty function. If the stationary point is feasible, they correspond to the Fritz-John stationary point, the KKT stationary point and the singular stationary point,… ▽ More We consider the nonlinear optimization problem with least $\ell_1$-norm measure of constraint violations and introduce the concepts of the D-stationary point, the DL-stationary point and the DZ-stationary point with the help of exact penalty function. If the stationary point is feasible, they correspond to the Fritz-John stationary point, the KKT stationary point and the singular stationary point, respectively. In order to show the usefulness of the new stationary points, we propose a new exact penalty sequential quadratic programming (SQP) method with inner and outer iterations and analyze its global and local convergence. The proposed method admits convergence to a D-stationary point and rapid infeasibility detection without driving the penalty parameter to zero, which demonstrates the commentary given in [SIAM J. Optim., 20 (2010), 2281--2299] and can be thought to be a supplement of the theory of nonlinear optimization on rapid detection of infeasibility. Some illustrative examples and preliminary numerical results demonstrate that the proposed method is robust and efficient in solving infeasible nonlinear problems and a degenerate problem without LICQ in the literature. △ Less

Submitted 24 September, 2023; originally announced September 2023.

Comments: 24 pages

MSC Class: 49M37; 65K05; 90C26; 90C30; 90C55

Lipschitz Transport Maps via the Follmer Flow

Authors: Yin Dai, Yuan Gao, Jian Huang, Yuling Jiao, Lican Kang, Jin Liu

Abstract: Inspired by the construction of the F{ö}llmer process, we construct a unit-time flow on the Euclidean space, termed the F{ö}llmer flow, whose flow map at time 1 pushes forward a standard Gaussian measure onto a general target measure. We study the well-posedness of the F{ö}llmer flow and establish the Lipschitz property of the flow map at time 1. We apply the Lipschitz mapping to several rich clas… ▽ More Inspired by the construction of the F{ö}llmer process, we construct a unit-time flow on the Euclidean space, termed the F{ö}llmer flow, whose flow map at time 1 pushes forward a standard Gaussian measure onto a general target measure. We study the well-posedness of the F{ö}llmer flow and establish the Lipschitz property of the flow map at time 1. We apply the Lipschitz mapping to several rich classes of probability measures on deriving dimension-free functional inequalities and concentration inequalities for the empirical measure. △ Less

Submitted 7 September, 2023; originally announced September 2023.