GeNIOS.jl

GeNIOS is an efficient large-scale operator splitting solver for convex optimization problems.

Documentation Contents:

Examples:

Advanced Usage:

Overview

GeNIOS solves convex optimization problems of the form

\[\begin{array}{ll} \text{minimize} & f(x) + g(z) \\ \text{subject to} & Mx + z = c, \end{array}\]

where $x \in \mathbb{R}^n$ and $z \in \mathbb{R}^m$ are the optimization variables. The function $f$ is assumed to be smooth, with known first and second derivatives, and the function $g$ must have a known proximal operator.

Compared to conic form programs, the form we use in GeNIOS facilitates custom subroutines that often provide significant speedups. To ameliorate the extra complexity, we provide a few interfaces that take advantage of special problem structure.

Interfaces

QP interface

Many important problems in machine learning, finance, operations research, and control can be formulated as QPs. Examples include

  • Lasso regression
  • Portfolio optimization
  • Trajectory optimization
  • Model predictive control
  • And many more...

GeNIOS accepts QPs of the form

\[\begin{array}{ll} \text{minimize} & (1/2)x^TPx + q^Tx \\ \text{subject to} & l \leq Mx \leq u, \end{array}\]

which can be constructed using

solver = GeNIOS.QPSolver(P, q, M, l, u)

ML interface

In machine learning problems, we can take advantage of additional structure. In our MLSolver, we assume the problem is of the form

\[\begin{array}{ll} \text{minimize} & \sum_{i=1}^m f(a_i^Tx - b_i) + (1/2)\lambda_2\|x\|_2^2 + \lambda_1\|x\|_1, \end{array}\]

where $f$ is the per-sample loss function. Let $A$ be a matrix with rows $a_i$ and $b$ be a vector with entries $b_i$. The MLSolver is constructed via

solver = GeNIOS.MLSolver(f, df, d2f, λ1, λ2, A, b)

where df, and d2f are scalar functions giving the first and second derivative of $f$ respectively.

In the future, we may extend this interface to allow constraints on $x$, but for now, you can use the generic interface to specify constraints in machine learning problems with non-quadratic objective functions.

Generic interface

For power users, we expose a fully generic interface for the problem

\[\begin{array}{ll} \text{minimize} & f(x) + g(z) \\ \text{subject to} & Mx + z = c. \end{array}\]

Users must specify $f$, $\nabla f$, $\nabla^2 f$ (via a HessianOperator), $g$, the proximal operator of $g$, $M$, and $c$. We provide full details of these functions in the User Guide. Also checkout the Lasso example to see a problem written in all three ways.

Algorithm

GeNIOS follows a similar approach to OSQP [1], solving the convex optimization problem using ADMM [2]. Note that the problem form of GeNIOS is, however, more general than conic form solvers. The key algorithmic differences lies in the $x$-subproblem of ADMM. Instead of solving this problem exactly, GeNIOS solves a quadratic approximation to this problem. Recent work [3] shows that this approximation does not harm ADMM's convergence rate. The subproblem is then solved via the iterative conjugate gradient method with a randomized preconditioner [4]. GeNIOS also incorporates several other heuristics from the literature. Please see our paper for additional details.

Getting Started

The JuMP interface is the easiest way to use GeNIOS. A simple Markowitz portfolio example is below.

using JuMP, GeNIOS
# TODO:

However, the native interfaces can be called directly by specifying the problem data. Using the QPSolver, is it written as

# TODO:

And, finally, using the fully general interface, it is written as

# TODO:

Please see the User Guide for a full explanation of the solver parameter options. Check out the examples as well.

References