A Note on Zeroth-Order Optimization on the Simplex

Resource allocation, mechanism design, load balancing, strategic classification, and many other problems with economic incentives require optimizing an objective function on the simplex. The simplex constraint can describe a fixed load to be distributed [6], a constraint on the budget to be allocated [7], or a distribution over actions individuals can take [9]; see Bomze [1] and De Klerk [3] for a survey on simplex optimization with applications. Moreover, these optimization problems often have to be solved using only zeroth-order feedback, i.e., function evaluations at different points on the simplex, as gradient feedback is not easily obtainable. There are a number of methods for zeroth-order optimization (e.g.