SLimOptim.jl documentation

linesearch(ls, sol, d, f, g!, fg!, t, funRef, gtd, gvec)

Line search interface to LineSearches.jl

Arguments

• ls: Line search structure (see LineSearches.jl documentation)
• f: Objective function, x -> f(x)
• g!`: Gradient in place function, x-> (g.= gradient(x))
• fg!`: Objective and in place gradient function, x-> (f = f(x); g.= gradient(x))
• t: Initial steplength gess
• funRef: Reference objective function value
• gtd: Reference direction inner product dot(g0, d0)
• gvec: prealocated array for thhe gradient

spg(funObj, x, funProj, options; ls=nothing, callback=nothing)

Function for using Spectral Projected Gradient to solve problems of the form min funObj(x) s.t. x in C

Arguments

• funObj(x):function to minimize (returns gradient as second argument)
• funProj(x): function that returns projection of x onto C
• x: Initial guess
• options: spg_options structure

Optional Arguments

• ls `: User provided linesearch function
• callback : Callback function. Must take as input a result callback(x::result)

Notes:

• if the projection is expensive to compute, you can reduce the number of projections by setting testOpt to 0 in the options

• Adapted fromt he matlab implementation of minConf_SPG

spg(f, g!, fg!, x, funProj, options; ls=nothing, callback=nothing)

Function for using Spectral Projected Gradient to solve problems of the form min funObj(x) s.t. x in C

Arguments

• f(x): function to minimize (returns objective only)
• g!(g, x): gradient of function (in place)
• fg!(g, x): objective and gradient (in place)
• funProj(x): function that returns projection of x onto C
• x: Initial guess
• options: spg_options structure

Optional Arguments

• ls `: User provided linesearch function
• callback : Callback function. Must take as input a result callback(x::result)

Notes:

• if the projection is expensive to compute, you can reduce the number of projections by setting testOpt to 0 in the options

• Adapted fromt he matlab implementation of minConf_SPG

spg_options(;verbose=3,optTol=1f-5,progTol=1f-7,
            maxIter=20,suffDec=1f-4,memory=2,
            useSpectral=true,curvilinear=false,
            feasibleInit=false,testOpt=true,
            bbType=true,testInit=false, store_trace=false,
            optNorm=Inf,iniStep=1f0, maxLinesearchIter=10)

Options structure for Spectral Project Gradient algorithm.

Arguments

• verbose: level of verbosity (0: no output, 1: iter (default))
• optTol: tolerance used to check for optimality (default: 1e-5)
• progTol: tolerance used to check for lack of progress (default: 1e-9)
• maxIter: maximum number of iterations (default: 20)
• suffDec: sufficient decrease parameter in Armijo condition (default: 1e-4)
• memory: number of steps to look back in non-monotone Armijo condition
• useSpectral: use spectral scaling of gradient direction (default: 1)
• curvilinear: backtrack along projection Arc (default: 0)
• testOpt: test optimality condition (default: 1)
• feasibleInit: if 1, then the initial point is assumed to be feasible
• bbType: type of Barzilai Borwein step (default: 1)
• testInit: Whether to test the initial estimate for optimality (default: false)
• store_trace: Whether to store the trace/history of x (default: false)
• optNorm: First-Order Optimality Conditions norm (default: Inf)
• iniStep: Initial step length estimate (default: 1)
• maxLinesearchIter: Maximum number of line search iteration (default: 20)

pqn(objective, x, projection, options; ls=nothing, callback=nothing)

Function for using a limited-memory projected quasi-Newton to solve problems of the form min objective(x) s.t. x in C

The projected quasi-Newton sub-problems are solved the spectral projected gradient algorithm

Arguments

• funObj(x): function to minimize (returns gradient as second argument)
• funProj(x): function that returns projection of x onto C
• x: Initial guess
• options: pqn_options structure

Optional Arguments

• ls `: User provided linesearch function
• callback : Callback function. Must take as input a result callback(x::result)

Notes:

Adapted fromt he matlab implementation of minConf_PQN

pqn(f, g!, fg!, x, projection, options; ls=nothing, callback=nothing)

Function for using a limited-memory projected quasi-Newton to solve problems of the form min objective(x) s.t. x in C

The projected quasi-Newton sub-problems are solved the spectral projected gradient algorithm.

Arguments

• f(x): function to minimize (returns objective only)
• g!(g, x): gradient of function (in place)
• fg!(g, x): objective and gradient (in place)
• funProj(x): function that returns projection of x onto C
• x: Initial guess
• options: pqn_options structure

Optional Arguments

• ls `: User provided linesearch function
• callback : Callback function. Must take as input a result callback(x::result)

Notes:

Adapted fromt he matlab implementation of minConf_PQN

pqn_options(;verbose=2, optTol=1f-5, progTol=1f-7,
            maxIter=20, suffDec=1f-4, corrections=10, adjustStep=false,
            bbInit=false, store_trace=false, SPGoptTol=1f-6, SPGprogTol=1f-7,
            SPGiters=10, SPGtestOpt=false, maxLinesearchIter=20)

Options structure for Spectral Project Gradient algorithm.

Arguments

• verbose: level of verbosity (0: no output, 1: iter (default))
• optTol: tolerance used to check for optimality (default: 1e-5)
• progTol: tolerance used to check for progress (default: 1e-9)
• maxIter: maximum number of iterations (default: 20)
• suffDec: sufficient decrease parameter in Armijo condition (default: 1e-4)
• corrections: number of lbfgs corrections to store (default: 10)
• adjustStep: use quadratic initialization of line search (default: 0)
• bbInit: initialize sub-problem with Barzilai-Borwein step (default: 1)
• store_trace: Whether to store the trace/history of x (default: false)
• SPGoptTol: optimality tolerance for SPG direction finding (default: 1e-6)
• SPGprogTol: SPG tolerance used to check for progress (default: 1e-7)
• SPGiters: maximum number of iterations for SPG direction finding (default:10)
• SPGtestOpt: Whether to check for optimality in SPG (default: false)
• maxLinesearchIter: Maximum number of line search iteration (default: 20)
• memory: Number of steps for the non-monotone functional decrease condition.
• iniStep: Initial step length estimate (default: 1). Ignored with adjustStep.

bregman_options(;verbose=1, optTol=1e-6, progTol=1e-8, maxIter=20,
                store_trace=false, quantile=.5, alpha=.25, spg=false)

Options structure for the bregman iteration algorithm

Arguments

• verbose: level of verbosity (0: no output, 1: final, 2: iter (default), 3: debug)
• progTol: tolerance used to check for lack of progress (default: 1e-9)
• maxIter: maximum number of iterations (default: 20)
• store_trace: Whether to store the trace/history of x (default: false)
• antichatter: Whether to use anti-chatter step length correction
• alpha: Strong convexity modulus. (step length is $α \frac{||r||_2^2}{||g||_2^2}$)
• spg: whether to use spg, default is false
• TD: sparsifying transform (e.g. curvelet), default is identity (LinearAlgebra.I)
• λfunc: a function to calculate threshold value, default is nothing
• λ: a pre-set threshold, will only be used if λfunc is not defined, default is nothing
• quantile: a percentage to calculate the threshold by quantile of the dual variable in 1st iteration, will only be used if neither λfunc nor λ are defined, default is .95 i.e thresholds 95% of the vector
• w: a weight vector that is applied on the threshold element-wise according to relaxation of weighted l1, default is 1 (no weighting)
• reset_lambda: How often should lambda be updated. Defaults to nothing i.e lambda is nerver updated and estimated at the first iteration.

bregman(A, x, b, options)

Linearized bregman iteration for the system

$\frac{1}{2} ||TD \ x||_2^2 + λ ||TD \ x||_{1,w} \ \ \ s.t Ax = b$

For example, for sparsity promoting denoising (i.e LSRTM)

Required arguments

• A: Forward operator (e.g. J or preconditioned J for LSRTM)
• x: Initial guess
• b: observed data

Optional Arguments

• callback : Callback function. Must take as input a result callback(x::result)

Non-required arguments

• options: bregman options, default is bregman_options(); options.TD provides the sparsifying transform (e.g. curvelet), options.w provides the weight vector for the weighted l1

bregman(funobj, x, options)

Linearized bregman iteration for the system

$\frac{1}{2} ||TD \ x||_2^2 + λ ||TD \ x||_{1,w} \ \ \ s.t Ax = b$

Required arguments

• funobj: a function that calculates the objective value (0.5 * norm(Ax-b)^2) and the gradient (A'(Ax-b))
• x: Initial guess

Optional Arguments

• callback : Callback function. Must take as input a result callback(x::result)

Non-required arguments

• options: bregman options, default is bregman_options(); options.TD provides the sparsifying transform (e.g. curvelet), options.w provides the weight vector for the weighted l1