The alternating-direction-method-of-multipliers-based (ADMM-based) interior point method, or ABIP method, is a hybrid algorithm that effectively combines interior point method (IPM) and first-order methods to achieve a performance boost in large-scale linear optimization. Different from traditional IPM that relies on computationally intensive Newton steps, the ABIP method applies ADMM to approximately solve the barrier penalized problem. However, similar to other first-order methods, this technique remains sensitive to condition number and inverse precision. In this paper, we provide an enhanced ABIP method with multiple improvements. First, we develop an ABIP method to solve the general linear conic optimization and establish the associated iteration complexity. Second, inspired by some existing methods, we develop different implementation strategies for the ABIP method, which substantially improve its performance in linear optimization. Finally, we conduct extensive numerical experiments in both synthetic and real-world data sets to demonstrate the empirical advantage of our developments. In particular, the enhanced ABIP method achieves a 5.8× reduction in the geometric mean of run time on 105 selected linear optimization instances from Netlib, and it exhibits advantages in certain structured problems, such as support vector machine and PageRank. However, the enhanced ABIP method still falls behind commercial solvers in many benchmarks, especially when high accuracy is desired. We posit that it can serve as a complementary tool alongside well-established solvers. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms—Continuous. Funding: This research was supported by the National Natural Science Foundation of China [Grants 72394360, 72394364, 72394365, 72225009, 72171141, and 72150001] and by the Program for Innovative Research Team of Shanghai University of Finance and Economics. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0017 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0017 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
We introduce a new first order method for solving the semidefinite programming (SDP) problem with a convex and differentiable objective based on the alternating direction method of multipliers (ADMM) and a matrix-splitting technique. Our algorithm has an advantage over the Burer–Monteiro (BM) approach as it involves much easier quadratically regularized subproblems in each iteration. For a linear objective, the subproblems are well-conditioned quadratic programs that can be efficiently solved by the standard conjugate gradient method. We show that our algorithm achieves sublinear or linear convergence rates to the Karush–Kuhn–Tucker solutions under different conditions. Based on this theoretical development, we present LoRADS, a new solver for linear SDP based on the low-rank ADMM splitting approach. LoRADS applies several strategies to significantly improve its efficiency. First, it initiates with a warm-start phase that uses the BM approach. Moreover, motivated by the advances on the SDP low-rank theory, LoRADS chooses an initial rank of logarithmic order and employs a dynamic approach to increase the rank. Although LoRADS does not necessarily ensure global optimality, it performs well on many important and large-scale problems, such as MaxCut and matrix completion. Notably, LoRADS solved (i) a MaxCut problem with the dimension of 1,048,576 in less than seven minutes and (ii) a matrix completion problem with 71,681,424 constraints and a 180,000 × 180,000 matrix in about half an hour, achieving accuracies below 1e-5 for both problems. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: C. Li, Z. Lin, and D. Ge were supported in part by the National Natural Science Foundation of China [Grants 72225009, 72394360, and 72394365]. C. Chen was supported in part by the National Natural Science Foundation of China [Grants 72394363/72394360, 12431011 and 12122107] and the Fundamental Research Funds for the Central Universities. Q. Deng was supported in part by the National Natural Science Foundation of China [Grants 72394364/72394360 and 12571325] and the Natural Science Foundation of Shanghai [Grant 24ZR1421300]. H. Liu was supported in part by the Young Elite Scientists Sponsorship Program [Grant CAST 2023QNRC001] and the National Natural Science Foundation of China [Grants NSFC-72192830 and 72192832]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0701 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0701 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
The software and data in this repository are a snapshot of the software and data that were used in the research reported on in the paper Uniformly Optimal and Parameter-free First-order Methods for Convex and Function-constrained Optimization by Qi Deng, Guanghui Lan and Zhenwei Lin
6 January 2026 in Mathematics of Operations Research
We study monotone function-constrained variational inequalities (FCVIs) whose feasible region is the intersection of a projection-friendly set and several convex function constraints; both the operator and the constraint functions may be smooth, nonsmooth, and/or stochastic. Computing the projection operator is challenging for FCVIs. We introduce the adaptive operator extrapolation (AdOpEx) method, which employs an operator extrapolation on the Karush–Kuhn–Tucker operator of the FCVI in a smooth deterministic setting. Because this operator is not uniformly Lipschitz continuous in the Lagrange multipliers, we employ an adaptive two-timescale algorithm leading to bounded multipliers and achieving the optimal [ ] convergence rate. For the nonsmooth and stochastic VIs, we introduce design changes to the AdOpEx method and propose a novel P-OpEx method that takes a partial extrapolation. It converges at the rate of [ ] when both the operator and constraints are stochastic or nonsmooth. This method has suboptimal dependence on the noise and Lipschitz constants of function constraints. We propose a constraint extrapolation approach leading to the OpConEx method that improves this dependence by an order of magnitude. All our algorithms also extend to solving saddle point problems with jointly convex function constraints that couple the primal and dual variables. Within this structured class of problems, our methods preserve their respective complexity guarantees, establishing what we believe to be the first such comprehensive complexity results. Funding: D. Boob and M. Khalafi were partially supported by the National Science Foundation [Grants 2245705 and 2340858]. D. Boob was partially supported by the Office of Naval Research [Grant N000142412749]. Q. Deng was partially supported by the National Natural Science Foundation of China [Grants 12571325 and 72394364/72394360] and the Natural Science Foundation of Shanghai [Grant 24ZR1421300].
LoRADS is an enhanced first-order method solver for low rank Semi-definite programming problems (SDPs). LoRADS is written in ANSI C and is maintained by Cardinal Operations COPT development team. More features are still under active development.
Cascade hydropower scheduling is a high-dimensional, tightly constrained multi-objective optimization problem in which classical genetic and evolutionary algorithms struggle to find feasible solutions. Under random initialization, algorithms such as the Non-dominated Sorting Genetic Algorithm II (NSGA-II), the Non-dominated Sorting Genetic Algorithm III (NSGA-III), and the Constrained Two-Archive Evolutionary Algorithm (C-TAEA) rarely produce any feasible solution when the feasible region occupies a vanishingly small fraction of the search space. This paper presents a three-phase framework that combines physics-guided deep learning with evolutionary computation to accelerate both NSGA-II and NSGA-III. The method trains a Physics-Embedded Temporal Convolutional Network (PeTCN) as a differentiable surrogate model that explicitly incorporates physical constraints, applies gradient-based inverse optimization to obtain a feasible or near-feasible solution of high quality, and warm-starts NSGA-II or NSGA-III with that solution for efficient Pareto front exploration. Experiments on a real-world six-station cascade system show that, under a 1500 s fixed-time budget across 20 independent runs, Boosted NSGA-II and Boosted NSGA-III both find feasible solutions in all runs. Boosted NSGA-II and Boosted NSGA-III both reach the first feasible solution within roughly 50–60 generations of Phase 3 search on average, whereas standard NSGA-II produces no feasible run within the same budget and standard NSGA-III requires thousands of generations among its successful runs. The mean final hypervolume reaches for Boosted NSGA-II and for Boosted NSGA-III, and both boosted algorithms reach a target hypervolume of in all 10 target-hypervolume runs. These results demonstrate that coupling physics-embedded surrogates with gradient-based initialization is an effective strategy for constrained multi-objective problems in which feasible solutions are extremely sparse.