Finding an initial feasible point which is both accurate and sparse for a linear programming (LP) problem has been known as the Phase I problem. Literature provides various ideas based on Lagrange relaxation that imply solving a sequence of convex quadratic subproblems with nonnegativity constraints. This paper provides a small elaboration of several ideas and adds a novel approach to generate a feasible point or certify that it does not exist. Moreover, we perform a comparative computational study on the smallest Netlib sparse LP problems to generate the performance profiles on five metrics where subproblems are solved to optimality with fmincon from Matlab® Optimization Toolbox.