# On Implementing a Two-Step Interior Point Method for Solving Linear Programs
## 1 Introduction
### Literature Review  
IPMs are generally divided into two categories, that is, small-update methods and large-update methods [8]. In practice, large-update methods are significantly more efficient.  
However, in theory, the best results are associated with small-update methods. From another perspective, IPMs are divided into feasible and infeasible methods [9]. Feasible methods start from a point that satisfies the constraints and seek to find the optimal solution within the feasible region. In contrast, infeasible methods begin with a point that does not meet the problem's constraints (infeasible). The algorithm first seeks to find a feasible point, and once a feasible point is found, it moves towards the optimal solution [9]. The IPM based on the kernel function is a popular method. The kernel function is used not only to find the search direction for the algorithm but also to estimate a lower bound for the step size [10]. In this type of IPM, the complexity bounds of the interior point algorithm are computed based on the kernel function. [PERSON] et al. [10] proposed a new variant of IPMs for solving linear optimization problems in which the self-regular barrier function replaces the logarithmic barrier function and they showed that their method has the best-known complexity bounds. Following this, several different kernel functions with the best-known complexity bounds have been introduced, including the exponential kernel functions [11], trigonometric kernel functions [12; 13] and hyperbolic kernel functions [14; 15].  
Predictor-corrector methods for interior point algorithms are an effective approach for solving both linear and nonlinear optimization problems [16; 17]. These methods incorporate two main steps, i.e., the predictor step and the corrector step. In the predictor step, an approximate direction is determined by solving a linearized system of the Karush-Kuhn-Tucker (KKT) conditions [17]. In the subsequent corrector step, this direction is refined to ensure that the iterates remain within the feasible region and maintain the balance between the primal and dual variables. This refinement typically involves solving another system of linear equations that corrects any infeasibilities introduced in the predictor step, thereby enhancing the convergence properties of the algorithm. [PERSON]'s algorithm [17] is a popular predictor-corrector algorithm used for solving optimization problems. In recent years, several new predictor-corrector algorithms have been introduced, further enhancing the effectiveness and efficiency of IPMs for various optimization problems [18; 19].  
The Newton method is a popular optimization technique that plays a vital role in interior-point methods. In the context of IPMs, the Newton method is used to solve the system of equations that arise from the Karush-Kuhn-Tucker (KKT) optimality conditions, which include both the primal and dual feasibility conditions, as well as the complementary slackness conditions. This approach is known for its fast convergence rate, often exhibiting quadratic convergence. A modification of [PERSON]'s method was proposed by [PERSON] and [PERSON] [20] that can significantly reduce the number of iterations when used to the root of functions. Their approach has a convergence of the order of \(1+\sqrt{2}\). To compute the search direction, their algorithm uses an auxiliary point and computes the gradient of the objective function only once in each iteration.  
[PERSON] and [PERSON] [20] applied this method to solve the power flow problem, which is a multivariate problem. They used the improved method to find the roots of a system of multivariable equations and demonstrated that it can reduce the number of iterations compared to [PERSON]'s method. Additionally, [PERSON] et al. [21] present some theoretical results related to the convergence of the method. In Example 4 of [21], it is shown that the method is effective for solving multivariable problems and can converge to the optimal solution.