NExOS.jl
Installation • Usage • Tutorials • Citing • Contact
NExOS.jl
is a Julia
package that implements Nonconvex Exteriorpoint Operator Splitting algorithm (NExOS). The package is tailored for minimizing a convex cost function over a nonconvex constraint set, where projection onto the constraint set is singlevalued around points of interest. These types of sets are called proxregular sets, e.g., sets containing lowrank and sparsity constraints.
NExOS.jl
considers nonconvex optimization problems of the following form:
minimize f(x)+(β/2)‖x‖^2
subject to x ∈ X,
where the decision variable x
can be a vector in ℜ^d
or a matrix in ℜ^(m×d)
or a combination of both. The cost function f
is convex, β
is a positive parameter (can be arbitrarily small), and the constraint set X
is a nonconvex proxregular set (please see Acceptable functions and sets for more details).
Installation
In Julia REPL
, type
] add NExOS
Usage
Below is a short usage example on using NExOS.jl
for sparse regression problem (for other examples, please see Tutorials).
# Load the packages
using Random, NExOS, ProximalOperators
# Random data generation
m = 25
n = 50
A = randn(m,n)
b = randn(m)
M = 100
k = convert(Int64, round(m/3))
beta = 10^10
# Create the problem instance in NExOS
C = SparseSet(M, k) # Create the set
f = LeastSquares(A, b, iterative = true) # Create the function
settings = Settings(μ_max = 2, μ_min = 1e8, μ_mult_fact = 0.85, verbose = false, freq = 250, γ_updt_rule = :adaptive, β = beta) # settings
z0 = zeros(n) # create an initial point
problem = Problem(f, C, settings.β, z0) # problem instance
# Solve the problem
state_final = solve!(problem, settings)
# Extract solution info
x_NExOS = state_final.x # solution found by NExOS
p_star = f(x_NExOS) # objective value
Acceptable functions and sets
f
Objective function NExOS.jl
allows for any f
that is convex. We can classify them into two types:

The function
f
is an unconstrained convex function with an easytocompute proximal operator. To compute the proximal operators for this category of functions,NExOS.jl
uses the packageProximalOperators.jl
. The list of available functions for this type is available at this link. 
The function
f
is a constrained convex function (i.e., a convex function over some convex constraint set). For such a function, no closed form solution usually exists, and in this situationNExOS
computes the proximal operator off
by solving a convex optimization problem usingJuMP
and any of the solvers supported by it (listed here). To know more about how to compute such proximal operators, please see this blog post I wrote.
X
Constraint set The constraint set X
is nonconvex, but it can be decomposed into a convex compact set C
and a nonconvex proxregular set N
, i.e., X = C ⋂ N
. For example:
 Sparse set.
N = {x ∈ ℜ^d ∣ card(x) ≦ k}
, wherecard(x)
denotes the number of nonzero components inx
,  Lowrank set.
N = { X ∈ ℜ^(m×d) ∣ rank(X) ≦ r}
, whererank(X)
denotes the rank of the matrixX
,  Combination of lowrank and sparse set.
N = {X ∈ ℜ^(m×d), x ∈ ℜ^d ∣ card(x) ≦ k, rank(X) ≦ r}
,  Any other proxregular set.
N
can be any other proxregular sets, e.g., weakly convex sets, proximally smooth sets, etc.
Tutorials
Please see the following jupyter notebook
tutorials that describe in more detail how to use NExOS.jl
.
Citing
If you find NExOS.jl
useful in your project, we kindly request that you cite the following paper:
@article{NExOS,
title={Exteriorpoint Operator Splitting for Nonconvex Learning},
author={Das Gupta, Shuvomoy and Stellato, Bartolomeo and Van Parys, Bart P.G.},
journal={arXiv preprint arXiv:2011.04552},
note={\url{https://arxiv.org/pdf/2011.04552.pdf}},
year={2020}
}
A preprint can be downloaded here.
Reporting issues
Please report any issues via the Github issue tracker. All types of issues are welcome including bug reports, feature requests, implementation for a specific research problem and so on.
Contact
Send an email