Projections onto the canonical simplex with additional linear inequalities

2019/05/09 by Lukáš Adam, Adam, L., Václav Mácha +1 · 1 citation
Decision Sciences · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Risk and Portfolio Optimization #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.1905.03488

openalex publication_date 2019/05/09 · openalex created_date 2019/05/16 · openalex updated_date 2026/07/28

Abstract

We consider the distributionally robust optimization and show that computing the distributional worst-case is equivalent to computing the projection onto the canonical simplex with additional linear inequality. We consider several distance functions to measure the distance of distributions. We write the projections as optimization problems and show that they are equivalent to finding a zero of real-valued functions. We prove that these functions possess nice properties such as monotonicity or convexity. We design optimization methods with guaranteed convergence and derive their theoretical complexity. We demonstrate that our methods have (almost) linear observed complexity.

Citations

• A Simplex Method for Function Minimization
• Fast projection onto the simplex and the \pmb l_\mathbf 1 l 1 ball
• Distributionally Robust Stochastic Optimization with Wasserstein Distance

Cited by

• Fairness-aware PageRank via Edge Reweighting

Related

• Splitting Algorithms for Distributionally Robust Optimization
• Fast projection onto the intersection of simplex and singly linear constraint and its generalized Jacobian
• Distributionally Robust Optimization via Iterative Algorithms in Continuous Probability Spaces
• Distributionally Robust Optimization with Polynomial Robust Constraints
• Sinkhorn Distributionally Robust Optimization