## 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