Homogenous Analytic Center Cutting Plane Methods with Approximate Centers

Rapport Rapport de recherche Homogenous Analytic Center Cutting Plane Methods with Approximate Centers eng 1998 author Nesterov Yurii 28897 author Peton Olivier 113897 author Vial Jean-Philippe 22754 In this paper we consider a homogeneous analytic center cutting plane method in a projective space. We describe a general scheme that uses a homogeneous oracle and computes an approximate analytic center at each iteration. This technique is applied to a convex feasibility problem, to variational inequalities, and convex constrained minimization. We prove that these problems can be solved with the same order of complexity as in the case of exact analytic centers. For the feasibility and the minimization problems rough approximations suffice, but very high precision is required for the variational inequalities. We give an exemple of variational inequality where even the first analytic center needs to be computed with a precision matching the precision required for the solution Dewey 332/658 Dewey 330/650 Cahiers de recherche 1998.03 9 Faculté d'économie et de management S false Faculté d'économie et de management

Title	Published in	Access level	OA Policy	Year	Views	Downloads

Homogenous Analytic Center Cutting Plane Methods with Approximate Centers				1998	540	0

Archive ouverte UNIGE

Nesterov, Yurii