R: Non smooth equation reformulation of the GNE problem.

GNE.minpb {GNE}

R Documentation

Non smooth equation reformulation of the GNE problem.

Description

Non smooth equation reformulation via the extended KKT system of the GNE problem.

Usage

GNE.minpb(init, dimx, obj, argobj, grobj, arggrobj, 
	heobj, argheobj, joint, argjoint, jacjoint, argjacjoint, 
	method="default", problem = c("NIR", "VIR"), control.outer=list(), 
	control.inner=list(), silent=TRUE, param=list(), 
	optim.type=c("free","constr"), ...)

Arguments

`init`	Initial values for the parameters to be optimized over: `z=(x, lambda, mu)`.
`dimx`	a vector of dimension for `x`.
`obj`	objective function (to be minimized), see details.
`argobj`	a list of additional arguments.
`grobj`	gradient of the objective function, see details.
`arggrobj`	a list of additional arguments of the objective gradient.
`heobj`	Hessian of the objective function, see details.
`argheobj`	a list of additional arguments of the objective Hessian.
`joint`	joint function (`h(x)<=0`), see details.
`argjoint`	a list of additional arguments of the joint function.
`jacjoint`	Jacobian of the joint function, see details.
`argjacjoint`	a list of additional arguments of the Jacobian.
`method`	either `"BB"`, `"CG"` or `"BFGS"`, see details.
`problem`	either `"NIR"`, `"VIP"`, see details.
`optim.type`	either `"free"`, `"constr"`, see details.
`control.outer`	a list with control parameters for the minimization algorithm.
`control.inner`	a list with control parameters for the minimization function.
`...`	further arguments to be passed to the optimization routine. NOT to the functions `phi` and `jacphi`.
`silent`	a logical to show some traces.
`param`	a list of parameters for the computation of the minimization function.

Details

Functions in argument must respect the following template:

obj must have arguments the current iterate z, the player number i and optionnally additional arguments given in a list.
grobj must have arguments the current iterate z, the player number i, the derivative index j and optionnally additional arguments given in a list.
heobj must have arguments the current iterate z, the player number i, the derivative indexes j, k and optionnally additional arguments given in a list.
joint must have arguments the current iterate z and optionnally additional arguments given in a list.
jacjoint must have arguments the current iterate z, the derivative index j and optionnally additional arguments given in a list.

The gap function minimization consists in minimizing a gap function min V(x). The function minGap provides two optimization methods to solve this minimization problem.

Barzilai-Borwein algorithm: when method = "BB", we use Barzilai-Borwein iterative scheme to find the minimum.
Conjugate gradient algorithm: when method = "CG", we use the CG iterative scheme implemented in R, an Hessian-free method.
Broyden-Fletcher-Goldfarb-Shanno algorithm: when method = "BFGS", we use the BFGS iterative scheme implemented in R, a quasi-Newton method with line search.

In the game theory literature, there are two main gap functions: the regularized Nikaido-Isoda (NI) function and the regularized QVI gap function. This correspond to type="NI" and type="VI", respectively. See von Heusinger & Kanzow (2009) for details on the NI function and Kubota & Fukushima (2009) for the QVI regularized gap function.

The control.outer argument is a list that can supply any of the following components:

tol: The absolute convergence tolerance. Default to 1e-6.
maxit: The maximum number of iterations. Default to 100.
echo: A logical or an integer (0, 1, 2, 3) to print traces. Default to FALSE, i.e. 0.
stepinit: Initial step size for the BB method (should be small if gradient is “big”). Default to 1.

Note that the Gap function can return a numeric or a list with computation details. In the latter case, the object return must be a list with the following components value, counts, iter, see the example below.

Value

A list with components:

par

The best set of parameters found.

value

The value of the merit function.

outer.counts

A two-element integer vector giving the number of calls to Gap and gradGap respectively.

outer.iter

The outer iteration number.

code

The values returned are

1: Function criterion is near zero. Convergence of function values has been achieved.
2: x-values within tolerance. This means that the relative distance between two consecutive x-values is smaller than xtol.
3: No better point found. This means that the algorithm has stalled and cannot find an acceptable new point. This may or may not indicate acceptably small function values.
4: Iteration limit maxit exceeded.
5: Jacobian is too ill-conditioned.
6: Jacobian is singular.
100: an error in the execution.

inner.iter

The iteration number when computing the minimization function.

inner.counts

A two-element integer vector giving the number of calls to the gap function and its gradient when computing the minimization function.

message

a string describing the termination code

Author(s)

Christophe Dutang

References

A. von Heusinger (2009), Numerical Methods for the Solution of the Generalized Nash Equilibrium Problem, Ph. D. Thesis.

A. von Heusinger and C. Kanzow (2009), Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions, Comput Optim Appl .

K. Kubota and M. Fukushima (2009), Gap function approach to the generalized Nash Equilibrium problem, Journal of Optimization theory and applications.