NExOS.jl

Installation • Usage • Tutorials • Citing • Contact

NExOS.jl is a Julia package that implements the Nonconvex Exterior-point 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

Objective function f

NExOS.jl allows for any f that is convex. We can classify them into two types:

1. The function f is an unconstrained convex function with an easy-to-compute proximal operator. To compute the proximal operators for this category of functions, NExOS.jl uses the package ProximalOperators.jl. The list of available functions for this type is available at this link.

2. 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 situation NExOS computes the proximal operator of f by solving a convex optimization problem using JuMP 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.

Constraint set X

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:

1. Sparse set. N = {x ∈ ℜ^d ∣ card(x) ≦ k}, where card(x) denotes the number of nonzero components in x,
2. Low-rank set. N = { X ∈ ℜ^(m×d) ∣ rank(X) ≦ r}, where rank(X) denotes the rank of the matrix X,
3. Combination of low-rank and sparse set. N = {X ∈ ℜ^(m×d), x ∈ ℜ^d ∣ card(x) ≦ k, rank(X) ≦ r},
4. Any other prox-regular set. N can be any other nonconvex set such that projection around local minima is single-valued, 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.

1. Affine rank minimization.
2. Matrix completion.
3. Sparse regression.
4. Low-rank factor analysis.

Citing

If you find NExOS.jl useful in your project, we kindly request that you cite the following paper:

@article{dasgupta2023NExOS,
  title={Exterior-point Optimization for Sparse and Low-rank Optimization},
  author={Das Gupta, Shuvomoy and Stellato, Bartolomeo and Van Parys, Bart P.G.},
  journal={Journal of Optimization Theory and Applications},
  note={\url{https://arxiv.org/pdf/2011.04552.pdf}},
  year={2024}
  publisher={Springer}
}

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 📧 to sdgupta@mit.edu 🚀!