On Unconstrained Quasi-Submodular Function Optimization


  • Jincheng Mei Shanghai Jiao Tong University
  • Kang Zhao Shanghai Jiao Tong University
  • Bao-Liang Lu Shanghai Jiao Tong University




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 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.




How to Cite

Mei, J., Zhao, K., & Lu, B.-L. (2015). On Unconstrained Quasi-Submodular Function Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9359



AAAI Technical Track: Heuristic Search and Optimization