IPM-LSTM: A Learning-Based Interior Point Method for Solving Nonlinear Programs

Thank the reviewer for reading our manuscript and providing constructive coments. Please refer to the Author Rebuttal for a clarification of the two-stage framework proposed in our work.

Weakness

1. The decision to use the L2O approach for solving a least squares.......

Thanks for raising this point.

• Theoretical: the least-squares problem (4) in our manuscript is an unconstrained convex optimization problem. Several works have proved that L2O approaches could solve such problems to guaranteed tolerances. For example, the work of [5] proved that solutions provided by properly parameterized LSTM networks converge to one of the minimizers of composite optimization problems. Another interesting case is the work of [6] in which the authors proposed an unrolling of the ISTA algorithm and proved that solutions returned by the ISTA-unrolled method converge to the optimal ones.
• Empirical: The accuracy condition is not strictly enforced in our implementation since we aim to balance the accuracy and efficiency of solving linear systems via LSTM. As shown in Section 4, the IPM-LSTM algorithm is able to provide high-quality approximate solutions with mild infeasibility and sub-optimality (Stage I). These solutions are suitable for many practical applications. If solutions with increased feasibility and optimality are needed, one can quickly polish and refine the approximate solutions by feeding them to an IPM solver (Stage II).

2. The approach of using an approximated IPM solution instead of.....[1][2][3][4]...

Thanks for raising this point. We further clarify the motivation of our algorithmic design as follows.

• In this work, we focus on developing learning-based methods to warm-start an IPM solver for optimizing general nonlinear and convex/non-convex programs. As the Reviewer 9Qph commented, "The topic is important as IPM plays a crucial role in solving linear and nonlinear programs, which have extensive applications in scientific computing." The works of [1][2] are focused on warm-starting fixed-point algorithms for efficiently solving convex QPs and conic programs.
• As we mentioned in Section 2, warm-starting an IPM solver is notoriously hard since it entails providing well-centered primal-dual solutions [7][8]. Recently, learning-based approaches have been proposed to address this. However, most of works such as [3][4] did not even include dual solutions for warm-starting. These methods might work well for specific applications but could not boost the performance of an IPM solver when optimizing general nonlinear programs. Some works such as [9] indeed provide primal-dual solutions but those pairs are not intended to be well-centered.
• Our proposed IPM-LSTM approach works in a similar way as a classic IPM except that linear systems are approximately solved by LSTM networks. Since every iterate (e.g., primal-dual solution) follows a central path (e.g., the same parameter $\mu$ is chosen for each dimension in the perturbed KKT system, as shown in Algorithm 1), the final solution pair returned by IPM-LSTM would then be well-centered and of high quality. Such a primal-dual solution is thus well-suited for warm-starting an IPM solver.

Questions

1. ...why not directly use the simple NN prediction as a warm-start point...

Thanks for raising this point. As pointed out by [10], a simple NN prediction often leads to significant constraint violation. To alleviate this issue, we integrated the objective function and penalty for constraint violation into the loss function and included such a method as a baseline (denoted as "NN") in our manuscript. From Table 1, 2, 5, 7, and 8, we can conclude that warm-starting IPOPT with initial solutions predicted by NNs brings limited (sometimes even negative) performance improvement.

2. ...why are the equality constraints not satisfied...

We apologize for any confusion. In the computational results, the "IPM-LSTM" in the end-to-end fashion produces approximate solutions that might be neither feasible nor optimal, which can result in small violations of the equality constraints. However, when these solutions are used to warm-start an IPM solver such as IPOPT (denoted as "IPOPT (warm-start)" in each table), IPOPT returns locally optimal solutions that do not exhibit any constraint violations, as shown in Table 1, 2, 5, 7, and 8.

3....Does this mean the proposed approach can not exceed state-of-the-art...

Thank you for raising this question. Indeed, the proposed IPM-LSTM approach is outperformed by OSQP when solving convex QPs.

• The IPM-LSTM method is designed to provide high-quality approximate solutions for general nonlinear and convex/non-convex programs. It follows a classic IPM approach, with the distinction that linear systems are approximately solved using an LSTM network.
• OSQP employs an operator-splitting algorithm specifically tailored for convex QPs. This solver has demonstrated superior performance even when compared to state-of-the-art general-purpose solvers like IPOPT and Gurobi in optimizing convex QPs.

Therefore, IPM-LSTM is capable of addressing a wide range of optimization problems, but it is not as competitive as OSQP when it comes to solving convex QPs.

[5] Liu, Jialin, et al. (2023) "Towards constituting mathematical structures for learning to optimize." ICML.

[6] Aberdam, A., et al. (2021). Ada-lista: Learned solvers adaptive to varying models. IEEE TPAMI.

[7] Nocedal, J., & Wright, S. J. (Eds.). (1999). Numerical optimization.

[8] Wright, S. J. (1997). Primal-dual interior-point methods.

[9] Park, S., & Van Hentenryck, P. (2023). Self-supervised primal-dual learning for constrained optimization. AAAI.

[10] Donti, P. L., et al. (2021). DC3: A learning method for optimization with hard constraints. ICLR.

Thank the reviewer for reading our manuscript and providing constructive coments. Please refer to the Author Rebuttal for a clarification of the two-stage framework proposed in our work.

My main concern about this paper is Assumption 1, which requires the accuracy of the linear system solution to increase as the number of iterations $k$ increases. Based on this assumption, exact convergence is derived, as shown in Proposition 1. However, the empirical results in Section 4 indicate that IPM-LSTM does not achieve exact optimality, revealing a gap between theory and practice.

Thank you for pointing this out. The IPM-LSTM utilizes an LSTM network to return approximate solutions to linear systems. Proposition 1 implies that exact optimality could be achieved by IPM-LSTM in theory. However, in practice, solving linear systems to the tolerance specified in Assumption 1 would be too time-consuming. As a result, we choose to strike a balance between the accuracy and efficiency of solving linear systems via LSTM. Consequently, the satisfaction of Assumption 1 is not fully ensured in our implementation, leading to the mild suboptimality and infeasibility observed in Section 4.

To address this gap, I suggest: 1. Reporting the error of LSTM at each iteration. This would provide readers with an understanding of how accurately the LSTM performs. Additionally, it would be beneficial to report the relationship between the error of the linear system solution with the size, training, and testing overhead of the LSTM.

Thanks for your suggestion. The error of solving linear systems is indeed vital. We have plotted the progress of $\\|J^ky^k+F^k\\|$ as the IPM iteration increases in Fig. 3(a) of our manuscript. Now we report the detailed values in the following table. From this table, $\\|J^ky^k+F^k\\|$ is roughly in the same order of magnitude as $\eta[(z^k)^{\top}x^k]/n$ at each IPM iteration.

To reveal the relationship between the error of the linear system solution $\\|J^ky^k+F^k\\|$ and the LSTM time steps, hidden dimensions, training sizes and test sizes, we conduct experiments on representative convex QP (RHS) problems with 100 variables, 50 inequality constraints, and 50 equality constraints, and the results are included in Fig. 2 of the supplementary material.

• In Fig. 2(a), with the LSTM time step increasing, $\\|J^ky^k+F^k\\|$ decreases.
• In Fig. 2(b), we consider LSTMs with 25, 50, 75, and 100 hidden dimensions and find that an LSTM with a hidden dimension of 50, as used in our manuscript, generally performs the best (e.g., resulting in the smallest $\\|J^ky^k + F^k\\|$).
• In Fig. 2$c$, a larger training set is more beneficial for model training. The training set size used in our manuscript is 8,334, and the error in solving the linear system $\\|J^ky^k + F^k\\|$ is smaller compared with the case of 4,000 or 6,000 training samples.
• As shown by Fig. 2(d), the number of samples in the test set does not affect the performance of LSTM for solving linear systems.

2. Using a log scale y-axis for Figure 3a for better precision. For example, 0.01 is 10 times greater than 0.001, but this difference is not reflected in the linear scale of Figure 3a.

Thanks for your suggestion. We now take the log of the y-axis in Fig. 3(a) of our manuscript and plot it in Fig. 3(a) of the supplementary material.

• Roughly speaking, $\\|J^k y^k + F^k\\|$ is smaller than $\eta [(z^k)^\top x^k] / n$ in the first $40$ IPM iterations, while $\\|J^k y^k + F^k\\|$ surpasses $\eta [(z^k)^\top x^k]/n$ in the later IPM iterations.
• Following the comments from Reviewer Qdyo, we increase the LSTM time steps and report the computational results in Fig. 3(b) of the supplementary material. From Fig. 3(a) and 3(b), We can claim that with the LSTM time steps increasing, $\\|J^k y^k + F^k\\|$ becomes smaller and closer to $\eta [(z^k)^\top x^k]/n$.

3. Modifying Assumption 1 to better align with practice. For example, assuming a fixed error on the right-hand sides of equations (5) and (6). Based on this relaxed assumption, a result similar to Proposition 1 could be derived, but with a fixed error on the limit of $(x^k, \lambda^k, z^k)$. The relationship between the allowed error in Assumption 1 and the propagated eventual error in Proposition 1 would sufficiently describe the performance of IPM-LSTM.

Thank you for your suggestion. Equation (5) in our manuscript is designed to be consistent with the assumptions made in classic inexact IPMs or inexact Newton methods, as seen in Equation (4) in [1], Equation (2.1) in [2], Equation (6) in [3], and Equation (12) in [4]. To the best of our knowledge, the theoretical bounds referenced in these works are dependent on the iteration count $k$, and do not involve fixed error terms. We would explore the use of fixed error bounds in our future studies.

[1] Bellavia, Stefania. Inexact interior-point method. Journal of Optimization Theory and Applications 96 (1998): 109-121.

[2] Eisenstat, Stanley C., and Homer F. Walker. Globally convergent inexact Newton methods. SIAM Journal on Optimization 4.2 (1994): 393-422.

[3] Al-Jeiroudi, Ghussoun, and Jacek Gondzio. Convergence analysis of the inexact infeasible interior-point method for linear optimization. Journal of Optimization Theory and Applications 141 (2009): 231-247.

[4] Gondzio, Jacek. Convergence analysis of an inexact feasible interior point method for convex quadratic programming. SIAM Journal on Optimization 23.3 (2013): 1510-1527.

Thank the reviewer for reading our manuscript and providing constructive coments. Please refer to the Author Rebuttal for a clarification of the two-stage framework proposed in our work.

1. The linear system solver used for IPOPT is unclear, which significantly impacts the solver's overall performance. While MUMPS is the default, HSL typically performs better, achieving 2-3 times faster results. This performance surpasses that of IPOPT when warm-started with the IPM-LSTM solution.

Thanks for your suggestion. The default solver MUMPS was used in our experiments. To evaluate the effect of linear solvers on the performance of IPOPT, we consider 3 commonly used linear solvers (MA27, MA57, and MA86) from HSL and bundle IPOPT with each of them. We conduct experiments on 6 datasets used in our manuscript, each with 100 variables, 50 inequality constraints, and 50 equality constraints. We report the average computational time (in seconds) for each dataset in the table below. Results for IPOPT with different linear solvers are presented in the 2nd - 5th columns, while those for IPOPT warm-started by IPM-LSTM are listed in the last four columns.

• The computational results demonstrate that MUMPS is generally outperformed by MA57 but superior to MA27 and MA86.
• Regardless of linear solvers, warm-starting IPOPT with primal-dual solutions provided by IPM-LSTM enhances the performance of IPOPT itself.

2. There is no analysis of how the performance changes with varying numbers of iterations in the inner LSTM, which decides the performance-efficiency trade-off of IPM-LSTM. Longer inner iterations (deeper LSTM) may improve the quality of the solutions but increases computation costs. However, improved solution quality may also decrease the number of outer iterations needed and thus reduce the overall solving time. Moreover, increased LSTM depth can make the training process more difficult. Overall, thise is tricky part and should be empirically investigated more carefully.

Thanks for your suggestion. We first remark that in our implementation, the number of IPM iteration (e.g., outer iteration) is fixed to $100$. The number of iterations in the inner LSTM indeed incurs the performance trade-off. To illustrate this, we conduct experiments on convex QP (RHS) problems with 100 variables, 50 inequality constraints, and 50 equality constraints, investigating the quality of approximate solutions under different LSTM inner iteration settings. We report the results in the table below and Fig. 1 in the supplementary material.

• At each IPM iteration, as the LSTM network depth increases, $\\|J^k y^k + F^k\\|$ decreases (see Fig. 1(a)). This indicates an improvement in the quality of solutions to the linear systems. Furthermore, the corresponding IPM-LSTM converges faster (e.g., fewer outer iterations) when the LSTM network becomes deeper (see Fig.1(b)).
• From the table below, generally speaking, the IPM-LSTM with deeper LSTM architectures tends to produce better approximate solutions (with lower objective values and smaller constraint violation) but with longer computational time.
• Training deeper LSTM networks indeed becomes more challenging, such as longer training time and more memory consumption due to large computational graphs, vanishing or exploding gradient issues [1].

3. Although LSTM benefits from batched processing—a potential strength of IPM-LSTM accelerated by GPU—this work fails to provide empirical evidence supporting this property.

Thanks for your suggestion. Given a batch size of $k$ testing samples, we are able to feed all of them to the trained IPM-LSTM at the same time. Let $T$ denote the wall-clock time used when all samples are solved by IPM-LSTM. The average solution time for each instance is then $T/k$. Thus, the proposed IPM-LSTM approach can indeed leverage the advantage of GPU batch processing.

To demonstrate this, we conducted tests on convex QPs (RHS) with 100 variables, 50 inequalities, and 50 equalities, with batch sizes varying from 10 to 5,000. The computational results are reported in Fig. 1$c$ of the supplementary material. As shown in Fig. 1$c$, the average solution time decreases as the batch size increases. However, due to hardware limitations, once the batch size exceeds a certain threshold, the average computational time will level off.

[1] Pascanu, Razvan, Tomas Mikolov, and Yoshua Bengio. "On the difficulty of training recurrent neural networks." International conference on machine learning. PMLR, 2013.

Dear Reviewer,

Thank you for your time and efforts throughout the review period. Please read the authors' rebuttal as soon as possible and indicate if their responses have addressed all your concerns.

Best,

Your AC