Affine Variational Inequalities (AVI)

Problem statement

The Affine Variational Inequality (AVI) is defined by

Given \(q\in\mathbb{R}^n\) , \(M\in\mathbb{R}^{n\times n}\) and a set \(K\in\mathbb{R}^n\) , find \(z\in\mathbb{R}^n\) such that:

\[\begin{equation*}(Mz+q)^T(y -z) \geq 0,\quad \text{ for all } y \in K,\end{equation*}\]

or equivalently,

\[\begin{equation*}-(Mz + q) \in \mathcal{N}_K(z)\end{equation*}\]

where \(\mathcal{N}_K\) is the normal cone to \(K\) at \(z\) .

The AVI is a special case of a Variational Inequality (VI), where the function \(F\) is affine. For VI solvers, see Variational Inequality (VI).

From more details on theory and analysis of AVI (and VI in general), we refer to [6]

Implementation in numerics

Structure to define the problem: AffineVariationalInequalities.

The generic driver for all VI is avi_driver().

solvers list AVI_SOLVER

AVI Available solvers

Cao Ferris (SICONOS_AVI_CAOFERRIS)

Direct solver for AVI based on pivoting method principle for degenerate problem. Choice of pivot variable is performed via lexicographic ordering

driver: avi_caoferris()

parameters:

  • iparam[SICONOS_IPARAM_MAX_ITER] = 10000

  • dparam[SICONOS_DPARAM_TOL] = 1e-12

Pathvi (SICONOS_AVI_PATHAVI)

Direct solver for VI based on pivoting method principle for degenerate problem.

Ref: “A structure-preserving Pivotal Method for Affine Variational Inequalities” Y. Kim, O. Huber, M.C. Ferris, Math Prog B (2017).

driver: avi_pathvi()

parameters:

  • iparam[SICONOS_IPARAM_MAX_ITER] = 10000

  • dparam[SICONOS_DPARAM_TOL] = 1e-12