This paper presents a universal trust-region method simultaneously incorporating quadratic regularization and the ball constraint. We introduce a novel mechanism to set the parameters in the proposed method that unifies the analysis for convex and nonconvex optimization. Our method exhibits an iteration complexity of $\tilde O(\epsilon^{-3/2})$ to find an approximate second-order stationary point for nonconvex optimization. Meanwhile, the analysis reveals that the universal method attains an $O(\epsilon^{-1/2})$ complexity bound for convex optimization and can be accelerated. These results are complementary to the existing literature as the trust-region method was historically conceived for nonconvex optimization. Finally, we develop an adaptive universal method to address practical implementations. The numerical results show the effectiveness of our method in both nonconvex and convex problems.
Integer programming with block structures has received considerable attention recently and is widely used in many practical applications such as train timetabling and vehicle routing problems. It is known to be NP-hard due to the presence of integer variables. We define a novel augmented Lagrangian function by directly penalizing the inequality constraints and establish the strong duality between the primal problem and the augmented Lagrangian dual problem. Then, a customized augmented Lagrangian method is proposed to address the block-structures. In particular, the minimization of the augmented Lagrangian function is decomposed into multiple subproblems by decoupling the linking constraints and these subproblems can be efficiently solved using the block coordinate descent method. We also establish the convergence property of the proposed method. To make the algorithm more practical, we further introduce several refinement techniques to identify high-quality feasible solutions. Numerical experiments on a few interesting scenarios show that our proposed algorithm often achieves a satisfactory solution and is quite effective.
A recent GPU implementation of the Restarted Primal-Dual Hybrid Gradient Method for Linear Programming was proposed in Lu and Yang (2023). Its computational results demonstrate the significant computational advantages of the GPU-based first-order algorithm on certain large-scale problems. The average performance also achieves a level close to commercial solvers for the first time in history. However, due to limitations in experimental hardware and the disadvantage of implementing the algorithm in Julia compared to C language, neither the commercial solver nor cuPDLP reached their maximum efficiency. Therefore, in this report, we have re-implemented and optimized cuPDLP in C language. Utilizing state-of-the-art CPU and GPU hardware, we extensively compare cuPDLP with the best commercial solvers. The experiments further highlight its substantial computational advantages and potential for solving large-scale linear programming problems. We also discuss the profound impact this breakthrough may have on mathematical programming research and the entire operations research community.
In this paper, we introduce a Homogeneous Second-Order Descent Method (HSODM) using the homogenized quadratic approximation to the original function. The merit of homogenization is that only the leftmost eigenvector of a gradient-Hessian integrated matrix is computed at each iteration. Therefore, the algorithm is a single-loop method that does not need to switch to other sophisticated algorithms, and is easy to be implemented. We show that HSODM has a global convergence rate of $O(\epsilon^{-3/2})$ to find an $\epsilon$-approximate second-order stationary point, and has a local quadratic convergence rate under the standard assumptions. The numerical results demonstrate the advantage of the proposed method over other second-order methods.
In many important machine learning applications, the standard assumption of having a globally Lipschitz continuous gradient may fail to hold. This paper delves into a more general $(L_0, L_1)$-smoothness setting, which gains particular significance within the realms of deep neural networks and distributionally robust optimization (DRO). We demonstrate the significant advantage of trust region methods for stochastic nonconvex optimization under such generalized smoothness assumption. We show that first-order trust region methods can recover the normalized and clipped stochastic gradient as special cases and then provide a unified analysis to show their convergence to first-order stationary conditions. Motivated by the important application of DRO, we propose a generalized high-order smoothness condition, under which second-order trust region methods can achieve a complexity of $\mathcal{O}(\epsilon^{-3.5})$ for convergence to second-order stationary points. By incorporating variance reduction, the second-order trust region method obtains an even better complexity of $\mathcal{O}(\epsilon^{-3})$, matching the optimal bound for standard smooth optimization. To our best knowledge, this is the first work to show convergence beyond the first-order stationary condition for generalized smooth optimization. Preliminary experiments show that our proposed algorithms perform favorably compared with existing methods.
This paper proposes a homogeneous second-order descent framework (HSODF) for nonconvex and convex optimization based on the generalized homogeneous model (GHM). In comparison to the Newton steps, the GHM can be solved by extremal symmetric eigenvalue procedures and thus grant an advantage in ill-conditioned problems. Moreover, GHM extends the ordinary homogeneous model (OHM) to allow adaptiveness in the construction of the aggregated matrix. Consequently, HSODF is able to recover some well-known second-order methods, such as trust-region methods and gradient regularized methods, while maintaining comparable iteration complexity bounds. We also study two specific realizations of HSODF. One is adaptive HSODM, which has a parameter-free $O(\epsilon^{-3/2})$ global complexity bound for nonconvex second-order Lipschitz continuous objective functions. The other one is homotopy HSODM, which is proven to have a global linear rate of convergence without strong convexity. The efficiency of our approach to ill-conditioned and high-dimensional problems is justified by some preliminary numerical results.
This paper introduces a mid-term planning model for scheduling assembly and test operations aimed at minimising the difference between customer demand and product completions each day. A secondary objective is to maximise daily surplus which is a surrogate for throughput. Typically, semiconductor companies have 1000s of products or devices in their catalogue that can be organised into unique groups of up to a 100 devices each. This simplifies the planning process because it is only necessary to consider the groups as a whole rather than the individual devices when constructing schedules. In all, we developed and tested three related models. Each provides daily production rates at each process step for each device group for up to one month at a time. The models are distinguished by how cycle time is treated. The first takes a steady-state approach and uses Little’s Law to formulate a WIP target constraint based on the average cycle time at each processing step. The second and third include integer and fractional cycle times in the variable definitions. To find solutions, raw production data are analysed in a preprocessing step and then converted to input files in a standard format. FlopC++ from the COIN-OR open source software project is used to write and solve the model. Testing was done using three data-sets from the Taiwan AT facility of a global semiconductor firm. By comparing model output with historical data for 6 device groups and 33 process steps, we were able to realise decreases in shortages of up to 40% per month.
The ADMM-based interior point (ABIP, Lin et al. 2021) 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 the alternating direction method of multipliers (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. Firstly, we develop an ABIP method to solve the general linear conic optimization and establish the associated iteration complexity. Secondly, inspired by some existing methods, we develop different implementation strategies for ABIP method, which substantially improve its performance in linear optimization. Finally, we conduct extensive numerical experiments in both synthetic and real-world datasets to demonstrate the empirical advantage of our developments. In particular, the enhanced ABIP method achieves a 5.8x reduction in the geometric mean of run time on $105$ selected LP instances from Netlib, and it exhibits advantages in certain structured problems such as SVM 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.
ADMM-based Interior Point Method for Linear and Conic Programming (ABIP) is a new framework that applies alternating direction method of multipliers (ADMM) to implement interior point method (IPM) for solving large-scale linear programs (LP) and conic programs (QCP). ABIP (LP part) was initially developed by Tianyi Lin (https://github.com/tyDLin) and is currently maintained by LEAVES optimization software platform. The original ABIP follows the following paper: @article{lin_admm-based_2021, title = {An {ADMM}-based interior-point method for large-scale linear programming}, volume = {36}, number = {2-3}, journal = {Optimization Methods and Software}, author = {Lin, Tianyi and Ma, Shiqian and Ye, Yinyu and Zhang, Shuzhong}, year = {2021}, note = {Publisher: Taylor \& Francis}, pages = {389--424}, }
The rear spoiler of an F1 racing car is the main component that affects its aerodynamic performance. In the race, it is necessary to select the wing with different characteristics according to different track characteristics. In this paper, computational fluid dynamics (CFD) technology is used to study four different types of stationary airfoils, analyze their aerodynamic performance under three different track conditions, combine the characteristics of the track for quantitative analysis, and finally target the most suitable airfoil. Airfoil 2 is suitable for track 1 - Spa Francolchamp, a track with many curves and changeable climate, because of its medium negative lift value. The high negative lift force generated by airfoil 4 is applicable to the high altitude track, for example, Track 2 - The Rodriguez Brothers Track in this study. For airfoil 1, the lowest resistance value is applicable to track 3 - Silverstone, which is a track with many straight tracks and high-speed curves.
'/%3e%3cuse xlink:href='%23a' transform='rotate(23.036 .093 25.536)'/%3e%3cuse xlink:href='%23a' transform='rotate(45.87 1.273 16.18)'/%3e%3cuse xlink:href='%23a' transform='rotate(69.945 .996 12.078)'/%3e%3cuse xlink:href='%23a' transform='rotate(20.66 -19.689 31.932)'/%3e%3c/svg%3e)
'/%3e%3cuse xlink:href='%23a' transform='rotate(144 450 300)'/%3e%3cuse xlink:href='%23a' transform='rotate(216 450 300)'/%3e%3cuse xlink:href='%23a' transform='rotate(288 450 300)'/%3e%3c/svg%3e)
