Projections onto the canonical simplex with additional linear inequalities

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.

Keywords:

• Projection
• simplex
• distributionally robust optimization
• linear observed complexity

2010 Mathematics Subject Classifications:

• 90C20
• 49M05
• 65K10
• 49K10

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 https://github.com/VaclavMacha/Projections.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [grant number 61850410534], Guangdong Provincial Key Laboratory [grant number 2020B121201001], the Program for Guangdong Introducing Innovative and Enterpreneurial Teams [grant number 2017ZT07X386], the Grant Agency of the Czech Republic (18-21409S) and by the OP RDE (OP VVV) funded project Research Center for Informatics, reg. No: CZ02.1.01/0.0./0.0./16_019/0000765.