Robust Data-Driven Quasi-Concave Optimization

We investigate a data-driven quasi-concave maximization problem where information about the objective function is limited to a finite sample of data points. We begin by defining an ambiguity set for admissible objective functions based on available partial information about the objective. This ambiguity set consists of those quasi-concave functions that majorize a given data sample and that satisfy additional functional properties (monotonicity, Lipschitz continuity, and permutation invariance). We then formulate a robust optimization (RO) problem that maximizes the worst-case objective function over this ambiguity set. Based on the quasi-concave structure in this problem, we explicitly construct the upper-level sets of the worst-case objective at all levels. We can then solve the resulting RO problem efficiently by doing binary search over the upper-level sets and solving a logarithmic number of convex feasibility problems. This numerical approach differs from traditional sub-gradient descent and support function-based methods for this problem class. Although these methods can be applied in our setting, the binary search method displays superb finite convergence to the global optimum, whereas the others do not. This is primarily because binary search fully exploits the specific structure of the worst-case quasi-concave objective, which leads to an explicit and general convergence rate in terms of the number of convex optimization problems to be solved. Our numerical experiments on a Cobb-Douglas production efficiency problem and a fair resource allocation problem demonstrate the tractability of our approach.

History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous.

Funding: This research was supported by the National Natural Science Foundation of China Young Scientist Fund [72201224] and Hong Kong Research Grants Council, University Grants Committee General Research Fund [17211325].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1570) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1570). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.