With the extensive application of submodularity, its generalizations are constantly being proposed. However, most of them are tailored for special problems. In this paper, we focus on quasi-submodularity, a universal generalization, which satisfies weaker properties than submodularity but still enjoys favorable performance in optimization. Similar to the diminishing return property of submodularity, we first define a corresponding property called the single sub-crossing , then we propose two algorithms for unconstrained quasi-submodular function minimization and maximization, respectively. The proposed algorithms return the reduced lattices in @math iterations, and guarantee the objective function values are strictly monotonically increased or decreased after each iteration. Moreover, any local and global optima are definitely contained in the reduced lattices. Experimental results verify the effectiveness and efficiency of the proposed algorithms on lattice reduction.
Quasi-supermodularity stems from economic fields. Milgrom and Shannon @cite_10 first propose the definition of quasi-supermodularity. They find that the maximizer of a quasi-supermodular function is monotone as the parameter changes. In combinatorial optimization, for quasi-submodular functions, this property means the set of minimizers has a nested structure, which is the foundation of the proposed UQSFMin algorithm. Based on the theorem above, suppose we start from @math , if @math , @math , then we can set @math . This theorem ensures that there exists a chain structure of minimizers. This is a general principle. First, it works in submodular cases, for submodularity is a strict subset of quasi-submodularity. Moreover, when the superdifferential in @cite_21 is not superdifferential for non-submodular quasi-submodular functions, such as the determinant function and the multiplicatively separable functions, this principle can also hold. In @cite_10 , only quasi-submodular function minimization (or equivalently, quasi-supermodular function maximization) is considered. For quasi-submodular function maximization, there is no existing study.
@cite_21 @cite_10
2951977866 2045665199
We present a practical and powerful new framework for both unconstrained and constrained submodular function optimization based on discrete semidifferentials (sub- and super-differentials). The resulting algorithms, which repeatedly compute and then efficiently optimize submodular semigradients, offer new and generalize many old methods for submodular optimization. Our approach, moreover, takes steps towards providing a unifying paradigm applicable to both submodular min- imization and maximization, problems that historically have been treated quite distinctly. The practicality of our algorithms is important since interest in submodularity, owing to its natural and wide applicability, has recently been in ascendance within machine learning. We analyze theoretical properties of our algorithms for minimization and maximization, and show that many state-of-the-art maximization algorithms are special cases. Lastly, we complement our theoretical analyses with supporting empirical experiments. The authors derive a necessary and sufficient condition for the solution set of an optimization problem to be monotonic in the parameters of the problem. In addition, they develop practical methods for checking the condition and demonstrate its applications to the classical theories of the competitive firm, the monopolist, the Bertrand oligopolist, consumer and growth theory, game theory, and general equilibrium analysis. Copyright 1994 by The Econometric Society.