Fixed point equation reformulation via the NI function of the GNE problem.
GNE.fpeq(init, dimx, obj, argobj, grobj, arggrobj,
heobj, argheobj, joint, argjoint, jacjoint, argjacjoint,
method = "default", problem = c("NIR", "VIR"),
merit = c("NI", "VI", "FP"), order.method=1, control.outer=list(),
control.inner=list(), silent=TRUE, param=list(), stepfunc, argstep, ...)A list with components:
parThe best set of parameters found.
valueThe value of the merit function.
outer.countsA two-element integer vector giving the number of calls to fixed-point and merit functions respectively.
outer.iterThe outer iteration number.
codeThe values returned are
1Function criterion is near zero. Convergence of function values has been achieved.
4Iteration limit maxit exceeded.
100an error in the execution.
inner.iterThe iteration number when computing the fixed-point function.
inner.countsA two-element integer vector giving the number of calls to the gap function and its gradient when computing the fixed-point function.
messagea string describing the termination code
Initial values for the parameters to be optimized over: \(z=(x, lambda, mu)\).
a vector of dimension for \(x\).
objective function (to be minimized), see details.
a list of additional arguments.
gradient of the objective function, see details.
a list of additional arguments of the objective gradient.
Hessian of the objective function, see details.
a list of additional arguments of the objective Hessian.
joint function (\(h(x)<=0\)), see details.
a list of additional arguments of the joint function.
Jacobian of the joint function, see details.
a list of additional arguments of the Jacobian.
either "pure", "UR", "vH", "RRE", "MPE",
"SqRRE" or "SqMPE" method, see details. "default"
corresponds to "MPE".
either "NIR", "VIP", see details.
either "NI", "VI", "FP", see details.
the order of the extrapolation method.
a list with control parameters for the fixed point algorithm.
a list with control parameters for the fixed point function.
a logical to show some traces.
a list of parameters for the computation of the fixed point function.
the step function, only needed when method="UR".
additional arguments for the step function.
further arguments to be passed to the optimization routine. NOT to the functions.
Christophe Dutang
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 fixed point approach consists in solving equation \(y(x)=x\).
It simply consists in iterations \(x_{n+1} = y(x_n)\).
The next iterate is computed as $$x_{n+1} = (1-\alpha_n) x_n + \alpha_n y(x_n).$$
The step \(\alpha_n\) can be computed in different ways: constant, decreasing
serie or a line search method. In the literature of game theory, the decreasing serie
refers to the method of Ursayev and Rubinstein (method="UR") while the line search
method refers to the method of von Heusinger (method="vH"). Note that the constant
step can be done using the UR method.
Reduced Rank Extrapolation and Minimal Polynomial Extrapolation
methods are polynomial extrapolation methods, where the monomials are functional
``powers'' of the y function, i.e. function composition of y. Of order 1, RRE and MPE
consists of $$x_{n+1} = x_n + t_n (y(x_n) - x_n),$$
where \(t_n\) equals to
\(<v_n, r_n> / <v_n, v_n>\) for RRE1 and \(<r_n, r_n> / <v_n, r_n>\) for MPE1, where
\(r_n =y(x_n) - x_n \) and \(v_n = y(y(x_n)) - 2y(x_n) + x_n\).
To use RRE/MPE methods, set method = "RRE" or method = "MPE".
It consists in using an extrapolation method (such as RRE and MPE)
after two iteration of the linear extrapolation, i.e.
$$x_{n+1} = x_n -2 t_n r_n + t_n^2 v_n.$$ The squared version of RRE/MPE methods are
available via setting method = "SqRRE" or method = "SqMPE".
Not implemented.
For details on fixed point methods, see Varadhan & Roland (2004).
The control.outer argument is a list that can supply any of the following components:
merit="FP" and method="pure"see fpiter.
the default parameters are list(tol=1e-6, maxiter=100, trace=TRUE).
merit="FP" and method!="pure"see squarem.
the default parameters are list(tol=1e-6, maxiter=100, trace=TRUE).
merit!="FP"parameters are
tolThe absolute convergence tolerance. Default to 1e-6.
maxitThe maximum number of iterations. Default to 100.
echoA logical or an integer (0, 1, 2, 3) to print traces.
Default to FALSE, i.e. 0.
sigma, betaparameters for von Heusinger algorithm. Default to 9/10 and 1/2 respectively.
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 .
S. Uryasev and R.Y. Rubinstein (1994), On relaxation algorithms in computation of noncooperative equilibria, IEEE Transactions on Automatic Control.
R. Varadhan and C. Roland (2004), Squared Extrapolation Methods (SQUAREM): A New Class of Simple and Efficient Numerical Schemes for Accelerating the Convergence of the EM Algorithm, Johns Hopkins University, Dept. of Biostatistics Working Papers.
See GNE.ceq, GNE.minpb and GNE.nseq
for other approaches.