# On Implementing a Two-Step Interior Point Method for Solving Linear Programs
## 2 Algorithm  
In this paper, without loss of generality, we make the following assumptions:  
* \(A\) is a full rank matrix, that is rank \(A=m\leq n\).
* Both problems (P) and (D) satisfy the Interior Point Condition (IPC) [8], i.e., there exists \((x^{0},s^{0})>0\) and \(y^{0}\) so that: \[Ax^{0} = b,\qquad x^{0}>0,\] \[A^{T}y^{0}+s^{0} = c,\qquad s^{0}>0.\] An optimal solution for (P) and (D) can be found by solving the following system [10]: \[Ax = b,\qquad\quad x\geq 0,\] \[A^{T}y+s = c,\qquad\quad s\geq 0,\] (1) \[xs = 0,\] where \(xs\) stands for the coordinate-wise (Hadamard) product of the vectors \(x\) and \(s\). Note that the first and second equations in (1) guarantee the feasibility of \(x\) and \((y,s)\) for problems (P) and (D), respectively, and the last equation is satisfied only if the feasible solution is optimal (complementarity conditions).  
The algorithm presented here is a two-step primal-dual IPM; therefore, we summarize the key idea behind the generic primal-dual IPMs for solving linear programming problems from the literature, see e.g., [8; 10]. The key idea is to replace the complementarity conditions with parameterized equations \(xs=\mu\mathbf{e}\), where \(\mathbf{e}\) denotes the all-one vector of length \(n\) and \(\mu\) is a real positive parameter. With these changes, the system of Equation (1) can be expressed as [10]:  
\[Ax = b,\qquad x\geq 0,\] \[A^{T}y+s = c,\qquad s\geq 0, \tag{2}\] \[xs = \mu\mathbf{e}.\]The parametric system (2) has a unique solution for any \(\mu>0\) if the IPC holds (10) (Theorem 1.2.4). For a given \(\mu>0\), denote the unique solution of (2) by \((x(\mu),y(\mu),s(\mu))\), where \(x(\mu)\) is the \(\mu\)-center of (P) and \((y(\mu),s(\mu))\) is called the \(\mu\)-center of (D). The set of all \(\mu\)-centers, for all \(\mu>0\), defines a path the so-called _central path_ for (P) and (D). It has been shown that, as \(\mu\to 0\), then the limit of the central path exists and converges to an analytic center of the optimal solutions set of (P) and (D) (22; 23).  
Given a current point \((x,y,s)\), the goal is to find direction \((\Delta x,\Delta y,\Delta s)\) such that the point \((x+\Delta x,y+\Delta y,s+\Delta s)\) lies on the central path at \(\mu\). If it did lie exactly on the central path, then Equation (2) will be satisfied, i.e., (10):  
\[A(x+\Delta x) = b\] \[A^{T}(y+\Delta y)+(s+\Delta s) = c \tag{3}\] \[(X+\Delta x)(S+\Delta s) = \mu\mathbf{e},\]  
where:  
\[X:=\text{diag}(x),\qquad S:=\text{diag}(s)\]  
Assuming that the point \((x,y,s)\) is feasible for the LO and dropping the non-linear term \(\Delta x\Delta s\)(10), we get the following system of equations:  
\[A\Delta x = 0\] \[A^{T}\Delta y+\Delta s = 0 \tag{4}\] \[S\Delta x+X\Delta s = \mu\mathbf{e}-XS\mathbf{e}\]  
System (4) has a unique solution, referred to as the search direction for IPMs. Many interior-point algorithms rely on the [PERSON] method to solve the system (4) and find the search direction. Therefore, improving the speed of convergence of [PERSON]'s method significantly impacts the convergence speed and efficiency of IPMs. To calculate the search direction in [PERSON]'s method, we use the method proposed in (20), which has a convergence speed of \(1+\sqrt{2}\). Accordingly, we introduce a two-step method for the IPM based on the approach proposed in (20). This change can significantly reduce the number of iterations needed to achieve the optimal solution.To apply the mentioned method, we present the system (4) as a problem of finding roots, followed by an explanation of the new approach.