Record Details

On set functions that can be extended to convex functionals

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title On set functions that can be extended to convex functionals
 
Creator NARAYANAN, H
 
Subject discrete convexity
submodular functions
hahn-banach separation theorem
 
Description A set function f : 2(S) is said to be polyhedrally tight (pt) (dually polyhedrally tight (dpt)) iff in the set polyhedron (dual set polyhedron) denoted by P-f (P-f) defined by x(M) = f (X) for all X subset of S every inequality can be satisfied as an equality (not necessarily simultaneously). We show that these are precisely the set functions that can be extended to convex (concave) functionals over R-+(S). We characterize such functions and show that if they have certain additional desirable properties, they are forced to become submodular/supermodular. We study pt and dpt functions using the notion of a legal dual generator (LDG) structure which is a refinement of the sets of generator vectors of the dual cones associated with the faces of the set polyhedron. We extend f (g) to convex and concave functionals on R-S by f(cup)(c) equivalent to max(x is an element of Pf) c(T)x, g(cap)(c) equivalent to min (g)(x is an element of P) c(T)x. We then show a refinement (in terms of LDG) of the following discrete separaton theorem. Theorem 0.1. If f is polyhedrally tight, g is dually polyhedrally tight and f >= g and P-f and P-g have the same dual cones associated with their faces, then f(cup) >= g(cap) and there exists a modular function h s.t. f >= h >= g.
 
Publisher ELSEVIER SCIENCE INC
 
Date 2011-07-27T10:41:01Z
2011-12-26T12:56:49Z
2011-12-27T05:46:07Z
2011-07-27T10:41:01Z
2011-12-26T12:56:49Z
2011-12-27T05:46:07Z
2005
 
Type Article
 
Identifier LINEAR ALGEBRA AND ITS APPLICATIONS, 402(), 74-100
0024-3795
http://dx.doi.org/10.1016/j.laa.2004.12.008
http://dspace.library.iitb.ac.in/xmlui/handle/10054/7202
http://hdl.handle.net/10054/7202
 
Language en