Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2000-007 (November 06, 2000)

An Infeasible Interior Proximal Method for Convex Programming Problems with Linear Constraints
by Nobuo Yamashita, Christian Kanzow, Tomoyuki Morimoto and Masao Fukushima

PostScript File

In this paper, we propose an infeasible interior proximal method for solving a convex programming problem with linear constraints. The interior proximal method proposed by Auslender and Haddou is a proximal method using a distance-like barrier function, and it has a global convergence property under mild assumptions. However this method is applicable only to problems whose feasible region has an interior point, because an initial point for the method must be chosen from the interior of the feasible region. The algorithm proposed in this paper is based on the idea underlying the infeasible interior point method for linear programming. This algorithm is applicable to problems whose feasible region may not have a nonempty interior, and it can be started from an arbitrary initial point. We establish global convergence of the proposed algorithm under appropriate assumptions.