Groupe d’études et de recherche en analyse des décisions


A Path-Following Cutting Plane Method for some Monotone Variational Inequalities


The paper considers two cases of variational inequality problems. The first case involves an affine monotone operator over a convex set defined by a separation oracle. An interior-point algorithm that mixes an interior cutting plane method and a short-step path-following method will be presented. Its complexity will be established. The second case involves a nonlinear monotone operator defined over the same type of convex set. An interior-point algorithm which is a combination of a cutting plane method and a long-step path-following method and uses the Jacobian of the operator will be presented. It will be shown that this latter algorithm finds an approximate solution in finite time.

, 30 pages