2625. Special implementation of steepest descent algorithm for M-natural-convex function minimization and related problems
Invited abstract in session WC-15: Topics in Combinatorial Optimization 1, stream Combinatorial Optimization.
Wednesday, 12:30-14:00Room: Esther Simpson 1.08
Authors (first author is the speaker)
| 1. | Norito Minamikawa
|
| Faculty of Science and Technology, Seikei University |
Abstract
The concept of M-natural-convex function gives a unified framework for discrete optimization problems with nonlinear objective functions, such as the minimum convex cost flow problem and the convex resource allocation problem. We consider M-natural-convex function minimization, one of the most fundamental problems concerning discrete convex analysis, and related problems. In this talk, we present some properties of the steepest descent algorithm for the class of M-natural-convex functions and a more general classes of discrete convex functions called jump M-natural-convex functions and quasi-M-natural-convex-functions. We show that a special implementation of the steepest descent algorithm enjoys the geodesic property. This implies that the trajectory of the solutions generated by the algorithm follows the shortest path to the nearest optimal solution.
Keywords
- Combinatorial Optimization
- Algorithms
- Mathematical Programming
Status: accepted
Back to the list of papers