Optimization of linear-convex programs

Let U∈Rni and V∈Rn2 be bounded polyhedral sets. Let f: U x L→R Consider the minimization of f(u,v) subject to u∈U, v∈V. For fixed v,f is linear in u and for fixed u∈U it is convex in v. If f is the global minimum function value, then there is at least one vertex u*∈U such that f* -f(u*, v*) for some v* We characterize KARUSH-KUHN-TUCKER and local minimum points of the problem. An algorithm is proposed where convexity cuts are developed from extreme points of V. To insure finite convergence, another type of cuts “facial cuts” are used. We propose a shallow facial cut that requires negligible computation. Finally, we give rules for deleting redundant shallow facial cuts.