Variational inequalities with the analytic center cutting plane method

This thesis concerns the solution of variational inequalities (VIs) with analytic center cutting plane methods (ACCPMs). A convex feasibility problem reformulation of the variational inequality is used; this reformulation applies to VIs defined with pseudo-monotone, single-valued mappings or with maximal monotone, multi-valued mappings.Two cutting plane methods are presented: the first is based on linear cuts while the second uses quadratic cuts. The first method, ACCPM-VI (linear cuts), requires mapping evaluations but no Jacobian evaluations; in fact, no differentiability assumption is needed. The cuts are placed at approximate analytic centers that are tracked with infeasible primal-dual Newton steps. Linear equality constraints may be present in the definition of the VI's set of reference, and are treated explicitly. The set of reference is assumed to be polyhedral, or is convex and iteratively approximated by polyhedra. Alongside of the sequence of analytic centers, another sequence of points is generated, based on convex combinations of the analytic centers. This latter sequence is observed to converge to a solution much faster than the former sequence.The second method, ACCPM-VI (quadratic cuts), has cuts based on both mapping evaluations and Jacobian evaluations. The use of such a richer information set allows cuts that guide more accurately the sequence of analytic centers towards a solution. Mappings are assumed to be strongly monotone. However, Jacobian approximations, relying only on mapping evaluations, are observed to work very well in practice, so that differentiability of the mappings may not be required. There are two versions of the ACCPM-VI (quadratic cuts), that differ in the way a new analytic center is reached after the introduction of a cut. One version uses a curvilinear search followed by dual Newton centering steps. The search entails a full eigenvector-eigenvalue decomposition of a dense matrix of the order of the number of variables. The other version uses two line searches, primal-dual Newton steps, but no eigenvector-eigenvalue decomposition.The algorithms described in this thesis were implemented in the M ATLAB environment. Numerical tests were performed on a variety of problems, some new and some traditional applications of variational inequalities