Maximization of the Choquet integral over a convex set and its application to resource allocation problems |
| |
Authors: | Mikhail Timonin |
| |
Affiliation: | 1. National Nuclear Research University MEPhI, 31 Kashirskoe Shosse, Moscow, 115409, Russian Federation
|
| |
Abstract: | We study the problem of the Choquet integral maximization over a convex set. The problem is shown to be generally non-convex (and non-differentiable). We analyze the problem structure, and propose local and global search algorithms. The special case when the problem becomes concave is analyzed separately. For the non-convex case we propose a decomposition scheme which allows to reduce a non-convex problem to several concave ones. Decomposition is performed by finding the coarsest partition of a capacity into disjunction of totally monotone measures. We discuss its effectiveness and prove that the scheme is optimal for 2-additive capacities. An application of the developed methods to resource allocation problems concludes the article. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|