Fenchel Duality Theorem in Discrete Convex Analysis and its Application

Please enable javascript in your browser.

This page was sent successfuly

Bookmark

1253 viewed

قضیه دوگانی فنچل در آنالیز محدب گسسته و کاربرد آن

59 Viewed

Type of Document: M.Sc. Thesis
Language: Farsi
Document No: 58637 (02)
University: Sharif University of Technology
Department: Mathematical Sciences
Advisor(s): Boroojeni, Javad Ebrahimi
Abstract:
In this thesis, we study the Fenchel duality theorem within the framework of Discrete Convex Analysis and its applications. The Fenchel duality theorem in the continuous case is a minimax theorem, which states that to obtain the optimal value on one side, one can solve the other side, or show that the solution to the minimization problem is equal to the solution of the maximization problem. In this theorem, one of the functions is convex and the other is concave. The discrete version of the Fenchel duality theorem is defined over the integers, and it applies to special classes of functions: one being an integer convex function and the other a separable concave function. The importance of this theorem lies in the fact that, in general, duality theorems do not hold for integer programming problems. In the final part, we examine an application of the discrete Fenchel duality theorem for bisubmodular functions
Keywords:
Fenchel Duality ; Discrete Convex Analysis ; Bisubmodular Function ; Integrally Convex Function