A Characterization of Simultaneous Optimization, Majorization, and (Bi-)Submodular Polyhedra

Martijn H. H. Schoot Uiterkamp ()
Additional contact information
Martijn H. H. Schoot Uiterkamp: Department of Econometrics and Operations Research, Tilburg University, 5000 LE Tilburg, Netherlands

Mathematics of Operations Research, 2025, vol. 50, issue 1, 252-276

Abstract: Motivated by resource allocation problems (RAPs) in power management applications, we investigate the existence of solutions to optimization problems that simultaneously minimize the class of Schur-convex functions, also called least-majorized elements. For this, we introduce a generalization of majorization and least-majorized elements, called ( a , b )-majorization and least ( a , b )-majorized elements, and characterize the feasible sets of problems that have such elements in terms of base and (bi-)submodular polyhedra. Hereby, we also obtain new characterizations of these polyhedra that extend classical characterizations in terms of optimal greedy algorithms from the 1970s. We discuss the implications of our results for RAPs in power management applications and derive a new characterization of convex cooperative games and new properties of optimal estimators of specific regularized regression problems. In general, our results highlight the combinatorial nature of simultaneously optimizing solutions and provide a theoretical explanation for why such solutions generally do not exist.

Keywords: Primary: 90C27; secondary: 62J07; 91A12; 91B32; simultaneous optimization; majorization; Schur convexity; least-majorized element; submodular polyhedra; bisubmodular polyhedra; resource allocation problem; convex cooperative game; regularized regression (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2023.0054 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:1:p:252-276

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().