NExOS.jl
Installation • Usage • Tutorials • Citing • Contact
NExOS.jl
is a Julia
package that implements the Nonconvex Exteriorpoint Optimization Solver (NExOS). The package is tailored for minimizing a convex cost function over a nonconvex constraint set.
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 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, μ_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 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 nonconvex set such that projection around local minima is singlevalued, 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 Optimization 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