# On Implementing a Two-Step Interior Point Method for Solving Linear Programs
## 2 Algorithm
### Discussion  
The idea in the Algorithm is also used in ([PERSON] et al., 2018) for finding roots of a univariate function \(f\) using a modification to the Newton-Raphson method. The method requires two steps a predictor step and a corrector step. The predictor step computes the point \(\tilde{x}_{+}\) based on a linear approximation of the function around the current point \(x\). In the corrector step, the new point is calculated using the derivative at a point which is the average of the current point and the predictor. This can be expressed as [20]:  
\[\hat{x}_{+}=x-\frac{f(x)}{f^{\prime}(\frac{x+\hat{x}}{2})}\]  
If we call \(1/2(x+\hat{x}_{+})\) as \(\hat{x}\) and use the derivative at \(\hat{x}\) instead at \(x\) in the predictor step, then we have the following scheme:  
\[\hat{x} = \frac{x+\hat{x}_{+}}{2}\] \[x_{+} = x-\frac{f(x)}{f^{\prime}(\hat{x})}\]  
In particular applications \(f^{\prime}(\hat{x})\) is a good estimate of \(f^{\prime}(x)\). Therefore this reduces the number of derivate evaluations. If the predictor-corrector scheme was not used, then the new point is \(\hat{x}\), and the function value would be \(f(\hat{x})=f(x-f(x)/f^{\prime}(\hat{x}))\). Since a corrector is used, the value of \(f\) at the new point is \(f(x-f(x)/f^{\prime}(\hat{x}_{+}))\). If there is a favourable relationship between the derivatives of the predictor and the corrector points, then (assuming a minimization problem) we have:  
\[f(x-f(x)/f^{\prime}(\hat{x}))>f(x-f(x)/f^{\prime}(\hat{x}_{+})) \tag{11}\]  
Suppose this inequality is valid in many iterative steps. In that case, there will be a reduction in the number of iterations compared to the Newton-Raphson method. The decrease in iterations required can be credited to the new approach's ability to attain the optimal point of the Newton method at a rate of \(1+\sqrt{2}\). This higher convergence rate means that the new method needs fewer iterations than the traditional approach.  
In general, if the function is multivariate denoted \(F\), then the updates can be written as:  
\[\hat{x}_{+}=x-\alpha(\
abla F(\hat{x}))^{-1}F(x)\] \[\hat{x}_{+}=1/2(x+\hat{x}_{+})\] \[x_{+}=x-\alpha(\
abla F(\hat{x}_{+}))^{-1}F(x)\]  
The algorithm presented in this paper is fundamentally distinct from the predictor-corrector method proposed by [PERSON] [17]. Notably, one of the main differences lies in the approach to calculating the search direction. While both algorithms leverage the two-stage search direction concept, Algorithm 1 computes the search direction by utilizing an auxiliary point and taking the average of this auxiliary point and the main point. Another significant contrast arises in the computation of the matrix inverse. Algorithm 1 requires calculating the matrix inverse only once per iteration. Consequently, it falls into the category of one-step methods in terms of time consumption, while achieving efficiency akin to two-step algorithms. These distinctions set Algorithm 1 apart from the predictor-corrector method of [17], highlighting its unique and promising characteristics in solving optimization problems. Moreover, the method in [17] requires tuning many parameters in each iteration, which can be expensive and complex for some problems to find their optimal values. In contrast, our proposed method involves far fewer parameters to tune, simplifying the process and potentially reducing the computational burden.