Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions |
| |
Authors: | Satoru Fujishige |
| |
Institution: | (1) Institute of Socio-Economic Planning, University of Tsukuba, 305 Sakura, Ibaraki, Japan |
| |
Abstract: | We consider submodular programs which are problems of minimizing submodular functions on distributive lattices with or without
constraints. We define a convex (or concave) conjugate function of a submodular (or supermodular) function and show a Fenchel-type
min-max theorem for submodular and supermodular functions. We also define a subgradient of a submodular function and derive
a necessary and sufficient condition for a feasible solution of a submodular program to be optimal, which is a counterpart
of the Karush-Kuhn-Tucker condition for convex programs.
This work is supported by the Alexander von Humboldt fellowship (1982/83), West Germany. |
| |
Keywords: | Submodular functions Supermodular functions Subgradients Fenchel's Duality Theorem Karush-Kuhn-Tucker Condition |
本文献已被 SpringerLink 等数据库收录! |