Skip to content

Latest commit

 

History

History
65 lines (44 loc) · 4.38 KB

README.md

File metadata and controls

65 lines (44 loc) · 4.38 KB
Raw

NExOS.jl

Build Status

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.

Installation/Usage

In Julia REPL, type

] add https://github.com/Shuvomoy/NExOS.jl

Examples

Please see the following jupyter notebook tutorials that describe how to use NExOS.jl.

  1. Affine rank minimization.
  2. Matrix completion.
  3. Sparse regression.

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 this proximal operator computation process, 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.

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={Optimization Online Preprint},
  note={\url{http://www.optimization-online.org/DB_FILE/2020/11/8099.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, documentation typos, feature requests and so on.

Contact

Send an email 📧 to Shuvomoy Das Gupta 🚀!