This paper describes two algorithms for the problem of minimizing a linear function over the intersection of an affine set and a convex set which is required to be the closure of the domain of a strongly self-concordant Barrier function. One algorithm is a path-following methods while the other is a primal potential-reduction method. We give bounds on the number of iterations necessary to attain a given accuracy