# On Implementing a Two-Step Interior Point Method for Solving Linear Programs
## 2 Algorithm
### Two-Step IPMs  
Here, we extend the idea presented in Section 2.1 to the interior-point algorithm. The extension involves two phases:  
* Phase 1: We obtain a feasible starting point \((x,y,s)\) using the method presented in [17]. Then, we create an auxiliary point \((\tilde{x},\tilde{y},\tilde{s})\), which initially has the same values as \((x,y,s)\). The parameter \(\mu\) is updated by a factor of \(1-\theta\), and \((\tilde{x},\tilde{y},\tilde{s})\) is set to \((x,y,s)\). After that, we set \((\tilde{x},\tilde{y},\tilde{s})=\frac{1}{2}((\tilde{x},\tilde{y},\tilde{s})+( x,y,s))\) and solve the following system to determine the search direction: \[A\Delta x = 0\] \[A^{T}\Delta y-\Delta s = 0\] (5) \[\hat{S}\Delta x+\hat{X}\Delta s = \mu\mathbf{e}-XS\mathbf{e}\] To satisfy the feasibility condition, the algorithm performs a line search to find the maximum step size. To obtain the new point, the current point is updated in the following way: \[(x,y,s)\leftarrow(x+\alpha\Delta x,y+\alpha\Delta y,s+\alpha\Delta s)\]
* Phase 2: In this phase, starting from \(k\geq 1\), we begin by updating the parameter \(\mu\) and constructing the auxiliary point. Then, we utilize it to create the principal point. As in Phase 1, we solve the following system to determine the search direction for the auxiliary point: \[A\Delta x = 0\] \[A^{T}\Delta y-\Delta s = 0\] (6) \[\hat{S}\Delta x+\hat{X}\Delta s = \mu\mathbf{e}-XS\mathbf{e}.\] Since the left-hand side of (6) is the same as the left-hand side of (5), so there is no need to compute the inverse. Next, a line search is performed to determine the maximum step size, and the auxiliary point is updated as follows: \[(\tilde{x},\tilde{y},\tilde{s})\leftarrow(x+\alpha\Delta x,y+\alpha\Delta y,s+ \alpha\Delta s)\]
Next, the middle point is updated as:  
\[(\hat{x},\hat{y},\hat{s})\leftarrow\frac{1}{2}((\hat{x},\hat{y},\hat{s})+(x,y,s))\]  
Finally, the algorithm updates the principal point using the search direction \((\Delta x,\Delta y,\Delta s)\) is obtained by solving the following system:  
\[A\Delta x = 0\] \[A^{T}\Delta y-\Delta s = 0\]0 \[A^{T}\Delta y-\Delta s = 0\]1  
As earlier, to ensure that the principal point satisfies the feasibility condition, a line search is performed to determine the maximum step size. The principal point is then updated as follows:  
\[A^{T}\Delta y-\Delta s = 0\]2  
In order to determine the maximum value for the step size \(\alpha\) in each iteration, we utilize the method presented by [PERSON] et al. (2018). This method initially calculates an upper bound based on the positivity constraints of the variables. If \((x+\alpha\Delta x,y+\alpha\Delta y,s+\alpha\Delta s)\) is not feasible, then \(\alpha\) is decreased by a certain multiplicative factor until the point is feasible. This approach is more efficient than determining the optimal value for \(\alpha\), as it avoids an additional computational step. Algorithm 1 outlines the steps of this new approach. ```
Input:\(x_{0},\ y_{0},\ s_{0},\ \mu,\theta,\epsilon\) \((x,y,s)\leftarrow(x_{0},y_{0},s_{0})\) \((\hat{x},\hat{y},\hat{s})\leftarrow(x,y,s)\) \((\hat{x},\hat{y},\hat{s})\leftarrow\frac{1}{2}((\hat{x},\hat{y},\hat{s})+(x,y, s))\) \(\mu\leftarrow(1-\theta)\mu\)  Find search direction \((\Delta x,\Delta y,\Delta s)\) by solving (5). Find the maximum value for the step size \(\alpha\). Set \((x,y,s)\leftarrow(x+\alpha\Delta x,y+\alpha\Delta y,s+\alpha\Delta s)\) whilestopping criteria is not metdo \(\mu\leftarrow\mu(1-\theta)\)  Solve (6) to find the search direction. Find the maximum value for the step size. Set \((\hat{x},\hat{y},\hat{s})\leftarrow(x+\alpha\Delta x,y+\Delta y,s+\Delta s)\). Set \((\hat{x},\hat{y},\hat{s})\leftarrow\frac{1}{2}((\hat{x},\hat{y},\hat{s})+(x,y, s))\)  Find search direction \((\Delta x,\Delta y,\Delta s)\) by solving (7). Find the maximum value for the step size \(\alpha\).