BQN: Broyden's quasi Newton acceleration scheme for fast...

In medhaaga/quasiNewtonMM: Quasi-Newton acceleration scheme for MM algorithms

Broyden's quasi Newton acceleration scheme for fast convergence of MM algorithm

Description

Acceleration method for fixed point iteration scheme - like majorization-minimization (MM). The algorithm uses the classical Broyden's root finding method and differes in the way secants are approximated (using MM algorithm map).

Usage

BQN(par, fixptfn, objfn, ..., control = list())

Arguments

par	A vector of parameters denoting the starting value for the fixed-point iteration.
fixptfn	A function $F$ that denotes the fixed-point MM algorithm map. It accepts the current parameter vector $x1$ of length $p$ and returns the update $x2 = F(x1)$ of same length such that the objective is smaller at $x2$ in majorization-minimization (and vice versa in minimization-majorization).
objfn	This is the objective function $L$ that MM algorithm tries to minimize. It takes a vector of parameters as input and returns a scalar that needs to be minimized. It attains its local minimum at the fixed point of the MM algorithm map $F$. Note: in case of maximization problem like maximizing the log-likelihood, this function should be the negative log-likelihood to be minimized.
control	A list of control parameters specifing any changes to default values of algorithm control parameters. Full names of control list elements must be specified, otherwise, user-specifications are ignored. See *Details*.
...	Arguments passed to fixptfn and objfn.

Details

These control parameters can be specified by the user, otherwise default values are used.

qn

An integer indicating the number of secant approximations that the quasi-Newton method should satisfy. Note that qn < p. Default is 1.

objfn.inc

A non-negative scalar that dictates the degree of non-montonicity. Default is 1. Set objfn.inc = 0 to obtain monotone convergence. Setting objfn.inc = Inf gives a non-monotone scheme. In-between values result in partially-monotone convergence.

tol

A small, positive scalar that determines when iterations should be terminated. Iteration is terminated when abs(x[k] - F(x[k])) <= tol. Default is 1.e-07.

maxiter

An integer denoting the maximum limit on the number of evaluations of fixptfn, F. Default is 1500.

obj.stop

A logical variable indicating whether the iterations should be terminated when the decrease in value of objective function is below a defined threshold. Default is FALSE.

obj.tol

When obj.stop==TRUE. A small, positive scalar that determines when iterations should be terminated. Iteration is terminated when abs(L(x2) - L(x1)) <= obj.tol. Default is 1.e-07.

step.max

A scalar that determines the maximum step length at each iteration. Default is 1000.

step.min

A scalar that determines the minimum step length at each iteration. Default is 1.

verbose

A logical variable denoting whether some of the intermediate results of iterations should be displayed to the user. Default is FALSE.

intermed

A logical variable denoting whether the intermediate results of iterations should be returned. If set to TRUE, the function will return a matrix where each row corresponds to parameters at each iteration, along with the corresponding log-likelihood value. This option is inactive when objfn is not specified. Default is FALSE.

Value

A list with the following components:

par	Parameter, x* that is the fixed-point of F such that x* = F(x*), if convergence is successful.
value.objfn	The value of the objective function $L$ at termination.
fpevals	Number of times the fixed-point function fixptfn was evaluated.
objfevals	Number of times the objective function objfn was evaluated.
convergence	An integer code indicating type of convergence. 0 indicates successful convergence, whereas 1 denotes failure to converge.
p.inter	A matrix where each row corresponds to parameters at each iteration, along with the corresponding log-likelihood value. This object is returned only when the control parameter intermed is set to TRUE.

References

Agarwal, M and Xu, J (2020+) Quasi-Newton acceleration of MM algorithm using Broyden's method, arxiv

See Also

LBQN which performs the limited memory BQN acceleration scheme.

Examples

##---- Should be DIRECTLY executable !! ----
##-- ==>  Define data, use random,
##--	or do  help(data=index)  for the standard data sets.


fixptfn <- function(x) x + sin(x)  ## Fixed-point iteration
objfn <- function(x) cos(x)        ## Objective function to be minimized

par <- (pi/2)-.1                   ## Starting point
fp <- BQN(par, fixptfn = fixptfn, objfn = objfn, control = list(qn=1))

medhaaga/quasiNewtonMM documentation built on Aug. 11, 2022, 11:02 p.m.