Affine Variational Inequalities (AVI)

Problem:

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

Facchinei, Francisco; Pang, Jong-Shi (2003), Finite Dimensional Variational Inequalities and Complementarity Problems , Vol. 1 & 2, Springer Series in Operations Research, Berlin-Heidelberg-New York: Springer-Verlag.

Available solvers:

The solvers and their parameters are described in Affine Variational Inequalities Solvers .

Use the generic function AVI_driver() to call one the the specific solvers listed below:

  • avi_caoferris() , direct solver for AVI based on pivoting method principle for degenerate problem.

    Choice of pivot variable is performed via lexicographic ordering

(see also the functions/solvers list in AVI_Solvers.h and numbering in AVI_cst.h )

Affine Variational Inequalities Solvers:

Overview of the available solvers for AVI and their required parameters.

For each solver, the input argument are:

  • an AffineVariationalInequalities
  • the unknown z
  • the value of the function F(z)
  • info, the termination value (0: convergence, >0 problem which depends on the solver)
  • a SolverOptions struct, which contains iparam and dparam

The Cao-Ferris algorithm:

Direct solver for AVI based on pivoting method principle for (degenerated) problem.

function: avi_caoferris()

parameters:

  • iparam[0] (in): max. number of iterations
  • iparam[1] (in,out): boolean, 1 if memory has been allocated, 0 otherwise
  • iparam[1] (out): number of iterations processed