Relay or box-constrained AVI problems

The problem:

Find \((z,w)\) such that:

\[\begin{split}\begin{equation*} \left\lbrace \begin{array}{l} w = M z + q\\ -w \in \mathcal{N}_{K}(z)\\ \end{array}, \right. \end{equation*}\end{split}\]

where M is an ( :math:` n times n ` )-matrix, q, z and w are n-dimensional vectors, K is the box defined by \(K=\{x\in\mathbb{R}^n \mid lb_i \leq x_i \leq ub_i, i = 1, ..., n \}\) and \(\mathcal{N}_K(z)\) is the normal cone to \(K\) at \(z\) .

The solvers and their parameters are described in Relay Problems Solvers .

Available solvers:

The “direct” solvers are

  • relay_avi_caoferris() based on an algorithm by Cao and Ferris for AVI with a polytopic set \(K\) .
  • relay_path() using the PATH solver

Using an LCP reformulation (splitting z in positive and negative part), we have the following available solvers:

(see the functions/solvers list in Relay_Solvers.h )

Relay Problems Solvers:

This page gives an overview of the available solvers for relay problems and their required parameters.

This page gives an overview of the available solvers for relay problems and their required parameters.

For each solver, the input argument are:

  • a RelayProblem
  • the unknowns (z,w)
  • info, the termination value (0: convergence, >0 problem which depends on the solver)
  • a SolverOptions structure, which handles iparam and dparam

Enumerative solver:

The relay problem is reformulated as a LCP and solved with the enumerative solver

function: relay_enum()

parameters:

  • dparam[0] (in): tolerance
  • iparam[0] (in) : search for multiple solutions if 1
  • iparam[1] (out) : key of the solution
  • iparam[3] (in) : starting key values (seed)
  • iparam[4] (in) : use DGELS (1) or DGESV (0).

PATH solver:

The relay problem is reformulated as a LCP and solved with the PATH solver

function: relay_path()

  • dparam[0] (in): tolerance

Lemke solver:

The relay problem is reformulated as a LCP and solved with Lemke’s method

function: relay_lexicolemke()

parameters:

  • iparam[0] (in): maximum number of iterations allowed
  • iparam[1] (out): number of iterations processed

CaoFerris solver:

The relay problem is reformulated as an AVI and solved with the solver proposed by Cao and Ferris

function: relay_avi_caoferris()

parameters:

  • iparam[0] (in): maximum number of iterations allowed
  • iparam[1] (out): number of iterations processed