On Unconstrained Quasi-Submodular Function Optimization
For researchers in combinatorial optimization, this work provides a theoretical and algorithmic foundation for optimizing a broader class of functions, though the results are incremental as they extend existing submodular optimization techniques.
The paper addresses unconstrained optimization of quasi-submodular functions, a generalization of submodularity. It proposes algorithms for minimization and maximization that return reduced lattices in O(n) iterations with strict monotonicity, and experimental results confirm their effectiveness and efficiency.
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 {\em 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 $\mathcal{O}(n)$ 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.