# FirstOrderSolvers

Package for large scale convex optimization solvers in julia. This package is intended to allow for easy implementation, testing, and running of solvers through the Convex.jl interface. The package is currently under active development and uses the ProximalOperators.jl package to do the low level projections.

## Installation

To run the solvers you need to have the following packages

Pkg.add("Convex")
Pkg.clone("https://github.com/mfalt/FirstOrderSolvers.jl.git")


## Usage

Define an optimization problem in the format supported by Convex.jl, and supply the desired solver to the solve! function. Exaple using DR for feasibility problems with the GAP solver

using Convex, FirstOrderSolvers
m = 40;  n = 50
A = randn(m, n); b = randn(m, 1)
x = Variable(n)
problem = minimize(sumsquares(A * x - b), [x >= 0])

solve!(problem, GAP(0.5, 2.0, 2.0, max_iters=2000))


## Solvers

Currently, the available solvers are

SolverDescriptionReference
GAP(α=0.8, α1=1.8, α2=1.8; kwargs...)Generalized Alternating Projections
DR(α=0.5; kwargs...)Douglas-Rachford (GAP(α, 2.0, 2.0))Douglas, Rachford (1956)
AP(α=0.5; kwargs...)Alternating Projections (GAP(α, 1.0, 1.0))Agmon (1954), Bregman (1967)
GAPA(α=1.0; kwargs...)GAP AdaptiveFält, Giselsson (2017)
FISTA(α=1.0; kwargs...)FISTABeck, Teboulle (2009)
Dykstra(; kwargs...)DykstraBoyle, Dykstra (1986)
GAPP(α=0.8, α1=1.8, α2=1.8; iproj=100; kwargs...)Projected GAPFält, Giselsson (2016)

## Keyword Arguments

All solvers accept for the following keyword arguments:

ArgumentDefaultDescription (Values)
max_iters10000Maximum number of iterations
verbose1Print verbosity level 0,1
debug1Level of debug data to save 0,1,2
eps1e-5Accuracy of solution
checki100Interval for checking convergence

## Debugging

If the keyword argument debug is set to 1 or 2 the following values will be stored in a ValueHistories.MVHistory in problem.model.history, for each iteration the convergence check is run:

NameDebug Level RequiredDescription
:p1Relative Primal Residual
:d1Relative Dual Residual
:g1Relative Duality Gap
:ctx1cᵀx
:bty1bᵀy
:κ1κ
:τ1τ
:x2x
:y2y
:s2s

These values correspond to the values in the paper Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding (O'Donoghue et.al).