## NExOS.jl

Nonconvex Exterior Point Operator Splitting
Author Shuvomoy
Popularity
7 Stars
Updated Last
2 Years Ago
Started In
November 2020

# `NExOS.jl` `NExOS.jl` is a `Julia` package that implements Nonconvex Exterior-point 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 single-valued around points of interest. These types of sets are called prox-regular sets, e.g., sets containing low-rank 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 prox-regular 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 = 1e-8, μ_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 prox-regular 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 prox-regular 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={Exterior-point 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}
}
``````

## 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 🚀!

### Required Packages

View all packages

### Used By Packages

No packages found.