论文标题
同时优化，多数化和（BI）次生polyhedra的表征
A characterization of simultaneous optimization, majorization, and (bi)submodular polyhedra
论文作者
论文摘要
在电力管理应用程序中的资源分配问题（RAP）的激励中，我们研究了解决优化问题的解决方案，以同时最大程度地减少整个目标功能。从经验上看，对于大多数优化问题而言，这种解决方案并不存在。但是，对于为什么是这样的情况以及是否存在确实具有这种解决方案的问题的表征，知之甚少。在本文中，我们通过将同时优化Schur-Convex函数类别（称为最少主要元素）的解决方案的存在联系起来，回答了这些问题。为此，我们介绍了主要化和最少的主要元素的概括，称为$（a，b）$ - $ - $（a，b）$ - 主要元素，并表征了可行的一组问题，这些问题与这些polyhedra有关。在此，我们还获得了基础和双型多面体的新特征，这些特征是根据1970年代线性优化的最佳贪婪算法来扩展这些集合的经典特征。我们讨论了我们的结果对公共电力管理应用程序中的说唱的含义，并使用结果来得出凸合作游戏的新表征以及特定正规回归问题的最佳估计量的新属性。通常，我们的结果突出了同时优化解决方案的组合性质，同时为观察到这种解决方案通常不存在的理论解释提供了理论上的解释。
Motivated by resource allocation problems (RAPs) in power management applications, we investigate solutions to optimization problems that simultaneously minimize an entire class of objective functions. It is straightforward to show empirically that such solutions do not exist for most optimization problems. However, little is known on why this is the case and whether a characterization exists of problems that do have such solutions. In this article, we answer these questions by linking the existence of solutions that simultaneously optimize the class of Schur-convex functions, called least majorized elements, to (bi)submodular functions and the corresponding polyhedra. 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 these polyhedra. Hereby, we also obtain new characterizations of base and bisubmodular polyhedra that extend classical characterizations of these sets in terms of optimal greedy algorithms for linear optimization from the 1970s. We discuss the implications of our results for RAPs in power management applications and use the results to 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, at the same time, provide a theoretical explanation for the observation that such solutions generally do not exist.
