Convexity and Optimization of Condense Discrete Functions

摘要

A function with one integer variable is defined to be integer convex by Fox [3] and Denardo [1] if its second forward differences are positive. In this paper, condense discrete convexity of nonlinear discrete multivariable functions with their corresponding Hessian matrices is introduced which is a generalization of the integer convexity definition of Fox [3] and Denardo [1] to higher dimensional space Z~n. In addition, optimization results are proven for C~ 1 condense discrete convex functions assuming that the given condense discrete convex function is C~1. Yiiceer [17] proves convexity results for a certain class of discrete convex functions and shows that the restriction of the adaptation of Rosen-brook's function from real variables to discrete variables does not yield a discretely convex function. Here it is shown that the adaptation of Rosenbrook's function considered in [17] is a condense discrete convex function where the set of local minimums is also the the set of global minimums.