# 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

Solver | Description | Reference |
---|---|---|

`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 Adaptive | Fält, Giselsson (2017) |

`FISTA(α=1.0; kwargs...)` | FISTA | Beck, Teboulle (2009) |

`Dykstra(; kwargs...)` | Dykstra | Boyle, Dykstra (1986) |

`GAPP(α=0.8, α1=1.8, α2=1.8; iproj=100; kwargs...)` | Projected GAP | Fält, Giselsson (2016) |

## Keyword Arguments

All solvers accept for the following keyword arguments:

Argument | Default | Description (Values) |
---|---|---|

`max_iters` | `10000` | Maximum number of iterations |

`verbose` | `1` | Print verbosity level `0,1` |

`debug` | `1` | Level of debug data to save `0,1,2` |

`eps` | `1e-5` | Accuracy of solution |

`checki` | `100` | Interval 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:

Name | Debug Level Required | Description |
---|---|---|

`:p` | 1 | Relative Primal Residual |

`:d` | 1 | Relative Dual Residual |

`:g` | 1 | Relative Duality Gap |

`:ctx` | 1 | `cᵀx` |

`:bty` | 1 | `bᵀy` |

`:κ` | 1 | `κ` |

`:τ` | 1 | `τ` |

`:x` | 2 | `x` |

`:y` | 2 | `y` |

`:s` | 2 | `s` |

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