Note on Steepest Descent Algorithm for Quasi L^\natural-convex Function Minimization

2023/07/21 by Kazuo Murota, Akiyoshi Shioura, Murota, Kazuo +1
Computer Science · Engineering · Mathematics · #52A41 #90C25 #90C27 #Advanced Optimization Algorithms Research #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2307.11491

openalex publication_date 2023/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We define a class of discrete quasi convex functions, called semi-strictly quasi L^\natural-convex functions, and show that the steepest descent algorithm for L^\natural-convex function minimization also works for this class of quasi convex functions. The analysis of the exact number of iterations is also extended, revealing the so-called geodesic property of the steepest descent algorithm when applied to semi-strictly quasi L^\natural-convex functions.

Related

• Note on Minimization of Quasi M^\natural-convex Functions
• Steepest Descent Algorithm for M-convex Function Minimization Using Long Step Length
• Accelerated Methods for α-Weakly-Quasi-Convex Problems
• Scaling, Proximity, and Optimization of Integrally Convex Functions
• Revisit First-order Methods for Geodesically Convex Optimization