EPM: An Exterior Point Method for Linear Programming

Terrence K. Kelly and Joseph G. Ecker

This paper looks at the linear programming problem ($min\{c^Tx |\;Ax=b,\;x\geq0,\;A\in \Re^{m \times n}\}$) from a new and naive perspective. A special LP formulation is presented, and a theory developed which uses exterior points as approximations to the optimal point. This leads to an exterior point algorithm which converges to the solution in at most $m$ iterations of a convex minimization problem over an affine space ${\cal C}_\alpha \in \Re^n$ of dimension $n-m-1$, contained in a contour of the objective function. Furthermore, it can be shown that the solution to the subproblem using a Newton's method converges to the subproblem optimal point in one iteration, if the current point and the subproblem optimal point are in the same orthant of $\Re^n$. This is of particular note, since the algorithm can therefore be viewed in three parts: Move from an exterior point in ${\cal C}_\alpha$ to some point in ${\cal C}_\alpha \cap {\cal O}$ where ${\cal O}$ is the orthant containing the subproblem optimal point. Move directly to the subproblem optimal point. Move back towards the positive orthant the step length prescribed by the algorithm. The second and third steps are polynomial in the dimensions of the problem only. If the dependence of the first step on the instance of the problem can be eliminated (which we do not claim in this paper), a strongly polynomial algorithm for LP would be in hand.

Contact: ft9290@exmail.usma.edu