Projections onto the canonical simplex with additional linear inequalities

This repository is a complementary material to our paper "Projections onto the canonical simplex with additional linear inequalities", where we consider several such projections coming from the field of distributionally robust optimization (DRO).

For a brief presentation, see the Jupyter notebook.

Installation

This package can be installed using pkg REPL as follows

(v1.2) pkg> add https://github.com/VaclavMacha/Projections.git

Usage

This package provides an interface to solve the three following problems

1. distributionally robust optimization (DRO) with φ -divergence or norm in constraints. All implemented φ -divergences and norms are presented in the following table

Name	Constructor	Our solver	General solver	Philpott solver
Kullback-Leibler divergence	KullbackLeibler()	✔	Ipopt	✘
Burg entropy	Burg()	✔	Ipopt	✘
Hellinger distance	Hellinger()	✔	Ipopt	✘
χ2-distance	ChiSquare()	✔	Ipopt	✘
Modified χ2-distance	ModifiedChiSquare()	✔	Ipopt	✘
l-1 norm	Lone()	✔	CPLEX	✘
l-2 norm	Ltwo()	✔	CPLEX	✘
l-infinity norm	Linf()	✔	CPLEX	✔

2. finding projection onto probability simplex (Simplex).

The interface provides 3 solvers:

1. Our() - our approach
2. General() - general purpose solvers such as Ipopt or CPLEX
3. Philpott() - algorithm presented in [Philpott 2018] for the DRO with l-2 norm

DRO

The following example shows how to solve the DRO with Burg distance using Our() and General() solver

julia> using Projections, Random, LinearAlgebra                                                                                           
                                                                                                                                          
julia> Random.seed!(1234);                                                                                                                
                                                                                                                                       
julia> d  = Projections.Burg();                                                                                                           
                     
julia> q  = rand(10);                                                                                                                     
                     
julia> q ./= sum(q);                                                                                                                      
                                                  
julia> c  = rand(10);                                                                                                                     
                                                                                        
julia> ε  = 0.1;                                                                                                                          
                                                                                                      
julia> model  = Projections.DRO(d, q, c, ε);                                                                                              
                       
julia> p1 = Projections.solve(Our(), model);                                                                                            
                                                                                                                                          
julia> p2 = Projections.solve(General(), model);                                                                                          

julia> LinearAlgebra.norm(p1 - p2)                                                                                                        
7.848203730531935e-9

Simplex

The following example shows how to solve the Simplex problem using Our() and General() solver

julia> using Projections, Random, LinearAlgebra                                                                                      

julia> Random.seed!(1234);                                                                                                           

julia> n  = 10;                                                                                                                      

julia> q  = rand(n);                                                                                                                 

julia> lb = rand(n)./n;                                                                                                              

julia> ub = 1 .+ rand(n);                                                                                                            

julia> model  = Projections.Simplex(q, lb, ub);                                                                                     

julia> p1 = Projections.solve(Our(), model);                                                                                       

julia> p2 = Projections.solve(General(), model);                                                                                     

julia> LinearAlgebra.norm(p1 - p2)                                                                                                   
2.9749633079816928e-8

---

If you have used Projections in a scientific project that lead to a publication, we'd appreciate you citing the paper associated with it:

@article{adam2020projections,
  author = {L. Adam and V. Mácha},
  title = {Projections onto the canonical simplex with additional linear inequalities},
  journal = {Optimization Methods and Software},
  pages = {1-29},
  year  = {2020},
  publisher = {Taylor & Francis},
  doi = {10.1080/10556788.2020.1797023},
  URL = {https://doi.org/10.1080/10556788.2020.1797023},
}