Note on Minimization of Quasi M^\natural-convex Functions

2023/05/29 by Kazuo Murota, Akiyoshi Shioura, Murota, Kazuo +1
Computer Science · #Optimization and Variational Analysis

paper · pdf · doi:10.48550/arxiv.2305.17849

Abstract

For a class of discrete quasi convex functions called semi-strictly quasi M^\natural-convex functions, we investigate fundamental issues relating to minimization, such as optimality condition by local optimality, minimizer cut property, geodesic property, and proximity property. Emphasis is put on comparisons with (usual) M^\natural-convex functions. The same optimality condition and a weaker form of the minimizer cut property hold for semi-strictly quasi M^\natural-convex functions, while geodesic property and proximity property fail.

Related

• Note on Steepest Descent Algorithm for Quasi L^\natural-convex Function Minimization
• X-convexity and Applications of Quasi-X-Convex Functions
• A Practical Approach to Quasi-convex Optimization
• Scaling, Proximity, and Optimization of Integrally Convex Functions
• Directed Discrete Midpoint Convexity