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